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

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

Это скалярное произведение равно:

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

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

p = s * [VT]

q = d * [VT]

w = g * [VT]

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

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

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

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

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

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

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

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

u = s + td + ag

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

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

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

w_j £ О и p_j £ 0 и p_j + q_j £ 0.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Альтернативой созданию специальной памяти для z-буфера является использование для этой цели оперативной или массовой памяти. Уменьшение требуемой памяти достигается разбиением пространства изображения на 4, 16 или больше квадратов или полос. В предельном варианте можно использовать z-буфер размером в одну строку развертки. Для последнего случая имеется интересный алгоритм построчного сканирования. Поскольку каждый элемент сцены обрабатывается много раз, то сегментирование z-буфера, вообще говоря, приводит к увеличению времени, необходимого для обработки сцены. Однако сортировка на плоскости, позволяющая не обрабатывать все многоугольники в каждом из квадратов или полос, может значительно сократить этот рост.

Другой недостаток алгоритма z-буфера состоит в трудоемкости и высокой стоимости устранения лестничного эффекта, а также реализации эффектов прозрачности и просвечивания.

Более формальное описание алгоритма z-буфера таково:

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

Заполнить z-буфер минимальным значением z.

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

Для каждого Пиксел(x, y) в многоугольнике вычислить его глубину z (x, y).

Сравнить глубину z (x, y) со значением Z буфер(x, y), хранящимися в z-буфере в этой же позиции.

Если z (x, y) > z буфер (x, y), то записать атрибут этого многоугольника (интенсивность, цвет и т. п.) в буфер кадра и заменить z-буфер(x, y) на z (x, y).

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

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

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

ax + by + cz + d =0

z = - ( ax + by + d)/c ¹ 0

Для сканирующей строки y = const. Поэтому глубина пиксела наэтой строке, у которого x = x + Dx, равна

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

или

z₁ = z – (a/c)Dx

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

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

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

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

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

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

Похожие работы

Компьютерная графика и решаемые ею задачи

Скачать

17177

0

0

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

Тенденции развития рынка компьютерной графики и анимации

Скачать

20082

0

0

... в качестве реальной альтернативы системе Unix.  _ 23.Платформа Intel ПК с процессором Intel продолжает оставаться наиболее распространённой платформой в сфере компьютерной графики и анимации. Главным событием, имеющим к ней непосредственное отноше- ние, стала демонстрация компанией Autodesk четвёртой версии программы 3D Studio - ...

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

Скачать

29081

0

3

... простыми. Большинство цветовых оттенков образуется смешением основных цветов. Способ разделения цветового оттенка на составляющие компоненты называется цветовой моделью. Существует много различных типов цветовых моделей, но в компьютерной графике, как правило, применяется не более трех. Эти модели известны под названиями: RGB, CMYK, НSB. Цветовая модель RGB Наиболее проста для понимания и ...

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

Скачать

66016

2

0

... прочие). В соответствии с принципами формирования изображения аддитивным или субтрактивным методами разработаны способы разделения цветового оттенка на составляющие компоненты, называемые цветовыми моделями. В компьютерной графике в основном применяют модели RGB и HSB (для создания и обработки аддитивных изображений) и CMYK (для печати копии изображения на полиграфическом оборудовании). Цветовые ...