Wednesday, September 12, 2012

Using Bresenham's Algorithm to Create Shapes in Javascript

Until recently, there has been little reason to spend much time building graphic libraries for Javascript. However, now that HTML5 is becoming supported in basically all modern browsers, Canvas tags and CSS3 transforms have opened the door to delving into these concepts.

I want to work with non-linear objects like arcs, circles, ovals, etc. However, I'd like to avoid all the trigonometry and floating point calculations. We can approximate these points by creatively iterating with integers by using Bresenham's algorithm to generate each point in the path.

I found a C implementation of this algorithm for lines, circles, ellipses, and bezier curves and ported it to Javascript. Instead of plotting the points, I built an array and returned the set of x/y coordinates that represent the shape. I plotted an example of each shape on a canvas to see what it looked like. As it turns out, the algorithm can generate a lot of points so I decided to add a step variable to skip every N points. This can greatly reduce the number of points returned which is more than enough for the kinds of tasks I have in mind for these generated objects.

With some of these tools, I can now investigate all kinds of other fun things like non-linear path animation, hits areas that are not boxes, etc. I know that as more and more developers dig into building with the capabilities of HTML5, some really powerful libraries will evolve.