Things are afoot. As part of these things, we have had to do a few things that we have been putting off for awhile now here at Gaslamp HQ. One of these things is fixing pathing so people do not walk through each other; the other, which is what I have been working on, is a thorough shakedown of the building code.

As long-time readers are no doubt aware, one of our interesting pieces of technology is the code for procedural buildings. In Clockwork Empires, you designate a building footprint, feed it some style information (“brick walls and gabled roofs, please!”) and the engine churns out a building to your specification. There is significant Technical Devilry in our building code to do this, as it is a fairly hard problem to take somebody’s blueprint and get a building out of it.

As part of upcoming Things, one of the things we have been working on is a rewrite of our code for procedural buildings. The new code has a few key features that were requested by our art department:

1. It should not explode. (See this picture, arranged by David Baumgart and sent to me, of roofs exploding, set against a backdrop of early 2013 art.)

2. Support for other roof types. (Roofs come in a number of different styles, and we should not blow up when we handle them.)

3. Less fragility when handling cuts in buildings (for things like modules, doors, windows.)

4. “Good” edge beveling for roof flashing. What this means is that when a roof faces the player, and has complex geometry, we should bevel it appropriately.

5. A litany of other, minor artist complaints.

Accomplishing all of these things requires a certain amount of very tricky programming, and some very skilled debugging. How do you debug an exploding roof?

Our building generation code is based on a 2011 paper by Thomas Kelly and Peter Wonka called Interactive Architectural Modeling with Procedural Extrusions (a copy can be found here) The original version by Kelly and Wonka does not include support for texturing, or some of our nicer features like happily punching doors in things; it also does a bunch of stuff we don’t need, and don’t want. Over the course of the past two years, I’ve modified things quite a lot.

Kelly and Wonka’s paper works by what computer scientists call “wavefront propagation”. Imagine that the top of a roof is a coastline – a closed, roof-shaped coastline – and we allow water to flow from the coastline in waves, merging it as we go. What this produces is called the straight skeleton of a polygon – by adding weights to it, so that some edges move faster than others, this produces what is called the weighted straight skeleton.

What is missing from the original paper is a description of how to generate geometry from it. This is noted as “simple enough”, or words to that effect. The original version of the code did various clever things to try and build geometry as the wavefront propagated. I decided that the first thing to do was to throw that out – we would compute the entire wavefront propagation, and then create a triangular mesh from the path that the wave took. The general approach to doing this turned out to be fairly hard (see this SIGGRAPH Asia paper: http://www.cse.wustl.edu/~zoum/projects/CycleDisc/), so I ended up taking advantage of the fact that – well, I know it’s a building – to make this work a little better. However, now I was faced with a mystery. In implementing a new geometry extractor, how could I figure out which exploding buildings were caused by the wavefront propagation code and which exploding buildings were caused by new bugs?

The answer turned out to be to dump every step of the Wavefront Propagation algorithm to an SVG file.

The SVG file format turns out to be a very easy thing to dump two-dimensional vector graphics to. In this case, I could dump every edge of the previous stage of the wavefront propagation, the current stage of the wavefront propagation, and all of the connectivity information. Any time something blew up, I could then track through it and figure out *why* it blew up.

Internally, the Kelly/Wonka SVG algorithm works by looking at the actions of ‘chains’ of edges as the wavefront propagates down to nothing. We are interested in two types of things: edge collapses and edge splits. An edge collapse occurs when three edges collapse down to two edges (edge 2 on the blue line above does this, for instance); an edge split occurs when two edges push forward and in doing so cause their point of connectivity to intersect with something on the other side of the blueprint (here, for instance, edges 13 and 14 are going to eventually collide with edge 6.) We track collapses and splits when they occur, and update our geometry accordingly. We also introduce something called an ‘edge move’, which happens when some shuffle moves an edge to another part of the data structure; for instance, after doing an edge split the edge known as edge 4 in the blueprint above is now known as edge 22.

The key to having a happy, non-exploding building is to make sure all the logic for a building collapse to work correctly – i.e. making sure that you get the number of the edge that you split correct, and that you handle cases such as splitting an edge that is later split by something else. Every time something in the code didn’t handle, er, an “edge case” correctly, you would get an exploded blueprint:

For instance, what the heck happened here? Well, something went completely wrong and linked something to the wrong thing. Sometimes the problem lies a few steps back, and is not obvious (for instance, this was caused by a failure to check for newly-formed colinear edges after an edge split. Colinear edges cause undefined behaviour, and we deal with them by screening for them at every turn.) As an added bonus, I added a debug routine which dumped out Every. Single. Thing. In. The. Algorithm every time I ran it.

After about seven rounds of this sort of debugging process – “find an exploded building, look at the logs, analyze its behaviour, understand the problem, fix the bug” – we got buildings with decent wavefronts that didn’t explode. We then extract what is known as a half-edge data structure from this. In non-technical speak, a half-edge is simply an edge with an orientation; two half-edges make an edge, each with an orientation going in a different direction.

We extract polygons from our half-edges, classify then by what plane they lie on, and convert them to closed loops. We can then do a few useful things with these closed loops: first, since they’re planar, any time we want to punch a hole in something (i.e. a window) we can simply project the thing that we want to do the hole-punching onto the thing we want to punch (i.e. a wall) to find the shape of the hole, and feed all such holes into the routine that does the triangulation. Second, we can bevel complex pieces to give them nice edging. How do we do that? Well, what we actually do is we run another wavefront propagation on just the surfaces we wish to bevel, making sure that we shut it off before it gets too far.

With all of this debugging done, our buildings now explode a lot less. At this point, I now send the entire mess over to David and he gets the interesting job of making it look pretty. Perhaps he will post about this in a future blog post… only time will tell.

My thanks to Dr. Alla Sheffer and Chongyang Ma at UBC for their assistance in coming up with ideas to track this stuff down.