lagrange.bvh¶

bvh module

Classes¶

`EdgeAABBTree2D`
`EdgeAABBTree3D`
`TriangleAABBTree2D`
`TriangleAABBTree3D`
`UVOverlapMethod`	Create a collection of name/value pairs.

Functions¶

`compute_chamfer`(source, target)	Compute the Chamfer distance between two meshes.
`compute_hausdorff`(source, target)	Compute the symmetric Hausdorff distance between two meshes.
`compute_intersecting_pairs`(mesh)	Compute all pairs of intersecting facets in a triangle mesh using BVH acceleration.
`compute_mesh_distances`(source, target[, ...])	Compute the distance from each vertex in source to the closest point on target.
`compute_uv_overlap`(mesh[, uv_attribute_name, ...])	Compute pairwise UV triangle overlap.
`remove_interior_shells`(mesh)	Removes interior shells from a (manifold, non-intersecting) mesh
`resolve_tjunctions`(mesh, *[, tolerance, ...])	Resolve T-junctions formed by collinear, overlapping edges.
`weld_vertices`(mesh[, radius, boundary_only])	Weld nearby vertices together of a surface mesh.

Module Contents¶

class lagrange.bvh.EdgeAABBTree2D(vertices, edges)¶

Parameters:

vertices (Annotated[numpy.typing.NDArray[numpy.float64], dict(shape=(None, 2), order='F')])
edges (Annotated[numpy.typing.NDArray[numpy.uint32], dict(shape=(None, 2), order='F')])

empty()¶

Check if the tree is empty

Return type:: bool

get_closest_point(query_point)¶

Find the closest element and point within the element to the query point

Parameters:: query_point (list | Annotated[numpy.typing.NDArray[numpy.float64], dict(shape=2, order='C', device='cpu')]) – Query point.
Returns:: A tuple containing: - The index of the closest element. - A NumPy array representing the closest point on the element. - The squared distance between the query point and the closest point.
Return type:: tuple[int, Annotated[numpy.typing.NDArray[numpy.float64], dict(shape=2, order=’C’)], float]

get_containing_elements(query_point)¶

Find all elements that contain the query point.

Parameters:: query_point (list | Annotated[numpy.typing.NDArray[numpy.float64], dict(shape=2, order='C', device='cpu')]) – Query point.
Returns:: A list of element indices that contain the query point.
Return type:: list[int]

get_element_closest_point(query_point, element_id)¶

Get the closest point on a specific edge.

Parameters:

query_point (list | Annotated[numpy.typing.NDArray[numpy.float64], dict(shape=2, order='C', device='cpu')]) – Query point.
element_id (int) – Index of the edge to query.

Returns:

A tuple containing: - A NumPy array representing the closest point on the edge. - The squared distance between the query point and the closest point.

Return type:

tuple[Annotated[numpy.typing.NDArray[numpy.float64], dict(shape=2, order=’C’)], float]

get_elements_in_radius(query_point, radius)¶

Find all elements within a given radius from a query point.

Parameters:

query_point (list | Annotated[numpy.typing.NDArray[numpy.float64], dict(shape=2, order='C', device='cpu')]) – Query point.
radius (float) – Search radius.

Returns:

A tuple containing: - A list of element indices within the specified radius. - A NumPy array of shape (N, 2) containing the closest points on each element.

Return type:

tuple[list[int], Annotated[numpy.typing.NDArray[numpy.float64], dict(shape=(None, 2), order=’C’, device=’cpu’)]]

class lagrange.bvh.EdgeAABBTree3D(vertices, edges)¶

Parameters:

vertices (Annotated[numpy.typing.NDArray[numpy.float64], dict(shape=(None, 3), order='F')])
edges (Annotated[numpy.typing.NDArray[numpy.uint32], dict(shape=(None, 2), order='F')])

empty()¶

Check if the tree is empty

Return type:: bool

get_closest_point(query_point)¶

Find the closest element and point within the element to the query point

Parameters:: query_point (list | Annotated[numpy.typing.NDArray[numpy.float64], dict(shape=3, order='C', device='cpu')]) – Query point.
Returns:: A tuple containing: - The index of the closest element. - A NumPy array representing the closest point on the element. - The squared distance between the query point and the closest point.
Return type:: tuple[int, Annotated[numpy.typing.NDArray[numpy.float64], dict(shape=3, order=’C’)], float]

get_containing_elements(query_point)¶

Find all elements that contain the query point.

Parameters:: query_point (list | Annotated[numpy.typing.NDArray[numpy.float64], dict(shape=3, order='C', device='cpu')]) – Query point.
Returns:: A list of element indices that contain the query point.
Return type:: list[int]

get_element_closest_point(query_point, element_id)¶

Get the closest point on a specific edge.

Parameters:

query_point (list | Annotated[numpy.typing.NDArray[numpy.float64], dict(shape=3, order='C', device='cpu')]) – Query point.
element_id (int) – Index of the edge to query.

Returns:

A tuple containing: - A NumPy array representing the closest point on the edge. - The squared distance between the query point and the closest point.

Return type:

tuple[Annotated[numpy.typing.NDArray[numpy.float64], dict(shape=3, order=’C’)], float]

get_elements_in_radius(query_point, radius)¶

Find all elements within a given radius from a query point.

Parameters:

query_point (list | Annotated[numpy.typing.NDArray[numpy.float64], dict(shape=3, order='C', device='cpu')]) – Query point.
radius (float) – Search radius.

Returns:

A tuple containing: - A list of element indices within the specified radius. - A NumPy array of shape (N, 3) containing the closest points on each element.

Return type:

tuple[list[int], Annotated[numpy.typing.NDArray[numpy.float64], dict(shape=(None, 3), order=’C’, device=’cpu’)]]

class lagrange.bvh.TriangleAABBTree2D(mesh)¶

Parameters:: mesh (lagrange.core.SurfaceMesh)

empty()¶

Check if the tree is empty

Return type:: bool

get_closest_point(query_point)¶

Find the closest element and point within the element to the query point

Parameters:: query_point (list | Annotated[numpy.typing.NDArray[numpy.float64], dict(shape=2, order='C', device='cpu')]) – Query point.
Returns:: A tuple containing: - The index of the closest element. - A NumPy array representing the closest point on the element. - The squared distance between the query point and the closest point.
Return type:: tuple[int, Annotated[numpy.typing.NDArray[numpy.float64], dict(shape=2, order=’C’)], float]

get_elements_in_radius(query_point, radius)¶

Find all elements within a given radius from a query point.

Parameters:

query_point (list | Annotated[numpy.typing.NDArray[numpy.float64], dict(shape=2, order='C', device='cpu')]) – Query point.
radius (float) – Search radius.

Returns:

A tuple containing: - A list of element indices within the specified radius. - A NumPy array of shape (N, 2) containing the closest points on each element.

Return type:

tuple[list[int], Annotated[numpy.typing.NDArray[numpy.float64], dict(shape=(None, 2), order=’C’, device=’cpu’)]]

class lagrange.bvh.TriangleAABBTree3D(mesh)¶

Parameters:: mesh (lagrange.core.SurfaceMesh)

empty()¶

Check if the tree is empty

Return type:: bool

get_closest_point(query_point)¶

Find the closest element and point within the element to the query point

Parameters:: query_point (list | Annotated[numpy.typing.NDArray[numpy.float64], dict(shape=3, order='C', device='cpu')]) – Query point.
Returns:: A tuple containing: - The index of the closest element. - A NumPy array representing the closest point on the element. - The squared distance between the query point and the closest point.
Return type:: tuple[int, Annotated[numpy.typing.NDArray[numpy.float64], dict(shape=3, order=’C’)], float]

get_elements_in_radius(query_point, radius)¶

Find all elements within a given radius from a query point.

Parameters:

query_point (list | Annotated[numpy.typing.NDArray[numpy.float64], dict(shape=3, order='C', device='cpu')]) – Query point.
radius (float) – Search radius.

Returns:

A tuple containing: - A list of element indices within the specified radius. - A NumPy array of shape (N, 3) containing the closest points on each element.

Return type:

tuple[list[int], Annotated[numpy.typing.NDArray[numpy.float64], dict(shape=(None, 3), order=’C’, device=’cpu’)]]

class lagrange.bvh.UVOverlapMethod¶

Bases: enum.Enum

Create a collection of name/value pairs.

Example enumeration:

>>> class Color(Enum):
...     RED = 1
...     BLUE = 2
...     GREEN = 3

Access them by:

attribute access:
```
>>> Color.RED
<Color.RED: 1>
```
value lookup:
```
>>> Color(1)
<Color.RED: 1>
```
name lookup:
```
>>> Color['RED']
<Color.RED: 1>
```

Enumerations can be iterated over, and know how many members they have:

>>> len(Color)
3

>>> list(Color)
[<Color.RED: 1>, <Color.BLUE: 2>, <Color.GREEN: 3>]

Methods can be added to enumerations, and members can have their own attributes – see the documentation for details.

BVH = 1¶: AABB tree per-triangle query.

Hybrid = 2¶: Zomorodian-Edelsbrunner HYBRID algorithm (recursive divide-and-conquer).

SweepAndPrune = 0¶: Zomorodian-Edelsbrunner sweep-and-prune.

lagrange.bvh.compute_chamfer(source, target)¶

Compute the Chamfer distance between two meshes.

The Chamfer distance is defined as: .. math:

\begin{aligned}
  C(A, B) = &\frac{1}{\|A\|} \sum_{a \in A} \text{dist}(a, B)^2 \\
            &+ \frac{1}{\|B\|} \sum_{b \in B} \text{dist}(b, A)^2
\end{aligned}

where dist(v, M) is the distance from vertex v to the closest point on mesh M.

Both meshes must have the same spatial dimension and must be triangle meshes.

Parameters:

source (lagrange.core.SurfaceMesh) – First mesh.
target (lagrange.core.SurfaceMesh) – Second mesh.

Returns:

Chamfer distance.

Return type:

float

lagrange.bvh.compute_hausdorff(source, target)¶

Compute the symmetric Hausdorff distance between two meshes.

The Hausdorff distance is the maximum of the two directed Hausdorff distances: .. math:

H(A, B) = \max \left(
  \max_{a \in A} \text{dist}(a, B), \quad
  \max_{b \in B} \text{dist}(b, A)
\right)

where dist(v, M) is the distance from vertex v to the closest point on mesh M.

Both meshes must have the same spatial dimension and must be triangle meshes.

Parameters:

source (lagrange.core.SurfaceMesh) – First mesh.
target (lagrange.core.SurfaceMesh) – Second mesh.

Returns:

Hausdorff distance.

Return type:

float

lagrange.bvh.compute_intersecting_pairs(mesh)¶

Compute all pairs of intersecting facets in a triangle mesh using BVH acceleration.

Detects facet pairs whose interiors intersect using exact geometric predicates. Only facets that do not share vertices are tested (vertex-adjacent facets are skipped).

Parameters:: mesh (lagrange.core.SurfaceMesh) – The input triangle mesh. Must contain only triangular facets.
Returns:: A list of tuples (i, j) where i < j representing non-vertex-adjacent facets whose interiors intersect.
Raises:: RuntimeError – If the mesh is not a triangle mesh or if the mesh is not 3D.
Return type:: list[tuple[int, int]]

Note

Vertex-adjacent facets are filtered before testing. The geometric test uses include_boundary=false (interior intersection only).

lagrange.bvh.compute_mesh_distances(source, target, output_attribute_name='@distance_to_mesh')¶

Compute the distance from each vertex in source to the closest point on target.

The result is stored as a per-vertex scalar attribute on source. Both meshes must have the same spatial dimension and target must be a triangle mesh.

Parameters:

source (lagrange.core.SurfaceMesh) – Mesh whose vertices are queried. The output attribute is added here.
target (lagrange.core.SurfaceMesh) – Triangle mesh against which distances are computed.
output_attribute_name (str) – Name of the output per-vertex attribute.

Returns:

AttributeId of the newly created (or overwritten) distance attribute on source.

Return type:

int

lagrange.bvh.compute_uv_overlap(mesh, uv_attribute_name='', compute_overlap_area=True, compute_overlap_coloring=False, overlap_coloring_attribute_name='@uv_overlap_color', compute_overlapping_pairs=False, method=UVOverlapMethod.Hybrid)¶

Compute pairwise UV triangle overlap.

For every pair of UV-space triangles whose 2-D bounding boxes intersect, an exact separating-axis test using orient2D predicates confirms a genuine interior intersection before computing the intersection area via Sutherland-Hodgman clipping.

Triangles that share only a boundary edge or a single vertex are never counted as overlapping.

Parameters:

mesh (lagrange.core.SurfaceMesh) – Input triangle mesh with a UV attribute.
uv_attribute_name (str) – UV attribute name. Empty string uses the first UV attribute found. Vertex, indexed and corner attributes are supported.
compute_overlap_area (bool) – If True, compute the total overlap area (default: True).
compute_overlap_coloring (bool) – If True, compute a per-facet coloring attribute (default: False).
overlap_coloring_attribute_name (str) – Name of the coloring attribute (default: “@uv_overlap_color”).
compute_overlapping_pairs (bool) – If True, return the list of overlapping pairs (default: False).
method (UVOverlapMethod) – Candidate detection algorithm (default: UVOverlapMethod.Hybrid).

Returns:

UVOverlapResult containing overlap detection results.

Return type:

UVOverlapResult

lagrange.bvh.remove_interior_shells(mesh)¶

Removes interior shells from a (manifold, non-intersecting) mesh

Warning

This method assumes that the input mesh is closed, manifold and has no self-intersections. The result may be invalid if these conditions are not met.

Parameters:: mesh (lagrange.core.SurfaceMesh) – Input mesh to process.
Returns:: A new mesh with interior shells removed.
Return type:: core.SurfaceMesh

lagrange.bvh.resolve_tjunctions(mesh, *, tolerance=-1.0, boundary_only=True, triangulate_affected=True)¶

Resolve T-junctions formed by collinear, overlapping edges.

A T-junction occurs when a vertex lies on an edge it is not topologically connected to. This splits every such edge at the vertices lying on it, and splits the adjacent facets accordingly, so the output mesh has no overlapping collinear edges. Vertices are not moved; only edges and facets are subdivided. Both triangle and polygonal meshes are supported.

Parameters:

mesh (lagrange.core.SurfaceMesh) – Input mesh, triangle or polygonal (modified in place).
tolerance (float) – Absolute distance tolerance for detecting vertices on an edge. If negative, defaults to 1e-6 times the bounding box diagonal.
boundary_only (bool) – If True, only boundary edges are checked for T-junctions. Set to False to also resolve T-junctions on interior edges.
triangulate_affected (bool) – If True (default), triangulate the facets affected by a split, so a triangle mesh stays triangular. If False, keep those facets as polygons.

Return type:

None

lagrange.bvh.weld_vertices(mesh, radius=9.999999974752427e-07, boundary_only=False)¶

Weld nearby vertices together of a surface mesh.

Parameters:

mesh (lagrange.core.SurfaceMesh) – The target surface mesh to be welded in place.
radius (float) – The maximum distance between vertices to be considered for welding. Default is 1e-6.
boundary_only (bool) – If true, only boundary vertices will be considered for welding. Defaults to False.

Return type:

None

Warning

This method may introduce non-manifoldness and degeneracy in the mesh.