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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Алгоритм DDA-лінії растеризує відрізок прямої між початковою та кінцевою точками. В найпростішій реалізації алгоритм інтерполює значення з інтервалів [(xstart, ystart), (xend, yend)] обчислюючи для кожного xi вираз xi = xi−1+1/m, yi = yi−1 + m, де Δx = xend − xstart , Δy = yend − ystart та m = Δy/Δx.

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

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

Алгоритм[ред.ред. код]

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

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

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

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

Далі представлено програмний код реалізації алгоритму DDA-лінії. Значення допоміжних змінних x і 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. Взагалі кажучи, якщо дійсні координати кінців відрізка задані в деякій логічній системі координат, то відповідні їм растрові координати визначаються на підставі правил перерахунку, встановлених для конкретної пари систем координат: логічної і екранної.

Див. також[ред.ред. код]

Джерела[ред.ред. код]