Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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

 

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

,

где O - множество объектов в трехмерном пространстве;

S - множество видимых отрезков в двумерном пространстве;

I - множество "промежуточных представлений";

f - множество "функций перехода", ;

st - "функция стратегии".

Рассмотрим смысл функций, входящих в множество f. Каждая функция перехода может иметь несколько вариантов реализации, применяемых в различных алгоритмах удаления. Т.е. каждая функция может представлять некоторый класс отображений.

PM - функция преобразования проецирования. Она строит проекции (чаще перспективные), т.е. преобразует трехмерное пространство в двумерное.

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

1. Найти точку отрезка прямой, в которой происходит изменение видимости;

2. Определить, имеется ли непустое пересечение проекций 2 многоугольников на картинную плоскость (см. 3-ю эвристику: при пустом пересечении возможна независимая обработка непересекающихся фрагментов);

3. Найти точки пересечения объектов со сканирующей прямой (см. растровые алгоритмы);

4. Использовать результат в тесте принадлежности (см. далее);

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

Пересекающиеся прямые описываются системой линейных уравнений:

 

.

Если , прямые параллельны. Если , прямые совпадают. Иначе - точка пересечения имеет координаты , .

Известные математические выкладки позволяют также в аналитической форме получить формулы для пересечения двух отрезков и пересечения плоскости и прямой. Для выпуклых многоугольников дело обстоит сложнее. С помощью анализа минимаксного выражения можно установить, перекрываются многоугольники или нет. Точки пересечения определяются с помощью ряда шагов, среди которых - тест пересечения. Более подробно аналитические выражения и описание шагов приведено в [ 9 ].

CT - функция, выполняющая в двумерном пространстве "тест принадлежности", т.е. проверяющая, лежит ли некоторая точка внутри многоугольника. Результат - булева переменная ИСТИНА или ЛОЖЬ. Проверку на принадлежность методом подсчета числа пересечений рассматривали ранее. Есть еще один тест, известный из элементарной геометрии. Соединим прямыми ис-

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

Каждая пара соседних прямых образует угол. Точка нахо-

дится вне многоугольника, если сумма углов равна 0, и

и внутри, если эта сумма равна .

DT - функция, выполняющая "тест глубины", т.е. сравнивающая 2 точки и определяющая, какая из них расположена дальше/ближе от точки наблюдения. Одна или обе сравниваемые точки могут принадлежать некоторой грани. Следовательно, сравниваются точка - точка, точка - грань, грань - грань. Под глубиной понимается расстояние между элементом и картинной плоскостью или между элементом и точкой наблюдения. Т.е. глубина относится к z -координате элемента, тест глубины заключается в сравнении z -координат двух элементов. Имеются 3 теста глубины. Обозначим их DT1, DT2, DT3.

1. Тест DT1 применяется для объектного пространства. Он сопоставляет грань и точку и определяет, заслоняет ли грань точку. Для этого ищется точка пересечения грани с так называемой "линией визирования”, т.е.

 

 

       
 
   
 

 


Точка протыкания

Точка наблюдения

 

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

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

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

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

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

общей для проекций на эту плоскость обеих граней. Затем находятся

точки на гранях, которые проецируются в выбранную точку. Для этого

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

содержащих грани, и эти уравнения решаются относительно координа-

наты z (параллельная проекция, точка наблюдения находится в бесконечности и лежит на ли-

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

ния). Точка плоскости выбирается так, чтобы было . Считается, что грань f1 имеет

приоритет над гранью f2, если . Поэтому тест DT2 называют также приоритетным тес-

том. y

 
 

 


f1 f2

P1 P2 P12


z

Точка

наблюдения х

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

Для проникающих граней и циклического перекрытия тест "в лоб" не работает. Поэтому грани разбивают (штриховая линия на рисунке).

       
   
 
 

 

 


Проникающие грани Циклическое перекрытие

3. Тест DT3 - самый простой. Он применяется в растровых алгоритмах при проверке видимости проекций граней на картинную плоскость вдоль сканирующей прямой. На сканирующей прямой выбирают интервалы, где нет пересечения проекций и нет проникающих граней в объектном пространстве. Для этих интервалов просто сравниваются z -координаты сегментов проекций. Видимый сегмент имеет наибольшую z -координату и образует полоску растровой прямой.

VT - функция, выполняющая "тест видимости" для данной поверхности. Она выдает значение ИСТИНА, если поверхность видима и ЛОЖЬ в противном случае. Применяется только к телам. Определяет, является ли некоторая грань тела "передней", т.е. потенциально видимой, или "задней". Очевидно, что тест может применяться только к структурированным объектам в объектном пространстве. К гладким поверхностям тест неприменим. Если имеется несколько объектов, то тест видимости не решает вопросы загораживания. Он выявляет только заведомо невидимые элементы каждого тела. Они не участвуют в последующих вычислениях.

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

Используется формулировка "потенциально видима", т.к. для невыпуклых тел или для нескольких тел нужны дополнительные тесты, проверяющие взаимное затенение. Процедура определения невидимости занимает немного времени, т.к. если найдена одна грань, затеняющая другую, то незатененную грань можно не проверять (справедливо для выпуклых тел, для невыпуклых тел тест не работает). Это позволяет сократить количество граней, участвующих в проверке на загораживание, т.е. существенно сократить время решения задачи.

Функция стратегии st определяет порядок применения функций из множества f для получения требуемого результата. Возможны 2 подхода к решению задачи и соответственно 2 типа алгоритмов: объектные и картинные. Объектный подход рассматривает видимость в объектном пространстве. При этом сначала выполняется тест видимости, потом - преобразование проецирования. Временные характеристики таких алгоритмов обычно обладают квадратичной зависимостью от числа объектов сцены. Картинный подход рассматривает видимость в пространстве отображения. Определяется видимость каждого элемента картинной плоскости (т.е. каждого пиксела). При этом сначала выполняется преобразование проецирования, потом - тест видимости. Временные характеристики таких алгоритмов оцениваются как линейные функции от произведения числа объектов на число точек растра. Существуют и смешанные алгоритмы, использующие как первый, так и второй подход.

 

<== предыдущая лекция | следующая лекция ==>
Исходные эвристики | Алгоритм Робертса
Поделиться с друзьями:


Дата добавления: 2014-01-11; Просмотров: 567; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.036 сек.