Алгоритм линии Bresenham - откуда берется параметр принятия решения?

Question

void line() 
{ 
    int x1 = 10, y1 = 10, x2 = 300, y2 = 500 , x, y; 
    int dx, dy, //deltas 
     e;  // decision parameter 

    glClear(GL_COLOR_BUFFER_BIT); 
    glColor3f(1 ,0, 0); 
    setPixel(x1, y1); //plot first point 

    // difference between starting and ending points 
    dx = x2 - x1; 
    dy = y2 - y1; 
    e = 2 * dy - dx; 
    x = x1; y = y1; 

    for(int k = 0; k < dx - 1; ++k) 
    { 
    if(e < 0) 
    { 
     //next pixel: (x+1, y) 
     e = e + 2*dy; 
    } 
    else 
    { 
     //next pixel: (x+1, y+1) 
     e = e + 2*dy - 2*dx; 
     ++y; 
    } 
    ++x; 
    setPixel(x, y); 
    } 

    glFlush(); 
} 

Откуда берутся e = 2*dy - dx? Почему мы увеличиваем его на 2*dy или 2*dy - 2*dx?

Answer 1

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

Алгоритм очень прост. Давайте начнем с уравнением линии

f(x) = y = a*x +b 

(и считать 0 < < = а 1 в настоящее время). Когда мы идем на один пиксель вправо, мы получим:

f(x+1) = a * (x+1) + b = f(x) + a 

Но одновременно и у не будут целыми для типичной линии. Итак, давайте просто представим «ошибку». Мы всегда идем к правильному соседу. При этом мы делаем ошибку a, не поднимаясь вверх. Если наша ошибка превышает половину пикселя (0,5), мы идем вверх (и, следовательно, уменьшить значение ошибки пикселя снова)

float e=a; 
float y=y1; 
int x=x1; 
while(x<=x2) { 
    SetPixel(x,y); 
    x++; 
    if (e > 0.5) { 
     y++; 
     e=e+a-1; 
    } else { 
     e=e+a; 
    } 
} 

(Обратите внимание, что мы уже установили ошибку e к a первоначально и не к нулю , потому что мы всегда принимаем решение после рисования пикселя, и нам не нужно проверять условие перед рисованием самого первого пикселя, потому что он всегда точно находится на линии.)

Теперь мы подошли близко , Но есть две вещи, которые мешают нам использовать целые числа: 0,5 и a, который равен dy/dx. Но: мы можем масштабировать значение ошибки (и условие) на коэффициент арбитража, не меняя ничего. Подумайте об этом: мы измерили ошибку в пикселях до сих пор (потому что это кажется интуитивно понятным вначале), но этот алгоритм может использовать любую произвольную единицу для значения ошибки - половинные пиксели, двойные пиксели, пиксели pi.

Итак, давайте просто нарисуем его на 2*dx, чтобы избавиться от обеих фракций в формуле выше! (В некотором роде, здесь ключевой трюк заключается в том, что «единица», в которой мы измеряем значение ошибки, просто не является константой в алгоритме, а является функцией линии).

int e=2*dy; 
int y=y1; 
int x=x1; 
while(x<=x2) { 
    SetPixel(x,y); 
    x++; 
    if (e > dx) { 
     y++; 
     e=e+2*dy - 2*dx; 
    } else { 
     e=e+2*dy; 
    } 
} 

Теперь у нас есть то, что мы хотим: только целые числа. (Отметим только одну вещь: перейдя от float к int, мы автоматически «привязываем» конечные точки линии к целочисленным координатам - наличие целых конечных точек является некоторым предварительным условием (и ограничения) алгоритма Брешенема).

Существует еще один трюк: условие содержит переменную. Было бы еще более эффективно, если бы мы протестировали против константы и в идеале против нуля (поскольку ветвление, зависящее только от знака или нуля, сохраняет операцию сравнения). И мы можем добиться этого, просто изменив наши значения ошибок. Точно так же, как и раньше, выбирается не только масштаб значения ошибки, но и начало.

Поскольку мы тестируем для e > dx в настоящее время, сдвигая ошибку -dx позволит протестировать 0 (и 0 теперь означает, что dx означает прежде, а именно 0,5 пикселей).Этот сдвиг влияет только на начальное значение e, и условие, все приращения остаются такими же, как и раньше:

int e=2*dy-dx; 
int y=y1; 
int x=x1; 
while(x<=x2) { 
    SetPixel(x,y); 
    x++; 
    if (e > 0) { 
     y++; 
     e=e+2*dy - 2*dx; 
    } else { 
     e=e+2*dy; 
    } 
} 

вуаля, 2*dy-dx термин внезапно появился ...;)