Растровая графика

Примитивы
Точки
Линии
Прямоугольники (со сторонами, параллельными границам экрана)
Многоугольники
Шрифты
Заливка областей
Плоское отсечение

Line

Line: Digital Differential Analyzer (DDA)
(x,y)
x2-x1
y2-y1
slope

Line: Алгоритм Брезенхема (метод центральной точки)
точка (x,y) «ниже» прямой
точка (x,y) «лежит» на прямой
точка (x,y) «выше» прямой

Line: Алгоритм Брезенхема (метод центральной точки)
P(x,y)
M(x+1,y+1/2)
f(x,y)
Подставляем точку M в функцию f:
если f(M) > 0 выбираем точку NЕ
если f(M) <= 0 выбираем точку Е
E
NE

Line: Алгоритм Брезенхема (метод центральной точки)
P(x,y)
ME(x+2,y+1/2)
f(x,y)
Подставляем точку M в функцию f:
если f(M) > 0 выбираем точку NЕ
если f(M) <= 0 выбираем точку Е
Изменения значения f(M) при переходе
к новым точкам (E или NE):
E
NE
MNE(x+2,y+3/2)
M

Line: Алгоритм Брезенхема (метод центральной точки)
P1(x1,y1)
M0(x+1,y+1/2)
f(x,y)
Известны приращения f.
Найдем первоначальное значение для точки (x1,y1)

Line: Алгоритм Брезенхема (метод центральной точки)
Сохранились вещественные числа.
Сделаем замену: 2f = e
Тогда помеченные строки изменяться на:
e = 2 * dy - dx;
e > 0
e = e + 2 * dy - 2 *dx;
e = e + 2 * dy
и e – целое число.

Line: Алгоритм Брезенхема (метод центральной точки)

Line: Алгоритм с использованием Fixed Point (DDA)
Fixed Point – вещественные числа с фиксированной точкой.
Рассмотрим 4-байтное целое:
2b целая часть
2b дробная часть
Точность 1/65536
Если x и y fixed point, то
сложение не изменяется (x+y)
вычитание не изменяется (x-y)
целая часть – «двоичный сдвиг» вправо на 16 бит (x >> 16)
из целого: x = a << 16

Circle
R

Circle: Алгоритм Брезенхема (метод центральной точки)
Подставляем точку M в функцию f:
если f(M) >= 0 выбираем точку SЕ
если f(M) < 0 выбираем точку Е

Circle: Алгоритм Брезенхема (метод центральной точки)
P(x,y)
M
E
SE
MSE
ME
f(x,y)
Изменения значения f(M) при переходе
к новым точкам (E или SE):

Circle: Алгоритм Брезенхема (метод центральной точки)
Определили приращения f.
Найдем первоначальное значение для точки (x1,y1)
Все приращения - целые. Сравнение f с 0 строгое: ‘<‘.
Поэтому из первоначального f можно вычесть 1/4..

Circle: Алгоритм Брезенхема (метод центральной точки)
Дополнительная оптимизация:
Просчитаем изменение приращений по направлениям E и SE (incrE=2*x+3 и incrSE=2*(x-y)+5) для избавления от доступа к переменным.
Если выбрана точка E, то ‘x’ увеличивается на 1 и:
incrE=incrE+2 и incrSE=incrSE+2
Если выбрана точка SE, то ‘x’ увеличивается на 1, ‘y’ уменьшается на 1 и:
incrE=incrE+2 и incrSE=incrSE+4
Изначальные значения:
incrE=3 и incrSE=5-2*R

Circle: Алгоритм Брезенхема (метод центральной точки)

Polygon

Flood Fill

Flood Fill

Text
Шрифты
Растровые Векторные Контурные

Text
0x3C
0x46
0x86
0x86
0x86
0xFE
0x86
0x00
Справа показана битовая кодировка каждой строки
(в шестнадцатеричном виде)