Алгоритм DDA-лінії

Алгоритм DDA-лінії растеризує відрізок прямої між початковою та кінцевою точками. В найпростішій реалізації алгоритм інтерполює значення з інтервалів [(x_start, y_start), (x_end, y_end)] обчислюючи для кожного x_i вираз x_i = x_i−1+1/m, y_i = y_i−1 + m, де Δx = x_end − x_start , Δy = y_end − y_start та m = Δy/Δx.

Абревіатура DDA в назві цього алгоритму комп'ютерної графіки походить від англ. Digital Differential Analyzer (цифровий диференціальний аналізатор) — обчислювальний пристрій, що застосовувалося раніше для генерації векторів.

Алгоритм можна реалізувати використовуючи дійсні або цілі числа.

Алгоритм

Нехай відрізок заданий дійсними координатами кінців ${\displaystyle (x_{1},y_{1});(x_{2},y_{2})}$. Растровими (цілочисельними) координатами кінцевих точок стають округлені значення вихідних координат: ${\displaystyle x_{\mathrm {start} }=\operatorname {round} (x_{1}),y_{\mathrm {start} }=\operatorname {round} (y_{1});}$${\displaystyle x_{\mathrm {end} }=\operatorname {round} (x_{2}),y_{\mathrm {end} }=\operatorname {round} (y_{2})}$.

Більше з двох чисел — ${\displaystyle (x_{\mathrm {end} }-x_{\mathrm {start} })}$ або ${\displaystyle (y_{\mathrm {end} }-y_{\mathrm {start} })}$ — за абсолютною величиною приймається за кількість кроків ${\displaystyle L}$ циклу растеризації, збільшене на 1.

На початку циклу допоміжним дійсним змінним ${\displaystyle x}$ і ${\displaystyle y}$ присвоюються вихідні координати початку відрізка: ${\displaystyle x=x_{1};y=y_{1}}$. На кожному кроці циклу ці дійсні змінні отримують приріст ${\displaystyle (x_{\mathrm {end} }-x_{\mathrm {start} })/L;(y_{\mathrm {end} }-y_{\mathrm {start} })/L}$. Растрові ж координати, віднайдені на кожному кроці, є результатом округлення відповідних дійсних значень ${\displaystyle x}$ і ${\displaystyle y}$.

Застосування обчислень з дійсними числами і лише одноразове використання округлення для остаточного отримання значення растрової координати зумовлюють високу точність і низьку швидкодію алгоритму.

Далі представлено програмний код реалізації алгоритму DDA-лінії. Значення допоміжних змінних ${\displaystyle x}$ і ${\displaystyle y}$ тут зберігаються у вигляді масивів.

void dda_line (float x1, float y1, float x2, float y2){  int i, L, xstart, ystart, xend, yend;  float dX, dY, x[1000], y[1000];   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-лінії застосовується для растеризації кіл.

Примітки

1. Взагалі кажучи, якщо дійсні координати кінців відрізка задані в деякій логічній системі координат, то відповідні їм растрові координати визначаються на підставі правил перерахунку, встановлених для конкретної пари систем координат: логічної і екранної.

Див. також

• Алгоритми побудови відрізка
• Алгоритм Брезенхейма
• Алгоритм Ву

Джерела

• Растеризація відрізка. Алгоритм DDA-лінії. (рос.) [ 7 грудня 2014 у Wayback Machine.]
• McCrea P. G., Baker P. W. On DDA circle generation for computer graphics. IEEE Trans. on Computers. — 1975. — V. C-24. — P. 1109–1110