Обобщение алгоритма Брезенхема.

Лекции 5. Алгоритмы растрово-векторной графики.

Растр и вектор.

Основа растрового дисплея – растр – упорядоченная сетка пикселей. Каждое изображение непрерывно: фотография, рисунок и т.д., представляет собой множество точек, линий, сплошных областей. Т.к. растр – матрица дискретных элементов (пикселей), то любое непрерывное изображение нельзя абсолютно точно изобразить на растровом экране => необходима аппроксимация (приблизительное описание).

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

Основными рассматриваемыми векторными примитивами являются:

Точка

Отрезок (прямая)

Дуга (эллипс, окружность)

Закраска замкнутой области (растровая развертка треугольника)

Текст (шрифты растровые и TT )

Алгоритмы вывода точки . Адрес в Буфере Кадра:
А=( Y * H + X )*РазмерЦвета [A]=C заносим цвет точки.

Алгоритмы развертки отрезков.

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

Алгоритмы симметричны по X <-> Y от угла наклона прямой <45°

Алгоритм проведения отрезка “ в лоб”.

- уравнение прямой

; [1] - tg угла наклона

x: x1...x2 с шагом 1

y: рассчитывается y=Round( [1] )

При увеличении угла наклона появляются разрывы (Dx=1, Dy>1), т.е. при m<1 (угол < 45) используем [1], при m>1 (угол > 45), обратаная зависимость:

[2]

y: y1...y2 с шагом 1

x: рассчитывается x=Round( [ 2 ] )

Недостатки: операции умножения, деления и дробная арифметика.

Данный алгоритм практически не используется.

Алгоритм Цифрового Дифференциального Анализатора.

(const) ;

Dx и Dy для отрезка постоянны.

, где

Xni = Round(Xi) Yni = Round(Yi)

Недостатки: работа с дробными числами. Данный алгоритм используется как основа для следующих алгоритмов растровой развертки.

Целочисленный алгоритм Брезенхема.

Вещественные переменные не используются совсем и, следовательно, округление не требуется.

Оговорки:

m = (0..1); x2 > x1; (x1,y1) = (0,0); (x1,y1) ¹ (x2,y2)

Dx = 1 – всегда, Dy = {

{ Алгоритм Брезенхема } Begin {для углов меньше 45} dX:=X2-X1; dY:=Y2-Y1; S:=dX div 2; Y:=Y1; For X:=X1 to X2 do begin PutPixel(X,Y,Color); S:=S-dY; IF S<0 then begin Y:=Y+1; S:=S+dX; end; end; End.