Алгоритмы рисования закрашенного многоугольника

Алгоритм де Костельжо

Кривые Безье. Алгоритм де Костельжо

Кривые Безье — это универсальный способ задания произвольных кривых на плоскости или в пространстве. Задаются многочленом Берштейна:

где

n — степень кривой

P₀ .. P_n — опорные точки, их как минимум две

t ∈ [0,1]

Свойства:

● Гладкость и непрерывность

● Количество изгибов зависит от количества опорных точек

● Степень многочлена Берштейна на один меньше количества опорных точек

● Легко выполнить сложные преобразования (поворот, перенос,..., либо их комбинация)

● Кривая лежит в оболочке опорных точек, которая является многоугольником.

● Кривая всегда проходит через P₀ и P_n, и в этих точках касательные к кривой параллельны отрезкам P₀P₁ и P_n-1P_n.

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

● Если кривую Безье разбить точкой P(t*), то мы получим две кривые Безье: t ∈ [0,t*] и t ∈ [t*,1]. Таким образом, кривую Безье высшего порядка порядка можно представить в виде набора кривых Безье низшего порядка.

Недостатки:

● Очень много вещественных вычислений

● Трудно подобрать Δt:

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

○ если взять слишком маленьким, прорисовка будет повторяться несколько раз.

Задача: построить кривую P(t) по ломаной P₀ … P_n.

Сначала берем t* = ⅓ и делим в таком отношении каждое звено ломаной. Полученные точки соединяем и получаем новую ломаную, степень которой меньше степени исходной ломаной на 1. Повторяем процесс, пока степень не станет равной единице, то есть пока ломаная не выродится в точку. Эта точка будет принадлежать кривой Безье.

Дальше берем t* = ½ и повторяем алгоритм, и так далее, пока t* не сольётся с P₀ (с заданной точностью)

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

NURBS— рациональные кривые Безье. Для каждой точки вводится ещё и вес (может быть и отрицательным). Он показывает, насколько точка “притягивает” к себе кривую. В этом случае кривая задается: — многочлен Берштейна.

В обычной кривой Безье все w = 1.

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

1 Алгоритм с упорядоченным списком рёбер (для закраски многоугольников)

Горизонтальные прямые, параллельные оси ОХ, пересекают многоугольник в нескольких точках, их число четное.

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

2 Находятся координаты всех пикселей, которые принадлежат границам. Не рассматриваются вершины многоугольника и торцевые ребра (принадлежащие охватывающему прямоугольнику).

3 Массив с этими координатами сортируется, причем сначала сравниваются координаты y, а потом — х.

4 В полученном массиве первая точка соединяется со второй, …, i-я c (i + 1)-ой. Таким образом получаются горизонтальные отрезки, находящиеся внутри многоугольника, которые называются сканирующими строками.

Недостаток:

○ при большом количестве точек на сортировку уйдёт много времени.

Решение недостатка: Разделим массив точек на несколько маленьких. Можно разделить так, чтобы в каждом массиве были точки с одинаковой координатой у. Тогда не надо будет внутри них хранить у - он же у всех одинаковый. Маленькие массивы легко и быстро сортировать, + используется меньше памяти, потому что после того, как нарисованы все прямые с точками из некоторого массива, его можно удалить из памяти и создать новый — это называется “отрисовка по мере необходимости”.

2 Алгоритм со списком активных рёбер.

Ребра делятся на активные (растеризованные) и неактивные. Принимаем во внимание ребра по мере прорисовки. То есть, те ребра, которые не участвуют в отрисовке текущей линии, отсутствуют в массиве.