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

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

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

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

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

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

не может экранировать это ребро. Использование этих приемов значительно

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

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

представление этого отрезка:

Р(t) = P1 + (Р2 - P1)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]

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

hj = pj + tqj + awj 0 ( t ( 1, a ( 0

где j - номер столбца в матрице тела. Эти условия должны выполняться при

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

Пограничный случай между видимостью и невидимостью возникает, когда hj = 0.

При hj = 0 точка лежит на плоскости. Полагая hj = 0 для всех плоскостей, мы

получим систему уравнений относительно a и t, которые должны

удовлетворяться одновременно. Результат можно получить путем совместного

решения всевозможных пар уравнений из этой системы, при этом будут найдены

все значения a и t, при которых изменяется значение видимости отрезка.

Схема решения показана на рис. 3.10. Число возможных решений при j

уравнениях (плоскостях) равно j(j ( 1)/2. Каждое решение в диапазонах 0 (

t ( 1, a ( 0, подставляется во все остальные уравнения для проверки того,

что условие hj ( 0 выполнено. Поиск корректных решений производится для

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

t(tminmax) и максимальное среди минимальных значений t(tmaxmin). Отрезок

невидим при (tmaxmin) < t < (tminmax). Последнее требование является

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

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

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

добавлении к сцене отрезков, связывающих эти точки. Отрезки образуются

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

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

Затем проверяется экранирование этих отрезков данными телами. Видимые

отрезки образуют структуру протыкания.

Из практики известно, что решения удовлетворяющие неравенствам hj > 0,

могут существовать и за пределами области, ограниченной условиями 0 ( t ( 1

и a = 0. Поэтому три уравнения, описывающие эти границы, т.е. t = 0, t ( 1

= 0 и a = 0, нужно добавить к множеству уравнений hj = 0. Теперь число

решений равно (j + 2)(j + 3)/2, где j - количество плоскостей,

ограничивающих выпуклый объем тела.

Как упоминалось ранее, выбор максимального из минимального и

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

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

программирования. Ее решение эквивалентно определению корректной

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

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

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

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

алгоритма. Алгоритм начинает работу с такими значениями t и a, которые

являются решениями пары линейных уравнений с номерами е1 и е2, а также с

tmin и tmax (текущими минимальным и максимальным значениями t) и с n

(мощностью множества уравнений). На первом этапе алгоритма проверяется

выполнение условий hj > 0. Если эти условия выполнены, то на втором этапе

вычисляются значения tmin и tmax. Результатом являются значения tmaxmin и

tminmax.

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

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

видимых отрезков. Основная: идея состоит в установлении того факта, что оба

конца отрезка лежат между точкой наблюдения и какой-нибудь видимой

плоскостью. Т.к.

u = s + td + ag

При a = 0 значение u задает сам отрезок. Далее, если a = 0, при t = 0 и t =

1 получаются концевые точки отрезка. Также известно, что

hj = u *[VT] = pj + qjt+ wja

и заметим, что при t = 0 pj является скалярным произведением концевой точки

отрезка и j-й плоскости, ограничивающей тело. Аналогично pj + qj является

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

ограничивающей тело. Наконец, напомним, что j-я плоскость, ограничивающая

тело, видима, если wj = 0. Поэтому, если wj ( О и pj ( 0, то один конец

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

точкой наблюдения. Если же pj + qj ( 0, то другой конец отрезка также лежит

либо на видимой плоскости, либо между этой плоскостью и точкой наблюдения.

Следовательно, отрезок полностью видим, если для любого j

wj ( О и pj ( 0 и pj + qj ( 0.

Эти условия гарантируют, что неравенства hj ( 0 не могут быть выполнены

ни при каких a ( 0 и 0 ( t ( 1. Поэтому никакая часть отрезка не может быть

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

Ниже приводится эффективная реализация алгоритма Робертса. Этот

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

индивидуально с целью удаления нелицевых плоскостей. На втором этапе

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

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

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

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

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

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

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

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

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

тела.

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

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

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

вершин.

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

тела.

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

плоскости.

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

Умножить ее слева на матрицу, обратную матрице видового

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

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

преобразованного объема: xmin, xmax, ymin, ymax.

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

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

бесконечности, на преобразованную матрицу тела.

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

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

от необходимости отдельно рассматривать, невидимые линии,

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

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

телами в сцене:

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

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

Провести сортировку по z. Сортировка производится по максимальным

значениям координаты z вершин преобразованных тел. Первым в

упорядоченном списке и обладающим наибольшим приоритетом будет то

тело, у которого минимальное среди максимальных значений z. В

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

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

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

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

сцены. Тело, ребра которого проверяются, называется пробным объектом,

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

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

экранирование пробного объекта только теми пробными телами, у которых

ниже приоритеты.

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

пробного объекта и пробного тела:

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

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

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

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

то пробное тело не может экранировать ни одного ребра пробного объекта.

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

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

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

экранирования первого последним.

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

значением z у пробного тела.

Если zmax (пробный объект) < zmin (пробное тело), то протыкание

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

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

Если zmin (пробный объект) > zmax (пробное тело), то пробный объект

может проткнуть переднюю грань пробного тела.

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

Занести проткнутое тело в список протыканий.

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

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

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

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

Завести тело в список протыканий.

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

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

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

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

Занести проткнутое тело в список протыканий.

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

надо.

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

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

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

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

следующему ребру.

Сформировать уравнения hj = 0 и решить их, объединяя попарно и

включив в систему уравнения границ t = 0 и t = 1. Если установлен

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

границы a = 0. Запомнить точки протыкания. В противном случае границу

a = 0 не учитывать.

Для каждой пары (t, a), являющейся решением проверить выполнение

условий 0 ( t ( 1, a ( 0 и hj > 0 для всех других плоскостей. Если

эти условия выполнены, то найти tmaxmin и tminmax.

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

проверки экранирования телами с более низкими приоритетами.

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

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

визуализации.

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

визуализации.

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

пар тел, связанных отношением протыкания.

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

связанными отношением протыкания.

Проверить экранирование оставшихся соединяющих ребер всеми прочими

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

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

3. Алгоритм использующий 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, равна

z1 ( z = ( (ax1 + d)/c + (ax + d)/c = a(x ( x1)/c

или

z1 = z – (a/c)(x

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

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

сечений поверхностей. Изменится только оператор сравнения:

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

где Zсечения - глубина искомого сечения. Эффект заключается в том, что

остаются только такие элементы поверхности, которые лежат на самом сечении

или позади него.

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

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

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

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

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

основе этого метода, заключается в том, что наблюдатель видит любой объект

посредством испускаемого неким источником света, который падает на этот

объект и затем каким-то путем доходит до наблюдателя. Свет может достичь

наблюдателя, отразившись от поверхности, преломившись или пройдя через нее.

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

убедиться, что весьма немногие из них дойдут до наблюдателя. Следовательно,

этот процесс был бы вычислительно неэффективен. В следствии этого было

предложено отслеживать (трассировать) лучи в обратном направлении, т. е. от

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

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

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

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

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

учитывают эффекты отражения одного объекта от поверхности другого,

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

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

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

Рис.3.11 служит иллюстрацией алгоритма трассировки лучей. В этом

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

изображения. Перспективное преобразование не используется. Считается, что

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

полуоси z. Поэтому все световые лучи параллельны оси z. Каждый луч,

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

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

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

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

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

и объекта. Можно получить большое количество пересечений, если

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

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

данного пиксела. Атрибуты этого объекта используются для определения

характеристик пиксела.

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

лучей лишь незначительно усложняется. Здесь предполагается, что наблюдатель

по-прежнему находится на положительной полуоси z. Картинная плоскость, т.

е. растр, перпендикулярна оси z, как показано на рис 3.12. Задача состоит в

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

плоскость.

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

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

состав сцены можно включать любой объект, для которого можно создать

процедуру построения пересечений. Объекты сцены могут состоять из набора

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

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

поверхностями. Поскольку 75-95% времени, затрачиваемого алгоритмом

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

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

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

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

объектом может оказаться высокой. Чтобы избавиться от ненужного поиска

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

рассматриваемого объекта. И если луч не пересекает оболочки, то не нужно

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

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

рис. 3.13, использование сферы в качестве оболочки может оказаться

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

очень просто. В частности, если расстояние от центра сферической оболочки

до луча превосходит радиус этой сферы, луч не пересекает оболочки.

Следовательно, он не может пересекаться и с объектом.

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

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

параметрическое представление прямой, проходящей через точки P1(x1, y1, z1)

и P2(x2, y2, z2) т. е.:

Р(t) = P1 + (P2 ( P1)t

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

x = x1 +(x2 ( x1)t = x1 +at

y = y1 +(y2 ( y1)t = y1 +bt

z = z1 +(z2 ( z1)t = z1 +ct

Тогда минимальное расстояние d от этой прямой до точки P0(x0, y0, z0)

равно:

d2 = (x ( x0)2 + (y ( y0)2 +(z ( z0)2

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

[pic]

Если d2 > R2, где R - радиус сферической оболочки, то луч не может

пересечься с объектом.

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

пространстве требует большого объема вычислений. При этом следует проверить

пересечение луча по меньшей мере с тремя бесконечными плоскостями,

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

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

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

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

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

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

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

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

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

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

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

перенесенной и повернутой системе координат знаки xmin и xmax, а так же

ymin и ymax. противоположны, как показано на рис. 3.14.

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

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

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

координаты которых удовлетворяют уравнению:

Q (x, y, z) = a1x2 + a2y2 + a3z2 +

b1yz + b2xz + b3xy +

c1x + c2y + c3z +d = 0

После применения преобразования, которое является комбинацией переноса и

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

луча с поверхностью, если оно имеет место, возникает при x = y = 0. Поэтому

в общем случае точки пересечения являются решениями уравнения:

[pic]

т.е.

[pic]

где штрих сверху обозначает коэффициенты общего уравнения поверхности

второго порядка после преобразования. Если [pic], то решения выражаются

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

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

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

пересечения. Если найдено пересечение с бесконечной ограничивающей

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

внутрь. Однако в преобразованной системе координат эту проверку можно

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

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

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

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

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

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

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

поверхности в его исходном положении. Если луч пересекает сферическую

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

алгоритма разбиения предложенного Кэтмулом. Затем луч проверяется на

пересечение со сферическими оболочками подэлементов. Если пересечение не

обнаружено, то луч не пересекается и с самим элементом. Если же луч

пересекается со сферической оболочкой какого-нибудь подэлемента, то

последний разбивается дальше. Процесс завершается, если ни одна из

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

их минимальный размер. Эти сферические оболочки минимального размера и

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

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

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

оболочкам, чем к сферическим. Это сокращает число разбиений и увеличивает

эффективность алгоритма. Для параметрических поверхностей, обладающих

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

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

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

прямоугольных.

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

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

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

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

Метод, подобный этому, можно реализовать в преобразованной системе

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

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

Q (u, w) = 0

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

x = f (u, w)

y = g (u, w)

z = h (u, w)

в преобразованной системе координат выполнено условие x = y = 0. Значит,

f (u, w) = 0

g (u, w) = 0

Совместное решение этой пары уравнений дает значения u и w для точек

пересечения. Подстановка этих значений в уравнение z = h (u, w) дает

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

решение означает, что луч не пересекает поверхность. Степень системы

уравнений для u, w равна произведению степеней биполиномиальных

поверхностей. Бикубическая поверхность, например, имеет шестую степень.

Следовательно, в общем случае потребуются численные методы решения. Там,

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

пересечения луча с выпуклой оболочкой. Для получения пересечений в исходной

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

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

Если трассируемый луч пересекает объекты сцены в нескольких точках, то

необходимо определить видимое пересечение. Для алгоритмов определения

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

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

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

следует упорядочить вдоль луча по расстоянию от его начала. В

преобразованной системе координат этой цели можно достичь простой

сортировкой по z.

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

представить следующим образом:

Подготовка данных для сцены:

Создать список объектов, содержащий по меньшей мере следующую

информацию:

Полное описание объекта: тип, поверхность, характеристики и т. п.

Описание сферической оболочки: центр и радиус,

Флаг прямоугольной оболочки. Если этот флаг поднят, то будет

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

опушен, то тест выполняться не будет. Заметим, что габаритный тест

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

Описание прямоугольной оболочки: xmin, xmax, ymin, ymax, zmin,

zmax.

Для каждого трассируемого луча:

Выполнить для каждого объекта трехмерный тест со сферической

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

сферу, то занести объект в список активных объектов. Если список

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

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

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

Запомнить это комбинированное преобразование.

Для каждого объекта из списка активных объектов:

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

комбинированное преобразование, эту оболочку в систему координат, в

которой находится луч1 и выполнить соответствующий тест. Если

пересечения с лучом нет, то перейти к следующему объекту. В противном

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

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

пересечения с лучом, если они существуют. Занести все пересечения в

список пересечений.

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

значением интенсивности.

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

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

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

исходной системе координат.

Изобразить данный пиксел, используя атрибуты пересеченного объекта и

соответствующую модель освещенности.

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

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

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

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

алгоритм свойств поверхности объекта или ее ориентации в точке пересечения.

Эти шаги включены в данный алгоритм для полноты и удобства при реализации

алгоритма трассировки лучей с учетом общей модели освещенности.

Две модификации этого простого алгоритма заметно повышают его

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

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

состоит из стола, на котором стоят ваза с фруктами и блюдо с конфетами. В

вазе лежат апельсин, яблоко, банан и груша. Блюдо содержит несколько конфет

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

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

конфет в нем, а также для стола и всех предметов на нем. Сферические

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

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

Вводится, кроме того, наибольший сферический кластер, именуемый сферой

сцены, которая охватывает все объекты в этой сцене. Затем сферические

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

сферу сцены, то он не может пересечь и ни одного из ее объектов.

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

фоновым значением интенсивности. Если же луч пересекает сферу сцены, то на

пересечение с лучом проверяются сферические кластеры и сферические оболочки

объектов, не содержащихся ни в одном из сферических кластеров,

принадлежащих кластеру сцены. Если луч не пересекает сферический кластер,

то сам этот кластер и все объекты или кластеры, содержащиеся в нем,

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

то эта процедура рекурсивно повторяется до тех пор, пока не будут

рассмотрены все объекты. Если луч пересекает сферическую оболочку некоего

объекта в какой-нибудь точке, то этот объект заносится в список активных

объектов. Эта процедура значительно сокращает количество вычислений точек

пересечения луча со сферическими оболочками и тем самым повышает

эффективность всего алгоритма.

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

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

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

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

список пересечённых объектов. После рассмотрения всех объектов сцены

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

глубины. Для определения приоритетного порядка можно использовать центры

сферических оболочек или наибольшие (наименьшие) значения z прямоугольных

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

определяются в порядке их приоритетов. К сожалению точка пересечения луча с

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

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

пересечения луча со всеми потенциально видимыми объектами из множества {Q}

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

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

алгоритме. К счастью, множество {Q} потенциально видимых объектов обычно

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

Следовательно, эффективность алгоритма возрастет. Обе эти модификации

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

отражение, преломление и прозрачность.

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

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

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

порядок обработки пикселов. Вместе с тем рассмотрение этих пикселов в

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

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

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

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

следовательно, к повышению эффективности алгоритма. Хотя использование

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

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

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

Например, если в алгоритме учтено отражение, то объект, который полностью

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

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

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

ранее, являются более эффективными.

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

и для создания каркасных чертежей сплошных тел. При этом предполагается,

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

т. е. сверху вниз и слева направо. Получающаяся процедура такова:

Если видимая поверхность для Пиксел(x, y) соответствует фону или

отличается от видимой поверхности для Пиксел(x – 1 , y) или для

Пиксел(x, y – 1), то изобразить этот пиксел. В противном случае пиксел

не изображать.

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

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

вопроса не входит в эту работу. Однако для иллюстрации этого подхода

приведем один пример. В частности, объем любого сплошного тела можно

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

параллелепипедов. Это можно проделать, породив множество параллельных

лучей, расположенных на определенных расстояниях друг от друга. Точки

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

вдоль направления этого луча. Если подвергнуть луч переносу, совмещающему

его с осью z, как это было описано выше, то объем каждого прямоугольного

параллелепипеда будет равен:

[pic]

где lx и ly – расстояние между лучами по горизонтали и вертикали

соответственно. Каждое слагаемое (zi-1 – zi) представляет собой участок

луча, лежащий внутри заданного тела. Объем тела, следовательно, равен сумме

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

зависит от числа использованных лучей. Точность можно повысить, умеренно

увеличив объем вычислений и рекурсивно уменьшив размер «пиксела», в том

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

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

определяются объемы тех элементов тела, где имеют место быстрые изменения,

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

поверхностями.

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

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

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

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

Резюме

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

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

Однако это далеко не все, что имеется. Кроме выше сказанного можно назвать

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

использовании списка приоритетов, разбиения и построчного сканирования.

Этот алгоритм работает в пространстве объекта, получает на входе выпуклые

или невыпуклые многоугольники, а оценка его эффективности линейно зависит

от числа объектов.

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

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

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

Внутренний цикл этого алгоритма изменен так, чтобы можно было реализовать

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

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

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

примерно в 60 раз меньше времени, чем обычный алгоритм трассировки лучей.

В заключении хочу сказать, что компьютерная графика не стоит на месте.

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

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

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

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

уровне процессорной техники (MMX – Intel, 3D Now – AMD), следовательно,

становится возможным реализация «медленных», но дающих лучшее качество

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

виртуальная реальность, которая уже в настоящее время получает широкое

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

тех пор – пока будет развиваться и совершенствоваться компьютерная техника.

Содержание

| Введение |1 |

|1. Введение в машинную графику |2 |

|2. Растровая графика |3 |

| 2.1. Алгоритмы вычерчивания отрезков |3 |

| 2.2. Цифровой дифференциальный анализатор |3 |

| 2.3. Алгоритм Брезенхема |5 |

| 2.4. Алгоритм Брезенхема для генерации окружностей |7 |

| 2.5. Растровая развёртка сплошных областей |14 |

| 2.6. Растровая развёртка многоугольников |14 |

| 2.7. Алгоритм с упорядоченным списком рёбер |17 |

| 2.8. Алгоритм заполнения по рёбрам |18 |

| 2.9. Алгоритм заполнения с затравкой |19 |

| 2.10. Построчный алгоритм заполнения с затравкой |20 |

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

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

| 3.2. Алгоритм Робертса |38 |

| 3.3. Алгоритм использующий z-буфер |50 |

| 3.4. Алгоритм определения видимых поверхностей |53 |

|путём трассировки лучей | |

| Резюме |63 |

Литература:

I. Д. Роджерс «Алгоритмические основы машинной графики»

Москва «Мир» 1989

II. Е. В. Шикин, А. В. Боресков, А. А. Зайцев

«Начала компьютерной графики»

Москва «Диалог - МИФИ» 1993

-----------------------

Рис. 2.11. Гранично-определённая область

Рис. 2.10. Внутренне - определённая область

2. )

2. Основная идея алгоритма Брезенхема

2. Разбор случаев для обобщённого алгоритма Брезенхема.

3. Генерация полной окружности из дуги в первом октанте

4. Окружность в первом квадранте

5. Выбор пикселов в первом квадранте

6. Пересечение окружности и сетки растра

7. Растровая развёртка сплошной области

8. Системы координаты строк сканирования.

9. Особенности пересечения со строками сканирования.

3. Необходимость удаления невидимых линий

2. Секущие плоскости с постоянной координатой

3. Кривые в секущих областях с постоянной координатой

4. Обработка нижней стороны поверхности

5. Линейная интерполяция между заданными точками

6. Эффект пересекающихся кривых

7. Эффект зазубренного ребра

8. Функция y = (1/5) sin x cos z ( (3/2) cos (7a/4) * exp ((a), a = (x (

()2 + (z ( ()2, изображённая в интервале (0, 2() с помощью алгоритма

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

9. Не лицевые плоскости

10. Схема решения относительно a и t

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

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

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

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

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