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 >

struct	ResolveTJunctionsOptions
	Option settings for resolve_tjunctions. More...

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	resolve_tjunctions (SurfaceMesh< Scalar, Index > &mesh, ResolveTJunctionsOptions options={})
	Resolve T-junctions formed by collinear, overlapping edges.

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.

◆ resolve_tjunctions()

template<typename Scalar, typename Index>

void resolve_tjunctions	(	SurfaceMesh< Scalar, Index > &	mesh,
		ResolveTJunctionsOptions	options = {} )

#include <lagrange/bvh/resolve_tjunctions.h>

Resolve T-junctions formed by collinear, overlapping edges.

A T-junction occurs when a vertex lies on an edge that it is not topologically connected to, causing the edge to overlap with the (unconnected) sub-edges incident to that vertex. This function splits every such edge at the vertices lying on it, and splits the adjacent facets accordingly, so the output mesh contains no overlapping collinear edges.

Vertices are not moved: only edges and facets are subdivided so the topology conforms to the existing vertex positions. The tolerance only controls detection, not geometric snapping.

Both triangle and polygonal meshes are supported. By default (triangulate_affected == true) the facets touched by a split are triangulated, so a triangle-mesh input yields a triangle-mesh output. Set triangulate_affected to false to instead keep those facets as polygons, with the split points inserted as additional (collinear) boundary vertices.

Parameters

[in,out]	mesh	Input mesh (triangle or polygonal). Modified in place.
[in]	options	Optional settings.

Template Parameters

Scalar	Mesh scalar type.
Index	Mesh index type.

Note: Consider running remove_duplicate_vertices and remove_degenerate_facets beforehand to avoid propagating pre-existing degeneracies.

◆ 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()

◆ resolve_tjunctions()

◆ weld_vertices()