Monday, December 29, 2014

Hardware accelerated general purpose computation in javascript. (gpgpu)

General-purpose computing on graphics processing units (GPGPU, rarely GPGP or GP²U) is the utilization of a graphics processing unit (GPU), which typically handles computation only for computer graphics, to perform computation in applications traditionally handled by the central processing unit (CPU). The use of multiple graphics cards in one computer, or large numbers of graphics chips, further parallelizes the already parallel nature of graphics processing. In addition, even a single GPU-CPU framework provides advantages that multiple CPU's on their own do not offer due to specialization in each chip.
source: wikipedia
So why would you want to do this in javascript? Well for one its awesome! The fact that you can now run code directly on the GPU via WebGL shaders makes general purpose computation on accelerated hardware now possible. Secondly, unlike javascript, shaders are compiled and are optimized for parallel operations. SO I thought, why wait for WebCL when i could just do it myself with WebGL shaders? I used three.js to take care of most of the WebGL grunt work which majorly simplified the setup code. I ended up with a small function that accepts a shader, an array of input data, and a callback function. It looks like this.
 gpgpu(shader, dataset, function (gpuout) { 
    /* do somthing with gpuout array */
});
So generally speaking, the way this works is a texture is created from an array of input data. This texture is loaded into the video card. A fragment shader renders onto a plane using the texture as input data. This plane is then rendered to a buffer which is then dumped back into a javascript array. If the whole process sounds inefficient its because it is. Luckily the speed increase of running computations on accelerated hardware usually makes up for the performance hit moving all the data back and forth. I have found that this approach tends to work best for computationally expensive functions and larger datasets. although the gpgpu function can accept a dataset as small as 16 floats.
Once I wrote a javascript function and its GLSL shader equivalent, I was able to run a test to compare the speed of native javascript vs. the same function written as a WebGL shader. Amazing! in some cases the WebGL shader was as much as 100x faster that its javascript counterpart. Finally I thought it would be cool to only have to write the code once so i wrote a very simple javascript -> GLSL cross compiler. I ended up with something that looks like this.
gpgpu(
    glsl(function(val){ 
        return Math.sqrt(val);
    }), 
    dataset, 
    function (gpuout) { 
    /* do somthing with gpuout array */
});
Leave a comment and let me know what you think and feel free to check out the live demo. There is a code editor window where you can modify the javascript/shader and see the execution times of the CPU vs the GPU. :)



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!

Thursday, December 11, 2014

Easy Local Storage persistence layer in angular.js

Angular.js is a MVC framework for client side javascript that gives HTML superpowers. I have only introduced a few developers to angular but so far every one of them has been blown away by how easy and incredibly useful it is for building dynamic and highly responsive web apps.

Object oriented programming in angular.js with ds.oop

One of the features I like most about angular (aside from the 2-way data binding) is that it allows you to write modular self-contained code and use dependency injection which is invaluable in large projects which would otherwise quickly become heaps of unmaintainable spaghetti code. Using dependency injection in angular, we can define a controller or service with exactly what it needs to operate clearly defined in the function parameters so that any developer looking at it later immediately knows what it touches (That is, what code it needs to run or have access to). To make use of some other oop ideas such as inheritance lets see how to implement ds.oop with angular.js. ds.oop is a lightweight object oriented framework to simplify class creation and inheritance in javascript. As you will see, it allows you to write classes in a way that feels like a class.

This short tutorial will demonstrate an easy way to persist data in HTML5 local storage using reusable code via inheritance with ds.oop in angular.js. These 2 frameworks are open-source and work quite well togeather.

Required Frameworks: To start, this is a regular angular factory that can be injected into other factories and controllers as a dependency. This is a fast function to generate a Guid using a lookup table. We will use this any time we need to create a random Identifier for something.

.factory('Guid', function () {
    var lut = []; for (var i = 0; i < 256; i++) { lut[i] = (i < 16 ? '0' : '') + (i).toString(16); }
    return function () {
        var d0 = Math.random() * 0xffffffff | 0;
        var d1 = Math.random() * 0xffffffff | 0;
        var d2 = Math.random() * 0xffffffff | 0;
        var d3 = Math.random() * 0xffffffff | 0;
        return lut[d0 & 0xff] + lut[d0 >> 8 & 0xff] + lut[d0 >> 16 & 0xff] + lut[d0 >> 24 & 0xff] + '-' +
            lut[d1 & 0xff] + lut[d1 >> 8 & 0xff] + '-' + lut[d1 >> 16 & 0x0f | 0x40] + lut[d1 >> 24 & 0xff] + '-' +
            lut[d2 & 0x3f | 0x80] + lut[d2 >> 8 & 0xff] + '-' + lut[d2 >> 16 & 0xff] + lut[d2 >> 24 & 0xff] +
            lut[d3 & 0xff] + lut[d3 >> 8 & 0xff] + lut[d3 >> 16 & 0xff] + lut[d3 >> 24 & 0xff];
    };
})

Don't worry if that looks a little intimidating. Its been heavily optimized. The important part to see here is that an angular factory is just a function that returns something. In this case we are returning a function to generate a Guid. Now we can inject this factory into controllers, directives, or even other factories. Actually, thats exacly what we are going to do. Here is the simple localStorage base class I made. This provides some simple methods to save and load the object state into localStorage. At this point you might be wondering what local storage is exactly. With local storage, web applications can store data locally within the user's browser using key/value pairs. Unlike cookies, the storage limit is far larger (at least 5MB) and information is never transferred to the server.

// Base class for persistence
.factory('LocalStorage', ['Guid', function (Guid) {
    return ds.make.class({
        init: function (id) {
            this.id = (id || Guid()).toString();
        },
        load: function () {
            var state = localStorage[this.id];
            if (state) ds.data.copy(JSON.parse(state), this, [this.id], false);
        },
        save: function () {
            localStorage[this.id] = JSON.stringify(this);
        }
    });
} ])

So as you can see this is a very simple class. Our Guid factory is injected at the top. Three methods. Init() will accept an optional id or generate one using the injected Guid factory. Save() will serialize *this and save it to local storage. and Load will deserialize the data from local storage and the load it into *this. You could use this class as it is but there is nothing interesting in this class to save so to make this useful we need to inherit it...

// FormModel inherits LocalStorage class for save/load methods
.factory('FormModel', ['LocalStorage', function (LocalStorage) {
    return ds.make.class({
        inherits: LocalStorage,
        constructor: function (id) {
            this.init(id);
        },

        reset: function () {
            this.firstName= 
            this.lastName= 
            this.age='';
        }
    });
} ])

Ok so here is another simple class but in this one we have inherited our LocalStorage class and can now make use of its methods. This class is called FormModel because it is going to hold all of the data for our particular form and to use this and tie everything together we must create a angular controller and view. Here is the super mega awesome controller

.controller('MyCtrl', ['$scope', 'FormModel', function ($scope, FormModel) {

    // create an instance of FormModel and give it the id: 'test001'
    $scope.model = new FormModel('test001'); 

} ]);

And here is the view. Angular is calling our save/load methods directly through our FormModel class and handling updates between the DOM and our model automatically via 2-way data binding. Yeah, did i mention angular.js is awesome?

    <body ng-controller="MyCtrl">
        
        <div>
            model.id:
            <input type="text" ng-model="model.id" ng-disabled="true" />
        </div>
        <div>
            First Name:   
            <input type="text" ng-model="model.firstName" />
        </div>
        <div>
            Last Name:
            <input type="text" ng-model="model.lastName" />
        </div>
        <div>
            Age (years):
            <input type="text" ng-model="model.age" />
        </div>
        
        <button ng-click="model.save()">Save</button>    
        <button ng-click="model.load()">Load</button>
        <button ng-click="model.reset()">Reset</button>
    </body>

So there it is. Now who needs a database? :)
By combining ds.oop with angular we are able to take advantage of dependency injection which simplifies code maintenance and development. We accomplish this by encapsulating our class in an angular factories. By using ds.oop we can define a base class that can be used to persist any other class to local storage by simply inheriting it. This base class could also be extended to use any other storage mechanism quite easily. Session Storage, cookies, even a server side database or cache using ajax if one so desires.

I hope you have enjoyed this short tutorial. Go forth and write code.