Алгоритму 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; } } }

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

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

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

Для меня это хорошее напоминание тем, кто пишет код сегодня. Мы привыкли решать задачи слоями абстракций и библиотеками на любой чих. А иногда самое сильное решение умещается в десяток строк и обходится одним сложением. Стоит время от времени спускаться на этот уровень и смотреть, как всё устроено на самом деле.