3D Booleans

2 min read•1 page

Constructive Solid Geometry (CSG) represents solid objects as binary trees where leaf nodes are primitive solids (boxes, spheres) and internal nodes are boolean operators (union, intersection, difference).

CSG Tree Structure:

1. Leaf nodes contain boundary meshes of input solid primitives. 2. Internal nodes store Boolean operation tags. 3. The complete shape is computed by evaluating the tree from bottom to top.

python

1# Constructive Solid Geometry (CSG) Tree Node
2class CSGNode:
3    def __init__(self, operation=None, left=None, right=None, mesh=None):
4        self.op = operation   # UNION, INTERSECT, DIFFERENCE
5        self.left = left       # Left CSGNode subtree
6        self.right = right     # Right CSGNode subtree
7        self.mesh = mesh       # Actual solid mesh if leaf node
8        self.is_leaf = mesh is not None

1 min read•1 page

To evaluate CSG boundaries, we first locate all triangle-triangle intersections between the two solid meshes to identify split lines.

Intersection Detection:

1. Accelerate queries by testing triangle bounding boxes. 2. Execute triangle-triangle intersection checks for overlapping candidates. 3. Record the resulting intersection segments.

python

1# Detect intersections between triangles of two meshes
2def intersect_meshes(meshA, meshB):
3    intersecting_pairs = []
4    for triA in meshA.triangles:
5        # Prune search using AABB box checks
6        if not box_overlap(triA.bounds, meshB.bounds):
7            continue
8        for triB in meshB.triangles:
9            if triangle_overlap_check(triA, triB):
10                intersecting_pairs.append((triA, triB))
11    return intersecting_pairs

1 min read•1 page

Once intersection segments are identified, the triangles they cross are subdivided into smaller, planar-conformant triangles sharing the intersection boundary lines.

Subdivision Rules:

1. Locate intersection coordinates on triangle edge segments. 2. Subdivide the original triangle into a set of smaller sub-triangles. 3. Maintain vertex indices mapping to preserve topology connectivity.

python

1# Split a triangle along a segment crossing it
2def split_triangle(triangle, segment):
3    # Find intersections of segment endpoints on triangle edges
4    pts = get_edge_intersections(triangle, segment)
5    
6    # Subdivide triangle into smaller sub-triangles (triangulation)
7    new_triangles = triangulate_polygon_points(triangle.vertices + pts)
8    return new_triangles

2 min read•1 page

Each vertex of Mesh A is classified relative to the solid volume of Mesh B. The parity of ray crossings determines if a coordinate is inside or outside the other shape.

Containment Check:

1. Project a test ray from the target vertex. 2. Calculate intersection count against all faces of the other solid mesh. 3. Classify: Odd crossing count indicates inside; even count indicates outside.

python

1# Classify vertices of mesh A against solid volume B
2def classify_vertices(vertices_A, mesh_B):
3    classification = []
4    for pt in vertices_A:
5        # Cast a ray in any direction, count boundary crossings
6        crossings = count_ray_crossings(pt, Vector3(0, 1, 0), mesh_B)
7        
8        # Odd crossings = inside, Even crossings = outside
9        if crossings % 2 == 1:
10            classification.append((pt, "INSIDE"))
11        else:
12            classification.append((pt, "OUTSIDE"))
13            
14    return classification

3 min read•1 page

Triangles are selected or discarded based on their location (inside/outside the other volume) to satisfy the Boolean operation.

Trimming Logic:

1. Union: Retain OUTSIDE triangles from both meshes. 2. Intersection: Retain INSIDE triangles from both meshes. 3. Difference: Retain OUTSIDE triangles from A and INSIDE triangles from B (inverting normals).

python

1# Filter triangles based on Boolean operation type
2def trim_mesh_faces(meshA, meshB, operation):
3    output_faces = []
4    
5    if operation == "UNION":
6        # Keep faces of A outside B, and faces of B outside A
7        output_faces.extend([f for f in meshA.faces if f.classification == "OUTSIDE"])
8        output_faces.extend([f for f in meshB.faces if f.classification == "OUTSIDE"])
9    elif operation == "INTERSECT":
10        # Keep faces of A inside B, and faces of B inside A
11        output_faces.extend([f for f in meshA.faces if f.classification == "INSIDE"])
12        output_faces.extend([f for f in meshB.faces if f.classification == "INSIDE"])
13    elif operation == "DIFFERENCE":
14        # Keep faces of A outside B, and faces of B inside A (flip normals)
15        output_faces.extend([f for f in meshA.faces if f.classification == "OUTSIDE"])
16        output_faces.extend([f.flipped() for f in meshB.faces if f.classification == "INSIDE"])
17        
18    return output_faces

Boolean Op (0=Union, 1=Intersect, 2=Difference)

0.00

2 min read•1 page

To assemble a watertight solid, duplicate vertices along the trimmed boundaries of both meshes are merged within a tolerance, stitching the open shells.

Seam Welding:

1. Identify duplicate boundary vertices within a tolerance limit. 2. Collapse duplicate vertex pairs into a single vertex coordinate. 3. Update face index tables to reference the merged vertices.

python

1# Weld open seams along triangle intersection boundaries
2def weld_mesh_seams(vertices, faces, tolerance=1e-5):
3    welded_vertices = []
4    vertex_map = {}
5    
6    for i, v in enumerate(vertices):
7        # Find if duplicate vertex exists within tolerance
8        duplicate_idx = find_duplicate_vertex(v, welded_vertices, tolerance)
9        if duplicate_idx is not None:
10            vertex_map[i] = duplicate_idx
11        else:
12            new_idx = len(welded_vertices)
13            welded_vertices.append(v)
14            vertex_map[i] = new_idx
15            
16    # Remap face indices
17    welded_faces = [[vertex_map[idx] for idx in f] for f in faces]
18    return welded_vertices, welded_faces

1 min read•1 page

The remaining triangles of both meshes are combined into a single vertex-face index array, forming the final clipped solid.

Assembly Phase:

1. Combine face lists of both trimmed meshes. 2. Execute seam welding to link boundaries. 3. Compute new vertex normal vectors for smooth shading.

python

1# Compile final watertight solid mesh from trimmed parts
2def assemble_csg(trimmed_faces_A, trimmed_faces_B):
3    # Merge face lists
4    combined_faces = trimmed_faces_A + trimmed_faces_B
5    
6    # Clean duplicates, weld vertices, rebuild normals
7    vertices, faces = weld_vertices_and_rebuild(combined_faces)
8    return SolidMesh(vertices, faces)

Boolean Op (0=Union, 1=Intersect, 2=Difference)

0.00

2 min read•1 page

Standard float arithmetic leads to catastrophic CSG failures when boundaries are exactly coplanar or share a single touching vertex.Nef Polyhedra represent solid geometry using boundary cells and local neighborhoods (sphere maps) to guarantee topological consistency.

Exact Geometric Predicates:

1. Arbitrary Precision: Homogeneous coordinates represented using arbitrary precision integers, completely removing rounding errors. 2. Sphere Maps: Local neighborhoods at each vertex represent boundaries as vertices, arcs, and faces on a unit sphere. 3. Open/Closed Sets: Nef representations support open and closed boundaries, handling non-manifold contacts cleanly.

python

1from CGAL.CGAL_Kernel import Exact_predicates_exact_constructions_kernel as Kernel
2from CGAL.CGAL_Nef_3 import Nef_polyhedron_3
3
4# Define shapes using exact computation kernels
5# Rather than floating-point coordinates, coordinates use arbitrary precision rationals
6cube_a_nef = Nef_polyhedron_3(polyhedron_a)
7cube_b_nef = Nef_polyhedron_3(polyhedron_b)
8
9# Exact Boolean operations are guaranteed to be topologically closed
10union_nef = cube_a_nef + cube_b_nef
11difference_nef = cube_a_nef - cube_b_nef

Overlap / Separation Shift

0.00