BSP CSG

2 min read•1 page

BSP Node Structure:

1. Splitting Plane: A plane separating space into positive (front) and negative (back) half-spaces. 2. Coplanar List: Polygons that lie exactly on the splitting plane. 3. Front & Back Subtrees: Pointers to child BSP nodes representing partitioned subspaces.

python

1class BSPNode:
2    def __init__(self, plane_polygon=None):
3        self.plane = plane_polygon  # Splitting plane definition
4        self.polygons = []          # Polygons coplanar with the plane
5        self.front = None           # Child BSPNode for space in front of plane
6        self.back = None            # Child BSPNode for space behind plane

A BSP tree is a spatial data structure that recursively partitions space into convex halves using splitting planes. In Constructive Solid Geometry (CSG), these planes are defined by the faces of the input polygons themselves.

2 min read•1 page

Vertex Classification:

1. Front Face: All vertices lie in the front half-space (d ≥ 0). 2. Back Face: All vertices lie in the back half-space (d ≤ 0). 3. Spanning: Vertices are split at the exact edge-plane intersection point.

python

1def split_polygon(plane, polygon):
2    front_verts, back_verts = [], []
3    pts = polygon.vertices
4    n = len(pts)
5
6    for i in range(n):
7        p1 = pts[i]
8        p2 = pts[(i + 1) % n]
9        d1 = plane.distance(p1)
10        d2 = plane.distance(p2)
11
12        if d1 >= 0:
13            front_verts.append(p1)
14        if d1 <= 0:
15            back_verts.append(p1)
16
17        # Check edge intersection (spanning case)
18        if (d1 > 0 and d2 < 0) or (d1 < 0 and d2 > 0):
19            t = d1 / (d1 - d2)
20            intersect = p1 + t * (p2 - p1)
21            front_verts.append(intersect)
22            back_verts.append(intersect)
23            
24    return Polygon(front_verts), Polygon(back_verts)

To insert a polygon into a BSP tree, we classify it against the node's splitting plane. If a polygon spans the plane, it must be split into Front and Back fragments.

Triangle Y Shift

0.00

2 min read•1 page

CSG Filtering Rules:

1. Union (A ∪ B): Keep fragments of A outside B, plus fragments of B outside A. 2. Intersection (A ∩ B): Keep fragments of A inside B, plus fragments of B inside A. 3. Difference (A - B): Keep fragments of A outside B, plus fragments of B inside A (with normals flipped).

python

1def csg_merge(poly_a, poly_b, op):
2    # 1. Clip A against B's BSP Tree
3    a_inside, a_outside = clip_polygons(poly_a, bsp_b)
4    # 2. Clip B against A's BSP Tree
5    b_inside, b_outside = clip_polygons(poly_b, bsp_a)
6
7    if op == "union":
8        # Keep outside fragments of both
9        return merge(a_outside, b_outside)
10    elif op == "intersection":
11        # Keep inside fragments of both
12        return merge(a_inside, b_inside)
13    elif op == "difference":
14        # Keep outside of A and inside of B (with inverted normals)
15        return merge(a_outside, invert(b_inside))

To perform a Boolean operation, we clip the polygons of Shape A against the BSP tree of Shape B, and vice versa. Each polygon is classified as completely Inside or Outside the other shape.

CSG Operation

3 min read•1 page

Exact Arithmetic Filter:

1. Floating Point Filter: Fast hardware evaluation with rigorous error bound calculation. 2. Adaptive Expansion: When uncertainty is detected, switches to multi-precision arbitrary-length floats. 3. Zero-Tolerance Manifold Boolean: Eliminates degenerate sliver triangles and open boundary cracks.

python

1def orient3d_exact(pa, pb, pc, pd):
2    """
3    Shewchuk's exact geometric predicate for 3D orientation.
4    Returns positive if pd lies below plane(pa, pb, pc), negative if above, 0 if coplanar.
5    Evaluates determinant using adaptive precision floating-point arithmetic.
6    """
7    adx = pa[0] - pd[0]
8    bdx = pb[0] - pd[0]
9    cdx = pc[0] - pd[0]
10    ady = pa[1] - pd[1]
11    bdy = pb[1] - pd[1]
12    cdy = pc[1] - pd[1]
13    adz = pa[2] - pd[2]
14    bdz = pb[2] - pd[2]
15    cdz = pc[2] - pd[2]
16
17    # Fast floating-point determinant estimate
18    det = (adx * (bdy * cdz - bdz * cdy) 
19         + bdx * (cdy * adz - cdz * ady) 
20         + cdx * (ady * bdz - adz * bdy))
21
22    # Error bound test: if |det| > error_bound, sign is guaranteed correct
23    # Otherwise, fallback to exact expansion arithmetic
24    return det

Robust Geometric Predicates (Shewchuk orient3d): The fatal flaw of mesh Booleans and CSG is IEEE 754 floating-point rounding. When faces are near-coplanar or edges graze vertices, round-off errors cause conflicting topological decisions, leading to non-manifold self-intersections or infinite loops. Exact predicates use adaptive precision arithmetic to guarantee 100% sound topological decisions.

Coplanar Perturbation Epsilon

0.00

Related Concepts

R-Trees

Hierarchical bounding boxes, dynamic inserts with quadratic splits, and overlap search queries.

Explore concept →

Interval Trees

1D range searching structures, center pivot partitioning, and overlap query operations.

Explore concept →

Booleans & CSG

Union, Difference, and Intersection operations.

Explore concept →