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

Нарисовать линию. Кажется, что это очень простая задача.

Но как бы вы нарисовали линии, например, из точки А(-6, -6) в точку В (7, 3), если квадраты можно или полностью закрасить, или оставить незакрашенными?

Может так?

А может так?

Или как то иначе? Это довольно важный вопрос, т.к. все экраны современных устройств представляют собой сетку пикселей, которые могут гореть только одним цветом. Этот пиксель нельзя разделить на меньшие значения. И хотя у устройств размеры таких пикселей могут быть очень маленькими, кто то должен "научить" экран рисовать прямые.

Итак, в этой статье мы попробуем написать универсальный алгоритм рисования линии между 2-мя точками.

Общее уравнение прямой

Чтобы разобраться с прямой основательно нужно вспомнить школьные формулы уравнения прямой.

Общее уравнение прямой имеет вид Ax+By+C=0, где x и y - переменные, а А, В, С - константы. Общее уравнение означает, что любая прямая может быть задана с помощью этого уравнения.

Уравнение прямой может быть неполным. В полном уравнение все константы (А, В и С) отличны от нуля. В неполном они могут быть равны нулю (при и А и В, равном нулю, уравнение не имеет смысла, так как мы получаем уравнение константа = 0).

Уравнение вида Аx+By = 0 соответствует уравнению прямой, проходящей через точку (0, 0), или начало координат.

Если значение А = 0, то уравнение описывает прямую, параллельную оси OX. Если В = 0, то уравнение описывает прямую, параллельную оси OY.

Для примера, как могут выглядеть некоторые прямые.

Уравнение прямой с угловым коэффициентом

Наиболее известным уравнением прямой является уравнение вида y=kx+b.

Если мы заменим (-A/B) на k, а (-C/B) на b, то получим уравнение с угловым коэффициентом.

Сразу стоит отметить, что с помощью данного уравнения нельзя выразить прямую, параллельную оси y. Как можно заметить выше, при уравнении прямой, параллельной оси y, коэффициент В равен нулю, а делить на ноль нельзя.

Конкретный пример

Все дальнейшие мы будем рассматривать на следующем примере: провести прямую, из точка А(3,2) в точку В (7,4).

Немного упростим наш пример. Мы будем рассматривать только такие отрезки, у которых Δx >= Δy, т.е. разница точек по оси x (в данном примере 7 - 3 = 4) больше или равна разнице по оси y (в данном случае 4 - 2 = 2). При таком условии мы будем получать прямые с углом между прямой и осью x от 0 до 45 градусов. В дальнейшем мы увидим, что поменяв оси x и y мы может получить линии в которых это условие не выполняется.

Для начала, поставим точки вцентре данных квадратов, и соединим их линией.

Здесь есть важный момент. Линии на изображении выше - это идеал, который мы не можем получить по той причине, что у нас есть только квадраты конечных размеров. А это значит, что мы можем только приблизительно найти такую прямую, построенную с помощью закрашивания квадратов (или по сложному, мы можем только аппроксимровать прямую).

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

Мы будем использовать уравнение с коэффициентом наклона, т.е. уравнение прямой y=kx+b (в целом выбор не так важен, но для построения прямой этот вид наиболее удобен).

Коэффициент k в данном случае определяем угол наклона прямой по отношению к оси x. Для наглядности вот примеры

Чем больше параметр k, тем больше угол между прямой и осью x. Чем меньше k - тем меньше угол. При k=1 угол ровно 45 градусов. Возьмем для примера прямую y=(1/3)x. Это означает, что каждый раз, когда x увеличивается на 1, y увеличивается только на (1/3)х. Когда x пройдет 3 значения по своей оси, y по своей оси пройдем только 1. Если мы нарисуем треугольник из этих координат, то увидим, что прямая с осью х образует угол. В таком случае (1/3) - это отношение y к x, или по другому - это тангенс образованного угла. Таким образом - коэффициент k характеризует тангенс угла наклона между прямой и осью x.

Коэффициент b говорит о смещении линии по оси y.

Потратив время на разбор всех коэффициентов, мы можем найти уравнение прямой по 2-м точкам. Коэффициент k = Δy/Δx=(y2-y1)/(x2-x1)=(4-2)/(7-3)=2/4=1/2. Чему равен параметр b? выведем из уравнения y=kx+b чему равен b: b = y - kx. Вместо x, y мы можем подставит координаты любой точки, т.е. b = 2 - 1/2 * 3 = 1/2.

В итоге мы получаем формулу прямой с угловым коэффициентом: y=(1/2)* x +(1/2). Дальше все очень просто. Проходим все точки по оси x от первой точки до второй (от 3 до 7, хотя на самом деле от 4 до 6 т.к. если мы проводим прямую по 2-м точкам, логично что первая и последняя точки, т.е. квадраты, будут закрашены).

Мы получим следующие значения

x = 3, y = 2 (1/2 * 3 + 1/2)

x = 4, y = 2.5 (1/2 * 4 + 1/2)

x = 5, y = 3 (1/2 * 5 + 1/2)

x = 6, y = 3.5 (1/2 * 6 + 1/2)

x = 7, y = 4 (1/2 * 7 + 1/2)

Проставим эти точки на графике.

В целом на этом все. Мы нашли для каждого x значение y и теперь нам нужно закрасить все точки y, вычисленные для каждой точки x, подставляя в уравнение прямой. Если у нас получилось значение, например 3.5 (или 3.2, 3.7 - т.е. между 2-х точек), то у нас есть 2 варианта: закрасить оба квадрата, и 3 и 4 (вариант слева), или округлить по правилам округления (до 4 в данном примере справа). Второй вариант выглядит лучше.

DDA алгоритм

Такой подход вполне работает, но есть одно но. Для вычисления каждой точки мы во-первых работаем с числами с плавающей точкой, а во-вторых выполняем умножение для нахождения каждой точки значения y. Говоря проще, такой подход работает медленно и если нам нужно рисовать тысячи прямых по 30-60 раз в секунду (например в играх), хотелось бы чтобы этот алгоритм занимал как можно меньше времени.

Сперва заметим, что прямая получается лучше всего когда 1 координате x соответствует 1 координата y. В противном случае мы в некоторых местах получим утолщение, которое выглядит некрасиво (там где 1 координате x соответствует 2 координаты y). Дальше, заметим, что мы знаем смещение по оси y следующей точки - в нашем случае оно равно (1/2). Зачем нам каждый раз подставлять следующий x в формулу y=kx+b, если мы заранее знаем, что следующее значение y будет увеличено на k = Δy/Δx. Начинаем со значений (x, y) первой точки, затем в цикле прибавляем 1 к x, а к y прибавляем значение k и округляем до целого числа, мы получим такую же прямую, как на изображении выше.

Мы не избавляемся от чисел с плавающей точкой, но избавились от умножения для нахождения каждой координаты y. Это заметно сократит вычисления.

Такой способ называется DDA алгоритм (Digital Differential Analyzer, или цифровой дифференциальный анализатор).

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

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

Посмотрим на небольшой фрагмент

На нем есть 6 пикселей с красными точками, обозначающими их центры, прямая линия, которую нужно изобразить и 1 закрашенный пиксель. Если прямая идет из левого нижнего угла в правый верхний, то каждая следующая точка может быть или справа от данной, или справа выше по диагонали. Т.е. когда мы переходим от координаты x к (x+1), то следующий пиксель будет или с той-же координатой по y, или на 1 больше (эти варианты обозначены стрелками). Все что нужно сделать - определить, в какую из двух точек идти.

И сейчас мы будем выяснять, какую из этих точек выбрать.

Введем некоторые обозначения: по оси x пронумеруем значения X(i-1), X(i), X(i+1). По оси y добавим Y(i-1) (в данном случае индекс Y(i-1) обозначает, что эта координата по оси y, которая соответствует координате X(i-1). Возможно более правильный вариант обозначения Y(X(i-1))). Как мы выяснили, квадрат с координатами (X(i-1), Y(i-1)) - закрашен. Нам нужно ответить на вопрос, при x=X(i), какую координату по оси y выбрать: Y(i-1) или Y(i-1) + 1, т.е. с точкой А или В. Ответ на этот вопрос - к какой точке по оси y прямая ближе, или что тоже самое - какой из отрезков от точки А до прямой(зеленый) или от точки В до прямой(синий) меньше.

Чтобы лучше понять эту идею, посмотрите на следующие изображение. Если a < b, нужно выбрать координату Y(i-1)+1, иначе - координату Y(i-1). При равенстве отрезков можно выбрать любую из двух точек.

В итоге получаем следующее выражение.

Это же выражение можно записать как. Запомним эти неравенства, они нам пригодятся.

А дальше начинается самое интересное, и самое сложное. Вычислим расстояние от А до прямой(расстояние между Y(i-1)+1 и прямой) и от В до прямой (расстояние от прямой до Y(i-1)).

Теперь мы можем подставить эти выражение вместо a и b в формулу b - a

Если посмотреть на эту формулу, можно заметить, что значение b - 1 будет не целым числом, т.к. у нас есть дробь Δy / Δx (коэффициент k). Давайте умножим все полученное значение на Δx, тогда знаменатель исчезнет и мы получим целое число.

Почему мы можем так сделать, ведь это изменит результат. Да, результат будет другой - но нам он и не так важен. Нам нужен только знак этого выражения. Представим d(i) = (b - a)Δx. Здесь мы именно находим d для x=i.

А теперь попробуем найти d для x=i+1. Это очень просто - мы заменяем все i на (i+1).

Вычислим Δ = d(i+1) - d(i), так мы узнаем как из d(i) получить d(i+1). Теперь сложим все вместе: по знаку d мы можем вычислить, надо ли изменять координату по оси y. Найдя d(i+1) - d(i), мы найдем способ получить d(i+1) зная d(i).

Преобразовывая это выражение, мы заметили, что X(i+1) - X(i) = 1 (мы двигаемся по оси x последовательно). Теперь найдем следующую координату по оси y как сумму d(i) и только что вычисленной дельты.

Напомню картинку, которая у нас была изначально.

Мы знаем, что для x=X(i-1), y=(i-1). Этот квадрат уже закрашен. Теперь мы переходим к координате X(i), т.е. к следующей точке. Для координаты X(i-1) мы вычислили d(i-1), и тут может быть 2 варианта

1) d(i-1) > 0. Нам важен только знак. Что это означает? Что выражение b - a > 0, а значит следующая координата по оси y будет на 1 больше. По другому, Y(i) - Y(i-1) = 1, значит формула для d(i+1) будет следующей

2) d(i-1) <= 0. Это означает, что b - a <= 0, а значит на следующем x менять координату y не нужно. Значит Y(i-1) = Y(i) и Y(i) - Y(i-1) = 0. Тогда формула примет вид

Теперь нам нужно найти d для первой точки. Посмотрим как выглядит начало отрезка, начинающегося из точки А. Когда отрезок проходит через следующую координату x, то образуется треугольник ABC. Этот треугольник подобен треугольнику, который получится от точки А до конца прямой. В таких треугольниках АС/(x2-x1) = BC/(y2-y1) (по правилу подобия труугольников).

Теперь заметим, что точка В на рисунке лежит ровно посередине между 2-мя вертикальными точками, т.е. ВС = 1/2 AC. Если BC будет больше 1/2 AC (вариант внизу слева), то d должно быть больше 0 и выбираем следующую координату по оси y. Если меньше (внизу справа), то d меньше 0 и оставляем координату y.

Таким образом, начальная формула для d = 2 * dy - dx. Вычислим заранее 2 * Δy и 2 * (Δy - Δx).

Собрав все это вместе, мы получим следующий всевдокод (setPixel закрашивает пиксель с координатой x, y).

В этой статье я не хотел рассматривать все варианты и все случаи прямой, обработку различных положений и т.д. Я хотел показать показать красоту алгоритма и саму идею, которая лежит в его основе. Сам алгоритм можно легко найти, но мало где объясняется что это за такие константы d, d1, d2 и почему они такие.

При реализации алгоритма прямой мы перешли от умножения и работе с числами с плавающей точкой к одной операции целочисленного сложения для каждой координаты x. Быстрее уже некуда.

Также хочу упомянуть про алгоритмы со сглаживанием. Т.е. мы закрашиваем пиксели не только в черно-белый цвет, но и в оттенки серого (или других) цветов. Визуально такие линии становятся очень гладкими. Например, вот алгоритм By (анимация позаимствована отсюда)

Большинство игр позволяют выбрать алгоритм сглаживания в настройках. Возможно вам знакомы такие выражения, как SSAA, MSAA, FXAA. Также в большинстве библиотек для построения простых геометрических фигур есть флаг, который называется anti-aliasing. Он отвечает за сглаживания. Например, в Java есть класс Paint, который представляет абстракцию кисти и у него флаг можно установить так Paint.setFlags(Paint.ANTI_ALIAS_FLAG).