Что подразумевается под симметричным DDA?
Я читал о DDA. Но я только что наткнулся на термин симметричный DDA. Что это? Чем он отличается от DDA?
1 ответ
Алгоритм DDA (Цифровой дифференциальный анализатор) используется для определения точек интерполяции между любыми заданными двумя точками, линейно (то есть, прямой линией). Теперь, поскольку это должно быть сделано на цифровом компьютере, скорость является важным фактором.
Уравнение прямой задается как m=Δx/Δy eq(i), где Δx = x(2)-x(1) & Δy = y(2)-y(1),
Теперь, используя это уравнение, мы можем вычислить последовательные точки, лежащие на прямой. Но тогда это дискретный мир растровой графики - поэтому нам нужны интегральные координаты.
В простом DDA eq(i) преобразуется в m=eΔx/eΔy, где e, назовем его коэффициентом приращения, является положительным действительным числом. поскольку помещение одного и того же числа в числитель и знаменатель ничего не меняет - но при правильном выборе - это может помочь нам в создании дискретных точек, тем самым уменьшая перегрузку необходимости округлять результирующие точки.
По сути, нам нужно: увеличить координаты на фиксированную небольшую величину, начиная с начальной точки, и каждый раз, когда у нас появляется новая точка, продвигающаяся к конечной точке.
В простом DDA - e выбирается как 1/max(|Δx|,|Δy|) так, что одна из координат является целой, и только другая координата должна быть округлена. т.е. P(i+1) = P(i)+(1,Round(e*Δy)), при этом одна координата увеличивается на 1, а другая на e * Δy
В симметричном DDA - e выбирается таким образом, что хотя обе координаты результирующих точек должны быть округлены, это можно сделать очень эффективно, а значит, быстро.
В частности, е выбирается как 1/2^n, где 2^(n-1) <= max(|Δx|,|Δy|) < 2^n. Другими словами, длина строки принимается равной 2 ^ n. Приращения для двух координат составляют e*Δx и e*Δy. При правильно выбранной начальной дробной части начальных координат: это приводит к тому, что точки генерируются как смешанные дроби, дробные части которых находятся в циклическом ряду, то есть они повторяются на небольшой длине. Таким образом, результирующие координаты могут быть легко округлены на основе двух справочных таблиц фиксированной длины, по одной для каждой координаты.
см. пример http://w3.msi.vxu.se/~gsu/DAB726-Ht06/Symm-DDA.pdf.
Обратите внимание на циклическое повторение в дробной части результирующих координат.