الدرس الثاني Line Scan Conversion

و الآن سنتحدث عن الطريقة الثانية و التي هي:

Digital Differential Analyzer المشهورة بإسم DDA:

إن هذه الطريقة تعتمد على التزايدي بحيث في كل مرة أريد إستخراج النقط الجديدة على الخط المراد رسمه

أعتمد على ما النقطة التي سبقتها، و هنا إعتمادنا على الفارق ما بين كل نقطة من هذه النقاط التي سترسم لتكون

الخط المراد، و الآن فلنقل بأن الخط النقط التي معي لها موقع Xi و Yi و النقط التي تليها X i+1 و Y i+1 لذا

نستطيع أن نقول بأن m = DeltaY/DeltaX بحيث أن DeltaY = Y i+1 - Yi و DeltaX = X i+1 - Xi

و لذا نستطيع أن نقول:

و هنا نتعامل بذات الطريقة التي سبقت، فنرى إن كانت m=<1 فإننا نبدأ ب X=X1 و من ثمّ بإعتبار أن X2 > X1

و Y=Y1 و من ثمّ نثبت DeltaX = 1 و بعدها نقوم بزيادة X و نستخرج في كل مرة من المعادلة Y الجديدة بإستخدام

و نتوقف عند الوصول إلى X = X2

أما في حالة m > 1 فإننا نعكس العملية، بحيث أننا نعمل على زيادة Y و نستخرج من المعادلة X الجديدة

فنضع X=X1 و Y=Y1 و DeltaY = 1 بما أننا نعمل على أساس أن الفارق هو واحد بين النقط Y و YNew الجديدة

و نحصل في كل مرة على X بإستخدام:

و نتوقف عند الوصول إلى Y = Y2

و لكن في هذه الطريقة أيضا لم نصل إلى افضل سرعة الأفضل لو كانت كل الحسابات Integer أعدادا صحيحة

و لكن هنا لدينا عنليات حسابية أهون من التي قبلها و أسرع لأنها تحصل على النقاط دون وجود ضرب float

و لكن بقي لدينا الجمع float و الذي نحتاجه لنحصل على دقة أفضل في إيجاد كل نقطة و لكن هناك خطأ قد يحدث

في هذه المعادلة لمحدودية الأرقام بعد الفاصلة مما يسبب للنقطة خروجها عن مسارها الطبيعي على الخط في حالة

الخطوط الطويلة

أما الآن فسنتحدث عن الطريقة الثالثة و التي هي أهم طريقة و المستخدمة نظرا لسرعتها و إستخدامها لعمليات

حسابية كلها Integer و كما تعلمون بأن عمليات Integer أسرع العمليات في الكومبيوتر نظرا لإستخدام floating point

في العمليات الحسابية التي فيها Decimal Numbers و التي تزيد من تكلفة القيام بحساب هذه العمليات لل CPU

ميزة هذه الطريقة أنها ذات نتيجة دقيقة و تعتمد على جمع و طرح و ضرب ب 2 أرقام صحيحة Integer Numbers

و ستقولون لي بأن فيها عملية ضرب و لكن أنظروا الميزة هنا أن عملية الضرب ب 2 هي عملية إزاحة بسيطة لل Binary

و الآن فلنبدأ الشرح:

يا إخوتي كما تعلمون بأن الشاشة هي عبارة عن مجموعة من Pixels و التي هي مجتمعة تتكون الصورة التي نراها

و إن أردنا رسم خط على هذه الشاشة فإننا نقوم بإختيار مجموعة Pixels التي أحتاجها لرسم الخط عبر تلوينها باللون

الذي أريده ليكون لون الخط المرسوم، بمعنى آخر أن الخط الذي نراه عباره عن مجموعة من Pixels ملونة باللون الذي

نريده و لهذا السبب كلها إزدادت Resolution في الشاشة فإن الصور و المؤثرات الحركية على الشاشة تكون أملس

و أجمل و خالية من الشوائب أكثر نظرا لزيادة عدد Pixels في الصورة أو المشهد.

ففي هذه الطريقة سنقوم بالإعتماد على النقطة الموجودة في الوسط في داخل كل Pixel و التي سنعتمد عليها في

هذه Algorithm و لنفترض بأن Slope الذي لدينا هو ما بين

0 < m < 1

و لدينا نقطة البداية P1 و التي من خلالها سنمر و نقوم بإختيار Pixels الأنسب لرسم الخط المرجو من اليسار إلى اليمين

وصولا إلى النقطة الثانية و التي هي P2 كما هو مبين في الصورة:

و الآن علينا بالعمل على الصورة لفهم الأحداث، سنقوم بتسمية النقطة التي نصل إليها من خلال رسمنا Xi

و التي بعدها هي X i+1 و كما نرى بأننا نمشي من اليسار إلى اليمين فالنقطة التي نحن عليها الآن لنفرض

بأنها Xi و لذا فالنقطة التالية هي X i+1 و لكن في حالة Y فعلينا الإختيار ما هي النقطة التي يتوجب علينا إختيارها

فإما النقطة التي على ذات المستوى للتي قبلها و إما النقطة التي فوقها كما هو مبين في الصورة، و نحن نعلم

ذاتيا بالنقطة الموجودة في وسط كل Pixel فقمنا بتسمية النقطة العليا ب T كبيرة و النقطة التي تحتها ب S كبيرة

و هنا سنرمز إلى هذه المفهوم أيضا عند قولنا Yi و التي نعني فيها البقاء على ذات المستوى من النقطة

التي سبقتها، و Y i+1 و التي هي النقطة التي فوقها

و الآن كما لاحظنا في الصورة فإننا قمنا بتعويض s - t ثم ضربها ب DeltaX قنحصل على معادلة قمنا بتسميتها di

و لكي نحصل على d i+1 فقط قمنا بوضع مكان Xi وضعنا X i+1 و مكان Yi وضعنا Y i+1

و من ثمّ قمنا بطرح d i+1 - di و بهذه العملية كسبنا الخلاص من constant و الذي هو رقم ثابت ظهر في التعويض

أنظر إلى الصورة لترى هذا في سطر الطرح لل di و d i+1

و الآن كما نعلم بأن X i+1 هي ذاتها Xi + 1 فنقوم بتعويض هذه في المعادلة التي حصلنا عليها في النهاية

و بعد هذا كله نرسل di إلى الجهة الأخرى فنحصل على التالي:

d i+1 = di + 2*DeltaY - 2*DeltaX ( Y i+1 - Yi)

و كما نرى لقد بقيت Y i+1 و Yi في المعادلة و التي نرى بأنه إن كانت s - t أكبر من صفر فإننا سنختار

Pixel T لأنها الأقرب و لكن نستطيع أيضا معرفة هذا من di فإن كانت أكبر من صفر أيضا نختار T

أوليست di هي DeltaX مضروبة ب s - t من المعادلة التي إفترضناها في الأعلى

و الآن كما نرى فإن إختيار T يعني بأن Y i+1 تساوي Yi + 1

و عند التعويض نحصل على:

d i+1 = di + 2 * (DeltaY - DeltaX)

و أما إن كانت di أصغر من صفر فإننا سنقوم بإختيار Pixel S

و مما يعني بأن Y i+1 تساوي Yi لأننا سنبقى على ذات المستوى، و عندها سنحصل على التالي:

d i+1 = di + 2*DeltaY

و من هذا كله فإننا سنستخلص ما يلي:

If di >= 0
d i+1 = di + 2 * (DeltaY - DeltaX)

If di < 0
d i+1 = di + 2*DeltaY

و لكن كي نكمل العمل علينا بإستخراج النقطة الأولى من هذا كله و هو التعويض في النقطة الأولى في s - t المضروبة ب DeltaX

لنستخرج d1 منها:

d1 = DeltaX * ( 2*m *(X1 + 1) + 2*b - 2*Y1 - 1)
d1 = DeltaX * 2*( m*X1 + b - y1) + 2*m -1

BUT m*X1 + b - y1 = 0

d1 = (2*DeltaY) - DeltaX

و الخلاصة الآن في كتابة Bresenham's Algorithm لرسم خط ما بين نقطة P1 و التي لها X1 و Y1

و نقطة P2 و التي لها X2 و Y2 كإحداثيات، مع X2 أكبر من X1 و أن m هي ما بين 1 و 0

X1 < X2

0 < m < 1

فإننا سنقدر على كتابة الكود البرمجي على الشكل التالي:

int x=X1 , y=Y1;
int dx = X2 - X1, dy = Y2 - Y1, dT = 2*(dy - dx) , dS = 2*dy;
int d = 2*dy - dx;
setPixel(x,y);
while( x < X2 ){
	x++;
	if( d < 0){
		d = d + dS;
	}
	else{
		y++;
		d = d + dT;
	}
	setPixel( x , y );
}

هل رأيتم كم هي رائعة هذه Algorithm فإنها تعمل على أعداد صحيحة فقط و أنظروا إلى أدائها و سرعتها

بالنسبة للطرق الأخرى و التي ذكرناها سابقا

و إليكم ملف هذا الدرس على PDF File

Line_Scan_Conversion.pdf

تمام اخي ،

اتمني ان تضع التطبيق و لو حتي علي الدوس و استخدام مكتبة صغيره للرسم ووضع فيها تجاربك و التكملة في شرح الرسم بالحاسب .

لا أعلم و لكني وجدت بأن كتابة هذه Algorithms سهل عند فهمها و لو وضعت الكود لعملها كاملا

فلن يضطر أحد لفهم عملها و يقوم بعمل copy و paste و يستخدم الكود دون فهم محتواه كيف يعمل

فالإبداع في رأيي ينصب في معرفة كيفية عمل الكود و ليس في إستخدامه

ولكن إرتأيت إلى وضع الكود في حالة واحدة و التي عندما تكون slope أصغر من واحد:

slope = (Y2-Y1) / (X2-X1)
Where slope <= 1

و هذا هو الكود الذي قمت بكتابته:

void drawLineEquation(int X1, int Y1, int X2, int Y2){
	float slope=(float)(Y2-Y1)/(X2-X1);
	float b=Y1 - (slope*X1);
	if(slope <= 1){
		for(int x=X1; x<X2; x++){
			glBegin(GL_POINTS);
				glVertex2f(x , ((slope*x)+b));
			glEnd();
			glFlush();
			Sleep(10);
		}
	}
}

فإنه يقوم بأخذ النقطتان اللتان سيوصلان بخط بينهما، و بعدها نقوم بحساب slope و نحسب b

و التي هي حدة إعتراض الخط لإعتمادنا على هذه معادلة الخط العادية:

Y = slope * X + b

و بعدها نتأكد من أن slope أصغر أو يساوي واحد و التي كما شرحنا سابقا فإننا في هذه الحالة نقوم

بزيادة X و من ثمّ إستخراج Y من المعادلة و لذا كما رأينا بأن فإننا نمر على كل X في الخط من خلال for loop

و من بعدها إستخدم glBegin و أرسلت لها الأمر الذي يعني بأن الرسم المرجوّ من النقاط هو رسمها نقطة نقطة

و من ثم أستخدم glVertex2f لرسم النقاط و التي كما تلاحظون بأنني أستخرج Y داخلها من خلال المعادلة السابقة

و إستخدامي ل Sleep هو لإبطاء سرعة loop بحيث نقدر على رؤية الخط و هو يرسم

و لاحظوا وضعي ل glFlush بحيث كلّ نقطة ترسم أقوم بإرسالها إلى الشاشة مباشرة

و بهذا الشكل أرى الخط و هو يرسم نقطة نقطة

void drawDDA(int X1, int Y1, int X2, int Y2){
	float slope=(float)(Y2-Y1)/(X2-X1);
	if(slope <= 1){
		glBegin(GL_POINTS);
			glVertex2f(X1 , Y1);
		glEnd();
		glFlush();
		Sleep(10);
		float y=Y1;
		for(int x=X1+1; x<X2; x++){
			y+=slope;
			glBegin(GL_POINTS);
				glVertex2f(x , y);
			glEnd();
			glFlush();
			Sleep(10);
		}
	}
}

و كما شرحنا في السابق في حالة slope التي قمنا بإختيارها فإننا نمر على كل X و نستخرج Y من خلال:

NextY = OldY + slope * DeltaX

و التي نقوم من خلالها بإستخراج Y الجديدة من Y القديمة عبر زيادة slope مضروبا ب DeltaX

و لكن كما رأينا فإن الفارق بي كل X على الخط هو واحد ما هو في for loop

و لذا فإن Y للنقطة تكون عبر

NewY = OldY  + slope

void drawBresenhamAlgorithm(int X1, int Y1, int X2, int Y2){
	float slope=(float)(Y2-Y1)/(X2-X1);
	if(slope <= 1){
		int x=X1 , y=Y1;
		int dx = X2 - X1, dy = Y2 - Y1, dT = 2*(dy - dx) , dS = 2*dy;
		int d = 2*dy - dx;
		glBegin(GL_POINTS);
			glVertex2f(x , y);
		glEnd();
		glFlush();
		Sleep(10);
		while( x < X2 ){
			x++;
			if( d < 0){
				d = d + dS;
			}
			else{
				y++;
				d = d + dT;
			}
			glBegin(GL_POINTS);
				glVertex2f(x , y);
			glEnd();
			glFlush();
			Sleep(10);
		}
	}
}

و كما رأينا علينا إستخراج المعادلات المطلوبة d الأولى و DeltaX و DeltaY و الأرقام التي ستجمع على d

في الحالتين لل d عندما تكون أكبر من صفر أو أصغر من صفر و كما فهمنا من الشرح السابق

في كل مرة نزيد X علينا التأكد من d

فعندما تكون d أصغر من صفر فإن النقطة سترسم على المستوى ذاته

أما في حالة d أكبر من صفر فإن النقطة التالية سترتفع بزيادة Y واحدا

أتمنى أن يكون الشرح وافيا

و هذا البرنامج الذي قمت به عند تشغيله سيقوم برسم ثلاثة خطوط كل خط يستخدم أحد هذه Algorithms

سترسم الخطوط شيئا فشيئا لترى مراحل رسم الخط:

فالخط الأحمر Line Equation

الخط الأخضر DDA

الخط الأزرق Bresenham's

و هذا هو الكود:

Line_Scan_Conversion.cpp

و هذه صورة النتيجة:

بصراحة أود الإعتذار لتوقفي لفترة عن إكمال الدروس و التي إن شاء الله سأعود لإكمالها حالما تسنح لي الفرصة

فأتمنى منكم العذر فأنا في السماستر الأخير و علي ضغط كتير كتير من مواد و مشاريع غير مشروع التخرج

و كنت سأكمل حاليا Circle Scan Conversion و سأضع الدرس على PDF File و هو باللغة الإنجليزية

و سأقوم بشرحه تفصيلياً مثل Line Scan Conversion في أول فرصة إن شاء الله

لا تنسوني من دعوة صالحة

Circle_Scan_Conversion.pdf

بارك الله فيك ..

أنت ناقشت أحد أهم المواضيع ( على الاقل بالنسبة لدي ..) رسم دائرة + خط مستقيم .. باستخدام الخوارزميات .

سيتم تثبيت الموضوع .. ونحن ننتظر الدروس الجديدة .. بعد تخرجك ان شاء الله

بارك الله فيكم