а = (yi - yJ)(zi + ZJ)
-28-
b - (zi - zj)(xi + xj)
с = (xi - xj)(yi + у)),где ]=1+1,если i=3,To j=l, а коэффициент d вычисляется с помощью любой точки на плоскости.
Перед реализацией алгоритма удаления невидимых линий и поверхностей для получения нужного положения синтезируемой сцены обычно проводится трехмерное видовое преобразование. Матрицы объектов преобразованной сцены можно получить или преобразованием исходных матриц объектов визуализации или вычислением новых матриц объектов, используя преобразованные вершины или другие точки объектов.
Предположим, что [В] - матрица однородных координат, задающая исходные вершины объекта, [Т] - матрица видового преобразования размером 4*4. Тогда координаты преобразованных вершин опи-шуться с помощью соотношения:
[ВТ] = [В][Т]; а уравнения исходных плоскостей, ограничивающих объект:
где [D] - ненулевая матрица. Аналогично, уравнения преобразованных плоскосстей задаются следующим образом:
где [VT] - преобразованная матрица объекта. Приравнивая левые части двух последних соотношений, получаем:
[BT][VT] = [B][V]. Затем преобразовываем к виду:
[VT] = [Т] [V].
Таким образом, преобразованная матрица объекта получается умножением исходной матрицы объекта слева на обратную матрицу видового преобразования .
плоскостей (рис. ).
После удаления нелицевых граней и ребер для каждого объекта выполняется самая трудоемкая часть алгоритма : проверка каждого оставщегося ребра на закрытие другими объектами. При этом использование Z - сортировки и простого минимаксного или габаритного с прямоугольной объемлющей оболочкой тестов позволяет удалить целые группы ребер и объектов. Например, все тела в сцене упорядочиваются в некоторый преоритетный список по значениям Z ближайших вершин и расстояния до наблюдателя. Тогда никакой объект из этого списка, у которого ближайшая точка находится дальше от наблюдателя, чем самая удаленная из концевых точек ребра, не может закрывать это ребро. Более того, ни одно из оставшихся тел, прямоугольная оболочка которого расположена полностью справа, слева, над или под ребром, не может экранировать это ребро. Использование этих приемов значительно сокращает число тел, с которыми нужно сравнивать каждый отрезок или ребро.
Для сравнения отрезка (R1,R2) с объектом используется параметрическое представление этого отрезка:
R(t) = Rl +(R2 -Rl)t , 0<=t<=l (6.2)
или
V = S + dt,
где V - вектор точки на отрезке, S - начальная точка, a d - направление отрезка.
Необходимо определить: существуют ли значения t, при которых данный отрезок или ребро невидимы. Для этого формируется другой отрезок от точки R(t) до точки наблюдения g :
Q(f,t) = U = V + gf = S + dt + gf , 0<=t<=l , f>=0. Значение t указывает точку на отрезке R(t) , a f указывает точ-
ку на отрезке, проведенном от точки R(t) до точки наблюдения. Фактически Q(f,t) представляет собой плоскость в трехмерном пространстве, a (f,t) определяет точку на этой плоскости. Значение f всегда положительно, ибо объекты, экранирующие R(t), могут находиться только в той части данной плоскости, которая заключена между исследуемым отрезком R(t) и точкой наблюдения.
Скалярное произведение любой точки, расположенной внутри объекта, на матрицу тела положительно. Если точка лежит внутри тела, то она невидима. Следовательно, для определения невидимой части ребра, которая экранируется объектом, достаточно определить те значения f и t, для которых скалярное произведение Q(f,t) = U на матрицу объекта положительно:
Н = U [VT] = S[VT] + dt[VT] + gf[VT] > 0. (6.3)
Те значения t и f, для которых все значения компоненты Н положительны соответствуют невидимой части ребра.
Обозначим: p = S[VT] , q = d[VT] , w = g[VT].
Тогда условие (6.3) запишется в виде:
Hj = pj + tqj + fwj > 0 , (6.4)
где j - номер столбца в матрице объекта.
Условия (6.4) должны выполняться для всех плоскостей, ограничивающих объект, то есть для всех j.
Случай, когда Hj = 0, является граничным между видимой и не-видомой частями ребра. Полагая Hj = 0 для всех плоскостей, получают систему уравнений относительно t и f, которые должны удовлетворяться одновременно. Решая эту систему уравнений, находят все значения t и f, при которых изменяется значение видимости ребра или части ребра (число возможных возможных решений при j
плоскостях равно j(j - 1)/2). Затем каждое решение в интервалах 0<=t<=l , f>=0, подставляется во все остальные неравенства системы (6.3) для проверки того, что условие Hj >= 0 выполнено. Поиск корректных решений производится для того, чтобы найти минимальное среди максимальных значений параметра t (t minmax) и максимальное среди минимальных значений t (t maxmin). Подставляя эти значения в уравнение (6.2) определяют видимые участки ребра на интервалах [0,t maxmin] и [t mimmax,!]. Условие экранирования ребер или отрезков ребер является простым следствием из классической задачи линейного программирования:
t maxmin < t, t minmax.
Решения, удовлетворяющие неравенствам Hj > 0, могут существовать и за пределами области, ограниченной условиями:
0<=t<=l и f>=0.
Поэтому к системе (6.4) необходимо добавить три уравнения, описывающие эти границы:
t = 0, t-1 =0 и f=0. Тогда число решений будет равно (j + 2)(j + 3)/2.
Для ускорения работы алгоритма перед определением t maxmin и t minmax удаляются не только нелицевые ребра, но и полностью видимые ребра. Видимые ребра определяются на основании того, что оба конца такого ребра должны лежать между точкой наблюдения и какой-либо видимой плоскостью. При f = 0 значение U задает сам отрезок. Далее, если f = 0, то при t = 0 и t = 1 получаются концевые точки отрезка. Из соотношений (6.4) видно, что при t = 0 pj является скалярным произведением концевой точки отрезка и j - ой плоскости. Аналогично, pj + qj является скалярным произведением другой концевой точки отрезка и j-ой плоскости. В свою очередь,
j-я плоскость, ограничивающая объект видима, если wj <= 0. Следовательно, если wj <=0 , pj <= 0 и pj + qj <=0, то отрезок полностью видим , а оба его конца лежат либо на видимой плоскости, либо между этой плоскостью и точкой наблюдения.
Для полностью невидимых ребер объекта отсутствуют простые тесты из-за бесконечности плоскостей. Поэтому полностью невидимые ребра определяют также как и частично невидимые ( в этом случае невидимый участок будет простираться от t = 0 до t = 1).
После определения частично видимых или полностью невидимых ребер определяются пары объектов, связанных отношениями протыкания, (в случае протыкания объектов сцены возникают решения на границе f = 0) и вычисляются отрезки, которые образуются при протыкании объектами друг друга. Эти отрезки проверяются на экранирование всеми прочими объектами сцены. Видимые отрезки образуют структуру протыкания.
Таким образом, реализация алгоритма Робертса подразделяется на следующие этапы (рис. ):
1. Определение коэффициентов уравнения плоскости каждой гра
ни, проверка правильности знака уравнения и формирование матрицы
объекта визуализации.
2. Проведение видового преобразования матрицы объекта, вы
числение прямоугольной охватывающей оболочки объекта.
3. Определение нелицевых граней, удаление их из списка гра
ней и соответствующих ребер - из списка ребер.
4. Определение списка других объектов синтезируемой сцены,
которые могут быть экранированы данным объектом визуализации на
основании сравнений охватывающих оболочек объектов.
5. Формирование списка протыканий также на основании сравне-
-34-
ний охватывающих оболочек объектов.
6. Определение невидимых ребер или участков ребер. Практическая реализация данного этапа основана на том, что скалярное произведение любой точки, лежащей внутри объекта на матрицу объекта положительно.
7.Формирования списка возможных ребер, соединяющих точки протыкания, для пар объектов, связанных отношением протыкания.
8.Проверка видимости полученных ребер по отношению ко всем объектам сцены в соответствии с действиями этапов 3 и 6.
9.Визуализация изображения.
6.2. АЛГОРИТМ ВАРНОКА
Алгоритм Варнока работает в пространстве изображений. В основу алгоритма положен принцип «разделяй и властвуй», состоящий в разбиении области рисунка на более мелкие подобласти (окна). Для каждой подобласти (окна) определяются связанные с ней многоугольники и те из них, видимость которых определить «легко», изображаются на экране. В противном же случае разбиение повторяется, и для каждой из вновь полученных подобластей рекурсивно применяется процедура принятия решения.
Предполагается, что с уменьшением размеров области ее перекрывает все меньшее и меньшее количество многоугольников. Считается, что в пределе будут получены области, содержащие не более одного многоугольника, и решение будет принято достаточно просто. Если же в процессе разбиения будут оставаться области, содержащие не один многоугольник, то следует продолжать процесс разбиения до тех пор, пока размер области не станет совпадать с одним пикселом. В этом случае для полученного пиксела необходи-
мо вычислить глубину (значение координаты Z) каждого многоугольника и визуализировать тот из них, у которого максимальное значение этой координаты (считаем, что наблюдатель находится на оси Z в плюс бесконечности).
В процессе анализа взаимного расположения окна и многоугольника могут быть получены следующие варианты:
1) многоугольник внешний (целиком находится за пределами об
ласти);
2) многоугольник внутренний (целиком лежит внутри области);
3) пересекающий многоугольник (пересекает область, т. е. одна
часть его лежит внутри области, другая - за пределами об
ласти);