Алгоритм DDA-линии растеризует отрезок прямой между двумя заданными точками, используя вычисления с вещественными числами. Аббревиатура DDA в названии этого алгоритма машинной графики происходит от англ. Digital Differential Analyzer (цифровой дифференциальный анализатор) — вычислительное устройство, применявшееся ранее для генерации векторов. Несмотря на то, что сейчас этот алгоритм практически не применяется, он позволяет понять сложности, которые встречаются при растеризации отрезка и способы их решения.
Пусть отрезок задан вещественными координатами концов (x1,y1); (x2,y2). Растровыми (целочисленными) координатами концевых точек становятся округлённые значения исходных координат: xstart=round(x1), ystart=round(x2); xend=round(x2), yend=round(y2).
Большее из двух чисел — (xend - xstart) или (yend - ystart) — по абсолютной величине принимается за количество шагов L цикла растеризации, увеличенное на 1.
В начале цикла вспомогательным вещественным переменным x и u присваиваются исходные координаты начала отрезка: x=x1; y=y1. На каждом шаге цикла эти вещественные переменные получают приращения (xend - xstart)/L; (yend - ystart)/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; }
void line_DDA(HDC hdc, float x1, float y1, float x2, float y2) { // Целочисленные значения координат начала и конца отрезка, // округленные до ближайшего целого int iX1 = roundf(x1); int iY1 = roundf(y1); int iX2 = roundf(x2); int iY2 = roundf(y2); // Длина и высота линии int deltaX = abs(iX1 - iX2); int deltaY = abs(iY1 - iY2); // Считаем минимальное количество итераций, необходимое // для отрисовки отрезка. Выбирая максимум из длины и высоты // линии, обеспечиваем связность линии int length = max(deltaX, deltaY); // особый случай, на экране закрашивается ровно один пиксел if (length == 0) { SetPixel (hdc, iX1, iY1, 0); return; } // Вычисляем приращения на каждом шаге по осям абсцисс и ординат double dX = (x2 - x1) / length; double dY = (y2 - y1) / length; // Начальные значения double x = x1; double y = y1; // Основной цикл length++; while (length--) { x += dX; y += dY; SetPixel(hdc, roundf(x), roundf(y), 0); } }
Прикрепленный файл | Размер |
---|---|
Исходный код | 6.12 кб |
Исполняемый файл | 12.16 кб |