In the previous tutorial, learning how to write a 3D soft engine in C#, TS or JS – loading meshes exported from Blender, we’ve loaded a JSON file where our meshes were serialized from Blender. Up to now, our render function was drawing the meshes with only a simple wireframe rendering. We’re now going to see how to fill the triangles using a rasterization algorithm. Then, we’ll see how to handle a Z-Buffer to avoid having faces living in the back being drawn on top on front faces.
This tutorial is part of the following series:
1 – Writing the core logic for camera, mesh & device object2 – Drawing lines and triangles to obtain a wireframe rendering3 – Loading meshes exported from Blender in a JSON format4 – Filling the triangle with rasterization and using a Z-Buffer (this article)4b – Bonus: using tips & parallelism to boost the performance5 – Handling light with Flat Shading & Gouraud Shading6 – Applying textures, back-face culling and WebGL
By following this tutorial, you will be able to have such rendering:Rasterization
There’s a lot of different types of rasterization algorithms. I even know someone in my team who has made his own patented rasterization algorithm for a well known GPU maker. It’s also thanks to him that I now know what Boustrophedon is and it has really changed my life since then. 🙂
To be more serious, we’re going to implement in this tutorial a simple but efficient rasterization algorithm. As we’re running on CPU with our 3D software engine, we must pay a lot of attention to this part. Indeed, it will to cost us a lot of CPU. Today, of course, this heavy part is done directly by GPUs.
Let’s start by an exercise. Take a piece of paper and start drawing all the types of triangles you could think of. The idea is to find a generic way to draw any type of triangles.
If we’re sorting the three vertices of each triangle on the Y coordinates in order to always have P1 followed by P2 followed by P3, we will finally only have 2 possible cases:
You then see that we have 2 cases: P2 is on the right of P1P3 or P2 is on the left of P1P3. In our case, as we want to always draw our lines from left to right from sx to ex, we will have a first conditional IF to handle these 2 cases.
Moreover, we’re going to draw from left to right by moving down from P1.Y to P3.Y following the red line drawn on the left case of the figure. But we will need to change our logic reaching P2.Y as the slope will change in both cases. That’s why, we’ve got 2 steps in the scan line process. Moving down from P1.Y to P2.Y and then from P2.Y to P3.Y, our final destination.
All the logic needed to understand how to build our algorithm is described on Wikipedia: http://en.wikipedia.org/wiki/Slope . This is really some basic math.
To be able to sort the cases between case 1 and case 2, you simply need to compute the inverse slopes in this way:
dP1P2 = P2.X – P1.X / P2.Y – P1.Y and dP1P3 = P3.X – P1.X / P3.Y – P1.Y
If dP1P2 > dP1P3 then we are in the first case with P2 on the right, otherwise if dP1P2 > dP1P2, we are in the second case with P2 on the left.
Now that we have the basic logic of our algorithm, we need to know how to compute X on each line between SX (Start X) and EX (End X) on my figure. So we need to compute SX & EX first. As we know the Y value and the slope P1P3 & P1P2, we can easily find SX & EX we’re interested in.
Let’s take the step 1 of the case 1 as an example. First step is to compute our gradient with the current Y value in our loop. It will tell us at which stage we are in the scan line processing between P1.Y and P2.Y in Step 1.
gradient = currentY – P1.Y / P2.Y – P1.Y
As X and Y are linearly linked, we can interpolate SX based on this gradient using P1.X and P3.X & interpolate EX using P1.X and P2.X.
If you manage to understand this concept of interpolation, you will be able to understand all the remaining tutorials to handle light & texture. You then definitely need to spend time on reading the associated code. You need also to be sure you’d be able to rebuild it from scratch yourself without copy/pasting the code below.
If it’s still not clear enough, here are other interesting articles to read addressing also rasterization:
– 3D Software Rendering Engine – Part I– Triangle Rasterization– Software Rasterization Algorithms for filling triangles
Now that we have our algorithm described. Let’s now work on the code. Start by removing the drawLine and drawBline from the device class. Then, replace your existing functions/methods by those one:C#TypeScriptJavaScript// Project takes some 3D coordinates and transform them
// in 2D coordinates using the transformation matrix
public Vector3 Project(Vector3 coord, Matrix transMat)
{
// transforming the coordinates
var point = Vector3.TransformCoordinate(coord, transMat);
// The transformed coordinates will be based on coordinate system
// starting on the center of the screen. But drawing on screen normally starts
// from top left. We then need to transform them again to have x:0, y:0 on top left.
var x = point.X * bmp.PixelWidth + bmp.PixelWidth / 2.0f;
var y = -point.Y * bmp.PixelHeight + bmp.PixelHeight / 2.0f;
return (new Vector3(x, y, point.Z));
}
// DrawPoint calls PutPixel but does the clipping operation before
public void DrawPoint(Vector2 point, Color4 color)
{
// Clipping what's visible on screen
if (point.X >= 0 && point.Y >= 0 && point.X < bmp.PixelWidth && point.Y < bmp.PixelHeight)
{
// Drawing a point
PutPixel((int)point.X, (int)point.Y, color);
}
}// Project takes some 3D coordinates and transform them
// in 2D coordinates using the transformation matrix
public project(coord: BABYLON.Vector3, transMat: BABYLON.Matrix): BABYLON.Vector3 {
// transforming the coordinates
var point = BABYLON.Vector3.TransformCoordinates(coord, transMat);
// The transformed coordinates will be based on coordinate system
// starting on the center of the screen. But drawing on screen normally starts
// from top left. We then need to transform them again to have x:0, y:0 on top left.
var x = point.x * this.workingWidth + this.workingWidth / 2.0;
var y = -point.y * this.workingHeight + this.workingHeight / 2.0;
return (new BABYLON.Vector3(x, y, point.z));
}
// drawPoint calls putPixel but does the clipping operation before
public drawPoint(point: BABYLON.Vector2, color: BABYLON.Color4): void {
// Clipping what's visible on screen
if (point.x >= 0 && point.y >= 0 && point.x < this.workingWidth && point.y < this.workingHeight) {
// Drawing a yellow point
this.putPixel(point.x, point.y, color);
}
}// Project takes some 3D coordinates and transform them
// in 2D coordinates using the transformation matrix
Device.prototype.project = function (coord, transMat) {
var point = BABYLON.Vector3.TransformCoordinates(coord, transMat);
// The transformed coordinates will be based on coordinate system
// starting on the center of the screen. But drawing on screen normally starts
// from top left. We then need to transform them again to have x:0, y:0 on top left.
var x = point.x * this.workingWidth + this.workingWidth / 2.0 >> 0;
var y = -point.y * this.workingHeight + this.workingHeight / 2.0 >> 0;
return (new BABYLON.Vector3(x, y, point.z));
};
// drawPoint calls putPixel but does the clipping operation before
Device.prototype.drawPoint = function (point, color) {
// Clipping what's visible on screen
if (point.x >= 0 && point.y >= 0 && point.x < this.workingWidth
&& point.y < this.workingHeight) {
// Drawing a yellow point
this.putPixel(point.x, point.y, color);
}
};