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

Мне нужна помощь в отношении алгоритма 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 любой 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

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

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


algorithm graphics dda
person M3taSpl0it    schedule 03.11.2009    source источник
comment
Для меня это не похоже на вопрос С++.   -  person navigator    schedule 03.11.2009
comment
да, это C-программа, извините за ошибку   -  person    schedule 03.11.2009

Ответы (2)


arrow_upward
2
arrow_downward

Кажется, здесь есть небольшая путаница.

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

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

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

person Jerry Coffin    schedule 03.11.2009
comment
вы, кажется, учите меня алгоритму Брезенхема, еще больше запутавшись, если вы рассказываете о DDA, не могли бы вы рассказать об этом более описательно? спасибо - person ; 03.11.2009

arrow_upward
3
arrow_downward

Расположение пикселей — это целочисленные значения. Уравнения идеальной линии представлены действительными числами. Таким образом, алгоритмы рисования линий преобразуют действительные числа линейного уравнения в целые значения. Сложный и медленный способ нарисовать линию — оценить уравнение линии для каждого значения 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 и округлить до целого значения. Это не работает, если вы не поддерживаете значение 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. Значение x будет равно 2,75, которое округляется до 3, и (3, 3) отображается на графике. Третий пиксель снова увеличит y, а затем добавит изменение x к x (2,75 + 0,75 = 3,5). Округление нанесет третий пиксель на (4, 4). Затем четвертый пиксель будет отображать (5, 4), поскольку y будет увеличен на 1, а x будет увеличен на 0,75 и будет равен 4,25.

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

person Mr. Berna    schedule 11.11.2009