Package eu.svjatoslav.sixth.e3d.csg

Class CSGNode

java.lang.Object
eu.svjatoslav.sixth.e3d.csg.CSGNode
public class CSGNode extends Object
A node in a Binary Space Partitioning (BSP) tree used for CSG operations.

BSP trees are the data structure that makes CSG boolean operations possible. Each node divides 3D space into two half-spaces using a plane, enabling efficient spatial queries and polygon clipping.

BSP Tree Structure:

                 [Node: plane P]
                /               \
        [Front subtree]     [Back subtree]
     (same side as P's     (opposite side
        normal)             of P's normal)

Key Properties:

  • polygons: Polygons coplanar with this node's partitioning plane
  • plane: The partitioning plane that divides space
  • front: Subtree for the half-space the plane normal points toward
  • back: Subtree for the opposite half-space

CSG Algorithm Overview:

CSG boolean operations (union, subtraction, intersection) work by:

  1. Building BSP trees from both input solids
  2. Clipping each tree against the other (removing overlapping geometry)
  3. Optionally inverting trees (for subtraction and intersection)
  4. Collecting the resulting polygons
See Also:

  • Field Details

    • polygons

      public final List<CSGPolygon> polygons
      Polygons that lie on this node's partitioning plane.

      These polygons are coplanar with the plane and are stored directly in this node rather than being pushed down to child nodes. This includes both polygons originally on this plane and polygons split by planes above that ended up coplanar here.

    • plane

      public CSGPlane plane
      The partitioning plane for this node.

      This plane divides 3D space into two half-spaces: front (where the normal points) and back. All polygons in this node are coplanar with this plane. Child nodes contain polygons on their respective sides.

      Null for leaf nodes (empty subtrees).

    • front

      public CSGNode front
      The front child subtree.

      Contains polygons that lie in the front half-space of this node's plane (the side the normal points toward). May be null if no polygons exist in the front half-space.

    • back

      public CSGNode back
      The back child subtree.

      Contains polygons that lie in the back half-space of this node's plane (the side opposite the normal direction). May be null if no polygons exist in the back half-space.

  • Constructor Details

    • CSGNode

      public CSGNode()
      Creates an empty BSP node with no plane or children.

      This constructor creates a leaf node. The plane, front, and back fields will be populated when polygons are added via build(List).

    • CSGNode

      public CSGNode(List<CSGPolygon> polygons)
      Creates a BSP tree from a list of polygons.

      Delegates to build(List) to construct the tree.

      Parameters:
      polygons - the polygons to partition into a BSP tree

  • Method Details

    • clone

      public CSGNode clone()
      Creates a deep clone of this BSP tree.

      Recursively clones all child nodes and polygons. The resulting tree is completely independent of the original.

      Overrides:
      clone in class Object
      Returns:
      a new CSGNode tree with cloned data

    • invert

      public void invert()
      Inverts this BSP tree, converting "inside" to "outside" and vice versa.

      This operation is fundamental to CSG subtraction and intersection:

      • All polygon normals are flipped (reversing their facing direction)
      • All plane normals are flipped
      • Front and back subtrees are swapped

      After inversion:

      • What was solid becomes empty space
      • What was empty space becomes solid
      • Front/back relationships are reversed throughout the tree

      This is used in CSG subtraction where solid B "carves out" of solid A by inverting B, unioning, then inverting the result.

    • clipPolygons

      public List<CSGPolygon> clipPolygons(List<CSGPolygon> polygons)
      Clips a list of polygons against this BSP tree.

      This recursively removes the portions of the input polygons that lie inside the solid represented by this BSP tree. The result contains only the portions that are outside this solid.

      Algorithm:

      1. At each node, split input polygons by the node's plane
      2. Polygons in front go to front child for further clipping
      3. Polygons in back go to back child for further clipping
      4. Coplanar polygons are kept (they're on the surface)
      5. If no back child exists, back polygons are discarded (they're inside)

      This is used during CSG operations to remove overlapping geometry.

      Parameters:
      polygons - the polygons to clip against this BSP tree
      Returns:
      a new list containing only the portions outside this solid

    • clipTo

      public void clipTo(CSGNode bsp)
      Clips this BSP tree against another BSP tree.

      This removes from this tree all polygons that lie inside the solid represented by the other BSP tree. Used during CSG operations to eliminate overlapping geometry.

      The operation modifies this tree in place, replacing all polygons with their clipped versions.

      Parameters:
      bsp - the BSP tree to clip against (the "cutter")

    • allPolygons

      public List<CSGPolygon> allPolygons()
      Collects all polygons from this BSP tree into a flat list.

      Recursively traverses the entire tree and collects all polygons from all nodes. This is used after CSG operations to extract the final result as a simple polygon list.

      Returns:
      a new list containing all polygons in this tree

    • build

      public void build(List<CSGPolygon> polygonList)
      Builds or extends this BSP tree from a list of polygons.

      This is the core BSP tree construction algorithm. It partitions space by selecting a splitting plane and recursively building subtrees.

      Algorithm:

      1. If this node has no plane, use the first polygon's plane as the partitioning plane
      2. For each polygon:
        • Coplanar polygons are stored in this node
        • Front polygons go to the front list
        • Back polygons go to the back list
        • Spanning polygons are split into front and back parts
      3. Recursively build front subtree with front polygons
      4. Recursively build back subtree with back polygons

      Calling Conventions:

      • Can be called multiple times to add more polygons to an existing tree
      • Empty polygon list is a no-op
      • Creates child nodes as needed
      Parameters:
      polygonList - the polygons to add to this BSP tree