BVH Module

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

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

Function Documentation

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.