Class RegionBSPTree3D.PartitionedRegionBuilder3D
- java.lang.Object
-
- org.apache.commons.geometry.core.partitioning.bsp.AbstractPartitionedRegionBuilder<Vector3D,RegionBSPTree3D.RegionNode3D>
-
- org.apache.commons.geometry.euclidean.threed.RegionBSPTree3D.PartitionedRegionBuilder3D
-
- Enclosing class:
- RegionBSPTree3D
public static final class RegionBSPTree3D.PartitionedRegionBuilder3D extends AbstractPartitionedRegionBuilder<Vector3D,RegionBSPTree3D.RegionNode3D>
Class used to build regions in Euclidean 3D space by inserting boundaries into a BSP tree containing "partitions", i.e. structural cuts where both sides of the cut have the same region location. When partitions are chosen that effectively divide the region boundaries at each partition level, the constructed tree is shallower and more balanced than one constructed from the region boundaries alone, resulting in improved performance. For example, consider a mesh approximation of a sphere. The region is convex so each boundary has all of the other boundaries on its minus side; the plus sides are all empty. When these boundaries are inserted directly into a tree, the tree degenerates into a simple linked list of nodes with a height directly proportional to the number of boundaries. This means that many operations on the tree, such as inside/outside testing of points, involve iterating through each and every region boundary. In contrast, if a partition is first inserted that passes through the sphere center, the first BSP tree node contains region nodes on its plus and minus sides, cutting the height of the tree in half. Operations such as inside/outside testing are then able to skip half of the tree nodes with a single test on the root node, resulting in drastically improved performance. Insertion of additional partitions (using a grid layout, for example) can produce even shallower trees, although there is a point unique to each boundary set at which the addition of more partitions begins to decrease instead of increase performance.Usage
Usage of this class consists of 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
insertPartition
or similar methods. TheINHERIT
cut rule is used internally to insert the cut so 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, using
insertBoundary
or similar methods. Attempting to insert a partition after this point results in anIllegalStateException
. This ensures that partitioning cuts are always located higher up the tree than boundary cuts.After all boundaries are inserted, the
build
method is used to perform final processing and return the computed tree.
-
-
Constructor Summary
Constructors Modifier Constructor Description private
PartitionedRegionBuilder3D()
Construct a new builder instance.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description RegionBSPTree3D
build()
Build and return the region BSP tree.RegionBSPTree3D.PartitionedRegionBuilder3D
insertAxisAlignedGrid(Bounds3D bounds, int level, org.apache.commons.numbers.core.Precision.DoubleEquivalence precision)
Insert a 3D grid of partitions.private void
insertAxisAlignedGridRecursive(Vector3D min, Vector3D max, int level, org.apache.commons.numbers.core.Precision.DoubleEquivalence precision)
Recursively insert axis-aligned grid partitions.RegionBSPTree3D.PartitionedRegionBuilder3D
insertAxisAlignedPartitions(Vector3D center, org.apache.commons.numbers.core.Precision.DoubleEquivalence precision)
Insert a set of three axis aligned planes intersecting at the given point as partitions.RegionBSPTree3D.PartitionedRegionBuilder3D
insertBoundaries(java.lang.Iterable<? extends PlaneConvexSubset> boundaries)
Insert a collection of region boundaries.RegionBSPTree3D.PartitionedRegionBuilder3D
insertBoundaries(BoundarySource3D boundarySrc)
Insert all boundaries from the given source.RegionBSPTree3D.PartitionedRegionBuilder3D
insertBoundary(PlaneConvexSubset boundary)
Insert a region boundary.RegionBSPTree3D.PartitionedRegionBuilder3D
insertPartition(Plane partition)
Insert a partition plane.RegionBSPTree3D.PartitionedRegionBuilder3D
insertPartition(PlaneConvexSubset partition)
Insert a plane convex subset as a partition.-
Methods inherited from class org.apache.commons.geometry.core.partitioning.bsp.AbstractPartitionedRegionBuilder
buildInternal, insertBoundaryInternal, insertPartitionInternal
-
-
-
-
Method Detail
-
insertPartition
public RegionBSPTree3D.PartitionedRegionBuilder3D insertPartition(Plane partition)
Insert a partition plane.- Parameters:
partition
- partition to insert- Returns:
- this instance
- Throws:
java.lang.IllegalStateException
- if a boundary has previously been inserted
-
insertPartition
public RegionBSPTree3D.PartitionedRegionBuilder3D insertPartition(PlaneConvexSubset partition)
Insert a plane convex subset as a partition.- Parameters:
partition
- partition to insert- Returns:
- this instance
- Throws:
java.lang.IllegalStateException
- if a boundary has previously been inserted
-
insertAxisAlignedPartitions
public RegionBSPTree3D.PartitionedRegionBuilder3D insertAxisAlignedPartitions(Vector3D center, org.apache.commons.numbers.core.Precision.DoubleEquivalence precision)
Insert a set of three axis aligned planes intersecting at the given point as partitions. The planes all contain thecenter
point and have the normals+x
,+y
, and+z
in that order. If inserted into an empty tree, this will partition the space into 8 sections.- Parameters:
center
- center point for the partitions; all 3 inserted planes intersect at this pointprecision
- precision context used to construct the planes- Returns:
- this instance
- Throws:
java.lang.IllegalStateException
- if a boundary has previously been inserted
-
insertAxisAlignedGrid
public RegionBSPTree3D.PartitionedRegionBuilder3D insertAxisAlignedGrid(Bounds3D bounds, int level, org.apache.commons.numbers.core.Precision.DoubleEquivalence precision)
Insert a 3D grid of partitions. The partitions are constructed recursively: at each level a set of three axis-aligned partitioning planes are inserted usinginsertAxisAlignedPartitions
. The algorithm then recurses using bounding boxes from the min point to the center and from the center point to the max. Note that this means no partitions are ever inserted directly on the boundaries of the given bounding box. This is intentional and done to allow this method to be called directly with the bounding box from a set of boundaries to be inserted without unnecessarily adding partitions that will never have region boundaries on both sides.- Parameters:
bounds
- bounding box for the gridlevel
- recursion level for the grid; each level subdivides each grid cube into 8 sections, making the total number of grid cubes equal to8 ^ level
precision
- precision context used to construct the partition planes- Returns:
- this instance
- Throws:
java.lang.IllegalStateException
- if a boundary has previously been inserted
-
insertAxisAlignedGridRecursive
private void insertAxisAlignedGridRecursive(Vector3D min, Vector3D max, int level, org.apache.commons.numbers.core.Precision.DoubleEquivalence precision)
Recursively insert axis-aligned grid partitions.- Parameters:
min
- min point for the grid cube to partitionmax
- max point for the grid cube to partitionlevel
- current recursion levelprecision
- precision context used to construct the partition planes
-
insertBoundary
public RegionBSPTree3D.PartitionedRegionBuilder3D insertBoundary(PlaneConvexSubset boundary)
Insert a region boundary.- Parameters:
boundary
- region boundary to insert- Returns:
- this instance
-
insertBoundaries
public RegionBSPTree3D.PartitionedRegionBuilder3D insertBoundaries(java.lang.Iterable<? extends PlaneConvexSubset> boundaries)
Insert a collection of region boundaries.- Parameters:
boundaries
- boundaries to insert- Returns:
- this instance
-
insertBoundaries
public RegionBSPTree3D.PartitionedRegionBuilder3D insertBoundaries(BoundarySource3D boundarySrc)
Insert all boundaries from the given source.- Parameters:
boundarySrc
- source of boundaries to insert- Returns:
- this instance
-
build
public RegionBSPTree3D build()
Build and return the region BSP tree.- Returns:
- the region BSP tree
-
-