Wednesday, December 17, 2014

Getting Old-School with Voxels in Phaser


Yay so what is a voxel anyway? A voxel represents a value on a rectangular grid in 3-dimensional space. Voxel is a combination of "volume" and "pixel" where pixel is a combination of "picture" and "element". As with pixels in a bitmap, voxels themselves do not typically have their position (their coordinates) explicitly encoded along with their values. Instead, the position of a voxel is inferred based upon its position relative to other voxels (i.e., its position in the data structure that makes up a single volumetric image). In contrast to pixels and voxels, points and polygons are often explicitly represented by the coordinates of their vertices.

So for those of you who have played Minecraft let me just say that Minecraft may or may not qualify as a voxel engine. It's sort of a gray area. Although minecraft stores and manipulates level data using a voxel data set, the rendering is entirely polygon based. Traditional voxel rendering does not make use of polygons but rather, voxels.

Voxel engines were much more commonly used in the past prior to modern 3D hardware acceleration however recently they have come back into style thanks in large part to popular games such as Minecraft so I decided to try my hand at some voxel rendering in Phaser.

My terrain voxel renderer prototype features rotation, pitch, linear interpolation (x-axis) for voxels and color. Currently the prototype works and can be viewed here. feel free to take my code and improve it. I am still working on speed optimizations. If you have some ideas to improve performance let me know. I would be interested in hearing your thoughts.

var heightmap;
var texture;
var scanline;
var graphicsRow;
var angle = 0;

var game = new Phaser.Game(800, 600, Phaser.WEBGL, 'voxel',
{
    preload: function () {
        game.time.advancedTiming = true;
        game.load.image('heightmap', 'assets/heightmap.jpg');
        game.load.image('texture', 'assets/terrain.jpg');
    },
    create: function () {

        heightmap = getBitmapData('heightmap', 'heightmap');
        texture = getBitmapData('texture', 'rgba');
        //graphics = game.add.graphics(game.width / 2, game.height / 2);

        // use a new graphics object for each row
        // for some reason when there are too many primitives in a graphics object the renderer chokes.
        // by creating a seperate graphics object for each row we ensure this does not happen.
        graphicsRow = [];
        for (var y = 0; y < texture.length; y++) {
            graphicsRow.push(game.add.graphics(game.width / 2, game.height / 2));
        }
    },
    update: function () {
        angle += 0.01;

        var height = texture.length;
        var width = texture[0].length;
        var halfHeight = height / 2;
        var halfWidth = width / 2;
        var centerx = -halfWidth;
        var centery = 0; // -halfHeight;
        var xScale = 4;
        var pitch = 2;

        // y-buffer        
        scanline = [];
        for (var x = 0; x < width * xScale; x++) {
            scanline.push(65535);
        }


        for (var y = height - 1; y > -1; y--) {

            var graphics = graphicsRow[y];
            graphics.clear();
            var ax;
            var ay;

            for (var x = 0; x < width; x++) {

                // calculate rotation
                var pax = ax;
                var pay = ay;
                var xoff = x - halfWidth;
                var yoff = y - halfHeight;
                var a = Math.atan2(yoff, xoff);
                a = Phaser.Math.wrapAngle(a + angle, true);
                var d = Math.sqrt(xoff * xoff + yoff * yoff);
                ay = Math.round((Math.sin(a) * d) + halfHeight);
                ax = Math.round((Math.cos(a) * d) + halfWidth);

                if (ax < 0 || ax >= width || ay < 0 || ay >= height || !pax || !pay || pax < 0 || pax >= width || pay < 0 || pay >= height) {
                    continue;
                }
                var lineHeight = heightmap[pay][pax];
                var color = texture[pay][pax];
                var nextLineHeight = heightmap[ay][ax];
                var nextColor = texture[ay][ax];
                if (!lineHeight) {
                    if (!nextLineHeight) continue;
                    lineHeight = nextLineHeight;
                }
                if (!color) {
                    if (!nextColor) continue;
                    color = nextColor;
                }

                var heights = subdivide(lineHeight, nextLineHeight, xScale);
                var colors = subdivideColor(color, nextColor, xScale);

                for (var s = 0; s < xScale; s++) {

                    lineHeight = heights[s];
                    color = colors[s];

                    var xs = (x * xScale) + s;
                    var cx = (x + centerx) * xScale + s;
                    var cy = (y * pitch) + centery;

                    var miny = cy - lineHeight;
                    if (scanline[xs] > miny) {

                        graphics.lineStyle(1, color, 1);
                        if (scanline[xs] > cy) {
                            graphics.moveTo(cx, cy);
                        } else {
                            graphics.moveTo(cx, scanline[xs]);
                        }
                        graphics.lineTo(cx, miny);
                        scanline[xs] = miny;
                    }
                }

            }
        }

    },
    render: function () {
        game.debug.text(game.time.fps || '--', 2, 14, "#00ff00");
    }
});

// steps must be >= 2
function subdivide(v1, v2, steps) {
    var diff = v2 - v1;
    var step = diff / steps;
    var values = [];
    for (var x = 0; x < steps; x++) {
        values.push( v1+ step*x );
    }
    return values;
}

function subdivideColor(c1, c2, steps) {
    var r = subdivide(c1.r, c2.r, steps);
    var g = subdivide(c1.g, c2.g, steps);
    var b = subdivide(c1.b, c2.b, steps);
    var values = [];
    for (var x = 0; x < steps; x++) {
        values.push(hex(r[x], g[x], b[x], 255));
    }
    return values;
}

function hex(r, g, b, a) {

    return a << 24 | r << 16 | g << 8 | b;

}

// function: getBitmapData
// scans an image and returns a 2-dimentional array of pixel data
//
// arguments:
//      imageName - the image key to the phaser image
//      format - the desired return format
//          possible values: 'rgba','hex','heightmap'  (default: 'hex')
//
function getBitmapData(imageName, format) {

    if (!imageName) throw 'imageName argument required';
    if (!format) format = 'hex';
    
    var image = game.cache.getImage(imageName);
    if (!image) throw 'invalid imageName. Verify imageName in your preload function!';    
    var bmd = game.make.bitmapData(image.width, image.height);

    bmd.draw(image, 0, 0);
    bmd.update();

    var data = [];
    if (format === 'rgba') {
        for (var y = 0; y < image.height; y++) {
            var row = [];
            for (var x = 0; x < image.width; x++) {
                var hex = bmd.getPixel32(x, y);

                var pixel = {
                    r: (hex) & 0xFF, // get the r
                    g: (hex >> 8) & 0xFF, // get the g
                    b: (hex >> 16) & 0xFF, // get the b
                    a: (hex >> 24) & 0xFF    // get the alpha                    
                };
                row.push(pixel);
            }
            data.push(row);
        }
    }
    else if (format === 'hex') {
        for (var y = 0; y < image.height; y++) {
            var row = [];
            for (var x = 0; x < image.width; x++) {
                var hex = bmd.getPixel32(x, y);
                row.push(hex);
            }
            data.push(row);
        }
    }
    else if (format === 'heightmap') {
        for (var y = 0; y < image.height; y++) {
            var row = [];
            for (var x = 0; x < image.width; x++) {
                var hex = bmd.getPixel32(x, y);

                var p = {
                    r: (hex) & 0xFF, // get the r
                    g: (hex >> 8) & 0xFF, // get the g
                    b: (hex >> 16) & 0xFF // get the b                    
                };
                row.push((p.r + p.b + p.g)/3); // average of rgb
            }
            data.push(row);
        }        
    }
    return data;
};

So this works but it is very slow. I get about 3-6 FPS on my laptop. Why is it so slow? The primary problem is that we are sending each voxel to webGL as a line segment (using phaser graphics primitives). Granted Phaser is using webGL to send the lines to the GPU with hardware acceleration but all of these line segments are independent webGL operations. Every call to webGL adds overhead and we are making ALOT of calls. The offending code:
    // we call this deep inside the render loop and it makes WebGL sad.
    graphics.lineStyle(1, color, 1);
    if (scanline[xs] > cy) {
        graphics.moveTo(cx, cy);
    } else {
        graphics.moveTo(cx, scanline[xs]);
    }
    graphics.lineTo(cx, miny);

The Solution? Instead of 480,000 operations per frame, lets just do 1 operation per frame. Better yet, lets move the render logic off of the CPU all together! Lets write a pixel shader to make the GPU do all the work for us. This will kill 2 birds with one stone because now we need only a few calls to WebGL and since the operation is running on the GPU we dont have to wait for the data to trickle down the bus for each frame. We can just send the data once and let it live in video RAM where the pixel shader will use it to render the terrain to a textured quad.

... Part 2: Coming Soon!

No comments:

Post a Comment