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

Typedefs
using	Scalar = typename VertexArray::Scalar

using	Index = typename EdgeArray::Scalar

using	AlignedBoxType = typename AABB<Scalar, Dim>::Box

using	RowVectorType = Eigen::Matrix<Scalar, 1, Dim>

using	ActionCallback = function_ref<void(Scalar, Index, const RowVectorType&)>
	closest_sq_dist x element_id x closest_point

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

	EdgeAABBTree (const VertexArray &V, const EdgeArray &E)
	Construct an AABB over the given edge graph.

bool	empty () const
	Test whether the tree is empty.

void	get_element_closest_point (const RowVectorType &p, Index element_id, RowVectorType &closest_point, Scalar &closest_sq_dist) const
	Gets the closest point to a given element.

void	foreach_element_in_radius (const RowVectorType &p, Scalar sq_dist, ActionCallback func) const
	Iterate over edges within a prescribed distance from a query point.

void	foreach_element_containing (const RowVectorType &p, ActionCallback func) const
	Iterate over edges that contain exactly a given query point.

void	get_closest_point (const RowVectorType &p, Index &element_id, RowVectorType &closest_point, Scalar &closest_sq_dist, function_ref< bool(Index)> filter_func=[](Index) { return true;}) const
	Gets the closest point to an element of the tree.

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_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 a triangle mesh.

Parameters

[in,out]	source	Mesh whose vertices are queried. The output attribute is added here.
[in]	target	Triangle mesh 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 mesh \( M \).

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

Parameters

[in]	source	First mesh.
[in]	target	Second mesh.

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 mesh \( M \).

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

Parameters

[in]	source	First mesh.
[in]	target	Second mesh.

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.

◆ EdgeAABBTree()

template<typename VertexArray, typename EdgeArray, int Dim>

EdgeAABBTree	(	const VertexArray &	V,
		const EdgeArray &	E )

#include <lagrange/bvh/EdgeAABBTree.h>

Construct an AABB over the given edge graph.

Parameters

[in]	V	V x Dim input vertex positions.
[in]	E	E x 2 input edge vertices.

◆ empty()

template<typename VertexArray, typename EdgeArray, int Dim = 3>

bool empty ( ) const

inline

#include <lagrange/bvh/EdgeAABBTree.h>

Test whether the tree is empty.

Returns: True iff empty, False otherwise.

◆ get_element_closest_point()

template<typename VertexArray, typename EdgeArray, int Dim>

void get_element_closest_point	(	const RowVectorType &	p,
		Index	element_id,
		RowVectorType &	closest_point,
		Scalar &	closest_sq_dist ) const

#include <lagrange/bvh/EdgeAABBTree.h>

Gets the closest point to a given element.

Parameters

[in]	p	Query point.
[in]	element_id	Element id.
[out]	closest_point	Closest point on the element.
[out]	closest_sq_dist	Squared distance between closest point and query point.

◆ foreach_element_in_radius()

template<typename VertexArray, typename EdgeArray, int Dim = 3>

void foreach_element_in_radius	(	const RowVectorType &	p,
		Scalar	sq_dist,
		ActionCallback	func ) const

#include <lagrange/bvh/EdgeAABBTree.h>

Iterate over edges within a prescribed distance from a query point.

Parameters

[in]	p	1 x Dim query point.
[in]	sq_dist	Squared query radius.
[in]	func	Function to apply to every edge within query distance.

◆ foreach_element_containing()

template<typename VertexArray, typename EdgeArray, int Dim = 3>

void foreach_element_containing	(	const RowVectorType &	p,
		ActionCallback	func ) const

#include <lagrange/bvh/EdgeAABBTree.h>

Iterate over edges that contain exactly a given query point.

This function uses exact predicates to determine whether the query point belong to an edge segment. Note that this is slightly different from calling foreach_element_in_radius with a search radius of 0, since foreach_element_in_radius does not use exact predicates, it might return false positives (i.e. points which are at distance 0, but not exactly collinear).

Parameters

[in]	p	1 x Dim query point.
[in]	func	Function to apply to every edge within query distance.

◆ get_closest_point()

template<typename VertexArray, typename EdgeArray, int Dim>

void get_closest_point	(	const RowVectorType &	p,
		Index &	element_id,
		RowVectorType &	closest_point,
		Scalar &	closest_sq_dist,
		function_ref< bool(Index)>	filter_func = [](Index) { return true; } ) const

#include <lagrange/bvh/EdgeAABBTree.h>

Gets the closest point to an element of the tree.

Whereas get_element_closest_point returns the closest point to a queried element, this function recursively traverses the tree nodes to find the element which is closest to the query point.

Parameters

[in]	p	Query point.
[out]	element_id	Closest element id.
[out]	closest_point	Closest point on the element.
[out]	closest_sq_dist	Squared distance between closest point and query point.
[in]	filter_func	Optional function to filter out elements from the test. Only elements for which filter_func(element_id) == true will be considered for closest point.

◆ 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

Typedefs

Enumerations

Functions

Detailed Description

Enumeration Type Documentation

◆ UVOverlapMethod

Function Documentation

◆ compute_mesh_distances()

◆ compute_hausdorff()

◆ compute_chamfer()

◆ compute_uv_overlap()

◆ EdgeAABBTree()

◆ empty()

◆ get_element_closest_point()

◆ foreach_element_in_radius()

◆ foreach_element_containing()

◆ get_closest_point()

◆ weld_vertices()