Метод построчного сканирования

Метод работает в картинной плоскости. Аналогично предыдущему методу используется в ряде алго­ритмов. Сцена в пространстве пересекается семейством плоскостей, проходящих через линии горизонтальной развертки растра и точку наблюдения (центр проектирования). На картинной плоскости каждая плоскость сече­ния порождает совокупность отрезков. Чтобы определить, какой из отрезков отображать на картинной плоско­сти, для плоскости сечения решается задача загораживания, т.е. трехмерная задача сводится к двумерной. Для того, чтобы определить, какой из нескольких накладывающихся друг на друга отрезков рисовать, можно применить тест видимости DT3, сравни­вая z-координаты объектов сцены в данной секущей плоскости и выби­рая наименьшую из этих координат по отношению к наблюдателю. Алго­ритм повторяется для всех секущих плоскостей.

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

30. Подсчет количественной невидимости с помощью алгоритма Аппеля.

Метод работает с многогранниками Он основан на подсчете количественной невидимости - числа точек, закрывающих данную точку поверхности. Число закрывающих точек равно числу закрывающих лицевые граней. Точка видима, если ее количественная невидимость равна 0.

Как изменяется количественная невидимость вдоль ребра? Естественно, рассматриваются только потенциально видимые ребра. т.е. перед работой алгоритма выполняется тест видимости. Количес­твенная невидимость точек ребра изменяется на единицу при прохо­ждении ребра позади контурной линии. Контурная линия состоит из ребер, для которых одна из составляющих ребро граней видима (ли­цевая), другая - нет. На рисунке контурной является ломаная ABCUDEKLGA.

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

Работа алгоритма начинается с выбора какой-либо вершины многогранника и определения ее количест­венной невидимости. Для этого через эту точку и точку наблюдения проводится отрезок прямой и находятся пересечения этого отрезка со всеми гранями (как в тесте глубины DT1). Число найденных граней - количественная невидимость начальной точки. Далее прослеживается изменение количественной невидимости вдоль каждого из ребер, выходящих из этой вершины Эти ребра проверяются на прохождение позади контурной линии, что изменяет количественную невидимость. Части отрезка с нулевой количественной невидимостью сразу рисуются Далее выбирается вершина, образуемая одним из рассмотренных ребер. Для нее количественная невидимость подсчитана, процесс повторяется. Как определить пересечение рассматриваемого ребра с контурным? Аппель предлагает следующее. Образуется треугольник, вершинами кото­рого являются точка наблюдения и концы исследуемого ребра. Контурное ребро изменяет количественную невидимость ребраq, если оно протыкает треугольник, т.е. точка пересечения контурного ребра с плоскостью треугольника лежит внутри треугольни­ка. Если пересечение существует, количественная невидимость q увеличивается на 1 при положительном знаке векторного произве­дения контурного и рассматриваемого ребер и уменьшается на 1 в противном случае.

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

Подсчет количественной невидимости можно применять и для гладких поверхностей. Здесь контур­ные линии являются гладкими кривыми. Количествен­ная невидимость точки изменяется, если точка поверх­ности проектируется на проекцию контурных линий (это происходит при наличии складок в теле). Складка изменяет невидимость на 2.

31. Удаление невидимых линий и поверхностей с помощью методов приоритетов (упорядочения).

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

1. Накладываются ли друг на друга отрезки при проектировании проекций граней в плоскости XY на ось X.

2. Накладываются ли друг на друга отрезки при проектировании проекций граней в плоскости XY на ось Y.

3. Находится ли грань Р по отношению к плоскости, проходящей через грань Q, по другую сторону, чем наблюдатель.

4. Находится ли грань Q по отношению к плоскости, проходящей через грань Р, по ту же сторону, что наблюдатель.

5. Пересекаются ли проекции граней Р и Q на картинную плоскость.

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

3а. Находятся ли грань Q и наблюдатель по разные стороны плоскости, проходящей через грань Р.

4а. Находится ли грань Р и наблюдатель по одну сторону плоскости, проходящей через грань Q.

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

32. Триангуляция.

Объекты пространства описываются функцией 2 переменных. Т.к. аналитические выражения для таю объектов весьма сложны и при непосредственном использовании требуют больших вычислительных ресурсе (это видно даже для простейшего случая прямой - программа п. 6.4.1), применяется аппроксимация более простыми фигурами. Наиболее часто используется кусочно-линейная аппроксимация, когда поверхность составляется из каких-либо плоских фигур. Имеются некоторые каноны аппроксимации, позволяющие получать наиболее рациональные результаты. Так кривая апроксимируется отрезками прямой, плоская фигура сложной формы - прямоугольниками или квадратами. Гладкие поверхности - непересекающимися треугольниками. Процесс триангуляции состоит в создании сети непересекающихся треугольников с вершинами в заданных точках.

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

1. Отсутствует единый масштаб для всех данных, когда размер ячейки прямоугольной сетки автоматически устанавливает предел подробности карты, и сгущения точек отображаются только в пределах размера решетки. Размер треугольника при триангуляции не устанавливается. Там, где исходные точки разрежен (поверхность приближается к плоской), треугольники крупнее, при сгущении точек (большой кривизне поверхности) треугольники мельче Количество треугольников определяется количеством исходных точек аппроксимации. Эйлер доказал теорему, что оно не превышает удвоенного количества исходных точек;

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

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

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

1. треугольник и плоскость не пересекаются, т.е. все вершины лежат по одну сторону плоскости;

2. треугольник касается плоскости одной вершиной, все вершины лежат по одну сторону плоскости;

3. треугольник пересекается с плоскостью по ребру, две вершины лежат на плоскости, все вершины лежат п одну сторону плоскости;

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

5. треугольник лежит в плоскости, т.е. все вершины лежат в плоскости.

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

33. Закраска методами Гуро и Фонга.

Закраска методом Гуро

Метод основан на определении освещенности грани в ее вершинах с последующей билинейной (би=2) интерполяцией результатов на всю грань. Пусть проекция некоторой грани на экран является выпуклым 4-угольником Пусть интенсивности вершин определены и равны I1,I2,I3,I4. Пусть W - произвольная точка грани. Проведем через нее горизонталь. Пусть Р и Q - точки пересечения горизонтали с границами проекции грани. Будем считать, что интенсивность на отрезкеPQ меняется линейно, те.

Для определения интенсивности в точках Р и Q снова применяется линейная интерполяция (отсюда термин билинейная). Считаем, что вдоль каждого из ребер границы интенсивность меняется линейно. Тогда ин­тенсивность в точках Р и Q:

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

Поиск по сайту: