Game Development Reference
In-Depth Information
The above points also make it trivial to implement instancing of groups of
brushes.
However, it does put a bigger burden on the final steps, where we have to
transform our individual vertices before we can optimize our mesh, as described in
Section 8.3, or when we need to render it.
When the shape of a brush is changed, or when it is moved, all the brushes that
touched it before and after the modification need to be updated. If a brush is very
large, it is more likely to touch more brushes and therefore more likely to take up
more processing time. To improve performance, large brushes should automatically
be split on each axis if their size passes a certain threshold. The polygons at the
intersection between the brushes can be flagged as never being visible and can be
skipped from processing entirely.
8.3 Mesh Optimization
The mesh generated by the interactive algorithm is a good representation of the
final output and may be used for quick iteration testing of the game environments.
However, the generated mesh may contain many extraneous polygon fragments
resulting from the brushes splitting process. The geometry may also contain T-
junctions, which can cause the rasterization of polygons to be misaligned slightly
and create cracks in the final rasterized geometry where the background shows
through. The best way to assure that adjacent polygons are rasterized without any
gaps is to ensure they use the same exact vertex values. This may require adding
additional vertices where polygons meet in a T-Junction.
8.3.1 T-Junction Elimination
Detecting and removing a T-junction involves keeping a table of all unique infinite
lines, which contain edges from the unoptimized CSG mesh. An infinite line is
defined as an intersection of two planes that are mutually perpendicular to the
direction of the line. The entry in the table for a given line also contains an
origin point to provide a relative ordering for a list of points that fall on this line.
The first step is to add all edges in the unoptimized CSG mesh to a T-junction
elimination table. Optionally, the edges can be sorted by length and added longest
first to improve the precision of the underlying calculations. When an edge is
added, we check if it falls on an existing line by calculating the distance of edge
endpoints to the two planes defining each line. If an edge falls on an existing
line, its end points are added in order based on the distance from the line origin.
Otherwise, a new unique line entry is created. Listing 8.2 shows the details of this
process.
The second phase involves asking the T-junction table if any edge of the CSG
model contains any other points between its end points. This can be quickly deter-
