Line Drawing Algorithms: DDA Algorithm, VECGEN, Bresenham

📖 Theory

दो Endpoints से Pixels की एक Row तक

यही subject का heart है। एक line के दो endpoints दिए, आप exactly कौन से pixels light up करते हैं? दो classic algorithms इसका answer देते हैं: DDA और Bresenham (उसी family में VECGEN के साथ)। दोनों exam favourites हैं, और दोनों pixel by pixel समझने लायक हैं।

हम same line के साथ work करेंगे, (0, 0) से (5, 3) तक (slope 0.6), दोनों algorithms के through, और same pixels पाएँगे, तो आप इन्हें directly compare कर सकते हैं। फिर हम देखेंगे क्यों Bresenham, सिर्फ़ integer arithmetic इस्तेमाल करते हुए, preferred है। Numbers को closely follow कीजिए; यह वह material है जिसे exams सबसे hard test करते हैं।

📖 Theory

DDA: Step और Round

DDA (Digital Differential Analyzer) line को unit steps पर sample करता है और nearest pixel तक round करता है।

(0,0) से (5,3) के लिए: dx = 5, dy = 3। steps = max(|dx|, |dy|) = 5 लीजिए। Increments हैं xInc = dx/steps = 1 और yInc = dy/steps = 0.6। (0,0) से start कीजिए और repeatedly increments add कीजिए, हर point को round करते हुए:

• (0, 0)
• (1, 0.6) round होकर (1, 1) बनता है
• (2, 1.2) round होकर (2, 1) बनता है
• (3, 1.8) round होकर (3, 2) बनता है
• (4, 2.4) round होकर (4, 2) बनता है
• (5, 3.0) (5, 3) है

Pixels: (0,0), (1,1), (2,1), (3,2), (4,2), (5,3)। Simple, पर यह floating-point (वह 0.6) और हर step पर rounding इस्तेमाल करता है।

⌨️ Practical

DDA line algorithm

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: Integers और एक Decision Parameter

Bresenham's algorithm same line draw करता है सिर्फ़ integer arithmetic इस्तेमाल करके, कोई floating point नहीं। एक shallow line (slope 0 और 1 के बीच) के लिए यह x के along step करता है और, हर step पर, एक decision parameter p इस्तेमाल करता है यह choose करने के लिए कि y same रहे या 1 से बढ़े।

(0,0) से (5,3) के लिए setup: dx = 5, dy = 3। Initial decision parameter है p0 = 2dy - dx = 6 - 5 = 1। दो constants precompute कीजिए: 2dy = 6 और 2dy - 2dx = -4। फिर हर x पर, pixel plot कीजिए, और update कीजिए: अगर p < 0, p में 2dy add कीजिए (y same रहता है); नहीं तो p में 2dy - 2dx add कीजिए और y increment कीजिए।

🪜 Follow along

(0,0) से (5,3) के लिए Bresenham Worked

1. x=0, p=1 (0,0) plot कीजिए। p >= 0, तो p = 1 + (-4) = -3, और y 1 बनता है।
2. x=1, p=-3 (1,1) plot कीजिए। p < 0, तो p = -3 + 6 = 3 (y 1 पर रहता है)।
3. x=2, p=3 (2,1) plot कीजिए। p >= 0, तो p = 3 + (-4) = -1, और y 2 बनता है।
4. x=3, p=-1 (3,2) plot कीजिए। p < 0, तो p = -1 + 6 = 5 (y 2 पर रहता है)।
5. x=4, p=5 (4,2) plot कीजिए। p >= 0, तो p = 5 + (-4) = 1, और y 3 बनता है।
6. x=5, p=1 (5,3) plot कीजिए। Done।

⌨️ Practical

Bresenham line algorithm (slope 0 to 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 vs Bresenham: Bresenham क्यों जीतता है

दोनों हमारी line के लिए same pixels produce करते हैं, तो Bresenham क्यों prefer किया जाए? DDA floating-point arithmetic इस्तेमाल करता है (वह 0.6 increment) और हर step पर round करता है, जो slower है और long lines पर rounding error accumulate कर सकता है। Bresenham सिर्फ़ integer addition और comparison इस्तेमाल करता है, कोई floats नहीं, कोई rounding नहीं, जो faster और exact है, hardware के लिए ideal।

यही वजह है Bresenham (और same family में VECGEN जैसे integer line generators) standard बन गए। Decision parameter clever trick है: यह track करता है कि true line ने y को bump करने लायक enough rise किया है या नहीं, सिर्फ़ integers इस्तेमाल करते हुए। Same result, cheaper arithmetic।

🧩 Quiz

Line (0,0) से (5,3) के लिए Bresenham's algorithm में, initial 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

Floating Point Avoid करना Bresenham के लिए इतनी बड़ी बात क्यों है?

DDA अपने 0.6 increment के साथ fine काम करता है। Bresenham का integer-only arithmetic इतना matter क्यों करता है? फिर tap कीजिए।

✅ Summary

Key takeaways

• Line-drawing algorithms दो endpoints को उन pixels में बदलते हैं जो line को best approximate करते हैं।
• DDA: steps = max(|dx|,|dy|); increments xInc = dx/steps, yInc = dy/steps; हर step add और round कीजिए।
• (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 (slope 0 से 1): p0 = 2dy - dx; अगर p < 0 तो 2dy add कीजिए, नहीं तो 2dy - 2dx add कीजिए और y increment कीजिए; integer only।
• Same line पर Bresenham: p0 = 1, p-sequence 1, -3, 3, -1, 5, 1, same pixels देते हुए।
• Bresenham preferred है क्योंकि integer arithmetic faster, exact (कोई accumulating rounding नहीं), और hardware-friendly है; VECGEN एक related integer line generator है।
• Memory hook: DDA एक fraction add करता है और round करता है; Bresenham integers और एक decision parameter p0 = 2dy - dx इस्तेमाल करता है।