Constructive Solid Geometry
2023-2024
Construction with binary combinations of solids is a convenient high level way to design models. Typically, primitive shapes such as cubes, cylinders and spheres are used for Constructive Solid Geometry. This implementation also supports solids represented by Signed Distance Functions and closed triangle meshes. The target representation is a mesh to be exported for rendering or manufacturing while simple ray casting is used as reference.
Although CSG can easily be made with SDFs alone the conversion from SDF to mesh using marching cubes is limited to a preset resolution which makes combining the mesh representations of the shapes a good alternative. However, a triangle mesh is a convenient structure for rendering but not for geometrical computation, as well described in the introduction of Exact predicates, exact constructions and combinatorics for mesh CSG. Combining two triangle meshes require every triangle in each mesh to be clipped to every triangle in the other mesh, determining which of the clipped triangles are inside and which are outside the opposing mesh and then stitching the pieces together.
This work use a simple but limited method to produce them based on a BSP triangle tree for each mesh clipping the other mesh and vice versa. The initial implementation was made by a straight forward porting the 2D polygon intersections based on linear algebra used in Polygon Editor to 3D. The limitations are that meshes may not be open, self intersecting or have triangles overlapped in the same plane. Numerically it is also quite sensitive to small perturbations in vertices. Often the first cut in a sequence works well while consecutive cuts suffer from the complex geometry produced by the previous cuts. All cuts are tracked and cuts that are not needed by the new geometry are prevented, and surface properties are assigned based on the origin of the new triangles.