BSP trees are an efficient way to represent space partitions and to associate attributes with each cell. Each node in a BSP tree represents a convex region which is partitioned in two convex sub-regions at each side of a cut hyperplane. The root tree contains the complete space.
The main use of such partitions is to use a boolean attribute to define an inside/outside property, hence representing arbitrary polytopes (line segments in 1D, polygons in 2D and polyhedrons in 3D) and to operate on them.
Another example would be to represent Voronoi tesselations, the attribute of each cell holding the defining point of the cell.
The application-defined attributes are shared among copied instances and propagated to split parts. These attributes are not used by the BSP-tree algorithms themselves, so the application can use them for any purpose. Since the tree visiting method holds internal and leaf nodes differently, it is possible to use different classes for internal nodes attributes and leaf nodes attributes. This should be used with care, though, because if the tree is modified in any way after attributes have been set, some internal nodes may become leaf nodes and some leaf nodes may become internal nodes.
One of the main sources for the development of this package was Bruce Naylor, John Amanatides and William Thibault paper Merging BSP Trees Yields Polyhedral Set Operations Proc. Siggraph '90, Computer Graphics 24(4), August 1990, pp 115-124, published by the Association for Computing Machinery (ACM).
| Modifier and Type | Class and Description |
|---|---|
| public static interface | BSPTree.
Type of the space. S extends Space>This interface gather the merging operations between a BSP tree leaf and another BSP tree. |
| public static interface | BSPTree.
Type of the space. S extends Space>This interface handles the corner cases when an internal node cut sub-hyperplane vanishes. |
| Modifier and Type | Field and Description |
|---|---|
| private Object | attribute
Application-defined attribute. |
| private SubHyperplane | cut
Cut sub-hyperplane. |
| private BSPTree | minus
Tree at the minus side of the cut hyperplane. |
| private BSPTree | parent
Parent tree. |
| private BSPTree | plus
Tree at the plus side of the cut hyperplane. |
| Access | Constructor and Description |
|---|---|
| public | |
| public | |
| public | BSPTree(final SubHyperplane<S>
cut sub-hyperplane for the tree cut, final BSPTree<S> plus side sub-tree plus, final BSPTree<S> minus side sub-tree minus, final Object attribute associated with the node (may be null) attribute)Build a BSPTree from its underlying elements. |
| Modifier and Type | Method and Description |
|---|---|
| private void | chopOffMinus(final Hyperplane<S>
chopping hyperplane hyperplane, final BSPTree.handler to use for handling very rare corner
cases of vanishing cut sub-hyperplanes in internal nodes during merging vanishingHandlerChop off parts of the tree. |
| private void | chopOffPlus(final Hyperplane<S>
chopping hyperplane hyperplane, final BSPTree.handler to use for handling very rare corner
cases of vanishing cut sub-hyperplanes in internal nodes during merging vanishingHandlerChop off parts of the tree. |
| private void | |
| public BSPTree | |
| private SubHyperplane | Returns: a new sub-hyperplane, guaranteed to have no part outside of the instance cellsub-hyperplane to fit sub)Fit a sub-hyperplane inside the cell defined by the instance. |
| public Object | Returns: attribute associated with the node or null if no attribute has been explicitly set using thesetAttribute methodGet the attribute associated with the instance. |
| public BSPTree | Returns: the tree cell to which the point belongspoint to check point)
Deprecated
as of 3.3, replaced with
getCell(Point, double)
Get the cell to which a point belongs. |
| public BSPTree | |
| public List | Returns: close cells (may be empty if all cut sub-hyperplanes are farther than maxOffset from the point)point to check point, final double offset below which a cut sub-hyperplane is considered
close to the point (in absolute value) maxOffset)Get the cells whose cut sub-hyperplanes are close to the point. |
| public SubHyperplane | |
| public BSPTree | Returns: tree on the minus side of the cut hyperplane, null if this is a leaf treeGet the tree on the minus side of the cut hyperplane. |
| public BSPTree | |
| public BSPTree | Returns: tree on the plus side of the cut hyperplane, null if this is a leaf treeGet the tree on the plus side of the cut hyperplane. |
| public boolean | Returns: true if a cut sub-hyperplane has been inserted (i.e. if the cell now has two leaf child nodes)hyperplane to insert, it will be chopped in
order to fit in the cell defined by the parent nodes of the
instance hyperplane)Insert a cut sub-hyperplane in a node. |
| public void | insertInTree(final BSPTree<S>
parent tree to connect to (may be null) parentTree, final boolean if true and if parentTree is not null, the
resulting tree should be the plus child of its parent, ignored if
parentTree is null isPlusChild)
Deprecated
as of 3.4, replaced with
insertInTree(BSPTree, boolean, VanishingCutHandler)
Insert the instance into another tree. |
| public void | insertInTree(final BSPTree<S>
parent tree to connect to (may be null) parentTree, final boolean if true and if parentTree is not null, the
resulting tree should be the plus child of its parent, ignored if
parentTree is null isPlusChild, final BSPTree.handler to use for handling very rare corner
cases of vanishing cut sub-hyperplanes in internal nodes during merging vanishingHandlerInsert the instance into another tree. |
| public BSPTree | Returns: a new tree, result ofinstance <op>
tree, this value can be ignored if parentTree is not null
since all connections have already been establishedother tree to merge with the instance (will be
unusable after the operation, as well as the
instance itself) tree, final BSPTree.object implementing the final merging phase
(this is where the semantic of the operation occurs, generally
depending on the attribute of the leaf node) leafMergerMerge a BSP tree with the instance. |
| private BSPTree | Returns: a new tree, result ofinstance <op>
tree, this value can be ignored if parentTree is not null
since all connections have already been establishedother tree to merge with the instance (will be
unusable after the operation, as well as the
instance itself) tree, final BSPTree.object implementing the final merging phase
(this is where the semantic of the operation occurs, generally
depending on the attribute of the leaf node) leafMerger,parent tree to connect to (may be null) parentTree, final boolean if true and if parentTree is not null, the
resulting tree should be the plus child of its parent, ignored if
parentTree is null isPlusChild)Merge a BSP tree with the instance. |
| public BSPTree | Returns: a new tree (the original tree is left untouched) containing a single branch with the cell as a leaf node, and other leaf nodes as the remnants of the pruned branchesattribute to set for the leaf node
corresponding to the initial instance cell cellAttribute, final Object attribute to set for the other leaf
nodes otherLeafsAttributes, final Object attribute to set for the internal nodes internalAttributes)Prune a tree around a cell. |
| private void | recurseCloseCuts(final Point<S>
point to check point, final double offset below which a cut sub-hyperplane is considered
close to the point (in absolute value) maxOffset, final List<BSPTree<S>> list to fill close)Get the cells whose cut sub-hyperplanes are close to the point. |
| public void | setAttribute(final Object
attribute to associate with the node attribute)Associate an attribute with the instance. |
| public BSPTree | Returns: a tree having the specified sub-hyperplane as its cut sub-hyperplane, the two parts of the split instance as its two sub-trees and a null parentpartitioning sub-hyperplane, must be already clipped
to the convex region represented by the instance, will be used as
the cut sub-hyperplane of the returned tree sub)Split a BSP tree by an external sub-hyperplane. |
| public void |
| attribute | back to summary |
|---|---|
| private Object attribute Application-defined attribute. | |
| cut | back to summary |
|---|---|
| private SubHyperplane<S> cut Cut sub-hyperplane. | |
| minus | back to summary |
|---|---|
| private BSPTree<S> minus Tree at the minus side of the cut hyperplane. | |
| parent | back to summary |
|---|---|
| private BSPTree<S> parent Parent tree. | |
| plus | back to summary |
|---|---|
| private BSPTree<S> plus Tree at the plus side of the cut hyperplane. | |
| BSPTree | back to summary |
|---|---|
| public BSPTree() Build a tree having only one root cell representing the whole space. | |
| BSPTree | back to summary |
|---|---|
| public BSPTree(final Object attribute) Build a tree having only one root cell representing the whole space.
| |
| BSPTree | back to summary |
|---|---|
| public BSPTree(final SubHyperplane<S> cut, final BSPTree<S> plus, final BSPTree<S> minus, final Object attribute) Build a BSPTree from its underlying elements. This method does not perform any verification on consistency of its arguments, it should therefore be used only when then caller knows what it is doing. This method is mainly useful to build trees
bottom-up. Building trees top-down is realized with the help of
method
| |
| chopOffMinus | back to summary |
|---|---|
| private void chopOffMinus(final Hyperplane<S> hyperplane, final BSPTree. Chop off parts of the tree. The instance is modified in place, all the parts that are on the minus side of the chopping hyperplane are discarded, only the parts on the plus side remain.
| |
| chopOffPlus | back to summary |
|---|---|
| private void chopOffPlus(final Hyperplane<S> hyperplane, final BSPTree. Chop off parts of the tree. The instance is modified in place, all the parts that are on the plus side of the chopping hyperplane are discarded, only the parts on the minus side remain.
| |
| condense | back to summary |
|---|---|
| private void condense() Perform condensation on a tree. The condensation operation is not recursive, it must be called explicitly from leaves to root. | |
| copySelf | back to summary |
|---|---|
| public BSPTree Copy the instance. The instance created is completely independent of the original one. A deep copy is used, none of the underlying objects are shared (except for the nodes attributes and immutable objects).
| |
| fitToCell | back to summary |
|---|---|
| private SubHyperplane Fit a sub-hyperplane inside the cell defined by the instance. Fitting is done by chopping off the parts of the sub-hyperplane that lie outside of the cell using the cut-hyperplanes of the parent nodes of the instance.
| |
| getAttribute | back to summary |
|---|---|
| public Object getAttribute() Get the attribute associated with the instance.
| |
| getCell | back to summary |
|---|---|
| public BSPTree Deprecated as of 3.3, replaced with Get the cell to which a point belongs. If the returned cell is a leaf node the points belongs to the interior of the node, if the cell is an internal node the points belongs to the node cut sub-hyperplane. | |
| getCell | back to summary |
|---|---|
| public BSPTree Get the cell to which a point belongs. If the returned cell is a leaf node the points belongs to the interior of the node, if the cell is an internal node the points belongs to the node cut sub-hyperplane. | |
| getCloseCuts | back to summary |
|---|---|
| public List Get the cells whose cut sub-hyperplanes are close to the point. | |
| getCut | back to summary |
|---|---|
| public SubHyperplane Get the cut sub-hyperplane.
| |
| getMinus | back to summary |
|---|---|
| public BSPTree Get the tree on the minus side of the cut hyperplane.
| |
| getParent | back to summary |
|---|---|
| public BSPTree Get the parent node.
| |
| getPlus | back to summary |
|---|---|
| public BSPTree Get the tree on the plus side of the cut hyperplane.
| |
| insertCut | back to summary |
|---|---|
| public boolean insertCut(final Hyperplane<S> hyperplane) Insert a cut sub-hyperplane in a node. The sub-tree starting at this node will be completely
overwritten. The new cut sub-hyperplane will be built from the
intersection of the provided hyperplane with the cell. If the
hyperplane does intersect the cell, the cell will have two
children cells with This method is mainly useful when called on leaf nodes
(i.e. nodes for which
| |
| insertInTree | back to summary |
|---|---|
| public void insertInTree(final BSPTree<S> parentTree, final boolean isPlusChild)
Deprecated as of 3.4, replaced with Insert the instance into another tree. The instance itself is modified so its former parent should not be used anymore.
| |
| insertInTree | back to summary |
|---|---|
| public void insertInTree(final BSPTree<S> parentTree, final boolean isPlusChild, final BSPTree. Insert the instance into another tree. The instance itself is modified so its former parent should not be used anymore.
| |
| merge | back to summary |
|---|---|
| public BSPTree Merge a BSP tree with the instance. All trees are modified (parts of them are reused in the new tree), it is the responsibility of the caller to ensure a copy has been done before if any of the former tree should be preserved, no such copy is done here! The algorithm used here is directly derived from the one described in the Naylor, Amanatides and Thibault paper (section III, Binary Partitioning of a BSP Tree).
| |
| merge | back to summary |
|---|---|
| private BSPTree Merge a BSP tree with the instance.
| |
| pruneAroundConvexCell | back to summary |
|---|---|
| public BSPTree Prune a tree around a cell. This method can be used to extract a convex cell from a tree. The original cell may either be a leaf node or an internal node. If it is an internal node, it's subtree will be ignored (i.e. the extracted cell will be a leaf node in all cases). The original tree to which the original cell belongs is not touched at all, a new independent tree will be built.
| |
| recurseCloseCuts | back to summary |
|---|---|
| private void recurseCloseCuts(final Point<S> point, final double maxOffset, final List<BSPTree<S>> close) Get the cells whose cut sub-hyperplanes are close to the point. | |
| setAttribute | back to summary |
|---|---|
| public void setAttribute(final Object attribute) Associate an attribute with the instance.
| |
| split | back to summary |
|---|---|
| public BSPTree Split a BSP tree by an external sub-hyperplane. Split a tree in two halves, on each side of the sub-hyperplane. The instance is not modified. The tree returned is not upward-consistent: despite all of its sub-trees cut sub-hyperplanes (including its own cut sub-hyperplane) are bounded to the current cell, it is not attached to any parent tree yet. This tree is intended to be later inserted into an higher level tree. The algorithm used here is the one given in Naylor, Amanatides and Thibault paper (section III, Binary Partitioning of a BSP Tree).
| |
| visit | back to summary |
|---|---|
| public void visit(final BSPTreeVisitor<S> visitor) Visit the BSP tree nodes.
| |
As explained in Bruce Naylor, John Amanatides and William
Thibault paper Merging
BSP Trees Yields Polyhedral Set Operations,
the operations on BSP trees can be expressed as a
generic recursive merging operation where only the final part,
when one of the operand is a leaf, is specific to the real
operation semantics. For example, a tree representing a region
using a boolean attribute to identify inside cells and outside
cells would use four different objects to implement the final
merging phase of the four set operations union, intersection,
difference and symmetric difference (exclusive or).
| Modifier and Type | Method and Description |
|---|---|
| public BSPTree | Returns: the BSP tree resulting from the merging (may be one of the arguments)leaf node (its cut hyperplane is guaranteed to be
null) leaf, BSPTree<S> tree node (its cut hyperplane may be null or not) tree, BSPTree<S> parent tree to connect to (may be null) parentTree, boolean if true and if parentTree is not null, the
resulting tree should be the plus child of its parent, ignored if
parentTree is null isPlusChild, boolean if true, the leaf node comes from the
instance tree ( leafFromInstance)tree1) and the tree node comes from
the argument tree (tree2)Merge a leaf node and a tree node. |
| merge | back to summary |
|---|---|
| public BSPTree Merge a leaf node and a tree node. This method is called at the end of a recursive merging
resulting from a Since the final operation may be non-commutative, it is
important to know if the leaf node comes from the instance tree
( The
| |
Such cases happens for example when a cut sub-hyperplane is inserted into another tree (during a merge operation), and is split in several parts, some of which becomes smaller than the tolerance. The corresponding node as then no cut sub-hyperplane anymore, but does have children. This interface specifies how to handle this situation. setting
| Modifier and Type | Method and Description |
|---|---|
| public BSPTree |
| fixNode | back to summary |
|---|---|
| public BSPTree Fix a node with both vanished cut and children. | |