Алгоритм Брезенхема

Алгоритм Брезенхема — это итеративный алгоритм, используемый для растровой аппроксимации отрезков прямых линий и кривых второго порядка (в первую очередь, окружностей) на дискретной сетке пикселей. Алгоритм был разработан американским инженером Джеком Элтоном Брезенхемом (Jack Elton Bresenham) в 1962 году в компании IBM. Основное преимущество алгоритма заключается в том, что он оперирует только целочисленной арифметикой (сложение, вычитание и битовые сдвиги), что делает его чрезвычайно быстрым и эффективным для реализации на аппаратном уровне и в программном обеспечении, где производительность вычислений с плавающей запятой была ограничена. Алгоритм определяет, какие пиксели на двумерной сетке должны быть закрашены, чтобы сформировать визуально гладкое приближение прямой линии или окружности, минимизируя отклонение от идеальной математической кривой.

История

Джек Брезенхем, работая в научно-исследовательском центре IBM в Йорктаун-Хайтс, штат Нью-Йорк, столкнулся с задачей управления цифровым плоттером. Плоттеры того времени могли перемещать перо только в одном из восьми направлений (по четырём сторонам света и четырём диагоналям). Для того чтобы нарисовать линию произвольного угла, необходимо было решить, в какой момент следует сделать шаг по горизонтали, а в какой — по диагонали, чтобы линия была как можно более прямой.

В 1962 году Брезенхем опубликовал статью «Algorithm for computer control of a digital plotter» (Алгоритм для компьютерного управления цифровым плоттером) в журнале IBM Systems Journal. В этой работе он впервые описал метод, основанный на вычислении ошибки (отклонения) между идеальной линией и текущим положением пера. Вместо использования дорогостоящих в то время операций умножения и деления, он предложил итеративно обновлять значение ошибки, используя только целочисленные сложения и вычитания. Этот подход впоследствии был адаптирован для растровых дисплеев (мониторов с электронно-лучевой трубкой) и стал стандартом в компьютерной графике. Алгоритм остаётся актуальным и сегодня, лежа в основе работы многих графических библиотек (например, в ранних версиях OpenGL) и аппаратных ускорителей.

Принцип работы

Алгоритм Брезенхема для отрезков решает задачу аппроксимации прямой линии между двумя точками с целочисленными координатами. Основная идея заключается в том, чтобы на каждом шаге (при движении вдоль оси X с шагом 1) решать, нужно ли делать шаг по оси Y (то есть закрашивать пиксель, смещённый по вертикали) или оставаться на той же строке пикселей.

Выбор пикселя

Для линии, идущей с углом наклона от 0 до 45 градусов (первый октант), алгоритм работает следующим образом. Пусть начальная точка — (x0, y0), конечная — (x1, y1). Уравнение прямой: y = m*x + b, где m = (y1 - y0) / (x1 - x0). На каждом шаге x увеличивается на 1. Алгоритм вычисляет так называемую переменную ошибки (decision parameter), которая показывает, насколько текущее положение пикселя по Y отклоняется от идеального значения y.

• Если ошибка меньше 0, то идеальная точка ближе к нижнему пикселю (y не меняется).
• Если ошибка больше или равна 0, то идеальная точка ближе к верхнему пикселю (y увеличивается на 1), и ошибка корректируется.

Ключевое нововведение Брезенхема — итеративное обновление ошибки без явного вычисления наклона m. Вместо этого используется целочисленная переменная, которая инициализируется как 2dy - dx (где dy = y1 - y0, dx = x1 - x0). Затем на каждом шаге к ней прибавляется 2dy (если y не меняется) или 2dy - 2dx (если y меняется). Это позволяет избежать операций с плавающей точкой.

Базовый алгоритм для отрезка (первый октант)

1. Инициализация: x = x0, y = y0, dx = x1 - x0, dy = y1 - y0, ошибка = 2*dy - dx.
2. Цикл: Для каждого x от x0 до x1:

• Закрасить пиксель (x, y).
• Если ошибка >= 0: y = y + 1, ошибка = ошибка - 2*dx.
• Ошибка = ошибка + 2*dy.
• x = x + 1.

Обобщение для всех октантов

Для того чтобы алгоритм работал для линий с любым углом наклона (включая вертикальные, горизонтальные и линии с отрицательным наклоном), необходимо выполнить преобразование координат. Обычно это делается путём определения «ведущей оси» (оси, вдоль которой изменение координаты больше). Если |dx| > |dy|, то ведущей является ось X, и алгоритм работает как описано выше. Если |dy| > |dx|, то ведущей становится ось Y, и алгоритм модифицируется: шаг делается по Y, а решение о шаге по X принимается на основе ошибки. Знаки приращений (dx, dy) также учитываются для определения направления движения (вправо/влево, вверх/вниз).

Алгоритм для окружности

Алгоритм Брезенхема также может быть применён для рисования окружностей. В этом случае он использует симметрию окружности: достаточно вычислить точки для одной восьмой (45-градусного сектора), а затем отразить их относительно осей и диагоналей. Алгоритм для окружности также оперирует целочисленной ошибкой, которая определяет, смещаться ли по оси Y при движении по оси X (или наоборот), чтобы минимизировать отклонение от идеальной дуги радиуса R.

Принцип для окружности

Для окружности с центром в (0,0) и радиусом R, уравнение имеет вид x² + y² = R². Алгоритм начинает с точки (0, R) и движется по часовой стрелке в первом октанте (x увеличивается, y уменьшается). На каждом шаге решается, какой из двух возможных пикселей (следующий по горизонтали или по диагонали) лучше аппроксимирует окружность. Критерием выбора служит знак целочисленной функции ошибки, которая вычисляется на основе разности квадратов расстояний до идеальной окружности.

Преимущества и недостатки

Преимущества

• Высокая скорость: Использование только целочисленных операций (сложение, вычитание, битовые сдвиги) делает алгоритм чрезвычайно быстрым. Это критически важно для встроенных систем, старых графических карт и приложений реального времени.
• Простота реализации: Алгоритм легко реализуется на любом языке программирования, включая ассемблер и аппаратные логические схемы (FPGA, ASIC).
• Низкое потребление ресурсов: Не требует вычислений с плавающей запятой, что экономит такты процессора и энергию.
• Точность: Обеспечивает визуально гладкие линии и окружности без пропусков пикселей.

Недостатки

• Алиасинг (ступенчатость): Как и любой растровый алгоритм, Брезенхем создаёт «лестничный» эффект на линиях, идущих под углами, близкими к 45 градусам. Для сглаживания (антиалиасинга) требуются более сложные алгоритмы, такие как алгоритм Ву (Wu's algorithm), которые используют полупрозрачные пиксели.
• Ограниченная точность для кривых: Алгоритм для окружности хорошо работает только для окружностей. Для эллипсов и других кривых второго порядка требуются отдельные модификации.
• Только для монохромных изображений: В базовой версии алгоритм определяет, закрашивать пиксель или нет. Для цветных изображений с градиентами или текстурами он не подходит без доработок.

Применение

Алгоритм Брезенхема является фундаментальным для компьютерной графики и находит применение в самых разных областях:

• Растеризация графики: Используется в графических библиотеках (Direct2D, GDI+, Cairo, Skia) и драйверах видеокарт для отрисовки линий и контуров.
• Компьютерные игры: В ранних 2D-играх (например, Doom, Wolfenstein 3D) использовался для отрисовки стен и объектов. В современных 3D-играх применяется на этапе растеризации треугольников.
• Встраиваемые системы: В дисплеях приборных панелей, калькуляторов, плоттеров, 3D-принтеров и станков с ЧПУ (где необходимо перемещать инструмент по прямой линии).
• Геоинформационные системы (ГИС): Для отрисовки линий дорог, границ и других векторных объектов на растровой карте.
• Обработка изображений: Используется в некоторых алгоритмах для построения гистограмм, линий уровня и преобразования Хафа.

Интересные факты

• Алгоритм Брезенхема часто путают с алгоритмом Цифрового дифференциального анализатора (ЦДА, DDA). DDA также используется для рисования линий, но в нём используются операции с плавающей запятой, что делает его медленнее, но проще для понимания.
• Существует модификация алгоритма Брезенхема для рисования линий с переменной толщиной, хотя она значительно сложнее базовой версии.
• Несмотря на свой возраст (более 60 лет), алгоритм продолжает изучаться в курсах компьютерной графики как классический пример оптимизации и элегантного решения задачи.

Источники

1. Bresenham, J. E. (1965). Algorithm for computer control of a digital plotter. IBM Systems Journal, 4(1), 25-30.
2. Foley, J. D., van Dam, A., Feiner, S. K., & Hughes, J. F. (1996). Computer Graphics: Principles and Practice (2nd ed.). Addison-Wesley.
3. Rogers, D. F. (1998). Procedural Elements for Computer Graphics (2nd ed.). WCB/McGraw-Hill.
4. Шикин, Е. В., & Боресков, А. В. (2000). Компьютерная графика. Динамика, реалистические изображения. Диалог-МИФИ.