Популярный метод.

Алгоритмы вычерчивания линий.

Растровые алгоритмы.

Лекция 16.11.2008

Существует теория особенностей (катастроф), доказывающая, что при проецировании на плоскость произвольного гладкого объекта(плоскости) возможны 3 типа проекций:

- обыкновенная

- складка

- сборка

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

Возникла из геологии - оттуда и название.

Большинство графических устройств - растровые, представляют изображение в виде прямоугольной матрицы пикселей (растра), поэтому большинство содержит набор растровых алгоритмов. Любая графическая библиотека, в том числе и в СИ++ содержит модули для реализации основных граф объектов:

- линейные изображения (отрезки прямых, дуги окружностей и эллипсов)

- сплошные объекты (растровые области 2-мерных областей - круги)

- шрифты

- изображение, прямоугольные матрицы пикселей, независимо от содержания объектов (графические примитивы)

Функции вычерчивания линий - основные подпрограммы. Используются для отображения линий заданного цвета путём задания координат.

Для растровой графики граф построения линий в общем виде - проблема. Важное понятия для растр сетки - связность, те соединение 2=х пикселей растровой линией. Линии состоит из соседних пикселей оного цвет. Понятия связности

a1(x1,y1) и a2(...)

А) 4х связность, когда пиксели соседние, если х или у отличаются на 1.

У каждой точки только 4 соседа.

|x1-x2| + |y1-y1|<=1

Б) 8-связность: пиксели соседние, если х и у отличаются на более чем на 1.

|x1-x2½£ 1; ½y1-y2½£ 1.

8 соседей

Понятие 4-с более строгое, чем 8-с, т.е. - это частный случай.

В качестве линий на растровой сетке - набор пикселей п1 - пн, где пи и пи+1 - соседние в смысле 4-х или 8-ми связности.

Один из подходов в вычерчивании линий - соотношение между смещением по координате х и у.

Для простоты считаем

0<=y2-y1<=x2-x1 : углы меньше 45

Описание:

Например, надо провести линию a1(0.0) - a2(10,5)

Dx=10

Dy=5

K = 10\5 -коэффициент зависимости, при котором надо изменять х и у при изображении линии, для этого требуется обработка чисел с плавающей точкой, что снижает быстродействие - редкое использование.

Алгоритм Брезенхейма для растрового построения отрезка.

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

Алгоритм применим для любой формы линии. Суть - итерационный процесс поиска соседних точек начиная с а0(х1. у1):

А) в каждой итерации цикла вычерчивании линии вычисляются 2 погрешности по осям которые увеличиваются с увеличением координат.

Б) Если значения достигнет определённой величины то оно обнуляется а соответствующая координата увеличивается на 1.

В) этот процесс идет до полного построения

При построении отрезка прямой всегда выбирается ближайший по вертикали пиксель - из 2-х точек выбирается та то ближе (а)

D=(x2-x1)(d-a)

Если д>0 то значение увеличивается на 1 а d=+2(dy-dx)

В противном случае у не изменится, а d = 2dy

Алгоритм в в конспекте.

Для дуг окружностей и эллипсов приращение и погрешности вычисляются по более сложному выражению.