Достоинства и недостатки метода двоичного разбиения пространства

Метод двоичного разбиения пространтва

Достоинства и недостатки алгоритма художника

Проблемы алгоритма художника

Пошаговое выполнение алгоритма художника

Алгоритм художника

Сформировать предварительный список приоритетов по глубине, используя в качестве ключа сортировки значение zmin для каждого многоугольника.

Характеристика удаленности для грани ABC - это среднее значени Z, mid_z = (A.z + B.z + C.z) / 3

Упорядочить все многоугольники в соотвествии с наименьшей (дальней) координатой z.

Разрешить неоднозначности, которые вызывают наложение z-габаритов.

Нарисовать многоугольники в порядке возрастания наименьшей координаты z.

- при некотором расположении граней этот алгоиртм вообще не может дать правильного результата в каком порядке грани не рисуй, получится неправильно.

- при некотором расположении граней и использовании среднего значения z как характеристики удаленности алгоритм тоже дает неправильный результат.

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

- + Явно соритурет все грани сцены в порядке их приближения к наблюдателю, выводит грани в этом порядке, в итоге получается корректное изображение

- - линейная сложность сортировки

- - квадратичная сложность для многоугольников с пересекающимся z-объемами

- - не может справиться со всеми типами взаимного расположения

Ни одна из граней, лежащих в том же полупространстве, что и наблюдатель, не может быть закрыта ни одной из граней из другого полупространства.

В связи с этим выполняется частичное упорядочевание граней исходя из возможности загораживания друг друга.

- + логарифмичсеская сложность сортировки объектов по глубине (быстро работает), позволяет быстро выводить полигоны back-to-front

- - проблемы, аналогичные алгоритму художника

- - работает для статических сцен, дерево перестраивается долго

Алгоритм сортировки по глубине (z-буфера)

Общее правило при использовании z-буфера: Если при вычерчивании на экране пикселя расстояне от него до соответствующей ему точки — прототипа меньше, чем значение, хранящееся в z-буфере для этого пикселя, то точка вычерчивается, а в Z-буфер заносится новое (меньшее) значение. Если же расстояние до прототипа больше, чем Z-значение для данного пикселя, то точка игнорируется (пиксель сохраняет прежний цвет).