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

Основной принцип алгоритма сортировки по глубине, или алгоритма художника (depth-sorting, painter’s algorithm), можно представить следующим образом. Поверхности объектов сортируются по удаленности от наблюдателя и заполняются соответствующими цветами, начиная с самой дальней. В результате закрашивания поверхностей в данной последовательности дальние поверхности автоматически скрываются ближними, если они проецируются в одну и ту же область экрана. Таким образом, алгоритм художника работает как алгоритм удаления невидимых поверхностей.

Расстояние от поверхности до наблюдателя определяется z-координатамн точек на этой поверхности в наблюдательской системе координат. Точка с большей координатой Z,, считается находящейся ближе к наблюдателю1. Здесь и далее z-ко- ордината в наблюдательской системе координат будет обозначаться Zv. Значит, остается только сравнить координаты Zv.. всех поверхностей и отобразить их, начиная с поверхности с наименьшим значением Zv..

 
Легко сравнивать координаты Zv. поверхностей, если максимальное значение Zv. одной из них меньше минимального значения Zv. другой. Однако в большинстве случаев диапазон значений Zv. точек одной поверхности перекрывается с диапазоном Zv. другой поверхности. Неоднозначности можно избежать, разбивая все поверхности на отдельные части до тех пор, пока диапазоны Zv. не перестанут перекрываться. Есть и другой, более простой в реализации способ решения проблемы. Все поверхности преобразуются в наборы небольших треугольников таким образом, чтобы диапазоны Zv. разных треугольников не перекрывались друг с другом, после чего треугольники окрашиваются в соответствующие цвета в нужной последовательности. Чем меньше размер треугольников, тем меньше шансов, что их диапазоны Zv. перекроются. Такое приближение поверхности объекта называется триангуляцией (triangulation) или фасетированием.
 
 
 

1 В OpenGL точки с большими Zv., находятся дальше от наблюдателя, поскольку эта библиотека основана на левосторонней наблюдательской системе координат.

Смотрите также