8.9. Другие типы древовидных структур
Деревья и ориентированные ациклические графы являются не только мощным средством описания сцен, но и находят широкое применение при решении других проблем компьютерной графики. В этом разделе будут рассмотрены три из них: использование деревьев для описания структуры сложных сплошных (solid) объектов в рамках конструктивной геометрии тел и два подхода к описанию пространственной иерархии, которые позволяют значительно повысить эффективность алгоритмов отображения.
8.9.1. Деревья в конструктивной геометрии тел Полигональное представление геометрических объектов, которое мы использовали до сих пор, имеет не только множество достоинств, но и ряд недостатков. Наиболее серьезным из них является то, что многоугольники - базовый элемент полигонального представления - позволяют описывать только "оболочку" вокруг какого-либо объема, а не собственно объем. Этот недостаток особенно отчетливо проявляется в системах автоматизации проектирования, где проектировщика интересует не только внешняя форма объекта, но и его объемные свой8.9. Другие типы древовидных структур
ства - масса, моменты инерции и т.п. Кроме того, представление пространственного объекта при отображении ребрами или гранями может стать причиной неоднозначной интерпретации пользователем предъявляемого образа. Например, "проволочное" изображение объекта, представленное на рис. 8.20, можно интерпретировать и как куб, в котором высверлено отверстие, и как узел, составленный из двух деталей.
Конструктивная геометрия тел (CSG - constructive solid geometry) - направление в компьютерной графике, призванное решать подобные проблемы. В рамках этого направления в качестве примитивов используются сплошные геометрические тела канонических типов - параллелепипед, цилиндр, сфера и т.п. Атрибуты объектов включают как оптические свойства их поверхностей (фактуру, отражательные свойства, цвет и т.п.), так и объемные свойства- размеры и плотность. При описании сцены, состоящей из таких объектов, принимаются во внимание точки внутреннего подпространства, принадлежащего объектам, и, наоборот, объекты рассматриваются как совокупности (множества) определенных точек пространства, из которых (множеств) с помощью операций алгебры множеств можно формировать другие множества - новые объекты. Методика моделирования в конструктивной объемной геометрии основана на использовании трех основных операций апгебры множеств: