Dealing with the Great Big World 3

I've discussed some of the terrain-related portions of dealing with the Great Big World before.  I'm going to touch on another aspect in this post - buildings.

I'm working on the (software) architecture for a fresh prototype for the splines and sketching that I've posted about in the past.  I'd originally planned to continue work with that prototype, but the architecture is just poorly suited as it stands now.  I'll be reusing a lot of the code, but trying to shoehorn the changes into the original prototype wasn't working well.  Nothing from that is even close to ready to show, though.  So let's discuss buildings.

The old prototype, showing a river, road, railroad, and three buildings.

There are three buildings in the screenshot above, represented by the dark blue-gray polygons at upper left, near where the railroad crosses the road (to get to the other side).  For a decent 3D representation, what would we do?  We could substituted manually-modeled building models, be they free, purchased, or created personally.  But imagine trying to store a 3D model for every planet on a building, let alone model them all.  Its not very practical, although it is perfectly feasible to do for some signature structures, such as a few buildings in a national capital, or the tallest, signature skyscrapers in a city.  What does that leave us as an alternative?  Procedural modeling of buildings.

That's start with a very simple form of procedural modeling.  Our starting point will be the polygons in the map that represent buildings.  Each such polygon is the footprint of a building.  If each such a polygon were extruded upwards, we would get a polyhedron from each polygon.

Extrusion process - from polygon to polyhedron

But that only gives us a simple three dimensional form.  We could apply a texture to it.  If there's a nice tiling (repeatable) texture for brick or stone, it could allow one to accept the polyhedron as a building - especially if some windows and doors were part of the pattern.  This may even work well enough in some scenarios, in fact.  If each polyhedron had a random texture from a set of of such textures assigned, the buildings wouldn't all look alike, either.  A couple examples of such textures, generated via Filter Forge 5 filters, are shown below.  It might be good enough for a flight simulator or a train simulator, or for more-distant background buildings in any game or simulation.

Brick texture created using filter Bricks version 1

Window in wall texture created using filter Window gen

For buildings that are more close up, as in a driving game, a first person shooter, or just a VR scenario that involves walking down the street, it'll fall flat pretty fast.  Thankfully, there are solutions.  There are plug-ins and packages for many game engines and modeling tools that will help with some of this.  Unity features the BuildR asset in its Asset Store, for example.  And then there's perhaps the ultimate expression of procedural building generation, ESRI's CityEngine.

ESRI is primarily a GIS (geographic information systems) company, producers of the ArcGIS product.  However, they purchased a company out of Zurich named Procedural, Inc. that had produced a product called CityEngine.  CityEngine can create entire cities, including detailed building models.  For building generation, it uses something called CGA Shape Grammar.  CGA Shape Grammar is discussed at length in a 2006 paper by Pascal Mueller, Peter Wonka, Simon Haegler, Andreas Ulmer, Luc Van Gool, Procedural Modeling of Buildings.  You can look at that paper and the online documentation for CityEngine if you want to learn all the details, but I'll cover a few high points below, greatly simplified.

Geometric primitives

Basically, CGA Shape Grammar is a production system like L-systems in which a set of rules are defined.  When fed some initial data (such as the polygon of the building footprint) the rules are iteratively applied and a building is generated.  The rules can use operators such as extrude and split to manipulate the 3D dimensional polyhedron or the polygon faces.  Extrude works in much the manner as described above.

Split lets a polyhedron or polygonal face be split into multiple parts, so different rules can be applied to different parts.  For example, in the image below a polyhedron has been split in two and two different textures have been applied to the top half and the bottom half.  This is a common scenario.  Note the difference in fenestration between the first and second stories in the photo.

Polyhedron split process

Note difference in windows between first and second floors.

Implementing split of a polyhedron or polygon is fairly simple.  Since the polyhedron is little more than a collection of polygons, splitting a polyhedron is simply a matter of splitting the polygons. A plane defines where splitting takes place.  See Graphic Gems V "Spatial Partitioning of the Polygon by a Plane" for details on implementing such an algorithm.

Polygon split process

The split operation in CGA Shape can take a set of mixed absolute and relative dimensions for the split operation.  This involves calculating a set of planes to split by.  The splits are then performed sequentially.  The outputs of the split can then be addressed by further rules.

I am not planning to implement the full CGA Shape Grammar system as described in the paper. Even the rule-based approach is probably more than I care to bother with.  However, a few of the operations defined therein could be useful.  If the CGA Shape Grammar style of extrude, split, and repeat operations are implemented as C# methods that are part of a broader set of geometric primitives and procedural modeling capabilities, C# code or PowerShell scripts could access them. Combined with Constructive Solid Geometry (CSG) techniques they could provide a very compact representation of buildings without requiring prohibitively-extensive modeling.  Can a few scripts generate the buildings for an entire world?  Perhaps.

(PS - The roof generating operations would be nice to have for residential architecture.  More thoughts on that later.)