34. Целочисленный алгоритм Брезенхема
Алгоритм Брезенхэ́ма — это алгоритм, определяющий, какие точки двумерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками. Это один из старейших алгоритмов в графике. Алгоритм выбирает оптимальные растровые координаты для представления отрезка. В процессе работы одна из координат - либо x, либо y (в зависимости от углового коэффициента) - изменяется на единицу. Изменение другой координаты (на 0 или 1) зависит от расстояния между действительным положением отрезка и ближайшими координатами сетки. Такое расстояние мы назовем ошибкой.
Алгоритм Брезенхема, работающий с действительными величинами, можно записать в следующем виде:
1. Ввод исходных данных Xн,Yн,Xк,Yк.
2. Проверка вырожденности отрезка. Если отрезок вырожденный, то высвечивается точка и осуществляется переход к п.10.
3. Вычисление приращений dX:=Xк-Xн и dY:=Yк-Yн.
4. Вычисление шага изменения каждой координаты пиксела: SX:=sign(dX), SY:=sign(dY).
5. Вычисление модулей приращения координат: dX:=dX, dY:=dY
6. Обмен значений dX и dY в зависимости от углового коэффициента наклона отрезка:
если dY > dX, то выполнить Temp:=dX, dX:=dY, dY:=Temp, flag:=1; иначе flag:=0 (flag - флаг, определяющий факт обмена местами координат).
7. Инициализация начального значения ошибки:
f:= dY/dX -0,5 (для целочисленного алгоритма: fц=2dY-dX)
8. Инициализация начальных значений координат текущего пиксела: X:=Xн, Y:=Yн
9. Цикл - пока Х Xк делать:
9.1. Высвечивание точки с координатами (X,Y).
9.2. Вычисление координат и корректировка ошибки для следующего пиксела:
Если f0, то если flag:=1, то X:=X+SX иначе Y:=Y+SY; корректировка ошибки f:=f-1 (fц=fц-2dX)
Если f<0, то если flag:=1, то Y:=Y+SY иначе X:=X+SX.
9.3. Вычисление ошибки f:=f+ dY/dX (fц=fц+2dY).
10. Конец.
Алгоритм Брезенхема требует использования арифметики с плавающей точкой и деления (для вычисления углового коэффициента и оценки ошибки). Быстродействие алгоритма можно увеличить, если использовать только целочисленную арифметику и исключить деление. Для этого выражение, например f = m - 0.5, запишем в виде: f = dY/dX-1/2 и, умножив обе части этого равенства на 2dX, получим:
2dXf = 2dY - dX.
Обозначив fц=2dXf, окончательно получим:
fц = 2dY - dX
(В соответствии с этим выражением должно вычисляться теперь начальное значение ошибки в п.7).
Тогда подсчет нового значения ошибки в п.9 "действительного" алгоритма будет производиться по формулам:
fц = fц + 2dY и fц = fц - 2dX.
- «Компьютерная графика»
- 1. Графический процессор. Структура графического процессора g80
- 2. Цифровой сигнальный процессор
- 3. Особенности архитектуры
- 4. Устройство цсп
- 5. Классификация цсп по архитектуре
- 6. Кластеры процессоров цифровой обработки
- 7. Аппаратно-программный комплекс vliw
- 9. Компоненты графической системы Windows
- 10. Компоненты режима ядра
- 11. Архитектура графической системы Windows (gdi)
- 12. Архитектура directx
- 13. Архитектура directdraw
- 14. Архитектура системы печати
- 15. Ве́кторная гра́фика
- 16. Растровое изображение
- 17. Цветовая модель rgb
- 18. Цветовая модель cmyk
- 19. Цветовая модель hsv и hsl
- 20. Цифровая обработка сигналов
- 21. Преобразования Фурье
- 22. Основы opengl
- 23. Графический конвейер OpenGl
- 24. Организация OpenGl. Сопутствующие api
- 25. Архитектура Windows Presentation Foundation
- 26. Организация шейдеров
- 27. Игровой движок
- 28. Графический движок
- 29. Воксел. Доксел
- 30. Спрайт
- 32. Графический ускоритель Intel gma
- 33. Графическое ядро Core i5
- 34. Целочисленный алгоритм Брезенхема
- 35. Алгоритм Брезенхема для генерации окружности
- 36. Буферы кадра
- 37. Точки и линии. Преобразование точек и линий
- 38. Полярная и декартовая система координат
- 39. Трехмерные преобразования
- 40. Трехмерный сдвиг. Трехмерные вращения.
- 41. Закраска Гуро
- 42. Закраска Фонга