Write a 3D Soft Engine from Scratch: Part 4

Written by admin. Posted in HTML5

Tagged: , , , , , , ,

Published on February 02, 2014 with No Comments

This entry is part 4 of 7 in the series Write a 3D Soft Engine from Scratch

In the previous tutorial, Part 3, 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.

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:

image

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:

<span style="color: green;">// Project takes some 3D coordinates and transform them
/ in 2D coordinates using the transformation matrix
</span><span style="color: blue;">public </span><span style="color: rgb(43, 145, 175);">Vector3 </span><span style="color: black;">Project(</span><span style="color: rgb(43, 145, 175);">Vector3 </span><span style="color: black;">coord, </span><span style="color: rgb(43, 145, 175);">Matrix </span><span style="color: black;">transMat)
   </span><span style="color: green;">// transforming the coordinates
   </span><span style="color: blue;">var </span><span style="color: black;">point = </span><span style="color: rgb(43, 145, 175);">Vector3</span><span style="color: black;">.TransformCoordinate(coord, transMat);
   </span><span style="color: green;">// 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.
   </span><span style="color: blue;">var </span><span style="color: black;">x = point.X * bmp.PixelWidth + bmp.PixelWidth / 2.0f;
   </span><span style="color: blue;">var </span><span style="color: black;">y = -point.Y * bmp.PixelHeight + bmp.PixelHeight / 2.0f;
   </span><span style="color: blue;">return </span><span style="color: black;">(</span><span style="color: blue;">new </span><span style="color: rgb(43, 145, 175);">Vector3</span><span style="color: black;">(x, y, point.Z));
</span><span style="color: green;">// DrawPoint calls PutPixel but does the clipping operation before
</span><span style="color: blue;">public void </span><span style="color: black;">DrawPoint(</span><span style="color: rgb(43, 145, 175);">Vector2 </span><span style="color: black;">point, </span><span style="color: rgb(43, 145, 175);">Color4 </span><span style="color: black;">color)
   </span><span style="color: green;">// Clipping what's visible on screen
   </span><span style="color: blue;">if </span><span style="color: black;">(point.X &gt;= 0 &amp;&amp; point.Y &gt;= 0 &amp;&amp; point.X &lt; bmp.PixelWidth &amp;&amp; point.Y &lt; bmp.PixelHeight)
   
       </span><span style="color: green;">// Drawing a point
       </span><span style="color: black;">PutPixel((</span><span style="color: blue;">int</span><span style="color: black;">)point.X, (</span><span style="color: blue;">int</span><span style="color: black;">)point.Y, color);
   
</span>

<span style="color: green;">// Project takes some 3D coordinates and transform them
/ in 2D coordinates using the transformation matrix
</span><span style="color: blue;">public </span><span style="color: black;">project(coord: BABYLON.Vector3, transMat: BABYLON.Matrix): BABYLON.Vector3 
   </span><span style="color: green;">// transforming the coordinates
   </span><span style="color: blue;">var </span><span style="color: black;">point = BABYLON.Vector3.TransformCoordinates(coord, transMat);
   </span><span style="color: green;">// 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.
   </span><span style="color: blue;">var </span><span style="color: black;">x = point.x * </span><span style="color: blue;">this</span><span style="color: black;">.workingWidth + </span><span style="color: blue;">this</span><span style="color: black;">.workingWidth / 2.0;
   </span><span style="color: blue;">var </span><span style="color: black;">y = -point.y * </span><span style="color: blue;">this</span><span style="color: black;">.workingHeight + </span><span style="color: blue;">this</span><span style="color: black;">.workingHeight / 2.0;
   </span><span style="color: blue;">return </span><span style="color: black;">(</span><span style="color: blue;">new </span><span style="color: black;">BABYLON.Vector3(x, y, point.z));
</span><span style="color: green;">// drawPoint calls putPixel but does the clipping operation before
</span><span style="color: blue;">public </span><span style="color: black;">drawPoint(point: BABYLON.Vector2, color: BABYLON.Color4): </span><span style="color: blue;">void </span><span style="color: black;">
   </span><span style="color: green;">// Clipping what's visible on screen
   </span><span style="color: blue;">if </span><span style="color: black;">(point.x &gt;= 0 &amp;&amp; point.y &gt;= 0 &amp;&amp; point.x &lt; </span><span style="color: blue;">this</span><span style="color: black;">.workingWidth &amp;&amp; point.y &lt; </span><span style="color: blue;">this</span><span style="color: black;">.workingHeight) 
       </span><span style="color: green;">// Drawing a yellow point
       </span><span style="color: blue;">this</span><span style="color: black;">.putPixel(point.x, point.y, color);
   
</span>

<span style="color: green;">// Project takes some 3D coordinates and transform them
/ in 2D coordinates using the transformation matrix
</span><span style="color: black;">Device.prototype.project = </span><span style="color: blue;">function </span><span style="color: black;">(coord, transMat) 
   </span><span style="color: blue;">var </span><span style="color: black;">point = BABYLON.Vector3.TransformCoordinates(coord, transMat);
   </span><span style="color: green;">// 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.
   </span><span style="color: blue;">var </span><span style="color: black;">x = point.x * </span><span style="color: blue;">this</span><span style="color: black;">.workingWidth + </span><span style="color: blue;">this</span><span style="color: black;">.workingWidth / 2.0 &gt;&gt; 0;
   </span><span style="color: blue;">var </span><span style="color: black;">y = -point.y * </span><span style="color: blue;">this</span><span style="color: black;">.workingHeight + </span><span style="color: blue;">this</span><span style="color: black;">.workingHeight / 2.0 &gt;&gt; 0;
   </span><span style="color: blue;">return </span><span style="color: black;">(</span><span style="color: blue;">new </span><span style="color: black;">BABYLON.Vector3(x, y, point.z));
;
</span><span style="color: green;">// drawPoint calls putPixel but does the clipping operation before
</span><span style="color: black;">Device.prototype.drawPoint = </span><span style="color: blue;">function </span><span style="color: black;">(point, color) 
   </span><span style="color: green;">// Clipping what's visible on screen
   </span><span style="color: blue;">if </span><span style="color: black;">(point.x &gt;= 0 &amp;&amp; point.y &gt;= 0 &amp;&amp; point.x &lt; </span><span style="color: blue;">this</span><span style="color: black;">.workingWidth
                                       &amp;&amp; point.y &lt; </span><span style="color: blue;">this</span><span style="color: black;">.workingHeight) 
       </span><span style="color: green;">// Drawing a yellow point
       </span><span style="color: blue;">this</span><span style="color: black;">.putPixel(point.x, point.y, color);
   
;</span>

We’re just preparing some stuff for the second part of this tutorial. Now, here is the most important part. Here is the logic that going to draw the triangles based on the previous explanations.

<span style="color: green;">// Clamping values to keep them between 0 and 1
</span><span style="color: blue;">float </span><span style="color: black;">Clamp(</span><span style="color: blue;">float </span><span style="color: black;">value, </span><span style="color: blue;">float </span><span style="color: black;">min = 0, </span><span style="color: blue;">float </span><span style="color: black;">max = 1)
   </span><span style="color: blue;">return </span><span style="color: rgb(43, 145, 175);">Math</span><span style="color: black;">.Max(min, </span><span style="color: rgb(43, 145, 175);">Math</span><span style="color: black;">.Min(value, max));
</span><span style="color: green;">// Interpolating the value between 2 vertices 
/ min is the starting point, max the ending point
/ and gradient the % between the 2 points
</span><span style="color: blue;">float </span><span style="color: black;">Interpolate(</span><span style="color: blue;">float </span><span style="color: black;">min, </span><span style="color: blue;">float </span><span style="color: black;">max, </span><span style="color: blue;">float </span><span style="color: black;">gradient)
   </span><span style="color: blue;">return </span><span style="color: black;">min + (max - min) * Clamp(gradient);
</span><span style="color: green;">// drawing line between 2 points from left to right
/ papb -&gt; pcpd
/ pa, pb, pc, pd must then be sorted before
</span><span style="color: blue;">void </span><span style="color: black;">ProcessScanLine(</span><span style="color: blue;">int </span><span style="color: black;">y, </span><span style="color: rgb(43, 145, 175);">Vector3 </span><span style="color: black;">pa, </span><span style="color: rgb(43, 145, 175);">Vector3 </span><span style="color: black;">pb, </span><span style="color: rgb(43, 145, 175);">Vector3 </span><span style="color: black;">pc, </span><span style="color: rgb(43, 145, 175);">Vector3 </span><span style="color: black;">pd, </span><span style="color: rgb(43, 145, 175);">Color4 </span><span style="color: black;">color)
   </span><span style="color: green;">// Thanks to current Y, we can compute the gradient to compute others values like
   // the starting X (sx) and ending X (ex) to draw between<br />    // if pa.Y == pb.Y or pc.Y == pd.Y, gradient is forced to 1
   </span><span style="color: blue;">var </span><span style="color: black;">gradient1 = pa.Y != pb.Y ? (y - pa.Y) / (pb.Y - pa.Y) : 1;
   </span><span style="color: blue;">var </span><span style="color: black;">gradient2 = pc.Y != pd.Y ? (y - pc.Y) / (pd.Y - pc.Y) : 1;
           
   </span><span style="color: blue;">int </span><span style="color: black;">sx = (</span><span style="color: blue;">int</span><span style="color: black;">)Interpolate(pa.X, pb.X, gradient1);
   </span><span style="color: blue;">int </span><span style="color: black;">ex = (</span><span style="color: blue;">int</span><span style="color: black;">)Interpolate(pc.X, pd.X, gradient2);
    </span><span style="color: green;">// drawing a line from left (sx) to right (ex) 
   </span><span style="color: blue;">for </span><span style="color: black;">(</span><span style="color: blue;">var </span><span style="color: black;">x = sx; x &lt; ex; x++)
   
       DrawPoint(</span><span style="color: blue;">new </span><span style="color: rgb(43, 145, 175);">Vector2</span><span style="color: black;">(x, y), color);
   
</span><span style="color: blue;">public void </span><span style="color: black;">DrawTriangle(</span><span style="color: rgb(43, 145, 175);">Vector3 </span><span style="color: black;">p1, </span><span style="color: rgb(43, 145, 175);">Vector3 </span><span style="color: black;">p2, </span><span style="color: rgb(43, 145, 175);">Vector3 </span><span style="color: black;">p3, </span><span style="color: rgb(43, 145, 175);">Color4 </span><span style="color: black;">color)
   </span><span style="color: green;">// Sorting the points in order to always have this order on screen p1, p2 &amp; p3
   // with p1 always up (thus having the Y the lowest possible to be near the top screen)
   // then p2 between p1 &amp; p3
   </span><span style="color: blue;">if </span><span style="color: black;">(p1.Y &gt; p2.Y)
   
       </span><span style="color: blue;">var </span><span style="color: black;">temp = p2;
       p2 = p1;
       p1 = temp;
   
    </span><span style="color: blue;">if </span><span style="color: black;">(p2.Y &gt; p3.Y)
   
       </span><span style="color: blue;">var </span><span style="color: black;">temp = p2;
       p2 = p3;
       p3 = temp;
   
    </span><span style="color: blue;">if </span><span style="color: black;">(p1.Y &gt; p2.Y)
   
       </span><span style="color: blue;">var </span><span style="color: black;">temp = p2;
       p2 = p1;
       p1 = temp;
   
    </span><span style="color: green;">// inverse slopes
   </span><span style="color: blue;">float </span><span style="color: black;">dP1P2, dP1P3;
    </span><span style="color: green;">// http://en.wikipedia.org/wiki/Slope
   // Computing inverse slopes
   </span><span style="color: blue;">if </span><span style="color: black;">(p2.Y - p1.Y &gt; 0)
       dP1P2 = (p2.X - p1.X) / (p2.Y - p1.Y);
   </span><span style="color: blue;">else
       </span><span style="color: black;">dP1P2 = 0;
    </span><span style="color: blue;">if </span><span style="color: black;">(p3.Y - p1.Y &gt; 0)
       dP1P3 = (p3.X - p1.X) / (p3.Y - p1.Y);
   </span><span style="color: blue;">else
       </span><span style="color: black;">dP1P3 = 0;
    </span><span style="color: green;">// First case where triangles are like that:
   // P1
   // -
   // -- 
   // - -
   // -  -
   // -   - P2
   // -  -
   // - -
   // -
   // P3
   </span><span style="color: blue;">if </span><span style="color: black;">(dP1P2 &gt; dP1P3)
   
       </span><span style="color: blue;">for </span><span style="color: black;">(</span><span style="color: blue;">var </span><span style="color: black;">y = (</span><span style="color: blue;">int</span><span style="color: black;">)p1.Y; y &lt;= (</span><span style="color: blue;">int</span><span style="color: black;">)p3.Y; y++)
       
           </span><span style="color: blue;">if </span><span style="color: black;">(y &lt; p2.Y)
           
               ProcessScanLine(y, p1, p3, p1, p2, color);
           
           </span><span style="color: blue;">else
           </span><span style="color: black;">
               ProcessScanLine(y, p1, p3, p2, p3, color);
           
       }
   }
   </span><span style="color: green;">// First case where triangles are like that:
   //       P1
   //        -
   //       -- 
   //      - -
   //     -  -
   // P2 -   - 
   //     -  -
   //      - -
   //        -
   //       P3
   </span><span style="color: blue;">else
   </span><span style="color: black;">
       </span><span style="color: blue;">for </span><span style="color: black;">(</span><span style="color: blue;">var </span><span style="color: black;">y = (</span><span style="color: blue;">int</span><span style="color: black;">)p1.Y; y &lt;= (</span><span style="color: blue;">int</span><span style="color: black;">)p3.Y; y++)
       
           </span><span style="color: blue;">if </span><span style="color: black;">(y &lt; p2.Y)
           
               ProcessScanLine(y, p1, p2, p1, p3, color);
           
           </span><span style="color: blue;">else
           </span><span style="color: black;">
               ProcessScanLine(y, p2, p3, p1, p3, color);
           
       }
   }
</span>

<span style="color: green;">// Clamping values to keep them between 0 and 1
</span><span style="color: blue;">public </span><span style="color: black;">clamp(value: </span><span style="color: blue;">number</span><span style="color: black;">, min: </span><span style="color: blue;">number </span><span style="color: black;">= 0, max: </span><span style="color: blue;">number </span><span style="color: black;">= 1): </span><span style="color: blue;">number </span><span style="color: black;">
   </span><span style="color: blue;">return </span><span style="color: black;">Math.max(min, Math.min(value, max));
</span><span style="color: green;">// Interpolating the value between 2 vertices 
/ min is the starting point, max the ending point
/ and gradient the % between the 2 points
</span><span style="color: blue;">public </span><span style="color: black;">interpolate(min: </span><span style="color: blue;">number</span><span style="color: black;">, max: </span><span style="color: blue;">number</span><span style="color: black;">, gradient: </span><span style="color: blue;">number</span><span style="color: black;">) 
   </span><span style="color: blue;">return </span><span style="color: black;">min + (max - min) * </span><span style="color: blue;">this</span><span style="color: black;">.clamp(gradient);
</span><span style="color: green;">// drawing line between 2 points from left to right
/ papb -&gt; pcpd
/ pa, pb, pc, pd must then be sorted before
</span><span style="color: blue;">public </span><span style="color: black;">processScanLine(y: </span><span style="color: blue;">number</span><span style="color: black;">, pa: BABYLON.Vector3, pb: BABYLON.Vector3, <br />                       pc: BABYLON.Vector3, pd: BABYLON.Vector3, color: BABYLON.Color4): </span><span style="color: blue;">void </span><span style="color: black;">
   </span><span style="color: green;">// Thanks to current Y, we can compute the gradient to compute others values like
   // the starting X (sx) and ending X (ex) to draw between<br />    // if pa.Y == pb.Y or pc.Y == pd.Y, gradient is forced to 1
   </span><span style="color: blue;">var </span><span style="color: black;">gradient1 = pa.y != pb.y ? (y - pa.y) / (pb.y - pa.y) : 1;
   </span><span style="color: blue;">var </span><span style="color: black;">gradient2 = pc.y != pd.y ? (y - pc.y) / (pd.y - pc.y) : 1;
    </span><span style="color: blue;">var </span><span style="color: black;">sx = </span><span style="color: blue;">this</span><span style="color: black;">.interpolate(pa.x, pb.x, gradient1) &gt;&gt; 0;
   </span><span style="color: blue;">var </span><span style="color: black;">ex = </span><span style="color: blue;">this</span><span style="color: black;">.interpolate(pc.x, pd.x, gradient2) &gt;&gt; 0;
    </span><span style="color: green;">// drawing a line from left (sx) to right (ex) 
   </span><span style="color: blue;">for </span><span style="color: black;">(</span><span style="color: blue;">var </span><span style="color: black;">x = sx; x &lt; ex; x++) 
       </span><span style="color: blue;">this</span><span style="color: black;">.drawPoint(</span><span style="color: blue;">new </span><span style="color: black;">BABYLON.Vector2(x, y), color);
   
</span><span style="color: blue;">public </span><span style="color: black;">drawTriangle(p1: BABYLON.Vector3, p2: BABYLON.Vector3, <br />                    p3: BABYLON.Vector3, color: BABYLON.Color4): </span><span style="color: blue;">void </span><span style="color: black;">
   </span><span style="color: green;">// Sorting the points in order to always have this order on screen p1, p2 &amp; p3
   // with p1 always up (thus having the Y the lowest possible to be near the top screen)
   // then p2 between p1 &amp; p3
   </span><span style="color: blue;">if </span><span style="color: black;">(p1.y &gt; p2.y) 
       </span><span style="color: blue;">var </span><span style="color: black;">temp = p2;
       p2 = p1;
       p1 = temp;
   
    </span><span style="color: blue;">if </span><span style="color: black;">(p2.y &gt; p3.y) 
       </span><span style="color: blue;">var </span><span style="color: black;">temp = p2;
       p2 = p3;
       p3 = temp;
   
    </span><span style="color: blue;">if </span><span style="color: black;">(p1.y &gt; p2.y) 
       </span><span style="color: blue;">var </span><span style="color: black;">temp = p2;
       p2 = p1;
       p1 = temp;
   
    </span><span style="color: green;">// inverse slopes
   </span><span style="color: blue;">var </span><span style="color: black;">dP1P2: </span><span style="color: blue;">number</span><span style="color: black;">; </span><span style="color: blue;">var </span><span style="color: black;">dP1P3: </span><span style="color: blue;">number</span><span style="color: black;">;
    </span><span style="color: green;">// http://en.wikipedia.org/wiki/Slope
   // Computing slopes
   </span><span style="color: blue;">if </span><span style="color: black;">(p2.y - p1.y &gt; 0)
       dP1P2 = (p2.x - p1.x) / (p2.y - p1.y);
   </span><span style="color: blue;">else
       </span><span style="color: black;">dP1P2 = 0;
    </span><span style="color: blue;">if </span><span style="color: black;">(p3.y - p1.y &gt; 0)
       dP1P3 = (p3.x - p1.x) / (p3.y - p1.y);
   </span><span style="color: blue;">else
       </span><span style="color: black;">dP1P3 = 0;
    </span><span style="color: green;">// First case where triangles are like that:
   // P1
   // -
   // -- 
   // - -
   // -  -
   // -   - P2
   // -  -
   // - -
   // -
   // P3
   </span><span style="color: blue;">if </span><span style="color: black;">(dP1P2 &gt; dP1P3) 
       </span><span style="color: blue;">for </span><span style="color: black;">(</span><span style="color: blue;">var </span><span style="color: black;">y = p1.y &gt;&gt; 0; y &lt;= p3.y &gt;&gt; 0; y++)
       
           </span><span style="color: blue;">if </span><span style="color: black;">(y &lt; p2.y) 
               </span><span style="color: blue;">this</span><span style="color: black;">.processScanLine(y, p1, p3, p1, p2, color);
           
           </span><span style="color: blue;">else </span><span style="color: black;">
               </span><span style="color: blue;">this</span><span style="color: black;">.processScanLine(y, p1, p3, p2, p3, color);
           
       
   }
   </span><span style="color: green;">// First case where triangles are like that:
   //       P1
   //        -
   //       -- 
   //      - -
   //     -  -
   // P2 -   - 
   //     -  -
   //      - -
   //        -
   //       P3
   </span><span style="color: blue;">else </span><span style="color: black;">
       </span><span style="color: blue;">for </span><span style="color: black;">(</span><span style="color: blue;">var </span><span style="color: black;">y = p1.y &gt;&gt; 0; y &lt;= p3.y &gt;&gt; 0; y++)
       
           </span><span style="color: blue;">if </span><span style="color: black;">(y &lt; p2.y) 
               </span><span style="color: blue;">this</span><span style="color: black;">.processScanLine(y, p1, p2, p1, p3, color);
           
           </span><span style="color: blue;">else </span><span style="color: black;">
               </span><span style="color: blue;">this</span><span style="color: black;">.processScanLine(y, p2, p3, p1, p3, color);
           
       }
   }
</span>

<span style="color: green;">// Clamping values to keep them between 0 and 1
</span><span style="color: black;">Device.prototype.clamp = </span><span style="color: blue;">function </span><span style="color: black;">(value, min, max) 
   </span><span style="color: blue;">if </span><span style="color: black;">(</span><span style="color: blue;">typeof </span><span style="color: black;">min === </span><span style="color: rgb(163, 21, 21);">"undefined"</span><span style="color: black;">)  min = 0; 
   </span><span style="color: blue;">if </span><span style="color: black;">(</span><span style="color: blue;">typeof </span><span style="color: black;">max === </span><span style="color: rgb(163, 21, 21);">"undefined"</span><span style="color: black;">)  max = 1; 
   </span><span style="color: blue;">return </span><span style="color: black;">Math.max(min, Math.min(value, max));
;
</span><span style="color: green;">// Interpolating the value between 2 vertices 
/ min is the starting point, max the ending point
/ and gradient the % between the 2 points
</span><span style="color: black;">Device.prototype.interpolate = </span><span style="color: blue;">function </span><span style="color: black;">(min, max, gradient) 
   </span><span style="color: blue;">return </span><span style="color: black;">min + (max - min) * </span><span style="color: blue;">this</span><span style="color: black;">.clamp(gradient);
;
</span><span style="color: green;">// drawing line between 2 points from left to right
/ papb -&gt; pcpd
/ pa, pb, pc, pd must then be sorted before
</span><span style="color: black;">Device.prototype.processScanLine = </span><span style="color: blue;">function </span><span style="color: black;">(y, pa, pb, pc, pd, color) 
   </span><span style="color: green;">// Thanks to current Y, we can compute the gradient to compute others values like
   // the starting X (sx) and ending X (ex) to draw between    
   // if pa.Y == pb.Y or pc.Y == pd.Y, gradient is forced to 1
   </span><span style="color: blue;">var </span><span style="color: black;">gradient1 = pa.y != pb.y ? (y - pa.y) / (pb.y - pa.y) : 1;
   </span><span style="color: blue;">var </span><span style="color: black;">gradient2 = pc.y != pd.y ? (y - pc.y) / (pd.y - pc.y) : 1;
    </span><span style="color: blue;">var </span><span style="color: black;">sx = </span><span style="color: blue;">this</span><span style="color: black;">.interpolate(pa.x, pb.x, gradient1) &gt;&gt; 0;
   </span><span style="color: blue;">var </span><span style="color: black;">ex = </span><span style="color: blue;">this</span><span style="color: black;">.interpolate(pc.x, pd.x, gradient2) &gt;&gt; 0;
    </span><span style="color: green;">// drawing a line from left (sx) to right (ex) 
   </span><span style="color: blue;">for</span><span style="color: black;">(</span><span style="color: blue;">var </span><span style="color: black;">x = sx; x &lt; ex; x++) 
       </span><span style="color: blue;">this</span><span style="color: black;">.drawPoint(</span><span style="color: blue;">new </span><span style="color: black;">BABYLON.Vector2(x, y), color);
   
;
Device.prototype.drawTriangle = </span><span style="color: blue;">function </span><span style="color: black;">(p1, p2, p3, color) 
   </span><span style="color: green;">// Sorting the points in order to always have this order on screen p1, p2 &amp; p3
   // with p1 always up (thus having the Y the lowest possible to be near the top screen)
   // then p2 between p1 &amp; p3
   </span><span style="color: blue;">if</span><span style="color: black;">(p1.y &gt; p2.y) 
       </span><span style="color: blue;">var </span><span style="color: black;">temp = p2;
       p2 = p1;
       p1 = temp;
   
   </span><span style="color: blue;">if</span><span style="color: black;">(p2.y &gt; p3.y) 
       </span><span style="color: blue;">var </span><span style="color: black;">temp = p2;
       p2 = p3;
       p3 = temp;
   
   </span><span style="color: blue;">if</span><span style="color: black;">(p1.y &gt; p2.y) 
       </span><span style="color: blue;">var </span><span style="color: black;">temp = p2;
       p2 = p1;
       p1 = temp;
   
    </span><span style="color: green;">// inverse slopes
   </span><span style="color: blue;">var </span><span style="color: black;">dP1P2; </span><span style="color: blue;">var </span><span style="color: black;">dP1P3;
    </span><span style="color: green;">// http://en.wikipedia.org/wiki/Slope
   // Computing slopes
   </span><span style="color: blue;">if</span><span style="color: black;">(p2.y - p1.y &gt; 0) 
       dP1P2 = (p2.x - p1.x) / (p2.y - p1.y);
    </span><span style="color: blue;">else </span><span style="color: black;">
       dP1P2 = 0;
   
    </span><span style="color: blue;">if</span><span style="color: black;">(p3.y - p1.y &gt; 0) 
       dP1P3 = (p3.x - p1.x) / (p3.y - p1.y);
    </span><span style="color: blue;">else </span><span style="color: black;">
       dP1P3 = 0;
   
    </span><span style="color: green;">// First case where triangles are like that:
   // P1
   // -
   // -- 
   // - -
   // -  -
   // -   - P2
   // -  -
   // - -
   // -
   // P3
   </span><span style="color: blue;">if</span><span style="color: black;">(dP1P2 &gt; dP1P3) 
       </span><span style="color: blue;">for</span><span style="color: black;">(</span><span style="color: blue;">var </span><span style="color: black;">y = p1.y &gt;&gt; 0; y &lt;= p3.y &gt;&gt; 0; y++) 
           </span><span style="color: blue;">if</span><span style="color: black;">(y &lt; p2.y) 
               </span><span style="color: blue;">this</span><span style="color: black;">.processScanLine(y, p1, p3, p1, p2, color);
            </span><span style="color: blue;">else </span><span style="color: black;">
               </span><span style="color: blue;">this</span><span style="color: black;">.processScanLine(y, p1, p3, p2, p3, color);
           
       
   }
   </span><span style="color: green;">// First case where triangles are like that:
   //       P1
   //        -
   //       -- 
   //      - -
   //     -  -
   // P2 -   - 
   //     -  -
   //      - -
   //        -
   //       P3
   </span><span style="color: blue;">else </span><span style="color: black;">
       </span><span style="color: blue;">for</span><span style="color: black;">(</span><span style="color: blue;">var </span><span style="color: black;">y = p1.y &gt;&gt; 0; y &lt;= p3.y &gt;&gt; 0; y++) 
           </span><span style="color: blue;">if</span><span style="color: black;">(y &lt; p2.y) 
               </span><span style="color: blue;">this</span><span style="color: black;">.processScanLine(y, p1, p2, p1, p3, color);
            </span><span style="color: blue;">else </span><span style="color: black;">
               </span><span style="color: blue;">this</span><span style="color: black;">.processScanLine(y, p2, p3, p1, p3, color);
           
       }
   }
;</span>

You see in the code how we’re handling the 2 types of triangles to fill as well as the 2 steps in the scan line process.

Finally, you need to update the render function to call drawTriangle instead of the 3 calls to drawLine/drawBline. We’re also using a level of grey to draw each triangle. Otherwise, if we draw every of them with the same color, we wouldn’t be able to really see what’s going on. We’ll see in the next tutorial how to handle a light in a proper way.

<span style="color: blue;">var </span><span style="color: black;">faceIndex = 0;
</span><span style="color: blue;">foreach </span><span style="color: black;">(</span><span style="color: blue;">var </span><span style="color: black;">face </span><span style="color: blue;">in </span><span style="color: black;">mesh.Faces)
   </span><span style="color: blue;">var </span><span style="color: black;">vertexA = mesh.Verticesface.A;
   </span><span style="color: blue;">var </span><span style="color: black;">vertexB = mesh.Verticesface.B;
   </span><span style="color: blue;">var </span><span style="color: black;">vertexC = mesh.Verticesface.C;
    </span><span style="color: blue;">var </span><span style="color: black;">pixelA = Project(vertexA, transformMatrix);
   </span><span style="color: blue;">var </span><span style="color: black;">pixelB = Project(vertexB, transformMatrix);
   </span><span style="color: blue;">var </span><span style="color: black;">pixelC = Project(vertexC, transformMatrix);
    </span><span style="color: blue;">var </span><span style="color: black;">color = 0.25f + (faceIndex % mesh.Faces.Length) * 0.75f / mesh.Faces.Length;
   DrawTriangle(pixelA, pixelB, pixelC, </span><span style="color: blue;">new </span><span style="color: rgb(43, 145, 175);">Color4</span><span style="color: black;">(color, color, color, 1));
   faceIndex++;
</span>

<span style="color: blue;">for </span><span style="color: black;">(</span><span style="color: blue;">var </span><span style="color: black;">indexFaces = 0; indexFaces &lt; cMesh.Faces.length; indexFaces++) 
   </span><span style="color: blue;">var </span><span style="color: black;">currentFace = cMesh.FacesindexFaces;
   </span><span style="color: blue;">var </span><span style="color: black;">vertexA = cMesh.VerticescurrentFace.A;
   </span><span style="color: blue;">var </span><span style="color: black;">vertexB = cMesh.VerticescurrentFace.B;
   </span><span style="color: blue;">var </span><span style="color: black;">vertexC = cMesh.VerticescurrentFace.C;
    </span><span style="color: blue;">var </span><span style="color: black;">pixelA = </span><span style="color: blue;">this</span><span style="color: black;">.project(vertexA, transformMatrix);
   </span><span style="color: blue;">var </span><span style="color: black;">pixelB = </span><span style="color: blue;">this</span><span style="color: black;">.project(vertexB, transformMatrix);
   </span><span style="color: blue;">var </span><span style="color: black;">pixelC = </span><span style="color: blue;">this</span><span style="color: black;">.project(vertexC, transformMatrix);
    </span><span style="color: blue;">var </span><span style="color: black;">color: </span><span style="color: blue;">number </span><span style="color: black;">= 0.25 + ((indexFaces % cMesh.Faces.length) / cMesh.Faces.length) * 0.75;
   </span><span style="color: blue;">this</span><span style="color: black;">.drawTriangle(pixelA, pixelB, pixelC, </span><span style="color: blue;">new </span><span style="color: black;">BABYLON.Color4(color, color, color, 1));
</span>

<span style="color: blue;">for </span><span style="color: black;">(</span><span style="color: blue;">var </span><span style="color: black;">indexFaces = 0; indexFaces &lt; cMesh.Faces.length; indexFaces++) 
   </span><span style="color: blue;">var </span><span style="color: black;">currentFace = cMesh.FacesindexFaces;
   </span><span style="color: blue;">var </span><span style="color: black;">vertexA = cMesh.VerticescurrentFace.A;
   </span><span style="color: blue;">var </span><span style="color: black;">vertexB = cMesh.VerticescurrentFace.B;
   </span><span style="color: blue;">var </span><span style="color: black;">vertexC = cMesh.VerticescurrentFace.C;
    </span><span style="color: blue;">var </span><span style="color: black;">pixelA = </span><span style="color: blue;">this</span><span style="color: black;">.project(vertexA, transformMatrix);
   </span><span style="color: blue;">var </span><span style="color: black;">pixelB = </span><span style="color: blue;">this</span><span style="color: black;">.project(vertexB, transformMatrix);
   </span><span style="color: blue;">var </span><span style="color: black;">pixelC = </span><span style="color: blue;">this</span><span style="color: black;">.project(vertexC, transformMatrix);
    </span><span style="color: blue;">var </span><span style="color: black;">color = 0.25 + ((indexFaces % cMesh.Faces.length) / cMesh.Faces.length) * 0.75;
   </span><span style="color: blue;">this</span><span style="color: black;">.drawTriangle(pixelA, pixelB, pixelC, </span><span style="color: blue;">new </span><span style="color: black;">BABYLON.Color4(color, color, color, 1));
</span>

And you should have this first result:

What’s going wrong there? You’ve probably got the feeling that you can watch through the mesh. This is because we’re drawing all triangles without “hiding” the triangles living in the back.

Z-Buffering or how to use a depth Buffer

We then need to test the Z value of the current pixel and compare it to a buffer before drawing it. If the Z of the current pixel to draw is lower than the previous pixel that was drawn here, we can override it. Indeed, this would mean that the current face we’re drawing is in front of a previously drawn face. However, if the Z of the current pixel to draw is greater than the previous pixel drawn here, we can discard the draw operation.

We then need to keep an history of these Z indexes per pixel on screen. To do that, declare a new array of float, named it depthBuffer. Its size will be equal to the number of pixels on screen (width * height). This depth buffer must be initialized during each clear() operation with a very high default Z value.

In the putPixel function/method, we just need to test the Z index of the pixel against the one that was stored in the depth buffer. Moreover, part of our previous logic was returning Vector2 to logically draw on screen. We’re going to change it to Vector3 to push the Z values of the vertices as we now need this information to be able to draw faces correctly.

Finally, in the same way we were interpolating X value between each side of the triangles, we need to interpolate also Z values using the very same algorithm for each pixel.

In conclusion, here is the code you need to update in your Device object:

<span style="color: blue;">private byte</span><span style="color: black;">[] backBuffer;
</span><span style="color: blue;">private readonly float</span><span style="color: black;">[] depthBuffer;
</span><span style="color: blue;">private </span><span style="color: rgb(43, 145, 175);">WriteableBitmap </span><span style="color: black;">bmp;
</span><span style="color: blue;">private readonly int </span><span style="color: black;">renderWidth;
</span><span style="color: blue;">private readonly int </span><span style="color: black;">renderHeight;
</span><span style="color: blue;">public </span><span style="color: black;">Device(</span><span style="color: rgb(43, 145, 175);">WriteableBitmap </span><span style="color: black;">bmp)
   </span><span style="color: blue;">this</span><span style="color: black;">.bmp = bmp;
   renderWidth = bmp.PixelWidth;
   renderHeight = bmp.PixelHeight;
    </span><span style="color: green;">// the back buffer size is equal to the number of pixels to draw
   // on screen (width*height) * 4 (R,G,B &amp; Alpha values). 
   </span><span style="color: black;">backBuffer = </span><span style="color: blue;">new byte</span><span style="color: black;">bmp.PixelWidth * bmp.PixelHeight * 4;
   depthBuffer = </span><span style="color: blue;">new float</span><span style="color: black;">bmp.PixelWidth * bmp.PixelHeight;
</span><span style="color: green;">// This method is called to clear the back buffer with a specific color
</span><span style="color: blue;">public void </span><span style="color: black;">Clear(</span><span style="color: blue;">byte </span><span style="color: black;">r, </span><span style="color: blue;">byte </span><span style="color: black;">g, </span><span style="color: blue;">byte </span><span style="color: black;">b, </span><span style="color: blue;">byte </span><span style="color: black;">a) 
   </span><span style="color: green;">// Clearing Back Buffer
   </span><span style="color: blue;">for </span><span style="color: black;">(</span><span style="color: blue;">var </span><span style="color: black;">index = 0; index &lt; backBuffer.Length; index += 4)
   
       </span><span style="color: green;">// BGRA is used by Windows instead by RGBA in HTML5
       </span><span style="color: black;">backBufferindex = b;
       backBufferindex + 1 = g;
       backBufferindex + 2 = r;
       backBufferindex + 3 = a;
   
    </span><span style="color: green;">// Clearing Depth Buffer
   </span><span style="color: blue;">for </span><span style="color: black;">(</span><span style="color: blue;">var </span><span style="color: black;">index = 0; index &lt; depthBuffer.Length; index++)
   
       depthBufferindex = </span><span style="color: blue;">float</span><span style="color: black;">.MaxValue;
   
</span><span style="color: green;">// Called to put a pixel on screen at a specific X,Y coordinates
</span><span style="color: blue;">public void </span><span style="color: black;">PutPixel(</span><span style="color: blue;">int </span><span style="color: black;">x, </span><span style="color: blue;">int </span><span style="color: black;">y, </span><span style="color: blue;">float </span><span style="color: black;">z, </span><span style="color: rgb(43, 145, 175);">Color4 </span><span style="color: black;">color)
   </span><span style="color: green;">// As we have a 1-D Array for our back buffer
   // we need to know the equivalent cell in 1-D based
   // on the 2D coordinates on screen
   </span><span style="color: blue;">var </span><span style="color: black;">index = (x + y * renderWidth);
   </span><span style="color: blue;">var </span><span style="color: black;">index4 = index * 4;
    </span><span style="color: blue;">if </span><span style="color: black;">(depthBufferindex &lt; z)
   
       </span><span style="color: blue;">return</span><span style="color: black;">; </span><span style="color: green;">// Discard
   </span><span style="color: black;">
    depthBufferindex = z;
    backBufferindex4 = (</span><span style="color: blue;">byte</span><span style="color: black;">)(color.Blue * 255);
   backBufferindex4 + 1 = (</span><span style="color: blue;">byte</span><span style="color: black;">)(color.Green * 255);
   backBufferindex4 + 2 = (</span><span style="color: blue;">byte</span><span style="color: black;">)(color.Red * 255);
   backBufferindex4 + 3 = (</span><span style="color: blue;">byte</span><span style="color: black;">)(color.Alpha * 255);
</span><span style="color: green;">// Project takes some 3D coordinates and transform them
/ in 2D coordinates using the transformation matrix
</span><span style="color: blue;">public </span><span style="color: rgb(43, 145, 175);">Vector3 </span><span style="color: black;">Project(</span><span style="color: rgb(43, 145, 175);">Vector3 </span><span style="color: black;">coord, </span><span style="color: rgb(43, 145, 175);">Matrix </span><span style="color: black;">transMat)
   </span><span style="color: green;">// transforming the coordinates
   </span><span style="color: blue;">var </span><span style="color: black;">point = </span><span style="color: rgb(43, 145, 175);">Vector3</span><span style="color: black;">.TransformCoordinate(coord, transMat);
   </span><span style="color: green;">// 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.
   </span><span style="color: blue;">var </span><span style="color: black;">x = point.X * bmp.PixelWidth + bmp.PixelWidth / 2.0f;
   </span><span style="color: blue;">var </span><span style="color: black;">y = -point.Y * bmp.PixelHeight + bmp.PixelHeight / 2.0f;
   </span><span style="color: blue;">return </span><span style="color: black;">(</span><span style="color: blue;">new </span><span style="color: rgb(43, 145, 175);">Vector3</span><span style="color: black;">(x, y, point.Z));
</span><span style="color: green;">// DrawPoint calls PutPixel but does the clipping operation before
</span><span style="color: blue;">public void </span><span style="color: black;">DrawPoint(</span><span style="color: rgb(43, 145, 175);">Vector3 </span><span style="color: black;">point, </span><span style="color: rgb(43, 145, 175);">Color4 </span><span style="color: black;">color)
   </span><span style="color: green;">// Clipping what's visible on screen
   </span><span style="color: blue;">if </span><span style="color: black;">(point.X &gt;= 0 &amp;&amp; point.Y &gt;= 0 &amp;&amp; point.X &lt; bmp.PixelWidth &amp;&amp; point.Y &lt; bmp.PixelHeight)
   
       </span><span style="color: green;">// Drawing a point
       </span><span style="color: black;">PutPixel((</span><span style="color: blue;">int</span><span style="color: black;">)point.X, (</span><span style="color: blue;">int</span><span style="color: black;">)point.Y, point.Z ,color);
   
</span><span style="color: green;">// drawing line between 2 points from left to right
/ papb -&gt; pcpd
/ pa, pb, pc, pd must then be sorted before
</span><span style="color: blue;">void </span><span style="color: black;">ProcessScanLine(</span><span style="color: blue;">int </span><span style="color: black;">y, </span><span style="color: rgb(43, 145, 175);">Vector3 </span><span style="color: black;">pa, </span><span style="color: rgb(43, 145, 175);">Vector3 </span><span style="color: black;">pb, </span><span style="color: rgb(43, 145, 175);">Vector3 </span><span style="color: black;">pc, </span><span style="color: rgb(43, 145, 175);">Vector3 </span><span style="color: black;">pd, </span><span style="color: rgb(43, 145, 175);">Color4 </span><span style="color: black;">color)
   </span><span style="color: green;">// Thanks to current Y, we can compute the gradient to compute others values like
   // the starting X (sx) and ending X (ex) to draw between
   // if pa.Y == pb.Y or pc.Y == pd.Y, gradient is forced to 1
   </span><span style="color: blue;">var </span><span style="color: black;">gradient1 = pa.Y != pb.Y ? (y - pa.Y) / (pb.Y - pa.Y) : 1;
   </span><span style="color: blue;">var </span><span style="color: black;">gradient2 = pc.Y != pd.Y ? (y - pc.Y) / (pd.Y - pc.Y) : 1;
    </span><span style="color: blue;">int </span><span style="color: black;">sx = (</span><span style="color: blue;">int</span><span style="color: black;">)Interpolate(pa.X, pb.X, gradient1);
   </span><span style="color: blue;">int </span><span style="color: black;">ex = (</span><span style="color: blue;">int</span><span style="color: black;">)Interpolate(pc.X, pd.X, gradient2);
    </span><span style="color: green;">// starting Z &amp; ending Z
   </span><span style="color: blue;">float </span><span style="color: black;">z1 = Interpolate(pa.Z, pb.Z, gradient1);
   </span><span style="color: blue;">float </span><span style="color: black;">z2 = Interpolate(pc.Z, pd.Z, gradient2);
    </span><span style="color: green;">// drawing a line from left (sx) to right (ex) 
   </span><span style="color: blue;">for </span><span style="color: black;">(</span><span style="color: blue;">var </span><span style="color: black;">x = sx; x &lt; ex; x++)
   
       </span><span style="color: blue;">float </span><span style="color: black;">gradient = (x - sx) / (</span><span style="color: blue;">float</span><span style="color: black;">)(ex - sx);
        </span><span style="color: blue;">var </span><span style="color: black;">z = Interpolate(z1, z2, gradient);
       DrawPoint(</span><span style="color: blue;">new </span><span style="color: rgb(43, 145, 175);">Vector3</span><span style="color: black;">(x, y, z), color);
   
</span>

<span style="color: green;">// the back buffer size is equal to the number of pixels to draw
/ on screen (width*height) * 4 (R,G,B &amp; Alpha values). 
</span><span style="color: blue;">private </span><span style="color: black;">backbuffer: ImageData;
</span><span style="color: blue;">private </span><span style="color: black;">workingCanvas: HTMLCanvasElement;
</span><span style="color: blue;">private </span><span style="color: black;">workingContext: CanvasRenderingContext2D;
</span><span style="color: blue;">private </span><span style="color: black;">workingWidth: </span><span style="color: blue;">number</span><span style="color: black;">;
</span><span style="color: blue;">private </span><span style="color: black;">workingHeight: </span><span style="color: blue;">number</span><span style="color: black;">;
</span><span style="color: green;">// equals to backbuffer.data
</span><span style="color: blue;">private </span><span style="color: black;">backbufferdata;
</span><span style="color: blue;">private </span><span style="color: black;">depthbuffer: </span><span style="color: blue;">number</span><span style="color: black;">[];
</span><span style="color: blue;">constructor</span><span style="color: black;">(canvas: HTMLCanvasElement) 
   </span><span style="color: blue;">this</span><span style="color: black;">.workingCanvas = canvas;
   </span><span style="color: blue;">this</span><span style="color: black;">.workingWidth = canvas.width;
   </span><span style="color: blue;">this</span><span style="color: black;">.workingHeight = canvas.height;
   </span><span style="color: blue;">this</span><span style="color: black;">.workingContext = </span><span style="color: blue;">this</span><span style="color: black;">.workingCanvas.getContext(</span><span style="color: rgb(163, 21, 21);">"2d"</span><span style="color: black;">);
   </span><span style="color: blue;">this</span><span style="color: black;">.depthbuffer = </span><span style="color: blue;">new </span><span style="color: black;">Array(</span><span style="color: blue;">this</span><span style="color: black;">.workingWidth * </span><span style="color: blue;">this</span><span style="color: black;">.workingHeight);
</span><span style="color: green;">// This function is called to clear the back buffer with a specific color
</span><span style="color: blue;">public </span><span style="color: black;">clear(): </span><span style="color: blue;">void </span><span style="color: black;">
   </span><span style="color: green;">// Clearing with black color by default
   </span><span style="color: blue;">this</span><span style="color: black;">.workingContext.clearRect(0, 0, </span><span style="color: blue;">this</span><span style="color: black;">.workingWidth, </span><span style="color: blue;">this</span><span style="color: black;">.workingHeight);
   </span><span style="color: green;">// once cleared with black pixels, we're getting back the associated image data to 
   // clear out back buffer
   </span><span style="color: blue;">this</span><span style="color: black;">.backbuffer = </span><span style="color: blue;">this</span><span style="color: black;">.workingContext.getImageData(0, 0, </span><span style="color: blue;">this</span><span style="color: black;">.workingWidth, </span><span style="color: blue;">this</span><span style="color: black;">.workingHeight);
    </span><span style="color: green;">// Clearing depth buffer
   </span><span style="color: blue;">for </span><span style="color: black;">(</span><span style="color: blue;">var </span><span style="color: black;">i = 0; i &lt; </span><span style="color: blue;">this</span><span style="color: black;">.depthbuffer.length; i++) 
       </span><span style="color: green;">// Max possible value 
       </span><span style="color: blue;">this</span><span style="color: black;">.depthbufferi = 10000000;
   
</span><span style="color: green;">// Called to put a pixel on screen at a specific X,Y coordinates
</span><span style="color: blue;">public </span><span style="color: black;">putPixel(x: </span><span style="color: blue;">number</span><span style="color: black;">, y: </span><span style="color: blue;">number</span><span style="color: black;">, z: </span><span style="color: blue;">number</span><span style="color: black;">, color: BABYLON.Color4): </span><span style="color: blue;">void </span><span style="color: black;">{
   </span><span style="color: blue;">this</span><span style="color: black;">.backbufferdata = </span><span style="color: blue;">this</span><span style="color: black;">.backbuffer.data;
   </span><span style="color: green;">// As we have a 1-D Array for our back buffer
   // we need to know the equivalent cell index in 1-D based
   // on the 2D coordinates of the screen
   </span><span style="color: blue;">var </span><span style="color: black;">index: </span><span style="color: blue;">number </span><span style="color: black;">= ((x &gt;&gt; 0) + (y &gt;&gt; 0) * </span><span style="color: blue;">this</span><span style="color: black;">.workingWidth);
   </span><span style="color: blue;">var </span><span style="color: black;">index4: </span><span style="color: blue;">number </span><span style="color: black;">= index * 4;
    </span><span style="color: blue;">if </span><span style="color: black;">(</span><span style="color: blue;">this</span><span style="color: black;">.depthbufferindex &lt; z) 
       </span><span style="color: blue;">return</span><span style="color: black;">; </span><span style="color: green;">// Discard
   </span><span style="color: black;">
    </span><span style="color: blue;">this</span><span style="color: black;">.depthbufferindex = z;
    </span><span style="color: green;">// RGBA color space is used by the HTML5 canvas 
   </span><span style="color: blue;">this</span><span style="color: black;">.backbufferdataindex4 = color.r * 255;
   </span><span style="color: blue;">this</span><span style="color: black;">.backbufferdataindex4 + 1 = color.g * 255;
   </span><span style="color: blue;">this</span><span style="color: black;">.backbufferdataindex4 + 2 = color.b * 255;
   </span><span style="color: blue;">this</span><span style="color: black;">.backbufferdataindex4 + 3 = color.a * 255;
</span><span style="color: green;">// Project takes some 3D coordinates and transform them
/ in 2D coordinates using the transformation matrix
</span><span style="color: blue;">public </span><span style="color: black;">project(coord: BABYLON.Vector3, transMat: BABYLON.Matrix): BABYLON.Vector3 
   </span><span style="color: green;">// transforming the coordinates
   </span><span style="color: blue;">var </span><span style="color: black;">point = BABYLON.Vector3.TransformCoordinates(coord, transMat);
   </span><span style="color: green;">// 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.
   </span><span style="color: blue;">var </span><span style="color: black;">x = point.x * </span><span style="color: blue;">this</span><span style="color: black;">.workingWidth + </span><span style="color: blue;">this</span><span style="color: black;">.workingWidth / 2.0;
   </span><span style="color: blue;">var </span><span style="color: black;">y = -point.y * </span><span style="color: blue;">this</span><span style="color: black;">.workingHeight + </span><span style="color: blue;">this</span><span style="color: black;">.workingHeight / 2.0;
   </span><span style="color: blue;">return </span><span style="color: black;">(</span><span style="color: blue;">new </span><span style="color: black;">BABYLON.Vector3(x, y, point.z));
</span><span style="color: green;">// drawPoint calls putPixel but does the clipping operation before
</span><span style="color: blue;">public </span><span style="color: black;">drawPoint(point: BABYLON.Vector3, color: BABYLON.Color4): </span><span style="color: blue;">void </span><span style="color: black;">
   </span><span style="color: green;">// Clipping what's visible on screen
   </span><span style="color: blue;">if </span><span style="color: black;">(point.x &gt;= 0 &amp;&amp; point.y &gt;= 0 &amp;&amp; point.x &lt; </span><span style="color: blue;">this</span><span style="color: black;">.workingWidth &amp;&amp; point.y &lt; </span><span style="color: blue;">this</span><span style="color: black;">.workingHeight) 
       </span><span style="color: green;">// Drawing a yellow point
       </span><span style="color: blue;">this</span><span style="color: black;">.putPixel(point.x, point.y, point.z, color);
   
</span><span style="color: green;">// drawing line between 2 points from left to right
/ papb -&gt; pcpd
/ pa, pb, pc, pd must then be sorted before
</span><span style="color: blue;">public </span><span style="color: black;">processScanLine(y: </span><span style="color: blue;">number</span><span style="color: black;">, pa: BABYLON.Vector3, pb: BABYLON.Vector3, pc: BABYLON.Vector3, pd: BABYLON.Vector3, color: BABYLON.Color4): </span><span style="color: blue;">void </span><span style="color: black;">
   </span><span style="color: green;">// Thanks to current Y, we can compute the gradient to compute others values like
   // the starting X (sx) and ending X (ex) to draw between
   // if pa.Y == pb.Y or pc.Y == pd.Y, gradient is forced to 1
   </span><span style="color: blue;">var </span><span style="color: black;">gradient1 = pa.y != pb.y ? (y - pa.y) / (pb.y - pa.y) : 1;
   </span><span style="color: blue;">var </span><span style="color: black;">gradient2 = pc.y != pd.y ? (y - pc.y) / (pd.y - pc.y) : 1;
    </span><span style="color: blue;">var </span><span style="color: black;">sx = </span><span style="color: blue;">this</span><span style="color: black;">.interpolate(pa.x, pb.x, gradient1) &gt;&gt; 0;
   </span><span style="color: blue;">var </span><span style="color: black;">ex = </span><span style="color: blue;">this</span><span style="color: black;">.interpolate(pc.x, pd.x, gradient2) &gt;&gt; 0;
    </span><span style="color: green;">// starting Z &amp; ending Z
   </span><span style="color: blue;">var </span><span style="color: black;">z1: </span><span style="color: blue;">number </span><span style="color: black;">= </span><span style="color: blue;">this</span><span style="color: black;">.interpolate(pa.z, pb.z, gradient1);
   </span><span style="color: blue;">var </span><span style="color: black;">z2: </span><span style="color: blue;">number </span><span style="color: black;">= </span><span style="color: blue;">this</span><span style="color: black;">.interpolate(pc.z, pd.z, gradient2);
    </span><span style="color: green;">// drawing a line from left (sx) to right (ex) 
   </span><span style="color: blue;">for </span><span style="color: black;">(</span><span style="color: blue;">var </span><span style="color: black;">x = sx; x &lt; ex; x++) 
       </span><span style="color: blue;">var </span><span style="color: black;">gradient: </span><span style="color: blue;">number </span><span style="color: black;">= (x - sx) / (ex - sx); </span><span style="color: green;">// normalisation pour dessiner de gauche à droite
        </span><span style="color: blue;">var </span><span style="color: black;">z = </span><span style="color: blue;">this</span><span style="color: black;">.interpolate(z1, z2, gradient);
        </span><span style="color: blue;">this</span><span style="color: black;">.drawPoint(</span><span style="color: blue;">new </span><span style="color: black;">BABYLON.Vector3(x, y, z), color);
   
</span>

<span style="color: blue;">function </span><span style="color: black;">Device(canvas) 
   </span><span style="color: blue;">this</span><span style="color: black;">.workingCanvas = canvas;
   </span><span style="color: blue;">this</span><span style="color: black;">.workingWidth = canvas.width;
   </span><span style="color: blue;">this</span><span style="color: black;">.workingHeight = canvas.height;
   </span><span style="color: blue;">this</span><span style="color: black;">.workingContext = </span><span style="color: blue;">this</span><span style="color: black;">.workingCanvas.getContext(</span><span style="color: rgb(163, 21, 21);">"2d"</span><span style="color: black;">);
   </span><span style="color: blue;">this</span><span style="color: black;">.depthbuffer = </span><span style="color: blue;">new </span><span style="color: black;">Array(</span><span style="color: blue;">this</span><span style="color: black;">.workingWidth * </span><span style="color: blue;">this</span><span style="color: black;">.workingHeight);
</span><span style="color: green;">// This function is called to clear the back buffer with a specific color
</span><span style="color: black;">Device.prototype.clear = </span><span style="color: blue;">function </span><span style="color: black;">() 
   </span><span style="color: green;">// Clearing with black color by default
   </span><span style="color: blue;">this</span><span style="color: black;">.workingContext.clearRect(0, 0, </span><span style="color: blue;">this</span><span style="color: black;">.workingWidth, </span><span style="color: blue;">this</span><span style="color: black;">.workingHeight);
   </span><span style="color: green;">// once cleared with black pixels, we're getting back the associated image data to 
   // clear out back buffer
   </span><span style="color: blue;">this</span><span style="color: black;">.backbuffer = </span><span style="color: blue;">this</span><span style="color: black;">.workingContext.getImageData(0, 0, </span><span style="color: blue;">this</span><span style="color: black;">.workingWidth, </span><span style="color: blue;">this</span><span style="color: black;">.workingHeight);
    </span><span style="color: green;">// Clearing depth buffer
   </span><span style="color: blue;">for </span><span style="color: black;">(</span><span style="color: blue;">var </span><span style="color: black;">i = 0; i &lt; </span><span style="color: blue;">this</span><span style="color: black;">.depthbuffer.length; i++) 
       </span><span style="color: green;">// Max possible value 
       </span><span style="color: blue;">this</span><span style="color: black;">.depthbufferi = 10000000;
   
;
</span><span style="color: green;">// Called to put a pixel on screen at a specific X,Y coordinates
</span><span style="color: black;">Device.prototype.putPixel = </span><span style="color: blue;">function </span><span style="color: black;">(x, y, z, color) {
   </span><span style="color: blue;">this</span><span style="color: black;">.backbufferdata = </span><span style="color: blue;">this</span><span style="color: black;">.backbuffer.data;
   </span><span style="color: green;">// As we have a 1-D Array for our back buffer
   // we need to know the equivalent cell index in 1-D based
   // on the 2D coordinates of the screen
   </span><span style="color: blue;">var </span><span style="color: black;">index = ((x &gt;&gt; 0) + (y &gt;&gt; 0) * </span><span style="color: blue;">this</span><span style="color: black;">.workingWidth);
   </span><span style="color: blue;">var </span><span style="color: black;">index4 = index * 4;
    </span><span style="color: blue;">if</span><span style="color: black;">(</span><span style="color: blue;">this</span><span style="color: black;">.depthbufferindex &lt; z) 
       </span><span style="color: blue;">return</span><span style="color: black;">; </span><span style="color: green;">// Discard
   </span><span style="color: black;">
    </span><span style="color: blue;">this</span><span style="color: black;">.depthbufferindex = z;
    </span><span style="color: green;">// RGBA color space is used by the HTML5 canvas 
   </span><span style="color: blue;">this</span><span style="color: black;">.backbufferdataindex4 = color.r * 255;
   </span><span style="color: blue;">this</span><span style="color: black;">.backbufferdataindex4 + 1 = color.g * 255;
   </span><span style="color: blue;">this</span><span style="color: black;">.backbufferdataindex4 + 2 = color.b * 255;
   </span><span style="color: blue;">this</span><span style="color: black;">.backbufferdataindex4 + 3 = color.a * 255;
;
</span><span style="color: green;">// Project takes some 3D coordinates and transform them
/ in 2D coordinates using the transformation matrix
</span><span style="color: black;">Device.prototype.project = </span><span style="color: blue;">function </span><span style="color: black;">(coord, transMat) 
   </span><span style="color: green;">// transforming the coordinates
   </span><span style="color: blue;">var </span><span style="color: black;">point = BABYLON.Vector3.TransformCoordinates(coord, transMat);
   </span><span style="color: green;">// 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.
   </span><span style="color: blue;">var </span><span style="color: black;">x = point.x * </span><span style="color: blue;">this</span><span style="color: black;">.workingWidth + </span><span style="color: blue;">this</span><span style="color: black;">.workingWidth / 2.0;
   </span><span style="color: blue;">var </span><span style="color: black;">y = -point.y * </span><span style="color: blue;">this</span><span style="color: black;">.workingHeight + </span><span style="color: blue;">this</span><span style="color: black;">.workingHeight / 2.0;
   </span><span style="color: blue;">return </span><span style="color: black;">(</span><span style="color: blue;">new </span><span style="color: black;">BABYLON.Vector3(x, y, point.z));
;
</span><span style="color: green;">// drawPoint calls putPixel but does the clipping operation before
</span><span style="color: black;">Device.prototype.drawPoint = </span><span style="color: blue;">function </span><span style="color: black;">(point, color) 
   </span><span style="color: green;">// Clipping what's visible on screen
   </span><span style="color: blue;">if</span><span style="color: black;">(point.x &gt;= 0 &amp;&amp; point.y &gt;= 0 &amp;&amp; point.x &lt; </span><span style="color: blue;">this</span><span style="color: black;">.workingWidth &amp;&amp; point.y &lt; </span><span style="color: blue;">this</span><span style="color: black;">.workingHeight) 
       </span><span style="color: green;">// Drawing a point
       </span><span style="color: blue;">this</span><span style="color: black;">.putPixel(point.x, point.y, point.z, color);
   
;
</span><span style="color: green;">// drawing line between 2 points from left to right
/ papb -&gt; pcpd
/ pa, pb, pc, pd must then be sorted before
</span><span style="color: black;">Device.prototype.processScanLine = </span><span style="color: blue;">function </span><span style="color: black;">(y, pa, pb, pc, pd, color) 
   </span><span style="color: green;">// Thanks to current Y, we can compute the gradient to compute others values like
   // the starting X (sx) and ending X (ex) to draw between
   // if pa.Y == pb.Y or pc.Y == pd.Y, gradient is forced to 1
   </span><span style="color: blue;">var </span><span style="color: black;">gradient1 = pa.y != pb.y ? (y - pa.y) / (pb.y - pa.y) : 1;
   </span><span style="color: blue;">var </span><span style="color: black;">gradient2 = pc.y != pd.y ? (y - pc.y) / (pd.y - pc.y) : 1;
    </span><span style="color: blue;">var </span><span style="color: black;">sx = </span><span style="color: blue;">this</span><span style="color: black;">.interpolate(pa.x, pb.x, gradient1) &gt;&gt; 0;
   </span><span style="color: blue;">var </span><span style="color: black;">ex = </span><span style="color: blue;">this</span><span style="color: black;">.interpolate(pc.x, pd.x, gradient2) &gt;&gt; 0;
    </span><span style="color: green;">// starting Z &amp; ending Z
   </span><span style="color: blue;">var </span><span style="color: black;">z1 = </span><span style="color: blue;">this</span><span style="color: black;">.interpolate(pa.z, pb.z, gradient1);
   </span><span style="color: blue;">var </span><span style="color: black;">z2 = </span><span style="color: blue;">this</span><span style="color: black;">.interpolate(pc.z, pd.z, gradient2);
    </span><span style="color: green;">// drawing a line from left (sx) to right (ex) 
   </span><span style="color: blue;">for</span><span style="color: black;">(</span><span style="color: blue;">var </span><span style="color: black;">x = sx; x &lt; ex; x++) 
       </span><span style="color: blue;">var </span><span style="color: black;">gradient = (x - sx) / (ex - sx);
       </span><span style="color: blue;">var </span><span style="color: black;">z = </span><span style="color: blue;">this</span><span style="color: black;">.interpolate(z1, z2, gradient);
       </span><span style="color: blue;">this</span><span style="color: black;">.drawPoint(</span><span style="color: blue;">new </span><span style="color: black;">BABYLON.Vector3(x, y, z), color);
   
;</span>

Using this new code, you should obtain the same kind of rendering as the iframe embedded at the very top of this article.

As usual, you can download the solutions containing the source code:

C# : SoftEngineCSharpPart4.zip

- TypeScript : SoftEngineTSPart4.zip

- JavaScript : SoftEngineJSPart4.zip or simply right-click –> view source on the first embedded iframe

In the fifth tutorial, we’ll see how to simulate lighting thanks to the Gouraud Shading and we will obtain this kind of rendering:

image

But before that, I have an extra bonus tutorial for you on Optimizing & Parallelism, explaining how to boost the current algorithm thanks to Parallel.For in C# and why we can’t have the same optimization in JavaScript. Look out for that tomorrow.

Originally published: http://blogs.msdn.com/b/davrous/archive/2013/06/21/tutorial-part-4-learning-how-to-write-a-3d-software-engine-in-c-ts-or-js-rasterization-amp-z-buffering.aspx. Reprinted here with permission of the author.

The post Write a 3D Soft Engine from Scratch: Part 4 appeared first on .

Learn CSS | HTML5 | JavaScript | WordPress | Tutorials-Web Development | Reference | Books and More

No Comments

Comments for Write a 3D Soft Engine from Scratch: Part 4 are now closed.