Building a 3D engine in HTML5

Marius Gundersen @GundersenMarius
September 2011

Before we start

HTML5

<canvas width="320" height="240" id="c"><canvas>
<script>
  var canvas = document.getElementById("c");
  var ctx = canvas.getContext("2d");
  ctx.fillStyle="red";
  ctx.lineStyle="black";
  ctx.fillRect(128, 96, 64, 48);
  ctx.strokeRect(128, 96, 64, 48);
</script>

Why do we need a 3D engine?

3D engine

This Presentation

Projecting points

The world 

var world = {
  vertices:[
    {x:100, y:100, z: 500},
    {x:-100, y:100, z: 500},
    {x:-100, y:-100, z: 500},
    {x:100, y:-100, z: 500},
    {x:100, y:100, z: 300},
    {x:-100, y:100, z: 300},
    {x:-100, y:-100, z: 300},
    {x:100, y:-100, z: 300},
    
  ]
};

The camera 

var camera = {
  depth: 350,
  screen: Demo.ctx,
  width: Demo.canvas.width,
  height: Demo.canvas.height,
  offsetX: Demo.canvas.width/2,
  offsetY: Demo.canvas.height/2
}

The render function (Pseudocode) 

for each vertex
  project onto screen
  draw on screen

The render function (JavaScript) 

function render(world, camera){
  for(var i=0; i<world.vertices.length; i++){
    var vertex = world.vertices[i];
	
    var scale = camera.depth / vertex.z;
    var posX = scale * vertex.x + camera.offsetX;
    var posY = scale * vertex.y + camera.offsetY;
    var size = scale * 10;
	
    camera.screen.fillRect(posX-size/2, posY-size/2, size, size);
  }
}

Moving the camera

The camera with position 

var camera = {
  x: 0,
  y: 0,
  z: 0,
  depth: 350,
  screen: Demo.ctx,
  width: Demo.canvas.width,
  height: Demo.canvas.height,
  offsetX: Demo.canvas.width/2,
  offsetY: Demo.canvas.height/2
}

Camera movement (Pseudocode) 

for each vertex
  offset from camera
  project onto screen
  draw on screen

The render function with camera movement 

...
var vertex = world.vertices[i];

var dx = vertex.x - camera.x;
var dy = vertex.y - camera.y;
var dz = vertex.z - camera.z;
  
var scale = camera.depth / dz;
var posX = scale * dx + camera.offsetX;
var posY = scale * dy + camera.offsetY;
var size = scale * 10;
...

Bugfix #1 

...

var dz = vertex.z - camera.z;

if(dz > 0){

  var scale = camera.depth / dz;
  var posX = scale * dx + camera.offsetX;
  var posY = scale * dy + camera.offsetY;
  var size = scale * 10;

  camera.screen.fillRect(posX - size / 2, posY - size / 2, size, size);
}
...

Rotating the camera

Camera Rotation (Pseudocode) 

for each vertex
  offset from camera
  rotate around each axis
  if in front of camera
    project onto screen
    draw on screen

Rotation around y-axis 

...
var dx = vertex.x - camera.x;
var dy = vertex.y - camera.y;
var dz = vertex.z - camera.z;

var d1x = Math.cos(camera.ry)*dx + Math.sin(camera.ry)*dz;
var d1y = dy;
var d1z = Math.cos(camera.ry)*dz - Math.sin(camera.ry)*dx;

if(d1z > 0){
...

Rotation around all axis 

...

var d1x = Math.cos(camera.ry)*dx + Math.sin(camera.ry)*dz;
var d1y = dy;
var d1z = Math.cos(camera.ry)*dz - Math.sin(camera.ry)*dx;

var d2x = d1x;
var d2y = Math.cos(camera.rx)*d1y - Math.sin(camera.rx)*d1z;
var d2z = Math.cos(camera.rx)*d1z + Math.sin(camera.rx)*d1y;

var d3x = Math.cos(camera.rz)*d2x + Math.sin(camera.rz)*d2y;
var d3y = Math.cos(camera.rz)*d2y - Math.sin(camera.rz)*d2x;
var d3z = d2z;

if(d3z > 0){
...

Sprites

Simple Sprites (Pseudocode) 

for each vertex
  offset from camera
  rotate around each axis
  if in front of camera
    project onto screen
    draw image on screen

Simple Sprites 


var sprite = new Image();
sprite.src = "gfx/tree.png";

...
  if(d3z > 0){
    var scale = camera.depth / d3z;	
    var posX = scale * d3x + camera.offsetX;
    var posY = scale * d3y + camera.offsetY;
    var width = scale * sprite.width;
    var height = scale * sprite.height;

    camera.screen.drawImage(sprite, 
      0, 0, sprite.width, sprite.height, 
      posX - width / 2, posY - height / 2, width, height);
    }

Bugfix #2 (Pseudocode) 

for each vertex
  offset from camera
  rotate around each axis
  if in front of camera
    project onto screen
    store in list
sort list
for each item in list
  draw image on screen

Storing draw operations 

var toDraw = [];

for(var i=0; i<world.vertices.length; i++){
  ...
  if(d3z > 0){
   ...
    toDraw.push({
      posX: posX - width / 2,
      posY: posY - height / 2,
      posZ: scale,
      width: width,
      height: height
    });
  }
}

Sorting textures 

toDraw.sort(function(a, b){
  return a.posZ - b.posZ;
});

for(var i=0; i<toDraw.length; i++){
  var item = toDraw[i];
  camera.screen.drawImage(sprite, 
    0, 0, sprite.width, sprite.height, 
    item.posX, item.posY, item.width, item.height);
}

Rotating sprites

Sprite sheet

New world 

var world = {
  vertices:[
    {x:140, y:20, z: 0, ry:Math.PI*1, sprite:{
      w:48,
      h:48,
      y:0
    }},
...

3D Sprites (Pseudocode) 

for each vertex
  offset from camera
  rotate around each axis
  if in front of camera
    project onto screen
    calculate angle
    store in list
sort list
for each item in list
  find image tile
  draw image on screen

toDraw sprite 

		
toDraw.push({
  posX: posX - width / 2,
  posY: posY - height / 2,
  posZ: scale,
  width: width,
  height: height,
  sprite: vertex.sprite,
  ry: camera.ry - vertex.ry,
});

Calculating tile 

		
for(var i=0; i<toDraw.length; i++){
  var item = toDraw[i];
  
  var angle = (item.ry)%(Math.PI*2);
  while(angle < 0) angle += Math.PI*2;

  var ratio = angle / (Math.PI*2) * sprite.width;
  var x = (Math.round(ratio / item.sprite.w)*item.sprite.w);
  x %= sprite.width;
  
  camera.screen.drawImage(sprite, 
    x, item.sprite.y, item.sprite.w, item.sprite.h,
    item.posX, item.posY, item.width, item.height);
}

Wireframes

A new world


var world = {
  lines:[
    {p1: 0, p2: 1},
    {p1: 1, p2: 2},
    {p1: 2, p2: 3},
    {p1: 3, p2: 0}
  ],
  vertices:[
    {x:100, y:100, z: 100},
    {x:-100, y:100, z: 100},
    {x:-100, y:-100, z: 100},
    {x:100, y:-100, z: 100},
  ],

Wireframes (Pseudocode) 

for each vertex
  offset from camera
  rotate around each axis
  project onto screen
  store in vertex
for each line
  if both vertices are in front of camera
    store line in list
sort list
for each line in list
  draw line

The Render Function

for(var i=0; i<world.vertices.length; i++){
  var vertex = world.vertices[i];
  ..
  vertex.posX = scale * d3x + camera.offsetX;
  vertex.posY = scale * d3y + camera.offsetY;
  vertex.posZ = scale;
}
	
for(var i=0; i<world.lines.length; i++){
  var line = world.lines[i];
  if(line.p1.posZ > 0 && line.p2.posZ > 0){
    toDraw.push({
      posX1: line.p1.posX,
      posY1: line.p1.posY,
      posX2: line.p2.posX,
      posY2: line.p2.posY,
      posZ: (line.p1.posZ + line.p2.posZ)/2
    });
  }
}

Drawing Lines

toDraw.sort(function(a, b){
  return a.posZ - b.posZ;
});

for(var i=0; i<toDraw.length; i++){
  camera.screen.beginPath();
  camera.screen.moveTo(toDraw[i].posX1, toDraw[i].posY1);
  camera.screen.lineTo(toDraw[i].posX2, toDraw[i].posY2);
  camera.screen.stroke();
}

Polygons

Yet another world


var world = {
  triangles:[
    {p1: 2, p2: 1, p3: 0, c:"#D00"},
    {p1: 0, p2: 3, p3: 2, c:"#D00"},
  ]
  vertices:[
    {x:100, y:100, z: 100},
    {x:-100, y:100, z: 100},
    {x:-100, y:-100, z: 100},
    {x:100, y:-100, z: 100},
  ],

Polygons (Pseudocode) 

for each vertex
  offset from camera
  rotate around each axis
  project onto screen
  store in vertex
for each triangle
  if all vertices are in front of camera
    store triangle in list
sort list
for each triangle in list
  draw triangle

Triangles

for(var i=0; i<world.triangles.length; i++){
  var triangle = world.triangles[i];
  if(triangle.p1.posZ > 0 && triangle.p2.posZ > 0 
       && triangle.p3.posZ > 0){
    toDraw.push({
      posX1: triangle.p1.posX,
      posY1: triangle.p1.posY,
      posX2: triangle.p2.posX,
      posY2: triangle.p2.posY,
      posX3: triangle.p3.posX,
      posY3: triangle.p3.posY,
      posZ: (triangle.p1.posZ + triangle.p2.posZ + 
	       triangle.p3.posZ)/3,
      color: triangle.c
    });
  }
}

Drawing Triangles

for(var i=0; i<toDraw.length; i++){
  camera.screen.beginPath();
  camera.screen.fillStyle = toDraw[i].color;
  camera.screen.moveTo(toDraw[i].posX1, toDraw[i].posY1);
  camera.screen.lineTo(toDraw[i].posX2, toDraw[i].posY2);
  camera.screen.lineTo(toDraw[i].posX3, toDraw[i].posY3);
  camera.screen.fill();
}

Bugfix #3 (Pseudocode) 

for each vertex
  offset from camera
  rotate around each axis
  project onto screen
  store in vertex
for each triangle
  if all vertices are in front of camera
    if polygon faces camera
      store triangle in list
sort list
for each triangle in list
  draw triangle

Finding the normal vector

		
var vector1 = {dx: triangle.p1.x - triangle.p2.x,
               dy: triangle.p1.y - triangle.p2.y,
               dz: triangle.p1.z - triangle.p2.z};
var vector2 = {dx: triangle.p3.x - triangle.p2.x,
               dy: triangle.p3.y - triangle.p2.y,
               dz: triangle.p3.z - triangle.p2.z};
var crossProduct = {dx: vector1.dy*vector2.dz - vector1.dz*vector2.dy,
                    dy: vector1.dz*vector2.dx - vector1.dx*vector2.dz,
                    dz: vector1.dx*vector2.dy - vector1.dy*vector2.dx};

Backface Culling

var cameraVector =  
  {dx: (camera.x - (triangle.p1.x + triangle.p2.x + triangle.p3.x)/3),
   dy: (camera.y - (triangle.p1.y + triangle.p2.y + triangle.p3.y)/3),
   dz: (camera.z - (triangle.p1.z + triangle.p2.z + triangle.p3.z)/3)};

var dp = crossProduct.dx * cameraVector.dx + 
         crossProduct.dy * cameraVector.dy + 
         crossProduct.dz * cameraVector.dz;

if(dp > 0){
  toDraw.push({
  ...

Light

Shading (Pseudocode) 

for each vertex
  offset from camera
  rotate around each axis
  project onto screen
  store in vertex
for each triangle
  if all vertices are in front of camera
    if polygon faces camera
      calculate shade
      store triangle in list
sort list
for each triangle in list
  draw triangle
  draw shade

Point light

var dp = crossProduct.dx * cameraVector.dx + 
         crossProduct.dy * cameraVector.dy + 
         crossProduct.dz * cameraVector.dz;

var length1 = Math.sqrt(cameraVector.dx * cameraVector.dx + 
                        cameraVector.dy * cameraVector.dy + 
                        cameraVector.dz * cameraVector.dz);
var length2 = Math.sqrt(crossProduct.dx * crossProduct.dx + 
                        crossProduct.dy * crossProduct.dy + 
                        crossProduct.dz * crossProduct.dz);
dp = dp/length1/length2;
if(dp > 0){
  toDraw.push({
    ...
    color: triangle.c,
    shade: 1-dp
  });

Drawing Shade

camera.screen.lineTo(toDraw[i].posX3, toDraw[i].posY3);
camera.screen.fill();
camera.screen.fillStyle = "rgba(0, 0, 0,"+toDraw[i].shade+")";
camera.screen.fill();

Now what?

Other possibilites?

CSS3 3D Transform

perspective: 600px;
transform: rotateY(0.25turn) translateZ(100px);

WebGl

Lessons Learned

Thank You

MariusGundersen.net
@gundersenMarius