Линейный алгоритм Брезенхема

Линейный алгоритм Брезенхэма — это алгоритм рисования линий , который определяет точки n -мерного растра , которые следует выбрать, чтобы сформировать близкое приближение к прямой линии между двумя точками . Он обычно используется для рисования примитивов линий в растровом изображении (например, на экране компьютера ), поскольку использует только сложение, вычитание и битовый сдвиг целых чисел , которые являются очень дешевыми операциями в исторически распространенных компьютерных архитектурах. Это алгоритм увеличения ошибок и один из первых алгоритмов, разработанных в области компьютерной графики . расширение исходного алгоритма, называемое алгоритмом окружности средней точки можно использовать Для рисования кругов .

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

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

История

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

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

Метод

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

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

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

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

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

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

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

.

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

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

.

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

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

Вывод

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

Линейное уравнение

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

y=f(x)=mx+b

где $m$ это наклон и $b$ это y-перехват. Поскольку это функция только $x$ , он не может представлять собой вертикальную линию. Поэтому было бы полезно записать это уравнение как функцию обоих $x$ и $y$ , чтобы иметь возможность рисовать линии под любым углом. Угол (или наклон) линии можно обозначить как «подъем над пробегом» или $\Delta y/\Delta x$ . Затем, используя алгебраические манипуляции,

{\begin{aligned}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{aligned}}

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

f(x,y):=Ax+By+C=0

где константы

$A=\Delta y=y_{1}-y_{0}$
$B=-\Delta x=-(x_{1}-x_{0})$
$C=(\Delta x)b=(x_{1}-x_{0})b$

Затем линия определяется для некоторых констант $A$ , $B$ , и $C$ где угодно $f(x,y)=0$ . То есть для любого $(x,y)$ не на линии, $f(x,y)\neq 0$ . Эта форма включает в себя только целые числа, если $x$ и $y$ являются целыми числами, поскольку константы $A$ , $B$ , и $C$ определяются как целые числа.

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

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

и точка (2,3) не лежит на прямой

f(2,3)=(2)-2(3)+2=2-6+2=-2

и дело не в этом (2,1)

f(2,1)=(2)-2(1)+2=2-2+2=2

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

Алгоритм

Очевидно, что отправная точка находится на линии

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

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

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

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

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

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

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

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

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

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

{\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=\Delta y-{\frac {1}{2}}\Delta x\end{array}}

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

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

{\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}}

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

{\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 положителен, то $(x_{0}+2,y_{0}+1)$ выбирается, в противном случае $(x_{0}+2,y_{0})$ . Это решение можно обобщить, накапливая ошибку в каждой последующей точке.

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

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

plotLine(x0, y0, x1, y1)
    dx = x1 - x0
    dy = y1 - y0
    D = 2*dy - dx
    y = y0

    for x from x0 to x1
        plot(x, y)
        if D > 0
            y = y + 1
            D = D - 2*dx
        end if
        D = D + 2*dy

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

D=2*3-6=0
Loop from 0 to 6
 * x=0: plot(0, 1), D≤0: D=0+6=6
 * x=1: plot(1, 1), D>0: D=6-12=-6, y=1+1=2, D=-6+6=0
 * x=2: plot(2, 2), D≤0: D=0+6=6
 * x=3: plot(3, 2), D>0: D=6-12=-6, y=2+1=3, D=-6+6=0
 * x=4: plot(4, 3), D≤0: D=0+6=6
 * x=5: plot(5, 3), D>0: D=6-12=-6, y=3+1=4, D=-6+6=0
 * x=6: plot(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
    if dy < 0
        yi = -1
        dy = -dy
    end if
    D = (2 * dy) - dx
    y = y0

    for x from x0 to x1
        plot(x, y)
        if D > 0
            y = y + yi
            D = D + (2 * (dy - dx))
        else
            D = D + 2*dy
        end if

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

plotLineHigh(x0, y0, x1, y1)
    dx = x1 - x0
    dy = y1 - y0
    xi = 1
    if dx < 0
        xi = -1
        dx = -dx
    end if
    D = (2 * dx) - dy
    x = x0

    for y from y0 to y1
        plot(x, y)
        if D > 0
            x = x + xi
            D = D + (2 * (dx - dy))
        else
            D = D + 2*dx
        end if

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

plotLine(x0, y0, x1, y1)
    if abs(y1 - y0) < abs(x1 - x0)
        if x0 > x1
            plotLineLow(x1, y1, x0, y0)
        else
            plotLineLow(x0, y0, x1, y1)
        end if
    else
        if y0 > y1
            plotLineHigh(x1, y1, x0, y0)
        else
            plotLineHigh(x0, y0, x1, y1)
        end if
    end if

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

В некоторых версиях используются принципы целочисленной возрастающей ошибки Брезенхема для рисования всех октантных линий, балансируя положительную и отрицательную ошибку между координатами x и y. ^{[ 3 ]}

plotLine(x0, y0, x1, y1)
    dx = abs(x1 - x0)
    sx = x0 < x1 ? 1 : -1
    dy = -abs(y1 - y0)
    sy = y0 < y1 ? 1 : -1
    error = dx + dy
    
    while true
        plot(x0, y0)
        if x0 == x1 && y0 == y1 break
        e2 = 2 * error
        if e2 >= dy
            error = error + dy
            x0 = x0 + sx
        end if
        if e2 <= dx
            error = error + dx
            y0 = y0 + sy
        end if
    end while

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

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

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

Брезенхэм также опубликовал вычислительный алгоритм Run-Slice: в то время как описанный выше алгоритм Run-Length запускает цикл по главной оси, вариант Run-Slice работает в другом направлении. ^{[ 5 ]} Этот метод представлен в ряде патентов США:

5,815,163		Способ и устройство для рисования срезов линий во время расчета.
5,740,345		Способ и устройство для отображения данных компьютерной графики, хранящихся в сжатом формате, с эффективной системой индексации цвета.
5,657,435		Запустите механизм рисования линий среза с возможностями нелинейного масштабирования.
5,627,957		Запустите механизм рисования линий среза с расширенными возможностями обработки.
5,627,956		Запустите механизм рисования линий среза с возможностями растяжения.
5,617,524		Запустите механизм рисования линий среза с возможностями затенения.
5,611,029		Запустите механизм рисования линий среза с возможностями нелинейного затенения.
5,604,852		Способ и устройство для отображения параметрической кривой на видеодисплее
5,600,769		Запустите механизм рисования линий среза с улучшенными методами обрезки.

Алгоритм был расширен до:

Рисуйте линии произвольной толщины — алгоритм, созданный Аланом Мерфи из IBM. ^{[ 6 ]}
Рисуйте кривые нескольких типов (круги, эллипсы, кубические, квадратичные и рациональные кривые Безье), а также сглаженные линии и кривые; набор алгоритмов Алоиса Зингля. ^{[ 3 ]}

См. также

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

Примечания

^ Пол Э. Блэк. Словарь алгоритмов и структур данных, NIST . https://xlinux.nist.gov/dads/HTML/bresenham.html
^ Радость, Кеннет. «Алгоритм Брезенхэма» (PDF) . Группа исследований визуализации и графики, факультет компьютерных наук, Калифорнийский университет, Дэвис . Проверено 20 декабря 2016 г.
^ Jump up to: ^а ^б Зингль, Алоис (2012). Алгоритм растеризации для рисования кривых (PDF) (Отчет).
HTML-аннотация и демонстрация: Зингль, Алоис (2016). «Бресенхем» . Members.chello.at .
^ США 5739818 , Спэкман, Джон Нил, «Устройство и метод для выполнения перспективно правильной интерполяции в компьютерной графике», опубликовано 14 апреля 1998 г., передано Canon KK.
^ «Черная книга Майкла Абраша по графическому программированию, специальное издание: хорошее, плохое и нарезанное» . www.phatcode.net . Проверено 13 февраля 2024 г. ;
^ «Модифицированный алгоритм линии Брезенхэма Мерфи» . homepages.enterprise.net . Проверено 9 июня 2018 г. («Утолщение линий путем модификации алгоритма Брезенхема» в Бюллетене технической информации IBM, том 20, № 12, май 1978 г., страницы 5358–5366.)

Ссылки

Брезенхэм, Дж. Э. (1965). «Алгоритм компьютерного управления цифровым плоттером» (PDF) . IBM Systems Journal . 4 (1): 25–30. дои : 10.1147/sj.41.0025 . Архивировано из оригинала (PDF) 28 мая 2008 г.
«Алгоритм рисования линий Брезенхема» , Колин Флэнаган
Абраш, Майкл (1997). Черная книга Майкла Абраша по графическому программированию . Олбани, Нью-Йорк: Кориолис. стр. 654–678 . ISBN 978-1-57610-174-2 . Очень оптимизированная версия алгоритма на языке C и ассемблер для использования в видеоиграх с полной информацией о его внутренней работе.
Зингль, Алоис (2012). «Алгоритм растеризации для рисования кривых» (PDF) . , Красота алгоритмов Брезенхема

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

Диссертация Патрика-Жиллесбанды , содержащая расширение алгоритма рисования линий Брезенхема для удаления скрытых 3D-линий.
- также опубликовано в сборнике статей MICAD '87 по CAD/CAM и компьютерной графике, стр. 591 - ISBN 2-86601-084-1 .
Утолщение линий путем модификации алгоритма Брезенхема , А.С. Мерфи, Бюллетень технической информации IBM, Vol. 20, № 12, май 1978 г.
Брезенхэм, Джек (февраль 1977 г.). «Линейный алгоритм инкрементного цифрового отображения дуг окружности». Коммуникации АКМ . 20 (2): 100–106. дои : 10.1145/359423.359432 . – также Технический отчет, 27 января 1964 г., 11 января, Алгоритм круга TR-02-286, лаборатория IBM в Сан-Хосе.

Внешние ссылки

Черная книга графического программирования Майкла Абраша, специальное издание: Глава 35: Брезенхэм быстр, а быстрота хороша
Алгоритм рисования линий Брезенхэма Колина Флэнагана
Страница Национального института стандартов и технологий об алгоритме Брезенхема
Информация о инкрементном плоттере Calcomp 563
Алгоритм Брезенхэма на нескольких языках программирования
Красота алгоритма Брезенхема - простая реализация для построения линий, кругов, эллипсов и кривых Безье.

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

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

[Zingl-3] Jump up to: ^а ^б Зингль, Алоис (2012). Алгоритм растеризации для рисования кривых (PDF) (Отчет).
HTML-аннотация и демонстрация: Зингль, Алоис (2016). «Бресенхем» . Members.chello.at .

[4] США 5739818 , Спэкман, Джон Нил, «Устройство и метод для выполнения перспективно правильной интерполяции в компьютерной графике», опубликовано 14 апреля 1998 г., передано Canon KK.

[5] «Черная книга Майкла Абраша по графическому программированию, специальное издание: хорошее, плохое и нарезанное» . www.phatcode.net . Проверено 13 февраля 2024 г. ;

[6] «Модифицированный алгоритм линии Брезенхэма Мерфи» . homepages.enterprise.net . Проверено 9 июня 2018 г. («Утолщение линий путем модификации алгоритма Брезенхема» в Бюллетене технической информации IBM, том 20, № 12, май 1978 г., страницы 5358–5366.)

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]