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