Рис. 7.32. Алгоритм маляра: а - два многоугольника и наблюдатель; б - многоугольник А частично закрывает от наблюдателя многоугольник В
*Некоторые прикладные проблемы можно решить обратным методом - отображением многоугольников от ближнего к дальнему (ТгопЫо-Ьаск гепскпп^. Эту тему мы затронем в главе 12.
Алгоритмы формирования изображения
удаления от наблюдателя, причем в качестве основного параметра сортировки берется максимальное значение координаты г-оболочки. Именно эта операция и дала название всему алгоритму- сортировка по глубине {depth sort). Предположим, что после сортировки многоугольники "выстроились" в порядке, показанном на рис. 7.33. По оси ординат на этом рисунке отложены значения параметров z-оболочек. Если минимальная глубина - значение гт1п - для данного многоугольника больше, чем максимальная глубина следующего за ним многоугольника, то после формирования их образов на экране в обратном порядке будет получено вполне корректное изображение сцены. Например, многоугольник А на рис. 7.33 расположен позади всех остальных, и его образ следует формировать первым. Но, к сожалению, в других случаях дело обстоит гораздо сложнее, и одними значениями параметров г-оболочек не обойтись.
Если z-оболочки двух многоугольников перекрываются, то порядок формирования их образов выявляется индивидуальным сравнением каждой пары таких объектов. В алгоритме сортировки по глубине для этого используется множество довольно сложных проверок. Рассмотрим пару многоугольников, z-оболочки которых перекрываются (рис. 7.34). Первой выполняется самая простая проверка- сравнение х- и у-оболочек (рис. 7.34,а). Если либо х-, либо у-оболочки не перекрываются, многоугольники не закрывают друг друга с точки зрения наблюдателя и порядок формирования их образов не имеет значения9. Но и в случае, если х- или у-оболочки перекрываются, можно отыскать порядок формирования их образов, который позволит корректно воспроизвести сцену на экране. Такой случай показан на рис. 7.35. Все вершины одного многоугольника лежат по одну сторону от плоскости