Алгоритм линии Брезенхамса - Bresenhams line algorithm

Линейный алгоритм Брезенхема это алгоритм рисования линий который определяет точки п-размерный растр который должен быть выбран, чтобы сформировать близкое приближение к прямая линия между двумя точками. Обычно используется для рисования линейные примитивы в растровое изображение (например, на экран компьютера ), поскольку он использует только целочисленное сложение, вычитание и битовый сдвиг, все это очень дешевые операции в стандартных компьютерные архитектуры. Это алгоритм возрастающей ошибки. Это один из самых ранних алгоритмов, разработанных в области компьютерная графика. Расширение^{[который? ]} к исходному алгоритму может использоваться для рисования круги.

Хотя такие алгоритмы, как Алгоритм Ву также часто используются в современной компьютерной графике, поскольку они могут поддерживать сглаживание, скорость и простота линейного алгоритма Брезенхема означает, что он по-прежнему важен. Алгоритм используется в оборудовании, таком как заговорщики и в графические чипы современных видеокарты. Его также можно найти во многих программного обеспечения графические библиотеки. Поскольку алгоритм очень прост, он часто реализуется либо в прошивка или графическое оборудование современных видеокарты.

Обозначение «Брезенхэм» сегодня используется для семейства алгоритмов, расширяющих или изменяющих исходный алгоритм Брезенхема.

История

Линейный алгоритм Брезенхема назван в честь Джек Элтон Брезенхэм который разработал его в 1962 г. IBM. В 2001 году Брезенхэм писал:^[1]

Я работал в вычислительной лаборатории лаборатории разработки IBM в Сан-Хосе. А Плоттер Calcomp был прикреплен к IBM 1401 через пульт пишущей машинки 1407. [Алгоритм] использовался в производстве летом 1962 года, возможно, на месяц или около того раньше. Программы в то время свободно обменивались между корпорациями, поэтому у Calcomp (Джим Ньюленд и Кэлвин Хефте) были копии. Когда я вернулся в Стэнфорд осенью 1962 года, я положил копию в библиотеку Стэнфордского вычислительного центра. Описание процедуры рисования линий было принято для презентации на конференции 1963 года. ACM национальный съезд в Денвере, Колорадо. Это был год, в котором не публиковались никакие материалы, только повестка дня докладчиков и темы в выпуске сообщений ACM. После того, как я выступил с презентацией, человек из IBM Systems Journal спросил меня, могут ли они опубликовать статью. Я с радостью согласился, и они напечатали его в 1965 году.

Алгоритм Брезенхема был расширен для создания кругов, эллипсов, кубических и квадратичных кривых Безье, а также их собственных сглаженных версий.^[2]

Метод

Иллюстрация результата линейного алгоритма Брезенхема. (0,0) находится в верхнем левом углу сетки, (1,1) находится в верхнем левом конце строки, а (11, 5) находится в правом нижнем конце строки.

Будут использоваться следующие соглашения:

верхний левый угол равен (0,0), так что координаты пикселей увеличиваются в направлениях вправо и вниз (например, пиксель в (7,4) находится непосредственно над пикселем в (7,5)), и
центры пикселей имеют целочисленные координаты.

Конечными точками линии являются пиксели в ${ displaystyle (x_ {0}, y_ {0})}$ и ${ displaystyle (x_ {1}, y_ {1})}$ , где первая координата пары - это столбец, а вторая - строка.

Изначально алгоритм будет представлен только для октант в котором отрезок идет вниз и вправо ( ${ Displaystyle x_ {0} leq x_ {1}}$ и ${ displaystyle y_ {0} leq y_ {1}}$ ), а его горизонтальная проекция ${ displaystyle x_ {1} -x_ {0}}$ длиннее вертикальной проекции ${ displaystyle y_ {1} -y_ {0}}$ (линия имеет положительный склон меньше 1). В этом октанте для каждого столбца Икс между ${ displaystyle x_ {0}}$ и ${ displaystyle x_ {1}}$ , есть ровно одна строка у (вычисляется алгоритмом), содержащий пиксель строки, а каждая строка между ${ displaystyle y_ {0}}$ и ${ displaystyle y_ {1}}$ может содержать несколько растеризованных пикселей.

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

{ displaystyle { frac {y-y_ {0}} {y_ {1} -y_ {0}}} = { frac {x-x_ {0}} {x_ {1} -x_ {0}}} }

.

Поскольку мы знаем столбец, Икс, строка пикселя, у, дается округлением этой величины до ближайшего целого числа:

{ displaystyle y = { frac {y_ {1} -y_ {0}} {x_ {1} -x_ {0}}} (x-x_ {0}) + y_ {0}}

.

Склон ${ displaystyle (y_ {1} -y_ {0}) / (x_ {1} -x_ {0})}$ зависит только от координат конечной точки и может быть вычислен заранее, а идеальный у для последовательных целочисленных значений Икс можно вычислить, начиная с ${ displaystyle y_ {0}}$ и многократно добавляя уклон.

На практике алгоритм не отслеживает координату y, которая увеличивается на м = ∆y / ∆x каждый раз Икс увеличивается на единицу; он сохраняет границу ошибки на каждом этапе, которая представляет собой отрицательное значение расстояния от (а) точки, где линия выходит из пикселя, до (b) верхнего края пикселя. Это значение сначала устанавливается на ${ displaystyle y_ {0} -0,5}$ (из-за использования координат центра пикселя), и увеличивается на м каждый раз Икс координата увеличивается на единицу. Если ошибка становится больше, чем 0.5, мы знаем, что линия переместилась вверх на один пиксель, и что мы должны увеличить наш у координируйте и скорректируйте ошибку, чтобы представить расстояние от вершины нового пикселя - это делается путем вычитания единицы из ошибки. ^[3]

В следующих псевдокод образец, сюжет (x, y) функция отображает пиксель с центром в координатах (х, у) и пресс возвращается абсолютная величина:

функция линия (x0, y0, x1, y1) настоящий deltax: = x1 - x0 настоящий задержка: = y1 - y0 настоящий deltaerr: = abs (задержка / deltax) // Предположим, что deltax! = 0 (линия не вертикальная),          // обратите внимание, что это деление должно быть сделано таким образом, чтобы сохранить дробную часть    настоящий error: = 0.0 // Нет ошибки при запуске int у: = у0 за Икс из x0 к x1 plot (x, y) error: = error + deltaerr если погрешность ≥ 0,5 тогда            y: = y + знак (задержка) ошибка: = ошибка - 1.0

Обратите внимание, что этот псевдокод работает только для конкретного случая, описанного выше, когда линия идет вниз и вправо и где изменение в Икс больше, чем изменение у.

Вывод

Чтобы вывести алгоритм Брезенхема, нужно сделать два шага. Первый шаг - это преобразование уравнения линии из типичной формы пересечения наклона в нечто иное; и затем используя это новое уравнение для линии, чтобы нарисовать линию на основе идеи накопления ошибки.

Уравнение линии

y = f (x) =. 5x + 1 или f (x, y) = x-2y + 2

Положительные и отрицательные полуплоскости

Форма пересечения линии наклона записывается как

{ Displaystyle у = е (х) = mx + b}

где m - наклон, а b - точка пересечения с y. Это функция только от x, и было бы полезно записать это уравнение как функцию от x и y. Используя алгебраические манипуляции и узнав, что уклон - это "подъем через пробег" или ${ displaystyle Delta y / Delta x}$ тогда

{ Displaystyle { begin {align} y & = mx + b y & = { frac {( Delta y)} {( Delta x)}} x + b ( Delta x) y & = ( Delta y) x + ( Delta x) b 0 & = ( Delta y) x - ( Delta x) y + ( Delta x) b end {выровнено}}}

Если это последнее уравнение является функцией x и y, то его можно записать как

{ displaystyle f (x, y) = 0 = Ax + By + C}

где постоянные

${ displaystyle A = Delta y}$
${ displaystyle B = - Delta x}$
${ Displaystyle C = ( Delta x) b}$

Затем линия определяется для некоторых констант A, B и C в любом месте ${ displaystyle f (x, y) = 0}$ . Для любого ${ Displaystyle (х, у)}$ тогда не на кону ${ Displaystyle е (х, у) neq 0}$ . Все в этой форме включает только целые числа, если x и y являются целыми числами, поскольку константы обязательно являются целыми числами.

Например, строка ${ Displaystyle у = { гидроразрыва {1} {2}} х + 1}$ тогда это можно было бы записать как ${ displaystyle f (x, y) = x-2y + 2}$ . Точка (2,2) находится на прямой

{ Displaystyle f (2,2) = x-2y + 2 = (2) -2 (2) + 2 = 2-4 + 2 = 0}

и точка (2,3) не находится на прямой

{ Displaystyle f (2,3) = (2) -2 (3) + 2 = 2-6 + 2 = -2}

и точка (2,1)

{ Displaystyle f (2,1) = (2) -2 (1) + 2 = 2-2 + 2 = 2}

Обратите внимание, что точки (2,1) и (2,3) находятся на противоположных сторонах линии и f (x, y) оценивается как положительное или отрицательное. Линия разделяет плоскость пополам, и полуплоскость с отрицательным f (x, y) может быть названа отрицательной полуплоскостью, а другая половина - положительной полуплоскостью. Это наблюдение очень важно для оставшейся части вывода.

Алгоритм

Ясно, что отправная точка находится на прямой

{ displaystyle f (x_ {0}, y_ {0}) = 0}

только потому, что линия определена так, чтобы начинаться и заканчиваться в целочисленных координатах (хотя вполне разумно рисовать линию с нецелочисленными конечными точками).

Кандидатские точки (2,2) отмечены синим цветом, а две кандидатские точки - зелеными (3,2) и (3,3)

Принимая во внимание, что наклон меньше или равен единице, теперь возникает проблема: должна ли следующая точка находиться в ${ displaystyle (x_ {0} + 1, y_ {0})}$ или же ${ displaystyle (x_ {0} + 1, y_ {0} +1)}$ . Возможно, интуитивно следует выбирать точку, исходя из того, какая точка находится ближе к линии на ${ displaystyle x_ {0} +1}$ . Если он ближе к первому, включите первую точку на линии, если второй, то второй. Чтобы ответить на этот вопрос, оцените функцию линии в середине между этими двумя точками:

{ displaystyle f (x_ {0} + 1, y_ {0} + { tfrac {1} {2}})}

Если значение этого параметра положительное, то идеальная линия находится ниже средней точки и ближе к точке-кандидату. ${ displaystyle (x_ {0} + 1, y_ {0} +1)}$ ; в действительности координата y продвинулась вперед. В противном случае идеальная линия проходит через или выше средней точки, а координата y не продвигается; в этом случае выберите точку ${ displaystyle (x_ {0} + 1, y_ {0})}$ . Это наблюдение очень важно понять! Значение линейной функции в этой средней точке является единственным определяющим фактором, какую точку следует выбрать.

На соседнем изображении показана синяя точка (2,2), выбранная для расположения на линии с двумя точками-кандидатами зеленого цвета (3,2) и (3,3). Черная точка (3, 2.5) - это середина между двумя точками-кандидатами.

Алгоритм целочисленной арифметики

В качестве альтернативы можно использовать разницу между точками вместо оценки f (x, y) в средних точках. Этот альтернативный метод позволяет выполнять арифметические операции только с целыми числами, что обычно быстрее, чем использование арифметики с плавающей запятой. Чтобы получить альтернативный метод, определите разницу следующим образом:

{ displaystyle D = f (x_ {0} + 1, y_ {0} + { tfrac {1} {2}}) - f (x_ {0}, y_ {0})}

Для первого решения эта формулировка эквивалентна методу средней точки, поскольку ${ displaystyle f (x_ {0}, y_ {0}) = 0}$ в начальной точке. Упрощение этого выражения дает:

{ displaystyle { begin {array} {rclcl} D & = & left [A (x_ {0} +1) + B left (y_ {0} + { frac {1} {2}} right) + C right] & - & left [Ax_ {0} + By_ {0} + C right] & = & left [Ax_ {0} + By_ {0} + C + A + { frac { 1} {2}} B right] & - & left [Ax_ {0} + By_ {0} + C right] & = & A + { frac {1} {2}} B end {массив }}}

Как и в случае с методом средней точки, если D положительно, выберите ${ displaystyle (x_ {0} + 1, y_ {0} +1)}$ , в противном случае выберите ${ displaystyle (x_ {0} + 1, y_ {0})}$ .

Если ${ displaystyle (x_ {0} + 1, y_ {0})}$ выбрано, изменение D будет:

{ displaystyle { begin {array} {lclcl} Delta D & = & f (x_ {0} + 2, y_ {0} + { tfrac {1} {2}}) - f (x_ {0} +1 , y_ {0} + { tfrac {1} {2}}) & = & A & = & Delta y end {array}}}

Если ${ displaystyle (x_ {0} + 1, y_ {0} +1)}$ выбрано изменение D будет:

{ displaystyle { begin {array} {lclcl} Delta D & = & f (x_ {0} + 2, y_ {0} + { tfrac {3} {2}}) - f (x_ {0} +1 , y_ {0} + { tfrac {1} {2}}) & = & A + B & = & Delta y- Delta x end {array}}}

Если новый D положительный, то ${ displaystyle (x_ {0} + 2, y_ {0} +1)}$ выбрано, иначе ${ displaystyle (x_ {0} + 2, y_ {0})}$ . Это решение можно обобщить, накапливая ошибку в каждой последующей точке.

Построение линии от (0,1) до (6,4), показывающей график линий сетки и пикселей

Весь вывод для алгоритма сделан. Одна из проблем с производительностью -¹⁄₂ множитель в начальном значении D. Поскольку все это касается знака накопленной разницы, то все можно без последствий умножить на 2.

В результате получается алгоритм, использующий только целочисленную арифметику.

plotLine (x0, y0, x1, y1) dx = x1 - x0 dy = y1 - y0 D = 2 * dy - dx y = y0 за x от x0 до x1 график (x, y) если D> 0 y = y + 1 D = D - 2 * dx конец, если        D = D + 2 * dy

Запуск этого алгоритма для ${ Displaystyle е (х, у) = х-2у + 2}$ от (0,1) до (6,4) дает следующие различия с dx = 6 и dy = 3:

D = 2 * 3-6 = 0 Цикл от 0 до 6 * x = 0: сюжет (0, 1), D≤0: D = 0 + 6 = 6 * x = 1: сюжет (1, 1), D> 0: D = 6-12 = -6, y = 1 + 1 = 2, D = -6 + 6 = 0 * x = 2: сюжет (2, 2), D≤0: D = 0 + 6 = 6 * x = 3: сюжет (3, 2), D> 0: D = 6-12 = -6, y = 2 + 1 = 3, D = -6 + 6 = 0 * x = 4: сюжет (4, 3), D≤0: D = 0 + 6 = 6 * x = 5: сюжет (5, 3), D> 0: D = 6-12 = -6, y = 3 + 1 = 4, D = -6 + 6 = 0 * x = 6: сюжет (6, 4), D≤0: D = 0 + 6 = 6

Результат этого графика показан справа. Построение можно просмотреть, построив график на пересечении линий (синие кружки) или заполнив поля пикселей (желтые квадраты). Тем не менее, сюжет такой же.

Все кейсы

Однако, как упоминалось выше, это только для октант ноль, то есть линии, начинающиеся в начале координат с градиентом от 0 до 1, где x увеличивается ровно на 1 за итерацию, а y увеличивается на 0 или 1.

Алгоритм может быть расширен для охвата градиентов от 0 до -1, проверяя, нужно ли y увеличивать или уменьшать (т.е. dy <0)

plotLineLow (x0, y0, x1, y1) dx = x1 - x0 dy = y1 - y0 yi = 1 если dy <0 yi = -1 dy = -dy конец, если    D = (2 * dy) - dx y = y0 за x от x0 до x1 график (x, y) если D> 0 y = y + yi D = D + (2 * (dy - dx)) конец, если        еще            D = D + 2 * dy

Путем переключения осей x и y реализация для положительных или отрицательных крутых градиентов может быть записана как

plotLineHigh (x0, y0, x1, y1) dx = x1 - x0 dy = y1 - y0 xi = 1 если dx <0 xi = -1 dx = -dx конец, если    D = (2 * dx) - dy x = x0 за y от y0 до y1 график (x, y) если D> 0 x = x + xi D = D + (2 * (dx - dy)) конец, если        еще            D = D + 2 * dx

Полное решение должно было бы определить, x1> x0 или y1> y0, и поменять местами входные координаты перед рисованием, таким образом

plotLine (x0, y0, x1, y1) если абс (у1 - у0) <абс (х1 - х0) если x0> x1 plotLineLow (x1, y1, x0, y0) еще            plotLineLow (x0, y0, x1, y1) конец, если    еще        если y0> y1 plotLineHigh (x1, y1, x0, y0) еще            plotLineHigh (x0, y0, x1, y1) конец, если    конец, если

В низкоуровневых реализациях, которые обращаются к видеопамяти напрямую, было бы типично, чтобы отдельные случаи вертикальных и горизонтальных линий обрабатывались отдельно, поскольку они могут быть сильно оптимизированы.

Некоторые версии используют принципы Брезенхэма целочисленной инкрементной ошибки для выполнения всех рисований линий октанта, балансируя положительную и отрицательную ошибку между координатами x и y.^[2] Обратите внимание, что порядок не обязательно гарантирован; другими словами, линия может быть проведена от (x0, y0) до (x1, y1) или от (x1, y1) до (x0, y0).

plotLine (int x0, int y0, int x1, int y1) dx = abs (x1-x0); sx = x0 пока (true) / * цикл * / plot (x0, y0); если (x0 == x1 && y0 == y1) перерыв; e2 = 2 * ошибка; если (e2> = dy) / * e_xy + e_x> 0 * / err + = dy; х0 + = sx; конец, если        если (e2 <= dx) / * e_xy + e_y <0 * / err + = dx; y0 + = sy; конец, если    конец пока

Подобные алгоритмы

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

Принцип использования инкрементная ошибка вместо операций деления есть другие приложения в графике. Этот метод можно использовать для расчета Координаты U, V во время растрового сканирования полигонов с наложенной текстурой.^[4] В воксель Механизмы программного рендеринга карт высот, используемые в некоторых играх для ПК, также использовали этот принцип.

Брезенхэм также опубликовал вычислительный алгоритм Run-Slice (в отличие от Run-Length).^{[нечеткий ]}

Расширение алгоритма обработки толстых линий было создано Аланом Мерфи из IBM.^[5]

Смотрите также

Цифровой дифференциальный анализатор (графический алгоритм), простой и общий метод растеризации линий и треугольников
Линейный алгоритм Сяолинь Ву, такой же быстрый метод рисования линий с сглаживание
Алгоритм среднего круга, аналогичный алгоритм рисования кругов

Примечания

^ Пол Э. Блэк. Словарь алгоритмов и структур данных, NIST. https://xlinux.nist.gov/dads/HTML/bresenham.html
^ ^а ^б Зингл, Алоис "Алгоритм растеризации для построения кривых" (2012) http://members.chello.at/~easyfilter/Bresenham.pdf
^ Джой, Кеннет. «Алгоритм Брезенхема» (PDF). Группа исследований визуализации и графики, Департамент компьютерных наук, Калифорнийский университет, Дэвис. Получено 20 декабря 2016.
^ [1] "Аппарат и метод для выполнения перспективно правильной интерполяции в компьютерной графике", выпущенный 31 мая 1995 г.
^ "Модифицированный алгоритм линии Брезенхема Мерфи". homepages.enterprise.net. Получено 2018-06-09.

дальнейшее чтение

Тезис Патрика-Жиля Майо расширение алгоритма рисования линий Брезенхема для удаления скрытых трехмерных линий; также опубликовано в трудах MICAD '87 по CAD / CAM и компьютерной графике, стр. 591 - ISBN 2-86601-084-1.
Утолщение линии путем модификации алгоритма Брезенхема, В КАЧЕСТВЕ. Мерфи, Бюллетень технического раскрытия информации IBM, Vol. 20, No. 12, май 1978 г.

внешняя ссылка

[DADS-1] Пол Э. Блэк. Словарь алгоритмов и структур данных, NIST. https://xlinux.nist.gov/dads/HTML/bresenham.html

[Zingl-2] а ^б Зингл, Алоис "Алгоритм растеризации для построения кривых" (2012) http://members.chello.at/~easyfilter/Bresenham.pdf

[3] Джой, Кеннет. «Алгоритм Брезенхема» (PDF). Группа исследований визуализации и графики, Департамент компьютерных наук, Калифорнийский университет, Дэвис. Получено 20 декабря 2016.

[4] [1] "Аппарат и метод для выполнения перспективно правильной интерполяции в компьютерной графике", выпущенный 31 мая 1995 г.

[5] "Модифицированный алгоритм линии Брезенхема Мерфи". homepages.enterprise.net. Получено 2018-06-09.

[1]

[2]

[3]

[4]

[5]