Компьютерная графика

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

Если на участке от предыдущего (x_n) до текущего (x_n+k) значения x видимость кривой изменяется, то вычисляется точка пересечения (x_i).

Если на участке от x_n до x_n+k сегмент кривой полностью видим, то он изображается целиком; если он стал невидимым, то изображается фрагмент от x_n до x_i; если же он стал видимым, то изображается фрагмент от x_i до x_n+k.

Заполнить массивы верхнего и нижнего плавающих горизонтов.

Изложенный алгоритм приводит к некоторым дефектам, когда кривая, лежащая в одной из более удаленных от точки наблюдения плоскостей, появляется слева или справа из-под множества кривых, лежащих в плоскостях, которые ближе к указанной точке наблюдения. Этот эффект продемонстрирован на рис. 3.7, где уже обработанные плоскости n - 1 и n расположены ближе к точке наблюдения. На рисунке показано, что получается при обработке плоскости n + 1. После обработки кривых n - 1 и n верхний горизонт для значений x = 0 и 1 равен начальному значению у; для значений x от 2 до 17 он равен ординатам кривой n; а для значений 18, 19, 20 - ординатам кривой n - 1. Нижний горизонт для значений x = 0 и 1 равен начальному значению у; для значений x = 2, 3, 4 - ординатам кривой n; а для значений x от 5 до 20 - ординатам кривой n - 1. При обработке текущей кривой (n + 1) алгоритм объявляет ее видимой при x = 4. Это показано сплошной линией на рис. 3.7. Аналогичный эффект возникает и справа при x = 18. Такой эффект приводит к появлению зазубренных боковых ребер. Проблема с зазубренностью боковых ребер решается включением в массивы верхнего и нижнего горизонтов ординат, соответствующих штриховым линиям на рис. 3.7. Это можно выполнить эффективно, создав ложные боковые ребра. Приведем алгоритм, реализующий эту идею для обеих ребер.

Рис. 3.7

Обработка левого бокового ребра:

Если P_n является первой точкой на первой кривой, то запомним P_n в качестве P_n1 и закончим заполнение. В противном случае создадим ребро, соединяющее P_n и P_n1.

Занесем в массивы верхнего и нижнего горизонтов ординаты этого ребра и запомним P_n в качестве P_n1.

Обработка правого бокового ребра:

Рис. 3.8

Если P_n является последней точкой на первой кривой, то запомним P_n в качестве P_n1 и закончим заполнение. В противном случае создадим ребро, соединяющее P_n и P_n1.

Занесем в массивы верхнего и нижнего горизонтов ординаты этого ребра и запомним P_n в качестве P_n1.

Теперь полный алгоритм выглядит так:

Для каждой плоскости z = const.

Обработать левое боковое ребро.

Для каждой точки, лежащей на кривой из текущей плоскости:

Если при некотором заданном значении x соответствующее значение у на кривой больше максимума или меньше минимума по у для всех предыдущих кривых при этом x, то кривая видима (в этой точке). В противном случае она невидима.

Если на сегменте от предыдущего (x_n) до текущего (x_n+k) значения x видимость кривой изменяется, то вычисляется пересечение (x_i).

Если на участке от x_n до (x_n+k) сегмент кривой полностью видим, то он изображается целиком; если он cтал невидимым, то изображается его кусок от x_n до x_i; если же он стал видимым, то изображается его кусок от x_i до x_n+k.

Заполнить массивы верхнего и нижнего плавающих горизонтов.

Обработать правое боковое ребро.

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

На рис. 3.8 показан типичный результат работы алгоритма плавающего горизонта. Запись этого алгоритма приводиться ниже.

Алгоритм плавающего горизонта

Гэкран - разрешение экрана в горизонтальном направлении

Вэкран - разрешение экрана в вертикальном направлении

Верх - массив, содержащий координаты верхнего горизонта

Низ - массив, содержащий координаты нижнего горизонта

Y - текущее значение функции y = f (x, z) при z = const

Тфлаг - флаг видимости для текущей точки

Пфлаг - флаг видимости для предыдущей точки, равный

0 = невидима

1 = видима и выше верхнего горизонта

-1 = видима и ниже нижнего горизонта

Draw - графическая команда, которая чертит видимую линию между точками, заданными их координатами.

Xmin, Xmax - минимальная и максимальная абсциссы функции

Xшаг - шаг приращения вдоль оси x

Zmin, Zmax - минимальная и максимальная аппликата функции

Zшаг - шаг между плоскостями z = const

Dimension Верх (Гэкран), Низ (Гэкран)

инициализация переменных

Xлевое = 1; Yлевое = 1; Xправое = 1; Yправое = 1

инициализация массивов горизонтов

Верх = 0

Низ = Вэкран

Вычисление функции на каждой плоскости z = const, начиная с ближайшей к наблюдателю плоскости Zmax

for z = Zmax to Zmin step Zшаг

инициализация предыдущих значений по x и y: Xпред и Yпред

Xпред = Xmin

Yпред = f (Xmin, z)

если используется видовое преобразование, то его нужно применить к Xпред, Yпред, z в данной точке

обработка левого бокового ребра

call Обрребра (Xпред, Yпред, Xлев, Yлев; Верх, Низ)

call Видимость (Xпред, Yпред, Верх, Низ; Пфлаг)

для каждой точки на кривой, лежащей в плоскости z = const

for x = Xmin to Xmax step Xшаг

y = f (x, z)

если используется видовое преобразование, то его нужно применить к данной точке

проверка видимости текущей точки и заполнение соответствующего массива горизонта

call Видимость (x, y, Верх, Низ; Тфлаг)

if Тфлаг = Пфлаг then

if (Тфлаг = 1) or (Тфлаг = 1) then

Draw (Xпред, Yпред, x, y)

call Горизонт (Xпред, Yпред, x, y; Верх, Низ)

end if

если видимость изменилась, то вычисляется пересечение и заполняется массив горизонта

else

if Тфлаг = 0 then

if Пфлаг = 1 then

call Пересечение (Xпред, Yпред, x, y, Верх; Xi, Yi)

else

call Пересечение (Xпред, Yпред, x, y, Низ; Xi, Yi)

end if

Draw (Xпред, Yпред, Xi, Yi)

сall Горизонт (Xпред, Yпред, Xi, Yi, Верх, Низ)

else

if Тфлаг = 1 then

if Пфлаг = 0 then

call Пересечение (Xпред, Yпред, x, y, Верх; Xi, Yi)

Draw (Xi, Yi, x, y)

сall Горизонт (Xi, Yi, x, y; Верх, Низ)

else

call Пересечение (Xпред, Yпред, x, y, Низ; Xi, Yi)

Draw (Xпред, Yпред, Xi, Yi)

call Горизонт (Xпред, Yпред, Xi, Yi; Верх, Низ)

call Пересечение (Xпред, Yпред, x, y, Верх; Xi, Yi)

Draw (Xi, Yi, x, y)

call Горизонт (Xi, Yi, x, y; Верх, Низ)

end if

else

if Пфлаг = 0 then

call Пересечение (Xпред, Yпред, x, y, Верх; Xi, Yi)

Draw (Xi, Yi, x, y)

call Горизонт (Xi, Yi, x, y; Верх, Низ)

else

call Пересечение (Xпред, Yпред, x, y, Верх; Xi, Yi)

Draw (Xпред, Yпред, Xi, Yi)

call Горизонт (Xпред, Yпред, Xi, Yi; Верх, Низ)

call Пересечение (Xпред, Yпред, x, y, Низ; Xi, Yi)

Draw (Xi, Yi, x, y)

call Горизонт (Xi, Yi, x, y; Верх, Низ)

end if

end if

end if

end if

вновь инициализировать Пфлаг, Xпред, Yпред

Пфлаг = Тфлаг

Xпред = x

Yпред = y

next x

обработка правого концевого ребра

call Обрребра (x, y, Xправ, Yправ; Верх, Низ)

next z

finish

подпрограмма обработки бокового ребра

Subroutine Обрребра (x, y, Xребра, Yребра; Верх, Низ)

если Xребра = 1, то встречена первая кривая и ребро не создаётся

if Xребра = 1 then 1

call Горизонт (Xребра, Yребра, x, y; Верх, Низ)

1 Xребра = x

Yребра = y

return

подпрограмма определения видимости точки

Subroutine Видимость (x, y, Верх, Низ; Тфлаг)

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

Тфлаг = 0, если точка невидима

= 1, если она видима и выше верхнего горизонта

= 1, если она видима и ниже нижнего горизонта

x считается целой

if (y < Верх (x)) and (y > Низ (x)) then Тфлаг = 0

if y Верх (x) then Тфлаг = 1

if y Низ (x) then Тфлаг = 1

return

подпрограмма заполнения массивов плавающих горизонтов

Subroutine Горизонт (X1, Y1, X2, Y2; Верх, Низ)

Эта программа использует линейную интерполяцию для заполнения массивов горизонтов между X1 и X2

Max (a, b) - определяет большее из a и b

Min (a, b) - определяет меньшее из a и b

проверка вертикальности наклона

if (X2 X1) = 0 then

Верх (X2) = Max (Верх (X2), Y2)

Низ (X2) = Min (Низ (X2), Y2)

else

Наклон = (Y2 Y1)/(X2 X1)

for x = X1 to X2 step 1

y = Наклон * (x X1) + Y1

Верх (x) = Max (Верх (x), y)

Низ (x) = Min (Низ (x), y)

next x

end if

return

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

Subroutine Пересечение (X1, Y1, X2, Y2, Массив; Xi, Yi)

Эта процедура вычисляет пересечение двух отрезков прямых

Массив содержит информацию о соответствующем горизонте

Sign - функция принимающая значения 1, 0, 1, если знак её аргумента <0, =0, >0 соответственно

проверка бесконечности наклона

if (X2 - X1) = 0 then

Xi = X2

Yi = Массив (X2)

else

вычисление пересечения

обход начинается с самой левой используемой точки

пересечение считается обнаруженным, когда изменяется знак разности значений y

Наклон = (Y2 - Y1)/(X2 - X1)

Ysign = Sign (Y1 + Наклон Массив (X1 + 1))

Csign = Ysign

Yi = Y1 + Наклон

Xi = X1 + 1

while Csign = Ysign

Yi = Y1 + Наклон

Xi = X1 + 1

Csign = Sign (Yi - Массив (Xi))

end while

выбирается ближайшее целое число

if |Yi Наклон Массив (X1 - 1)| |Yi Наклон Массив (X1)| then

Yi = Y1 - Наклон

Xi = X1 - 1

end if

end if

return

В приведенных выше алгоритме и примере функция у = f (x, z) рассматривалась только при z = const. Часто бывает удобно вычерчивать кривые, полагая постоянными как z, так и x. При этом возникает эффект перекрестной штриховки. На первый взгляд может показаться, что перекрестную штриховку можно получить путем наложения двух результатов, образованных плоскостями z = const и x = const. Однако это не так. Верный результат получается при обработке тех кривых из числа лежащих в плоскостях z = const и x = const, которые ближе всего к горизонтальным при обычном порядке их следования. Однако после обработки каждой кривой, самой близкой к горизонтальной, необходимо обрабатывать участки кривых, лежащих в ортогональных ей плоскостях, которые находятся между указанной кривой и кривой, следующей за ней. Разумеется, при обработке обеих последовательностей кривых нужно использовать одни и те же массивы верхнего и нижнего плавающих горизонтов. Если используется перекрестная штриховка, то не надо формировать левое и правое боковые ребра.

Алгоритм Робертса

Алгоритм Робертса представляет собой первое известное решение задачи об удалении невидимых линий. Это математически элегантный метод, работающий в объектном пространстве. Алгоритм, прежде всего, удаляет из каждого тела те ребра или грани, которые экранируются самим телом. Затем каждое из видимых ребер каждого тела сравнивается с каждым из оставшихся тел для определения того, какая его часть или части, если таковые есть, экранируются этими телами. Поэтому вычислительная трудоемкость алгоритма Робертса растет теоретически как квадрат числа объектов. Именно этот факт привёл к снижению интереса к алгоритму Робертса. Однако математические методы, используемые в этом алгоритме, просты, мощны и точны. Кроме того, этот алгоритм можно использовать для иллюстрации некоторых важных концепций. Наконец, более поздние реализации алгоритма, использующие предварительную приоритетную сортировку вдоль оси z и простые габаритные или минимаксные тесты, демонстрируют почти линейную зависимость от числа объектов.

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

ах + by + cz + d = 0 (3.1)

В матричной форме это выглядит так:

или

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

где каждый столбец содержит коэффициенты одной плоскости.

Напомним, что любая точка пространства представима в однородных координатах вектором

Более того, если точка [S] лежит на плоскости, то [S]*[P]^T = 0. Если же [S] не лежит на плоскости, то знак этого скалярного произведения показывает, по какую сторону от плоскости расположена точка. В алгоритме Робертса предполагается, что точки, лежащие внутри тела, дают положительное скалярное произведение.

Хотя уравнение плоскости (3.1) содержит четыре неизвестных коэффициента, его можно нормировать так, чтобы d = 1 следовательно, трех неколлинеарных точек достаточно для определения этих коэффициентов. Подстановка координат трех неколлинеарных точек (x₁, y₁, z₁), (x₂, y₂, z₂), (x₂, y₂, z₂) в нормированное уравнение (3.1) дает:

ax₁ + by₁ + cz₁ = 1

ax₂ + by₂ + cz₂ = 1

ax₃ + by₃ + cz₃ = 1

В матричной форме это выглядит так:

или

(3.2)

Решение этого уравнения дает значения коэффициентов уравнения плоскости:

Другой способ используется, если известен вектор нормали к плоскости, т. е.

n = ai + bj + ck

где i, j, k - единичные векторы осей x, y, z соответственно. Тогда уравнение плоскости примет вид

ax + by + cz + d = 0(3.3)

Величина d вычисляется с помощью произвольной точки на плоскости. В частности, если компоненты этой точки на плоскости (х₁, y₁, z₁) то:

d = (aх₁ + by₁ + cz₁) (3.4)

Поскольку объем вычислений в алгоритмах удаления невидимых линий или поверхностей растет с увеличением числа многоугольников, для описания поверхностей выгодно использовать многоугольники с более чем тремя сторонами. Эти многоугольники могут быть как невыпуклыми, так и неплоскими. Метод, предложенный Мартином Ньюэлом, позволяет найти как точное решение для уравнений плоскостей, содержащих плоские многоугольники, так и «наилучшее» приближение для неплоских многоугольников. Этот метод эквивалентен определению нормали в каждой вершине многоугольника посредством векторного произведения прилежащих ребер и усреднения результатов. Если a, b, c, d - коэффициенты уравнения плоскости, то

(3.5)

где

if i =n then j = 1 else j = i + 1

а d вычисляется с помощью любой точки на плоскости.

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

Если [В] - матрица однородных координат, представляющая исходные вершины тела, а [Т] - матрица размером 4х4 видового преобразования, то преобразованные вершины таковы:

[ВТ] = [В][T] (3.6)

где [ВТ] - преобразованная матрица вершин. Использование уравнения (3.2) позволяет получить уравнения исходных плоскостей, ограничивающих тело:

[В][V] = [D] (3.7)

где [V] - матрица тела, а [D] в правой части - нулевая матрица. Аналогично уравнения преобразованных плоскостей задаются следующим образом:

[ВТ][VТ] = [D] (3.8)

где [VТ] - преобразованная матрица тела. Приравнивая левые части уравнения (3.7) и (3.8), получаем

[ВТ][VT] = [В][V]

Подставляя уравнение (3.6), сокращая на [В] и умножая слева на

[T]^-1 имеем

[VT] = [T]^-1[V]

Итак, преобразованная матрица тела получается умножением исходной матрицы тела слева на обратную матрицу видового преобразования.

Тот факт, что плоскости имеют бесконечную протяженность и что скалярное произведение точки на матрицу тела отрицательно, если точка лежит вне этого тела, позволяет предложить метод, в котором матрица тела используется для определения граней, которые экранируются самим этим телом. Отрицательное скалярное произведение даёт только такая плоскость (столбец) в матрице тела, относительно которой точка лежит снаружи.

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



Рис. 3.9

который служит, кроме того, образом точки, лежащей в бесконечности на отрицательной полуоси z. Фактически [Е] представляет любую точку, лежащую на плоскости z = , т. е. любую точку типа (x, y, ). Поэтому, если скалярное произведение [Е] на столбец, соответствующий какой-нибудь плоскости в матрице тела, отрицательно, то [Е] лежит по отрицательную сторону этой плоскости. Следовательно, эти плоскости невидимы из любой точки наблюдения, лежащей в плоскости z = , а пробная точка на z = экранируется самим телом, как показано на рис. 3.8. Такие плоскости называются не лицевыми, а соответствующие им грани задними. Следовательно,

[Е][V] < 0

является условием того, что плоскости - не лицевые, а их грани - задние. Заметим, что для аксонометрических проекций (точка наблюдения в бесконечности) это эквивалентно поиску положительных значений в третьей строке матрицы тела.

Этот метод является простейшим алгоритмом удаления невидимых поверхностей для тел, представляющих собой одиночные выпуклые многогранники. Этот способ часто называют отбрасыванием задних плоскостей. Для выпуклых многогранников число граней при этом сокращается примерно наполовину. Метод эквивалентен вычислению нормали к поверхности для каждого отдельного многоугольника. Отрицательность нормали к поверхности показывает, что нормаль направлена в сторону от наблюдателя и, Следовательно, данный многоугольник не виден.

Этот метод можно использовать также и для простой закраски. Интенсивность или цветовой оттенок многоугольника делается пропорциональным проекции нормали к поверхности на направление взгляда.

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

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

После определения нелицевых плоскостей остается найти нелицевые отрезки. Нелицевой отрезок образуется в результате пересечения пары нелицевых плоскостей. После первого этапа удаления нелицевых отрезков необходимо выяснить, существуют ли такие отрезки, которые экранируются другими телами на картинке или в сцене. Для этого каждый оставшийся отрезок или ребро нужно сравнить с другими телами сцены или картинки. При этом использование приоритетной сортировки (z-сортировки) и простого минимаксного или габаритного с прямоугольной объемлющей оболочкой тестов позволяет удалить целые группы или кластеры отрезков и тел. Например, если все тела в сцене упорядочены в некотором приоритетном списке, использующем значения z ближайших вершин для представления расстояния до наблюдателя, то никакое тело из этого списка, у которого ближайшая вершина находится дальше от наблюдателя, чем самая удаленная из концевых точек ребра, не может закрывать это ребро. Более того, ни одно из оставшихся тел, прямоугольная оболочка которого расположена полностью справа, слева, над или под ребром, не может экранировать это ребро. Использование этих приемов значительно сокращает число тел, с которыми нужно сравнивать каждый отрезок или ребро.

Для сравнения отрезка P₁P₂ с телом удобно использовать параметрическое представление этого отрезка:

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

v = s + dt

где v - вектор точки на отрезке, s - начальная точка, d - направление отрезка. Необходимо определить, будет ли отрезок невидимым. Если он невидим, то надо найти те значения t, для которых он невидим. Для этого формируется другой параметрический отрезок от точки Р(t) до точки наблюдения g:

Q(a,t) = u = v + ga = s + dt + ga 0 t 1, a 0

Здесь a и t выполняют аналогичные функции. Заданное значение t указывает точку на отрезке P(t), а a указывает точку на отрезке, проведенном от точки P(t) до точки наблюдения. Фактически Q(a,t) представляет собой плоскость в трехмерном пространстве. Пара (a,t) определяет точку на этой плоскости. Значение a положительно, поскольку тела, экранирующие P(t) могут находиться только в той части этой плоскости, которая заключена между отрезком P(t) и точкой наблюдения.

Скалярное произведение любой точки, лежащей внутри тела, на матрицу тела положительно. Если же точка лежит внутри тела, то она невидима. Поэтому для определения части отрезка, которая экранируется телом, достаточно найти те значения a и t, для которых скалярное произведение Q(a,t) = u на матрицу тела положительно. Это скалярное произведение равно:

h = u * [VT] = s * [VT] + td * [VT] + ag * [VT] >0 0 t 1, a 0

Если все компоненты h неотрицательны для некоторых t и a, отрезок при этих значениях t экранируется данным телом. Обозначим

p = s * [VT]

q = d * [VT]

w = g * [VT]

запишем условия в виде

h_j = p_j + tq_j + aw_j 0 t 1, a 0

где j - номер столбца в матрице тела. Эти условия должны выполняться при всех значениях j, т. е. для всех плоскостей, ограничивающих объем тела. Пограничный случай между видимостью и невидимостью возникает, когда h_j = 0. При h_j = 0 точка лежит на плоскости. Полагая h_j = 0 для всех плоскостей, мы получим систему уравнений относительно a и t, которые должны удовлетворяться одновременно. Результат можно получить путем совместного решения всевозможных пар уравнений из этой системы, при этом будут найдены все значения a и t, при которых изменяется значение видимости отрезка. Схема решения показана на рис. 3.9. Число возможных решений при j уравнениях (плоскостях) равно j(j 1)/2. Каждое решение в диапазонах 0 t 1, a 0, подставляется во все остальные уравнения для проверки того, что условие h_j 0 выполнено. Поиск корректных решений производится для того, чтобы найти минимальное среди максимальных значений параметра t(t_minmax) и максимальное среди минимальных значений t(t_maxmin). Отрезок невидим при (t_maxmin) < t < (t_minmax). Последнее требование является простым следствием из классической задачи линейного программирования.

Решение на границе a = 0 возникает в случае протыкания (объектов).

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

Из практики известно, что решения удовлетворяющие неравенствам h_j > 0, могут существовать и за пределами области, ограниченной условиями 0 t 1 и a = 0. Поэтому три уравнения, описывающие эти границы, т.е. t = 0, t 1 = 0 и a = 0, нужно добавить к множеству уравнений h_j = 0. Теперьчисло решений равно (j + 2)(j + 3)/2, где j - количество плоскостей, ограничивающих выпуклый объем тела.

Как упоминалось ранее, выбор максимального из минимального и минимального из максимальных значений t среди возможных корректных решений указанной системы уравнений является простой задачей линейного программирования. Ее решение эквивалентно определению корректной ограниченной области, получающейся в результате графического решения. Предполагается, что этот алгоритм используется только для таких отрезков, о которых известно, что они частично или полностью невидимы. Все нелицевые и все полностью видимые отрезки выявлены и удалены до начала работы алгоритма. Алгоритм начинает работу с такими значениями t и a, которые являются решениями пары линейных уравнений с номерами е₁ и е₂, а также с t_min и t_max (текущими минимальным и максимальным значениями t) и с n (мощностью множества уравнений). На первом этапе алгоритма проверяется выполнение условий h_j > 0. Если эти условия выполнены, то на втором этапе вычисляются значения t_min и t_max. Результатом являются значения t_maxmin и t_minmax.

Метод решения, обсуждавшийся выше, требует больших затрат машинного времени. Поэтому стоит поискать более быстрые способы определения полностью видимых отрезков. Основная: идея состоит в установлении того факта, что оба конца отрезка лежат между точкой наблюдения и какой-нибудь видимой плоскостью. Т.к.

u = s + td + ag

При a = 0 значение u задает сам отрезок. Далее, если a = 0, при t = 0 и t = 1 получаются концевые точки отрезка. Также известно, что

h_j = u *[VT] = p_j + q_jt+ w_ja

и заметим, что при t = 0 p_j является скалярным произведением концевой точки отрезка и j-й плоскости, ограничивающей тело. Аналогично p_j + q_j является скалярным произведением другой концевой точки отрезка и j-й плоскости, ограничивающей тело. Наконец, напомним, что j-я плоскость, ограничивающая тело, видима, если w_j = 0. Поэтому, если w_j О и p_j 0, то один конец отрезка лежит или на видимой плоскости или между видимой плоскостью и точкой наблюдения. Если же p_j + q_j 0, то другой конец отрезка также лежит либо на видимой плоскости, либо между этой плоскостью и точкой наблюдения. Следовательно, отрезок полностью видим, если для любого j

w_j О и p_j 0 и p_j + q_j 0.

Эти условия гарантируют, что неравенства h_j 0 не могут быть выполнены ни при каких a 0 и 0 t 1. Поэтому никакая часть отрезка не может быть невидимой, т. е. отрезок полностью видим.

Ниже приводится эффективная реализация алгоритма Робертса. Этот алгоритм делится на три этапа. На первом этапе каждое тело анализируется индивидуально с целью удаления нелицевых плоскостей. На втором этапе проверяется экранирование оставшихся в каждом теле ребер всеми другими телами с целью обнаружения их невидимых отрезков. На третьем этапе вычисляются отрезки, которые образуют новые ребра при протыкании телами друг друга. В данном алгоритме предполагается, что тела состоят из плоских полигональных граней, которые в свою очередь состоят из рёбер, а ребра - из отдельных вершин. Все вершины, ребра и грани связаны с конкретным телом.

Удаление нелицевых плоскостей

Для каждого тела в сцене:

Сформировать многоугольники граней и ребра, исходя из списка вершин тела.

Вычислить уравнение плоскости для каждой полигональной грани тела.

Проверить знак уравнения плоскости:

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

Вычислить скалярное произведение уравнения плоскости и точки внутри тела.

Если это скалярное произведение < О, то изменить знак уравнения этой плоскости.

Сформировать матрицу тела.

Умножить ее слева на матрицу, обратную матрице видового преобразования, включающего перспективу.

Вычислить и запомнить габариты прямоугольной объемлющей оболочки преобразованного объема: x_min, x_max, y_min, y_max.

Определить нелицевые плоскости:

Вычислить скалярное произведение пробной точки, лежащей в бесконечности, на преобразованную матрицу тела.

Если это скалярное произведение < О, то плоскость невидима.

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

Удаление из каждого тела тех ребер, которые экранируются всеми остальными телами в сцене:

Если задано только одно тело, то алгоритм завершается.

Сформировать приоритетный список этих тел:

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

Для каждого тела из приоритетного списка:

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

Провести проверки экранирования для прямоугольных объемлющих оболочек пробного объекта и пробного тела:

Еслиx_min (пробное тело) > x_max (пробный объект) или

x_max (пробное тело) < x_min (пробный объект) или

y_min (пробное тело) > y_max (пробный объект) или

y_max (пробное тело) < y_min (пробный объект),

то пробное тело не может экранировать ни одного ребра пробного объекта. Перейти к следующему пробному телу. В противном случае:

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

Сравнить максимальное значение z у пробного объекта с минимальным значением z у пробного тела.

Если z_max (пробный объект) < z_min (пробное тело), то протыкание невозможно. Перейти к следующему телу. В противном случае:

Проверить видимое протыкание.

Если z_min (пробный объект) > z_max (пробное тело), то пробный объект может проткнуть переднюю грань пробного тела.

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

Если x_max (пробное тело) > x_min (пробный объект) или

x_min (пробное тело) < x_max (пробный объект),

то пробный объект может проткнуть бок пробного тела.

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

Если y_max (пробное тело) > y_min (пробный объект) или

y_min (пробное тело) < y_max (пробный объект),

то пробный объект может проткнуть верх или виз пробного тела.

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

Если список протыканий пуст, то устанавливать флаг протыкания не надо.

Провести проверки экранирования ребер:

Вычислить s и d для ребра.

Вы числить p, q, w для каждой плоскости, несущей грань пробного тела.

Проверка полной видимости. Если ребро полностью, видимо, то перейти к следующему ребру.

Сформировать уравнения h_j = 0 и решить их, объединяя попарно и включив в систему уравнения границ t = 0 и t = 1. Если установлен флаг видимого протыкания, то в систему надо включить и уравнение границы a = 0. Запомнить точки протыкания. В противном случае границу a = 0 не учитывать.

Для каждой пары (t, a), являющейся решением проверить выполнение условий 0 t 1, a 0 и h_j > 0 для всех других плоскостей. Если эти условия выполнены, то найти t_maxmin и t_minmax.

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

Определить видимые отрезки, связывающие точки протыкания:

Если флаг видимого протыкания не установлен, перейти к процедуре визуализации.

Если точек протыкания не обнаружено, перейти к процедуре визуализации.

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

Проверить экранирование всех соединяющих ребер обоими телами, связанными отношением протыкания.

Проверить экранирование оставшихся соединяющих ребер всеми прочими телами сцены. Запомнить видимые отрезки.

Визуализировать оставшиеся видимые отрезки ребер.

Алгоритм использующий Z-буфер

Это один из простейших алгоритмов удаления невидимых поверхностей. Работает этот алгоритм в пространстве изображения. Идея z-буфера является простым обобщением идеи о буфере кадра. Буфер кадра используется для запоминания атрибутов (интенсивности) каждого пиксела в пространстве изображения. Z-буфер - это отдельный буфер глубины, используемый для запоминания координаты z или глубины каждого видимого пиксела в пространстве изображения. В процессе работы глубина или значение z каждого нового пиксела, который нужно занести в буфер кадра, сравнивается с глубиной того пиксела, который уже занесен в z-буфер. Если это сравнение показывает, что новый пиксел расположен впереди пиксела, находящегося в буфере кадра, то новый пиксел заносится в этот буфер и, кроме того, производится корректировка z-буфера новым значением z. Если же сравнение дает противоположный результат, то никаких действий не производится. По сути, алгоритм является поиском по x и y наибольшего значения функции z (z, y).

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

Основной недостаток алгоритма - большой объем требуемой памяти. Если сцена подвергается видовому преобразованию и отсекается до фиксированного диапазона координат z значений, то можно использовать z-буфер с фиксированной точностью. Информацию о глубине нужно обрабатывать с большей точностью, чем координатную информацию на плоскости (x, y); обычно бывает достаточно 20 бит. Буфер кадра размером 512х512х24 бит в комбинации с z-буфером размером 512х512х20 бит требует почти 1.5 мегабайт памяти. Однако снижение цен на память делает экономически оправданным создание специализированных запоминающих устройств для z-буфера и связанной с ним аппаратуры.

Альтернативой созданию специальной памяти для 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 + x, равна

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

или

z₁ = z - (a/c)x

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

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

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

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

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

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

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

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

Рис. 3.10

Рис. 3.11

Наиболее важным элементом алгоритма определения видимых поверхностей путем трассировки лучей, является процедура определения пересечений. В состав сцены можно включать любой объект, для которого можно создать процедуру построения пересечений. Объекты сцены могут состоять из набора плоских многоугольников, многогранников или тел, ограниченных или определяемых квадратичными или биполиномиальными параметрическими поверхностями. Поскольку 75-95% времени, затрачиваемого алгоритмом трассировки лучей, уходит на определение пересечений, то эффективность процедуры поиска пересечений оказывает значительно влияние на производительность всего алгоритма. Вычислительная стоимость определения пересечений произвольной пространственной прямой с одним выделенным объектом может оказаться высокой. Чтобы избавиться от ненужного поиска пересечений, производится проверка пересечения луча с объемной оболочкой рассматриваемого объекта. И если луч не пересекает оболочки, то не нужно больше искать пересечений этого объекта с лучом. В качестве оболочки можно использовать прямоугольный параллелепипед или сферу. Хотя, как показано, на рис. 3.11, использование сферы в качестве оболочки может оказаться неэффективным, факт пересечения трехмерного луча со сферой определяется очень просто. В частности, если расстояние от центра сферической оболочки до луча превосходит радиус этой сферы, луч не пересекает оболочки. Следовательно, он не может пересекаться и с объектом. Поэтому тест со сферической оболочкой сводится к определению расстояния от точки до трехмерной прямой, т. е. луча. Будем использовать параметрическое представление прямой, проходящей через точки 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. противоположны.

Рассмотрим упрощение вычислений точек пересечения луча и поверхности второго порядка общего вида. В произвольной декартовой системе координат поверхностей второго порядка является геометрическим местом точек, координаты которых удовлетворяют уравнению:

Q (x, y, z) = a₁x² + a₂y² + a₃z² +

b₁yz + b₂xz + b3xy +

c₁x + c₂y + c₃z +d = 0

После применения преобразования, которое является комбинацией переноса и поворота и используется для совмещения луча с осью z, пересечение этого луча с поверхностью, если оно имеет место, возникает при x = y = 0. Поэтому в общем случае точки пересечения являются решениями уравнения: