Game Development: Toying with CSG and WebGL

I just started experimenting with WebGL and JavaScript for game development. The possibility of developing 3D games anyone can play on any platform without installing anything, so long as they have a capable browser, is a very attractive one. Now that browsers are implementing JavaScript APIs for fullscreen mode and pointer capture, it seems like it might finally be possible to create browser games that can compete with their desktop counterparts.

You might think JavaScript is still too slow to create performance intensive 3D games like First Person Shooters (FPS). It’s true that JavaScript code still isn’t as fast as what you can make with C++ (perhaps by an order of magnitude or so), but I’ve recently seen demos of a Quake III map renderer, a Quake II port and 3D physics that convinced me JavaScript was probably fast enough to make serious games.

I’ve been thinking it would be nice to try and make a simple FPS game of my own. Perhaps something with entirely (or almost entirely) procedurally generated content, along the lines of kkrieger. Generating simple worlds, meshes and textures procedurally would free me from one of the main issues I’ve had in my past game development attempts. The issue being that it’s very hard to recruit and motivate artists to work on your project when you’re a hobbyist and can’t offer them money.

There are many nice tutorials out there to help you learn WebGL, which is essentially a simplified OpenGL API with less room for confusion. I was able to quickly write my own shaders for basic point/ambient lighting and vertex coloring. The next step, I figured, would be to work on tools to make procedural content generation easier. With that goal in mind, I started reading up on Constructive Solid Geometry (CSG).

CSG is a technique to build 3D shapes out of combinations of simple primitives and operations such as addition, subtraction and intersection. It’s fairly tricky to implement, but I find the math and algorithms involved to be fairly interesting. I found this document to be particularly useful in helping me to implement the generation of CSG primitives. Specifically, it’s possible to fully specify a brush (convex polytope) in space by its bounding planes. To render this brush, however, you need to compute its vertices and sort the said vertices in either clockwise or counterclockwise order for each face.

So far, I’ve been able to generate cubes, convex prisms and pyramids with any number of sides. The algorithm I implemented unfortunately scales fairly poorly, however, as it tests each possible combination of 3 bounding planes for intersection to find the vertices of a given brush, which has expected O(n^3) running time. This slows down to a crawl as soon as a brush has 50 faces or more. I’m considering perhaps manually computing the vertices ahead of time in my brush generation process instead. For now, I will probably look into the computation of CSG operations and see what representation makes more sense from that point of view.