Advertisement
  1. Game Development
  2. Programming

Let's Build a 3D Graphics Engine: Rasterizing Triangles and Quads

Scroll to top
Read Time: 9 min
This post is part of a series called Let’s Build a 3D Graphics Software Engine.
Let's Build a 3D Graphics Engine: Rasterizing Line Segments and Circles
Let's Build a 3D Graphics Engine: Colors

Welcome to the fifth part of our Let's Build a 3D Graphics Engine series!  This time, we will be building two new classes for rasterizing: one for triangles and one for basic quadrilaterals.  Then, we are going to take pieces from those two classes and put together a final, almighty polygon class.

Tip: This is a part of a series, so if you want to get the most out of it make sure that you read the other tutorials leading up to this one.


Recap

We've built quite a bit into our engine so far!  Here's what we have:

  • Point and Vector classes (the building blocks of our engine).
  • Transformation functions for our points.
  • A Camera class (sets our viewport, and culls points outside of the screen).
  • Two classes for rasterizing (line segments and circles).

Here is a quick reference for all of the classes we've built:

1
Point Class
2
{
3
	Variables:
4
		num tuple[3]; //(x,y,z)

5
	Operators:
6
		Point AddVectorToPoint(Vector);
7
		Point SubtractVectorFromPoint(Vector);
8
		Vector SubtractPointFromPoint(Point);
9
		Null SetPointToPoint(Point);
10
	Functions:
11
		drawPoint; //draw a point at its position tuple

12
}
13
14
Vector Class
15
{
16
	Variables:
17
		num tuple[3]; //(x,y,z)

18
	Operators:
19
		Vector AddVectorToVector(Vector);
20
		Vector SubtractVectorFromVector(Vector);
21
		Vector RotateXY(degrees);
22
		Vector RotateYZ(degrees);
23
		Vector RotateXZ(degrees);
24
		Vector Scale(s0,s1,s2); //receives a scaling 3-tuple, returns the scaled vector

25
}
26
27
Camera Class
28
{
29
	Vars:
30
		int minX, maxX;
31
		int minY, maxY;
32
		int minZ, maxZ;
33
		array objectsInWorld; //an array of all existent objects

34
	Functions:
35
		null drawScene(); //draws all needed objects to the screen

36
}
37
38
LineSegment Class
39
{
40
	Variables:
41
		int startX, startY; //the starting point of our line segment

42
		int endX, endY; //the ending point of our line segment

43
	Function:
44
		array returnPointsInSegment; //all points lying on this line segment

45
}

We are going to rely heavily on the LineSegment class to create our Triangle and Quad classes, so make sure to refamiliarize yourself with it before moving on.


Rasterizing Triangles

512px-Euler_diagram_of_triangle_types512px-Euler_diagram_of_triangle_types512px-Euler_diagram_of_triangle_types

Putting together a Triangle class for the engine is fairly simple, especially since the LineSegment class is where all of our rasterization is actually going to take place. This class will allow three points to be set, and will draw a line segment between them to make the completed triangle.  

A basic outline of the class could look like this:

1
Triangle Class
2
{
3
	Variables:
4
		//co-ordinates for the three points of our triangles

5
		int Point1X, Point1Y; 
6
		int Point2X, Point2Y;
7
		int Point3X, Point3Y;
8
	Function:
9
		array returnPointsInTriangle; //all points within the triangle's perimeter

10
}

For the sake of standards, we are going to assume that the three points declared within our triangle are in a clockwise pattern.  

Using our LineSegment class, then, we can set up our returnPointsInTriangle() function like this:

1
function returnPointsInTriangle()
2
{
3
	array PointsToReturn; //create a temporary array to hold the triangle's points

4
5
	//Create three line segments and store their points in the array

6
	PointsToReturn.push(new LineSegment(this.Point1X, this.Point1Y, this.Point2X, this.Point2Y));
7
	PointsToReturn.push(new LineSegment(this.Point2X, this.Point2Y, this.Point3X, this.Point3Y));
8
	PointsToReturn.push(new LineSegment(this.Point3X, this.Point3Y, this.Point1X, this.Point1Y));
9
10
	return(PointsToReturn);
11
}

Not too bad, right? Since we already have a lot of the work being done within our LineSegment class, we only have to continue stringing them together to create more complex shapes. This makes it easy to create ever more complicated polygons on the screen, simply by adding on more LineSegments (and storing more points within the class itself).

Next, let's take a look at how we can add more points to this system by creating a square class.


Getting Squared Away

300px-Six_Quadrilaterals

Putting together a class to handle quadrilaterals only involves adding a few extra things to our Triangle class.  With another set of points, our quadrilateral class would look like this:

1
Quad Class
2
{
3
	Variables:
4
		int Point1X, Point1Y; //co-ordinates for the four points of our quadrilateral

5
		int Point2X, Point2Y;
6
		int Point3X, Point3Y;
7
		int Point4X, Point4Y;
8
9
 	Function:
10
		 array returnPointsInQuad; //return all points within the quadrilateral

11
}

Then, we just add in the additional line segment to the returnPointsInQuad function, like so:

1
function returnPointsInQuad()
2
{
3
	array PointsToReturn; //create a temporary array to hold the quad's points

4
5
	//Create four line segments and store their points in the array

6
	PointsToReturn.push(new LineSegment(this.Point1X, this.Point1Y, this.Point2X, this.Point2Y));
7
	PointsToReturn.push(new LineSegment(this.Point2X, this.Point2Y, this.Point3X, this.Point3Y));
8
	PointsToReturn.push(new LineSegment(this.Point3X, this.Point3Y, this.Point4X, this.Point4Y));
9
	PointsToReturn.push(new LineSegment(this.Point4X, this.Point4Y, this.Point1X, this.Point1Y));
10
11
	return(PointsToReturn);
12
}

While building new classes like this is pretty straight-forward, there is a much easier way to encapsulate all of our polygons into one class. By using the magic of loops and arrays, we can put together a polygon class that could make almost any size shape that you could want!


Where Have All the Polys-Gon?

To create an ever expanding polygon class, we need to do two things. The first is to move all of our points into an array, which would give us a class outline similar to something like this:

1
Polygon Class
2
{
3
	Variables:
4
		array Points; //holds all of the polygon's points in an array

5
6
	Function:
7
		array returnPointsInPolygon; //an array holding all of the polygon's points

8
}

The second is to use a loop to allow an unnamed number of line segments to be traversed in our returnPointsInPolygon() function, which could look something like this:

1
function returnPointsInPolygon
2
{
3
	array PointsToReturn; //a temporary array to hold the polygon's points

4
5
	//loop through all points in the polygon, moving one co-ordinate pair at a time (by a step of two)

6
	for(int x = 0; x < this.Points.length; x+=2)
7
	{
8
		if(this is not the last point)
9
		{
10
			//create a line segment between this point and the next one in the array

11
			PointsToReturn.push(new LineSegment(this.Points[x], this.Points[x+1], this.Points[x+2], this.Points[x+3]));
12
		}
13
		else if(this is the last point)
14
		{
15
			//create a line segment between this point and the first point in the array

16
			PointsToReturn.push(new LineSegment(this.Points[x-2], this.Points[x-1], this.Points[0], this.Points[1]));
17
		}
18
	}
19
20
	//return the array of points

21
	return PointsToReturn;
22
}

With this class added to our engine, we can now create anything from a triangle to some 39-sided abomination with the same line of code.


Polygon Creator

To play with our new polygon class, let's make a program that shows the extent of its reach.  Our program is going to allow the user to add to or remove sides from the displayed polygon using key presses. Of course, we will have to set limits for the number of sides that our polygon can have, since having less than three sides will no longer make it a polygon.  We don't really have to keep an eye on the upper limits of our polygon because they should scale nicely.  However, we are going to limit polygons to having ten sides at maximum since we will be setting its new points from within the code.

Our program specifications can be broken down into these smaller parts:

  • Draw a polygon to the screen initially.
  • When the 'a' key is pressed, lower the number of sides on the polygon by 1.
  • When the 's' key is pressed, increase the number of sides on the polygon by 1.
  • Prevent the polygon's number of sides from falling below 3.
  • Prevent the polygon's number of sides from increasing above 10.

Let's look at what our code could look like:

1
main{
2
	//setup for your favorite Graphics API here

3
	//setup for keyboard input (may not be required) here

4
5
	var camera = new Camera(); //create an instance of our camera class

6
	camera.objectsInWorld[]; //initialize the camera's object array

7
8
	//set up the camera's view space

9
	camera.minX = 0;
10
	camera.maxX = screenWidth;
11
	camera.minY = 0;
12
	camera.maxY = screenHeight;
13
	camera.minZ = 0;
14
	camera.maxZ = 100;
15
16
	//create an array of points for each polygon size

17
	var threeSides = new Array(100,100,100,50,50,50);
18
	var fourSides = new Array(points in here);
19
	var fiveSides = new Array(points in here);
20
	var sixSides = new Array(points in here);
21
	var sevenSides = new Array(points in here);
22
	var eightSides = new Array(points in here);
23
	var nineSides = new Array(points in here);
24
	var tenSides = new Array(points in here);
25
26
	//store all of the arrays in another array for easier access

27
	var sidesArray = new Array(threeSides, fourSides, fiveSides, sixSides, sevenSides, eightSides, nineSides, tenSides);
28
29
	//keep track of how many points the polygon currently has

30
	var polygonPoints = 3;
31
32
	//create the initial polygon to be displayed

33
	var polygon = new Polygon(sidesArray[0][0], sidesArray[0][1], sidesArray[0][2], sidesArray[0][3], sidesArray[0][4], sidesArray[0][5],);
34
	//draw the initial polygon to the screen

35
	camera.drawScene();
36
37
	//while the user has not pressed the escape key

38
	while(key != esc) {
39
		if(key pressed == 'a')
40
		{
41
			//if the polygon is not at risk of falling below 3

42
			if(polygonPoints != 3)
43
			{
44
				//reduce the number of points

45
				polygonPoints--;
46
				//change the polygon to have the correct number of points

47
			}
48
			//redraw the scene

49
			camera.drawScene();
50
		}
51
		else if(key pressed == 's')
52
		{
53
			//if the polygon is not at risk of going above 10

54
			if(polygonPoints != 10)
55
			{
56
				//increase the number of points

57
				polygonPoints++;
58
				//change the polygon to have the correct number of points

59
			}
60
			//redraw the scene

61
			camera.drawScene();
62
		}
63
	}
64
}

Our little program should let you adjust a polygon on-screen now! Check out the demo. If you would like to beef up this program a bit, you might want to try putting the polygon alteration section into some form of an algorithm to make the scaling easier on yourself.  I'm unsure if one already exists, but if it does, you could easily have an infinitely scaling polygon on your hands!


Conclusion

We've quite an extensive amount of rasterizing built into our engine now, letting us create almost any shape that we might need (though some only through combination).  Next time we will be moving away from drawing shapes and talking more about their properties.  If you're interested in bringing some color to your screen, then be sure to check out the next part!

Advertisement
Did you find this post useful?
Want a weekly email summary?
Subscribe below and we’ll send you a weekly email summary of all new Game Development tutorials. Never miss out on learning about the next big thing.
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.