Очень распространенной структурой данных в задачах удаления невидимых линий и поверхностей являются различные тины деревьев -двоичные (BSP-trees), четверичные (Quadtrees), восьмеричные (Octtrees) и др.
Методы, практически применяющиеся в настоящее время, в большинстве являются комбинациями ряда простейших алгоритмов, неся в себе целый ряд разного рода оптимизаций.
Крайне важную роль в повышении эффективности методов удаления невидимых линий и граней играет использование когерентности (coherence, связность). Выделяют три типа когерентности:
Когерентность в картинной плоскости. Если данный пиксел соответствует точке грани Р, то скорее всего соседние пикселы также соответствуют точкам той же грани (рис. 2.4).
Когерентность в пространстве объектов. Если данный объект (грань) видим (невидим), то расположенный рядом объект (грань) скорее всего также является видимым (невидимым) (рис. 2.5).
А. В. Боресков. Гиафика трехмерной компьютерной игры
В случае построения анимации возникает третий тип когерентности -временная. Грани, видимые в данном кадре, скорее всего будут видимы и в следующем. Аналогично грани, невидимые в данном кадре, скорее всего будут невидимы также и в следующем.
Фактически применение когерентности заключается в использовании результатов, полученных для одних объектов (пикселов, кадров) для ускорения обработки других.
Аккуратное использование когерентности позволяет заметно сократить количество возникающих проверок и заметно повысить быстродействие алгоритма.
Методы оптимизации Отсечение нелицевых граней Рассмотрим многогранник, для каждой грани которого задан единичный вектор внешней нормали (рис. 2.6). Несложно заметить, что если вектор нормали грани п составляет с вектором /, задающим направление проектирования, тупой угол (вектор нормали направлен от наблюдателя), то эта грань заведомо не может быть видна (рис. 2.7). Такие грани называются нелицевыми. Если соответствующий угол является острым, Рис. 2.6 грань называется лицевой.
