7DFPS – Day 1 – Constructive Solid Geometry
I decided yesterday to finally participate in a game jam again. Not just for one/two days but the 7DFPS which lasts a whole week. I am no big fan of the First Person Shooter genre from a gameplay perspective but highly interested in the technologies used to make this visual worlds possible. With id Software’s John Carmack as one of the celeberties in the field and pusing the technologie for the past 20 years, I decided on challenging myself to have a deeper look at some of the concepts that make up the quake engine. Used by a hugh number of successfull games. Starting with id software’s in-house titles Quake 1 to 3. I will take this as a learning experience and not so much as a task to create a playable game at the end of the week. In case it will happen, I won’t be disappointed though…
The core idea behind the quake engine family (id tech 1 to 3; used in Quake 1 to Quake 3) seems to have stayed quiet constant. Mainly: Using Binary-Space-Partition (BSP) and Constructive Solid Geometry (CSG) to create the game world and define solid and empty space of the world. Querying the world database for visibility calculations, lighting calculations and physics is done via the BSP tree structure. The BSP tree itself and visibility (Potential Visibility Sets are built and attached to the BSP) and lighting (shadows/lights are baked into static textures that during runtime then just blended with the standard diffuse textures of the world) are calculated as am expensive prepossessing step. During runtime of the game, the BSP is then used mainly for rendering, physics, dynamic light calculations.
From there, the first day mainly consisted of reading articles and papers on the core technologies used by quake’s graphics engine; Binary-Space-Partition Trees (BSP Trees) and Constructive Solid Geometry:
To be able to build a BSP of the world, all the individual solid entities the world is made up of (lots of blocks) have to be merged via a CSG Union operation. This will lead to a set of solid and closed surfaces. No two polygons/faces intersect each other. I read up on some CSG approaches over at flipcode. From there, the Laidlaw paper on CSG is a good next step as it seems like this was also the main approach used within quake’s CSG tools.
From there, I started to get more practical: Let’s try to create a simple world, load it, CSG it and BSP it. Obviously, I needed a fast way to create this world, define some export format and load it. As I am on the track of Quake, I decided to use the .map file-format that is also used by all the level editors for the quake engine family. Trenchbroom was the editor of choice because it runs on windows and Mac OS. For the .map file-format itself there is a great article available describing not only the structure but also some alternative approaches for the polygon-creation and the CSG process.
I also tried to read the QBSP tool (which is part of the quake-engine’s asset creation pipeline; i.e. loaded a .map file and does the CSG, BSP, Visibility, Lighting etc) to get some help on implementing the CSG algorithm. It is really hard to read code with alot of shared state and confusing names. Fabian Sanglard’s commented repository clone helps a little to understand the interwoven codebase.
So what’s did I do expect reading? I implemented the loading of the .map file (Java + LWJGL) and that’s the result of today (as you can see in the screen shot in the top-right): A loaded .map file, CSG’ed and rendered. The colored faces show nicely how the actual source polygons for the walls and floors have been slip up into smaller regios to have one closed surface for the whole room.
Tomorrow comes the BSP.