Advertisement
  1. Game Development
  2. Programming
Gamedevelopment

Let's Build a 3D Graphics Engine: Rasterizing Line Segments and Circles

by
Difficulty:IntermediateLength:MediumLanguages:
This post is part of a series called Let’s Build a 3D Graphics Software Engine.
Let's Build a 3D Graphics Engine: Spaces and Culling
Let's Build a 3D Graphics Engine: Rasterizing Triangles and Quads

Hello, this is the fourth part of our series on 3D graphics engines. This time, we will be covering rasterization: the process of taking a shape described by mathematical formulas and converting it to an image on your screen.

Tip: All of the concepts in this article are built off of classes that we've established in the first three posts, so be sure to check them out first.


Recap

Here's a review of the classes that we've made so far:

You can check out the sample program from the third part of the series to see how they work together.

Now, let's take a look at some new stuff!


Rasterization

Rasterization (or rasterisation, if you like) is the process of taking a shape described in a vector graphics format (or in our case, mathematically) and converting it into a raster image (where the shape is fit onto a pixel structure).

Because math isn't always as precise as we need it to be for computer graphics, we must use algorithms to fit the shapes it describes onto our integer-based screen. For example, a point can fall onto the co-ordinate \((3.2, 4.6)\) in mathematics, but when we render it, we must nudge it to \((3, 5)\) so it can fit into the pixel structure of our screen.

Each type of shape that we rasterize will have its own algorithm for doing so. Let's start with one of the more simple shapes to rasterize: the line segment.


Line Segments

Source: http://en.wikipedia.org/wiki/File:Bresenham.svg
Source: http://en.wikipedia.org/wiki/File:Bresenham.svg

Line segments are one of the simplest shapes that can be drawn, and so are often one of the first things covered in any geometry class. They are represented by two distinct points (one beginning point and one ending point), and the line that connects the two. The most commonly used algorithm in rasterizing a line segment is called Bresenham's Algorithm.

Step by step, Bresenham's Algorithm works like this:

  1. Receive a line segment's beginning and ending points as input.
  2. Identify a line segment's direction by determining its \(dx\) and \(dy\) properties (\(dx = x_{1} - x_{0}\), \(dy = y_{1} - y_{0}\)).
  3. Determine sx, sy, and error catching properties (I'll show the mathematical definition for these below).
  4. Round each point in the line segment to either the pixel above or below.

Before we implement Bresenham's Algorithm, lets put together a basic line segment class to be used in our engine:

If you want to perform a transformation on our new LineSegment class, all you have to do is apply your chosen transformation to the beginning and ending points of the LineSegment and then place them back into the class.  All of the points that fall between will be processed when the LineSegment itself is drawn, as Bresenham's Algorithm only requires the beginning and ending points to find each subsequent point.

In order for the LineSegment class to fit with our current engine, we can't actually have a draw() function built into the class, which is why I've opted for using a returnPointsInSegment function instead. This function will return an array of every point that exists within the line segment, allowing us to easily draw and cull the line segment as appropriate.

Our function returnPointsInSegment() looks a bit like this (in JavaScript):

The easiest way to add the rendering of our line segments into our camera class is to add in a simple if structure, similar to the following:

That's all you need to get your first shape class up and running!  If you want to learn more about the more technical aspects of Bresenham's Algorithm (particularly the error sections), you can check out the Wikipedia article on it.


Circles

Source: http://en.wikipedia.org/wiki/File:Bresenham_circle.svg
Source: http://en.wikipedia.org/wiki/File:Bresenham_circle.svg

Rasterizing a circle is a bit more difficult than rasterizing a line segment, but not much. We will be using the midpoint circle algorithm to do all of our heavy lifting, which is an extension of the previously mentioned Bresenham's Algorithm.  As such, it follows similar steps to those that were listed above, with some minor differences.

Our new algorithm works like this:

  1. Receive a circle's center point and radius.
  2. Forcibly set the points in each cardinal direction
  3. Cycle through each of our quadrants, drawing their arcs

Our circle class will be very similar to our line segment class, looking something like this:

Our returnPointsInCircle() function is going to behave in the same way that our LineSegment class's function does, returning an array of points so that our camera can render and cull them as needed. This lets our engine handle a variety of shapes, with only minor changes needed for each.

Here is what our returnPointsInCircle() function is going to look like (in JavaScript):

Now, we just add in another if statement to our main drawing loop, and these circles are fully integrated!

Here is how the updated drawing loop may look:

Now that we've got our new classes out of the way, let's make something!


Raster Master

Our program is going to be simple this time. When the user clicks on the screen, we are going to draw a circle whose center point is the point that was clicked, and whose radius is a random number.

Let's take a look at the code:

With any luck, you should now be able to use your updated engine to draw some awesome circles.


Conclusion

Now that we have some basic rasterization features in our engine, we can finally start drawing some useful things to our screen! Nothing too complicated just yet, but if you wanted to, you could piecing together some stick figures, or something of the kind.

In the next post, we're going to be taking another look at rasterization. - only this time, we're going to be setting up two more classes to be used within our engine: triangles and quadrilaterals. Stay tuned!

Advertisement
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.