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

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


1. Алгоритм

Нехай відрізок заданий речовими координатами кінців (X_1, y_1) ; (X_2, y_2) . Растровими ( цілочисельними) координатами кінцевих точок стають округлені значення вихідних координат: xstart = round (x_1) , ystart = round (y_1) ; xend = round (x_2) , yend = round (y_2) [1].

Більше з двох чисел - (Xend-xstart) або (Yend-ystart) - По абсолютній величині приймається за кількість кроків L циклу растеризації, збільшене на 1.

На початку циклу допоміжним речовим змінним x і y присвоюються початкові координати початку відрізка: x = x_1 ; y = y_1 . На кожному кроці циклу ці речові змінні отримують прирости (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; } 

Модифікований алгоритм DDA-лінії застосовується для растеризації окружностей.


Примітки

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