lagrange.bvh¶

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_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
`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(*args, **kwds)¶

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_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:

object

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.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.