2026-07-07 #Computer Graphics #Algorithms #Mathematics

Drawing Lines Like a Pro: Demystifying the DDA Algorithm
কম্পিউটার গ্রাফিক্সে লাইন আঁকার সহজ কৌশল: DDA অ্যালগরিদম!

Let's explore how computers draw perfect straight lines pixel-by-pixel using the simplest approach in Computer Graphics: the Digital Differential Analyzer (DDA) Algorithm.
কম্পিউটার কীভাবে স্ক্রিনে নিখুঁত সোজা লাইন আঁকে? চলো জেনে নিই কম্পিউটার গ্রাফিক্সের সবচেয়ে সহজ 'DDA অ্যালগরিদম' এবং এর পেছনের গাণিতিক ম্যাজিক!

Hello! Today we are going to dive into the mathematical magic behind how computers draw straight lines on your screen. When you draw a line in MS Paint or any graphics software, the computer has to figure out exactly which tiny pixels to light up. Let's see how it does this using the DDA Line Drawing Algorithm.

1. An Overview of Line Drawing Algorithms

To draw a line perfectly on a pixelated screen, Computer Graphics mainly relies on three popular algorithms:

  1. DDA Line Drawing Algorithm (Digital Differential Analyzer)
  2. Bresenham Line Drawing Algorithm
  3. Mid-point Line Drawing Algorithm

Among these, the DDA Algorithm is considered the absolute simplest. If you give it a starting coordinate $(X_0, Y_0)$ and an ending coordinate $(X_n, Y_n)$, it uses basic mathematics to calculate all the intermediate pixel points step by step.

2. The Four Mathematical Cases of DDA

Before jumping into the calculations, we first need to find three base values from our given points:

  • $\Delta X = X_n - X_0$
  • $\Delta Y = Y_n - Y_0$
  • Slope of the line, $M = \frac{\Delta Y}{\Delta X}$

Based on the value of the slope ($M$), DDA decides the next pixel using one of these four cases:

  • Case 01 ($0 < M \le 1$): Positive slope, less than or equal to 1. $X_1 = X_0 + 1$ $Y_1 = Y_0 + M$
  • Case 02 ($-1 < M \le 0$): Negative slope, greater than -1. $X_1 = X_0 - 1$ $Y_1 = Y_0 - M$
  • Case 03 ($M > 1$): Steep positive line. $X_1 = X_0 + \frac{1}{M}$ $Y_1 = Y_0 + 1$
  • Case 04 ($M \le -1$): Steep negative line. $X_1 = X_0 - \frac{1}{M}$ $Y_1 = Y_0 - 1$

3. Solving a Problem (Slope $M > 1$)

Question: Find the intermediate pixels between starting point $(5, 6)$ and ending point $(8, 12)$.

  • $\Delta X = 8 - 5 = 3$
  • $\Delta Y = 12 - 6 = 6$
  • $M = \frac{6}{3} = 2$

Since $\mathbf{M = 2}$ (which is $> 1$), this falls under Case 03. Here, $Y$ increases by $1$ in every step, and $X$ increases by $\frac{1}{M}$ (which is $0.5$). As we progress, we add $0.5$ to $X$ and $1$ to $Y$. Because screens don't have half-pixels, we use a round_off() function to convert decimals to integers (e.g., $5.5, 7$ becomes $6, 7$). The resulting pixels drawn on the screen will form a zigzag staircase pattern!

4. Solving a Problem (Slope $M < 1$)

Question: Calculate pixels between $(5, 6)$ and $(13, 10)$.

  • $\Delta X = 13 - 5 = 8$
  • $\Delta Y = 10 - 6 = 4$
  • $M = \frac{4}{8} = 0.50$

Since $\mathbf{M = 0.50}$ (between $0$ and $1$), this is Case 01. Here, $X$ increases by $1$, and $Y$ increases by $M = 0.50$ in every step. When plotted and rounded off, this line appears much flatter horizontally.

5. Solving a Problem (Slope $M = 1$)

Question: Find pixels between $(1, 7)$ and $(11, 17)$.

  • $M = \frac{10}{10} = 1$

This is the perfect $45^\circ$ angle, satisfying the upper limit of Case 01. Both $X$ and $Y$ will increase evenly by $1$ in every single step! Since there are no decimals, no rounding off is needed. The line is drawn perfectly straight without any jagged edges.

6. Advantages & Disadvantages of DDA

Why should we use DDA, and why shouldn't we?

  • Advantages: It is incredibly simple to understand and easy to implement in code. It also completely avoids heavy multiplication operations to calculate pixels, making it highly efficient since addition is much faster for a computer than multiplication.
  • Disadvantages: It constantly uses the round_off() function in every step. This creates an overhead for the processor, increasing the time complexity. Furthermore, rounding off causes the final lines to look jagged (not smooth) and slightly inaccurate compared to perfect mathematical lines.

[!NOTE] IMPORTANT NOTES FOR NOTEBOOK Concept: DDA Line Drawing Algorithm Key Point 1: Slope Formula: $M = \frac{\Delta Y}{\Delta X}$ Key Point 2: Four Cases: Based on whether the slope is positive, negative, steep ($>1$), or gradual ($\le 1$). Advantage: Simple algorithm that avoids costly multiplication, opting for faster addition. Disadvantage: Heavy overhead from continuous round_off() function calls, leading to increased time complexity and jagged, less accurate lines.

Hope this makes the math behind line drawing algorithms a lot less intimidating!

হ্যালো! চলো আজ আমরা কম্পিউটার স্ক্রিনে সোজা লাইন আঁকার পেছনের গাণিতিক ম্যাজিকটি শিখে নিই। তুমি যখন MS Paint বা কোনো গ্রাফিক্স সফটওয়্যারে একটি লাইন টানো, তখন কম্পিউটারকে ঠিক করতে হয় যে স্ক্রিনের কোন কোন পিক্সেলগুলো জ্বালাতে হবে। আজ আমরা দেখব কম্পিউটার কীভাবে DDA লাইন ড্রয়িং অ্যালগরিদম ব্যবহার করে এই কাজটা করে।

১. লাইন ড্রয়িং অ্যালগরিদমের ধারণা

স্ক্রিনে নিখুঁতভাবে পিক্সেল সিলেক্ট করে লাইন আঁকার জন্য কম্পিউটার গ্রাফিক্সে মূলত তিনটি জনপ্রিয় অ্যালগরিদম ব্যবহার করা হয়: ১. DDA Line Drawing Algorithm (Digital Differential Analyzer) ২. Bresenham Line Drawing Algorithm ৩. Mid point Line Drawing Algorithm

এগুলোর মধ্যে DDA Algorithm হলো সবচেয়ে সহজ! যখন একটি লাইনের স্টার্টিং পয়েন্ট $(X_0, Y_0)$ এবং এন্ডিং পয়েন্ট $(X_n, Y_n)$ দেওয়া থাকে, তখন এটি চমৎকার গাণিতিক নিয়মে মাঝখানের পিক্সেলগুলো ধাপে ধাপে বের করে ফেলে।

২. DDA অ্যালগরিদমের ৪টি গাণিতিক শর্ত (Cases)

যেকোনো হিসাব শুরুর আগে আমাদের দেওয়া ইনপুট থেকে তিনটি জিনিস বের করে নিতে হয়:

  • $\Delta X = X_n - X_0$
  • $\Delta Y = Y_n - Y_0$
  • লাইনের ঢাল (Slope), $M = \frac{\Delta Y}{\Delta X}$

এই ঢাল বা $M$-এর মানের ওপর ভিত্তি করেই পরের পিক্সেলটি বের করার ৪টি আলাদা শর্ত বা Case তৈরি হয়:

  • Case 01 ($0 < M \le 1$): ঢাল পজিটিভ এবং ১-এর কম বা সমান। $X_1 = X_0 + 1$ $Y_1 = Y_0 + M$
  • Case 02 ($-1 < M \le 0$): ঢাল নেগেটিভ কিন্তু $-1$ এর চেয়ে বড়। $X_1 = X_0 - 1$ $Y_1 = Y_0 - M$
  • Case 03 ($M > 1$): ঢাল যদি ১-এর চেয়ে বড় হয় (খাড়া লাইন)। $X_1 = X_0 + \frac{1}{M}$ $Y_1 = Y_0 + 1$
  • Case 04 ($M \le -1$): ঢাল যদি $-1$ এর সমান বা ছোট হয়। $X_1 = X_0 - \frac{1}{M}$ $Y_1 = Y_0 - 1$

৩. গাণিতিক সমস্যার সমাধান (ঢাল $M > 1$)

প্রশ্ন: স্টার্টিং পয়েন্ট $(5, 6)$ এবং এন্ডিং পয়েন্ট $(8, 12)$ এর মধ্যবর্তী পিক্সেলগুলো বের করো।

  • $\Delta X = 8 - 5 = 3$
  • $\Delta Y = 12 - 6 = 6$
  • $M = \frac{6}{3} = 2$

যেহেতু এখানে $\mathbf{M = 2}$, যা ১-এর চেয়ে বড় ($\mathbf{M > 1}$), তাই এটি Case 03-কে নির্দেশ করে। সূত্র অনুযায়ী, প্রতিবার $Y$ বাড়বে ১ ঘর করে এবং $X$ বাড়বে $\frac{1}{M}$ অর্থাৎ $0.5$ ঘর করে। হিসাবের সময় প্রাপ্ত দশমিক মানগুলোকে স্ক্রিনে বসানোর জন্য round_off() ফাংশন দিয়ে রাউন্ড বা পূর্ণসংখ্যা করে নিতে হয় (যেমন $5.5, 7$ হয়ে যাবে $6, 7$)। গ্রাফে বসালে এটি একটি জিগ-জ্যাগ বা সিঁড়ির মতো লাইনে যুক্ত হবে!

৪. গাণিতিক সমস্যার সমাধান (ঢাল $M < 1$)

প্রশ্ন: স্টার্টিং পয়েন্ট $(5, 6)$ এবং এন্ডিং পয়েন্ট $(13, 10)$ এর মধ্যবর্তী পিক্সেলগুলো গণনা করো।

  • $\Delta X = 13 - 5 = 8$
  • $\Delta Y = 10 - 6 = 4$
  • $M = \frac{4}{8} = 0.50$

এখানে $\mathbf{M = 0.50}$, যা $0$ থেকে $1$ এর মধ্যে অবস্থিত। তাই এটি Case 01 মেনে চলে। এবার সূত্র অনুযায়ী প্রতিবার $X$ বাড়বে ১ ঘর করে এবং $Y$ বাড়বে $M$ অর্থাৎ $0.50$ ঘর করে। রাউন্ড অফ করার পর রেখাটি ভূমির দিকে বেশি চ্যাপ্টা বা ফ্ল্যাট দেখাবে।

৫. গাণিতিক সমস্যার সমাধান (ঢাল $M = 1$)

প্রশ্ন: স্টার্টিং পয়েন্ট $(1, 7)$ এবং এন্ডিং পয়েন্ট $(11, 17)$ এর মধ্যবর্তী পিক্সেলগুলো বের করো।

  • $M = \frac{10}{10} = 1$

যেহেতু $\mathbf{M = 1}$, এটি নিখুঁত $45^\circ$ কোণ নির্দেশ করে, যা আমাদের Case 01-এর সর্বোচ্চ সীমার শর্ত পূরণ করে। এই ক্ষেত্রে $X$ এবং $Y$ উভয়ই প্রতি ধাপে ১ ঘর করে সমানভাবে বৃদ্ধি পাবে। যেহেতু কোনো দশমিক মান নেই, তাই সরাসরি পূর্ণসংখ্যা পাওয়া যাবে এবং গ্রাফে লাইনটি একদম সোজা ও নিখুঁত হবে!

৬. DDA অ্যালগরিদমের সুবিধা ও অসুবিধা

  • সুবিধা: এটি অত্যন্ত সহজ একটি অ্যালগরিদম এবং কোডে বাস্তবায়ন করা সহজ। লাইনের পিক্সেল গণনায় এটি কোনো গুণন (Multiplication) অপারেশন ব্যবহার করে না, বরং যোগ ব্যবহার করে, যা প্রসেসিং টাইম অনেক বাঁচায়।
  • অসুবিধা: প্রতি ধাপে দশমিক স্থানাঙ্ককে পূর্ণসংখ্যায় রূপান্তর করতে round_off() ফাংশন ব্যবহার করতে হয়, যা প্রসেসরের ওপর বাড়তি কাজের চাপ তৈরি করে এবং টাইম কমপ্লেক্সিটি বাড়িয়ে দেয়। এই রাউন্ড অফ করার কারণে লাইনগুলো একদম মসৃণ হয় না, কিছুটা খাঁজকাটা (jagged) ভাব থেকে যায় এবং এর নির্ভুলতাও কিছুটা কমে যায়।

[!NOTE] IMPORTANT NOTES FOR NOTEBOOK Concept: DDA Line Drawing Algorithm Key Point 1: Slope Formula: $M = \frac{\Delta Y}{\Delta X}$ Key Point 2: Four Cases: Based on whether the slope is positive, negative, steep ($>1$), or gradual ($\le 1$). Advantage: Simple algorithm that avoids costly multiplication, opting for faster addition. Disadvantage: Heavy overhead from continuous round_off() function calls, leading to increased time complexity and jagged, less accurate lines.

আশা করি লাইন আঁকার পেছনের এই ম্যাথমেটিক্স এখন তোমার কাছে পানির মতো পরিষ্কার!

GitHub LinkedIn Portfolio Blog