Алгоритму Брезенхэма 60 лет, а он всё ещё рисует линии

В 1962 году инженер IBM Джек Брезенхэм решал простую с виду задачу: провести прямую между двумя точками, имея под рукой только целочисленную арифметику и сложение. Деление и числа с плавающей точкой тогда стоили дорого. Он придумал способ обойтись без них полностью.

Идея простая. Мы идём вдоль линии по одной оси и храним накопленную ошибку, то есть насколько мы отклонились от идеальной прямой. Как только ошибка превышает половину пикселя, делаем шаг по второй оси и корректируем накопитель. Внутри цикла нет ни одного деления, только сложение и сравнение с нулём.

Вот как это выглядит в коде:

// Bresenham's line algorithm (1962)
// draws a line using only integer arithmetic

void line(int x0, int y0, int x1, int y1) {
    int dx = x1-x0, dy = y1-y0, err = dx/2, y = y0;
    for (int x = x0; x <= x1; x++) {
        plot(x, y);
        err -= dy;
        if (err < 0) { y++; err += dx; }
    }
}

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

Самое интересное в том, где этот код работает прямо сейчас. Растровые движки видеокарт рисуют им рёбра треугольников. Терминалы и графические библиотеки тянут на нём линии и рамки. Игровые движки используют ту же логику для трассировки по сетке. На встраиваемых дисплеях со слабым процессором ему просто нет альтернатив.

Вытеснить его так и не смогли, потому что вытеснять нечем. Алгоритму не нужна дополнительная память, таблицы предвычислений или сложные инструкции. Он даёт нужный результат за минимальное число действий. Когда решение доведено до такой простоты, его уже не улучшишь, его можно только заново открыть.