lagrange.bvh¶

Classes¶

`EdgeAABBTree2D`
`EdgeAABBTree3D`
`TriangleAABBTree2D`
`TriangleAABBTree3D`

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.
`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’)]]

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