, пожалуйста, объясните этот чертежный код линии Bresenham для меня

Question

Я искал в Интернете и нашел сотни вариантов реализации алгоритма рисования линии Брешенема. Но одна вещь, которую я нашел странной, состоит только в двух или трех из них, которые могут охватывать все восемь октетов. Тем не менее, они используются во многих приложениях.

0 Например: this ladythis version (line 415) алгоритм Брешенема. Но он не охватывает все 360 градусов. This guy here, похоже, разрабатывает библиотеку. Но все равно это не работает должным образом.

Можете ли вы сказать мне, почему?

This guy's implementation работает нормально. Но, я полагаю, это не Алгоритм Брешенема. У него очень мало сходства с the theory.

И наконец, я нашел the following version алгоритма рисования линии Брешенема, который работает правильно.

#include "utils.h" 

void Bresenham(int x1, int y1, int const x2, int const y2, int color) 
{ 
    int dx = x2 - x1; 
    // if x1 == x2, then it does not matter what we set here 
    int ix((dx > 0) - (dx < 0)); 

    dx = abs(dx) << 1; 

    int dy = y2 - y1; 
    // if y1 == y2, then it does not matter what we set here 
    int iy((dy > 0) - (dy < 0)); 
    dy = abs(dy) << 1; 

    PlotPixel(x1, y1, color); 

    if (dx >= dy) 
    { 
     // error may go below zero 
     int error(dy - (dx >> 1)); 

     while (x1 != x2) 
     { 
      if ((error >= 0) && (error || (ix > 0))) 
      { 
       error -= dx; 
       y1 += iy; 
      } 
      // else do nothing 

      error += dy; 
      x1 += ix; 

      PlotPixel(x1, y1, color); 
     } 
    } 
    else 
    { 
     // error may go below zero 
     int error(dx - (dy >> 1)); 

     while (y1 != y2) 
     { 
      if ((error >= 0) && (error || (iy > 0))) 
      { 
       error -= dy; 
       x1 += ix; 
      } 
      // else do nothing 

      error += dx; 
      y1 += iy; 

      PlotPixel(x1, y1, color); 
     } 
    } 
} 

int main() 
{ 
    int gm = DETECT; 
    int gd = DETECT; 

    initgraph(&gm, &gd, ""); 

    double x1 = 0; 
    double y1 = 0; 
    double r = 50; 
    double x2 = 0; 
    double y2 = 0; 
    double signx = 0; 
    double signy = 0; 

    for(int theta=0 ; theta<=360 ; theta++) 
    { 
     x2 = r * cos(DegreeToRad((double) theta)); 
     y2 = r * sin(DegreeToRad((double) theta)); 

     x1 = 5 * cos(DegreeToRad((double) theta)); 
     y1 = 5 * sin(DegreeToRad((double) theta)); 

     Bresenham(x1, y1, x2, y2, YELLOW); 

     //delay(10); 
    } 

    getch(); 
    closegraph(); 
    return 0; 
} 

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

• Почему он оставил смещение dx и dy, а затем, прежде чем вычислять, снова переместил их вправо?

• Где dt и ds, о которых говорят the theory?

• Согласно теории, dt и ds должны быть проверены на каждом этапе цикла while. Но этот код не делает этого. Зачем?

• Теория, по-видимому, не имеет указаний на обработку ошибок. Каково использование error, которое вычисляет код? Как он вычисляет error? Как он использует значение error?

• Какова логика теста if(dx >= dy)?

Answer 1

Вот объяснение моей собственной версии Bresenham.

Начнем с параметрического уравнения линии, (X + t.Dx, Y + t.Dy), где t является параметром в диапазоне [0, 1]. Конечными точками являются, очевидно, (X, Y) и (X + Dx, Y + Dy).

Чтобы превратить его в цифровую линию, мы хотим, чтобы ровно один пиксель на строку или на столбец, в зависимости от того, что обеспечивает непрерывную линию. Таким образом, определяя D = Max(|Dx|, |Dy|), мы нарисуем D+1 точек, соответствующих дробным t: (X + I.Dx/D, Y + I.Dy/D), с I в [0, D].

Предположим на мгновение 0 <= Dy < Dx = D, и уравнение упростится до (X + I, Y + I.Dy/Dx). Поскольку последний член не может быть целым числом, мы будем округлять его с round(I.Dy/Dx) = floor(I.Dy/Dx + 1/2) = floor((I.Dy + Dx/2)/Dx).

Последнее выражение является частным числом чисел, следующих за арифметической прогрессией над знаменателем, большим, чем общая разница. Следовательно, когда вы увеличиваете I, соотношение либо остается фиксированным, либо увеличивается на 1. Для бездекорной реализации мы используем трюк: сохраняем коэффициент и остаток деления, давайте Q и R, и каждый раз, когда вы увеличиваете I, обновите их.

N = I.Dy + Dx/2, и Q = N/Dx, R = N % Dx. Затем увеличиваются I, I' = I + 1, N' = N + Dy, Q' = (N + Dy)/Dx, R' = (N + Dy) % Dx.Как вы можете проверить следующее правило выполняется:

if R + Dy >= Dx 
    Q' = Q + 1; R' = R + Dy - Dx 
else 
    Q' = Q; R' = R + Dy 

Положат теперь все элементы вместе, настроить признаки и различать более-горизонтальные и более-вертикальные случаи (как вы заметите, что нет необходимости представлять Q явно):

# Increments 
Sx= Sign(Dx); Sy= Sign(Dy) 

# Segment length 
Dx= |Dx|; Dy= |Dy|; D= Max(Dx, Dy) 

# Initial remainder 
R= D/2 

if Dx > Dy: 
    # Main loop 
    for I= 0..D: 
     Set(X, Y) 

     # Update (X, Y) and R 
     X+= Sx; R+= Dy # Lateral move 
     if R >= Dx 
      Y+= Sy; R-= Dx # Diagonal move 
else: 
    # Main loop 
    for I= 0..D: 
     Set(X, Y) 

     # Update (X, Y) and R 
     Y+= Sy; R+= Dx # Lateral move 
     if R >= Dy 
      X+= Sx; R-= Dy # Diagonal move 

C/C++ Реализация (по @anonymous)

void Set(int x, int y, int color) 
{ 
    PlotPixel(x, y, color); 
} 

int Sign(int dxy) 
{ 
    if(dxy<0) return -1; 
    else if(dxy>0) return 1; 
    else return 0; 
} 
void Bresenham(int x1, int y1, int x2, int y2, int color) 
{ 
    int Dx = x2 - x1; 
    int Dy = y2 - y1; 

    //# Increments 
    int Sx = Sign(Dx); 
    int Sy = Sign(Dy); 

    //# Segment length 
    Dx = abs(Dx); 
    Dy = abs(Dy); 
    int D = max(Dx, Dy); 

    //# Initial remainder 
    double R = D/2; 

    int X = x1; 
    int Y = y1; 
    if(Dx > Dy) 
    { 
     //# Main loop 
     for(int I=0; I<D; I++) 
     { 
      Set(X, Y, color); 
      //# Update (X, Y) and R 
      X+= Sx; R+= Dy; //# Lateral move 
      if (R >= Dx) 
      { 
       Y+= Sy; 
       R-= Dx; //# Diagonal move 
      } 
     } 
    } 
    else 
    { 
     //# Main loop 
     for(int I=0; I<D; I++) 
     {  
      Set(X, Y, color); 
      //# Update (X, Y) and R 
      Y+= Sy; 
      R+= Dx; //# Lateral move 
      if(R >= Dy) 
      {  
       X+= Sx; 
       R-= Dy; //# Diagonal move 
      } 
     } 
    } 
} 

Answer 2

Почему он оставил сдвигая дх и ду, а затем, перед вычислением, снова сдвига вправо их?

Он использует половину int так, чтобы он был точным. Но половина int будет усечена. Таким образом, используя представление, которое по сути удваивается, он может использовать правый сдвиг в качестве необрезанного разделения на два. Это не так, как я давно узнал Брешенема. Но намерение кажется ясным.

Где находятся dt и ds, о которых говорит теория?

Я не читал вашу теорию ссылки тщательно, но так, как я узнал, что Бресенхэм проще, чем это. Первоначальный момент был для очень примитивных процессоров, в которых вы хотите минимизировать вычисления.

Теория, по-видимому, не имеет указаний на обработку ошибок. Какая польза от ошибки, которую вычисляет код? Как он расчет ошибки? Как он использует значение ошибки?

Я ожидаю, что только терминологическая разница вас сбивает с толку. Ключевым моментом алгоритма (в любой форме) является накопитель, представляющий кумулятивную «ошибку» по сравнению с не оцифрованной линией. Эта «ошибка» обычно имеет другое имя, но под любым именем это сердце кода. Вы должны уметь видеть, что он используется на каждом шаге, чтобы определить, в каком направлении этот этап оцифрован.

Какова логика теста, если (dx> = dy)?

Идея состоит в том, что более быстрое изменение направления изменяется на 1 на каждом шаге, а более медленное изменение направления изменяется на 0 или 1 на шаг в зависимости от этой кумулятивной «ошибки». Назад, когда размер кода был основным фактором, реальный трюк с этим алгоритмом заключался в том, чтобы закодировать его, чтобы код был разделен по большей разности X быстрее по сравнению с Y быстрее. Но ясно, что все это просто понять, если вы посмотрите на X, изменяющий более быстрый случай отдельно от Y, меняющегося быстрее.

Answer 3

• Почему он оставил смещение dx и dy, а затем, перед вычислением, снова их правое смещение?

Ниже я объясню.

• Где dt и ds, о которых говорит теория?

Они исчезли, реализация реализует алгоритм рисования линии средней точки. Вы можете вывести один алгоритм из другого. Это упражнение для читателя :-)

• Согласно теории, дт и DS должны были быть проверены в каждом шаге цикла While. Но этот код не делает этого. Зачем?

То же, что и выше. Он тестирует ошибку, что то же самое.

• Теория, по-видимому, не имеет указаний на обработку ошибок. Какая польза от ошибки, которую вычисляет код? Как он расчет ошибки? Как он использует значение ошибки?

Уравнение линии a*x + b*y + c = 0, где a = x2 - x1 и b = -(y2 - y1) может дать указание на ошибку, так как a*x + b*y + c пропорциональна расстоянию от точки (x, y) от линии, с вещественными коэффициентами a, b и c. Мы можем умножить уравнение на произвольную вещественную константу k, не равную 0, и она будет сохраняться для каждой точки линии.

Предположим, что мы рисуем только в первом квадранте. На каждом шаге мы хотим оценить a*x + b*y + c для (x + 1, y + 1/2), чтобы увидеть, как далеко от линии, в которой находится (средняя) точка, и на основании этого решаем, увеличиваем ли мы y или нет, но расстояние не имеет значения, только его знак. Для первого квадранта расстояние будет положительным, если линия выше средней точки (x + 1, y + 1/2) и отрицательная, если ниже. Если линия находится выше середины, мы должны идти вверх.

Знаем для начального (x, y), a*x + b*y + c = 0, но как насчет (x + 1, y + 1/2)? Термин ошибки равен a + b/2. Нам не нравятся половинки, поэтому мы умножаем (сдвиг влево) a и b на 1, и поэтому получаем начальную ошибку 2*a + b, это и является причиной сдвига вправо. Если ошибка положительная, то линия находится выше середины (x + 1, y + 1/2), и мы должны подняться.Если отрицательный, то линия находится ниже середины, и мы оставляем y be. Мы обновляем ошибку постепенно на каждом шаге, в зависимости от того, увеличиваем ли мы y или нет.

С некоторыми соображениями вы можете расширить алгоритм на все квадранты.

• Какова логика теста, если (dx> = dy)?

Мы проверяем крутизну линии. Это делает ненужными свопы.