Class AbstractPartitionedRegionBuilder<P extends Point<P>,​N extends AbstractRegionBSPTree.AbstractRegionNode<P,​N>>

  • Type Parameters:
    P - Point implementation type
    N - BSP tree node implementation type
    Direct Known Subclasses:
    RegionBSPTree2D.PartitionedRegionBuilder2D, RegionBSPTree3D.PartitionedRegionBuilder3D

    public abstract class AbstractPartitionedRegionBuilder<P extends Point<P>,​N extends AbstractRegionBSPTree.AbstractRegionNode<P,​N>>
    extends java.lang.Object
    Class encapsulating logic for building regions by inserting boundaries into a BSP tree containing structural cuts, i.e. cuts where both sides of the cut have the same region location. This technique only produces accurate results when the inserted boundaries define the entire surface of the region. However, for valid input boundaries, significant performance improvements can be achieved due to the reduced height of the tree, especially where large numbers of boundaries are involved and/or the defined region is convex.

    Implementation Notes

    This class constructs regions in two phases: (1) partition insertion and (2) boundary insertion. Instances begin in the partition insertion phase. Here, partitions can be inserted into the empty tree using the standard BSP insertion logic. The INHERIT cut rule is used so that the represented region remains empty even as partitions are inserted.

    The instance moves into the boundary insertion phase when the caller inserts the first region boundary. Attempting to insert a partition after this point results in an IllegalStateException. This ensures that partitioning cuts are always located higher up the tree than boundary cuts.

    After all boundaries are inserted, the tree undergoes final processing to ensure that the region is consistent and that unnecessary nodes are removed.

    This class does not expose any public methods so that subclasses can present their own public API, tailored to the specific types being worked with. In particular, most subclasses will want to restrict the tree types used with the algorithm, which is difficult to implement cleanly at this level.

    • Constructor Detail

      • AbstractPartitionedRegionBuilder

        protected AbstractPartitionedRegionBuilder​(AbstractRegionBSPTree<P,​N> tree)
        Construct a new instance that builds a partitioned region in the given tree. The tree must be empty.
        Parameters:
        tree - tree to build the region in; must be empty
        Throws:
        java.lang.IllegalArgumentException - if the tree is not empty
    • Method Detail

      • buildInternal

        protected AbstractRegionBSPTree<P,​N> buildInternal()
        Internal method to build and return the tree representing the final partitioned region.
        Returns:
        the partitioned region
      • insertPartitionInternal

        protected void insertPartitionInternal​(HyperplaneConvexSubset<P> partition)
        Internal method to insert a partition into the tree.
        Parameters:
        partition - partition to insert
        Throws:
        java.lang.IllegalStateException - if a boundary has previously been inserted
      • insertBoundaryInternal

        protected void insertBoundaryInternal​(HyperplaneConvexSubset<P> boundary)
        Internal method to insert a region boundary into the tree.
        Parameters:
        boundary - boundary to insert
      • insertBoundaryRecursive

        private void insertBoundaryRecursive​(N node,
                                             HyperplaneConvexSubset<P> insert,
                                             HyperplaneConvexSubset<P> trimmed,
                                             java.util.function.BiConsumer<N,​HyperplaneConvexSubset<P>> leafFn)
        Insert a region boundary into the tree.
        Parameters:
        node - node to insert into
        insert - the hyperplane convex subset to insert
        trimmed - version of the hyperplane convex subset filling the entire space of node
        leafFn - function to apply to leaf nodes
      • propagateRegionInterior

        private boolean propagateRegionInterior()
        Propagate the region interior to partitioned leaf nodes that have not had a boundary inserted.
        Returns:
        true if any nodes were changed
      • getOutsidePartitionedLeaves

        private java.util.List<N> getOutsidePartitionedLeaves()
        Return a list containing all outside leaf nodes that have a parent marked as a partition node.
        Returns:
        a list containing all outside leaf nodes that have a parent marked as a partition node
      • collectOutsidePartitionedLeavesRecursive

        private void collectOutsidePartitionedLeavesRecursive​(N node,
                                                              boolean parentIsPartitionNode,
                                                              java.util.List<N> result)
        Recursively collect all outside leaf nodes that have a parent marked as a partition node.
        Parameters:
        node - root of the subtree to collect nodes from
        parentIsPartitionNode - true if the parent of node is a partition node
        result - list of accumulated results
      • touchesInside

        private boolean touchesInside​(HyperplaneConvexSubset<P> sub,
                                      N node)
        Return true if sub touches an inside leaf node anywhere in the subtree rooted at node.
        Parameters:
        sub - convex subset to check
        node - root node of the subtree to test against
        Returns:
        true if sub touches an inside leaf node anywhere in the subtree rooted at node
      • isPartitionNode

        private boolean isPartitionNode​(N node)
        Return true if the given node is marked as a partition node.
        Parameters:
        node - node to check
        Returns:
        true if the given node is marked as a partition node
      • ensureInsertingPartitions

        private void ensureInsertingPartitions()
        Throw an exception if the instance is no longer accepting partitions.
        Throws:
        java.lang.IllegalStateException - if the instance is no longer accepting partitions