Game Development Reference
In-Depth Information
Constructive solid geometry is a well-researched algorithm for generating com-
plex 3D geometry through the composition of solid volumes using Boolean operators
such as union, difference, and intersection. For the purposes of real-time games, we
are interested in the outer boundary representation of the resulting CSG volume in
the form of a triangle mesh optimized for GPU rendering. Our contribution is to
present an algorithm that is incremental, can run at interactive rates, and produces
well-behaved meshes with optimized triangulation.
This technique has been effectively used in the Id Tech engines, the Source En-
gine from Valve, and the Unreal Engines from Epic. These engines implemented
CSG calculations with the aid of a BSP-tree data structure. This method is de-
scribed in [Schneider 03]. The BSP tree was also used to accelerate visibility deter-
mination when these engines initially used software rasterization and, as a result,
generated many more triangle fragments than would otherwise be necessary. This
became a disadvantage within modern engines designed for powerful GPUs that,
generally speaking, reach their peak performance rendering large batches of large
triangles. The global nature of BSP-tree planar splits also meant that a local change
in the CSG model specification could modify the entire output mesh. Our system
addresses the different optimization priorities of modern game engines as well as
the need for quick incremental feedback within game tools.
We present a modernized version of the CSG algorithm that
does not use BSP trees, although it can be implemented with small BSP trees
at the leaves;
can perform all common CSG operations;
makes it trivial to perform CSG on multiple brushes in parallel;
allows for updates to be applied locally and independently from the rest of
the model;
can be updated at interactive rates for local changes;
produces geometry optimized for modern GPUs;
produces watertight geometry and is therefore physics-friendly;
can be extended to produce optimized triangulations without T-junctions.
Furthermore, the combination of these properties makes this CSG implementa-
tion useful for use in procedural geometry synthesis. It is possible to create param-
eterized CSG components that include information on how to first remove a given
volume from the world before adding new solid geometry. This makes it possible
to, for example, insert predesigned windows and doors onto walls interactively.