Запутался в алгоритме DDA, нужна помощь

Question

Мне нужна помощь в отношении алгоритма DDA, меня смущает учебник, который я нашел в Интернете на DDA Algo, вот ссылка на этот учебник

http://i.thiyagaraaj.com/tutorials/computer-graphics/basic-drawing-techniques/1-dda-line-algorithm

Пример:

xa,ya=>(2,2)
xb,yb=>(8,10)
dx=6
dy=8

xincrement=6/8=0.75
yincrement=8/8=1

1)     for(k=0;k<8;k++)
xincrement=0.75+0.75=1.50
yincrement=1+1=2
1=>(2,2)

2)     for(k=1;k<8;k++)
xincrement=1.50+0.75=2.25
yincrement=2+1=3
2=>(3,3)

Теперь я хочу спросить, как появилась эта строка xincrement=0,75+0,75=1,50, когда теоретически написано, что

"Если наклон больше 1, роли x any y в единичных y-интервалах Dy=1 и вычисляют каждое последующее значение y. Dy=1

m= Dy / Dx
m= 1/ (  x2-x1 )
m = 1 / ( xk+1 – xk  )

xk+1   =  xk   +  ( 1 / m )

"

так должно быть xincrement=x1 (which is 2) + 0.75 = 2.75

или я неправильно понимаю, кто-нибудь может научить меня, как это делается?

Большое спасибо)

Answer 1

Здесь, кажется, немного путаницы.

Для начала предположим, что 0 <= slope <= 1. В этом случае вы продвигаете один пиксель за раз в направлении X. На каждом шаге X у вас есть текущее значение Y. Затем вы выясняете, является ли "идеальное" значение Y ближе к вашему текущему значению Y или к следующему большему значению Y. Если оно ближе к большему значению Y, вы увеличиваете текущее значение Y. Несколько иначе, вы выясняете, превышает ли ошибка при использовании текущего значения Y больше половины пикселя, и если это так, вы увеличиваете свое значение Y.

Если наклон> 1, то (как упоминалось в вашем вопросе) вы меняете роли X и Y. То есть, вы продвигаете один пиксель за раз в направлении Y, и на каждом шаге определяете, следует ли увеличивать текущее значение X,

Отрицательные уклоны работают примерно так же, за исключением того, что вы уменьшаете, а не увеличиваете.

Answer 2

Расположение пикселей - это целочисленные значения. Идеальные линейные уравнения представлены в действительных числах. Таким образом, алгоритмы рисования линий преобразуют действительные числа уравнения в целочисленные значения. Трудный и медленный способ нарисовать линию - это оценить уравнение линии для каждого значения x в вашем массиве пикселей. Цифровые дифференциальные анализаторы оптимизируют этот процесс несколькими способами.

Во-первых, DDA используют тот факт, что известен хотя бы один пиксель - начало строки. Исходя из этого пикселя, DDA рассчитывают следующий пиксель в строке, пока они не достигнут конечной точки линии.

Во-вторых, DDA используют тот факт, что вдоль оси x или y следующий пиксель в строке всегда является следующим целочисленным значением по направлению к концу строки. DDA выясняет, какая ось, оценивая наклон. Положительные наклоны между 0 и 1 будут увеличивать значение x на 1. Положительные наклоны больше единицы увеличивают значение y на 1. Отрицательные наклоны между -1 и 0 увеличивают значение x на -1, а отрицательные наклоны меньше -1 увеличит значение y на -1.

В-третьих, DDA используют тот факт, что если изменение в одном направлении равно 1, изменение в другом направлении является функцией наклона. Теперь это становится намного сложнее объяснить в общих чертах. Поэтому я просто рассмотрю положительные наклоны между 0 и 1. В этом случае, чтобы найти следующий пиксель для построения графика, x увеличивается на 1, и вычисляется изменение y. Один из способов рассчитать изменение у - просто добавить наклон к предыдущему у и округлить до целочисленного значения. Это не работает, если вы не поддерживаете значение y как действительное число. Наклоны, превышающие единицу, можно просто увеличить y на 1 и рассчитать изменение x.

В-четвертых, некоторые DDA дополнительно оптимизируют алгоритм, избегая вычислений с плавающей запятой. Например, линейный алгоритм Брезенхэма - это DDA, оптимизированный для использования целочисленной арифметики.

В этом примере это линия от (2, 2) до (8, 10), наклон составляет 8/6, что больше 1. Первый пиксель находится в (2, 2). Следующий пиксель рассчитывается путем увеличения значения y на 1 и добавления изменения x (обратный наклон dx/dy = 6/8 = 0,75) к x. Значение х будет 2,75, которое округляется до 3, и (3, 3) наносится на график. Третий пиксель снова увеличит y, а затем добавит изменение x к x (2.75 + .75 = 3.5). Округление построит третий пиксель в точке (4, 4). Четвертый пиксель затем строит график (5, 4), так как y будет увеличен на 1, а x будет увеличен на 0,75 и будет равен 4,25.

Из этого примера вы видите проблему с вашим кодом?