Datastructures

Bounding-volume hierarchy

compas_model.datastructures.bvh

Classes

AABBNode

AABBNode(objects: list[BVHObject[T]])

BVH tree node with an axis-aligned bounding box as bounding volume.

Methods:

compute_box

compute_box() -> Box

Compute the axis-aligned box of the collections of primitives in this node.

Returns:

• Box –

  The axis-aligned box.

intersect_box

intersect_box(box: Box) -> Generator[BVHNode[T], None, None]

Intersect this node with a box to find all intersected descending nodes.

Parameters:

• box (Box) –

Yields:

• AABBNode –

  Intersected descending nodes.

intersect_line

intersect_line(line: Line) -> Generator[BVHNode[T], None, None]

Intersect this node with a line to find all intersected descending nodes.

Parameters:

• line (Line) –

Yields:

• AABBNode –

  Intersected descending nodes.

overlaps

overlaps(other: BVHNode[Any]) -> bool

Determine whether this node overlaps another node.

BVH

BVH(
    nodetype: type[BVHNode[T]] = AABBNode,
    max_depth: int | None = None,
    leafsize: int = 1,
)

Binary bounding volume hierarchy.

Parameters:

• nodetype (type[BVHNode[T]], default: AABBNode ) –

  The type of bounding volume node to use in the tree.

• max_depth (int | None, default: None ) –

  The maximum depth of the tree.

• leafsize (int, default: 1 ) –

  The number of objects contained by a leaf.

Attributes

leaves property

leaves: list[BVHNode[T]]

All leaf nodes in breadth-first order.

nodes property

nodes: list[BVHNode[T]]

All nodes in breadth-first order.

Methods:

from_breps classmethod

from_breps(
    triangles: list[Brep],
    nodetype: type[BVHNode[Brep]] = AABBNode,
    max_depth: int | None = None,
    leafsize: int = 1,
) -> BVH[Brep]

Construct a BVH from a collection of breps.

Parameters:

• triangles (list[Brep]) –

  A list of brep objects.

• nodetype (type[BVHNode[Brep]], default: AABBNode ) –

  The type of node to use during construction.

• max_depth (int | None, default: None ) –

  The maximum depth of the tree.

• leafsize (int, default: 1 ) –

  The maximum number of breps contained in a leaf node.

Returns:

• BVH –

  The constructed tree.

from_mesh staticmethod

from_mesh(
    mesh: Mesh,
    nodetype: type[BVHNode[list[Point]]] = AABBNode,
    max_depth: int | None = None,
    leafsize: int = 1,
) -> BVH[list[Point]]

Construct a BVH from a mesh.

Parameters:

• mesh (Mesh) –

  A mesh data structure.

• nodetype (type[BVHNode[list[Point]]], default: AABBNode ) –

  The type of node to use during construction.

• max_depth (int | None, default: None ) –

  The maximum depth of the tree.

• leafsize (int, default: 1 ) –

  The maximum number of mesh faces contained in a leaf node.

Returns:

• BVH –

  The constructed tree.

from_meshes classmethod

from_meshes(
    meshes: list[Mesh],
    nodetype: type[BVHNode[Mesh]] = AABBNode,
    max_depth: int | None = None,
    leafsize: int = 1,
) -> BVH[Mesh]

Construct a BVH from a collection of meshes.

Parameters:

• meshes (list[Mesh]) –

  A list of mesh objects.

• nodetype (type[BVHNode[Mesh]], default: AABBNode ) –

  The type of node to use during construction.

• max_depth (int | None, default: None ) –

  The maximum depth of the tree.

• leafsize (int, default: 1 ) –

  The maximum number of meshes contained in a leaf node.

Returns:

• BVH –

  The constructed tree.

from_polyhedrons classmethod

from_polyhedrons(
    polyhedrons: list[Polyhedron],
    nodetype: type[BVHNode[Polyhedron]] = AABBNode,
    max_depth: int | None = None,
    leafsize: int = 1,
) -> BVH[Polyhedron]

Construct a BVH from a collection of polyhedrons.

Parameters:

• polyhedrons (list[Polyhedron]) –

  A list of polyhedron objects.

• nodetype (type[BVHNode[Polyhedron]], default: AABBNode ) –

  The type of node to use during construction.

• max_depth (int | None, default: None ) –

  The maximum depth of the tree.

• leafsize (int, default: 1 ) –

  The maximum number of polyhedrons contained in a leaf node.

Returns:

• BVH –

  The constructed tree.

from_triangles staticmethod

from_triangles(
    triangles: list[list[Point]],
    nodetype: type[BVHNode[list[Point]]] = AABBNode,
    max_depth: int | None = None,
    leafsize: int = 1,
) -> BVH[list[Point]]

Construct a BVH from a collection of triangles.

Parameters:

• triangles (list[list[Point]]) –

  A list of triangles, with each triangle represented by three points.

• nodetype (type[BVHNode[list[Point]]], default: AABBNode ) –

  The type of node to use during construction.

• max_depth (int | None, default: None ) –

  The maximum depth of the tree.

• leafsize (int, default: 1 ) –

  The maximum number of triangles contained in a leaf node.

Returns:

• BVH –

  The constructed tree.

intersect_box

intersect_box(box: Box) -> Generator[BVHNode, None, None]

Intersect the tree with a box to find all intersected nodes in descending order.

Parameters:

• box (Box) –

Yields:

• BVHNode –

  Intersected nodes.

intersect_line

intersect_line(line: Line) -> Generator[BVHNode, None, None]

Intersect the tree with a line to find all intersected nodes in descending order.

Parameters:

• line (Line) –

Yields:

• BVHNode –

  Intersected nodes.

intersect_sphere

intersect_sphere(sphere: Sphere) -> Generator[BVHNode, None, None]

Intersect the tree with a sphere to find all intersected nodes in descending order.

Parameters:

• sphere (Sphere) –

Yields:

• BVHNode –

  Intersected nodes.

overlap_pairs

overlap_pairs(
    other: BVH[U], *, self_collision: bool = False
) -> Generator[tuple[BVHObject[T], BVHObject[U]], None, None]

Yield broad-phase object pairs from overlapping BVH leaves.

Parameters:

• other (BVH[U]) –

  The other bounding volume hierarchy.

• self_collision (bool, default: False ) –

  Enable comparison of a hierarchy with itself. This is ignored when comparing different hierarchies.

Yields:

• tuple[BVHObject[T], BVHObject[U]] –

  Pairs of object records from overlapping leaf nodes.

Raises:

• ValueError –

  If a hierarchy is compared with itself without enabling self_collision.

Notes

The yielded pairs are broad-phase candidates. Their bounding volumes overlap, but the underlying geometry may not. Result ordering is not part of the public contract.

During self-collision traversal, an object is never paired with itself and each unordered object pair is yielded at most once.

rebuild

rebuild() -> None

Rebuild the tree using the current objects.

refit

refit() -> None

Refit the tree to the current objects.

BVHNode

BVHNode(objects: list[BVHObject[T]])

Base BVH tree node.

Parameters:

• objects (list[BVHObject[T]]) –

  The objects contained by the node.

Attributes

children property

children: list[BVHNode[T]]

The child nodes in left-to-right order.

is_leaf property

is_leaf: bool

Determine whether the node has no children.

Methods:

add

add(node: BVHNode[T]) -> None

Add a child node and update its hierarchy metadata.

Raises:

• ValueError –

  If the node already has two children or the child already has a parent.

compute_box

compute_box() -> Box

Compute the bounding box of the node.

Returns:

• Box –

  The bounding box.

intersect_box

intersect_box(box: Box) -> Generator[BVHNode, None, None]

Intersect this node with a box to find all intersected descending nodes.

Parameters:

• box (Box) –

Yields:

• BVHNode –

  Intersected descending nodes.

intersect_line

intersect_line(line: Line) -> Generator[BVHNode, None, None]

Intersect this node with a line to find all intersected descending nodes.

Parameters:

• line (Line) –

Yields:

• BVHNode –

  Intersected descending nodes.

intersect_sphere

intersect_sphere(sphere: Sphere) -> Generator[BVHNode, None, None]

Intersect this node with a sphere to find all intersected descending nodes.

Parameters:

• sphere (Sphere) –

Yields:

• BVHNode –

  Intersected descending nodes.

overlaps

overlaps(other: BVHNode[Any]) -> bool

Determine whether this node overlaps another node.

Parameters:

• other (BVHNode[Any]) –

  The other node.

Returns:

• bool –

  True if the node bounding boxes overlap.

BVHObject dataclass

BVHObject(key: Hashable, centroid: Point, payload: T, points: list[Point])

Object record stored in a bounding volume hierarchy.

Parameters:

• key (Hashable) –

  Identifier of the object in its source collection.

• centroid (Point) –

  Representative point used to partition the hierarchy.

• payload (T) –

  The application-specific object.

• points (list[Point]) –

  Points used to compute bounding volumes.

OBBNode

OBBNode(objects: list[BVHObject[T]])

BVH tree node with an oriented bounding box as bounding volume.

Methods:

compute_box

compute_box() -> Box

Compute the oriented box of the collections of primitives in this node.

Returns:

• Box –

  The oriented box.

intersect_box

intersect_box(box: Box) -> Generator[BVHNode[T], None, None]

Intersect this node with a box to find all intersected descending nodes.

Parameters:

• box (Box) –

Yields:

• OBBNode –

  Intersected descending nodes.

intersect_line

intersect_line(line: Line) -> Generator[BVHNode[T], None, None]

Intersect this node with a line to find all intersected descending nodes.

Parameters:

• line (Line) –

Yields:

• OBBNode –

  Intersected descending nodes.

intersect_sphere

intersect_sphere(sphere: Sphere) -> Generator[BVHNode[T], None, None]

Intersect this node with a line to find all intersected descending nodes.

Parameters:

• sphere (Sphere) –

Yields:

• OBBNode –

  Intersected descending nodes.

overlaps

overlaps(other: BVHNode[Any]) -> bool

Determine whether this node overlaps another node.

KD-tree

compas_model.datastructures.kdtree

Classes

KDTree

KDTree(elements: list[Element])

A tree for nearest neighbor search in a k-dimensional space.

Parameters:

• elements (list[Element]) –

  A list of objects to populate the tree with. The tree is built automatically.

References

Wikipedia, k-d tree: https://en.wikipedia.org/wiki/K-d_tree Dell'Amico, M. KD-Tree for nearest neighbor search in a K-dimensional space (Python recipe): http://code.activestate.com/recipes/577497-kd-tree-for-nearest-neighbor-search-in-a-k-dimensional-space/.

Methods:

nearest_neighbor

nearest_neighbor(
    point: Point, exclude: Iterable[Element] | None = None
) -> tuple[Element, float]

Find the nearest neighbor to a given point, excluding neighbors that have already been found.

Parameters:

• point (Point) –

  The base point.

• exclude (Iterable[Element] | None, default: None ) –

  A sequence of point identified by their label to exclude from the search.

Returns:

• tuple[Element, float] –

  The nearest neighbor and its distance to the base point.

nearest_neighbors

nearest_neighbors(
    point: Point, number: int, distance_sort: bool = False
) -> list[tuple[Element, float]]

Find the N nearest neighbors to a given point.

Parameters:

• point (Point) –

  The base point.

• number (int) –

  The number of nearest neighbors.

• distance_sort (bool, default: False ) –

  Sort the nearest neighbors by distance to the base point.

Returns:

• list[tuple[Element, float]] –

  A list of N nearest neighbors.