Game Development: Toying with CSG and WebGL
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.