Fastest way to implement z-buffering for a software renderer?

Question

I'm implementing a javascript software renderer (for academic purposes). It handles representing a 3d object as triangles, and handles Perspective Projection from 3d space to 2d space.

Until now, I used the lineTo and fillRect to represent the vertices and the lines on screen. I've even used lineTo to do Scan Line triangle filling. (you can check out the project here)

So far the FPS has been quite good. But the last part of the assignment is to implement z-Buffering :P. To my knowledge, the only way to do this is to stop filling my triangles using lineTo and fill them with either an array of 1px lines or an array of 1px squares. (because before I draw each "pixel", I have to check the depth buffer and see if I should actually draw it or not.)

The problem is, filling triangles with tiny rectangles or lines is SLOW. Gets everything down to 2FPS. So my question is, is there any method to draw one pixel instead of a tiny line (which may be faster)?

Alternatively, what else can I do to speed things up? My goal is to have it spin fast enough to demo the principle. (6-10fps would be enough)

Cheers.

[EDIT] While I wait for an answer, I will procede to modify my triangle filling functions to draw 4px sized "pixels" instead of 1px. But that will look jaggedy...

Answer 1

Check this out: http://jsfiddle.net/ZXjAM/2/

// points 0,1,2,3 front face
var fAvgZ = (cube.processPoints[0].colorZ + 
    cube.processPoints[1].colorZ + 
    cube.processPoints[2].colorZ + 
    cube.processPoints[3].colorZ) / 4 / 20;

// points 0,2,4,6 top
var tAvgZ = (cube.processPoints[0].colorZ + 
    cube.processPoints[2].colorZ + 
    cube.processPoints[4].colorZ + 
    cube.processPoints[6].colorZ) / 4 / 20;

// points 4,5,6,7 rear
var reAvgZ = (cube.processPoints[4].colorZ + 
    cube.processPoints[5].colorZ + 
    cube.processPoints[6].colorZ + 
    cube.processPoints[7].colorZ) / 4 / 20;

// points 1,3,5,7 bottom
var bAvgZ = (cube.processPoints[1].colorZ + 
    cube.processPoints[3].colorZ + 
    cube.processPoints[5].colorZ + 
    cube.processPoints[7].colorZ) / 4 / 20;

// points 2,3,6,7 right side
var rAvgZ = (cube.processPoints[2].colorZ + 
    cube.processPoints[3].colorZ + 
    cube.processPoints[6].colorZ + 
    cube.processPoints[7].colorZ) / 4 / 20;

// points 0,1,4,5 left side
var lAvgZ = (cube.processPoints[0].colorZ + 
    cube.processPoints[1].colorZ + 
    cube.processPoints[4].colorZ + 
    cube.processPoints[5].colorZ) / 4 / 20;

var layers = [{key:0, val:fAvgZ},
          {key:1, val:fAvgZ},
          {key:2, val:tAvgZ},
          {key:3, val:tAvgZ},
          {key:4, val:reAvgZ},
          {key:5, val:reAvgZ},
          {key:6, val:bAvgZ},
          {key:7, val:bAvgZ},
          {key:8, val:rAvgZ},
          {key:9, val:rAvgZ},
          {key:10, val:lAvgZ},
          {key:11, val:lAvgZ}];

var outLay = layers.sort(function(a,b){
    return (a.val - b.val);
});

for(var i = 0; i < outLay.length; i++)
{
    var k = outLay[i].key;
    ...
}

This is, by no means, the most efficient way to average/sort the point values, and it can probably be done with fewer lines of code using the cube's pre-existing properties, but the basic concept remains the same.

I'm finding the average z-index and using that to assume layering order. Obviously, this won't work for everything ever, but for simple polyhedra, it should suffice.

This can be simplified to:

var layers = [];
for (var i = 0; i < cube.sides.length; i++){
    var side = cube.sides[i];
    var avg = (cube.processPoints[side.a].colorZ + 
               cube.processPoints[side.b].colorZ + 
               cube.processPoints[side.c].colorZ) / 3 / 20;                   
    layers.push({key:i, val:avg});
}

var outLay = layers.sort(function(a,b){
    return (a.val - b.val);
});

There do seem to be some fringe-cases where there is a quick ordering-problem.

This seems to be more accurate: http://jsfiddle.net/ZXjAM/4/

var layers = [];
for (var i = 0; i < 12; ++i){
    var side1 = cube.sides[i];
    var side2 = cube.sides[++i];
    var avg = (cube.processPoints[side1.a].colorZ + 
               cube.processPoints[side1.b].colorZ + 
               cube.processPoints[side1.c].colorZ + 
               cube.processPoints[side2.a].colorZ + 
               cube.processPoints[side2.b].colorZ + 
               cube.processPoints[side2.c].colorZ) / 6;                   
    layers.push({key:i-1, val:avg});
    layers.push({key:i, val:avg});
}

var outLay = layers.sort(function(a,b){
    return (a.val - b.val);
});