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

Алгоритм Робертса Алгоритм Робертса [2] представляет собой первое известное решение задачи об удалении невидимых линий . Это математически элегантный метод, работающий в объектном пространстве. Алгоритм, прежде всего, удаляет из каждого тела те ребра или грани, ко­торые экранируются самим телом. Затем каждое из видимых ребер каждого тела сравнивается с каждым из оставшихся тел для опре­деления того, какая его часть или части, если таковые есть, экрани­руются этими телами. Поэтому вычислительная трудоемкость ал­горитма Робертса растет теоретически как квад числа объек­тов. Именно этот факт привёл к снижению инте­реса к алгоритму Робертса. Однако математические методы, ис­пользуемые в этом алгоритме, просты, мощны и точны. Кроме то­го, этот алгоритм можно использовать для иллюстрации некоторых важных концепций. Наконец, более поздние реализации алго­ритма, использующие предварительную приоритетную сортировку вдоль оси z и простые габаритные или минимаксные тесты, демонстрируют почти линейную зависимость от числа объектов. В алгоритме Робертса требуется, чтобы все изображаемые тела или объекты были выпуклыми. Невыпуклые тела должны быть разбиты на выпуклые части. В этом алгоритме вы­пуклое многогранное тело с плоскими гранями должно представ­ляться набором пересекающихся плоскостей. Уравнение произвольной плоскости в трехмерном пространстве имеет вид ах + by + cz + d = 0 (2) В матричной форме это выглядит так: или где представляет собой плоскость. Поэтому любое выпуклое твердое тело можно выразить матрицей тела, состоящей из коэффициентов уравнений плоскостей, т. е. где каждый столбец содержит коэффициенты одной плоскости. Напомним, что любая точка пространства представима в однородных координатах вектором Более того, если точка [S] лежит на плоскости, то [S]*[P]T = 0. Если же [S] не лежит на плоскости, то знак этого скалярного произведения показывает, по какую сторону от плоскости расположена точка. В алгоритме Робертса предпола­гается, что точки, лежащие внутри тела, дают положительное ска­лярное произведение. Хотя уравнение плоскости (2) содержит четыре неизвестных коэффициента, его можно нормировать так, чтобы d = 1 следовательно, трех неколлинеарных точек достаточно для определения этих коэффициентов. Подстановка координат трех неколлинеарных точек (x1, y1, z1), (x2, y2, z2), (x2, y2, z2) в нормированное уравнение (2) дает: ax1 + by1 + cz1 = 1 ax2 + by2 + cz2 = 1 ax3 + by3 + cz3 = 1 В матричной форме это выглядит так: или (3) Решение этого уравнения дает значения коэффициентов уравнения плоскости: Другой способ используется, если известен вектор нормали к плоскости, т. е. n = ai + bj + ck где i, j, k - единичные векторы осей x, y, z соответственно. Тогда уравнение плоскости примет вид ax + by + cz + d = 0 (4) ­ Величина d вычисляется с помощью произвольной точки на плоско­сти. В частности, если компоненты этой точки на плоскости (х1, y1, z1) то: d =  (aх1 + by1 + cz1) (5) Поскольку объем вычислений в алгоритмах удаления невидимых линий или поверхностей растет с увеличением числа многоугольни­ков, для описания поверхностей выгодно использовать многоуголь­ники с более чем тремя сторонами. Эти многоугольники могут быть как невыпуклыми, так и неплоскими. Метод, предложенный Мартином Ньюэлом, позволяет найти как точное решение для уравнений плоскостей, содержащих плоские многоугольники, так и «наилучшее» приближение для неплоских многоугольников. Этот метод эквивалентен определению нормали в каждой вершине мно­гоугольника посредством векторного произведения прилежащих ре­бер и усреднения результатов. Если a, b, c, d – коэффициенты уравнения плоскости, то (6) где if (i =n) j = 1 else j++; а d вычисляется с помощью любой точки на плоскости. Перед началом работы алгоритма удаления невидимых линий или поверхностей для получения желаемого вида сцены часто применя­ется трехмерное видовое преобразование. Матрицы тел для объек­тов преобразованной сцены можно получить или преобразованием исходных матриц тел или вычислением новых матриц тел, используя преобразованные вершины или точки. Если [В] - матрица однородных координат, представляющая исходные вершины тела, а [Т] - матрица размером 4х4 видового преобразования, то преобразованные вершины таковы: [ВТ] = [В][T] (7) где [ВТ] - преобразованная матрица вершин. Использование уравнения (3) позволяет получить уравнения исходных плоскостей, ограничивающих тело: [В][V] = [D] (8) где [V] - матрица тела, а [D] в правой части - нулевая матрица. Аналогично уравнения преобразованных плоскостей задаются следующим образом: [ВТ][VТ] = [D] (9) где [VТ] - преобразованная матрица тела. Приравнивая левые части уравнения (8) и (9), получаем [ВТ][VT] = [В][V] Подставляя уравнение (7), сокращая на [В] и умножая слева на [T]-1 имеем [VT] = [T]-1[V] Итак, преобразованная матрица тела получается умножением исходной матрицы тела слева на обратную матрицу видового преобразования. Тот факт, что плоскости имеют бесконечную протяженность и что скалярное произведение точки на матрицу тела отрицательно, если точка лежит вне этого тела, позволяет предложить метод, в котором матрица тела используется для определения граней, которые экранируются самим этим телом. Отрицательное скалярное произведение даёт только такая пло­скость (столбец) в матрице тела, относительно которой точка ле­жит снаружи. Если зритель находится в бесконечности на положительной полуоси z и смотрит на начало координат, то его взгляд направлен в сторону отрицательной полуоси z. В однородных координатах вектор такого направления равен: Не лицевые плоскости к оторый служит, кроме того, образом точки, лежащей в бесконечности на отрицательной полуоси z. Фактически [Е] представляет любую точку, лежащую на плоскости z =  , т. е. любую точку типа (x, y,  ). Поэтому, если скалярное произведение [Е] на столбец, соответствующий какой-нибудь плоскости в матрице тела, отрицательно, то [Е] лежит по отрицательную сторону этой пло­скости. Следовательно, эти плоскости невидимы из любой точки наблюдения, лежащей в плоскости z = , а пробная точка на z =   экранируется самим телом, как показано на рис. 16. Та­кие плоскости называются не лицевыми, а соответствующие им грани задними. Следовательно, [Е][V] < 0 является условием того, что плоскости – не лицевые, а их грани - задние. Заметим, что для аксонометрических проекций (точка наблюдения в бесконечности) это эквивалентно поиску положительных значений в третьей строке матрицы тела. Этот метод является простейшим алгоритмом удаления невидимых поверхностей для тел, представляющих собой одиночные вы­пуклые многогранники. Этот способ часто называют отбрасыванием зад­них плоскостей. Для выпуклых многогранников число граней при этом сокращается примерно наполовину. Метод эквивалентен вы­числению нормали к поверхности для каждого отдельного многоугольника. Отрицательность нормали к поверхности показывает, что нормаль направлена в сторону от наблюдателя и, Следовательно, данный многоугольник не виден. Этот метод можно использовать также и для простой закраски. Интенсивность или цветовой оттенок многоугольника делается пропорциональным проекции нормали к поверхности на направление взгляда. Данный метод определения не лицевых граней в результате фор­мирует аксонометрическую проекцию на некую плоскость, расположенную бесконечно далеко от любой точки трехмерного про­странства. Видовые преобразования, включая перспективное, про­изводятся до определения не лицевых плоскостей. Когда видовое преобразование включает в себя перспективу, то нужно использовать полное перспективное преобразование одного трехмерного пространства в другое, а не перспективное проецирование на неко­торую двумерную плоскость. Полное перспективное преобра­зование приводит к искажению трехмерного тела, которое затем проецируется на некую плоскость в бесконечности, когда не лицевые плоскости уже определены. Этот результат эквивалентен перспек­тивному проецированию из некоторого центра на конечную пло­скость проекции. Видовое преобразование можно применить к телу так, чтобы точка наблюдения оставалась фиксированной. При другом способе тело остается неподвижным. Соответствующие точка наблюдения и направление взгляда получаются умножением справа на матрицу, обратную матрице видового преобразования. После определения нелицевых плоскостей остается найти нелицевые отрезки. Нелицевой отрезок образуется в результате пересечения пары нелицевых плоскостей. После первого этапа удаления нелицевых отрезков необходимо выяснить, существуют ли такие отрезки, которые экранируются другими телами на картинке или в сцене. Для этого каждый остав­шийся отрезок или ребро нужно сравнить с другими телами сцены или картинки. При этом использование приоритетной сортировки (z–сортировки) и простого минимаксного или габаритного с прямо­угольной объемлющей оболочкой тестов позволяет удалить целые группы или кластеры отрезков и тел. Например, если все тела в сцене упорядочены в некотором приоритетном списке, использую­щем значения 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, при которых изменяется значение видимости отрезка. Схема решения показана на рис. 17. Число возможных решений при j уравнениях (плоскостях) равно j(j  1)/2. Каждое решение в диапазонах 0  t  1, a  0, подставляется во все остальные уравнения для проверки того, что условие hj  0 выполнено. Поиск корректных решений производится для того, чтобы найти минимальное среди максимальных значений параметра t(tminmax) Схема решения относительно a и t и максимальное среди минимальных значений 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. Метод решения, обсуждавшийся выше, требует больших затрат машинного времени. Поэтому стоит поискать более быстрые способы определения полностью видимых отрезков. Основная идея состоит в установлении того факта, что оба конца отрезка лежат между точкой наблюдения и какой-нибудь видимой плоскостью. Т.к.

Похожие:

	Контрольная работа №1 Тема контрольной работы №1 Базовые основы компьютерной Области применения компьютерной графики; технические средства компьютерной графики: мониторы, графические адаптеры		«Юго-Западный государственный университет» (юзгу) Кафедра программного... Цель работы: Исследование развития криптографии и способов применения шифров в деятельности человека
	Разработка и исследование интегрированных алгоритмов размещения элементов... Специальности: 05. 13. 12 – Системы автоматизации проектирования, 05. 13. 17 – Теоретические основы информатики		Факультет математики и информационных технологий Кафедра информатики и вычислительной техники Познакомить учащихся с планетами Солнечной системы, сформировать представление о них и о том, отчего на Земле сменяются день, ночь,...
	Учитель математики, информатики и вычислительной техники Образование высшее Стаж работы Урок Правила техники безопасности. Повторение курса 8 класса (двоичная система)		Программа дисциплины Современные проблемы информатики и вычислительной... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 09....
	Рабочая программа по дисциплине В. В основы компьютерной графики Дисциплина «Основы компьютерной графики» является фундаментальной дисциплиной в подготовке бакалавра. Это одна из основных дисциплин...		«Наука компьютерной графики» Сазерленд и доктор Дэвид Эванс (David... После защиты диссертации на тему «Наука компьютерной графики» Сазерленд и доктор Дэвид Эванс (David Evans) открывают в университете...
	Задача изучения дисциплины освоить основные понятия компьютерной... Цель преподавания дисциплины – ознакомление студентов с основами компьютерной графики и графическими программами		Задача изучения дисциплины освоить основные понятия компьютерной... Цель преподавания дисциплины – ознакомление студентов с основами компьютерной графики и графическими программами
	Информатика и вычислительная техника Аналитический обзор по курсу «Современные проблемы информатики и вычислительной техники»		Контрольная работа выполняется в два этапа Составитель: Е. В. Моисеенко, доцент кафедры информатики, инженерной и компьютерной графики вгуэс
	Конспект урока информатики и икт (с использованием технологии сдп... Тема "Использование вспомогательных алгоритмов для рисования орнаментов в исполнителе Чертежник"		Программа по формированию навыков безопасного поведения на дорогах... После защиты диссертации на тему «Наука компьютерной графики» Сазерленд и доктор Дэвид Эванс (David Evans) открывают в университете...
	Программа по формированию навыков безопасного поведения на дорогах... После защиты диссертации на тему «Наука компьютерной графики» Сазерленд и доктор Дэвид Эванс (David Evans) открывают в университете...		Курсовая работа по дисциплине «Информатика и программирование» Кафедра «Программное обеспечение вычислительной техники и автоматизированных систем»