Chapter 4 of 15

Bresenham’s Line Drawing Algorithm

Fast integer-only scan-conversion using midpoints, decision variables, and incremental East/North-East steps

25 min read

Created ২ সেপ, ২০২৬

Bresenham’s Line Drawing Algorithm (ব্রেসেনহ্যামস লাইন অ্যালগরিদম)

১৯৬২ সালে আইবিএম (IBM)-এ কাজ করার সময় কম্পিউটার বিজ্ঞানী জ্যাক এলটন ব্রেসেনহ্যাম (Jack Elton Bresenham) এমন একটি লাইন অ্যালগরিদম আবিষ্কার করেন যা গ্রাফিক্স রেন্ডারিংয়ের ইতিহাস বদলে দেয়। মৌলিক সমীকরণ পদ্ধতি কিংবা DDA অ্যালগরিদমে যেখানে ফ্র্যাকশন (ফ্ল্লোটিং-পয়েন্ট নম্বর) ও রাউন্ডিংয়ের প্রয়োজন হতো, Bresenham’s Algorithm সেখানে ১০০% নিখুঁত পূর্ণসংখ্যা (Pure Integer Arithmetic) দিয়ে লাইন আঁকতে সক্ষম।

ক্যান্ডিডেট পিক্সেল E ও NE-এর মাঝে মিডপয়েন্ট M-এর চিত্র — ব্রেসেনহ্যাম অ্যালগরিদম পরীক্ষা করে যে প্রকৃত জ্যামিতিক লাইনটি মিডপয়েন্ট M-এর ওপর দিয়ে গেছে নাকি নিচ দিয়ে গেছে।

বাস্তব জীবনের গল্প: ১৯৬২ সালে জ্যাক ব্রেসেনহ্যাম ও আইবিএম প্লটার

১৯৬২ সালে আইবিএম-এ কাজ করার সময় জ্যাক ব্রেসেনহ্যাম যান্ত্রিক ড্রম প্লটার দিয়ে নকশা আঁকার দায়িত্বে ছিলেন। প্লটারের মোটরগুলো কেবল নির্দিষ্ট ঘর ডানে, ওপরে বা কোণাকুণি চলতে পারত। ১৯৬০ দশকের ঢিমেতাল কম্পিউটারে ভগ্নাংশের হিসাব ( $y = mx + b$ ) চালাতে গিয়ে প্রিন্টিং মোটরগুলো থেমে থেমে স্লো হয়ে যেত।

ব্রেসেনহ্যাম তখন Midpoint Decision Test আবিষ্কার করেন: মনে করুন আপনি সীমানা বেড়ার ওপর দিয়ে হাঁটছেন এবং প্রতিটি মোড়ে বেড়ার ঠিক মাঝের মিডপয়েন্ট দেখে সিদ্ধান্ত নিচ্ছেন আপনি কোন দিকে পা ফেলবেন। ভগ্নাংশ ছাড়া কেবল পূর্ণসংখ্যার যোগ-বিয়োগের এই লজিকটি এত দ্রুত কাজ করেছিল যে আজও বিশ্বের সকল GPU চিপে সরাসরি ব্রেসেনহ্যাম অ্যালগরিদম হার্ডওয়্যারে বসানো থাকে!

Efficient Line Drawing Using Incremental Integer Calculations (ইনটিজার গণনার দক্ষতা)

আগের DDA অ্যালগরিদমে প্রতি ধাপে ফ্ল্লোটিং-পয়েন্ট যোগ ( $y = y + m$ ) এবং রাউন্ডিং করতে হতো (round(y))।

কেন পূর্ণসংখ্যার হিসাব এত দ্রুতগতির?

কম্পিউটার হার্ডওয়্যারে (বিশেষ করে GPU প্রসেসরে):

পূর্ণসংখ্যার যোগ ও বিট-শিফটিং: প্রসেসরের মাত্র ১টি ক্লক সাইকেলে সম্পন্ন হয়।
ফ্ল্লোটিং-পয়েন্ট যোগ ও ভাগ: চালাতে প্রসেসরের FPU (Floating Point Unit) লাগে, যা ধীরগতির এবং লম্বা লাইনে ভগ্নাংশের ভুল জমতে জমতে লাইন সরে যায় (Drift ঘটে)।

ব্রেসেনহ্যামের অনন্য আবিষ্কার ছিল: লাইনের গাণিতিক সমীকরণকে এমনভাবে সাজানো যাতে পরবর্তী পিক্সেল নির্বাচন করার পুরো প্রক্রিয়াটি কেবল একটি পূর্ণসংখ্যা সিদ্ধান্ত ভেরিয়েবলের ( $d_k$ ) চিহ্ন (+ বা -) দিয়ে নির্ধারণ করা যায়!

Basic Idea: Unit X-Interval Movement & Candidate Pixels (মূল আইডিয়া)

ধরি, লাইনটি $(x_1, y_1)$ থেকে শুরু হয়ে $(x_2, y_2)$ বিন্দুতে শেষ হয় এবং এর ঢাল হালকা:

$0 \le m \le 1 \quad (\Delta x \ge \Delta y > 0)$

১. প্রধান অক্ষ ধরে ১ একক এগিয়ে যাওয়া: যেহেতু $0 \le m \le 1$ , তাই $X$ -অক্ষ বরাবর মান দ্রুত বাড়ে। আমরা প্রতি ধাপে $X$ -কে ১ একক করে বাড়াই: $x_{p+1} = x_p + 1$

২. দুটি সম্ভাব্য পিক্সেল নির্বাচন (East বনাম North-East): বর্তমান পিক্সেল $P = (x_p, y_p)$ প্লট করার পর, $x_p + 1$ স্থানে আসল জ্যামিতিক রেখাটি দুটি সম্ভাব্য পিক্সেলের মাঝখান দিয়ে যায়:

East ( $E$ ): ঠিক ডানপাশের পিক্সেল: $E = (x_p + 1, y_p)$
North-East ( $NE$ ): ডানপাশের এক ঘর উপরের পিক্সেল: $NE = (x_p + 1, y_p + 1)$

text

Pixel Selection Based on the Midpoint (মিডপয়েন্ট ভিত্তি)

$E$ নাকি $NE$ — কোন পিক্সেলটি আসল রেখার বেশি কাছে অবস্থিত, তা জানার জন্য আমরা $E$ এবং $NE$ -এর ঠিক মাঝের বিন্দু মিডপয়েন্ট ( $M$ ) পরীক্ষা করি।

মিডপয়েন্টের স্থানাঙ্ক

$M = \left(x_p + 1, y_p + \frac{1}{2}\right)$

ইমপ্লিসিট লাইনের সমীকরণ

সরলরেখার সমীকরণ $y = \frac{\Delta y}{\Delta x} x + b$ -কে আমরা সাধারণ সমীকরণ $F(x, y) = 0$ আকারে সাজাতে পারি:

$F(x, y) = A \cdot x + B \cdot y + C = 0$

যেখানে:

$A = \Delta y = y_2 - y_1$
$B = -\Delta x = -(x_2 - x_1)$
$C = \Delta x \cdot b$

$F(x, y)$ -এর জ্যামিতিক বৈশিষ্ট্য

যে কোনো বিন্দু $(x, y)$ -এর জন্য:

$F(x, y) = 0 \implies$ বিন্দুটি সরাসরি লাইনের ওপর অবস্থিত।
$F(x, y) > 0 \implies$ বিন্দুটি লাইনের নিচে অবস্থিত।
$F(x, y) < 0 \implies$ বিন্দুটি লাইনের উপরে অবস্থিত।

Decision Variable ( $d$ ) & Pixel Selection Rules (সিদ্ধান্ত ভেরিয়েবল)

মিডপয়েন্ট $M$ -এর মান ইমপ্লিসিট সমীকরণে বসিয়ে যে সিদ্ধান্ত ভেরিয়েবল $d_k$ পাওয়া যায়, তাকে ২ দিয়ে গুণ করে ভগ্নাংশ মুক্ত করা হয়:

$d_k = 2 \cdot F(M) = 2 \cdot F\left(x_p + 1, y_p + \frac{1}{2}\right)$

২ দিয়ে গুণ করার ফলে $\frac{1}{2}$ ভগ্নাংশটি চলে যায় এবং $d_k$ একটি নিখুঁত পূর্ণসংখ্যা (Integer) হয়ে যায়!

পিক্সেল নির্বাচনের সিদ্ধান্ত নিয়ম

যদি $d_k < 0$ হয়: মিডপয়েন্ট $M$ আসল লাইনের উপরে অবস্থিত। অর্থাৎ আসল লাইনটি East ( $E$ ) পিক্সেলের বেশি কাছে। $\implies$ East ( $E$ ) পছন্দ করুন $\implies (x_p + 1, y_p)$ ।
যদি $d_k \ge 0$ হয়: মিডপয়েন্ট $M$ আসল লাইনের নিচে বা ওপর অবস্থিত। অর্থাৎ আসল লাইনটি North-East ( $NE$ ) পিক্সেলের বেশি কাছে। $\implies$ North-East ( $NE$ ) পছন্দ করুন $\implies (x_p + 1, y_p + 1)$ ।

Calculate the Initial Decision Variable ( $d_0$ ) (প্রাথমিক সিদ্ধান্ত মান)

প্রথম পিক্সেল $(x_1, y_1)$ আঁকার পর প্রথম মিডপয়েন্ট $M_0 = (x_1 + 1, y_1 + 0.5)$ -এ প্রাথমিক সিদ্ধান্ত ভেরিয়েবল $d_0$ পাওয়া যায়:

$d_0 = 2 \cdot F\left(x_1 + 1, y_1 + \frac{1}{2}\right)$

$d_0 = 2\Delta y - \Delta x$

যেহেতু $\Delta x$ এবং $\Delta y$ পিক্সেলের বিয়োগফল (পূর্ণসংখ্যা), তাই $d_0$ একটি পূর্ণসংখ্যা!

Update $d$ Incrementally After Choosing E or NE (ইনক্রিমেন্টাল আপডেট)

প্রতি ধাপে নতুন করে $F(M)$ হিসাব না করে, পূর্বের সিদ্ধান্ত মান $d_k$ -এর সাথে ইনক্রিমেন্ট যোগ করে পরবর্তী $d_{k+1}$ বের করা হয়।

ইন্টারেক্টিভ ব্রেসেনহ্যাম লাইন স্ক্যান-কনভার্সন এক্সপ্লোরার

ব্রেসেনহ্যামের সম্পূর্ণ পূর্ণসংখ্যা ভিত্তিক সিদ্ধান্ত লজিক ধাপে ধাপে পরীক্ষা করুন। মিডপয়েন্ট M, সিদ্ধান্ত ভেরিয়েবল d_k, East ও North-East পিক্সেল নির্বাচন সরাসরি দেখুন।

Interactive Bresenham's Line Scan-Conversion Explorer

⚡ 100% Integer Arithmetic

Presets:

Start Point (x₁, y₁)

End Point (x₂, y₂)

📐 Derived Bresenham Parameters

Δx, Δy12, 6

Initial d₀0

East Inc (ΔE)12

NE Inc (ΔNE)-12

Simulation Step: All13 / 13 pixels plotted

Plotted Pixels Candidate Midpoint M

Step k	Pixel (Xₖ, Yₖ)	Decision dₖ	dₖ < 0 ? Choice	Next dₖ₊₁
0	(2, 2)	0	North-East (NE)	-12
1	(3, 3)	-12	East (E)	0
2	(4, 3)	0	North-East (NE)	-12
3	(5, 4)	-12	East (E)	0
4	(6, 4)	0	North-East (NE)	-12
5	(7, 5)	-12	East (E)	0
6	(8, 5)	0	North-East (NE)	-12
7	(9, 6)	-12	East (E)	0
8	(10, 6)	0	North-East (NE)	-12
9	(11, 7)	-12	East (E)	0
10	(12, 7)	0	North-East (NE)	-12
11	(13, 8)	-12	East (E)	0
12	(14, 8)	0	North-East (NE)	-12

ইনক্রিমেন্ট মান ( $\Delta E$ ও $\Delta NE$ )

১. যদি East ( $E$ ) নেওয়া হয় ( $d_k < 0$ )

পিক্সেল স্থানাঙ্ক হয় $(x_p + 1, y_p)$ ( $Y$ অপরিবর্তিত থাকে)।
পরবর্তী সিদ্ধান্ত মান: $d_{k+1} = d_k + \Delta E$ $\Delta E = 2 \cdot \Delta y$

২. যদি North-East ( $NE$ ) নেওয়া হয় ( $d_k \ge 0$ )

পিক্সেল স্থানাঙ্ক হয় $(x_p + 1, y_p + 1)$ ( $Y$ মান ১ বাড়ে)।
পরবর্তী সিদ্ধান্ত মান: $d_{k+1} = d_k + \Delta NE$ $\Delta NE = 2 \cdot (\Delta y - \Delta x)$

Execution Flow for East ( $E$ ) and North-East ( $NE$ ) Moves (ধাপের সারণী)

East এবং North-East মুভের এক্সিকিউশন তুলনা
প্যারামিটার / স্টেট	East ( $E$ ) মুভ	North-East ( $NE$ ) মুভ
ট্রিগার শর্ত	$d_k < 0$ (মিডপয়েন্ট লাইনের উপরে)	$d_k ge 0$ (মিডপয়েন্ট লাইনের নিচে বা ওপরে)
পরবর্তী X স্থানাঙ্ক	$x_{k+1} = x_k + 1$	$x_{k+1} = x_k + 1$
পরবর্তী Y স্থানাঙ্ক	$y_{k+1} = y_k$ (অপরিবর্তিত)	$y_{k+1} = y_k + 1$ (১ বৃদ্ধি)
সিদ্ধান্ত ইনক্রিমেন্ট	যোগ করুন $Delta E = 2Delta y$	যোগ করুন $Delta NE = 2(Delta y - Delta x)$
হার্ডওয়্যার অপারেশন	১টি ইনটিজার যোগ ( $d + Delta E$ )	১টি ইনটিজার যোগ ( $d + Delta NE$ )

Bresenham’s Line Algorithm & Pseudocode (সিউডোকোড)

ব্রেসেনহ্যাম অ্যালগরিদমে লুপের আগে কন্সট্যান্ট dx, dy, d, incE, এবং incNE হিসাব করে রাখা হয় যাতে লুপে সর্বোচ্চ স্পিড পাওয়া যায়।

স্ট্যান্ডার্ড সিউডোকোড ( $0 \le m \le 1$ )

text

সমস্ত ঢাল ও কোণায় প্রয়োগ (All Slopes & Octants)

যদি লাইনটি খাড়া হয় ( $m > 1$ বা $\Delta y > \Delta x$ ), তবে $Y$ -অক্ষকে মূল অক্ষ ধরে $X$ ও $Y$ -এর ভূমিকা অদলবদল করা হয়। নেগেটিভ ঢালের ক্ষেত্রে $+1$ -এর বদলে step-এর মান $-1$ করা হয়।

বিশ্ববিদ্যালয়ের পরীক্ষার প্রশ্নোত্তর ও পূর্ণাঙ্গ গাণিতিক সমাধান (University Exam Questions & Solutions)

কম্পিউটার গ্রাফিক্স ও অ্যানিমেশন কোর্সের ফাইনাল পরীক্ষায় ব্রেসেনহ্যাম অ্যালগরিদম থেকে যেভাবে উত্তর লিখতে হয় তার পূর্ণাঙ্গ ও গোছানো উপস্থাপনা:

১. থিওরিটিক্যাল প্রশ্ন ও উত্তর (Theoretical Questions & Answers)

প্রশ্ন ১: ব্রেসেনহ্যাম লাইন অ্যালগরিদমের প্রাথমিক সিদ্ধান্ত ভেরিয়েবল d0 = 2Δy - Δx প্রতিপাদন করো।

উত্তর: $(x_1, y_1)$ এবং $(x_2, y_2)$ বিন্দুগামী সরলরেখার ইমপ্লিসিট সমীকরণ: $F(x, y) = \Delta y \cdot x - \Delta x \cdot y + C = 0$ যেখানে $F(x_1, y_1) = 0$ হওয়ায় $C = \Delta x \cdot y_1 - \Delta y \cdot x_1$ ।

প্রথম ধাপ $x = x_1 + 1$ -এ, দুটি সম্ভাব্য পিক্সেল $E(x_1+1, y_1)$ এবং $NE(x_1+1, y_1+1)$ -এর মধ্যবিন্দু $M_0$ : $M_0 = \left(x_1 + 1, \, y_1 + \frac{1}{2}\right)$

ভগ্নাংশ দূর করতে সিদ্ধান্ত প্যারামিটার $d_0 = 2 \cdot F(M_0)$ সংজ্ঞায়িত করা হয়: $d_0 = 2 \cdot \left[ \Delta y(x_1 + 1) - \Delta x\left(y_1 + \frac{1}{2}\right) + C \right]$ $d_0 = 2\left[\Delta y \cdot x_1 - \Delta x \cdot y_1 + C\right] + 2\Delta y - \Delta x$ যেহেতু $\Delta y \cdot x_1 - \Delta x \cdot y_1 + C = F(x_1, y_1) = 0$ , সুতরাং: $d_0 = 2\Delta y - \Delta x$

প্রশ্ন ২: ব্রেসেনহ্যাম অ্যালগরিদমের ইনক্রিমেন্টাল সিদ্ধান্ত মান (ΔE ও ΔNE) প্রতিপাদন করো।

উত্তর: ধরি ধাপ $k$ -তে সিদ্ধান্ত মান $d_k = 2 F\left(x_k + 1, y_k + \frac{1}{2}\right)$ এবং পরবর্তী ধাপ $k+1$ -এ $d_{k+1} = 2 F\left(x_{k+1} + 1, y_{k+1} + \frac{1}{2}\right)$ । বিয়োগ করলে: $\Delta d = d_{k+1} - d_k = 2\Delta y(x_{k+1} - x_k) - 2\Delta x(y_{k+1} - y_k)$ । যেহেতু সর্বদা $x_{k+1} = x_k + 1$ , তাই $(x_{k+1} - x_k) = 1$ :

East ( $E$ ) নির্বাচিত হলে ( $d_k < 0$ ): $y_{k+1} = y_k \implies y_{k+1} - y_k = 0$ $\Delta E = 2\Delta y(1) - 2\Delta x(0) = 2\Delta y \implies d_{k+1} = d_k + 2\Delta y$
North-East ( $NE$ ) নির্বাচিত হলে ( $d_k \ge 0$ ): $y_{k+1} = y_k + 1 \implies y_{k+1} - y_k = 1$ $\Delta NE = 2\Delta y(1) - 2\Delta x(1) = 2(\Delta y - \Delta x) \implies d_{k+1} = d_k + 2(\Delta y - \Delta x)$

প্রশ্ন ৩: DDA এবং Bresenham লাইন অ্যালগরিদমের মধ্যে পার্থক্য লিখো।

উত্তর:

হিসাবের ধরন: DDA প্রতি ধাপে ফ্র্যাকশন বা দশমিক যোগ ( $y = y + m$ ) এবং round(y) ব্যবহার করে; ব্রেসেনহ্যাম ১০০% পূর্ণসংখ্যা (Pure Integer Arithmetic) ব্যবহার করে।
হার্ডওয়্যার স্পিড: ব্রেসেনহ্যামে কেবল পূর্ণসংখ্যার যোগ, বিয়োগ ও বিট-শিফট ( $2\Delta y = \Delta y \ll 1$ ) ব্যবহৃত হয়, যা হার্ডওয়্যারে মাত্র ১ ক্লক সাইকেলে সম্পন্ন হয়।
নির্ভুলতা: লম্বা লাইনে DDA-তে রাউন্ডিং ভুলের ড্র্রিফট (Drift) ঘটে; ব্রেসেনহ্যাম গাণিতিকভাবে ১০০% নিখুঁত।

প্রশ্ন ৪: ব্রেসেনহ্যাম অ্যালগরিদমে কেন মিডপয়েন্ট ফাংশনকে ২ দ্বারা গুণ করা হয়?

উত্তর: মিডপয়েন্ট $M = (x_k + 1, y_k + 0.5)$ -এ ভগ্নাংশ $0.5 = 1/2$ থাকে। ফলে $F(M)$ -এর মান বের করার সময় $-\frac{1}{2}\Delta x$ তৈরি হয়। পুরো সমীকরণকে ২ দ্বারা গুণ ( $d_k = 2 \cdot F(M)$ ) করলে চিহ্নের (+ বা -) কোনো পরিবর্তন ছাড়াই ভগ্নাংশ সম্পূর্ণরূপে দূর হয়ে যায় এবং সকল ভেরিয়েবল খাঁটি পূর্ণসংখ্যায় রূপান্তরিত হয়।

২. বিশ্ববিদ্যালয় ফাইনাল পরীক্ষার গাণিতিক সমস্যা ও পূর্ণাঙ্গ সমাধান

সমস্যা: প্রান্তবিন্দু (20, 10) এবং (30, 18) [১০ম ব্যাচ ফাইনাল পরীক্ষা (10th Batch)]

পরীক্ষার প্রশ্ন [নম্বর: ৪ + ১]

প্রশ্ন: Calculate the intermediate points for the line with end points $(20, 10)$ and $(30, 18)$ using Bresenham line drawing algorithm and draw the line.

(ব্রেসেনহ্যাম লাইন ড্রয়িং অ্যালগরিদম ব্যবহার করে $(20, 10)$ এবং $(30, 18)$ প্রান্তবিন্দুর মধ্যবর্তী পয়েন্টসমূহ গণনা করো এবং লাইনটি অঙ্কন করো।)

ধাপে ধাপে পরীক্ষার সমাধান:

১. প্রদত্ত উপাত্ত (Given Data):

শুরুর প্রান্তবিন্দু: $(x_1, y_1) = (20, 10)$
শেষের প্রান্তবিন্দু: $(x_2, y_2) = (30, 18)$

২. ঢাল ও মূল অক্ষ নির্ধারণ (Slope Calculation):

$\Delta x = x_2 - x_1 = 30 - 20 = 10$
$\Delta y = y_2 - y_1 = 18 - 10 = 8$
ঢাল (Slope): $m = \frac{\Delta y}{\Delta x} = \frac{8}{10} = 0.8$
যেহেতু $0 \le m \le 1$ এবং $x_1 < x_2$ , তাই প্রতি ধাপে $x$ বরাবর ১ একক বৃদ্ধি পাবে ( $x_{k+1} = x_k + 1$ )।

৩. প্রাথমিক সিদ্ধান্ত প্যারামিটার ও ধ্রুবক নির্ণয় (Initial Parameters):

প্রাথমিক সিদ্ধান্ত প্যারামিটার ( $d_0$ ): $d_0 = 2\Delta y - \Delta x = 2(8) - 10 = 16 - 10 = 6$
East ( $E$ ) মুভের জন্য ধ্রুবক: $\Delta E = 2\Delta y = 2 \times 8 = 16$
North-East ( $NE$ ) মুভের জন্য ধ্রুবক: $\Delta NE = 2\Delta y - 2\Delta x = 2(8) - 2(10) = 16 - 20 = -4$

৪. ধাপে ধাপে স্টেট ট্রেস টেবিল (Decision Trace Table):

ব্রেসেনহ্যাম লাইনের ধাপে ধাপে হিসাব সারণী (২০, ১০) থেকে (৩০, ১৮)
ধাপ k	dk	শর্ত / সিদ্ধান্ত	নির্বাচিত মুভ	প্লটকৃত পিক্সেল (x, y)	পরবর্তী dk+1 হিসাব	dk+1
Init	-	-	-	(20, 10)	d0 = 2(8) - 10	6
0	6	dk >= 0	NE (x+1, y+1)	(21, 11)	d1 = 6 + (-4)	2
1	2	dk >= 0	NE (x+1, y+1)	(22, 12)	d2 = 2 + (-4)	-2
2	-2	dk < 0	E (x+1, y)	(23, 12)	d3 = -2 + 16	14
3	14	dk >= 0	NE (x+1, y+1)	(24, 13)	d4 = 14 + (-4)	10
4	10	dk >= 0	NE (x+1, y+1)	(25, 14)	d5 = 10 + (-4)	6
5	6	dk >= 0	NE (x+1, y+1)	(26, 15)	d6 = 6 + (-4)	2
6	2	dk >= 0	NE (x+1, y+1)	(27, 16)	d7 = 2 + (-4)	-2
7	-2	dk < 0	E (x+1, y)	(28, 16)	d8 = -2 + 16	14
8	14	dk >= 0	NE (x+1, y+1)	(29, 17)	d9 = 14 + (-4)	10
9	10	dk >= 0	NE (x+1, y+1)	(30, 18)	শেষ বিন্দু অর্জিত (x = x2)	-

৫. মধ্যবর্তী বিন্দুসমূহ (Intermediate Points): $(20, 10)$ এবং $(30, 18)$ প্রান্তবিন্দুর মধ্যবর্তী নির্ণেয় পয়েন্টসমূহ হলো: $\mathbf{(21, 11), (22, 12), (23, 12), (24, 13), (25, 14), (26, 15), (27, 16), (28, 16), (29, 17)}$

৬. পিক্সেল গ্রিডে লাইনের চিত্রাঙ্কন (Draw the Line):

সমস্যা ২: মিডপয়েন্ট লাইন অ্যালগরিদম ব্যাখ্যা ও (3, 5) থেকে (7, 9) বিন্দুর ট্রেস [১১তম ব্যাচ ফাইনাল পরীক্ষা (11th Batch)]

পরীক্ষার প্রশ্ন [নম্বর: ৭]

প্রশ্ন: Explain the Midpoint line drawing algorithm and trace the algorithm for the given points $(3, 5)$ to $(7, 9)$ .

(মিডপয়েন্ট লাইন ড্রয়িং অ্যালগরিদম ব্যাখ্যা করো এবং প্রদত্ত বিন্দু $(3, 5)$ থেকে $(7, 9)$ এর জন্য অ্যালগরিদমটি ট্রেস করো।)

ধাপে ধাপে পরীক্ষার সমাধান:

১ম অংশ: মিডপয়েন্ট লাইন অ্যালগরিদমের তাত্ত্বিক ব্যাখ্যা [৩.৫ নম্বর] ১. মূল জ্যামিতিক ধারণা: $0 \le m \le 1$ ঢালের ক্ষেত্রে প্রধান $X$ -অক্ষ বরাবর প্রতি ধাপে ১ একক বৃদ্ধি পায় ( $x_{k+1} = x_k + 1$ )। বর্তমান পিক্সেল $P_k(x_k, y_k)$ প্লট করার পর পরবর্তী ধাপে আসল জ্যামিতিক রেখাটি দুটি সম্ভাব্য পিক্সেলের মাঝ দিয়ে যায়:

East ( $E$ ): $(x_k + 1, y_k)$
North-East ( $NE$ ): $(x_k + 1, y_k + 1)$

২. মিডপয়েন্ট টেস্ট: $E$ ও $NE$ -এর ঠিক মাঝের মিডপয়েন্ট ( $M$ ) বিবেচনা করা হয়: $M = \left(x_k + 1, \, y_k + \frac{1}{2}\right)$ সরলরেখার ইমপ্লিসিট সমীকরণ $F(x, y) = \Delta y \cdot x - \Delta x \cdot y + C = 0$ -এ $M$ -কে বসিয়ে পূর্ণসংখ্যা সিদ্ধান্ত ভেরিয়েবল $d_k = 2 \cdot F(M)$ সংজ্ঞায়িত করা হয়।

৩. সিদ্ধান্ত ও পিক্সেল নির্বাচন বিধি:

যদি $d_k < 0$ হয়: মিডপয়েন্ট $M$ আসল রেখার উপরে অবস্থিত $\implies$ রেখাটি $E$ পিক্সেলের বেশি কাছে $\implies$ $E(x_k + 1, y_k)$ নির্বাচিত হবে এবং $d_{k+1} = d_k + 2\Delta y$ ।
যদি $d_k \ge 0$ হয়: মিডপয়েন্ট $M$ আসল রেখার নিচে বা ওপরে অবস্থিত $\implies$ রেখাটি $NE$ পিক্সেলের বেশি কাছে $\implies$ $NE(x_k + 1, y_k + 1)$ নির্বাচিত হবে এবং $d_{k+1} = d_k + 2(\Delta y - \Delta x)$ ।

৪. সূচনা মান: প্রারম্ভিক বিন্দু $(x_1, y_1)$ থেকে প্রাথমিক সিদ্ধান্ত মান $d_0 = 2\Delta y - \Delta x$ ।

২য় অংশ: (3, 5) থেকে (7, 9) বিন্দুর জন্য গাণিতিক স্টেট ট্রেস [৩.৫ নম্বর]

১. প্রদত্ত উপাত্ত:

শুরুর প্রান্তবিন্দু: $(x_1, y_1) = (3, 5)$
শেষের প্রান্তবিন্দু: $(x_2, y_2) = (7, 9)$

২. ডেল্টা ও ঢাল নির্ণয়:

$\Delta x = x_2 - x_1 = 7 - 3 = 4$
$\Delta y = y_2 - y_1 = 9 - 5 = 4$
ঢাল: $m = \frac{\Delta y}{\Delta x} = \frac{4}{4} = 1.0$
যেহেতু $0 \le m \le 1$ , তাই প্রতি ধাপে $x$ বরাবর ১ একক বাড়বে ( $x_{k+1} = x_k + 1$ )।

৩. প্রাথমিক প্যারামিটার ও ইনক্রিমেন্ট ধ্রুবক:

প্রাথমিক সিদ্ধান্ত প্যারামিটার ( $d_0$ ): $d_0 = 2\Delta y - \Delta x = 2(4) - 4 = 8 - 4 = \mathbf{4}$
East ইনক্রিমেন্ট ( $\Delta E$ ): $\Delta E = 2\Delta y = 2(4) = 8$
North-East ইনক্রিমেন্ট ( $\Delta NE$ ): $\Delta NE = 2\Delta y - 2\Delta x = 2(4) - 2(4) = \mathbf{0}$

৪. ধাপে ধাপে স্টেট ট্রেস সারণী:

মিডপয়েন্ট অ্যালগরিদমের স্টেট ট্রেস সারণী (৩, ৫) থেকে (৭, ৯)
ধাপ k	dk	শর্ত	নির্বাচিত মুভ	প্লটকৃত বিন্দু (x, y)	পরবর্তী dk+1 হিসাব	dk+1
Init	-	-	-	(3, 5)	d0 = 2(4) - 4	4
0	4	dk >= 0	NE (x+1, y+1)	(4, 6)	d1 = 4 + 0	4
1	4	dk >= 0	NE (x+1, y+1)	(5, 7)	d2 = 4 + 0	4
2	4	dk >= 0	NE (x+1, y+1)	(6, 8)	d3 = 4 + 0	4
3	4	dk >= 0	NE (x+1, y+1)	(7, 9)	শেষ বিন্দুতে পৌঁছাল (x = x2)	-

৫. মধ্যবর্তী বিন্দুসমূহ (Intermediate Points): $(3, 5)$ এবং $(7, 9)$ এর মধ্যবর্তী বিন্দুগুলো হলো: $\mathbf{(4, 6), (5, 7), (6, 8)}$

৬. সম্পূর্ণ রেখার বিন্দুসমূহ: $(3, 5) \longrightarrow (4, 6) \longrightarrow (5, 7) \longrightarrow (6, 8) \longrightarrow (7, 9)$

(নোট: যেহেতু ঢাল $m = 1$ , তাই রেখাটি নিখুঁত ৪৫° কোণের কর্ণের রেখা এবং প্রতিটি ধাপেই North-East ( $NE$ ) দিকে সরাসরি কোণাকুণি ধাবিত হয়।)

সংক্ষেপ

Bresenham’s Algorithm ফ্ল্লোটিং-পয়েন্ট, ভাগ ও রাউন্ডিং পুরোপুরি বাদ দিয়ে ১০০% ইনটিজার যোগ ও বিয়োগ দিয়ে কাজ করে।
লুপের প্রতি ধাপে একটি সাধারণ ইনটিজার শর্ত ( $d_k < 0$ ) দিয়ে East ( $E$ ) এবং North-East ( $NE$ ) পিক্সেলের মধ্যে একটি বেছে নেওয়া হয়।
সিদ্ধান্ত ভেরিয়েবলটি ইনক্রিমেন্টাল কন্সট্যান্ট $\Delta E = 2\Delta y$ এবং $\Delta NE = 2(\Delta y - \Delta x)$ দিয়ে খুব দ্রুত আপডেট করা হয়।

Chapter 4 of 15

Bresenham’s Line Drawing Algorithm

Fast integer-only scan-conversion using midpoints, decision variables, and incremental East/North-East steps

25 min read

Created ২ সেপ, ২০২৬

Bresenham’s Line Drawing Algorithm (ব্রেসেনহ্যামস লাইন অ্যালগরিদম)

বাস্তব জীবনের গল্প: ১৯৬২ সালে জ্যাক ব্রেসেনহ্যাম ও আইবিএম প্লটার

Efficient Line Drawing Using Incremental Integer Calculations (ইনটিজার গণনার দক্ষতা)

কেন পূর্ণসংখ্যার হিসাব এত দ্রুতগতির?

কম্পিউটার হার্ডওয়্যারে (বিশেষ করে GPU প্রসেসরে):

পূর্ণসংখ্যার যোগ ও বিট-শিফটিং: প্রসেসরের মাত্র ১টি ক্লক সাইকেলে সম্পন্ন হয়।
ফ্ল্লোটিং-পয়েন্ট যোগ ও ভাগ: চালাতে প্রসেসরের FPU (Floating Point Unit) লাগে, যা ধীরগতির এবং লম্বা লাইনে ভগ্নাংশের ভুল জমতে জমতে লাইন সরে যায় (Drift ঘটে)।

Basic Idea: Unit X-Interval Movement & Candidate Pixels (মূল আইডিয়া)

ধরি, লাইনটি $(x_1, y_1)$ থেকে শুরু হয়ে $(x_2, y_2)$ বিন্দুতে শেষ হয় এবং এর ঢাল হালকা:

$0 \le m \le 1 \quad (\Delta x \ge \Delta y > 0)$

East ( $E$ ): ঠিক ডানপাশের পিক্সেল: $E = (x_p + 1, y_p)$
North-East ( $NE$ ): ডানপাশের এক ঘর উপরের পিক্সেল: $NE = (x_p + 1, y_p + 1)$

text

Pixel Selection Based on the Midpoint (মিডপয়েন্ট ভিত্তি)

মিডপয়েন্টের স্থানাঙ্ক

$M = \left(x_p + 1, y_p + \frac{1}{2}\right)$

ইমপ্লিসিট লাইনের সমীকরণ

$F(x, y) = A \cdot x + B \cdot y + C = 0$

যেখানে:

$A = \Delta y = y_2 - y_1$
$B = -\Delta x = -(x_2 - x_1)$
$C = \Delta x \cdot b$

$F(x, y)$ -এর জ্যামিতিক বৈশিষ্ট্য

যে কোনো বিন্দু $(x, y)$ -এর জন্য:

$F(x, y) = 0 \implies$ বিন্দুটি সরাসরি লাইনের ওপর অবস্থিত।
$F(x, y) > 0 \implies$ বিন্দুটি লাইনের নিচে অবস্থিত।
$F(x, y) < 0 \implies$ বিন্দুটি লাইনের উপরে অবস্থিত।

Decision Variable ( $d$ ) & Pixel Selection Rules (সিদ্ধান্ত ভেরিয়েবল)

$d_k = 2 \cdot F(M) = 2 \cdot F\left(x_p + 1, y_p + \frac{1}{2}\right)$

পিক্সেল নির্বাচনের সিদ্ধান্ত নিয়ম

যদি $d_k < 0$ হয়: মিডপয়েন্ট $M$ আসল লাইনের উপরে অবস্থিত। অর্থাৎ আসল লাইনটি East ( $E$ ) পিক্সেলের বেশি কাছে। $\implies$ East ( $E$ ) পছন্দ করুন $\implies (x_p + 1, y_p)$ ।
যদি $d_k \ge 0$ হয়: মিডপয়েন্ট $M$ আসল লাইনের নিচে বা ওপর অবস্থিত। অর্থাৎ আসল লাইনটি North-East ( $NE$ ) পিক্সেলের বেশি কাছে। $\implies$ North-East ( $NE$ ) পছন্দ করুন $\implies (x_p + 1, y_p + 1)$ ।

Calculate the Initial Decision Variable ( $d_0$ ) (প্রাথমিক সিদ্ধান্ত মান)

$d_0 = 2 \cdot F\left(x_1 + 1, y_1 + \frac{1}{2}\right)$

$d_0 = 2\Delta y - \Delta x$

Update $d$ Incrementally After Choosing E or NE (ইনক্রিমেন্টাল আপডেট)

ইন্টারেক্টিভ ব্রেসেনহ্যাম লাইন স্ক্যান-কনভার্সন এক্সপ্লোরার

Interactive Bresenham's Line Scan-Conversion Explorer

⚡ 100% Integer Arithmetic

Presets:

Start Point (x₁, y₁)

End Point (x₂, y₂)

📐 Derived Bresenham Parameters

Δx, Δy12, 6

Initial d₀0

East Inc (ΔE)12

NE Inc (ΔNE)-12

Simulation Step: All13 / 13 pixels plotted

Plotted Pixels Candidate Midpoint M

Step k	Pixel (Xₖ, Yₖ)	Decision dₖ	dₖ < 0 ? Choice	Next dₖ₊₁
0	(2, 2)	0	North-East (NE)	-12
1	(3, 3)	-12	East (E)	0
2	(4, 3)	0	North-East (NE)	-12
3	(5, 4)	-12	East (E)	0
4	(6, 4)	0	North-East (NE)	-12
5	(7, 5)	-12	East (E)	0
6	(8, 5)	0	North-East (NE)	-12
7	(9, 6)	-12	East (E)	0
8	(10, 6)	0	North-East (NE)	-12
9	(11, 7)	-12	East (E)	0
10	(12, 7)	0	North-East (NE)	-12
11	(13, 8)	-12	East (E)	0
12	(14, 8)	0	North-East (NE)	-12

ইনক্রিমেন্ট মান ( $\Delta E$ ও $\Delta NE$ )

১. যদি East ( $E$ ) নেওয়া হয় ( $d_k < 0$ )

পিক্সেল স্থানাঙ্ক হয় $(x_p + 1, y_p)$ ( $Y$ অপরিবর্তিত থাকে)।
পরবর্তী সিদ্ধান্ত মান: $d_{k+1} = d_k + \Delta E$ $\Delta E = 2 \cdot \Delta y$

২. যদি North-East ( $NE$ ) নেওয়া হয় ( $d_k \ge 0$ )

পিক্সেল স্থানাঙ্ক হয় $(x_p + 1, y_p + 1)$ ( $Y$ মান ১ বাড়ে)।
পরবর্তী সিদ্ধান্ত মান: $d_{k+1} = d_k + \Delta NE$ $\Delta NE = 2 \cdot (\Delta y - \Delta x)$

Execution Flow for East ( $E$ ) and North-East ( $NE$ ) Moves (ধাপের সারণী)

East এবং North-East মুভের এক্সিকিউশন তুলনা
প্যারামিটার / স্টেট	East ( $E$ ) মুভ	North-East ( $NE$ ) মুভ
ট্রিগার শর্ত	$d_k < 0$ (মিডপয়েন্ট লাইনের উপরে)	$d_k ge 0$ (মিডপয়েন্ট লাইনের নিচে বা ওপরে)
পরবর্তী X স্থানাঙ্ক	$x_{k+1} = x_k + 1$	$x_{k+1} = x_k + 1$
পরবর্তী Y স্থানাঙ্ক	$y_{k+1} = y_k$ (অপরিবর্তিত)	$y_{k+1} = y_k + 1$ (১ বৃদ্ধি)
সিদ্ধান্ত ইনক্রিমেন্ট	যোগ করুন $Delta E = 2Delta y$	যোগ করুন $Delta NE = 2(Delta y - Delta x)$
হার্ডওয়্যার অপারেশন	১টি ইনটিজার যোগ ( $d + Delta E$ )	১টি ইনটিজার যোগ ( $d + Delta NE$ )

Bresenham’s Line Algorithm & Pseudocode (সিউডোকোড)

স্ট্যান্ডার্ড সিউডোকোড ( $0 \le m \le 1$ )

text

সমস্ত ঢাল ও কোণায় প্রয়োগ (All Slopes & Octants)

বিশ্ববিদ্যালয়ের পরীক্ষার প্রশ্নোত্তর ও পূর্ণাঙ্গ গাণিতিক সমাধান (University Exam Questions & Solutions)

১. থিওরিটিক্যাল প্রশ্ন ও উত্তর (Theoretical Questions & Answers)

East ( $E$ ) নির্বাচিত হলে ( $d_k < 0$ ): $y_{k+1} = y_k \implies y_{k+1} - y_k = 0$ $\Delta E = 2\Delta y(1) - 2\Delta x(0) = 2\Delta y \implies d_{k+1} = d_k + 2\Delta y$
North-East ( $NE$ ) নির্বাচিত হলে ( $d_k \ge 0$ ): $y_{k+1} = y_k + 1 \implies y_{k+1} - y_k = 1$ $\Delta NE = 2\Delta y(1) - 2\Delta x(1) = 2(\Delta y - \Delta x) \implies d_{k+1} = d_k + 2(\Delta y - \Delta x)$

প্রশ্ন ৩: DDA এবং Bresenham লাইন অ্যালগরিদমের মধ্যে পার্থক্য লিখো।

উত্তর:

হিসাবের ধরন: DDA প্রতি ধাপে ফ্র্যাকশন বা দশমিক যোগ ( $y = y + m$ ) এবং round(y) ব্যবহার করে; ব্রেসেনহ্যাম ১০০% পূর্ণসংখ্যা (Pure Integer Arithmetic) ব্যবহার করে।
হার্ডওয়্যার স্পিড: ব্রেসেনহ্যামে কেবল পূর্ণসংখ্যার যোগ, বিয়োগ ও বিট-শিফট ( $2\Delta y = \Delta y \ll 1$ ) ব্যবহৃত হয়, যা হার্ডওয়্যারে মাত্র ১ ক্লক সাইকেলে সম্পন্ন হয়।
নির্ভুলতা: লম্বা লাইনে DDA-তে রাউন্ডিং ভুলের ড্র্রিফট (Drift) ঘটে; ব্রেসেনহ্যাম গাণিতিকভাবে ১০০% নিখুঁত।

২. বিশ্ববিদ্যালয় ফাইনাল পরীক্ষার গাণিতিক সমস্যা ও পূর্ণাঙ্গ সমাধান

সমস্যা: প্রান্তবিন্দু (20, 10) এবং (30, 18) [১০ম ব্যাচ ফাইনাল পরীক্ষা (10th Batch)]

পরীক্ষার প্রশ্ন [নম্বর: ৪ + ১]

প্রশ্ন: Calculate the intermediate points for the line with end points $(20, 10)$ and $(30, 18)$ using Bresenham line drawing algorithm and draw the line.

ধাপে ধাপে পরীক্ষার সমাধান:

১. প্রদত্ত উপাত্ত (Given Data):

শুরুর প্রান্তবিন্দু: $(x_1, y_1) = (20, 10)$
শেষের প্রান্তবিন্দু: $(x_2, y_2) = (30, 18)$

২. ঢাল ও মূল অক্ষ নির্ধারণ (Slope Calculation):

$\Delta x = x_2 - x_1 = 30 - 20 = 10$
$\Delta y = y_2 - y_1 = 18 - 10 = 8$
ঢাল (Slope): $m = \frac{\Delta y}{\Delta x} = \frac{8}{10} = 0.8$
যেহেতু $0 \le m \le 1$ এবং $x_1 < x_2$ , তাই প্রতি ধাপে $x$ বরাবর ১ একক বৃদ্ধি পাবে ( $x_{k+1} = x_k + 1$ )।

৩. প্রাথমিক সিদ্ধান্ত প্যারামিটার ও ধ্রুবক নির্ণয় (Initial Parameters):

প্রাথমিক সিদ্ধান্ত প্যারামিটার ( $d_0$ ): $d_0 = 2\Delta y - \Delta x = 2(8) - 10 = 16 - 10 = 6$
East ( $E$ ) মুভের জন্য ধ্রুবক: $\Delta E = 2\Delta y = 2 \times 8 = 16$
North-East ( $NE$ ) মুভের জন্য ধ্রুবক: $\Delta NE = 2\Delta y - 2\Delta x = 2(8) - 2(10) = 16 - 20 = -4$

৪. ধাপে ধাপে স্টেট ট্রেস টেবিল (Decision Trace Table):

ব্রেসেনহ্যাম লাইনের ধাপে ধাপে হিসাব সারণী (২০, ১০) থেকে (৩০, ১৮)
ধাপ k	dk	শর্ত / সিদ্ধান্ত	নির্বাচিত মুভ	প্লটকৃত পিক্সেল (x, y)	পরবর্তী dk+1 হিসাব	dk+1
Init	-	-	-	(20, 10)	d0 = 2(8) - 10	6
0	6	dk >= 0	NE (x+1, y+1)	(21, 11)	d1 = 6 + (-4)	2
1	2	dk >= 0	NE (x+1, y+1)	(22, 12)	d2 = 2 + (-4)	-2
2	-2	dk < 0	E (x+1, y)	(23, 12)	d3 = -2 + 16	14
3	14	dk >= 0	NE (x+1, y+1)	(24, 13)	d4 = 14 + (-4)	10
4	10	dk >= 0	NE (x+1, y+1)	(25, 14)	d5 = 10 + (-4)	6
5	6	dk >= 0	NE (x+1, y+1)	(26, 15)	d6 = 6 + (-4)	2
6	2	dk >= 0	NE (x+1, y+1)	(27, 16)	d7 = 2 + (-4)	-2
7	-2	dk < 0	E (x+1, y)	(28, 16)	d8 = -2 + 16	14
8	14	dk >= 0	NE (x+1, y+1)	(29, 17)	d9 = 14 + (-4)	10
9	10	dk >= 0	NE (x+1, y+1)	(30, 18)	শেষ বিন্দু অর্জিত (x = x2)	-

৬. পিক্সেল গ্রিডে লাইনের চিত্রাঙ্কন (Draw the Line):

সমস্যা ২: মিডপয়েন্ট লাইন অ্যালগরিদম ব্যাখ্যা ও (3, 5) থেকে (7, 9) বিন্দুর ট্রেস [১১তম ব্যাচ ফাইনাল পরীক্ষা (11th Batch)]

পরীক্ষার প্রশ্ন [নম্বর: ৭]

প্রশ্ন: Explain the Midpoint line drawing algorithm and trace the algorithm for the given points $(3, 5)$ to $(7, 9)$ .

ধাপে ধাপে পরীক্ষার সমাধান:

East ( $E$ ): $(x_k + 1, y_k)$
North-East ( $NE$ ): $(x_k + 1, y_k + 1)$

৩. সিদ্ধান্ত ও পিক্সেল নির্বাচন বিধি:

যদি $d_k < 0$ হয়: মিডপয়েন্ট $M$ আসল রেখার উপরে অবস্থিত $\implies$ রেখাটি $E$ পিক্সেলের বেশি কাছে $\implies$ $E(x_k + 1, y_k)$ নির্বাচিত হবে এবং $d_{k+1} = d_k + 2\Delta y$ ।
যদি $d_k \ge 0$ হয়: মিডপয়েন্ট $M$ আসল রেখার নিচে বা ওপরে অবস্থিত $\implies$ রেখাটি $NE$ পিক্সেলের বেশি কাছে $\implies$ $NE(x_k + 1, y_k + 1)$ নির্বাচিত হবে এবং $d_{k+1} = d_k + 2(\Delta y - \Delta x)$ ।

২য় অংশ: (3, 5) থেকে (7, 9) বিন্দুর জন্য গাণিতিক স্টেট ট্রেস [৩.৫ নম্বর]

১. প্রদত্ত উপাত্ত:

শুরুর প্রান্তবিন্দু: $(x_1, y_1) = (3, 5)$
শেষের প্রান্তবিন্দু: $(x_2, y_2) = (7, 9)$

২. ডেল্টা ও ঢাল নির্ণয়:

$\Delta x = x_2 - x_1 = 7 - 3 = 4$
$\Delta y = y_2 - y_1 = 9 - 5 = 4$
ঢাল: $m = \frac{\Delta y}{\Delta x} = \frac{4}{4} = 1.0$
যেহেতু $0 \le m \le 1$ , তাই প্রতি ধাপে $x$ বরাবর ১ একক বাড়বে ( $x_{k+1} = x_k + 1$ )।

৩. প্রাথমিক প্যারামিটার ও ইনক্রিমেন্ট ধ্রুবক:

প্রাথমিক সিদ্ধান্ত প্যারামিটার ( $d_0$ ): $d_0 = 2\Delta y - \Delta x = 2(4) - 4 = 8 - 4 = \mathbf{4}$
East ইনক্রিমেন্ট ( $\Delta E$ ): $\Delta E = 2\Delta y = 2(4) = 8$
North-East ইনক্রিমেন্ট ( $\Delta NE$ ): $\Delta NE = 2\Delta y - 2\Delta x = 2(4) - 2(4) = \mathbf{0}$

৪. ধাপে ধাপে স্টেট ট্রেস সারণী:

মিডপয়েন্ট অ্যালগরিদমের স্টেট ট্রেস সারণী (৩, ৫) থেকে (৭, ৯)
ধাপ k	dk	শর্ত	নির্বাচিত মুভ	প্লটকৃত বিন্দু (x, y)	পরবর্তী dk+1 হিসাব	dk+1
Init	-	-	-	(3, 5)	d0 = 2(4) - 4	4
0	4	dk >= 0	NE (x+1, y+1)	(4, 6)	d1 = 4 + 0	4
1	4	dk >= 0	NE (x+1, y+1)	(5, 7)	d2 = 4 + 0	4
2	4	dk >= 0	NE (x+1, y+1)	(6, 8)	d3 = 4 + 0	4
3	4	dk >= 0	NE (x+1, y+1)	(7, 9)	শেষ বিন্দুতে পৌঁছাল (x = x2)	-

৬. সম্পূর্ণ রেখার বিন্দুসমূহ: $(3, 5) \longrightarrow (4, 6) \longrightarrow (5, 7) \longrightarrow (6, 8) \longrightarrow (7, 9)$

সংক্ষেপ

Bresenham’s Algorithm ফ্ল্লোটিং-পয়েন্ট, ভাগ ও রাউন্ডিং পুরোপুরি বাদ দিয়ে ১০০% ইনটিজার যোগ ও বিয়োগ দিয়ে কাজ করে।
লুপের প্রতি ধাপে একটি সাধারণ ইনটিজার শর্ত ( $d_k < 0$ ) দিয়ে East ( $E$ ) এবং North-East ( $NE$ ) পিক্সেলের মধ্যে একটি বেছে নেওয়া হয়।
সিদ্ধান্ত ভেরিয়েবলটি ইনক্রিমেন্টাল কন্সট্যান্ট $\Delta E = 2\Delta y$ এবং $\Delta NE = 2(\Delta y - \Delta x)$ দিয়ে খুব দ্রুত আপডেট করা হয়।

Bresenham’s Line Drawing Algorithm (ব্রেসেনহ্যামস লাইন অ্যালগরিদম)

Efficient Line Drawing Using Incremental Integer Calculations (ইনটিজার গণনার দক্ষতা)

কেন পূর্ণসংখ্যার হিসাব এত দ্রুতগতির?

Basic Idea: Unit X-Interval Movement & Candidate Pixels (মূল আইডিয়া)

Pixel Selection Based on the Midpoint (মিডপয়েন্ট ভিত্তি)

মিডপয়েন্টের স্থানাঙ্ক

ইমপ্লিসিট লাইনের সমীকরণ

F(x,y)F(x, y)F(x,y)-এর জ্যামিতিক বৈশিষ্ট্য

Decision Variable (ddd) & Pixel Selection Rules (সিদ্ধান্ত ভেরিয়েবল)

Calculate the Initial Decision Variable (d0d_0d0​) (প্রাথমিক সিদ্ধান্ত মান)

Update ddd Incrementally After Choosing E or NE (ইনক্রিমেন্টাল আপডেট)

Interactive Bresenham's Line Scan-Conversion Explorer

ইনক্রিমেন্ট মান (ΔE\Delta EΔE ও ΔNE\Delta NEΔNE)

১. যদি East (EEE) নেওয়া হয় (dk<0d_k < 0dk​<0)

২. যদি North-East (NENENE) নেওয়া হয় (dk≥0d_k \ge 0dk​≥0)

Execution Flow for East (EEE) and North-East (NENENE) Moves (ধাপের সারণী)

Bresenham’s Line Algorithm & Pseudocode (সিউডোকোড)

স্ট্যান্ডার্ড সিউডোকোড (0≤m≤10 \le m \le 10≤m≤1)

সমস্ত ঢাল ও কোণায় প্রয়োগ (All Slopes & Octants)

বিশ্ববিদ্যালয়ের পরীক্ষার প্রশ্নোত্তর ও পূর্ণাঙ্গ গাণিতিক সমাধান (University Exam Questions & Solutions)

১. থিওরিটিক্যাল প্রশ্ন ও উত্তর (Theoretical Questions & Answers)

২. বিশ্ববিদ্যালয় ফাইনাল পরীক্ষার গাণিতিক সমস্যা ও পূর্ণাঙ্গ সমাধান

সমস্যা: প্রান্তবিন্দু (20, 10) এবং (30, 18) [১০ম ব্যাচ ফাইনাল পরীক্ষা (10th Batch)]

সমস্যা ২: মিডপয়েন্ট লাইন অ্যালগরিদম ব্যাখ্যা ও (3, 5) থেকে (7, 9) বিন্দুর ট্রেস [১১তম ব্যাচ ফাইনাল পরীক্ষা (11th Batch)]

Bresenham’s Line Drawing Algorithm (ব্রেসেনহ্যামস লাইন অ্যালগরিদম)

Efficient Line Drawing Using Incremental Integer Calculations (ইনটিজার গণনার দক্ষতা)

কেন পূর্ণসংখ্যার হিসাব এত দ্রুতগতির?

Basic Idea: Unit X-Interval Movement & Candidate Pixels (মূল আইডিয়া)

Pixel Selection Based on the Midpoint (মিডপয়েন্ট ভিত্তি)

মিডপয়েন্টের স্থানাঙ্ক

ইমপ্লিসিট লাইনের সমীকরণ

F(x,y)F(x, y)F(x,y)-এর জ্যামিতিক বৈশিষ্ট্য

Decision Variable (ddd) & Pixel Selection Rules (সিদ্ধান্ত ভেরিয়েবল)

Calculate the Initial Decision Variable (d0d_0d0​) (প্রাথমিক সিদ্ধান্ত মান)

Update ddd Incrementally After Choosing E or NE (ইনক্রিমেন্টাল আপডেট)

Interactive Bresenham's Line Scan-Conversion Explorer

ইনক্রিমেন্ট মান (ΔE\Delta EΔE ও ΔNE\Delta NEΔNE)

১. যদি East (EEE) নেওয়া হয় (dk<0d_k < 0dk​<0)

২. যদি North-East (NENENE) নেওয়া হয় (dk≥0d_k \ge 0dk​≥0)

Execution Flow for East (EEE) and North-East (NENENE) Moves (ধাপের সারণী)

Bresenham’s Line Algorithm & Pseudocode (সিউডোকোড)

স্ট্যান্ডার্ড সিউডোকোড (0≤m≤10 \le m \le 10≤m≤1)

সমস্ত ঢাল ও কোণায় প্রয়োগ (All Slopes & Octants)

বিশ্ববিদ্যালয়ের পরীক্ষার প্রশ্নোত্তর ও পূর্ণাঙ্গ গাণিতিক সমাধান (University Exam Questions & Solutions)

১. থিওরিটিক্যাল প্রশ্ন ও উত্তর (Theoretical Questions & Answers)

২. বিশ্ববিদ্যালয় ফাইনাল পরীক্ষার গাণিতিক সমস্যা ও পূর্ণাঙ্গ সমাধান

সমস্যা: প্রান্তবিন্দু (20, 10) এবং (30, 18) [১০ম ব্যাচ ফাইনাল পরীক্ষা (10th Batch)]

সমস্যা ২: মিডপয়েন্ট লাইন অ্যালগরিদম ব্যাখ্যা ও (3, 5) থেকে (7, 9) বিন্দুর ট্রেস [১১তম ব্যাচ ফাইনাল পরীক্ষা (11th Batch)]

$F(x, y)$ -এর জ্যামিতিক বৈশিষ্ট্য

Decision Variable ( $d$ ) & Pixel Selection Rules (সিদ্ধান্ত ভেরিয়েবল)

Calculate the Initial Decision Variable ( $d_0$ ) (প্রাথমিক সিদ্ধান্ত মান)

Update $d$ Incrementally After Choosing E or NE (ইনক্রিমেন্টাল আপডেট)

ইনক্রিমেন্ট মান ( $\Delta E$ ও $\Delta NE$ )

১. যদি East ( $E$ ) নেওয়া হয় ( $d_k < 0$ )

২. যদি North-East ( $NE$ ) নেওয়া হয় ( $d_k \ge 0$ )

Execution Flow for East ( $E$ ) and North-East ( $NE$ ) Moves (ধাপের সারণী)

স্ট্যান্ডার্ড সিউডোকোড ( $0 \le m \le 1$ )

$F(x, y)$ -এর জ্যামিতিক বৈশিষ্ট্য

Decision Variable ( $d$ ) & Pixel Selection Rules (সিদ্ধান্ত ভেরিয়েবল)

Calculate the Initial Decision Variable ( $d_0$ ) (প্রাথমিক সিদ্ধান্ত মান)

Update $d$ Incrementally After Choosing E or NE (ইনক্রিমেন্টাল আপডেট)

ইনক্রিমেন্ট মান ( $\Delta E$ ও $\Delta NE$ )

১. যদি East ( $E$ ) নেওয়া হয় ( $d_k < 0$ )

২. যদি North-East ( $NE$ ) নেওয়া হয় ( $d_k \ge 0$ )

Execution Flow for East ( $E$ ) and North-East ( $NE$ ) Moves (ধাপের সারণী)

স্ট্যান্ডার্ড সিউডোকোড ( $0 \le m \le 1$ )