Line Drawing Algorithms: DDA Algorithm, VECGEN, Bresenham

📖 Theory

બે છેડાથી pixels ની હરોળ સુધી

આ વિષયનું હૃદય છે. લીટીના બે છેડા આપેલા હોય, તો બરાબર કયા pixels પ્રગટાવવા? બે પ્રચલિત algorithms આનો જવાબ આપે છે: DDA અને Bresenham (અને એ જ કુટુંબનું VECGEN). પરીક્ષામાં બંને પ્રિય છે, અને બંનેને pixel પ્રમાણે સમજવા જેવા છે.

આપણે એક જ લીટી, એટલે કે (0, 0) થી (5, 3) સુધીની (ઢાળ 0.6), બંને algorithms માંથી ગણીશું અને એ જ pixels મેળવીશું, જેથી તમે બંનેને સીધા સરખાવી શકો. પછી જોઈશું કે ફક્ત પૂર્ણાંક ગણિત વાપરતું Bresenham કેમ પસંદ કરાય છે. આંકડા ધ્યાનથી અનુસરો; પરીક્ષા આ સામગ્રીની જ સૌથી આકરી કસોટી કરે છે.

📖 Theory

DDA: પગલું ભરો અને પૂર્ણાંક બનાવો

DDA (Digital Differential Analyzer) લીટીને એકમ પગલે તપાસે છે અને નજીકના pixel પર પૂર્ણાંક બનાવે છે.

(0,0) થી (5,3) માટે: dx = 5, dy = 3. લો steps = max(|dx|, |dy|) = 5. વધારા છે xInc = dx/steps = 1 અને yInc = dy/steps = 0.6. (0,0) થી શરૂ કરો અને વારંવાર વધારા ઉમેરતા જાઓ, અને દરેક બિંદુને પૂર્ણાંક બનાવો:

• (0, 0)
• (1, 0.6) નું પૂર્ણાંક રૂપ (1, 1)
• (2, 1.2) નું પૂર્ણાંક રૂપ (2, 1)
• (3, 1.8) નું પૂર્ણાંક રૂપ (3, 2)
• (4, 2.4) નું પૂર્ણાંક રૂપ (4, 2)
• (5, 3.0) એટલે (5, 3)

Pixels: (0,0), (1,1), (2,1), (3,2), (4,2), (5,3). સાદું છે, પણ એ દરેક પગલે floating point (0.6) અને પૂર્ણાંક બનાવવાની ક્રિયા વાપરે છે.

⌨️ Practical

DDA line algorithm (લીટી દોરવાનો DDA)

void ddaLine(int x1, int y1, int x2, int y2) {
    int dx = x2 - x1, dy = y2 - y1;
    int steps = abs(dx) > abs(dy) ? abs(dx) : abs(dy);   // max(|dx|,|dy|)
    float xInc = (float)dx / steps;   // 5/5 = 1.0
    float yInc = (float)dy / steps;   // 3/5 = 0.6
    float x = x1, y = y1;
    for (int i = 0; i <= steps; i++) {
        putPixel(round(x), round(y));  // (0,0)(1,1)(2,1)(3,2)(4,2)(5,3)
        x += xInc;
        y += yInc;
    }
}

📖 Theory

Bresenham: પૂર્ણાંક અને decision parameter

Bresenham નો algorithm એ જ લીટીને ફક્ત પૂર્ણાંક ગણિતથી દોરે છે, જરાય floating point વગર. છીછરી લીટી માટે (ઢાળ 0 અને 1 વચ્ચે) એ x પર પગલાં ભરે છે અને દરેક પગલે decision parameter p વાપરીને નક્કી કરે છે કે y એનું એ રહેશે કે 1 વધશે.

(0,0) થી (5,3) માટેની ગોઠવણ: dx = 5, dy = 3. શરૂઆતનું decision parameter છે p0 = 2dy - dx = 6 - 5 = 1. બે અચળ પહેલેથી ગણી લો: 2dy = 6 અને 2dy - 2dx = -4. પછી દરેક x પર pixel મૂકો અને p સુધારો: જો p < 0 હોય તો p માં 2dy ઉમેરો (y એનું એ રહે); નહીં તો p માં 2dy - 2dx ઉમેરો અને y ને 1 વધારો.

🪜 Follow along

(0,0) થી (5,3) માટે Bresenham ગણીને

1. x=0, p=1 (0,0) મૂકો. p >= 0 છે, એટલે p = 1 + (-4) = -3, અને y થાય 1.
2. x=1, p=-3 (1,1) મૂકો. p < 0 છે, એટલે p = -3 + 6 = 3 (y એનું એ 1 રહે).
3. x=2, p=3 (2,1) મૂકો. p >= 0 છે, એટલે p = 3 + (-4) = -1, અને y થાય 2.
4. x=3, p=-1 (3,2) મૂકો. p < 0 છે, એટલે p = -1 + 6 = 5 (y એનું એ 2 રહે).
5. x=4, p=5 (4,2) મૂકો. p >= 0 છે, એટલે p = 5 + (-4) = 1, અને y થાય 3.
6. x=5, p=1 (5,3) મૂકો. પૂરું.

⌨️ Practical

Bresenham line algorithm (ઢાળ 0 થી 1)

void bresenhamLine(int x1, int y1, int x2, int y2) {
    int dx = x2 - x1, dy = y2 - y1;
    int p = 2 * dy - dx;      // p0 = 2dy - dx = 1
    int y = y1;
    for (int x = x1; x <= x2; x++) {
        putPixel(x, y);       // (0,0)(1,1)(2,1)(3,2)(4,2)(5,3)
        if (p < 0) {
            p = p + 2 * dy;            // 2dy = 6
        } else {
            p = p + 2 * dy - 2 * dx;   // 2dy - 2dx = -4
            y = y + 1;
        }
    }
}

✏️ Formula

DDA સામે Bresenham: Bresenham કેમ જીતે છે

આપણી લીટી માટે બંને એ જ pixels આપે છે, તો પછી Bresenham કેમ પસંદ કરવું? DDA floating point ગણિત વાપરે છે (0.6 નો વધારો) અને દરેક પગલે પૂર્ણાંક બનાવે છે, જે ધીમું છે અને લાંબી લીટીઓ પર પૂર્ણાંક બનાવવાની ભૂલ ભેગી થતી જાય છે. Bresenham ફક્ત પૂર્ણાંક સરવાળો અને સરખામણી વાપરે છે, અપૂર્ણાંક નહીં, પૂર્ણાંક બનાવવાનું નહીં, એટલે એ વધુ ઝડપી અને ચોક્કસ છે, અને hardware માટે આદર્શ.

એટલે જ Bresenham (અને એ જ કુટુંબનાં VECGEN જેવાં પૂર્ણાંક line generators) પ્રમાણભૂત બની ગયાં. Decision parameter એ ચતુર યુક્તિ છે: એ ફક્ત પૂર્ણાંક વાપરીને નજર રાખે છે કે ખરી લીટી y ને એક વધારવા જેટલી ઊંચી ગઈ છે કે નહીં. પરિણામ એ જ, પણ ગણિત સસ્તું.

🧩 Quiz

લીટી (0,0) થી (5,3) માટે Bresenham ના algorithm માં શરૂઆતનું decision parameter p0 શું છે?

1. p0 = dx - dy = 2
2. p0 = 2dy - dx = 2(3) - 5 = 1
3. p0 હંમેશા 0 જ હોય
4. p0 = dy/dx = 0.6

💭 Think first

Bresenham માટે floating point ટાળવું આટલી મોટી વાત કેમ છે?

DDA એના 0.6 ના વધારા સાથે બરાબર ચાલે જ છે. તો પણ Bresenham નું ફક્ત પૂર્ણાંક વાળું ગણિત આટલું મહત્ત્વનું કેમ? વિચારીને પછી tap કરો.

✅ Summary

Key takeaways

• લીટી દોરવાના algorithms બે છેડાને એવા pixels માં ફેરવે છે જે લીટીની સૌથી નજીક બેસે.
• DDA: steps = max(|dx|,|dy|); વધારા xInc = dx/steps, yInc = dy/steps; દરેક પગલે ઉમેરો અને પૂર્ણાંક બનાવો.
• (0,0) થી (5,3) પર DDA: steps 5, yInc 0.6, pixels (0,0)(1,1)(2,1)(3,2)(4,2)(5,3); એ floating point વાપરે છે.
• Bresenham (ઢાળ 0 થી 1): p0 = 2dy - dx; p < 0 હોય તો 2dy ઉમેરો, નહીં તો 2dy - 2dx ઉમેરો અને y ને 1 વધારો; બધું જ પૂર્ણાંકમાં.
• એ જ લીટી પર Bresenham: p0 = 1, p ની હાર 1, -3, 3, -1, 5, 1, અને એ જ pixels મળે છે.
• Bresenham એટલા માટે પસંદ કરાય છે કે પૂર્ણાંક ગણિત વધુ ઝડપી, ચોક્કસ (પૂર્ણાંક બનાવવાની ભૂલ ભેગી ન થાય) અને hardware ને અનુકૂળ છે; VECGEN એ સંબંધિત પૂર્ણાંક line generator છે.
• યાદ રાખવાની કડી: DDA અપૂર્ણાંક ઉમેરીને પૂર્ણાંક બનાવે છે; Bresenham પૂર્ણાંક અને decision parameter p0 = 2dy - dx વાપરે છે.