CSG and n-gons

A week ago I finally got the CSG routines working properly for a project of mine, and I’ve spent the last couple of days improving the algorithm for efficiency and robustness; I think it is now ready to be put to use in a game. The algorithm only supports 2 modes – additive or subtractive, but another mode will likely be added later for deforming geometry.

The basic algorithm follows a 3 stage process:
– Find intersection loops, generated along the intersection of the faces from the two models.
– Cut the polygons along this intersection loop, discarding the parts of the polygons that lie on the inner edge (this is where additive/subtractive makes a difference).
– Propagate outward, including other triangles where the triangle shares a vertex with an included triangle.

This algorithm, along with the ability to work on ngons, has significantly sped up the operations. Although using low poly models, the system is responsive without the need for triangle partitioning (this will likely be added later).

Finding intersections

To detect intersections, the system tests each polygon of one model against each polygon in the other, producing a set of intersections between the two polygons. This test first determines that the plane of each polygon intersect the other polygon, and that the two are not coplanar. A logical axis is generated along the intersection of these planes. The edges of each polygon are then iterated and tested for intersections with the other polygon (through projecting onto the plane and checking that the projected point lies inside of the polygon). Each intersection found is added to a list, ordered based on its occurrence along the logical intersection axis.

As the polygons in each mesh form a closed surface, it can be assumed that each intersection point will appear twice (as each edge is shared by two polygons in a mesh). The intersections collected from each polygon-polygon test are aggregated such that similar intersections are nearby, thereby producing an intersection loop.

Under certain conditions, such as an unclosed mesh, or coplanar faces, an intersection loop may be incomplete. This can be easily checked and the operation can be terminated to prevent further destruction of the mesh.

Cutting polygons

The intersection parts that each polygon participates in are extracted and added to a list of intersection lists (note, there may be multiple disjoint sets). These lists should begin and end with an intersection along the edge of the polygon, and may contain only external intersections, penetrating the polygon interior, between these two edge intersection points.

For each polygon, an iterator begins following one of these intersection sets, then continues along the polygon outline, visiting any intersection set it comes across, until it loops back to where it started. This produces a cut output polygon, and after removing the used intersection sets, the process is repeated until no sets remain.

Propagate outward

The last stage is quite simple; the triangles that are known to be on the correct side of the intersection loop (the ones that were previously created) have their vertices marked. All other triangles are then iterated through; any that contain a marked vertex are added to the list of valid triangles, and have their vertices marked. This process is repeated until no more triangles are found. All other triangles are assumed to be inside the mesh and are discarded.

Known bugs

This algorithm will likely produce incorrect results when an operation splits the solid in half, and another operation operates on one of these halves. The propagation will likely cause the other half of the geometry to be destroyed.

The algorithm still has trouble with coplanar faces, although this case may easier to determine and resolve through use of the intersection loop. This situation is also quite rare in real-world uses.

Intersections that involve vertices can cause problems for the final propagation stage.

Second CSG prototype
Play in Chrome

Update: Had some more progress last night to get a bit of gameplay in, you can now build extractors, and task your commander with building it: Play

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s