دعونا نبني محرك رسومات ثلاثية الأبعاد: تنقيط الخطوط الخطية والدوائر

() translation by (you can also view the original English article)

مرحباً ، هذا هو الجزء الرابع من سلسلتنا على محركات الرسومات ثلاثية الأبعاد. في هذه المرة ، سنقوم بتغطية التنقيط: عملية أخذ شكل موصوف بواسطة صيغ رياضية وتحويله إلى صورة على شاشتك.

تلميح: تم إنشاء جميع المفاهيم الموجودة في هذه المقالة خارج الفصول الدراسية التي أنشأناها في المشاركات الثلاث الأولى ، لذا تأكد من التحقق منها أولاً.

خلاصة

فيما يلي مراجعة للصفوف التي قمنا بها حتى الآن:


Point Class
{
  Variables:
		num tuple[3]; //(x,y,z)
	Operators:
		Point AddVectorToPoint(Vector);
		Point SubtractVectorFromPoint(Vector);
		Vector SubtractPointFromPoint(Point);
		Null SetPointToPoint(Point);
	Functions:
		drawPoint; //draw a point at its position tuple
}

Vector Class
{
	Variables:
		num tuple[3]; //(x,y,z)
	Operators:
		Vector AddVectorToVector(Vector);
		Vector SubtractVectorFromVector(Vector);
		Vector RotateXY(degrees);
		Vector RotateYZ(degrees);
		Vector RotateXZ(degrees);
		Vector Scale(s0,s1,s2); //receives a scaling 3-tuple, returns the scaled vector
}

Camera Class
{
	Vars:
		int minX, maxX;
		int minY, maxY;
		int minZ, maxZ;
		array objectsInWorld; //an array of all existent objects
	Functions:
		null drawScene(); //draws all needed objects to the screen
}

يمكنك الاطلاع على نموذج البرنامج من الجزء الثالث من السلسلة لمعرفة كيفية عملهم معًا.

الآن ، دعونا نلقي نظرة على بعض الأشياء الجديدة!

التنقيط

التنقيط (أو البكسلة، إذا كنت ترغب في ذلك) هو عملية أخذ شكل موصوف في تنسيق رسومات متجه (أو في حالتنا ، رياضياً) وتحويلها إلى صورة نقطية (حيث يتم احتواء الشكل على بنية بكسل).

نظرًا لأن الرياضيات ليست دائمًا بالدقة التي نحتاجها لاستخدامها في رسومات الكمبيوتر ، يجب أن نستخدم الخوارزميات لتلائم الأشكال التي تصفها على الشاشة الصحيحة. على سبيل المثال ، يمكن أن تقع نقطة على التنسيق \\ ((3.2 ، 4.6) \\) في الرياضيات ، ولكن عندما نعرضها ، يجب علينا دفعها إلى \\ ((3 ، 5) \\) حتى يمكن وضعها في هيكل بكسل لشاشتنا.

سيكون لكل نوع من الأشكال التي نقوم بتنقيطها خوارزمية خاصة بها للقيام بذلك. لنبدأ بأحد الأشكال الأكثر بساطة للتنقيط: مقطع الخط.

سطر القطعة

Source: http://en.wikipedia.org/wiki/File:Bresenham.svg — المصدر: http://en.wikipedia.org/wiki/File:Bresenham.svg

تعتبر المقاطع الخطية واحدة من أبسط الأشكال التي يمكن رسمها ، ولذلك غالبًا ما تكون واحدة من أول الأشياء التي يتم تغطيتها في أي فئة من أشكال الهندسة. يتم تمثيلها بنقطتين متميزتين (نقطة بداية واحدة ونقطة نهاية واحدة) ، والخط الذي يربط بين الاثنين. تسمى الخوارزمية الأكثر شيوعًا في تنقيط مقطع الخط خوارزمية Bresenham.

خطوة بخطوة ، تعمل خوارزمية Bresenham على النحو التالي:

استلم نقطة البداية ونقطة النهاية لقطعة الخط كمدخل.
تحديد الاتجاه مقطع خط بتحديد خصائصه \(dx\) و \(dy\) (\ (dx = x_ {1}-x_ {0} \)، \ (dy = y_ {1}-y_ {0} \)).
تحديد sx ،sy, و ، سنلقي نظرة على بعض من أفضل تقويم وجدولة التطبيقات المتاحة عبر الإنترنت.
تقريب كل نقطة في جزء السطر إلى البكسل الموجود أعلاه أو أسفله.

قبل أن ننفذ خوارزمية Bresenham ، دعنا نجمع فئة من الشرائح الأساسية لاستخدامها في محركنا:


LineSegment Class
{
	Variables:
		int startX, startY; //the starting point of our line segment
		int endX, endY; //the ending point of our line segment
	Function:
		array returnPointsInSegment; //all points lying on this line segment
}

إذا كنت تريد إجراء تحويل على صف LineSegment الجديد ، فكل ما عليك فعله هو تطبيق التحويل الذي اخترته على نقاط البداية والنهاية لـ LineSegment ثم وضعها مرة أخرى في الفصل. ستتم معالجة جميع النقاط التي تقع بين النقاط عندما يتم رسم LineSegment نفسه ، حيث تتطلب خوارزمية Bresenham نقطة البداية والنهاية فقط للعثور على كل نقطة لاحقة.

لكي تتناسب فئة LineSegment مع محركنا الحالي ، لا يمكننا أن نمتلك بالفعل دالة draw() مضمنة في الفصل ، ولهذا السبب اخترت استخدام وظيفة returnPointsInSegment بدلاً من ذلك. ستقوم هذه الدالة بإرجاع مصفوفة من كل نقطة موجودة داخل مقطع الخط ، مما يسمح لنا برسم الجزء الخطي وإعدامه بالشكل المناسب.

تبدو الدالة returnPointsInSegment() تشبه إلى حد ما هذا (في JavaScript):


function returnPointsInSegment()
{
	//create a list to store all of the line segment's points in
	var pointArray = new Array();
	//set this function's variables based on the class's starting and ending points
	var x0 = this.startX;
	var y0 = this.startY;
	var x1 = this.endX;
	var y1 = this.endY;
	//define vector differences and other variables required for Bresenham's Algorithm
	var dx = Math.abs(x1-x0);
	var dy = Math.abs(y1-y0);
	var sx = (x0 & x1) ? 1 : -1; //step x
	var sy = (y0 & y1) ? 1 : -1; //step y
	var err = dx-dy; //get the initial error value
	//set the first point in the array
	pointArray.push(new Point(x0,y0));

	//Main processing loop
	while(!((x0 == x1) && (y0 == y1)))
	{
		var e2 = err * 2; //hold the error value
		//use the error value to determine if the point should be rounded up or down
 		if(e2 => -dy)
		{
			err -= dy;
			x0 += sx;
		}
		if(e2 < dx)
		{
			err += dx;
			y0 += sy;
		}
		//add the new point to the array
		pointArray.push(new Point(x0, y0));
	}
	return pointArray;
}

تتمثل أسهل طريقة لإضافة شرائح الخط في فئة الكاميرا في إضافة بنية بسيطة if كانت مشابهة لما يلي:


	//loop through array of objects
	if (class type == Point)
	{
		//do our current rendering code
	}
	else if (class type == LineSegment)
	{
		var segmentArray = LineSegment.returnPointsInSegment();
		//loop through points in the array, drawing and culling them as we have previously
	}

هذا هو كل ما تحتاجه للحصول على صفك الدراسي الأول وتشغيله! إذا كنت ترغب في معرفة المزيد عن الجوانب الأكثر تقنية لخوارزمية Bresenham (خصوصًا أقسام الأخطاء) ، يمكنك الاطلاع على مقالة Wikipedia عليه.

الدوائر

Source: http://en.wikipedia.org/wiki/File:Bresenham_circle.svg — المصدر: http://en.wikipedia.org/wiki/File:Bresenham_circle.svg

تكون عملية تنقيط الدائرة أكثر صعوبة قليلاً من تنقيط جزء من الخط ، ولكن ليس كثيرًا. سنستخدم خوارزمية دائرة المنتصف لنفعل كل رفعنا الثقيل ، وهو امتداد لخوارزمية Bresenham التي سبق ذكرها. على هذا النحو ، فإنه يتبع خطوات مشابهة لتلك المذكورة أعلاه ، مع بعض الاختلافات الطفيفة.

تعمل الخوارزمية الجديدة لدينا على النحو التالي:

استلم نقطة مركزية ونصف دائرة.
اضبط النقاط في كل اتجاه أساسي
دورة من خلال كل من الأرباع ، رسم الأقواس الخاصة بهم

سيكون فصل الدائرة لدينا مشابهًا جدًا لفئة شرائح الخط ، ويبحث عن شيء من هذا القبيل:


Circle Class
{
	Variables:
		int centerX, centerY; //the center point of our circle
		int radius; //the radius of our circle
	Function:
		array returnPointsInCircle; //all points within this Circle
}

تعمل وظيفة returnPointsInCircle() الخاصة بنا بالطريقة نفسها التي تعمل بها وظيفة صف LineSegment ، حيث تقوم بإرجاع مجموعة من النقاط حتى تتمكن الكاميرا من تقديمها وإعدامها حسب الحاجة. يتيح ذلك لمحركنا التعامل مع مجموعة متنوعة من الأشكال ، مع وجود تغييرات طفيفة فقط مطلوبة لكل منها.

هذا ما ستبدو عليه وظيفة returnPointsInCircle() الخاصة بنا (في JavaScript):


function returnPointsInCircle()
{
	//store all of the circle's points in an array
	var pointArray = new Array();
	//set up the values needed for the algorithm
	var f = 1 - radius; //used to track the progress of the drawn circle (since its semi-recursive)
	var ddFx = 1; //step x
	var ddFy = -2 * this.radius; //step y
	var x = 0;
	var y = this.radius;

	//this algorithm doesn't account for the farthest points, 
	//so we have to set them manually
	pointArray.push(new Point(this.centerX, this.centerY + this.radius));
	pointArray.push(new Point(this.centerX, this.centerY - this.radius));
	pointArray.push(new Point(this.centerX + this.radius, this.centerY));
	pointArray.push(new Point(this.centerX - this.radius, this.centerY));

	while(x < y) {
	 	if(f >= 0) {
			y--;
			ddFy += 2;
			f += ddFy;
		}
		x++;
		ddFx += 2;
		f += ddFx;

		//build our current arc
		pointArray.push(new Point(x0 + x, y0 + y));
		pointArray.push(new Point(x0 - x, y0 + y));
		pointArray.push(new Point(x0 + x, y0 - y));
		pointArray.push(new Point(x0 - x, y0 - y));
		pointArray.push(new Point(x0 + y, y0 + x));
		pointArray.push(new Point(x0 - y, y0 + x));
		pointArray.push(new Point(x0 + y, y0 - x));
		pointArray.push(new Point(x0 - y, y0 - x));
	}

	return pointArray;
}

الآن ، نقوم فقط بإضافة عبارة if أخرى إلى حلقة الرسم الرئيسية الخاصة بنا ، وهذه الدوائر متكاملة تمامًا!

إليك كيفية ظهور حلقة الرسم المحدثة:


	//loop through array of objects
	if(class type == point)
	{
		//do our current rendering code
	}
	else if(class type == LineSegment)
	{
		var segmentArray = LineSegment.returnPointsInSegment();
		//loop through points in the array, drawing and culling them as we have previously
	}
	else if(class type == Circle)
	{
		var circleArray = Circle.returnPointsInCircle();
		//loop through points in the array, drawing and culling them as we have previously
	}

الآن بعد أن أصبح لدينا صفوف جديدة بعيدة عن الطريق ، دعونا نجعل شيء ما!

ماستر النقطية

برنامجنا سيكون بسيطا هذه المرة. عندما ينقر المستخدم على الشاشة ، سنقوم برسم دائرة تكون نقطة مركزها هي النقطة التي تم النقر عليها ، ويكون نصف قطرها رقمًا عشوائيًا.

دعونا نلقي نظرة على الكود:


main{
	//setup for your favorite Graphics API here
	//setup for keyboard input (may not be required) here

	var camera = new Camera(); //create an instance of the camera class
	camera.objectsInWorld[]; //create 100 object spaces within the camera's array

	//set the camera's view space
	camera.minX = 0;
	camera.maxX = screenWidth;
	camera.minY = 0;
	camera.maxY = screenHeight;
	camera.minZ = 0;
	camera.maxZ = 100;

	while(key != esc) {
		if(mouseClick) {
			//create a new circle
			camera.objectsInWorld.push(new Circle(mouse.x,mouse.y,random(3,10));
			//render everything in the scene
			camera.drawScene();
		}
	}
}

مع أي حظ ، يجب أن تكون الآن قادرًا على استخدام محرك محدّث لجذب بعض الدوائر الرائعة.

استنتاج

الآن وبعد أن أصبح لدينا بعض ميزات التنقيط الأساسية في محركنا ، يمكننا في النهاية البدء في رسم بعض الأشياء المفيدة على الشاشة! لا شيء معقد للغاية بعد ، ولكن إذا أردت ، يمكنك تجميع بعض الأرقام العصا ، أو شيء من هذا القبيل.

في المشاركة التالية ، سنلقي نظرة أخرى على التنقيط. - سنقوم في هذه المرة فقط بإعداد فئتين أخريين لاستخدامهما في محركنا: مثلثات وأربعة أجيال. ترقب!