В материале про Сапёра мы обсудили преимущества рисования горизонтальных линий, но очевидно, что одними горизонтальными линиями все задачи не решить. Ведь часто требуется рисовать линии под любым углом.
Есть готовые библиотечные методы рисования линий. Зачем нам делать это вручную? Во-первых, для упражнения, чтобы понять математическую основу. Во-вторых, нам может потребоваться рисовать линию, где каждый пиксел надо обработать по-своему. В-третьих, линию необязательно рисовать на экране. Она может понадобиться и для других задач в виде просто набора данных, так что библиотечный метод, который рисует на экране, нам не поможет.
Как вообще нарисовать линию
Для порядка уточним, что мы рисуем отрезки, у которых есть начало (x0, y0) и конец (x1, y1).
Рассмотрим тривиальный случай – горизонтальную линию. Например, её длина равна 100 пикселов. Значит, надо начать с координат (x0, y0) и сделать цикл на 100 повторений, и в каждом шаге цикла просто увеличивать координату "x" на 1.
Теперь рассмотрим такую же линию, но под наклоном. В ширину она занимает 100 пикселов, а в высоту 50.
По сути задача не изменилась: мы точно так же делаем цикл на 100 повторений, и прибавляем к координате "x" по 1. Но теперь мы должны прибавлять что-то и к координате "y". Если ширина и высота линии относятся как 100:50, значит, когда мы к "x" прибавляем 1, то к "y" должны прибавлять 0.5. Ну то есть в общем случае:
Если шаг по "x" это 1, то шаг по "y" это 1 * (dy/dx).
Можно посмотреть онлайн, линии генерируются при каждом перезапуске:
Как видим, не всё хорошо: если dx < dy, то по оси "y"появляются разрывы между пикселами. Но это решается выбором, по какой оси двигаться в цикле. Если dx > dy, то двигаемся по "x", а иначе по "y". Это будет сделано ниже, а пока –
Почему это порождало проблемы?
Рассмотрим вариант, когда к "y" прибавляется 0.5. Это дробное число, а пикселы на экране целые. Мы не можем закрасить 0.5 пиксела.
Стоп, но вот же в примере выше нарисованы линии с дробной координатой "y" и всё прекрасно. В чём проблема?
Пикселы здесь рисуются с помощью библиотечного метода рисования прямоугольника (каждый пиксел по факту это маленький квадратик), и когда мы передаём туда дробные координаты, они автоматически округляются. Кроме того, библиотечный метод, когда видит дробную координату, сглаживает края квадрата, заменяя чёрный цвет на градации серого.
Вот так линии будут выглядеть, если мы сами начнём округлять координаты, и сглаживания тогда происходить не будет:
В общем, проблема – в вещественной арифметике, которая во-первых требовала постоянного округления, а во-вторых, на старых процессорах вообще работала медленнее, чем целочисленная (говорят, что сейчас это уже не так).
Как бы то ни было, алгоритм Брезенхема позволяет построить данные для линии, используя только целые числа и только сложение или вычитание, без умножения и деления.
Именно поэтому в прошлом он был абсолютно необходим всем, кто занимался компьютерной графикой. Думаю, что будет интересен и сейчас.
В его основе лежит принцип накопления ошибки. Познакомившись с ним, вы сможете применять его не только для рисования линий, но и для других задач.
Реализация алгоритма Брезенхема
Реализацию на JavaScript вы можете посмотреть онлайн, а здесь будут пояснения. Самое первое – при рисовании линии c шириной dx и высотой dy мы всегда нарисуем не более чем dx или dy пикселов (смотря что из них больше). Например, линия задана координатами (100,100)–(200,150). Значит, по "x" она занимает 100 пикселов, а по "y" 50 пикселов. Значит, мы нарисуем 100 пикселов, расположенных вдоль координаты x.
1. Выяснить наибольшую дистанцию
Так как конец отрезка может находиться и левее-правее, и выше-ниже начала, то dx или dy могут получиться отрицательные. Чтобы узнать, кто больше, надо взять их абсолютные значения. Мы сохраним их в переменных dist_x и dist_y:
dx = x1 - x0;
dy = y1 - y0;
dist_x = Math.abs(dx);
dist_y = Math.abs(dy);
Затем заводим переменную dist, которая хранит максимальную из двух дистанций:
dist = dist_x;
if (dist_y > dist_x) dist = dist_y;
В нашем примере она будет равна 100.
2. Отказ от дробных чисел
После первого пункта мы уже точно знаем, что будем двигаться по координате "x" с приращением 1. Приращение по "y" равно 1 * (dy/dx) = 0.5.
Координаты (x,y) сразу целочисленные, так как иначе нет смысла использовать этот алгоритм. Добавляя 1 к координате "x", мы увеличиваем её ровно на 1, здесь всё работает нормально. Но добавляя 0.5 к "y", мы не увеличиваем её ни на сколько – целое число остаётся целым. То есть приращение по "y" работать не будет.
Как исправить эту проблему, сохранив координаты целочисленными?
В качестве временной меры заведём переменную-накопитель для координаты "y": err_y. Пусть она пока будет вещественного типа. Теперь мы можем добавлять 0.5 не к координате "y", а к накопителю. Как только накопитель станет больше либо равен 1, мы получили целое смещение. Тогда мы уже законно прибавим 1 к "y", и отнимем 1 от накопителя, чтобы он мог снова накапливать.
Теперь надо сделать сам накопитель целочисленным. Сейчас пороговым значением, когда срабатывает накопитель, является 1.
Берём во внимание тот факт, что 0.5 во столько же раз меньше 1, во сколько раз расстояние dy меньше dx. Собственно говоря, иначе и быть не может, так как само приращение по "y" вычисляется из отношения dy/dx.
Следовательно, пороговым значением можно сделать не 1, а dist. И тогда к накопителю err_y прибавляем уже не 0.5, а dist_y. Накопитель будет расти в той же самой пропорции, в какой рос при приращении 0.5 и пороге 1. Как только он превышает порог (dist), мы прибавляем 1 к координате "y" и вычитаем dist из накопителя. Таким образом, мы получили целочисленный накопитель, который работает идентично вещественному.
2. Установить шаги приращения координат.
И координата "x", и координата "y" всегда изменяются с шагом 1. Потому что меньше пиксела нельзя, а больше – будут разрывы . На каждом шаге цикла прирастает либо "x", либо "y", либо обе координаты. Но также как и dx, dy, эти приращения могут быть отрицательными. Определим их правильно и занесём в переменные step_x, step_y:
step_x = 1;
step_y = 1;
if (dx < 0) step_x = -1;
if (dy < 0) step_y = -1;
3. Накопители ошибок
Мы уже сделали накопитель err_y для оси "y", сделаем то же самое для оси "x": err_x, ведь отношение сторон не всегда будет такое, как в нашем примере, и значит, для "x" понадобятся такие же расчёты.
4. Рисование линии
Делаем цикл на dist повторений, так как мы уже знаем, что нужно нарисовать ровно dist пикселов.
Тут мы уже не делаем предположений, что dist_x больше чем dist_y или наоборот. Мы просто в каждом шаге прибавляем к накопителю err_x значение dist_x, а к err_y значение dist_y. Как только один из накопителей превысил порог dist, мы вычитаем из него dist, и прибавляем к соответствующей координате её шаг.
И вот что выходит. Один из накопителей ВСЕГДА будет точно достигать порога dist при каждом шаге. Потому что dist равна либо dist_x, либо dist_y. Допустим, dist_x > dist_y, тогда dist = dist_x, и прибавляя к накопителю err_x значение dist_x, мы мы всегда будем точно достигать dist, и значит, "x" будет прирастать на 1 в каждом шаге цикла. А err_x будет сбрасываться точно в ноль.
А что происходит с err_y? К нему прибавляется dist_y, то есть 50. И на первом шаге err_y будет меньше, чем dist. Значит, мы сдвинемся по "x", но не сдвинемся по "y".
На втором шаге мы опять сдвинемся по "x", и увеличим err_y ещё на 50. Теперь err_y == dist, и значит, можно прибавить шаг к координате "y" и вычесть dist из err_y.
Значит, "x" будет прибавляться каждый шаг, а "y" – через один шаг. Cобственно так и должно быть при пропорциях линии 2:1.
Мы получим такую линию:
Если взять другую линию, где dy = 100 и dx = 50, то теперь dist будет равна dist_y, и уже "y" начнёт прирастать каждый шаг, а "x" через шаг.
А где же накапливается ошибка?
В примере у нас соотношение сторон 2:1. Это значит, что высота укладывается в ширину ровно два раза, и тогда линия рисуется как лестница со ступеньками шириной в 2 пиксела. То же самое можно сказать про отношения 1:1, 3:1, 4:1, 5:1 и т.д. Везде высота укладывается в ширину целое число раз, и поэтому все ступеньки линии будут одинаковой длины.
Но можно взять другие размеры линии, например, dx = 100, dy = 63. Тогда каждая ступенька линии должна быть длиной 1.587 пиксела. Это уже не целое число, и мы возвращаемся к проблеме, когда мы не можем закрасить часть пиксела.
Но посмотрим, как работает алгоритм:
На первом шаге err_y = 63. На втором шаге err_y = 126. Это больше 100, поэтому вычитаем 100 и остаётся 26. Этот остаток и есть ошибка. Это величина, на которую err_y превысило порог. Можно считать его дробной частью пиксела. В следующий раз добавляем 63 и получаем 89, добавляем ещё 63 и получаем 152. Вычитаем 100, остаётся 52 – ошибка выросла. Добавляем 63, получаем 115. Вычитаем 100, остаётся 15 – ошибка снизилась.
Каждый остаток идёт в зачёт для следующего пиксела. То есть дробные части пикселов мы не обнуляем, а накапливаем. Это похоже на механизм високосного года: каждый месяц набегает небольшое количество лишнего времени, и все эти погрешности за 4 года складываются в один лишний день. На практике это выглядит так: линия состоит из ступенек, допустим, по 3 пиксела. Но вдруг где-то появляется ступенька в 2 пиксела. Потом опять 3, а потом опять 2. И линия будем выглядеть примерно так:
Таким образом, нецелые соотношения заставляют длину ступенек время от времени меняться. Разная длина ступенек это и есть следствие накопления ошибки.
Общая мораль такова: если работаете с целыми числами, то не обнуляйте, а накапливайте погрешность.