Алгоритм DDA-лінії растеризує відрізок прямої між початковою та кінцевою точками. В найпростішій реалізації алгоритм інтерполює значення з інтервалів обчислюючи для кожного вираз , , де , та .
Абревіатура DDA в назві цього алгоритму комп'ютерної графіки походить від (цифровий диференціальний аналізатор) — обчислювальний пристрій, який раніше застосовували для генерування векторів.
Алгоритм можна реалізувати використовуючи дійсні або цілі числа.
Алгоритм Нехай відрізок задано дійсними координатами кінців . Растровими (цілочисельними) координатами кінцевих точок стають округлені значення вхідних координат: .Загалом, якщо дійсні координати кінців відрізка задано в деякій логічній системі координат, то відповідні їм растрові координати визначаються на підставі правил перерахунку, встановлених для конкретної пари систем координат: логічної й екранної.
Більше з двох чисел — або — за абсолютною величиною приймають за кількість кроків циклу растеризації, збільшену на 1.
На початку циклу допоміжним дійсним змінним і присвоюються вхідні координати початку відрізка: . На кожному кроці циклу ці дійсні змінні отримують приріст . Растрові ж координати, знайдені на кожному кроці, є результатом округлення відповідних дійсних значень і .
Застосування обчислень з дійсними числами і лише одноразове використання округлення для остаточного отримання значення растрової координати зумовлюють високу точність і низьку швидкодію алгоритму.
Далі представлено програмний код реалізації алгоритму DDA-лінії. Значення допоміжних змінних і тут зберігаються у вигляді масивів.
void dda_line (float x1, float y1, float x2, float y2){ int i, L, xstart, ystart, xend, yend; float dX, dY, x, y; xstart = roundf(x1); ystart = roundf(y1); xend = roundf(x2); yend = roundf(y2); L = max(abs(xend-xstart), abs(yend-ystart)); dX = (x2-x1) / L; dY = (y2-y1) / L; i = 0; x[i] = x1; y[i] = y1; i++; while (i < L)
x[i] = x[i-1] + dX; y[i] = y[i-1] + dY; i++;
x[i] = x2; y[i] = y2; /* Output: -----------------------*/ i = 0; while (i <= L)
plot (roundf(x[i]), roundf(y[i])); /* Draws a point. */ i++;
/* -------------------------------*/ }
Оптимізований алгоритм замість поділу використовує побітовий зсув. sx, sy — початок лінії tx, ty — кінець лінії. Застосовується в разі, якщо використання змінних із рухомою комою (float, double тощо) з певних причин неможливе. int l, dx, dy; int xr = Math.abs(tx-sx); int yr = Math.abs(ty-sy); if(xr > yr) {l=xr;} else {l=yr;} int px = (sx<<12)+(1<<11); // 1<<11 аналогично 0.5 у float int py = (sy<<12)+(1<<11); int ex = (tx<<12)+(1<<11); int ey = (ty<<12)+(1<<11); if(l != 0) { dx = (ex-px) / l; dy = (ey-py) / l; } else { dx = 0; dy = 0;
for(int i=0; i<=l; i++) { drawpoint(px>>12, py>>12); px += dx; py += dy;
Модифікований алгоритм DDA-лінії застосовують для растеризації кіл.
Примітки
Див. також Алгоритми побудови відрізка Алгоритм Брезенхейма Алгоритм Ву
Джерела Чириков С. В. Алгоритмы компьютерной графики (Методы растрирования кривых). Учебное пособие — СПб: СПбГИТМО(ТУ), 2001. — 120 с. Растеризація відрізка. Алгоритм DDA-лінії. (рос.) McCrea P. G., Baker P. W. On DDA circle generation for computer graphics. IEEE Trans. on Computers. — 1975. — V. C-24. — P. 1109–1110