The other day I stumbled onto Dmitry Sokolov’s ‘How OpenGL works’ series, about implementing your own software 3D renderer which functions kind of like OpenGL. I decided to give it a go myself, and maybe write some posts detailing the journey. In part 1 we get set up and get some pseudo wireframe rendering going. You can check out the results, then read on to find out how it’s done.
If you want to follow along, just download and unzip the code for this part. I’ll briefly go over the contents before we proceed:
- index.html - The file containing the main code for this part. Our source code will be inside this HTML in an inline script tag, at least for now.
- teapot.obj - A 3D teapot model I nabbed off the internet.
- serve.bat - A batch file which, assuming you have Python installed and in your PATH, starts a server at
http://127.0.0.1:12345, necessary because otherwise using
XMLHttpRequestto load files won’t work. If you have Python 2.x, this will work, but if you’re running 3.x you should replace ‘SimpleHTTPServer’ with ‘http.server’.
- misc.js - This contains some helper code that isn’t that interesting to cover for what we’re doing, including:
- IO module - Contains the
Fileclass which lets us load files using
XMLHttpRequest, in bulk and using a queue if necessary.
- debugMode function - Lets us turn alerts for errors with nicely formatted stack traces on and off.
- usingModule function - Takes an object and adds all its properties to the window object so we can use for instance
new File("teapot.obj")instead of
- IO module - Contains the
And because I’m a crotchety C# programmer at heart I’ll be using ECMAScript 6’s new
class keyword and features, which means that this will run in recent versions of Firefox, Chrome, and Edge 13 and basically nothing below that. Sorry not sorry.
Preparing the Canvas
First things first, we need a canvas to draw into, so we get that ready.
Pretty simple. Just a
canvas element, with the mind bogglingly original
canvas, the property
moz-opaque for some performance enhancements in browsers that support it since we don’t care about seeing what’s below the canvas, and a 1 pixel black border.
Inside the run function we get our canvas by its id, and set the width and height, as well as create a 2d rendering context. Then, for good measure and since not all browsers support
moz-opaque, we clear it to black just to be sure. Finally we store our canvas’ image data so we can pass it around to our custom drawing functions later.
Note that the
debugMode function is one of our helper functions from
misc.js. If you’re following along, make sure to include this in the
head section of your file using
Bresenham’s Line Drawing Algorithm
This is what part 1 of the lessons I’m following covers. However, I already had this implemented, and just reused/rewrote the C# code I already had to implement this. Other people are far more qualified to cover Bresenham’s algorithm, so I won’t go into detail on how it actually works. I will however, provide the code that does the drawing.
We pass it an
ImageData instance, which we got from our canvas already, as well as the coordinates to draw from and to, and this draws an aliased 1 pixel thick white line. Note that Bresenham’s line algorithm can use only integers for added performance, which this version does. In order to make that work we have to convert the coordinates to integers, so we do that. Then we get the pixel data from our
imageData using its
data property, which is a
Uint8ClampedArray instance, or an array of width times height times 4 unsigned 8-bit integers with values between 0 and 255 inclusive. We’ll be using this to write directly to the pixels.
When we want to draw a pixel we determine its starting position inside this array and set all 4 bytes to 255, which creates a full opaque white pixel. Ideally you’d want to be able to specify the color of the pixels, but right now we’re just trying to get up and running so this will do. Now we can render a line to our canvas using the following code in our
At this point we could theoretically render a model, if we had one, so that’s our next step.
Loading and Parsing the Model
Loading files inside an HTML file is a right pain in the ass. The way its usually done is using
XMLHttpRequest, which can fetch other documents either synchronously or asynchronously, although the former is discouraged, so we don’t want to do that. Fortunately our
IO module in
misc.js has us covered with the
IO.File class, which lets us queue up any number of files to load, and letting us know when it’s done. We modify our earlier
run function to do this like so:
IO.File.loadFiles function takes a function to call when done loading the files, and then a list of items which can either be an URI string, or an array containing an URI string and a type string. Since the default way to load is as a plain-text file, we can just supply our
"teapot.obj" string directly. Once our file is loaded our function will be called with a list of files in the order we supplied them, so
files will be an instance of
IO.File, and if all is well its
value property will have the text we need, which we pass to a
parseObj function that we will create shortly.
Once everything’s loaded and the model’s been parsed we call a new
start function, which contains the code that was in our
run function before. Of course we need to actually parse the model file. Fortunately the obj format is pretty easy to follow. For example:
This describes a 3D ‘model’, with three vertices and one face (or triangle). Every line that starts with ‘v’ describes a vertex, with its X, Y, then Z coordinates. Every line that starts with ‘f’ describes a single triangle, with the three numbers describing the indices of the vertices in order. For some reason the obj file format decided that the first declared vertex starts at index 1, not 0, so be careful of that. A face declaration can also have negative indices, in which case -1 refers to the last vertex specified so far, -2 to the second to last, and so on.
With this knowledge we can write our
parseObj function to get the vertices and faces that make up our model:
There’s really nothing shocking here. We loop through all the lines in our text, if a line starts with ‘v’ we push a vertex into our array of vertices, if it starts with ‘f’ we push a face into the faces array containing the vertex indices. Once we’ve gone through all the lines we return an object containing our vertex and face arrays.
Rendering the Model
Now we’re finally ready to render our model! We add the following code to the end of our
First we set up some variables that lets us position where we draw onto the canvas. We want to center our drawing, so we calculate the center X and Y coordinates. The teapot we’re rendering is kinda small though, so we’ll just multiply all coordinates by a
scale variable, and it sits on top of zero on the Y axis, so we add an offset to that as well.
If all vertices look good we draw a line from vertex 0, to vertex 1, to vertex 2, and back to vertex 0. You might notice that we’re subtracting the vertices’ Y coordinates from the center Y coordinate, instead of adding them. That’s because in 3D space a bigger value for Y means the position is higher up, but we’re drawing in 2D space where a higher value means the position is actually lower, so we subtract the value instead of adding it. This isn’t a problem for now, and it’ll fix itself when we start doing proper 3D transformations later on.
Finally, we update our canvas with our new pixel data to see the results. And viola, we have a teapot!
The astute among you might notice something doesn’t seem quite right. Every quad on the model is divided like a sort of X shape, into what appears to be 4 triangles. What is actually happening is that we’re drawing the model’s wireframe without backface culling, that is we are drawing the back of the teapot as well as the front, and they line up and overlap perfectly because of how the model is made, but the diagonal faces the opposite way, creating the X shape.
The lessons I was following saved backface culling for the 2nd lesson but I figured I’d get a head start and implement it straight away. Face culling relies on something called the polygon’s winding order; the clockwise or counterclockwise direction you get if you follow the order of the vertices inside the polygon on the screen from one, to the next, to the next, to the first. In OpenGL the convention is that if the order of vertices is counterclockwise, then we’re looking at the front of a polygon, if its clockwise then we’re looking at the back of a polygon and (unless specified otherwise by the programmer) we don’t need to draw it.
Unfortunately, this does involve some math. Feel free to skip most of the explanations below and skip straight to the code, but for those interested in understanding how to do it, I’ll explain. To figure out the winding order, we need to perform the following steps:
- Transform all the vertices to screen space.
- Calculate the cross product of two of the polygon’s edges.
- Check the Z component of the result to see if the polygon is front or back facing.
Given that we have our vertices in screen space, we know that X is the horizontal axis, Y is the vertical axis, and Z is the axis that points into and out of the screen. The X and Y axes aren’t going to tell us if we’re looking at the back or front, we want the axis that either points towards us, or away from us, to tell us if we’re looking at the polygon’s back or front. That means we don’t actually need the full cross product, but just the Z component, defined as
a.x * b.y - a.y * b.x, which saves us a lot of calculations.
Unfortunately our vertices are not defined relative to the origin. Fortunately, it’s easy to fix that. Imagine a line from a point at (1, 1) to another point at (5, 1), the red line in the image above. If you subtract the former point from the latter point, you get a point that’s at (5-1, 1-1) or (4, 0) in space. If you then draw the green line from (0, 0) to (4, 0), you’d get the same line as the red one, just eminating from the origin instead of from somewhere else.
We can do the same with 3D points, and we happen to have three of them; our vertices. If we subtract our first vertex’s positions from the 2nd and 3rd, we get two vectors that describe the edges of our triangle, starting at the origin, which lets us do our cross product cheaply and easily. So if we define our vertices as v0, v1, and v2 in order we get the following:
a.x = v1.x - v0.x a.y = v1.y - v0.y b.x = v2.x - v0.x b.y = v2.y - v0.y z = a.x * b.y - a.y * b.x z = (v1.x - v0.x) * (v2.y - v0.y) - (v1.y - v0.y) * (v2.x - v0.x)
You might notice we’re not calculating a.z or b.z, but that’s just because the calculation we’re doing doesn’t require those. If we try this out we wind up getting a negative value for Z if the vertices are counterclockwise, which lets us write our function as follows:
And we can add a call to this function to our drawing code to only draw polygons which are facing towards us:
This section was very heavy on the maths, but if you don’t understand the cross product you can just use the code as provided or read more about the cross product on Math Is Fun.
Note: In an earlier version of this article I said that
isCcw should return a negative value for front facing polygons even though OpenGL specifies that a negative Z value points away from us, into the screen. I argued that this was correct because our screen coordinates are reversed from OpenGL’s where 0 is at the bottom, and Y increases towards the top. This explanation would have been correct if the cross product we were calculating was the cross product of the screen coordinates, unfortunately I failed to recognize that we were passing it the model’s vertices, which do not have a flipped Y axis, and thus would function completely as normal. Oops?
And this is what our final result looks like. Not bad! Next we’ll be adding triangle rasterization and some other things. You can find the source code download and relevant links below, and if you liked this post maybe give it a share using one of the buttons below or check out options to support our work.