BSP CSG

1 min read•1 page

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.

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

2 min read•1 page

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.

Vertex Classification:

1. Front Face: All vertices lie in the front half-space ($d \ge 0$). 2. Back Face: All vertices lie in the back half-space ($d \le 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)

Triangle Y Shift

0.00

2 min read•1 page

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 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))

CSG Operation

3 min read•1 page

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.

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

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 →