Нарисовать картинку с системой координат

Если многогранник является выпуклым и он один в сцене, то задача удаления невидимых граней т.о. решается полностью.

Данный подход не решает проблему удаления невидимых линий.

Метод оптимизации «Применение ограничивающих тел».

Вокруг каждого объекта создается ограничивающее тело простого вида. Если тела не пересекаются, то и объекты, находящиеся внутри них не пересекаются. В качестве ограничивающих тел чаще всего используют прямоугольные параллелепипед с ребрами параллельными координатным. (Xmin, Ymin, Zmin) (Xmax, Ymax, Zmax)

Проверка на пересечение тел сводится к проверке на пересечение промежутков

[Xmin, Xmax], [Ymin, Ymax], [Zmin, Zmax] для одного и другого тела. Если сравнение хотя бы одной из пар промежутков пусто, то объекты не пересекаются. Ограничивающие тела можно построить и для проекций объектов. Ограничивающие тела можно строить вокруг группы объектов или даже отдельных граней.

Метод оптимизации «Разбиение пространства или плоскости».

Типы когерентности:

1. когерентность картинной плоскости – если данный пиксель соответствует точке некоторой грани, то скорее всего соседний пиксель также соответствует точкам той же грани;

2. когерентность в пространстве объектов – если данный объект (грань) видим (не видим), то расположенные рядом объекты (грани) скорее всего также являются видимыми (не видимыми).

3. временная когерентность (в случае анимации) – грани видимые в данном кадре скорее всего будут видим и в следующем (аналогично – не видимые).

Строится разбиение пространства и для каждой клетки разбиения составляется список всех объектов, которые ее пересекают. Простейший способ – равномерное разбиения. Для сцен с неравномерным распределением объектов, используется не равномерное (адаптивное) разбиение пространства.

При использовании разбиения картинной плоскости каждой клетке разбиения ставится в соответствие список тех объектов, проекции которых данную плоскость пересекают.

Метод оптимизации «Иерархические структуры».

1. Иерархия ограничивающих тел. Ограничивающееся тело описывается вокруг всех объектов. На следующем шаге объекты разбиваются на несколько групп вокруг каждой из них описывается свое ограничивающее тело и т.д. В результате получается дерево, корнем которого является тело, ограничивающее всю сцену. Тела описанные вокруг первичных групп образуют первичных потомков, вокруг вторичных групп – вторичных и т.д.

2. Иерархическая структура на основе разбиения пространства (картинной плоскости). Каждая клетка исходного разбиения на части, которые тоже могут быть разбиты на части.

Иерархические структуры позволяют упорядочить грани, производить их отсечение.

Удаление невидимых линий.

Работает в объектном пространстве.

Алгоритм Робертса. Требует, чтобы каждая грань была выпуклым многоугольником.

1. Из каждого тела удаляются те грани и ребра, которые экранируются (закрываются) самим телом.

2. Каждое из видимых ребер каждого тела сравнивается с каждым из оставшихся тел, для определения того, какая его часть или части экранируются этими телами.

Удаление невидимых граней.