Упрощенный алгоритм Брезенхема: что он делает?

Question

Основываясь на статье Википедии о строковом алгоритме Брезенхема, я реализовал упрощенную версию , описанную там, моя реализация Java выглядит следующим образом:

int dx = Math.abs(x2 - x1);
int dy = Math.abs(y2 - y1);

int sx = (x1 < x2) ? 1 : -1;
int sy = (y1 < y2) ? 1 : -1;

int err = dx - dy;

while (true) {
    framebuffer.setPixel(x1, y1, Vec3.one);

    if (x1 == x2 && y1 == y2) {
        break;
    }

    int e2 = 2 * err;

    if (e2 > -dy) {
        err = err - dy;
        x1 = x1 + sx;
    }

    if (e2 < dx) {
        err = err + dx;
        y1 = y1 + sy;
    }
}

Теперь я понимаю, что err контролирует соотношение между шагами по оси X по сравнению с шагами по оси Y - но теперь, когда я должен задокументировать, что делает код, я не могу четко выразить, для чего он нужен и почему точно операторы if, как они есть и почему err изменяется так, как видно из кода.

Википедия не указывает на более подробные объяснения или источники, поэтому мне интересно:

Что именно делает err и почему dx и dy используются именно так, как показано, для поддержания правильного соотношения между горизонтальными и вертикальными шагами, используя эту упрощенную версию алгоритма линии Брезенхэма?

Answer 1

Существуют различные формы уравнений для линии, одним из наиболее знакомых из которых является y=m*x+b. Теперь, если m=dy/dx и c = dx*b, то dx*y = dy*x + c. Запись f(x) = dy*x - dx*y + c означает, что f(x,y) = 0 если (x,y) - точка на данной линии.

Если вы продвинетесь на x одну единицу, f(x,y) изменится на dy; если вы продвигаетесь на y одну единицу, f(x,y) изменяется на dx. В вашем коде err представляет текущее значение линейного функционала f(x,y) и последовательности операторов

    err = err - dy;
    x1 = x1 + sx;

и

    err = err + dx;
    y1 = y1 + sy;

представляет собой продвижение x или y на одну единицу (в направлении sx или sy) с последующим воздействием на значение функции. Как отмечалось ранее, f(x,y) - ноль для точек на линии; это положительно для точек на одной стороне линии, и отрицательно для тех, с другой. Тесты if определяют, будет ли продвижение x оставаться ближе к желаемой линии, чем продвижение y, или наоборот, или оба.

Инициализация err = dx - dy; предназначена для минимизации ошибки смещения; если вы взорвете свой масштабный график, вы увидите, что ваша вычисленная линия может не центрироваться на нужной линии с различными инициализациями.

Answer 2

Просто хочу добавить один бит информации "почему" в отличный ответ jwpat.

Смысл использования формулы f(x) = dy*x - dx*y + c заключается в ускорении расчетов. Эта формулировка использует целочисленную арифметику (быстрее), тогда как традиционная формулировка y = mx + b использует арифметику с плавающей запятой (медленнее).