35. Алгоритм Брезенхема для генерации окружности
Один из наиболее эффективных и простых для понимания алгоритмов генерации окружности принадлежит Брезенхему. Для начала необходимо сгенерировать только одну восьмую часть окружности. Остальные ее части могут быть получены последовательными отражениями, как это показано на рис. Если сгенерирован первый октант (от 0 до 45° против часовой стрелки), то второй октант можно получить зеркальным отражением относительно прямой у = х, что дает в совокупности первый квадрант. Первый квадрант отражается относительно прямой х = 0 для получения соответствующей части окружности во втором квадранте. Верхняя полуокружность отражается относительно прямой у = 0 для завершения построения. На рис. приведены двумерные матрицы соответствующих преобразований.
Для вывода алгоритма рассмотрим первую четверть окружности с центром в начале координат. Заметим, что если работа алгоритма начинается в точке х = 0, у = R, то при генерации окружности по часовой стрелке в первом квадранте у является монотонно убывающей функцией аргументам (рис. 5.2). Аналогично, если исходной точкой является у = 0, х == R, то при генерации окружности против часовой стрелки х будет монотонно убывающей функцией аргумента у. В нашем случае выбирается генерация по часовой стрелке с началом в точке х = 0, у = R. Предполагается, что центр окружности и начальная точка находятся точно в точках растра. Для любой заданной точки на окружности при генерации по часовой стрелке существует только три возможности выбрать следующий пиксел, наилучшим образом приближающий окружность: горизонтально вправо, по диагонали вниз и вправо, вертикально вниз. На рис. 5.3 эти направления обозначены соответственно mH, mD, mV. Алгоритм выбирает пиксел, для которого минимален квадрат расстояния между одним из этих пикселов и окружностью, т. е. минимум из mH = |(xi + 1)2 + (yi)2 -R2|; mD = |(xi + 1)2 + (yi -1)2 -R2|; mV = |(xi )2 + (yi -1)2 -R2|
Рис. 5.2. Окружность в первом квадранте.
Рис.5.3. Выбор пикселов в первом квадранте.
- «Компьютерная графика»
- 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. Закраска Фонга