Трёхмерная компьютерная графика (стр. 10 из 12)

Альтернативой созданию специальной памяти для z-буфера является использование для этой цели оперативной или массовой памяти. Уменьшение требуемой памяти достигается разбиением пространства изображения на 4, 16 или больше квадратов или полос. В предельном варианте можно использовать z-буфер размером в одну строку развертки. Для последнего случая имеется интересный алгоритм построчного сканирования. Поскольку каждый элемент сцены обрабатывается много раз, то сегментирование z-буфера, вообще говоря, приводит к увеличению времени, необходимого для обработки сцены. Однако сортировка на плоскости, позволяющая не обрабатывать все многоугольники в каждом из квадратов или полос, может значительно сократить этот рост.

Другой недостаток алгоритма z-буфера состоит в трудоемкости и высокой стоимости устранения лестничного эффекта, а также реализации эффектов прозрачности и просвечивания.

Более формальное описание алгоритма z-буфера таково:

Заполнить буфер кадра фоновым значением интенсивности или цвета.

Заполнить z-буфер минимальным значением z.

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

Для каждого Пиксел(x, y) в многоугольнике вычислить его глубину z (x, y).

Сравнить глубину z (x, y) со значением Z буфер(x, y), хранящимися в z-буфере в этой же позиции.

Если z (x, y) > zбуфер (x, y), то записать атрибут этого многоугольника (интенсивность, цвет и т. п.) в буфер кадра и заменить z-буфер(x, y)на z (x, y).

В противном случае никаких действий не производить.

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

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

ax + by + cz + d =0

z = - ( ax + by + d)/c ¹ 0

Для сканирующей строки y = const. Поэтому глубина пиксела наэтой строке, у которого x = x + Dx, равна

z₁ - z = - (ax₁ + d)/c + (ax + d)/c = a(x - x₁)/c

или

z₁ = z – (a/c)Dx

Но Dx = 1, поэтому z₁ = - (а/с).

Алгоритм, использующий z-буфер, можно также применитьдля построения сечений поверхностей. Изменится только операторсравнения:

z(x, y) > z-буфер(x, y) andz(x, y) £Zсечения

где Zсечения - глубина искомого сечения. Эффект заключается втом, что остаются только такие элементы поверхности, которыележат на самом сечении или позади него.

Алгоритм определения видимых поверхностей путём трассировки лучей

Оценки эффективности всех алгоритмов удаления невидимых поверхностей, изложенных ранее, зависят от определенных характеристик когерентности той сцены, для которой ведется поиск ее видимых участков. В отличие от них трассировка лучей является методом грубой силы. Главная идея, лежащая в основе этого метода, заключается в том, что наблюдатель видит любой объект посредством испускаемого неким источником света, который падает на этот объект и затем каким-то путем доходит до наблюдателя. Свет может достичь наблюдателя, отразившись от поверхности, преломившись или пройдя через нее. Если проследить за лучами света, выпущенными источником, то можно убедиться, что весьма немногие из них дойдут до наблюдателя. Следовательно, этот процесс был бы вычислительно неэффективен. В следствии этого было предложено отслеживать (трассировать) лучи в обратном направлении, т. е. от наблюдателя к объекту, как показано на рис. 3.11. В первом алгоритме трассировка прекращалась, как только луч пересекал поверхность видимого непрозрачного объекта; т. е. луч использовался только для обработки скрытых или видимых поверхностей. С течением времени был реализован алгоритм трассировки лучей с использованием общих моделей освещения. Эти алгоритмы учитывают эффекты отражения одного объекта от поверхности другого, преломления, прозрачности и затенения. Производится также устранение ступенчатости.Рассмотрим применением метода трассировки лучей для определения видимых или скрытых поверхностей.

3.11. Простая трассировка лучей

Рис.3.11 служит иллюстрацией алгоритма трассировки лучей. В этом алгоритме предполагается, что сцена уже преобразована в пространство изображения. Перспективное преобразование не используется. Считается, что точка зрения или наблюдатель находится в бесконечности на положительной полуоси z. Поэтому все световые лучи параллельны оси z. Каждый луч, исходящий от наблюдателя, проходит через центр пиксела на растре до сцены. Траектория каждого луча отслеживается, чтобы определить, какие именно объекты сцены, если таковые существуют, пересекаются с данным лучом. Необходимо проверить пересечение каждого объекта сцены с каждым лучом.

3.12. Трассировка луча с учётом перспективы

Если луч пересекает объект, то определяются всевозможные точки пересечения луча и объекта. Можно получить большое количество пересечений, если рассматривать много объектов. Эти пересечения упорядочиваются по глубине. Пересечение с максимальным значением z представляет видимую поверхность для данного пиксела. Атрибуты этого объекта используются для определения характеристик пиксела.

Если точка зрения находится не в бесконечности, алгоритм трассировки лучей лишь незначительно усложняется. Здесь предполагается, что наблюдатель по-прежнему находится на положительной полуоси z. Картинная плоскость, т. е. растр, перпендикулярна оси z, как показано на рис 3.12. Задача состоит в том, чтобы построить одноточечную центральную проекцию на картинную плоскость.

Наиболее важным элементом алгоритма определения видимых поверхностей путем трассировки лучей, является процедура определения пересечений. В состав сцены можно включать любой объект, для которого можно создать процедуру построения пересечений. Объекты сцены могут состоять из набора плоских многоугольников, многогранников или тел, ограниченных или определяемых квадратичными или биполиномиальными параметрическими поверхностями. Поскольку 75-95% времени, затрачиваемого алгоритмом трассировки лучей, уходит на определение пересечений, то эффективность процедуры поиска пересечений оказывает значительно влияние на производительность всего алгоритма. Вычислительная стоимость определения пересечений произвольной пространственной прямой (луча) с одним выделенным объектом может оказаться высокой. Чтобы избавиться от ненужного поиска пересечений, производится проверка пересечения луча с объемной оболочкой рассматриваемого объекта. И если луч не пересекает оболочки, то не нужно больше искать пересечений этого объекта с лучом. В качестве оболочки можно использовать прямоугольный параллелепипед или сферу.

3.13 Сферическая и прямоугольная оболочки

Хотя, как показано, на рис. 3.13, использование сферы в качестве оболочки может оказаться неэффективным, факт пересечения трехмерного луча со сферой определяется очень просто. В частности, если расстояние от центра сферической оболочки до луча превосходит радиус этой сферы, луч не пересекает оболочки. Следовательно, он не может пересекаться и с объектом.

Поэтому тест со сферической оболочкой сводится к определению расстояния от точки до трехмерной прямой, т. е. луча. Будем использовать параметрическое представление прямой, проходящей через точки P₁(x₁, y₁, z₁) и P₂(x₂, y₂, z₂) т. е.:

Р(t) = P₁ + (P₂ - P₁)t

с компонентами

x = x₁ +(x₂ - x₁)t = x₁ +at

y = y₁ +(y₂ - y₁)t = y₁ +bt

z = z₁ +(z₂ - z₁)t = z₁ +ct

Тогда минимальное расстояние d от этой прямой до точки P₀(x₀, y₀, z₀) равно:

d² = (x - x₀)² + (y - y₀)² +(z - z₀)²

а параметр t, определяющий ближайшую точку Р(t)равен:

Если d²> R², где R - радиус сферической оболочки, то луч неможет пересечься с объектом.

Выполнение габаритного теста с прямоугольной оболочкой втрехмерном пространстве требует большого объема вычислений. При этом следует проверить пересечение луча по меньшей мере с тремя бесконечными плоскостями, ограничивающими прямоугольную оболочку. Поскольку точки пересечения могут оказаться вне граней этого параллелепипеда, то для каждой из них следует, кроме того, произвести проверку на охват или попадание внутрь. Следовательно, для трех измерений тест с прямоугольной оболочкой оказывается более медленным, чем тест со сферической оболочкой.

Одной простой процедурой можно свести тест с прямоугольной оболочкой к сравнению знаков, упрощая тем самым вычисление пересечений с объектом, а также сравнения по глубине среди точек пересечения. В этой процедуре используются переносы и повороты вокруг координатных осей для того, чтобы добиться совпадения луча с осью z. Аналогичным преобразованиям подвергается ипрямоугольная оболочка объекта. Луч пересекает оболочку, если вновой перенесенной и повернутой системе координат знаки x_minи x_max, а так же y_min и y_max.противоположны, как показано на рис. 3.14.