Package eu.svjatoslav.sixth.e3d.geometry

Class BspTree

java.lang.Object
eu.svjatoslav.sixth.e3d.geometry.BspTree
public class BspTree extends Object
A Binary Space Partitioning (BSP) tree 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)
See Also:

  • Field Details

    • polygons

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

    • plane

      public Plane plane
      The partitioning plane for this node.

    • front

      public BspTree front
      The front child subtree.

    • back

      public BspTree back
      The back child subtree.

  • Constructor Details

    • BspTree

      public BspTree()
      Creates an empty BSP tree with no plane or children.

    • BspTree

      public BspTree(List<SolidPolygon> polygons)
      Creates a BSP tree from a list of polygons.
      Parameters:
      polygons - the polygons to partition into a BSP tree

  • Method Details

    • clone

      public BspTree clone()
      Creates a deep clone of this BSP tree.
      Overrides:
      clone in class Object
      Returns:
      a new BspTree with cloned data

    • invert

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

    • clipPolygons

      public List<SolidPolygon> clipPolygons(List<SolidPolygon> polygons)
      Clips a list of polygons against this BSP tree, returning only the portions that lie outside the solid represented by this tree.

      This is a core CSG operation used for boolean subtraction and intersection. The method recursively traverses the BSP tree, splitting polygons at each partitioning plane and discarding interior fragments.

      Algorithm:

      1. At each node, split polygons by the partitioning plane
      2. Recursively clip front fragments against the front subtree
      3. Recursively clip back fragments against the back subtree
      4. Combine and return all surviving fragments

      Leaf nodes: If this node has no plane (leaf node), all polygons are considered outside and returned unchanged.

      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(BspTree bsp)
      Clips this BSP tree against another BSP tree.
      Parameters:
      bsp - the BSP tree to clip against

    • allPolygons

      public List<SolidPolygon> allPolygons()
      Collects all polygons from this BSP tree into a flat list.
      Returns:
      a new list containing all polygons in this tree

    • addPolygons

      public void addPolygons(List<SolidPolygon> polygons)
      Adds polygons to this BSP tree, partitioning space recursively.

      This method is the core BSP tree construction algorithm. It builds or extends the tree by choosing a partition plane and classifying each polygon:

      • Coplanar — polygons on the partition plane are stored in this node
      • Front — polygons in the front half-space (same side as plane normal) go to the front child subtree
      • Back — polygons in the back half-space (opposite to plane normal) go to the back child subtree
      • Spanning — polygons crossing the plane are split into front and back fragments, each going to its respective subtree

      For an empty tree, the first polygon's plane becomes the partition plane. Child nodes are created lazily when polygons need to be stored in them.

      Can be called multiple times to incrementally extend an existing tree, though the original partition planes remain unchanged.

      Parameters:
      polygons - the polygons to insert into this BSP tree
      See Also: