Write a 3D Soft Engine from Scratch: Part 2

Now that we have built the core of our 3D engine thanks to the previous tutorial Part 1, we can work on enhancing the rendering. The next step is then to connect the dots to draw some lines in order to render what you probably know as a “wireframe” rendering.

1 – Writing the core logic for camera, mesh & device object
2 – Drawing lines and triangles to obtain a wireframe rendering (this article)
3 – Loading meshes exported from Blender in a JSON format
4 – Filling the triangle with rasterization and using a Z-Buffer
4b – Bonus: using tips & parallelism to boost the performance
5 – Handling light with Flat Shading & Gouraud Shading
6 – Applying textures, back-face culling and WebGL

In this tutorial, you will learn how to draw lines, what a face is and how cool is the Bresenham algorithm to draw some triangles.

Thanks to that, at the end, you will know how to code something as cool as that:

Yes! Our 3D rotating cube starts to really live on our screens!

First basic algorithm to draw a line between two points

Let’s start by coding a simple algorithm. To draw a line between 2 vertices, we’re going to use the following logic:

– if the distance between the 2 points (point0 & point1) is less than 2 pixels, there’s nothing to do
– otherwise, we’re finding the middle point between both points (point0 coordinates + (point1 coordinates – point0 coordinates) / 2)
– we’re drawing that point on screen
– we’re launching this algorithm recursively between point0 & middle point and between middle point & point1

Here is the code to do that:

C#
TypeScript
JavaScript

public void DrawLine(Vector2 point0, Vector2 point1)
   var dist = (point1 - point0).Length();
    // If the distance between the 2 points is less than 2 pixels
   // We're exiting
   if (dist < 2)
       return;
    // Find the middle point between first & second point
   Vector2 middlePoint = point0 + (point1 - point0)/2;
   // We draw this point on screen
   DrawPoint(middlePoint);
   // Recursive algorithm launched between first & middle point
   // and between middle & second point
   DrawLine(point0, middlePoint);
   DrawLine(middlePoint, point1);

public drawLine(point0: BABYLON.Vector2, point1: BABYLON.Vector2): void {
   var dist = point1.subtract(point0).length();
    // If the distance between the 2 points is less than 2 pixels
   // We're exiting
   if (dist < 2)
       return;
    // Find the middle point between first & second point
   var middlePoint = point0.add((point1.subtract(point0)).scale(0.5));
   // We draw this point on screen
   this.drawPoint(middlePoint);
   // Recursive algorithm launched between first & middle point
   // and between middle & second point
   this.drawLine(point0, middlePoint);
   this.drawLine(middlePoint, point1);

Device.prototype.drawLine = function (point0, point1) {
   var dist = point1.subtract(point0).length();
    // If the distance between the 2 points is less than 2 pixels
   // We're exiting
   if(dist < 2) {
       return;
   }
    // Find the middle point between first & second point
   var middlePoint = point0.add((point1.subtract(point0)).scale(0.5));
   // We draw this point on screen
   this.drawPoint(middlePoint);
   // Recursive algorithm launched between first & middle point
   // and between middle & second point
   this.drawLine(point0, middlePoint);
   this.drawLine(middlePoint, point1);
;

You need to update the rendering loop to use this new piece of code:

C#
TypeScript
JavaScript

for (var i = 0; i < mesh.Vertices.Length - 1; i++)
   var point0 = Project(mesh.Vertices[i], transformMatrix);
   var point1 = Project(mesh.Vertices[i + 1], transformMatrix);
   DrawLine(point0, point1);

for (var i = 0; i < cMesh.Vertices.length -1; i++){
   var point0 = this.project(cMesh.Vertices[i], transformMatrix);
   var point1 = this.project(cMesh.Vertices[i + 1], transformMatrix);
   this.drawLine(point0, point1);

for (var i = 0; i < cMesh.Vertices.length -1; i++){
   var point0 = this.project(cMesh.Vertices[i], transformMatrix);
   var point1 = this.project(cMesh.Vertices[i + 1], transformMatrix);
   this.drawLine(point0, point1);

And you should now obtain something like that:

I know this looks weird but this was the expected behavior. It should help you starting to understand what you need to do to display a 3D mesh. But to have a better rendering, we need to discover a new concept.

Displaying faces with triangles

Now that we know how to draw lines, we need a better way to render the mesh with them. The simplest geometric 2D shape is a triangle. The idea in 3D is then to draw all our meshes by using those triangles. We then need to split each side of our cube into 2 triangles. We’re going to do this “manually” but we’ll see in the next tutorial that 3D modelers are doing this step automatically for us now.

To draw triangles, you need to have 3 points/vertices. A face is then simply a structure containing 3 values which are indexes pointing to the proper vertices array of the mesh to be rendered.

To be understand this concept, let’s take our previous figure with a Cube displayed by Blender:

We have 4 vertices displayed on this figure with the following indices: 0, 1, 2, 3. To draw the upper side of the cube, we need to draw 2 triangles. The first one, Face 0, will be drawn with 3 lines from vertex 0 (-1, 1, 1) to vertex 1 (1, 1, 1), from vertex 1 (1, 1, 1) to vertex 2 (-1, –1, 1) and finally from vertex 2 (-1, –1, 1) to vertex 0 (-1, 1, 1). The second triangle, Face 1, will be drawn with the lines from vertex 1 to vertex 2, vertex 2 to vertex 3 and vertex 3 to vertex 1.

The equivalent code would be something like that:

var mesh = new SoftEngine.Mesh("Square", 4, 2);
eshes.Add(mesh);
esh.Vertices[0] = new Vector3(-1, 1, 1);
esh.Vertices[1] = new Vector3(1, 1, 1);
esh.Vertices[2] = new Vector3(-1, -1, 1);
esh.Vertices[3] = new Vector3(1, -1, 1);
mesh.Faces[0] = new Face { A = 0, B = 1, C = 2 };
esh.Faces[1] = new Face { A = 1, B = 2, C = 3 };

If you want to draw to whole cube, you need to find the 10 remaining faces as we’ve got 12 faces for the 6 sides of our cube to draw.

Let’s now define the code for a Face object. It’s a very simple object as this is just a set of 3 indexes. Here’s the code of Face and the new Mesh definition which also now use it:

C#
TypeScript
JavaScript

namespace SoftEngine
   public struct Face
   {
       public int A;
       public int B;
       public int C;
   }
   public class Mesh
   {
       public string Name { get; set; }
       public Vector3[] Vertices { get; private set; }
       public Face[] Faces { get; set; }
       public Vector3 Position { get; set; }
       public Vector3 Rotation { get; set; }
        public Mesh(string name, int verticesCount, int facesCount)
       {
           Vertices = new Vector3[verticesCount];
           Faces = new Face[facesCount];
           Name = name;
       }
   }

///<reference path="babylon.math.ts"/>
module SoftEngine {
   export interface Face {
       A: number;
       B: number;
       C: number;
   }
    export class Mesh {
       Position: BABYLON.Vector3;
       Rotation: BABYLON.Vector3;
       Vertices: BABYLON.Vector3[];
       Faces: Face[];
        constructor(public name: string, verticesCount: number, facesCount: number) {
           this.Vertices = new Array(verticesCount);
           this.Faces = new Array(facesCount);
           this.Rotation = new BABYLON.Vector3(0, 0, 0);
           this.Position = new BABYLON.Vector3(0, 0, 0);
       }
   }

var SoftEngine;
function (SoftEngine) {
   var Mesh = (function () {
       function Mesh(name, verticesCount, facesCount) {
           this.name = name;
           this.Vertices = new Array(verticesCount);
           this.Faces = new Array(facesCount);
           this.Rotation = new BABYLONTS.Vector3(0, 0, 0);
           this.Position = new BABYLONTS.Vector3(0, 0, 0);
       }
       return Mesh;
   })();
   SoftEngine.Mesh = Mesh;    
)(SoftEngine || (SoftEngine = {}));

We now need to update our Render() function/method of our Device object to iterate through all the faces defined and to draw the triangles associated.

C#
TypeScript
JavaScript

foreach (var face in mesh.Faces)
   var vertexA = mesh.Vertices[face.A];
   var vertexB = mesh.Vertices[face.B];
   var vertexC = mesh.Vertices[face.C];
    var pixelA = Project(vertexA, transformMatrix);
   var pixelB = Project(vertexB, transformMatrix);
   var pixelC = Project(vertexC, transformMatrix);
    DrawLine(pixelA, pixelB);
   DrawLine(pixelB, pixelC);
   DrawLine(pixelC, pixelA);

for (var indexFaces = 0; indexFaces < cMesh.Faces.length; indexFaces++)
   var currentFace = cMesh.Faces[indexFaces];
   var vertexA = cMesh.Vertices[currentFace.A];
   var vertexB = cMesh.Vertices[currentFace.B];
   var vertexC = cMesh.Vertices[currentFace.C];
    var pixelA = this.project(vertexA, transformMatrix);
   var pixelB = this.project(vertexB, transformMatrix);
   var pixelC = this.project(vertexC, transformMatrix);
    this.drawLine(pixelA, pixelB);
   this.drawLine(pixelB, pixelC);
   this.drawLine(pixelC, pixelA);

for (var indexFaces = 0; indexFaces < cMesh.Faces.length; indexFaces++)
   var currentFace = cMesh.Faces[indexFaces];
   var vertexA = cMesh.Vertices[currentFace.A];
   var vertexB = cMesh.Vertices[currentFace.B];
   var vertexC = cMesh.Vertices[currentFace.C];
    var pixelA = this.project(vertexA, transformMatrix);
   var pixelB = this.project(vertexB, transformMatrix);
   var pixelC = this.project(vertexC, transformMatrix);
    this.drawLine(pixelA, pixelB);
   this.drawLine(pixelB, pixelC);
   this.drawLine(pixelC, pixelA);

We finally need to declare the mesh associated with our Cube properly with its 12 faces to make this new code working as expected.

Here is the new declaration:

C#
TypeScript/a>
JavaScript

var mesh = new SoftEngine.Mesh("Cube", 8, 12);
eshes.Add(mesh);
esh.Vertices[0] = new Vector3(-1, 1, 1);
esh.Vertices[1] = new Vector3(1, 1, 1);
esh.Vertices[2] = new Vector3(-1, -1, 1);
esh.Vertices[3] = new Vector3(1, -1, 1);
esh.Vertices[4] = new Vector3(-1, 1, -1);
esh.Vertices[5] = new Vector3(1, 1, -1);
esh.Vertices[6] = new Vector3(1, -1, -1);
esh.Vertices[7] = new Vector3(-1, -1, -1);
mesh.Faces[0] = new Face { A = 0, B = 1, C = 2 };
esh.Faces[1] = new Face { A = 1, B = 2, C = 3 };
esh.Faces[2] = new Face { A = 1, B = 3, C = 6 };
esh.Faces[3] = new Face { A = 1, B = 5, C = 6 };
esh.Faces[4] = new Face { A = 0, B = 1, C = 4 };
esh.Faces[5] = new Face { A = 1, B = 4, C = 5 };
mesh.Faces[6] = new Face { A = 2, B = 3, C = 7 };
esh.Faces[7] = new Face { A = 3, B = 6, C = 7 };
esh.Faces[8] = new Face { A = 0, B = 2, C = 7 };
esh.Faces[9] = new Face { A = 0, B = 4, C = 7 };
esh.Faces[10] = new Face { A = 4, B = 5, C = 6 };
esh.Faces[11] = new Face { A = 4, B = 6, C = 7 };

var mesh = new SoftEngine.Mesh("Cube", 8, 12);
eshes.push(mesh);
esh.Vertices[0] = new BABYLON.Vector3(-1, 1, 1);
esh.Vertices[1] = new BABYLON.Vector3(1, 1, 1);
esh.Vertices[2] = new BABYLON.Vector3(-1, -1, 1);
esh.Vertices[3] = new BABYLON.Vector3(1, -1, 1);
esh.Vertices[4] = new BABYLON.Vector3(-1, 1, -1);
esh.Vertices[5] = new BABYLON.Vector3(1, 1, -1);
esh.Vertices[6] = new BABYLON.Vector3(1, -1, -1);
esh.Vertices[7] = new BABYLON.Vector3(-1, -1, -1);
mesh.Faces[0] = { A:0, B:1, C:2 };
esh.Faces[1] = { A:1, B:2, C:3 };
esh.Faces[2] = { A:1, B:3, C:6 };
esh.Faces[3] = { A:1, B:5, C:6 };
esh.Faces[4] = { A:0, B:1, C:4 };
esh.Faces[5] = { A:1, B:4, C:5 };
mesh.Faces[6] = { A:2, B:3, C:7 };
esh.Faces[7] = { A:3, B:6, C:7 };
esh.Faces[8] = { A:0, B:2, C:7 };
esh.Faces[9] = { A:0, B:4, C:7 };
esh.Faces[10] = { A:4, B:5, C:6 };
esh.Faces[11] = { A:4, B:6, C:7 };

var mesh = new SoftEngine.Mesh("Cube", 8, 12);
eshes.push(mesh);
esh.Vertices[0] = new BABYLON.Vector3(-1, 1, 1);
esh.Vertices[1] = new BABYLON.Vector3(1, 1, 1);
esh.Vertices[2] = new BABYLON.Vector3(-1, -1, 1);
esh.Vertices[3] = new BABYLON.Vector3(1, -1, 1);
esh.Vertices[4] = new BABYLON.Vector3(-1, 1, -1);
esh.Vertices[5] = new BABYLON.Vector3(1, 1, -1);
esh.Vertices[6] = new BABYLON.Vector3(1, -1, -1);
esh.Vertices[7] = new BABYLON.Vector3(-1, -1, -1);
mesh.Faces[0] = { A:0, B:1, C:2 };
esh.Faces[1] = { A:1, B:2, C:3 };
esh.Faces[2] = { A:1, B:3, C:6 };
esh.Faces[3] = { A:1, B:5, C:6 };
esh.Faces[4] = { A:0, B:1, C:4 };
esh.Faces[5] = { A:1, B:4, C:5 };
mesh.Faces[6] = { A:2, B:3, C:7 };
esh.Faces[7] = { A:3, B:6, C:7 };
esh.Faces[8] = { A:0, B:2, C:7 };
esh.Faces[9] = { A:0, B:4, C:7 };
esh.Faces[10] = { A:4, B:5, C:6 };
esh.Faces[11] = { A:4, B:6, C:7 };

You should now have this beautiful rotating cube:

Congrats! :)

Enhancing the line drawing algorithm with Bresenham

There is an optimized way to draw our lines using the Bresenham’s line algorithm. It’s faster & sharper than our current simple recursive version. The story of this algorithm is fascinating. Please read the Wikipedia definition of this algorithm to discover how Bresenham build it and for which reasons.

Here are the versions of this algorithm in C#, TypeScript and JavaScript:

C#
TypeScript
JavaScript

public void DrawBline(Vector2 point0, Vector2 point1)
   int x0 = (int)point0.X;
   int y0 = (int)point0.Y;
   int x1 = (int)point1.X;
   int y1 = (int)point1.Y;
           
   var dx = Math.Abs(x1 - x0);
   var dy = Math.Abs(y1 - y0);
   var sx = (x0 < x1) ? 1 : -1;
   var sy = (y0 < y1) ? 1 : -1;
   var err = dx - dy;
    while (true) {
       DrawPoint(new Vector2(x0, y0));
        if ((x0 == x1) && (y0 == y1)) break;
       var e2 = 2 * err;
       if (e2 > -dy) { err -= dy; x0 += sx; }
       if (e2 < dx) { err += dx; y0 += sy; }
   }

public drawBline(point0: BABYLON.Vector2, point1: BABYLON.Vector2): void {
   var x0 = point0.x >> 0;
   var y0 = point0.y >> 0;
   var x1 = point1.x >> 0;
   var y1 = point1.y >> 0;
   var dx = Math.abs(x1 - x0);
   var dy = Math.abs(y1 - y0);
   var sx = (x0 < x1) ? 1 : -1;
   var sy = (y0 < y1) ? 1 : -1;
   var err = dx - dy;
    while (true) {
       this.drawPoint(new BABYLON.Vector2(x0, y0));
        if ((x0 == x1) && (y0 == y1)) break;
       var e2 = 2 * err;
       if (e2 > -dy) { err -= dy; x0 += sx; }
       if (e2 < dx) { err += dx; y0 += sy; }
   }

Device.prototype.drawBline = function (point0, point1) {
   var x0 = point0.x >> 0;
   var y0 = point0.y >> 0;
   var x1 = point1.x >> 0;
   var y1 = point1.y >> 0;
   var dx = Math.abs(x1 - x0);
   var dy = Math.abs(y1 - y0);
   var sx = (x0 < x1) ? 1 : -1;
   var sy = (y0 < y1) ? 1 : -1;
   var err = dx - dy;
   while(true) {
       this.drawPoint(new BABYLON.Vector2(x0, y0));
       if((x0 == x1) && (y0 == y1)) break;
       var e2 = 2 * err;
       if(e2 > -dy) { err -= dy; x0 += sx; }
       if(e2 < dx) { err += dx; y0 += sy; }
   }
;

In the render function, replace the call do DrawLine by DrawBline and you should notice that this is a bit more fluid & a bit more sharp:

If you’re observing it with attention, you should see that this version using Bresenham is less choppy than our first algorithm.

Again, you can download the solutions containing the source code:

– C# : SoftEngineCSharpPart2.zip
– TypeScript : SoftEngineTSPart2.zip
– JavaScript : SoftEngineJSPart2.zip or simply right-click –> view source on the embedded iframe

In next tutorial, you will learn how to export some Meshes from Blender, a free 3D modeler tool, into a JSON format. We will then load this JSON file to display it with our wireframe engine. Indeed, we already have everything setup to display much more complex meshes like these one:

See you in the third part.

Originally published: https://blogs.msdn.com/b/davrous/archive/2013/06/14/tutorial-part-2-learning-how-to-write-a-3d-soft-engine-from-scratch-in-c-ts-or-js-drawing-lines-amp-triangles.aspx. Reprinted here with permission of the author.

Frequently Asked Questions about Writing a 3D Software Engine from Scratch

What does it mean to write a 3D software engine from scratch?

Writing a 3D software engine from scratch means creating a 3D software engine without using any pre-existing third-party libraries or tools. It involves writing all the code yourself, starting from the very basics. This process can be quite complex and time-consuming, but it provides a deep understanding of how 3D software engines work and allows for complete customization.

What are the basic steps to write a 3D software engine from scratch?

The basic steps to write a 3D software engine from scratch include understanding the mathematics behind 3D graphics, learning about the different components of a 3D engine such as rendering, animation, and physics, and then writing the code for each of these components. It also involves testing and debugging the engine to ensure it works correctly.

What programming languages are best for writing a 3D software engine from scratch?

The choice of programming language depends on your personal preference and the specific requirements of your project. However, C++ is commonly used for writing 3D software engines due to its high performance and flexibility. Other languages like Java and Python can also be used, but they may not offer the same level of performance.

What mathematical concepts do I need to understand to write a 3D software engine from scratch?

Writing a 3D software engine from scratch requires a good understanding of several mathematical concepts, including linear algebra, geometry, and trigonometry. You need to understand vectors, matrices, and transformations, as well as concepts like dot product and cross product. A solid understanding of these concepts is essential for creating realistic 3D graphics.

How can I optimize the performance of my 3D software engine?

There are several ways to optimize the performance of a 3D software engine. These include using efficient algorithms, minimizing memory usage, and optimizing the rendering pipeline. It’s also important to profile your engine regularly to identify and fix any performance bottlenecks.

What are the challenges of writing a 3D software engine from scratch?

Writing a 3D software engine from scratch can be quite challenging. It requires a deep understanding of 3D graphics and the underlying mathematics, as well as strong programming skills. It can also be time-consuming, as you need to write all the code yourself. However, the process can be very rewarding and educational.

Can I write a 3D software engine from scratch if I’m a beginner programmer?

While it’s possible for a beginner programmer to write a 3D software engine from scratch, it’s a complex task that requires a good understanding of both programming and mathematics. If you’re a beginner, it might be better to start with simpler projects and gradually work your way up to more complex ones.

What resources can I use to learn about writing a 3D software engine from scratch?

There are many resources available online to help you learn about writing a 3D software engine from scratch. These include tutorials, online courses, books, and forums. You can also learn a lot by studying the source code of existing 3D engines.

How long does it take to write a 3D software engine from scratch?

The time it takes to write a 3D software engine from scratch can vary greatly depending on your experience level, the complexity of the engine, and the amount of time you can dedicate to the project. It can take anywhere from several months to several years.

Why should I write a 3D software engine from scratch instead of using an existing one?

Writing a 3D software engine from scratch can be a great learning experience. It allows you to gain a deep understanding of how 3D engines work and can help you develop strong programming and problem-solving skills. However, if your goal is to create a 3D game or application quickly, using an existing engine might be a better option.