10.4.3.1. Метод сортировки по глубине. Алгоритм художника Этот метод является самым простым из методов, основанных на упорядочении граней. Как художник сначала рисует более далекие объекты, а затем поверх них более близкие, так и метод сортировки по глубине сначала упорядочивает грани по мере приближения к наблюдателю, а затем выводит их в этом порядке.
Метод основывается на следующем простом наблюдении: если для двух граней А и В самая дальняя точка грани А ближе к наблюдателю (картинной плоскости), чем самая ближняя точка грани В, то грань В никак не может закрыть грань А от наблюдателя.
Поэтому если заранее известно, что для любых двух лицевых граней ближайшая точка одной из них находится дальше, чем самая дальняя точка другой, то для упорядочения граней достаточно просто отсортировать их по расстоянию от наблюдателя (картинной плоскости).
Однако такое не всегда возможно: могут встретиться такие пары граней, что самая дальняя точка одной находится к наблюдателю не ближе, чем самая близкая точка другой.
10. Удаление невидимых линий и поверхностей На практике часто встречается следующая реализация этого алгоритма: множество всех лицевых граней сортируется по ближайшему расстоянию до картинной плоскости (наблюдателя) и потом эти грани выводятся в порядке приближения к наблюдателю. В качестве алгоритмов сортировки можно использовать либо быструю сортировку, либо поразрядную (radix sort).
Метод хорошо работает для целого ряда типичных сцен, включая, например, построение изображения нескольких непересекающихся простых тел.
Приведенная ниже программа осуществляет построение изображения тора на основе этого метода. Тор, описываемый уравнениями х = (R + rcosfycos %
y=(R + rsin ф)С05' <р,
z = rsin<j),представляется в виде набора треугольных граней. После этого для сортировки граней по расстоянию до наблюдателя используется стандартная процедура qsort.
Расстояние от точки р до наблюдателя, расположенного в начале координат, при параллельном проектировании вдоль единичного вектора / задается следующей формулой: d=(p, Г).