Алгоритм с упорядоченным списком активных ребер (САР)

Достоинства:

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

Алгоритм:

1. Предполагаем что начальная точка любого ребра многоугольника это точка с большей Y координатой. Для каждого ребра создадим структуру данных: y x_0­ dy dx

y - Начальная точка ребра по Y координате

x0 – x координата точки пересечения ребра со сканирующей строкой(крайняя левая точка)

dy – число пересекаемых ребром строк

dx – смещение по X

2.Вычисляем пересечение i+1 сканирующей строки с ребром:

xi+1=xi +1\k, где k=dy\dx тангенс угла наклона ребра

3. Сортируем ребра по возрастанию Y-координаты.

рис3

6 12 5 1

3 3 2 -9

11 3 8 2

11 5 3 -5

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

5. Отсортировываются Х – координаты точек пересечения ребер с текущей сканирующей строкой.

6. определяются интервалы.

7. Закрашиваются интервалы.

8. Увеличиваем dy на 1.

9. Проверяем САР.

10. Если ребра не пересекается с данной сканир строкой – исключаем его из списка.

Растровая развертка многоуголников.

Достоинства:

1.Медленная операция отрисовки вып всего один раз

Недостатки:

1.Требует доп памяти и усложняет алгоритм

Растровая развертка многоугольников инверсией

Алгоритм использует св-ва операции XOR:

рис4

1.Обозначим через i(x,y) состояние пикселя с коорд x,y.

Если I= 1, если пиксель «включен», иначе «не включен»

2. Последовательно выполняем операцию

i(x+1,y)=1(x+1,y) XOR 1(x,y)

Нюансы – растеризация многоугольников.

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

Аппроксимация кривых на плоскости и в пространстве.

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

Аппрокс. ф-ии f(x) это нахождение F(x) которая была бы близка к заданной.

Аппроксимация

Точечная.

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

рис5

рис6

частный вид аппроксимации – интерполяция (налагается строгое условие совпадения в заданных точках xi f(x) От F(x))

Аппроксимация:

-интерполяция

-экстраполяция

Интерполяция:

-глобальная – проходит через все точки заданного интервала

-локальная- интерполируется несколькими ф-иями

-алгебраическая(методы ближайшего соседа)

-полиноминальная

-сплайн-интерполяция

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