Bounding Volume Hierarchy
BoundingVolumeHierarchy(vertices, simplices=None, **kwargs)
Bounding Volume Hierarchy for closest point and distance queries to a set of points, of edges in 2D or of triangles in 3D. The BVH is dimension-agnostic and works with 3D as well as 2D data.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
vertices
|
ndarray
|
array of shape (n_vertices, dim) of vertex positions. |
required |
simplices
|
ndarray
|
array of shape (n_simplices, dim) of vertex indices: edges in 2D or triangles in 3D. If not provided, the BVH is built over the vertices only. Defaults to None. |
None
|
Other Parameters:
| Name | Type | Description |
|---|---|---|
leaf_size |
int
|
Maximal number of primitives stored in a leaf of the hierarchy. Defaults to 10. |
n_workers |
int
|
Number of parallel workers to consider for queries. If unspecified, will be set to the maximum number of numba threads. |
Attributes:
| Name | Type | Description |
|---|---|---|
perm |
ndarray
|
permutation of the primitives such that the primitives of each node are contiguous. |
bb_pmin |
ndarray
|
minimal corner of the bounding box of each node. |
bb_pmax |
ndarray
|
maximal corner of the bounding box of each node. |
left |
ndarray
|
index of the left child of each node (-1 for leaves). |
right |
ndarray
|
index of the right child of each node (-1 for leaves). |
node_start |
ndarray
|
index in |
node_count |
ndarray
|
number of primitives in each node. |
Raises:
| Type | Description |
|---|---|
Exception
|
if the simplices do not have as many vertices as the dimension of the points. |
query_distance(x, oriented=False)
Computes the distance from query points to the closest primitive of the BVH, and the corresponding closest points.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
x
|
ndarray
|
query points, either a single point of shape (dim,) or an array of shape (n_queries, dim). |
required |
oriented
|
bool
|
Whether to orient the distance using the angle-weighted pseudonormal of the closest primitive feature (face, edge or vertex). The distance is then negative for points lying on the opposite side of the normals, which is the inside of the shape for a closed mesh whose faces are consistently oriented outward (in 2D, for closed polylines whose edges run counter-clockwise around the interior). The orientation of the input is trusted: the sign is meaningless for inconsistently oriented meshes. The pseudonormals are computed on the fly during the first query. Defaults to False. |
False
|
Returns:
| Type | Description |
|---|---|
|
np.ndarray: array of shape (n_queries,) of distances. |
|
|
np.ndarray: array of shape (n_queries, dim) of closest points. |