Game Development Reference
In-Depth Information
which outer contour a hole belongs to, it is sucient to test if one of its points falls
withinanouterboundaryusingastandardpointinapolygontest(see
Figure8.11
)
.
Below is an outline of steps involved in the retriangulation phase:
1. Sort all the polygons produced by the CSG algorithm into groups based on
their plane, material ID and other properties.
2. Gather all edges for a group of polygons that share the same plane and ma-
terial ID.
3. From this, determine the set of closed and connected boundary edges. These
are the half edges that don't have a twin edge in the current working set.
These edges will form one or more closed contours.
4. For each boundary contour, determine if it is a inner or outer contour. The
inner contours will be the holes in the polygon.
5. For all outer contours, determine which inner contours fall within them. Sub-
mit the outer contour and list of holes to the triangulation library for pro-
cessing.
8.4 Conclusions
We presented a new approach to implementing a CSG algorithm and integrating
it into a content production pipeline. The core of the CSG algorithm can be made
to run interactively in the editor, which is crucial for properly visualizing the effect
of subtractive and intersection CSG operations on the primitive volumes. The T-
junction elimination and retriangulation phases of the algorithm can be applied
when saving or exporting the CSG model to production-ready world geometry.
Constructive solid geometry has been used in several commercial engines with
great success, and a variant of this algorithm has been implemented in the Day
1 Studios' Despair Engine tool set. The primary benefit observed in adding CSG
to a game production pipeline is that designers can block out game spaces quickly
without involving environment artists. Changes can be made iteratively to the
layout of game environments while testing game-play ideas. The final CSG model
serves as a blue print used to describe the space layout to the environment art staff
who uses it as a basis for the final art pass.
We are particularly excited about the future possibilities in content-amplification
and procedural geometry generation that this algorithm enables. As a future ex-
tension of this work, it is possible to allow designers to specify model components
such as doors, windows, and building structures as separate CSG trees. The CSG
trees of these structures could first remove geometry before adding new geometry,
allowing, for example, dragging and dropping windows on and across walls, auto-
matically creating and updating the hole in the wall where the window is placed. A
