Упрощенный алгоритм линии Bresenham: что он делает * точно *?

Основываясь на статье Википедии о линейном алгоритме Брешенема, я описал там упрощенную версию, моя реализация 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-statements, как они выглядят, и почему err изменяется так, как показано в коде.

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

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

Ответ 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 iff (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; предназначена для минимизации ошибки смещения; если вы взорвали масштаб графика, вы увидите, что вычисленная линия не может быть сосредоточена на нужной строке с различными инициализациями.

Ответ 2

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

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