Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Алгоритм Робертса представляет собой первое известное решение задачи об удалении невидимых линий. Это математически элегантный метод, работающий в объектном пространстве. Алгоритм прежде всего удаляет из каждого тела те ребра или грани, которые экранируются самим телом. Затем каждое из видимых ребер каждого тела сравнивается с каждым из оставшихся тел для определения того, какая его часть или части, если таковые есть экранируются самим телом.
В алгоритме Робертса требуется, чтобы все изображаемые тела или объекты были выпуклыми, невыпуклые тела должны быть разбиты на выпуклые части. В этом алгоритме выпуклое многогранное тело с плоскими гранями должно представляться набором пересекающихся плоскостей. Уравнение произвольной плоскости в трехмерном пространстве имеет вид
ax + by + cz + d = 0 (1)
В матричной форме этот результат выглядит так:
или
,
где
представляет собой плоскость. Поэтому любое выпуклое твердое тело можно выразить матрицей тела состоящей из коэффициентов уравнений плоскостей, т.е.
где каждый столбец содержит коэффициенты одной плоскости.
Напомним, что любая точка пространства представима в однородных координатах вектором
Более того, если точка лежит на плоскости, то , Если же не лежит на плоскости, то знак этого скалярного произведения показывает, по какую сторону от плоскости расположена точка. В алгоритме Робертса предполагается, что точки, лежащие внутри тела, дают положительное скалярное произведение. Чтобы проиллюстрировать эти идеи, рассмотрим следующий пример.
Матрица тела
Шесть плоскостей описывающих куб с центром в начале координат, таковы: х1 = ½,
х2=-½, у3=½, у4=-½, z5=½, z6=-½. Они изображены на рисунке. Уравнение правой плоскости имеет вид
или
Полная матрица тела такова
Эту матрицу следует проверить с помощью одной из тех точек, о которых известно, что они лежат внутри тела, чтобы убедиться, что знаки каждого уравнения плоскости выбраны верно. Если знак скалярного произведения для какой-нибудь плоскости меньше нуля, то соответствующее уравнение плоскости следует умножить на –1. Точка внутри куба с координатами x=1/4, y=1/4, z=1/4 представляется в однородных координатах в виде вектора
Скалярное произведение этого вектора на матрицу объема равно
Здесь результаты для первого, третьего и пятого уравнений плоскостей (столбцов) отрицательны, и, следовательно, они составлены некорректно. Умножая эти уравнения (столбцы) на –1, получаем корректную матрицу тела для данного куба.
В приведенном примере корректность уравнений плоскостей была проверена экспериментально. Разумеется, это не всегда возможно. Существует несколько полезных методов для более общего случая. Хотя уравнение плоскости содержит четыре коэффициента, его можно нормировать так, чтобы d=1. Следовательно, трех неколлинеарных точек достаточно для определения этих коэффициентов. Подстановка координат трех неколлинеарных точек в нормированное уравнение дает
ax1 + by1 +cz1 = -1
ax2 + by2 +cz2 = -1
ax3 + by3 +cz3 = -1
В матричной форме это выглядит так
или
(2)
Решение этого уравнения дает значение коэффициентов уравнения плоскости:
Другой способ используется, если известен вектор нормали к плоскости, т.е.
n = ai +bJ+ck
где i, j, k – единичные векторы осей x, y, z соответственно. Тогда уравнение плоскости примет вид
ax + by + cz + d = 0 (3)
Величина d вычисляется с помощью произвольной точки на плоскости. В частности, если компоненты этой точки на плоскости (x1, y1, z1), то
d= -( ax1 + by1 + cz1). (4)
Поскольку объем вычислений в алгоритмах растет с увеличением числа многоугольников, для описания поверхностей выгодно использовать многоугольники с более чем тремя сторонами. Эти многоугольники могут быть как невыпуклыми, так и не плоскими. Метод, предложенный Мартином Ньюэлом, позволяет найти как точное решение для уравнений плоскостей, содержащих плоские многоугольники, так и «наилучшее» приближение для неплоских многоугольников. Этот метод эквивалентен определению нормали в каждой вершине многоугольника посредством векторного произведения прилежащих ребер и усреднения результатов. Если a, b, c и d – коэффициенты уравнения плоскости, то
(5)
где
if i=n then j=1 else j=i+1
а d вычисляется с помощью любой точки на плоскости. Этот метод иллюстрируется следующим примером.
Уравнение плоскостей
Рассмотрим четырехсторонний плоский многоугольник, описываемый четыремя вершинами V1(1, 0, 0), V2 (0, 1, 0), V3 (0, 0, 1), V4 (1, -1, 1) (см. рисунок). Используя вершины V1, V2 , V3 , V4 и уравнение (2) получаем
Или, разрешая относительно коэффициентов уравнения плоскости:
Уравнение плоскости теперь имеет вид:
Или
Решая другим методом, может получить нормаль к этой плоскости, используя векторное произведение пары векторов, являющихся смежными ребрами одной из вершин, например V1:
n==
или
=i+j+k
Где i, j, k – единичные векторы осей x, y, z соответственно. Используя уравнение 4 и V4, получаем значение постоянного члена в уравнении плоскости:
d = -1(1-1+1) = -1.
Следовательно, уравнение плоскости имеет вид:
x + y + z – 1= 0
Обращаясь теперь к методу Ньюэла при n=4, получаем из уравнения (5)
a=(y1 – y2)(z1 + z2) +(y2 – y3)(z2 + z3) +(y3 – y4)(z3 + z4) +(y4 – y1)(z4 + z1)=
=(-1)(0) +(1)(1)+(1)(2)+(-1)(1)=2
b=(z1-z2)(x1+x2)+ (z2-z3)(x2+x3)+ (z3-z4)(x3+x4)+ (z4-z1)(x4+x1)=
=(0)(1)+(-1)(0)+(0)(1)+(1)(2)=2
c=(x1-x2)(y1+y2)+ (x2-x3)(y2+y3)+ (x3-x4)(y3+y4)+ (x4-x1)(y4+y1)=
= (1) (1) + (0) (1) +(-1) (-1) + (0) (1) = 2
а используя V4 получаем для постоянного члена
d = - (2-2+2) =-2
После деления на 2 уравнение плоскости вновь примет вид
x + y + z – 1= 0
Следующий пример иллюстрирует метод Ньюэла для почти плоских многоугольников.
Неплоские многоугольники
Рассмотрим почти плоский многоугольник, описанный четыремя вершинами V1(1, 0, 0), V2 (0, 1, 0), V3 (0, 0, 1), V4 (1.1, -1, -1)
Вычисляя нормаль в каждой вершине через векторное произведение пары прилежащих ребер имеем
n1= V1V2V1V4=i+j+0.9k
n2= V2V3V2V1=i+j+k
n3= V3V4V3V2=i+1.1j+1.1k
n4= V4V1V4V3=i+1.1j+k
Усредняя эти нормали, получаем
n = i + 1.05j + k
Определение постоянного члена в уравнении плоскости с использованием одной из вершин, например, V1, дает d = -1. Следовательно, приближенное уравнение плоскости таково:
x + 1.05y +z -1 =0
Метод Ньюэла приводит к такому же результату, в частности,
a = (-1)(0) + (1) (1) + (1)(2) + (-1)(1) = 2
b = (0)(1) + (-1)(0) +(0)(1.1) +(1)(2.1) = 2.1
c= (1)(1) + (0) (1) + (-1)(-1) +(0.1)(-1) = 2
Вычисление d с использованием V1 и деление на 2 дает такое же приближенное уравнение плоскости. Аппроксимирующая плоскость проходит через прямую x=z и содержит вершины V1 и V2. Однако V2 и V4 немного смещены по разные стороны от этой плоскости.
Перед началом работы алгоритма удаления невидимых линий или поверхностей для получения желаемого вида сцены часто применяется трехмерное видовое преобразование. Матрицы тел для объектов преобразованной сцены можно получить или преобразованием исходных матриц тел или вычислением новых матриц тел, используя преобразованные вершины или точки.
Если матрица однородных координат, представляющая исходные вершины тела, а - матрица размером 44 видового преобразования, то преобразованные вершины таковы:
,
где - преобразованная матрица вершин. Использование уравнения позволяет получить уравнения исходных плоскостей, ограничивающих тело:
,
где - матрица тела, а в правой части нулевая матрица. Аналогично уравнения преобразованных плоскостей задаются следующим образом
, где
- преобразованная матрица тела. Приравнивая левые части последних уравнений, получаем
Подставляя уравнения , сокращая на и умножая слева на-1, имеем
=-1.
Итак, преобразованная матрица тела получается умножением исходной матрицы тела слева на обратную матрицу видового преобразования. Следующий пример служит этому иллюстрацией.
Преобразование тела.
Рассмотрим перенос единичного куба с центром в начале координат на три единицы в положительном направлении оси х. Соответствующая матрица преобразования размером 4 4 имеет вид
А обратная к ней матрица, которая может быть получена формально или подбором, такова
Умножение слева матрицы тела данного единичного куба, полученной ранее на [T]-1 дает матрицу тела для перенесенного куба:
Перенос единичного куба с центром в начале координат на три единицы вправо помещает левую грань на отметку х=2.5, а правую грань - на отметку 3.5. Первый столбец в преобразованной матрице тела содержит коэффициенты уравнения плоскости правой грани
-2х+7 = 0 или х=3.5,
Что и требовалось. Аналогично второй столбец дает
2х-5=0 или х = 2.5
Что и ожидалось для левой грани.
Напомним, что в первом примере точка
[S] = [¼ ¼ ¼ 1] = [1 1 1 4]
Лежала внутри преобразованного тела. Следовательно, [S] [V]0. Однако точка [S] лежит вне перенесенного тела. Проверка скалярного произведения [S] и преобразованной матрицы тела [S] [VT] =[1 1 1 4] [VT] =[26 -18 2 6 2 6]
дает один отрицательный элемент во втором столбце, который соответствует левой грани куба, т.е. С внешней стороны относительно левой грани, что и показал отрицательный знак.
Если преобразование матрицы точки [S] получается умножением на матрицу преобразования, то
[ST]= [S] [T]= [1 1 1 4] [T]= [13 1 1 4]= [3.25 0.25 0.25 1]
Проверка скалярного произведения преобразованной токи с х =3.25 на преобразованную матрицу тела дает
[ST] [VT]= [2 6 2 6 2 6]
Этот результат показывает, что преобразованная точка лежит внутри преобразованного тела.
Тот факт, что плоскости имеют бесконечную протяженность и что скалярное произведение точки на матрицу тела отрицательно, если точка лежит вне этого тела, позволяют предложить метод, в котором матрица тела используется для определения граней, которые экранируются самим этим телом. В последнем примере показано, что отрицательное скалярное произведение дает только такая плоскость (столбец) в матрице тела, относительно которой точка лежит снаружи. В последнем примере таковой объявляется левая плоскость (второй столбец) в преобразованной матрице тела и непреобразованная точка . Эти рассуждения проиллюстрированы на следующем рисунке.
Если зритель находится в бесконечности на положительной полуоси z и смотрит на начало координат, то его взгляд направлен в сторону отрицательной полуоси z. В однородных координатах вектор такого направления равен :
,
который служит, кроме того, образом точки, лежащей в бесконечности на отрицательной полуоси z. Фактически представляет любую точку, лежащую на плоскости , т.е. любую точку типа . Поэтому, если скалярное произведение на столбец соответствующий какой-нибудь плоскости в матрице тела, отрицательно, то лежит по отрицательную сторону этой плоскости. Следовательно, эти плоскости невидимы из любой точки наблюдения лежащей в плоскости , а пробная точка на экране экранируется самим телом, как показано на следующем рисунке. Такие плоскости называются нелицевыми, а соответствующие им грани – задними. Следовательно,
является условием того, что плоскости нелицевые, а их грани задние. Заметим, что для аксонометрической проекции (точка наблюдения в бесконечности) это эквивалентно поиску положительных значений в третьей строке матрицы тела.
Этот метод является простейшим алгоритмом удаления невидимых поверхностей для тел, представляющих собой одиночные выпуклые многогранники. Он также используется для удаления нелицевых или задних граней из сцены перед применением одного из алгоритмов невидимых линий, которые будем обсуждать дальше. Этот способ часто называют отбрасыванием задних плоскостей. Для выпуклых многогранников число граней при этом сокращается примерно наполовину. Метод эквивалентен вычислению нормали для каждого отдельного многоугольника. Отрицательность нормали к поверхности показывает, что нормаль направлена в сторону от наблюдателя и, следовательно, данный многоугольник не виден. Этот метод можно использовать также и для простой закраски. Интенсивность или цветовой оттенок многоугольника делается пропорциональным проекции нормали к поверхности на направление взгляда. Следующий пример иллюстрирует данный подход.
Нелицевая плоскость
Вновь рассмотрим единичный куб с центром в начале координат, как показано на рисунке. Точка наблюдения находится на положительной полуоси z, ее координаты [0 0 1 0], взгляд направлен на начало координат, Скалярное произведение указанного вектора на матрицу тела дает:
Отрицательное число в шестом столбце показывает, что грань с этим номером нелицевая; рисунок подтверждает это. Нулевые результаты соответствуют плоскостям, параллельным направлению взгляда.
Данный метод определения нелицевых граней в результате формирует аксонометрическую проекцию на некую плоскость, расположенную бесконечно далеко от любой точки трехмерного пространства. Видовые преобразования, включая перспективное производятся до определения нелицевых плоскостей. Когда видовое преобразование включает в себя перспективу, то нужно использовать полное перспективное преобразование одного трехмерного пространства в другое, а не перспективное проецирование на некоторую двумерную плоскость. Полное перспективное преобразование приводит к искажению трехмерного тела, которое затем проецируется на некоторую плоскость в бесконечности, когда нелицевые плоскости уже определены. Тот результат эквивалентен проецированию из некоторого центра на конечную плоскость проекции.
Видовое преобразование можно применить к телу так, чтобы точка наблюдения осталась фиксированной. При другом способе тело остается неподвижным. Соответствующая точка наблюдения и направление взгляда получаются умножением справа на матрицу, обратную матрице видового преобразования. Следующий пример служит иллюстрацией к этим методам.
Нелицевая плоскость с учетом видового преобразования.
Рассмотрим единичный куб с центром в начале координат, повернутый на 45º вокруг оси у. Соответствующее видовое преобразование будет иметь вид
Преобразованная матрица тела получается умножением исходной матрицы тела слева на матрицу, обратную матрице видового преобразования. Для чистого поворота обращение матрицы видового преобразования сводится к ее транспортированию. Поэтому
Преобразованная матрица тела такова:
Если смотреть на начало координат из точки наблюдения , лежащей на положительной полуоси, то направление взгляда или пробная точка задаются вектором:
Скалярное произведение на преобразованную матрицу тела равно:
Следовательно, первая и шестая плоскости, которым соответствуют левая и задняя грани в исходном положении куба, - нелицевые (рисунок подтверждает это). Заметим также, что когда тело преобразовано и направление взгляда фиксировано, то поиск отрицательных членов в скалярном произведении пробной точки на преобразованную матрицу тела эквивалентен поиску положительных членов в третьей строке преобразованной матрице тела.
Эквивалентная точка наблюдения для непреобразованного тела, соответствующая повороту вокруг оси у, равна
т.е. эта точка расположена на прямой –х = у в бесконечности в направлении положительной полуоси z, как показано на рисунке справа. Аналогично определяются эквивалентное направление взгляда и пробная точка:
Эта точка расположена на прямой –х = z в бесконечности в направлении отрицательной полуоси z. Скалярное произведение этого эквивалентного направления взгляда на исходную матрицу тела равно:
Это вновь показывает, что первая и шестая плоскость нелицевые и рисунок подтверждает это.
После определения нелицевых плоскостей остается найти нелицевые отрезки. Нелицевой отрезок образуется в результате пересечения пары нелицевых плоскостей. Хотя в предпоследнем примере шестая плоскость нелицевая, однако нелицевых отрезков нет, поскольку только одна плоскость заслоняет сама себя. В то же время в последнем примере ребро, образованное пересечением первой и шестой плоскостей является нелицевым.
После первого этапа удаления нелицевых отрезков необходимо выяснить, существуют ли такие отрезки. Которые экранируются другими телами в картинке или в сцене. Для этого каждый оставшийся отрезок или ребро нужно сравнить с другими телами сцены или картинки. При этом использование приоритетной сортировки и простого минимаксного или габаритного с прямоугольной объемлющей оболочкой тестов позволяют удалить целые группы или кластеры отрезков и тел. Например, если все тела в сцене упорядочены в некотором приоритетном списке, использующем значение z ближайших вершин для представления расстояния до наблюдателя, то никакое тело из этого списка, у которого ближайшая вершина находится дальше от наблюдателя, чем самая удаленная из концевых точек ребра, не может закрывать это ребро. Более того, ни одно из оставшихся тел, прямоугольная оболочка которого расположена полностью справа, слева или под ребром, не может экранировать это ребро. Использование этих приемов значительно сокращает число тел, с которыми нужно сравнивать каждый отрезок или ребро.
Для сравнения отрезка Р1Р2 с телом удобно использовать параметрическое представление этого отрезка:
v = s +dt
где v – вектор точки на отрезке, s – начальная точка, а d – направление отрезка. Обходимо определить, будет ли отрезок невидимым. Если он невидим, то надо найти те значения t, для которых он невидим. Для этого формируется другой параметрический отрезок от точки P(t) до точки наблюдения g
Q(, t) = u =v +g= s +dt+ g
Здесь и t выполняют аналогичные функции. Заданное значение t указывает точку на отрезке P(t), а указывает точку на отрезке, проведенном от точки P(t) до точки наблюдения. Фактически Q(, t) представляет собой плоскость в трехмерном пространстве. Пара (, t) определяет точку на этой плоскости. Значение положительно, поскольку тела, экранирующие P(t), могут находиться только в той части этой плоскости, которая заключена между отрезком P(t) и точкой наблюдения.
Параметрическая плоскость
Рассмотрим отрезок, проведенный из точки Р1(-2, 0, -2) в точку Р2 (2, 0, -2) из точки наблюдения, расположенной в бесконечности на положительной полуоси z. В однородных координатах Р1 и Р2 таковы
Следовательно,
Вектор точки наблюдения имеет вид
Рисунок и таблица показывают, что происходит при изменении t и ά. В качестве частного примера рассмотрим случай, когда t = 0.5 и ά = 3. Тогда
|
t |
ά |
v(t) |
Q(ά, t) |
|
0 |
0 1/2 1 2 3 |
||
|
1/2 |
0 1/2 1 2 3 |
||
|
1 |
0 1/2 1 2 3 |
Эта точка лежит на отрезке Р1 Р2 и является точкой его пересечения с осью z при z = -2. При ά = 3.
что соответствует точке на оси z при z=1. Заметим, что каждая из полученных прямых параллельна оси z.
Напомним, что скалярное произведение любой точки, лежащей внутри тела, на матрицу тела положительно. Если же точка лежит внутри тела, то она невидима. Поэтому для определения части отрезка, которая экранируется телом, достаточно найти те значения и t, для которых скалярное произведение Q(, t)=u на матрицу тела положительно. Это скалярное произведение равно
H=g
Если все компоненты h неотрицательны для некоторых и t,то отрезок при этих значениях t экранируется левым телом. Обозначив
запишем условия в виде
где j – номер столбца в матрице тела. Эти условия должны выполняться при всех значениях j, т.е. для всех плоскостей, ограничивающих объем тела. Пограничный случай между видимостью и невидимостью возникает, когда hj = 0. При hj = 0 точка лежит на плоскости. Полагая hj = 0 для всех плоскостей, мы получим систему уравнений относительно и t, которые должны удовлетворяться одновременно. Результат можно получить путем совместного решения всевозможных пар уравнений из этой системы, при этом будут найдены все значения и t, при которых изменяется значение видимости отрезка. Схема решений показана на рисунке. Число всевозможных решений при j уравнениях (плоскостях) равно j(j - 1)/2. Каждое решение в диапазонах , подставляется во все остальные уравнения для проверки того, что условие выполнено. Поиск корректных решений производится для того, чтобы найти минимальной среди максимальных значений параметра t(tminmax) и максимальное среди минимальных отрезков t(tmaxmin). Отрезок невидим при tmaxmin < t < tminmax. Последнее требование является простым следствием из классической задачи линейного.
программирования.
Ниже приводится еще один алгоритм решения данной задачи. Но сначала дадим несколько примеров, которые могут пояснить приведенные рассуждения.
Проверка экранирования отрезков телами.
Вновь рассмотрим единичный куб с центром в начале координат. Отрезок, от Р1[-2 0 -2 1] до Р2 [2 0 -2 1] лежит за этим кубом и частично экранируется им, как показано на рисунке. Снова имеем
Для точки наблюдения, расположенной в бесконечности на положительной полуоси z, имеем
Здесь будем считать, что куб не преобразуется следовательно,
Значения p, q и w суть результат скалярного произведения s, d и g на :
Используя эти значения, получаем шесть неравенств, соответствующих условию
hj = pj +tqj + άwj > 0, по одному на каждую из шести плоскостей, несущих грани куба. Конкретно,
5 – 8 t > 0
-3 + 8 t > 0
5 - 2ά > 0
-3 + 2ά > 0
Третье и четвертое из этих неравенств просто устанавливают, что соответствующие условия всегда выполняются. Они выражают тот геометрический факт, что отрезок находится целиком «внутри» бесконечных полупространств, ограниченных плоскостями, несущих верхнюю и нижнюю грани куба. Превращение оставшихся четырех неравенств в равенства дает следующие решения: t=5/8, t=3/8, ά=5/2 и ά=3/2. Разумеется приведенный пример элементарен. Эти уравнения можно решить, просто посмотрев на них, однако в общем случае это не так.
Каждое из полученных уравнений описывает прямую в пространстве (ά, t). Поучительно взглянуть на графическое решение, показанное на следующем рисунке. Штриховкой обозначены те стороны прямых, где расположены возможные решения. Очевидно, что все неравенства hj > 0 удовлетворяются только внутри указанной на рисунке ограниченной области. Итак, tmaxmin = 3/8, a tminmax = 5/8.
Отрезок невидим в диапазоне и видим при и
Используя параметрическое уравнение отрезка, имеем
что и показано на предыдущем рисунке.
В приведенном примере получены два значения t. Поэтому удается выбрать tmaxmin и tminmax. Что же делать, если в результате решения уравнения получится только одно значение t. Следующие примеры иллюстрируют эту проблему и методы ее решения.
Решение с единственным значением t.
Продолжая рассматривать модель единичного куба с центром в начале координат рассмотрим отрезок от Р1[1 0 -1 0] до Р2 [0 0 -1 1], как показано на рисунке. Здесь
Рассматривается случай непреобразованного куба, т.е. . Величины p, q и w равны
Система неравенств, выражающих условия hj > 0, такова
-1+ 2 t > 0
3 - 2 t > 0
1 > 0
1 > 0
3 - 2ά > 0
-1 + 2ά > 0
Решение соответствующих уравнений для hj = 0 дает значения t = 1/2, t = 3/2, ά = 3/2 и ά =1/2 Решение t = 3/2 надо отбросить, ибо оно выходит за пределы допустимого диапазона Следовательно, найдено только одно значение t. Графическое решение показано на следующем рисунке. Вновь штриховкой обозначена та сторона линии, по которую могут лежать допустимые решения. Очевидно, что результат не обращает ограниченную область. Однако в изложенном методе решения не использовались граничные условия, представленные прямыми t = 0 и t = 1. Как показано на рисунке справа, добавление этих прямых к решению, очевидно образует требуемую ограниченную область. Поэтому tmaxmin = 1/2 и tminmax = 1. Далее, все ограничения hj > 0удовлетворяются при обоих этих значениях t. Следовательно, отрезок видим при , т.е. от
до
Изменение направления отрезка, т.е. перемена мест Р1 и Р2 дает область решения от t=0 до t=1/2.
Следующий пример показывает, что граница ά=0 тоже должна быть учтена.
Граница по параметру ά.
Рассмотрим непреобразованный куб и отрезок от Р1[1 0 2 1] до Р2 [-1 0 -2 1], как показано на рисунке. Этот отрезок протыкает тело. Здесь
Снова точка наблюдения находится в бесконечности и для непреобразованного куба, т.е. .
Условия hj > 0 имеют вид
-1+ 4 t > 0
3 - 4 t > 0
1 > 0
1 > 0
-3 + 8 t - 2ά > 0
-1 - 8 t + 2ά > 0
Решение соответствующих уравнений для hj = 0 дает единственный результат t = 3/4. Это решение показано в графическом виде на следующем рисунке. Вновь заштрихована та сторона линии, по которую могут лежать решения. Но решения не образуют ограниченную область. Добавляя границы t = 0 и t = 1, получаем ограниченную область между t = 3/4 и t = 1. Однако, как показывает штриховка эта область некорректна, поскольку при t >3/4 не выполняется условие hj > 0 для j=2. Добавление границы ά=0 дает уже корректную ограниченную область с краями t = 3/8 и t = 3/4. Именно эта область дает значения tmaxmin = 3/8 и tminmax =3/4. Следовательно, отрезок видим при и или
от до
и
от до
Решения на границе возникают в случае протыкания (объектов).
Один из приемов заключается в запоминании всех точек протыкания и в добавлении к сцене отрезков, связывающих эти точки. Отрезки образуются путем соединения каждой точки протыкания для пары тел, связанных отношением протыкания, со всеми остальными точками протыкания этой пары объектов. Затем проверяется экранирование отрезков этими телами. Видимые отрезки образуют структуру протыкания.
Примеры показывают, что решения удовлетворяющие неравенствам hj > 0, могут существовать и за пределами области, ограниченной условиями и ά = 0. Поэтому, три уравнения описывающие эти границы, т.е. t = 0, t -1 = 0 и ά = 0 нужно добавить к множеству уравнений hj = 0. Теперь число решений равно (j + 2) (j + 3) / 2, где j количество плоскостей, ограничивающих выпуклый объем тела.
Как уже упоминалось, выбор максимального из минимальных и минимального из максимальных значений t среди возможных корректных решений указанной системы уравнений является простой задачей линейного программирования. Ее решение эквивалентно определению корректной ограниченной области, получающегося в результате графического решения, примеры которого были даны на рисунках. Блок-схема, приведенная ниже, содержит алгоритм решения указанной минимаксной задачи. Предполагается, что этот алгоритм используется только для таких отрезков, о которых известно, что они частично или полностью невидимы. Все нелицевые и все полностью видимые отрезки выявлены и удалены до начала работы алгоритма. Алгоритм начинает работу с такими значениями t и ά , которые являтся решениями пары линейных уравнений с номерами е1 и е2, а также с tmin и tmax. Результатом являются значения tmaxmin и tminmax..
Метод решения, обсуждавшийся выше, требует больших затрат машинного времени. Поэтому стоит поискать более быстрые способы определения полностью видимых отрезков. Основная идея состоит в установлении того факта, что оба конца отрезка лежат между точкой наблюдения и какой-нибудь видимой плоскостью. Напомним, что
u = s + td +άg
При ά = 0 значение u задает сам отрезок. Далее, если ά = 0, то при t=0 и t=1получаются концевые точки отрезка. Напомним, что
hj = u = pj +qjt + wj ά
и заметим, что при t =0 pj является скалярным произведением концевой точки отрезка и
j-й плоскости, ограничивающей тело. Наконец, напомним, что j-я плоскость, ограничивающая тело, видима, если . Поэтому, если и pj, то один конец отрезка лежит или на видимой плоскости или между видимой плоскостью и точкой наблюдения. Если же pj + qj , то другой конец отрезка также лежит либо на видимой плоскости, либо между этой плоскостью и точкой наблюдения.
Следовательно, отрезок полностью видим, если для любого j
wj и pj и pj + qj .
Эти условия гарантируют, что неравенства hi не могут быть выполнены ни при каких и . Поэтому никакая часть отрезка не может быть невидимой, т.е. отрезок полностью видим.
Полностью видимые отрезки
Для единичного куба с центром в начале координат рассмотрим отрезок от Р1[-2 0 2 1] до Р2 [2 0 2 1], который как показано на рисунке проходит перед этим кубом. Здесь
и с учетом того, что точка наблюдения лежит в бесконечности на положительной полуоси z, имеем
Для непреобразованного куба .
Заметим, что w5 < 0, p5 < 0, p5 + q5 < 0. Значит этот отрезок полностью видим.
Дополнительно, в качестве примера рассмотрим отрезок от от Р3[-1 1 1 1] до Р4 [1 1 -1 1], который проходит по диагонали над кубом. Этот отрезок тоже показан на рисунке. Здесь
Заметим, что w5 < 0, p5 < 0, но p5 + q5 > 0.
Но w3 = 0 и p3 < 0, p3 + q3 < 0. Этот отрезок также полностью видим.
Хотя верхняя плоскость (плоскость 3) и лежит «под ребром» при взгляде из точки наблюдения, расположенной в бесконечности на оси z, математически отрезок Р3Р4 в приведенном примере расположен между этой точкой и указанной видимой плоскостью. Аналогичное условие справедливо для нижней и двух боковых плоскостей.
К сожалению, нет простого теста для полностью невидимых линий. Конечно, можно определить, что обе концевые точки отрезка расположены позади невидимой плоскости. Однако, поскольку плоскость простирается до бесконечности, невозможно определить, будут ли при этом концы отрезка позади тела. Полностью невидимые отрезки приходится обнаруживать, используя общий метод решения этой задачи. В этом случае невидимый участок простирается от t = 0 до t=1.
Приведем эффективную организацию алгоритма Робертса. Этот алгоритм делится на три этапа. На первом этапе каждое тело анализируется индивидуально с целью удаления
нелицевых плоскостей. На втором этапе проверяется экранирование оставшихся в каждом теле ребер всеми другими телами с целью обнаружения их невидимых отрезков. На третьем этапе вычисляются отрезки, которые образуют новые ребра при протыкании телами друг друга. В данном алгоритме предполагается, что тела состоят из плоских многоугольных граней, которые в свою очередь состоит из ребер, а ребра – из отдельных вершин. Все вершины ребра и грани связанны с конкретным телом.
Удаление нелицевых плоскостей
Для каждого тела в сцене
Сформировать многоугольники граней и ребра, исходя из списка вершин.
Вычислить уравнение плоскости для каждой многоугольной грани тела.
Проверить знак уравнения плоскости:
Взять любую точку внутри тела, например, усреднив координаты его вершин.
Вычислить скалярное произведение уравнения плоскости и точки внутри тела.
Если это скалярное произведение меньше 0, то изменить знак уравнения этой
плоскости.
Сформировать матрицу тела.
Умножить ее слева на матрицу, обратную матрице видового преобразования,
включающего перспективу.
Вычислить и запомнить габариты прямоугольной объемлющей оболочки
преобразованного объема: xmax, xmin, ymax, ymin.
Определить нелицевые плоскости:
Вычислить скалярное произведение пробной точки, лежащей в бесконечности на
преобразованную матрицу тела.
Если это скалярное произведение меньше нуля, то плоскость невидима.
Удалить весь многоугольник, лежащий в этой плоскости. Это избавляет от
необходимости отдельно рассматривать невидимые линии, образуемые
пересечением пар невидимых плоскостей.
Удаление из каждого тела тех ребер, которые экранируются всеми остальными телами в сцене.
Если задано только одно тело, то алгоритм завершается.
Сформировать приоритетный список этих тел:
Провести сортировку по z. Сортировка проводится по максимальным значениям
координаты z вершин преобразованных тел. Первым в упорядоченном списке и
обладающем наибольшим приоритетом будет то тело, у которого минимальное
среди максимальных значений z. В используемой правой системе координат это
тело будет самым удаленным от точки наблюдения, расположенной в
бесконечности оси z.
Для каждого тела из приоритетного списка:
Проверить экранирование всех лицевых ребер всеми другими телами сцены. Тело,
ребра которого проверяются, называется пробным объектом, а тело, относительно
которого в настоящий момент производится проверка, называется пробным телом.
Естественно, что нужно проверять экранирование пробного объекта только теми
пробными телами, у которых ниже приоритеты
Провести проверки экранирования для прямоугольных объемлющих оболочек пробного объекта и пробного тела:
Если xmin(пробное тело) > xmax(пробный объект) или
xmax(пробное тело) < xmin(пробный объект) или
ymin(пробное тело) > ymax(пробный объект) или
ymax(пробное тело) < ymin(пробный объект),
то пробное тело не может экранировать ни одного ребра пробного объекта. Перейти
к следующему пробному телу. В противном случае:
Провести предварительные проверки протыкания, чтобы увидеть, не протыкается ли пробное тело пробным объектом и существует ли возможность частичного экранирования первого последним.
Сравнить максимальное значение z у пробного объекта с минимальным значением z
у пробного тела.
Если zmzx(пробный объект) < zmin(пробное тело), то протыкание невозможно.
Перейти к следующему телу. В противном случае:
Проверить видимое протыкание.
Если zmzx(пробный объект) > zmin(пробное тело), то пробный объект может
проткнуть переднюю грань пробного тела.
Установить флаг видимого протыкания для последующего использования.
Занести проткнутое тело в список протыкания.
Если xmax (пробный объект) > xmin (пробное тело) или
xmin(пробный объект) < xmax (пробное тело),
То пробный объект может проткнуть бок пробного тела.
Установить флаг видимого протыкания для последующего использования.
Занести тело в список протыкания
Если ymax (пробный объект) > ymin (пробное тело) или
ymin(пробный объект) < ymax (пробное тело),
То пробный объект может проткнуть верх или низ пробного тела.
Установить флаг видимого протыкания для последующего использования.
Занести проткнутое тело в список протыкания
Если список протыканий пуст, то устанавливать флаг протыкания не надо.
Провести проверки экранирования ребер:
Вычислить s и d для ребра.
Вычислить p, q, w для каждой плоскости, несущей грань пробного тела.
Проверка полной видимости. Если ребро полностью видимо, то перейти к
следующему ребру.
Сформировать уравнения hj = 0 и решить их, объединяя попарно и включив
систему уравнений границ t = 0 и t = 1. Если установлен флаг видимого
протыкания, то в систему надо включить и уравнение границы ά = 0.
Запомнить точки протыкания. В противном случае границу ά = 0 не
учитывать.
Для каждой пары (t, ά), являющейся решением, проверить выполнение
условий и hj > 0 для всех других плоскостей. Если эти
условия выполнены, то найти tmaxmin и tminmax
Вычислить видимые участки отрезков и сохранить их для последующей
проверки телами с более низким приоритетом.
Определить видимые отрезки, связывающие точки протыкания.
Если флаг видимого протыкания не установлен, перейти к процедуре
визуализации.
Если точек протыкания не обнаружено, перейти к процедуре
визуализации.
Сформировать все возможные ребра, соединяющие точки протыкания, для пар
тел, связанных отношением протыкания.
Проверить экранирование всех соединяющих ребер обоими телами,
связанными отношением протыкания.
Проверить экранирование оставшихся соединяющих ребер всеми прочими
телами сцены. Запомнить видимые отрезки.
У
Внутри
Внутри
Снаружи
Преобразованное тело [VT]
1 2 3
Внутри
Непреобразованная точка [S]
Бесконечные
плоскости
Х
1
2
5
6
Бесконечные плоскости
Направление взгляда
Точка наблюдения в + ∞
[Е] =[0 0 1 0]
Тело
Внутри
Внутри
Снаружи
Точка в - ∞
[Е]=[0 0 –1 0]
Х
Z
-Z
Нелицевая
плоскость
-z
Пробная точка
[0 0 –1 0]
Нелицевая прямая
6
Нелицевая плоскость
1
5
2
Точка наблюдения
[0 0 1 0 ]
Направление взгляда
[0 0 –1 0]
а
1
х
Нелицевая плоскость
-z
6
2
Направление взгляда
[1 0 –1 0]
Точка наблюдения [-1 0 1 0]
Нелицевая
плоскость
1
1
х
Нелицевая
прямая
Пробная точка
[1 0 –1 0 ]
Р1[-2 0 –2 1]
P2 [2 0 –2 1 ]
-1
-1
1
1
z
j
j-1
P1[-2 0 –2 1 ]
P2 [2 0 –2 1]
Невидимый участок
-1
-2 -1 1 2
1
z
α
t= 3/8 t=5/8
3
2
1
5
α = 5/2
Отрезок невидим
В этой области
α = 3/2
6
2
1
0 0 1.0
t
-1
Р2[0 0 –1 1]
P1 [1 0 –1 1]
Невидимый участок
1
х
z
Направление
взгляда
Точка
Наблюдения [0 0 1 0]
α
2
1
0
0 1.0
t= 1/2
1
5
6
α =3/2
α = 1/2
α = 1/2
α =3/2
6
5
1
t= 1/2
α
2
1
0
0 1.0
t=1
Отрезок невидим
в этой области
P2 [-1 0 –2 1]
-1
Невидимый участок
-1
1
х
1
z
P2 [1 0 2 1]
Точка [0 0 1 0]
наблюдения
α
2
1
0
0
1.0 t
1
t = 3/4
2
5
6
5
2
t = 3/4
1
6
α
2
1
0
0
1.0 t
t=1/4
t = 0
Отрезок невидим в этой области
t=1/4
t =1
Вход
На этом этапе проверяются условия
hj > 0
нет
Выход
t > 1
Выход
да
да
t < 0
нет
Выход
нет
j = e1
j = e2
Hj = pj +qjt +αwj0
Выход
j = j+1
j > n
нет
нет
да
да
нет
да
нет
да
На этом этапе вычисляются
tmaxmin и tminmax
tmin t
ttmin
Выход
Первое
обращение
ttmax
tmax t
Выход
Выход
нет
нет
да
да
нет
нет
-2 -1
1 2
-1
1
P4 [1 1 –1 1]
P3 [-1 1 1 1]
P1 [-2 0 2 1]
z
P2 [2 0 2 1]
Направление взгляда
Точка
Наблюдения [0 0 1 0]