Алгоритм DDA-линии растеризует отрезок прямой между двумя заданными точками, используя вычисления с вещественными числами. Аббревиатура DDA в названии этого алгоритма машинной графики происходит от англ. Digital Differential Analyzer (цифровой дифференциальный анализатор) — вычислительное устройство, применявшееся ранее для генерации векторов...
Содержание |
Пусть отрезок задан вещественными координатами концов ; . Растровыми (целочисленными) координатами концевых точек становятся округлённые значения исходных координат: , ; , [1].
Большее из двух чисел — или — по абсолютной величине принимается за количество шагов цикла растеризации, увеличенное на 1.
В начале цикла вспомогательным вещественным переменным и присваиваются исходные координаты начала отрезка: ; . На каждом шаге цикла эти вещественные переменные получают приращения / L; / L. Растровые же координаты, продуцируемые на каждом шаге, являются результатом округления соответствующих вещественных значений и .
Применение вычислений с вещественными числами и лишь однократное использование округления для окончательного получения значения растровой координаты обусловливают высокую точность и низкое быстродействие алгоритма.
Далее представлен программный код реализации алгоритма DDA-линии. Значения вспомогательных переменных и здесь сохраняются в виде массивов.
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-линии применяется для растеризации окружностей.
ЦДА.