Line Drawing Algorithms & DDA

Basic of Line (লাইনের মৌলিক ধারণা)

কম্পিউটার গ্রাফিক্সের জগতে সবচেয়ে মৌলিক জ্যামিতিক অবজেক্ট হলো একটি সরলরেখা (Straight Line)। কোনো ৩ডি মডেল, গেমের ক্যারেক্টার কিংবা মনিটরের উইন্ডো তৈরি করার সময় কম্পিউটারকে সবার আগে দুটি বিন্দুর মাঝে নিখুঁত রেখা আঁকা শিখতে হয়।

লাইন সেগমেন্ট ও এন্ডপয়েন্ট

একটি লাইন সেগমেন্ট বা রেখাংশ গাণিতিকভাবে তার দুটি প্রান্তবিন্দু (Endpoints) দ্বারা সংজ্ঞায়িত করা হয়:

$\text{Endpoint 1} = (x_1, y_1), \quad \text{Endpoint 2} = (x_2, y_2)$

• কন্টিনিউয়াস বনাম ডিসক্রিট: সাধারণ জ্যামিতিতে দুটি বিন্দুর মাঝে অসীম সংখ্যক বিন্দু থাকে। কিন্তু কম্পিউটারের মনিটর আসলে বর্গাকার পিক্সেলের (Discrete Grid) সমন্বয়ে গঠিত।
• লাইন স্ক্যান-কনভার্সন (Line Scan-Conversion): দুটি প্রান্তবিন্দুর স্থানাঙ্ক $(x_1, y_1)$ এবং $(x_2, y_2)$ ব্যবহার করে স্ক্রিনের কোন কোন পিক্সেলে রঙ বসালে একটি সরলরেখা ফুটে উঠবে, তা হিসাব করার প্রক্রিয়াকেই Line Drawing Algorithm বলা হয়।

---

Line Equation (লাইনের সমীকরণ)

২ডি স্পেসে একটি সরলরেখার হিসাব করা হয় তার ঢাল-ছেদক সমীকরণ (Slope-Intercept Form) দিয়ে।

ঢাল-ছেদক সমীকরণ

$y = m \cdot x + b$

যেখানে:

• $m$: লাইনের ঢাল (Slope) — যা নির্দেশ করে $X$-এর পরিবর্তনের সাথে $Y$-এর পরিবর্তন কতটা হচ্ছে।
• $b$: Y-ছেদক (y-intercept) — যেখানে রেখাটি Y-অক্ষকে ছেদ করে।

$\Delta x = x_2 - x_1, \quad \Delta y = y_2 - y_1$

$m = \frac{\Delta y}{\Delta x} = \frac{y_2 - y_1}{x_2 - x_1}$

$b = y_1 - m \cdot x_1$

ঢালের ($m$) ভৌত অর্থ

ঢাল $m$ আমাদের বলে দেয় যে $X$-এর মান প্রতি ১ একক বাড়লে $Y$-এর মান কতটা পরিবর্তিত হবে:

$\Delta y = m \cdot \Delta x$

• যদি $m = 1$ হয়: রেখাটি $45^\circ$ কোণে যাবে। ডানে ১ পিক্সেল গেলে উপরেও ১ পিক্সেল যাবে।
• যদি $0 < m < 1$ হয়: রেখাটি ঢালু হবে। ডানে ১ পিক্সেল সরলে $Y$ খুব অল্প ফ্র্যাকশন পরিমাণ বাড়বে।
• যদি $m > 1$ হয়: রেখাটি খাড়া হবে। $X$-এর চেয়ে $Y$ খুব দ্রুত বাড়বে।

---

Basic Line Drawing Algorithm (মৌলিক লাইন অ্যালগরিদম)

সরলরেখা আঁকার সবচেয়ে সহজ পদ্ধতি হলো সরাসরি সমীকরণ $y = mx + b$-তে মান বসিয়ে দেওয়া।

অ্যালগরিদমের ধাপসমূহ

১. ইনপুট গ্রহণ: প্রান্তবিন্দু $(x_1, y_1)$ এবং $(x_2, y_2)$ ইনপুট নেওয়া হয় (ধরি $x_1 < x_2$)। ২. ঢাল ও ছেদক নির্ণয়: $m = \frac{y_2 - y_1}{x_2 - x_1}, \quad b = y_1 - m \cdot x_1$ ৩. $X$-এর মান বাড়ানো: $x = x_1$ থেকে শুরু করে প্রতি ধাপে $x$-কে $+1$ করে বাড়াতে থাকা হয় যতক্ষণ না $x = x_2$ হয়। ৪. $Y$ নির্ণয় ও রাউন্ডিং: $y = m \cdot x + b$ $\text{Plot Pixel at } (x, \text{round}(y))$

অ্যালগরিদম সিউডোকোড

text

Copy

---

Problem with Basic Algorithm (মৌলিক অ্যালগরিদমের সমস্যা)

গাণিতিকভাবে সোজা হলেও বাস্তবে এটি অত্যন্ত ধীর ও অদক্ষ একটি অ্যালগরিদম।

কেন গুণন অপারেশন ক্ষতিকর?

• কম্পিউটারের প্রসেসরে যোগ বা বিয়োগের চেয়ে গুণন (Multiplication) প্রসেস করতে অনেক বেশি ক্লক সাইকেল খরচ হয়।
• প্রতি ফ্রেমে হাজার হাজার লাইন আঁকার সময় প্রতি পিক্সেলে গুণন করা হলে পুরো সিস্টেম স্লো হয়ে যায়।

---

DDA Algorithm (ডিডিএ অ্যালগরিদম)

মৌলিক অ্যালগরিদমের গুণন সমস্যার সমাধান করার জন্যই আবিষ্কৃত হয় Digital Differential Analyzer (DDA) অ্যালগরিদম।

DDA কী?

DDA (Digital Differential Analyzer) হলো একটি ইনক্রিমেন্টাল বা পর্যায়ক্রমিক লাইন অ্যালগরিদম, যা প্রতি ধাপে নতুন করে গুণন না করে পূর্বের পিক্সেল স্থানাঙ্কের সাথে ডিফারেন্স বা পার্থক্য (Increment) যোগ করে কাজ করে।

DDA-এর মূল কনসেপ্ট

প্রতি ধাপে $y = m \cdot x + b$ হিসাব না করে DDA প্রশ্ন করে: "আমি যদি বর্তমান স্থানাঙ্ক $(x_k, y_k)$ জানি, তবে $X$ ১ বাড়লে পরবর্তী স্থানাঙ্ক $(x_{k+1}, y_{k+1})$ কী হবে?"

$y_k = m \cdot x_k + b$

$y_{k+1} = m \cdot (x_k + 1) + b = (m \cdot x_k + b) + m = y_k + m$

DDA অ্যালগরিদম সিউডোকোড

text

Copy

---

DDA Based on Slope (ঢালের ওপর ভিত্তি করে DDA)

যদি লাইনের ঢাল $0 \le m \le 1$ হয়, তবে ওপরের সহজ পদ্ধতিটি কাজ করে। কিন্তু যদি লাইন খাড়া হয় ($m > 1$) বা উল্টো দিকে যায়, তবে $X$-কে ১ করে বাড়ালে লাইনে পিক্সেল বাদ পড়বে।

তাই DDA অ্যালগরিদমে প্রথমে লাইনের মোট স্টেপ সংখ্যা $N$ নির্ধারণ করা হয়:

$N = \max(|\Delta x|, |\Delta y|)$

$\delta x = \frac{\Delta x}{N}, \quad \delta y = \frac{\Delta y}{N}$

ঢালের ৪টি ক্ষেত্র (Four Slope Cases)

---

Advantages of DDA (DDA-এর সুবিধাসমূহ)

মৌলিক পদ্ধতির তুলনায় DDA অ্যালগরিদমের প্রধান সুবিধাগুলো হলো:

---

Problems of DDA (DDA-এর সমস্যাসমূহ)

গতি বাড়ালেও DDA অ্যালগরিদমে কিছু বাধ্যবাধকতা ও ত্রুটি রয়ে গেছে:

১. রাউন্ড-অফ ভুলের ধারাবাহিক পুঞ্জিভবন (Round-off Error Accumulation)

যেহেতু $\delta x$ বা $\delta y$ একটি ভগ্নাংশ (যেমন $m = 0.33333...$), তাই বারবার লুপ ঘুরলে ভগ্নাংশের সামান্য ভুলগুলো জমতে জমতে (drift) ১০০-২০০ পিক্সেল পরের লাইনটি তার আসল পথ থেকে কিছুটা সরে যায়।

২. ফ্ল্লোটিং-পয়েন্ট অপারেশনের বাধ্যবাধকতা

DDA-তে গুণন না থাকলেও $m$ ও $y$-এর জন্য ফ্ল্লোটিং-পয়েন্ট যোগ করতে হয়। যেসব হার্ডওয়্যারে FPU (Floating Point Unit) নেই, সেখানে ফ্ল্লোটিং-পয়েন্ট যোগও কিছুটা ধীরগতির হতে পারে।

৩. প্রতি ধাপে রাউন্ডিং ফাংশন ব্যবহার

প্রতিটি পিক্সেল প্লট করার আগে $y$-এর মানকে পূর্ণসংখ্যায় রূপান্তর করতে round(y) করতে হয়, যা প্রতি পিক্সেলে কিছুটা অতিরিক্ত প্রসেসিং সময় নেয়।

---

Key Difference (পার্থক্য)

পরিশেষে মৌলিক সমীকরণ পদ্ধতি এবং DDA অ্যালগরিদম-এর তুলনামূলক পার্থক্য নিচে সারণীতে দেওয়া হলো: