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

if Флаг = 0 then Флаг = 1

x = x + 1

end while

помещаем в стек крайний справа пиксел

if Флаг =1 then

if ( x = Xправ and Пиксел ( x, y ) ( Гран_значение

and Пиксел ( x, y ) ( Нов_значение ) then

Push Пиксел ( x, y )

else

Push Пиксел ( x ( 1, y )

end if

Флаг = 0

end if

продолжим проверку, если интервал был прерван

Xвход = x

while (( Пиксел ( x, y ) = Гран_значение or

Пиксел ( x, y ) = Нов_значение ) and x < Xправ)

x = x + 1

end while

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

if x = Xвход then x = x + 1

end while

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

уже полностью заполненной

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

выше, за исключением, того что вместо y = y + 1 надо подставить

y = y ( 1

end while

finish

3. Удаление невидимых линий и поверхностей

Задача удаления невидимых линий и поверхностей является одной из

наиболее сложных в машинной графике. Алгоритмы удаления невидимых линий и

поверхностей служат для определения линий ребер, поверхностей или объемов,

которые видимы или невидимы для наблюдателя, находящегося в заданной точке

пространства.

Необходимость удаления невидимых линий, ребер, поверхностей или объемов

проиллюстрирована рис.3.1. На рис.4.1, а приведен типичный каркасный чертеж

куба. Его можно интерпретировать двояко: как вид куба сверху, слева или

снизу, справа. Удаление тех линий или поверхностей, которые невидимы с

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

Результаты показаны на рис.4.1, b и c.

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

появлению большого числа, различных способов ее решения. Многие из них

ориентированы на специализированные приложения. Наилучшего решения общей

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

моделирования процессов в реальном времени, например, для авиа тренажеров,

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

видео генерации (30 кадр/с). Для машинной мультипликации требуются

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

которых представлены тени, прозрачность и фактура, учитывающие эффекты

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

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

даже часов. Строго говоря, учет эффектов прозрачности, фактуры, отражения и

т. п. не входит в задачу удаления невидимых линий или поверхностей.

Естественнее считать их частью процесса визуализации изображения. Процесс

визуализации является интерпретацией или представлением изображения или

сцены в реалистической манере. Однако многие из этих эффектов встроены в

алгоритмы удаления невидимых поверхностей и поэтому будут затронуты.

Существует тесная взаимосвязь между скоростью работы алгоритма и

детальностью его результата. Ни один из алгоритмов не может достигнуть

хороших оценок для этих двух показателей одновременно. По мере создания все

более быстрых алгоритмов можно строить все более детальные изображения.

Реальные задачи, однако, всегда будут требовать учета еще большего

количества деталей.

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

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

котором они работают. Алгоритмы, работающие в объектном пространстве, имеют

дело с физической системой координат, в которой описаны эти объекты. При

этом получаются весьма точные результаты, ограниченные, вообще говоря, лишь

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

много раз. Алгоритмы, работающие в объектном пространстве, особенно полезны

в тех приложениях, где необходима высокая точность. Алгоритмы же,

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

экрана, на котором объекты визуализируются. При этом точность вычислений

ограничена разрешающей способностью экрана. Результаты, полученные в

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

соответствовать исходной сцене. Алгоритмы, формирующие список приоритетов

работают попеременно в обеих упомянутых системах координат.

Объем вычислений для любого алгоритма, работающего в объектном

пространстве, и сравнивающего каждый объект сцены со всеми остальными

объектами этой сцены, растет теоретически как квадрат числа объектов ( n2

). Аналогично, объем вычислений любого алгоритма, работающего в

пространстве изображения и сравнивающего каждый объект сцены с позициями

всех пикселов в системе координат экрана, растет теоретически, как nN.

Здесь n обозначает количество объектов (тел, плоскостей или ребер) в сцене,

а N - число пикселов. Теоретически трудоемкость алгоритмов, работаюoих в

объектном пространстве, меньше трудоемкости алгоритмов, работающих в

пространстве изображения, при n < N. Поскольку N обычно равно ( 512 )2, то

теоретически большинство алгоритмов следует реализовывать в объектном

пространстве. Однако на практике это не так. Дело в том, что алгоритмы,

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

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

Далее дается изложение некоторых алгоритмов, работающих как в объектном

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

одну или несколько основополагающих идей теории алгоритмов удаления

невидимых линий и поверхностей.

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

Алгоритм плавающего горизонта чаще всего используется для удаления

невидимых линий трехмерного представления функций, описывающих поверхность

в виде

F ( x, у, z ) = 0

Подобные функции возникают во многих приложениях в математике, технике,

естественных науках и других дисциплинах.

Существует много алгоритмов, использующих этот подход. Поскольку в

приложениях в основном нас интересует описание поверхности, этот алгоритм

обычно работает в пространстве изображения. Главная идея данного метода

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

исходной поверхности последовательностью параллельных секущих плоскостей,

имеющих постоянные значения координат x, y или z.

На рис. 3.2 приведен пример, где указанные параллельные плоскости

определяются постоянными значениями z. Функция F ( x, у, z ) = 0 сводится к

последовательности кривых, лежащих в каждой из этих параллельных

плоскостей, например к последовательности

y = f ( x, z ) или y = g ( y, z )

где z постоянно на каждой из заданных параллельных плоскостей.

Итак, поверхность теперь складывается из последовательности кривых,

лежащих в каждой из этих плоскостей, как показано на рис. 3.3. Здесь

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

независимых переменных. Если спроецировать полученные кривые на плоскость z

= 0, то сразу становится ясна идея алгоритма удаления невидимых участков

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

z = const по возрастанию расстояния до них от точки наблюдения. Затем для

каждой плоскости, начиная с ближайшей к точке наблюдения, строится кривая,

лежащая на ней. Алгоритм удаления невидимой линии заключается в следующем:

Если на текущей плоскости при некотором заданном значении x

соответствующее значение y на кривой больше значения y для всех

предыдущих кривых при этом значении x, то текущая кривая видима в

этой точке; в противном случае она невидима.

Реализация данного алгоритма достаточно проста. Для хранения максимальных

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

числу различимых точек (разрешению) по оси x в пространстве изображения.

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

«горизонта». Поэтому по мере рисования каждой очередной кривой этот

горизонт «всплывает». Фактически этот алгоритм удаления невидимых линий

работает каждый раз с одной линией.

Алгоритм работает очень хорошо до тех пор, пока какая-нибудь очередная

кривая не окажется ниже самой первой из кривых. Как показано на рис.3.4,а.

Подобные кривые, естественно, видимы и представляют собой нижнюю сторону

исходной поверхности. Однако алгоритм будет считать их невидимыми. Нижняя

сторона поверхности делается видимой, если модифицировать этот алгоритм,

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

алгоритма. Это реализуется при помощи второго массива, длина которого равна

числу различимых точек по оси x в пространстве изображения. Этот массив

содержит наименьшие значения y для каждого значения x. Алгоритм теперь

становится таким:

Если на текущей плоскости при некотором заданном значении x

соответствующее значение y на кривой больше максимума или меньше

минимума по y для всех предыдущих кривых при этом x, то текущая

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

Полученный результат показан на рис. 3.4, b.

В изложенном алгоритме предполагается, что значение функции, т. е. y,

известно для каждого значения x в пространстве изображения. Однако если

для каждого значения x нельзя указать (вычислить) соответствующее ему

значение у, то невозможно поддерживать массивы верхнего и нижнего плавающих

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

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

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

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

результата. Этот эффект проиллюстрирован рис. 3.6,а. Предполагая, что

операция по заполнению массивов проводится после проверки видимости,

получаем, что при переходе текущей кривой от видимого к невидимому

состоянию (сегмент АВ на рис. 3.6,а), точка (xn+k, yn+k ) объявляется

невидимой. Тогда участок кривой между точками (xn, yn) и (xn+k, yn+k ) не

изображается и операция по заполнению массивов не производится. Образуется

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

происходит переход от невидимого состояния к видимому (сегмент CD на рис.

3.6,а), то точка (xm+k, ym+k ) объявляется видимой, а участок кривой между

точками (xm, ym) и (xm+k, ym+k ) изображается и операция по заполнению

массивов проводится. Поэтому изображается и невидимый кусок сегмента CD.

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

у. А это может повлечь за собой дополнительные нежелательные эффекты для

последующих кривы. Следовательно,

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

предшествующей кривых.

Существует несколько методов получения точек пересечения кривых. На

растровых дисплеях значение координаты x можно увеличивать на 1, начиная с

xn или xm (рис. 3.6,а). Значение у, соответствующее текущему значению

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

значению у, соответствующему предыдущему значению координаты x,

вертикального приращения (y вдоль заданной кривой. Затем определяется

видимость новой точки с координатами (x + 1, y + (y ). Если эта точка

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

активируется, а x увеличивается на 1. Этот процесс продолжается до тех пор,

пока не встретится xn+k или xm+k. Пересечения для растровых дисплеев

определяются изложенным методом с достаточной точностью. Близкий и даже

более элегантный метод определения пересечений основан на двоичном поиске.

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

интерполируют текущую и предшествующую кривые, между точками (xn, yn) и

(xn+k, yn+k ) (рис. 3.6) задается формулами:

[pic]

где

[pic]

а индексы c и p соответствуют текущей и предшествующей кривым. Полученный

результат показан на рис. 3.6,b. Теперь алгоритм излагается более

формально.

Если на текущей плоскости при некотором заданном значении x

соответствующее значение y на кривой больше максимума или меньше

минимума по y для всех предыдущих кривых при этом x, то текущая

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

Если на участке от предыдущего (xn) до текущего (xn+k) значения x

видимость кривой изменяется, то вычисляется точка пересечения (xi).

Если на участке от xn до xn+k сегмент кривой полностью видим, то он

изображается целиком; если он стал невидимым, то изображается

фрагмент от xn до xi; если же он стал видимым, то изображается

фрагмент от xi до xn+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. Это можно выполнить

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

идею для обеих ребер.

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

Если Pn является первой точкой на первой кривой, то запомним Pn в

качестве Pn(1 и закончим заполнение. В противном случае создадим

ребро, соединяющее Pn и Pn(1.

Занесем в массивы верхнего и нижнего горизонтов ординаты этого

ребра и запомним Pn в качестве Pn(1.

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

Если Pn является последней точкой на первой кривой, то запомним Pn в

качестве Pn(1 и закончим заполнение. В противном случае создадим

ребро, соединяющее Pn и Pn(1.

Занесем в массивы верхнего и нижнего горизонтов ординаты этого

ребра и запомним Pn в качестве Pn(1.

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

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

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

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

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

на кривой больше максимума или меньше минимума по у для всех

предыдущих кривых при этом x, то кривая видима (в этой точке). В

противном случае она невидима.

Если на сегменте от предыдущего (xn) до текущего (xn+k) значения x

видимость кривой изменяется, то вычисляется пересечение (xi).

Если на участке от xn до (xn+k) сегмент кривой полностью видим, то

он изображается целиком; если он cтал невидимым, то изображается

его кусок от xn до xi; если же он стал видимым, то изображается его

кусок от xi до xn+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 соответственно

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

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, которые ближе всего к горизонтальным при обычном порядке их

следования. Однако после обработки каждой кривой, самой близкой к

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

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

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

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

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

то не надо формировать левое и правое боковые ребра.

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

Алгоритм Робертса представляет собой первое известное решение задачи об

удалении невидимых линий . Это математически элегантный метод, работающий в

объектном пространстве. Алгоритм, прежде всего, удаляет из каждого тела те

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

ребер каждого тела сравнивается с каждым из оставшихся тел для определения

того, какая его часть или части, если таковые есть, экранируются этими

телами. Поэтому вычислительная трудоемкость алгоритма Робертса растет

теоретически как квадрат числа объектов. Именно этот факт привёл к снижению

интереса к алгоритму Робертса. Однако математические методы, используемые в

этом алгоритме, просты, мощны и точны. Кроме того, этот алгоритм можно

использовать для иллюстрации некоторых важных концепций. Наконец, более

поздние реализации алгоритма, использующие предварительную приоритетную

сортировку вдоль оси z и простые габаритные или минимаксные тесты,

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

В алгоритме Робертса требуется, чтобы все изображаемые тела или объекты

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

этом алгоритме выпуклое многогранное тело с плоскими гранями должно

представляться набором пересекающихся плоскостей. Уравнение произвольной

плоскости в трехмерном пространстве имеет вид

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

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

[pic]

или

[pic]

где [pic] представляет собой плоскость. Поэтому любое выпуклое твердое тело

можно выразить матрицей тела, состоящей из коэффициентов уравнений

плоскостей, т. е.

[pic]

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

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

координатах вектором

[pic]

Более того, если точка [S] лежит на плоскости, то [S]*[P]T = 0.

Если же [S] не лежит на плоскости, то знак этого скалярного произведения

показывает, по какую сторону от плоскости расположена точка. В алгоритме

Робертса предполагается, что точки, лежащие внутри тела, дают положительное

скалярное произведение.

Хотя уравнение плоскости (3.1) содержит четыре неизвестных

коэффициента, его можно нормировать так, чтобы d = 1 следовательно, трех

неколлинеарных точек достаточно для определения этих коэффициентов.

Подстановка координат трех неколлинеарных точек (x1, y1, z1), (x2, y2, z2),

(x2, y2, z2) в нормированное уравнение (3.1) дает:

ax1 + by1 + cz1 = (1

ax2 + by2 + cz2 = (1

ax3 + by3 + cz3 = (1

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

[pic]

или

[pic] (3.2)

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

плоскости:

[pic]

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

т. е.

n = ai + bj + ck

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

уравнение плоскости примет вид

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

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

частности, если компоненты этой точки на плоскости (х1, y1, z1) то:

d = ( (aх1 + by1 + cz1) (3.4)

Поскольку объем вычислений в алгоритмах удаления невидимых линий или

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

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

сторонами. Эти многоугольники могут быть как невыпуклыми, так и неплоскими.

Метод, предложенный Мартином Ньюэлом, позволяет найти как точное решение

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

«наилучшее» приближение для неплоских многоугольников. Этот метод

эквивалентен определению нормали в каждой вершине многоугольника

посредством векторного произведения прилежащих ребер и усреднения

результатов. Если a, b, c, d – коэффициенты уравнения плоскости, то

[pic] (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. В однородных координатах вектор такого направления

равен:

[pic]

который служит, кроме того, образом точки, лежащей в бесконечности на

отрицательной полуоси z. Фактически [Е] представляет любую точку, лежащую

на плоскости z = ( (, т. е. любую точку типа (x, y, ( (). Поэтому, если

скалярное произведение [Е] на столбец, соответствующий какой-нибудь

плоскости в матрице тела, отрицательно, то [Е] лежит по отрицательную

сторону этой плоскости. Следовательно, эти плоскости невидимы из любой

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

экранируется самим телом, как показано на рис. 3.8. Такие плоскости

называются не лицевыми, а соответствующие им грани задними.

Следовательно,

[Е][V] < 0

является условием того, что плоскости – не лицевые, а их грани - задние.

Заметим, что для аксонометрических проекций (точка наблюдения в

бесконечности) это эквивалентно поиску положительных значений в третьей

строке матрицы тела.

Этот метод является простейшим алгоритмом удаления невидимых

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

многогранники. Этот способ часто называют отбрасыванием задних плоскостей.

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

наполовину. Метод эквивалентен вычислению нормали к поверхности для каждого

отдельного многоугольника. Отрицательность нормали к поверхности

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

Следовательно, данный многоугольник не виден.

Этот метод можно использовать также и для простой закраски.

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

проекции нормали к поверхности на направление взгляда.

Данный метод определения не лицевых граней в результате формирует

аксонометрическую проекцию на некую плоскость, расположенную бесконечно

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

включая перспективное, производятся до определения не лицевых плоскостей.

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

использовать полное перспективное преобразование одного трехмерного

пространства в другое, а не перспективное проецирование на некоторую

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

искажению трехмерного тела, которое затем проецируется на некую плоскость в

бесконечности, когда не лицевые плоскости уже определены. Этот результат

эквивалентен перспективному проецированию из некоторого центра на конечную

плоскость проекции.

Видовое преобразование можно применить к телу так, чтобы точка

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

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

получаются умножением справа на матрицу, обратную матрице видового

преобразования.

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

отрезки. Нелицевой отрезок образуется в результате пересечения пары

нелицевых плоскостей. После первого этапа удаления нелицевых отрезков

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

другими телами на картинке или в сцене. Для этого каждый оставшийся отрезок

или ребро нужно сравнить с другими телами сцены или картинки. При этом

использование приоритетной сортировки (z–сортировки) и простого

минимаксного или габаритного с прямоугольной объемлющей оболочкой тестов

позволяет удалить целые группы или кластеры отрезков и тел. Например, если

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

Страницы: 1, 2, 3