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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Алгоритм DDA-линии растеризует отрезок прямой между двумя заданными точками, используя вычисления с вещественными числами. Аббревиатура 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.

Применение вычислений с вещественными числами и лишь однократное использование округления для окончательного получения значения растровой координаты обусловливают высокую точность и низкое быстродействие алгоритма.

Далее представлен программный код реализации[источник не указан 1378 дней] алгоритма 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. Вообще говоря, если вещественные координаты концов отрезка заданы в некоторой логической системе координат, то соответствующие им растровые координаты определяются на основании правил пересчёта, установленных для конкретной пары систем координат: логической и экранной.

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]

Литература[править | править вики-текст]

  • Роджерс Д. Алгоритмические основы машинной графики. — М.: Мир, 1989. — С. 50-54. — ISBN 5-03-000476-9