Основные схемы представления объемных тел. Методы пространственного перечисления. Восьмеричные деревья

Твердое тело разбивается на множество смежных, непересекающихся более примитивных твердых тел, причем необязательно того же типа, что и исходное тело. Примитивы могут различаться типом, размером, позицией, параметризацией, ориентацией. Восьмеричные деревья - это иерархический вариант пространственного разбиения, позволяющий резко сократить использование памяти. На плоскости - квадратичные деревья. Фундаментальный подход, служащий основой этого представления, - двоичное разбиение по принципу “разделяй и властвуй”.

Каждый квадрант для quadtrees и октант для octrees получает свой номер и может быть полным, частично полным или пустым. Последовательное разбиение производится до достижения однородности всех потомков данного отца (т.е. все потомки либо пустые, либо полные. Когда эти 4 или 8 детей - однородны - они снова замещаются одним соответствующим родителем. Такое представление иногда называют адаптивным, т.к. оно как бы настраивается само на разную плотность заполения объектом пространства в разных его местах.

Разработаны специальные алгоритмы для выполнения теоретико-множественных операций и других преобразований основанные на прохождении деревьев снизу вверх параллельно для обоих объектов-аргументов).

Дискретные геометрические модели.

Перечисление по пространственной занятости- э то специальный случай разбиения на ячейки, в которой твердое тело разбивается на идентичные ячейки, называемые вокселами, располагающиеся в фиксированном регулярном порядке, по аналогии с пикселами. Наиболее используемый тип ячейки - куб. Чтобы представить объект, каждый воксель считается либо “занятым”, либо - нет. Ясно, что в общем случае тела аппроксимируются; нет понятия частичной занятости вокселов; высоки требования к памяти. Тем не менее, это ведущее представления для экспериментальных данных (volumetric data), в частности, в биомедицинских (томография) исследованиях.