Skip to content

Instantly share code, notes, and snippets.

@rygorous
Created April 25, 2012 03:48
Show Gist options
  • Save rygorous/2486101 to your computer and use it in GitHub Desktop.
Save rygorous/2486101 to your computer and use it in GitHub Desktop.
Half-space tri rasterizers in JS
<html>
<body>
<script src="Stats.js"></script>
<p id="timing">&nbsp;</p>
<script>
var requestAnimationFrame = window.requestAnimationFrame || window.webkitRequestAnimationFrame || window.mozRequestAnimationFrame || window.oRequestAnimationFrame || window.msRequestAnimationFrame;
var stats = new Stats();
document.body.appendChild( stats.getDomElement() );
var canvas = document.createElement( 'canvas' );
canvas.width = 1024;
canvas.height = 512;
document.body.appendChild( canvas );
var canvasWidth = canvas.width;
var canvasHeight = canvas.height;
var context = canvas.getContext( '2d' );
var imagedata = context.getImageData( 0, 0, canvasWidth, canvasHeight );
var data = imagedata.data;
// var typedarray = new Uint8ClampedArray( data.length );
// console.log( data instanceof Uint8ClampedArray );
render();
animate();
function animate() {
requestAnimationFrame( animate );
render();
stats.update();
}
function render() {
// clear
for ( var i = 3, l = data.length; i < l; i += 4 ) {
data[ i ] = 0;
}
/*
for ( var i = 0; i < 100000; i ++ ) {
var color = Math.random() * 0xffffff;
drawPixel(
Math.floor( Math.random() * canvasWidth ),
Math.floor( Math.random() * canvasHeight ),
color >> 16 & 255,
color >> 8 & 255,
color & 255
);
}
*/
/*
for ( var i = 0; i < 100; i ++ ) {
drawRectangle(
Math.random() * canvasWidth,
Math.random() * canvasHeight,
Math.random() * canvasWidth,
Math.random() * canvasHeight,
Math.random() * 0xffffff
);
}
*/
var startTime = new Date();
for ( var i = 0; i < 1000; i ++ ) {
drawTriangle(
Math.random() * canvasWidth,
Math.random() * canvasHeight,
Math.random() * 0xffffff,
Math.random() * canvasWidth,
Math.random() * canvasHeight,
Math.random() * 0xffffff,
Math.random() * canvasWidth,
Math.random() * canvasHeight,
Math.random() * 0xffffff
);
}
var endTime = new Date();
document.getElementById("timing").innerText = (endTime - startTime) + "ms";
context.putImageData( imagedata, 0, 0 );
}
//
function drawPixel( x, y, r, g, b ) {
var offset = ( x + y * canvasWidth ) * 4;
if ( data[ offset + 3 ] ) return;
data[ offset ] = r;
data[ offset + 1 ] = g;
data[ offset + 2 ] = b;
data[ offset + 3 ] = 255;
}
function drawRectangle( x1, y1, x2, y2, color ) {
var r = color >> 16 & 255;
var g = color >> 8 & 255;
var b = color & 255;
var xmin = Math.min( x1, x2 ) >> 0;
var xmax = Math.max( x1, x2 ) >> 0;
var ymin = Math.min( y1, y2 ) >> 0;
var ymax = Math.max( y1, y2 ) >> 0;
for ( var y = ymin; y < ymax; y ++ ) {
for ( var x = xmin; x < xmax; x ++ ) {
drawPixel( x, y, r, g, b );
}
}
}
function drawTriangle( x1, y1, color1, x2, y2, color2, x3, y3, color3 ) {
// http://devmaster.net/forums/topic/1145-advanced-rasterization/
// 28.4 fixed-point coordinates
var x1 = Math.round( 16 * x1 );
var x2 = Math.round( 16 * x2 );
var x3 = Math.round( 16 * x3 );
var y1 = Math.round( 16 * y1 );
var y2 = Math.round( 16 * y2 );
var y3 = Math.round( 16 * y3 );
// Deltas
var dx12 = x1 - x2, dy12 = y2 - y1;
var dx23 = x2 - x3, dy23 = y3 - y2;
var dx31 = x3 - x1, dy31 = y1 - y3;
// Bounding rectangle
var minx = Math.max( ( Math.min( x1, x2, x3 ) + 0xf ) >> 4, 0 );
var maxx = Math.min( ( Math.max( x1, x2, x3 ) + 0xf ) >> 4, canvasWidth );
var miny = Math.max( ( Math.min( y1, y2, y3 ) + 0xf ) >> 4, 0 );
var maxy = Math.min( ( Math.max( y1, y2, y3 ) + 0xf ) >> 4, canvasHeight );
// Block size, standard 8x8 (must be power of two)
var q = 8;
// Start in corner of 8x8 block
minx &= ~(q - 1);
miny &= ~(q - 1);
// Constant part of half-edge functions
var c1 = -dy12 * x1 - dx12 * y1;
var c2 = -dy23 * x2 - dx23 * y2;
var c3 = -dy31 * x3 - dx31 * y3;
// Correct for fill convention
if ( dy12 > 0 || ( dy12 == 0 && dx12 > 0 ) ) c1 ++;
if ( dy23 > 0 || ( dy23 == 0 && dx23 > 0 ) ) c2 ++;
if ( dy31 > 0 || ( dy31 == 0 && dx31 > 0 ) ) c3 ++;
// Note this doesn't kill subpixel precision, but only because we test for >=0 (not >0).
// It's a bit subtle. :)
c1 = (c1 - 1) >> 4;
c2 = (c2 - 1) >> 4;
c3 = (c3 - 1) >> 4;
// Set up min/max corners
var qm1 = q - 1; // for convenience
var nmin1 = 0, nmax1 = 0;
var nmin2 = 0, nmax2 = 0;
var nmin3 = 0, nmax3 = 0;
if (dx12 >= 0) nmax1 -= qm1*dx12; else nmin1 -= qm1*dx12;
if (dy12 >= 0) nmax1 -= qm1*dy12; else nmin1 -= qm1*dy12;
if (dx23 >= 0) nmax2 -= qm1*dx23; else nmin2 -= qm1*dx23;
if (dy23 >= 0) nmax2 -= qm1*dy23; else nmin2 -= qm1*dy23;
if (dx31 >= 0) nmax3 -= qm1*dx31; else nmin3 -= qm1*dx31;
if (dy31 >= 0) nmax3 -= qm1*dy31; else nmin3 -= qm1*dy31;
// Loop through blocks
var linestep = (canvasWidth - q) * 4;
for ( var y0 = miny; y0 < maxy; y0 += q ) {
for ( var x0 = minx; x0 < maxx; x0 += q ) {
// Edge functions at top-left corner
var cy1 = c1 + dx12 * y0 + dy12 * x0;
var cy2 = c2 + dx23 * y0 + dy23 * x0;
var cy3 = c3 + dx31 * y0 + dy31 * x0;
// Skip block when at least one edge completely out
if (cy1 < nmax1 || cy2 < nmax2 || cy3 < nmax3) continue;
// Offset at top-left corner
var offset = (x0 + y0 * canvasWidth) * 4;
// Accept whole block when fully covered
if (cy1 >= nmin1 && cy2 >= nmin2 && cy3 >= nmin3) {
for ( var iy = 0; iy < q; iy ++ ) {
for ( var ix = 0; ix < q; ix ++, offset += 4 ) {
if (data[offset + 3]) continue;
data[offset] = 0;
data[offset + 1] = 255;
data[offset + 2] = 0;
data[offset + 3] = 255;
}
offset += linestep;
}
} else { // Partially covered block
for ( var iy = 0; iy < q; iy ++ ) {
var cx1 = cy1;
var cx2 = cy2;
var cx3 = cy3;
for ( var ix = 0; ix < q; ix ++ ) {
if ( (cx1 | cx2 | cx3) >= 0 && !data[offset+3]) {
data[offset] = 0;
data[offset + 1] = 0;
data[offset + 2] = 255;
data[offset + 3] = 255;
}
cx1 += dy12;
cx2 += dy23;
cx3 += dy31;
offset += 4;
}
cy1 += dx12;
cy2 += dx23;
cy3 += dx31;
offset += linestep;
}
}
}
}
}
</script>
</body>
</html>
<html>
<body>
<script src="Stats.js"></script>
<p id="timing">&nbsp;</p>
<script>
var requestAnimationFrame = window.requestAnimationFrame || window.webkitRequestAnimationFrame || window.mozRequestAnimationFrame || window.oRequestAnimationFrame || window.msRequestAnimationFrame;
var stats = new Stats();
document.body.appendChild( stats.getDomElement() );
var blocksize = 8;
var canvas = document.createElement( 'canvas' );
canvas.width = 1024;
canvas.height = 512;
document.body.appendChild( canvas );
var canvasWidth = canvas.width;
var canvasHeight = canvas.height;
var canvasWBlocks = Math.floor((canvasWidth + blocksize-1) / blocksize);
var canvasHBlocks = Math.floor((canvasHeight + blocksize-1) / blocksize);
var context = canvas.getContext( '2d' );
var imagedata = context.getImageData( 0, 0, canvasWidth, canvasHeight );
var data = imagedata.data;
var block_full = new Uint8Array(canvasWBlocks * canvasHBlocks);
// var typedarray = new Uint8ClampedArray( data.length );
// console.log( data instanceof Uint8ClampedArray );
render();
animate();
function animate() {
requestAnimationFrame( animate );
render();
stats.update();
}
function render() {
// clear
for ( var i = 3, l = data.length; i < l; i += 4 ) {
data[ i ] = 0;
}
for (var i = 0, l = block_full.length; i < l; i++) {
block_full[i] = 0;
}
/*
for ( var i = 0; i < 100000; i ++ ) {
var color = Math.random() * 0xffffff;
drawPixel(
Math.floor( Math.random() * canvasWidth ),
Math.floor( Math.random() * canvasHeight ),
color >> 16 & 255,
color >> 8 & 255,
color & 255
);
}
*/
/*
for ( var i = 0; i < 100; i ++ ) {
drawRectangle(
Math.random() * canvasWidth,
Math.random() * canvasHeight,
Math.random() * canvasWidth,
Math.random() * canvasHeight,
Math.random() * 0xffffff
);
}
*/
var startTime = new Date();
for ( var i = 0; i < 1000; i ++ ) {
drawTriangle(
Math.random() * canvasWidth,
Math.random() * canvasHeight,
Math.random() * 0xffffff,
Math.random() * canvasWidth,
Math.random() * canvasHeight,
Math.random() * 0xffffff,
Math.random() * canvasWidth,
Math.random() * canvasHeight,
Math.random() * 0xffffff
);
}
var endTime = new Date();
document.getElementById("timing").innerText = (endTime - startTime) + "ms";
context.putImageData( imagedata, 0, 0 );
}
//
function drawPixel( x, y, r, g, b ) {
var offset = ( x + y * canvasWidth ) * 4;
if ( data[ offset + 3 ] ) return;
data[ offset ] = r;
data[ offset + 1 ] = g;
data[ offset + 2 ] = b;
data[ offset + 3 ] = 255;
}
function drawRectangle( x1, y1, x2, y2, color ) {
var r = color >> 16 & 255;
var g = color >> 8 & 255;
var b = color & 255;
var xmin = Math.min( x1, x2 ) >> 0;
var xmax = Math.max( x1, x2 ) >> 0;
var ymin = Math.min( y1, y2 ) >> 0;
var ymax = Math.max( y1, y2 ) >> 0;
for ( var y = ymin; y < ymax; y ++ ) {
for ( var x = xmin; x < xmax; x ++ ) {
drawPixel( x, y, r, g, b );
}
}
}
function drawTriangle( x1, y1, color1, x2, y2, color2, x3, y3, color3 ) {
// http://devmaster.net/forums/topic/1145-advanced-rasterization/
// 28.4 fixed-point coordinates
var x1 = Math.round( 16 * x1 );
var x2 = Math.round( 16 * x2 );
var x3 = Math.round( 16 * x3 );
var y1 = Math.round( 16 * y1 );
var y2 = Math.round( 16 * y2 );
var y3 = Math.round( 16 * y3 );
// Deltas
var dx12 = x1 - x2, dy12 = y2 - y1;
var dx23 = x2 - x3, dy23 = y3 - y2;
var dx31 = x3 - x1, dy31 = y1 - y3;
// Bounding rectangle
var minx = Math.max( ( Math.min( x1, x2, x3 ) + 0xf ) >> 4, 0 );
var maxx = Math.min( ( Math.max( x1, x2, x3 ) + 0xf ) >> 4, canvasWidth );
var miny = Math.max( ( Math.min( y1, y2, y3 ) + 0xf ) >> 4, 0 );
var maxy = Math.min( ( Math.max( y1, y2, y3 ) + 0xf ) >> 4, canvasHeight );
// Block size, standard 8x8 (must be power of two)
var q = blocksize;
// Start in corner of 8x8 block
minx &= ~(q - 1);
miny &= ~(q - 1);
// Constant part of half-edge functions
var c1 = -dy12 * x1 - dx12 * y1;
var c2 = -dy23 * x2 - dx23 * y2;
var c3 = -dy31 * x3 - dx31 * y3;
// Correct for fill convention
if ( dy12 > 0 || ( dy12 == 0 && dx12 > 0 ) ) c1 ++;
if ( dy23 > 0 || ( dy23 == 0 && dx23 > 0 ) ) c2 ++;
if ( dy31 > 0 || ( dy31 == 0 && dx31 > 0 ) ) c3 ++;
// Note this doesn't kill subpixel precision, but only because we test for >=0 (not >0).
// It's a bit subtle. :)
c1 = (c1 - 1) >> 4;
c2 = (c2 - 1) >> 4;
c3 = (c3 - 1) >> 4;
// Set up min/max corners
var qm1 = q - 1; // for convenience
var nmin1 = 0, nmax1 = 0;
var nmin2 = 0, nmax2 = 0;
var nmin3 = 0, nmax3 = 0;
if (dx12 >= 0) nmax1 -= qm1*dx12; else nmin1 -= qm1*dx12;
if (dy12 >= 0) nmax1 -= qm1*dy12; else nmin1 -= qm1*dy12;
if (dx23 >= 0) nmax2 -= qm1*dx23; else nmin2 -= qm1*dx23;
if (dy23 >= 0) nmax2 -= qm1*dy23; else nmin2 -= qm1*dy23;
if (dx31 >= 0) nmax3 -= qm1*dx31; else nmin3 -= qm1*dx31;
if (dy31 >= 0) nmax3 -= qm1*dy31; else nmin3 -= qm1*dy31;
// Loop through blocks
var linestep = (canvasWidth - q) * 4;
for ( var y0 = miny; y0 < maxy; y0 += q ) {
for ( var x0 = minx; x0 < maxx; x0 += q ) {
// Edge functions at top-left corner
var cy1 = c1 + dx12 * y0 + dy12 * x0;
var cy2 = c2 + dx23 * y0 + dy23 * x0;
var cy3 = c3 + dx31 * y0 + dy31 * x0;
// Skip block when at least one edge completely out
if (cy1 < nmax1 || cy2 < nmax2 || cy3 < nmax3) continue;
// Skip writing full block if it's already fully covered
var blockX = (x0 / q) | 0;
var blockY = (y0 / q) | 0;
var blockInd = blockX + blockY * canvasWBlocks;
if (block_full[blockInd]) continue;
// Offset at top-left corner
var offset = (x0 + y0 * canvasWidth) * 4;
// Accept whole block when fully covered
if (cy1 >= nmin1 && cy2 >= nmin2 && cy3 >= nmin3) {
for ( var iy = 0; iy < q; iy ++ ) {
for ( var ix = 0; ix < q; ix ++, offset += 4 ) {
if (data[offset + 3]) continue;
data[offset] = 0;
data[offset + 1] = 255;
data[offset + 2] = 0;
data[offset + 3] = 255;
}
offset += linestep;
}
block_full[blockInd] = 1;
} else { // Partially covered block
for ( var iy = 0; iy < q; iy ++ ) {
var cx1 = cy1;
var cx2 = cy2;
var cx3 = cy3;
for ( var ix = 0; ix < q; ix ++ ) {
if ( (cx1 | cx2 | cx3) >= 0 && !data[offset+3]) {
data[offset] = 0;
data[offset + 1] = 0;
data[offset + 2] = 255;
data[offset + 3] = 255;
}
cx1 += dy12;
cx2 += dy23;
cx3 += dy31;
offset += 4;
}
cy1 += dx12;
cy2 += dx23;
cy3 += dx31;
offset += linestep;
}
}
}
}
}
</script>
</body>
</html>
<html>
<body>
<script src="Stats.js"></script>
<p id="timing">&nbsp;</p>
<script>
var requestAnimationFrame = window.requestAnimationFrame || window.webkitRequestAnimationFrame || window.mozRequestAnimationFrame || window.oRequestAnimationFrame || window.msRequestAnimationFrame;
var stats = new Stats();
document.body.appendChild( stats.getDomElement() );
var blocksize = 8;
var canvas = document.createElement( 'canvas' );
canvas.width = 1024;
canvas.height = 512;
document.body.appendChild( canvas );
var canvasWidth = canvas.width;
var canvasHeight = canvas.height;
var canvasWBlocks = Math.floor((canvasWidth + blocksize-1) / blocksize);
var canvasHBlocks = Math.floor((canvasHeight + blocksize-1) / blocksize);
var context = canvas.getContext( '2d' );
var imagedata = context.getImageData( 0, 0, canvasWidth, canvasHeight );
var data = imagedata.data;
var block_full = new Uint8Array(canvasWBlocks * canvasHBlocks);
// var typedarray = new Uint8ClampedArray( data.length );
// console.log( data instanceof Uint8ClampedArray );
render();
animate();
function animate() {
requestAnimationFrame( animate );
render();
stats.update();
}
function render() {
// clear
for ( var i = 3, l = data.length; i < l; i += 4 ) {
data[ i ] = 0;
}
for (var i = 0, l = block_full.length; i < l; i++) {
block_full[i] = 0;
}
/*
for ( var i = 0; i < 100000; i ++ ) {
var color = Math.random() * 0xffffff;
drawPixel(
Math.floor( Math.random() * canvasWidth ),
Math.floor( Math.random() * canvasHeight ),
color >> 16 & 255,
color >> 8 & 255,
color & 255
);
}
*/
/*
for ( var i = 0; i < 100; i ++ ) {
drawRectangle(
Math.random() * canvasWidth,
Math.random() * canvasHeight,
Math.random() * canvasWidth,
Math.random() * canvasHeight,
Math.random() * 0xffffff
);
}
*/
var startTime = new Date();
for ( var i = 0; i < 1000; i ++ ) {
drawTriangle(
Math.random() * canvasWidth,
Math.random() * canvasHeight,
Math.random() * 0xffffff,
Math.random() * canvasWidth,
Math.random() * canvasHeight,
Math.random() * 0xffffff,
Math.random() * canvasWidth,
Math.random() * canvasHeight,
Math.random() * 0xffffff
);
}
var endTime = new Date();
document.getElementById("timing").innerText = (endTime - startTime) + "ms";
context.putImageData( imagedata, 0, 0 );
}
//
function drawPixel( x, y, r, g, b ) {
var offset = ( x + y * canvasWidth ) * 4;
if ( data[ offset + 3 ] ) return;
data[ offset ] = r;
data[ offset + 1 ] = g;
data[ offset + 2 ] = b;
data[ offset + 3 ] = 255;
}
function drawRectangle( x1, y1, x2, y2, color ) {
var r = color >> 16 & 255;
var g = color >> 8 & 255;
var b = color & 255;
var xmin = Math.min( x1, x2 ) >> 0;
var xmax = Math.max( x1, x2 ) >> 0;
var ymin = Math.min( y1, y2 ) >> 0;
var ymax = Math.max( y1, y2 ) >> 0;
for ( var y = ymin; y < ymax; y ++ ) {
for ( var x = xmin; x < xmax; x ++ ) {
drawPixel( x, y, r, g, b );
}
}
}
function drawTriangle( x1, y1, color1, x2, y2, color2, x3, y3, color3 ) {
// http://devmaster.net/forums/topic/1145-advanced-rasterization/
// 28.4 fixed-point coordinates
var x1 = Math.round( 16 * x1 );
var x2 = Math.round( 16 * x2 );
var x3 = Math.round( 16 * x3 );
var y1 = Math.round( 16 * y1 );
var y2 = Math.round( 16 * y2 );
var y3 = Math.round( 16 * y3 );
// Deltas
var dx12 = x1 - x2, dy12 = y2 - y1;
var dx23 = x2 - x3, dy23 = y3 - y2;
var dx31 = x3 - x1, dy31 = y1 - y3;
// Bounding rectangle
var minx = Math.max( ( Math.min( x1, x2, x3 ) + 0xf ) >> 4, 0 );
var maxx = Math.min( ( Math.max( x1, x2, x3 ) + 0xf ) >> 4, canvasWidth );
var miny = Math.max( ( Math.min( y1, y2, y3 ) + 0xf ) >> 4, 0 );
var maxy = Math.min( ( Math.max( y1, y2, y3 ) + 0xf ) >> 4, canvasHeight );
// Block size, standard 8x8 (must be power of two)
var q = blocksize;
// Start in corner of 8x8 block
minx &= ~(q - 1);
miny &= ~(q - 1);
// Constant part of half-edge functions
var c1 = -dy12 * x1 - dx12 * y1;
var c2 = -dy23 * x2 - dx23 * y2;
var c3 = -dy31 * x3 - dx31 * y3;
// Correct for fill convention
if ( dy12 > 0 || ( dy12 == 0 && dx12 > 0 ) ) c1 ++;
if ( dy23 > 0 || ( dy23 == 0 && dx23 > 0 ) ) c2 ++;
if ( dy31 > 0 || ( dy31 == 0 && dx31 > 0 ) ) c3 ++;
// Note this doesn't kill subpixel precision, but only because we test for >=0 (not >0).
// It's a bit subtle. :)
c1 = (c1 - 1) >> 4;
c2 = (c2 - 1) >> 4;
c3 = (c3 - 1) >> 4;
// Set up min/max corners
var qm1 = q - 1; // for convenience
var nmin1 = 0, nmax1 = 0;
var nmin2 = 0, nmax2 = 0;
var nmin3 = 0, nmax3 = 0;
if (dx12 >= 0) nmax1 -= qm1*dx12; else nmin1 -= qm1*dx12;
if (dy12 >= 0) nmax1 -= qm1*dy12; else nmin1 -= qm1*dy12;
if (dx23 >= 0) nmax2 -= qm1*dx23; else nmin2 -= qm1*dx23;
if (dy23 >= 0) nmax2 -= qm1*dy23; else nmin2 -= qm1*dy23;
if (dx31 >= 0) nmax3 -= qm1*dx31; else nmin3 -= qm1*dx31;
if (dy31 >= 0) nmax3 -= qm1*dy31; else nmin3 -= qm1*dy31;
// Loop through blocks
var linestep = (canvasWidth - q) * 4;
var scale = 255.0 / (c1 + c2 + c3);
for ( var y0 = miny; y0 < maxy; y0 += q ) {
for ( var x0 = minx; x0 < maxx; x0 += q ) {
// Edge functions at top-left corner
var cy1 = c1 + dx12 * y0 + dy12 * x0;
var cy2 = c2 + dx23 * y0 + dy23 * x0;
var cy3 = c3 + dx31 * y0 + dy31 * x0;
// Skip block when at least one edge completely out
if (cy1 < nmax1 || cy2 < nmax2 || cy3 < nmax3) continue;
// Skip writing full block if it's already fully covered
var blockX = (x0 / q) | 0;
var blockY = (y0 / q) | 0;
var blockInd = blockX + blockY * canvasWBlocks;
if (block_full[blockInd]) continue;
// Offset at top-left corner
var offset = (x0 + y0 * canvasWidth) * 4;
// Accept whole block when fully covered
if (cy1 >= nmin1 && cy2 >= nmin2 && cy3 >= nmin3) {
for ( var iy = 0; iy < q; iy ++ ) {
var cx1 = cy1;
var cx2 = cy2;
for ( var ix = 0; ix < q; ix ++ ) {
if (!data[offset + 3]) {
var u = cx1 * scale; // 0-255!
var v = cx2 * scale; // 0-255!
data[offset] = u;
data[offset + 1] = v;
data[offset + 2] = 0;
data[offset + 3] = 255;
}
cx1 += dy12;
cx2 += dy23;
offset += 4;
}
cy1 += dx12;
cy2 += dx23;
offset += linestep;
}
block_full[blockInd] = 1;
} else { // Partially covered block
for ( var iy = 0; iy < q; iy ++ ) {
var cx1 = cy1;
var cx2 = cy2;
var cx3 = cy3;
for ( var ix = 0; ix < q; ix ++ ) {
if ( (cx1 | cx2 | cx3) >= 0 && !data[offset+3]) {
var u = cx1 * scale; // 0-255!
var v = cx2 * scale; // 0-255!
data[offset] = u;
data[offset + 1] = v;
data[offset + 2] = 0;
data[offset + 3] = 255;
}
cx1 += dy12;
cx2 += dy23;
cx3 += dy31;
offset += 4;
}
cy1 += dx12;
cy2 += dx23;
cy3 += dx31;
offset += linestep;
}
}
}
}
}
</script>
</body>
</html>
<html>
<body>
<script src="Stats.js"></script>
<p id="timing">&nbsp;</p>
<script>
var requestAnimationFrame = window.requestAnimationFrame || window.webkitRequestAnimationFrame || window.mozRequestAnimationFrame || window.oRequestAnimationFrame || window.msRequestAnimationFrame;
var stats = new Stats();
document.body.appendChild( stats.getDomElement() );
var blocksize = 8;
var canvas = document.createElement( 'canvas' );
canvas.width = 1024;
canvas.height = 512;
document.body.appendChild( canvas );
var canvasWidth = canvas.width;
var canvasHeight = canvas.height;
var canvasWBlocks = Math.floor((canvasWidth + blocksize-1) / blocksize);
var canvasHBlocks = Math.floor((canvasHeight + blocksize-1) / blocksize);
var context = canvas.getContext( '2d' );
var imagedata = context.getImageData( 0, 0, canvasWidth, canvasHeight );
var data = imagedata.data;
var block_full = new Uint8Array(canvasWBlocks * canvasHBlocks);
// var typedarray = new Uint8ClampedArray( data.length );
// console.log( data instanceof Uint8ClampedArray );
render();
animate();
function animate() {
requestAnimationFrame( animate );
render();
stats.update();
}
function render() {
// clear
for ( var i = 3, l = data.length; i < l; i += 4 ) {
data[ i ] = 0;
}
for (var i = 0, l = block_full.length; i < l; i++) {
block_full[i] = 0;
}
/*
for ( var i = 0; i < 100000; i ++ ) {
var color = Math.random() * 0xffffff;
drawPixel(
Math.floor( Math.random() * canvasWidth ),
Math.floor( Math.random() * canvasHeight ),
color >> 16 & 255,
color >> 8 & 255,
color & 255
);
}
*/
/*
for ( var i = 0; i < 100; i ++ ) {
drawRectangle(
Math.random() * canvasWidth,
Math.random() * canvasHeight,
Math.random() * canvasWidth,
Math.random() * canvasHeight,
Math.random() * 0xffffff
);
}
*/
var startTime = new Date();
for ( var i = 0; i < 100; i ++ ) {
drawTriangle(
Math.random() * canvasWidth,
Math.random() * canvasHeight,
Math.random() * 0xffffff,
Math.random() * canvasWidth,
Math.random() * canvasHeight,
Math.random() * 0xffffff,
Math.random() * canvasWidth,
Math.random() * canvasHeight,
Math.random() * 0xffffff
);
}
var endTime = new Date();
document.getElementById("timing").innerText = (endTime - startTime) + "ms";
context.putImageData( imagedata, 0, 0 );
}
//
function drawPixel( x, y, r, g, b ) {
var offset = ( x + y * canvasWidth ) * 4;
if ( data[ offset + 3 ] ) return;
data[ offset ] = r;
data[ offset + 1 ] = g;
data[ offset + 2 ] = b;
data[ offset + 3 ] = 255;
}
function drawRectangle( x1, y1, x2, y2, color ) {
var r = color >> 16 & 255;
var g = color >> 8 & 255;
var b = color & 255;
var xmin = Math.min( x1, x2 ) >> 0;
var xmax = Math.max( x1, x2 ) >> 0;
var ymin = Math.min( y1, y2 ) >> 0;
var ymax = Math.max( y1, y2 ) >> 0;
for ( var y = ymin; y < ymax; y ++ ) {
for ( var x = xmin; x < xmax; x ++ ) {
drawPixel( x, y, r, g, b );
}
}
}
function drawTriangle( x1, y1, color1, x2, y2, color2, x3, y3, color3 ) {
// http://devmaster.net/forums/topic/1145-advanced-rasterization/
// 28.4 fixed-point coordinates
var x1 = Math.round( 16 * x1 );
var x2 = Math.round( 16 * x2 );
var x3 = Math.round( 16 * x3 );
var y1 = Math.round( 16 * y1 );
var y2 = Math.round( 16 * y2 );
var y3 = Math.round( 16 * y3 );
// Deltas
var dx12 = x1 - x2, dy12 = y2 - y1;
var dx23 = x2 - x3, dy23 = y3 - y2;
var dx31 = x3 - x1, dy31 = y1 - y3;
// Bounding rectangle
var minx = Math.max( ( Math.min( x1, x2, x3 ) + 0xf ) >> 4, 0 );
var maxx = Math.min( ( Math.max( x1, x2, x3 ) + 0xf ) >> 4, canvasWidth );
var miny = Math.max( ( Math.min( y1, y2, y3 ) + 0xf ) >> 4, 0 );
var maxy = Math.min( ( Math.max( y1, y2, y3 ) + 0xf ) >> 4, canvasHeight );
// Block size, standard 8x8 (must be power of two)
var q = blocksize;
// Start in corner of 8x8 block
minx &= ~(q - 1);
miny &= ~(q - 1);
// Constant part of half-edge functions
var c1 = dy12 * ((minx << 4) - x1) + dx12 * ((miny << 4) - y1);
var c2 = dy23 * ((minx << 4) - x2) + dx23 * ((miny << 4) - y2);
var c3 = dy31 * ((minx << 4) - x3) + dx31 * ((miny << 4) - y3);
// Correct for fill convention
if ( dy12 > 0 || ( dy12 == 0 && dx12 > 0 ) ) c1 ++;
if ( dy23 > 0 || ( dy23 == 0 && dx23 > 0 ) ) c2 ++;
if ( dy31 > 0 || ( dy31 == 0 && dx31 > 0 ) ) c3 ++;
// Note this doesn't kill subpixel precision, but only because we test for >=0 (not >0).
// It's a bit subtle. :)
c1 = (c1 - 1) >> 4;
c2 = (c2 - 1) >> 4;
c3 = (c3 - 1) >> 4;
// Set up min/max corners
var qm1 = q - 1; // for convenience
var nmin1 = 0, nmax1 = 0;
var nmin2 = 0, nmax2 = 0;
var nmin3 = 0, nmax3 = 0;
if (dx12 >= 0) nmax1 -= qm1*dx12; else nmin1 -= qm1*dx12;
if (dy12 >= 0) nmax1 -= qm1*dy12; else nmin1 -= qm1*dy12;
if (dx23 >= 0) nmax2 -= qm1*dx23; else nmin2 -= qm1*dx23;
if (dy23 >= 0) nmax2 -= qm1*dy23; else nmin2 -= qm1*dy23;
if (dx31 >= 0) nmax3 -= qm1*dx31; else nmin3 -= qm1*dx31;
if (dy31 >= 0) nmax3 -= qm1*dy31; else nmin3 -= qm1*dy31;
// Loop through blocks
var linestep = (canvasWidth - q) * 4;
var scale = 255.0 / (c1 + c2 + c3);
var cb1 = c1;
var cb2 = c2;
var cb3 = c3;
var qstep = -q;
var e1x = qstep * dy12;
var e2x = qstep * dy23;
var e3x = qstep * dy31;
var x0 = minx;
for (var y0 = miny; y0 < maxy; y0 += q) {
// New block line - keep hunting for tri outer edge in old block line dir
while (x0 >= minx && x0 < maxx && cb1 >= nmax1 && cb2 >= nmax2 && cb3 >= nmax3) {
x0 += qstep;
cb1 += e1x;
cb2 += e2x;
cb3 += e3x;
}
// Okay, we're now in a block we know is outside. Reverse direction and go into main loop.
qstep = -qstep;
e1x = -e1x;
e2x = -e2x;
e3x = -e3x;
while (1) {
// Step everything
x0 += qstep;
cb1 += e1x;
cb2 += e2x;
cb3 += e3x;
// We're done with this block line when at least one edge completely out
// If an edge function is too small and decreasing in the current traversal
// dir, we're done with this line.
if (x0 < minx || x0 >= maxx) break;
if (cb1 < nmax1) if (e1x < 0) break; else continue;
if (cb2 < nmax2) if (e2x < 0) break; else continue;
if (cb3 < nmax3) if (e3x < 0) break; else continue;
// We can skip this block if it's already fully covered
var blockX = (x0 / q) | 0;
var blockY = (y0 / q) | 0;
var blockInd = blockX + blockY * canvasWBlocks;
if (block_full[blockInd]) continue;
// Offset at top-left corner
var offset = (x0 + y0 * canvasWidth) * 4;
// Accept whole block when fully covered
if (cb1 >= nmin1 && cb2 >= nmin2 && cb3 >= nmin3) {
var cy1 = cb1;
var cy2 = cb2;
for ( var iy = 0; iy < q; iy ++ ) {
var cx1 = cy1;
var cx2 = cy2;
for ( var ix = 0; ix < q; ix ++ ) {
if (!data[offset + 3]) {
var u = cx1 * scale; // 0-255!
var v = cx2 * scale; // 0-255!
data[offset] = u;
data[offset + 1] = v;
data[offset + 2] = 0;
data[offset + 3] = 255;
}
cx1 += dy12;
cx2 += dy23;
offset += 4;
}
cy1 += dx12;
cy2 += dx23;
offset += linestep;
}
block_full[blockInd] = 1;
} else { // Partially covered block
var cy1 = cb1;
var cy2 = cb2;
var cy3 = cb3;
for ( var iy = 0; iy < q; iy ++ ) {
var cx1 = cy1;
var cx2 = cy2;
var cx3 = cy3;
for ( var ix = 0; ix < q; ix ++ ) {
if ( (cx1 | cx2 | cx3) >= 0 && !data[offset+3]) {
var u = cx1 * scale; // 0-255!
var v = cx2 * scale; // 0-255!
data[offset] = u;
data[offset + 1] = v;
data[offset + 2] = 0;
data[offset + 3] = 255;
}
cx1 += dy12;
cx2 += dy23;
cx3 += dy31;
offset += 4;
}
cy1 += dx12;
cy2 += dx23;
cy3 += dx31;
offset += linestep;
}
}
}
// Advance to next row of blocks
cb1 += q*dx12;
cb2 += q*dx23;
cb3 += q*dx31;
}
}
</script>
</body>
</html>
// stats.js r9 - http://github.com/mrdoob/stats.js
var Stats=function(){var h,a,r=0,s=0,i=Date.now(),u=i,t=i,l=0,n=1E3,o=0,e,j,f,b=[[16,16,48],[0,255,255]],m=0,p=1E3,q=0,d,k,g,c=[[16,48,16],[0,255,0]];h=document.createElement("div");h.style.cursor="pointer";h.style.width="80px";h.style.opacity="0.9";h.style.zIndex="10001";h.addEventListener("mousedown",function(a){a.preventDefault();r=(r+1)%2;0==r?(e.style.display="block",d.style.display="none"):(e.style.display="none",d.style.display="block")},!1);e=document.createElement("div");e.style.textAlign=
"left";e.style.lineHeight="1.2em";e.style.backgroundColor="rgb("+Math.floor(b[0][0]/2)+","+Math.floor(b[0][1]/2)+","+Math.floor(b[0][2]/2)+")";e.style.padding="0 0 3px 3px";h.appendChild(e);j=document.createElement("div");j.style.fontFamily="Helvetica, Arial, sans-serif";j.style.fontSize="9px";j.style.color="rgb("+b[1][0]+","+b[1][1]+","+b[1][2]+")";j.style.fontWeight="bold";j.innerHTML="FPS";e.appendChild(j);f=document.createElement("div");f.style.position="relative";f.style.width="74px";f.style.height=
"30px";f.style.backgroundColor="rgb("+b[1][0]+","+b[1][1]+","+b[1][2]+")";for(e.appendChild(f);74>f.children.length;)a=document.createElement("span"),a.style.width="1px",a.style.height="30px",a.style.cssFloat="left",a.style.backgroundColor="rgb("+b[0][0]+","+b[0][1]+","+b[0][2]+")",f.appendChild(a);d=document.createElement("div");d.style.textAlign="left";d.style.lineHeight="1.2em";d.style.backgroundColor="rgb("+Math.floor(c[0][0]/2)+","+Math.floor(c[0][1]/2)+","+Math.floor(c[0][2]/2)+")";d.style.padding=
"0 0 3px 3px";d.style.display="none";h.appendChild(d);k=document.createElement("div");k.style.fontFamily="Helvetica, Arial, sans-serif";k.style.fontSize="9px";k.style.color="rgb("+c[1][0]+","+c[1][1]+","+c[1][2]+")";k.style.fontWeight="bold";k.innerHTML="MS";d.appendChild(k);g=document.createElement("div");g.style.position="relative";g.style.width="74px";g.style.height="30px";g.style.backgroundColor="rgb("+c[1][0]+","+c[1][1]+","+c[1][2]+")";for(d.appendChild(g);74>g.children.length;)a=document.createElement("span"),
a.style.width="1px",a.style.height=30*Math.random()+"px",a.style.cssFloat="left",a.style.backgroundColor="rgb("+c[0][0]+","+c[0][1]+","+c[0][2]+")",g.appendChild(a);return{getDomElement:function(){return h},getFps:function(){return l},getFpsMin:function(){return n},getFpsMax:function(){return o},getMs:function(){return m},getMsMin:function(){return p},getMsMax:function(){return q},update:function(){i=Date.now();m=i-u;p=Math.min(p,m);q=Math.max(q,m);k.textContent=m+" MS ("+p+"-"+q+")";var a=Math.min(30,
30-30*(m/200));g.appendChild(g.firstChild).style.height=a+"px";u=i;s++;if(i>t+1E3)l=Math.round(1E3*s/(i-t)),n=Math.min(n,l),o=Math.max(o,l),j.textContent=l+" FPS ("+n+"-"+o+")",a=Math.min(30,30-30*(l/100)),f.appendChild(f.firstChild).style.height=a+"px",t=i,s=0}}};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment