Friday 27 May 2016

CSG : Constructive Solid Geometry


Constructive Solid Geometry is a Modelling technique, and it's not a new one.

Basically you get to create or load 'CSG Brushes' which can be used to sculpt your game's level geometry.  Further, you can apply boolean operations to sets of brushes in order to create more complex brushes - which is the basis of CSG Modelling.
A brush is nothing but a set of unique 3D Planes, each of which carries one or more Coplanar Polygons - typically, textured planar n-gons.
You can imagine a simple cube as a nice example of a Brush - it has six planes, each plane contains one polygon with four sides. We could use such a Brush to create a 'room', then shrink the brush (yes we can manipulate brush geometry) and use it again to stamp out a doorway in one of the walls just like you were wielding a cookie-cutter.
That's what CSG editing is like in practice, although our brushes can be much more complex and interesting... importantly, it's possible to construct a CSG brush from an existing mesh of arbitrary complexity... we can basically load brushes from existing meshes, or face-selections thereof.

Less obviously, CSG can be used to create a BSP Tree (and by extension, a Sector-and-Portal Graph), rather than generating the BSP Tree from a large mesh (or set of mesh instances), and then extracting sectors and portals from the triangle soup.

It is noteworthy that CSG Brushes share some properties with BSP Leaf Nodes.
Both are comprised of Planes and their Planar Polygons, one major difference is that there is no guarantee that the set of planes comprising a Brush form a closed space, while BSP leaf nodes have an iron-clad guarantee that the surrounding planes form a watertight seal - a truly closed space.
They are nonetheless, more similar than they are different, which is what got my attention.
We can in fact, generate a BSP Tree from a Brush, and if we wish, we can define CSG boolean operations as operations involving BSP Trees - however, this is not the only possible approach.

Now I have to be honest, my only interest in BSP Trees is their ability to spew forth a set of connected gamespaces, as well as information about the connections between the spaces - that is to say, we can extract a sector-and-portal graph from a conventional solid-leaf bsp tree.

Having said that, the process of generating BSP Trees for entire levels is exponentially expensive with respect to the complexity of the input triangle soup. CSG Brushes, on the other hand, offer a rapid way to produce large and complex BSP Trees from much smaller and simpler subtrees, as well as a way to re-use those subtrees.

Most modern game engines have deprecated CSG within their respective toolsets, although there are notable exceptions. The reasons given generally mention that CSG has been more or less replaced by static meshes (with respect to MODELLING) which is a fair statement, that CSG Brushes are notoriously difficult and error-prone to implement with respect to models of arbitrary complexity (also a fair call), and that there are better tools for modelling than the engine's CSG editing tools can provide - this last point is completely irrelevant, and really seems like a cop-out.

In my opinion, what is not being talked about is how modern game engines deal with static meshes with respect to spatial partitioning. I mean, octrees and boundingvolume hierarchies are still the order of the day, while the best features of BSP trees (the properties of their leaves) are still valid, even if we discard the tree, we still want some kind of sparse spatial mapping, and nothing I can think of does a better job of mapping mostly-empty space than a sector and portal graph.

I'm looking forward to implementing realtime in-game CSG editing tools, and I admit that I will be looking at the current crop of modelling tools for inspiration.


No comments:

Post a Comment