Лекция 2. Растровая графика

1.

1
Raster
Растровая
графика
URL:
http://www.school30.spb.ru/cgsg/cgc/
E-mail: [email protected]
Галинский В.А.
Физико-математический лицей № 30
Computer Graphics Support Group

2. Примитивы

2
Примитивы
Raster
• Точки
• Линии
• Прямоугольники (со сторонами,
параллельными границам экрана)
• Многоугольники
• Шрифты
• Заливка областей
• Плоское отсечение
Галинский В.А.
Физико-математический лицей № 30
Computer Graphics Support Group

3. Line

3
Line
Raster
y
(x2,y2)
(x1,y1)
x
Галинский В.А.
Физико-математический лицей № 30
Computer Graphics Support Group

4. Line: Digital Differential Analyzer (DDA)

4
Line: Digital Differential Analyzer (DDA)
Raster
y2-y1
slope
(x,y)
x2-x1
Галинский В.А.
Физико-математический лицей № 30
Computer Graphics Support Group

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

5
Raster
y y1
x x1
x 2 x1 y 2 y1
( x x1) ( y 2 y1) ( y y1) ( x 2 x1) 0
y
(x2,y2)
(x,y)
(x1,y1)
dy x dx y ( x1 dy y1 dx) 0
f ( x, y ) dy x dx y ( x1 dy y1 dx)
f ( x, y ) 0
f ( x, y ) 0
x
f ( x, y ) 0
точка (x,y) «ниже» прямой
точка (x,y) «лежит» на прямой
точка (x,y) «выше» прямой
Галинский В.А.
Физико-математический лицей № 30
Computer Graphics Support Group

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

NE
f(x,y)
Подставляем точку M в функцию f:
• если f(M) > 0 выбираем точку NЕ
• если f(M) <= 0 выбираем точку Е
M(x+1,y+1/2)
P(x,y)
E
Галинский В.А.
Физико-математический лицей № 30
Computer Graphics Support Group
6
Raster

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

f(x,y)
NE
P(x,y)
E
Raster
Подставляем точку M в функцию f:
• если f(M) > 0 выбираем точку NЕ
• если f(M) <= 0 выбираем точку Е
MNE(x+2,y+3/2)
ME(x+2,y+1/2)
M
7
Изменения значения f(M) при переходе
к новым точкам (E или NE):
f ( M ) f ( x 1, y 1 ) dy ( x 1) dx ( y 1 ) C
2
2
dy x dy dx y dx C
2
f ( M E ) f ( x 2, y 1 ) dy ( x 2) dx ( y 1 ) C
2
2
dy x 2 dy dx y dx C f ( M ) dy
2
f ( M NE ) f ( x 2, y 3 ) dy ( x 2) dx ( y 3 ) C
2
2
dy x 2 dy dx y 3 dx C f ( M ) dy dx
2
Галинский В.А.
Физико-математический лицей № 30
Computer Graphics Support Group

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

Известны приращения f.
f(x,y)
Найдем первоначальное значение для
точки (x1,y1)
M0(x+1,y+1/2)
P1(x1,y1)
f ( M 0 ) f ( x1 1, y1 1 )
2
dy ( x1 1) dx ( y1 1 ) ( x1 dy y1 dx)
2
dy dx
2
Галинский В.А.
Физико-математический лицей № 30
Computer Graphics Support Group
8
Raster

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

Сохранились вещественные
числа.
Сделаем замену: 2f = e
Тогда помеченные строки
изменяться на:
e = 2 * dy - dx;
e > 0
e = e + 2 * dy - 2 *dx;
e = e + 2 * dy
и e – целое число.
Галинский В.А.
Физико-математический лицей № 30
Computer Graphics Support Group
9
Raster

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

Галинский В.А.
Физико-математический лицей № 30
Computer Graphics Support Group
10
Raster

11. 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
Галинский В.А.
Физико-математический лицей № 30
Computer Graphics Support Group
11
Raster

12. Circle

12
Circle
Raster
y
R
x
Галинский В.А.
Физико-математический лицей № 30
Computer Graphics Support Group

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

y
(0,R)
f ( x, y) x 2 y 2 R 2
x<=y
x
f ( x, y ) 0
f ( x, y ) 0
f ( x, y ) 0
P(x,y)
точка (x,y) вне круга
точка (x,y) на окружности
точка (x,y) внутри круга
E
M(x+1,y-1/2)
f(x,y)
SE
Подставляем точку M в функцию f:
• если f(M) >= 0 выбираем точку SЕ
• если f(M) < 0 выбираем точку Е
Галинский В.А.
Физико-математический лицей № 30
Computer Graphics Support Group
13
Raster

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

14
Raster
P(x,y)
E
M
SE
ME
Изменения значения f(M) при переходе
к новым точкам (E или SE):
f(x,y)
MSE
f ( M ) f ( x 1, y 1 ) ( x 1) 2 ( y 1 ) 2 R 2
2
2
x2 2x 1 y2 y 1 R2
4
f ( M E ) f ( x 2, y 1 ) ( x 2) 2 ( y 1 ) 2 R 2
2
2
x2 4 x 4 y 2 y 1 R2 f (M ) 2 x 3
4
f ( M NE ) f ( x 2, y 3 ) ( x 2) 2 ( y 3 ) 2 R 2
2
2
x2 4 x 4 y 2 3 y 9 R2 f (M ) 2 x 2 y 5
4
Галинский В.А.
Физико-математический лицей № 30
Computer Graphics Support Group

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

P(0,R)
E
M0(1,R-1/2)
Определили приращения f.
Найдем первоначальное значение для
точки (x1,y1)
f ( M 0 ) f (1, R 1 ) 12 ( R 1 )2 R 2
2
2
1 R2 R 1 R2 5 R
4
4
f(x,y)
SE
Все приращения - целые. Сравнение f с
0 строгое: ‘<‘.
Поэтому из первоначального f можно
вычесть 1/4..
Галинский В.А.
Физико-математический лицей № 30
Computer Graphics Support Group
15
Raster

16. 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
Галинский В.А.
Физико-математический лицей № 30
Computer Graphics Support Group
16
Raster

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

Галинский В.А.
Физико-математический лицей № 30
Computer Graphics Support Group
17
Raster

18. Polygon

18
Polygon
Raster
Галинский В.А.
Физико-математический лицей № 30
Computer Graphics Support Group

19. Flood Fill

19
Flood Fill
Raster
Галинский В.А.
Физико-математический лицей № 30
Computer Graphics Support Group

20. Flood Fill

20
Flood Fill
Raster
Галинский В.А.
Физико-математический лицей № 30
Computer Graphics Support Group

21. Text

21
Text
Raster
Шрифты
Растровые
Векторные
Контурные
Галинский В.А.
Физико-математический лицей № 30
Computer Graphics Support Group

22. Text

22
Text
Raster
0x3C
0x46
0x86
0x86
0x86
0xFE
0x86
0x00
Справа показана битовая кодировка
каждой строки
(в шестнадцатеричном виде)
Галинский В.А.
Физико-математический лицей № 30
Computer Graphics Support Group

23.

23
Raster
• Упражнение
– Рекомендуется реализовать растровые алгоритмы
с помощью программы из первого упражнения.
Растровые шрифты необходимо загружать из
файла.
Галинский В.А.
Физико-математический лицей № 30
Computer Graphics Support Group