Bounding Volume Hierarchy (BVH) construction and traversal. More...

Classes
class	AABB< Scalar, Dim >
	Axis-Aligned Bounding Box (AABB) tree for efficient spatial queries. More...

struct	MeshDistancesOptions
	Options for compute_mesh_distances. More...

struct	UVOverlapOptions
	Options for compute_uv_overlap. More...

struct	UVOverlapResult< Scalar, Index >
	Result of compute_uv_overlap. More...

struct	EdgeAABBTree< VertexArray, EdgeArray, Dim >

class	TriangleAABBTree< Scalar, Index, Dim >
	AABB tree for a triangle mesh. More...

struct	WeldOptions

Enumerations
enum class	UVOverlapMethod { SweepAndPrune , BVH , Hybrid }
	Algorithm used to find candidate bounding-box pairs in compute_uv_overlap. More...

Functions
template<typename Scalar, typename Index>
AdjacencyList< Index >	compute_intersecting_pairs (const SurfaceMesh< Scalar, Index > &mesh)
	Compute all pairs of intersecting facets in a mesh using an AABB tree for acceleration.

template<typename Scalar, typename Index>
LA_BVH_API AttributeId	compute_mesh_distances (SurfaceMesh< Scalar, Index > &source, const SurfaceMesh< Scalar, Index > &target, const MeshDistancesOptions &options={})
	Compute the distance from each vertex in `source` to the closest point on `target`, and store the result as a per-vertex scalar attribute on `source`.

template<typename Scalar, typename Index>
LA_BVH_API Scalar	compute_hausdorff (const SurfaceMesh< Scalar, Index > &source, const SurfaceMesh< Scalar, Index > &target)
	Compute the symmetric Hausdorff distance between `source` and `target`.

template<typename Scalar, typename Index>
LA_BVH_API Scalar	compute_chamfer (const SurfaceMesh< Scalar, Index > &source, const SurfaceMesh< Scalar, Index > &target)
	Compute the Chamfer distance between `source` and `target`.

template<typename Scalar, typename Index>
LA_BVH_API UVOverlapResult< Scalar, Index >	compute_uv_overlap (SurfaceMesh< Scalar, Index > &mesh, const UVOverlapOptions &options={})
	Compute pairwise UV triangle overlap.

template<typename Scalar, typename Index>
void	weld_vertices (SurfaceMesh< Scalar, Index > &mesh, WeldOptions options={})
	Weld nearby vertices together of a surface mesh.

Detailed Description

Bounding Volume Hierarchy (BVH) construction and traversal.

Enumeration Type Documentation

◆ UVOverlapMethod

enum class UVOverlapMethod

strong

#include <lagrange/bvh/compute_uv_overlap.h>

Algorithm used to find candidate bounding-box pairs in compute_uv_overlap.

Enumerator

SweepAndPrune

Zomorodian-Edelsbrunner sweep-and-prune.

Sorts triangle bounding-box x-intervals and sweeps a 1-D active set to enumerate all overlapping pairs in O((n + k) log n) time, where k is the output size.

BVH

AABB tree per-triangle query.

Builds an AABB<Scalar,2> tree on all triangle bounding boxes, then queries each box against the tree in parallel. Useful for benchmarking and cross-validation against the sweep-and-prune path.

Hybrid

Zomorodian-Edelsbrunner HYBRID algorithm (recursive divide-and-conquer).

Based on the HYBRID procedure from Figure 5 of "Fast Software for Box Intersections" (Zomorodian & Edelsbrunner, 2002), simplified for the 2-D complete case. Recursively splits on the y-dimension median, handles spanning intervals at each node with a one-dimensional OneWayScan, and falls through to scanning for subsets below a cutoff size. See the implementation file for a detailed description of the differences from the paper's algorithm.

Function Documentation

◆ compute_intersecting_pairs()

template<typename Scalar, typename Index>

AdjacencyList< Index > compute_intersecting_pairs ( const SurfaceMesh< Scalar, Index > & mesh )

#include <lagrange/bvh/compute_intersecting_pairs.h>

Compute all pairs of intersecting facets in a mesh using an AABB tree for acceleration.

Detects facet pairs whose interiors overlap using exact geometric predicates. All facet pairs (including vertex- and edge-adjacent ones) are tested geometrically. Contacts at shared vertices or edges do not count as intersections; only interior overlaps are reported.

Parameters

[in] mesh The input mesh. Must be a triangle mesh (only triangular facets).

Template Parameters

Scalar	Mesh scalar type.
Index	Mesh index type.

Returns: An AdjacencyList representing the intersection graph. For each facet i, get_neighbors(i) returns all facets whose interior overlaps the interior of i.

Exceptions

std::runtime_error if the mesh is not a triangle mesh or not 3D.

Note: Uses exact predicates (orient3D, orient2D) with include_boundary=false. Boundary contacts (shared vertices or edges) are correctly excluded.

See also: triangle_triangle_intersection

◆ compute_mesh_distances()

template<typename Scalar, typename Index>

LA_BVH_API AttributeId compute_mesh_distances	(	SurfaceMesh< Scalar, Index > &	source,
		const SurfaceMesh< Scalar, Index > &	target,
		const MeshDistancesOptions &	options = {} )

#include <lagrange/bvh/compute_mesh_distances.h>

Compute the distance from each vertex in source to the closest point on target, and store the result as a per-vertex scalar attribute on source.

Both meshes must have the same spatial dimension. target must be either a triangle mesh or a point cloud (no facets). If target is a point cloud, distances are computed to the nearest vertex rather than to the nearest point on a triangle.

Parameters

[in,out]	source	Mesh whose vertices are queried. The output attribute is added here.
[in]	target	Triangle mesh or point cloud against which distances are computed.
[in]	options	Options controlling the name of the output attribute.

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

Template Parameters

Scalar	Mesh scalar type.
Index	Mesh index type.

◆ compute_hausdorff()

template<typename Scalar, typename Index>

LA_BVH_API Scalar compute_hausdorff	(	const SurfaceMesh< Scalar, Index > &	source,
		const SurfaceMesh< Scalar, Index > &	target )

#include <lagrange/bvh/compute_mesh_distances.h>

Compute the symmetric Hausdorff distance between source and target.

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

\[ H(A, B) = \max\!\left( \max_{a \in A} \mathrm{dist}(a, B),\; \max_{b \in B} \mathrm{dist}(b, A) \right) \]

where \( \mathrm{dist}(v, M) \) is the distance from vertex \( v \) to the closest point on \( M \). For triangle meshes the closest point may lie on a triangle face or edge; for point clouds (no facets) it is the nearest vertex.

Both meshes must have the same spatial dimension. Each mesh must be either a triangle mesh or a point cloud (no facets).

Parameters

[in]	source	First mesh or point cloud.
[in]	target	Second mesh or point cloud.

Returns: Hausdorff distance.

Template Parameters

Scalar	Mesh scalar type.
Index	Mesh index type.

◆ compute_chamfer()

template<typename Scalar, typename Index>

LA_BVH_API Scalar compute_chamfer	(	const SurfaceMesh< Scalar, Index > &	source,
		const SurfaceMesh< Scalar, Index > &	target )

#include <lagrange/bvh/compute_mesh_distances.h>

Compute the Chamfer distance between source and target.

The Chamfer distance is defined as:

\[ C(A, B) = \frac{1}{|A|} \sum_{a \in A} \mathrm{dist}(a, B)^2 + \frac{1}{|B|} \sum_{b \in B} \mathrm{dist}(b, A)^2 \]

where \( \mathrm{dist}(v, M) \) is the distance from vertex \( v \) to the closest point on \( M \). For triangle meshes the closest point may lie on a triangle face or edge; for point clouds (no facets) it is the nearest vertex.

Both meshes must have the same spatial dimension. Each mesh must be either a triangle mesh or a point cloud (no facets).

Parameters

[in]	source	First mesh or point cloud.
[in]	target	Second mesh or point cloud.

Returns: Chamfer distance.

Template Parameters

Scalar	Mesh scalar type.
Index	Mesh index type.

◆ compute_uv_overlap()

template<typename Scalar, typename Index>

LA_BVH_API UVOverlapResult< Scalar, Index > compute_uv_overlap	(	SurfaceMesh< Scalar, Index > &	mesh,
		const UVOverlapOptions &	options = {} )

#include <lagrange/bvh/compute_uv_overlap.h>

Compute pairwise UV triangle overlap.

For every pair of UV-space triangles whose 2-D axis-aligned bounding boxes intersect (detected via the Zomorodian-Edelsbrunner sweep-and-prune or a BVH), an exact separating-axis test using orient2D predicates is applied to confirm a genuine interior intersection before computing the intersection area using Sutherland-Hodgman polygon clipping.

Triangles that share only a boundary edge or a single vertex are never counted as overlapping — the exact orient2D predicate handles boundary contacts correctly.

Parameters

[in,out]	mesh	Input triangle mesh with a UV attribute.
[in]	options	Options controlling algorithm and output.

Returns: UVOverlapResult containing the optional total overlap area and the optional AttributeId of the per-facet coloring attribute.

Template Parameters

Scalar	Mesh scalar type.
Index	Mesh index type.

◆ weld_vertices()

template<typename Scalar, typename Index>

void weld_vertices	(	SurfaceMesh< Scalar, Index > &	mesh,
		WeldOptions	options = {} )

#include <lagrange/bvh/weld_vertices.h>

Weld nearby vertices together of a surface mesh.

Parameters

[in,out]	mesh	The target surface mesh to be welded in place.
[in]	options	Options for welding.

Warning: This method may lead to non-manifoldness and degeneracy in the output mesh.

Classes

Enumerations

Functions

Detailed Description

Enumeration Type Documentation

◆ UVOverlapMethod

Function Documentation

◆ compute_intersecting_pairs()

◆ compute_mesh_distances()

◆ compute_hausdorff()

◆ compute_chamfer()

◆ compute_uv_overlap()

◆ weld_vertices()