Подход, основанный на анализе пространства изображения, имеет много общего с моделированием процесса визуализации с помощью приведения лучей (рис. 7.28). Рассмотрим луч, исходящий из центра проецирования и проходящий через определенный пиксель на картинной плоскости. Этот луч где-то пересекается с плоскостью каждого из к многоугольников. Мы можем вычислить координаты этих точек, выяснить, лежит ли точка пересечения во внутренней области многоугольника, и затем выбрать тот многоугольник, который первым пересекается этим лучом. Этот пиксель затем можно окрасить в цвет, который присвоен точке пересечения с выбранным многоугольником после выполнения тонирования. Если размер видового окна изображения пх т пикселей, то такая операция должна быть повторена птк раз4, т.е. оценка сложности имеет вид О(к). Полученная оценка является оценкой сверху, но в любом случае тот факт, что сложность процедуры при таком подходе пропорциональна количеству объектов, а не квадрату этого количества заставляет нас отдать предпочтение анализу видимости в пространстве изображения5. Но следует учесть, что работа на уровне отдельных пикселей может привести к образованию зубцов на границах, разделяющих изображения отдельных объектов, что не свойственно алгоритмам, работающим в пространстве объектов.
''При необходимости повысить качество изображения можно "пропустить " через один пиксель не один, а несколько лучей и каким-то способом суммировать результаты.
5Иа практике алгоритмы удаления невидимых поверхностей, работающие в пространстве изображения, справляются с задачей, не перебирая все объекты для каждого луча (см. упр. 7.9).
Алгоритмы формирования изображения
Рис. 7.28. Удаление невидимых поверхностей в пространстве изображения
7.7.1. Удаление нелицевых граней
Рис. 7.29. Анализ лицевой грани В главе 6 отмечалось, что в OpenGL можно задавать режим тонирования только внешних граней многоугольников. Если сцена состоит только из выпуклых многогранников, то внутренние грани многоугольников никогда не будут "показываться на глаза" наблюдателю. Но у такого выпуклого многогранника часть граней будет повернута от наблюдателя (так называемые нелицевые грани) и, следовательно, тоже не будет видна наблюдателю. В конце концов, нелицевые грани будут перекрыты другими, и это сможет выявить универсальный алгоритм удаления невидимых поверхностей, но можно облегчить ему работу, сразу же отбраковав нелицевые грани. Принцип отбраковки {culling) нелицевых граней поясняется на рис. 7.29. Внешняя сторона многоугольника будет видима наблюдателю только в том случае, если нормаль к плоскости многоугольника будет направлена к наблюдателю. Обозначим через 8 угол между внешней нормалью плоскости многоугольника и направлением на наблюдателя, тогда многоугольник будет представлять лицевую грань объекта только в том случае, если -90° < 6 < 90°, или, что то же самое, если cos6 > 0.