Axis Aligned Bounding Box tree of mesh facets in 3D. More...

#include <geogram/mesh/mesh_AABB.h>

Inheritance diagram for GEO::MeshFacetsAABB:

Classes
struct	Intersection
	Stores all the information related with a ray-facet intersection. More...

Public Member Functions
	MeshFacetsAABB ()
	MeshFacetsAABB constructor.

void	initialize (Mesh &M, bool reorder=true)
	Initializes the Axis Aligned Bounding Boxes tree.

	MeshFacetsAABB (Mesh &M, bool reorder=true)
	Creates the Axis Aligned Bounding Boxes tree.

void	compute_facet_bbox_intersections (std::function< void(index_t, index_t)> action) const
	Computes all the pairs of intersecting facets.

void	compute_bbox_facet_bbox_intersections (const Box &box_in, std::function< void(index_t)> action) const
	Computes all the intersections between a given box and the bounding boxes of all the facets.

index_t	nearest_facet (const vec3 &p, vec3 &nearest_point, double &sq_dist) const
	Finds the nearest facet from an arbitrary 3d query point.

index_t	nearest_facet (const vec3 &p) const
	Finds the nearest facet from an arbitrary 3d query point.

void	nearest_facet_with_hint (const vec3 &p, index_t &nearest_facet, vec3 &nearest_point, double &sq_dist) const
	Computes the nearest point and nearest facet from a query point, using user-specified hint.

double	squared_distance (const vec3 &p) const
	Computes the distance between an arbitrary 3d query point and the surface.

bool	ray_intersection (const Ray &R, double tmax=Numeric::max_float64(), index_t ignore_f=NO_INDEX) const
	Tests whether there exists an intersection between a ray and the mesh.

bool	ray_nearest_intersection (const Ray &R, Intersection &I) const
	Computes the nearest intersection along a ray.

bool	segment_intersection (const vec3 &q1, const vec3 &q2) const
	Tests whether this surface mesh has an intersection with a segment.

bool	segment_nearest_intersection (const vec3 &q1, const vec3 &q2, double &t, index_t &f) const
	Finds the intersection between a segment and a surface that is nearest to the first extremity of the segment.

void	ray_all_intersections (const Ray &R, std::function< void(const Intersection &)> action) const
	Calls a user function for all ray-facet intersection.

Public Member Functions inherited from GEO::MeshAABB3d
	MeshAABB3d ()
	MeshAABB3d constructor.

const Mesh *	mesh () const
	Gets the mesh.

Protected Member Functions
void	get_nearest_facet_hint (const vec3 &p, index_t &nearest_facet, vec3 &nearest_point, double &sq_dist) const
	Computes a reasonable initialization for nearest facet search.

void	nearest_facet_recursive (const vec3 &p, index_t &nearest_facet, vec3 &nearest_point, double &sq_dist, index_t n, index_t b, index_t e) const
	The recursive function used by the implementation of nearest_facet().

bool	ray_intersection_recursive (const Ray &R, const vec3 &dirinv, double max_t, index_t ignore_f, index_t n, index_t b, index_t e) const
	The recursive function used by the implementation of ray_intersection()

void	ray_nearest_intersection_recursive (const Ray &R, const vec3 &dirinv, Intersection &I, index_t ignore_f, index_t n, index_t b, index_t e, index_t coord) const
	The recursive function used by the implementation of ray_nearest_intersection()

void	ray_all_intersections_recursive (const Ray &R, const vec3 &dirinv, std::function< void(const Intersection &)> action, index_t n, index_t b, index_t e) const
	The function used to implement ray_all_intersections()

Protected Member Functions inherited from GEO::AABB< BOX >
void	initialize (index_t nb, std::function< void(BOX &, index_t)> get_bbox)
	Initializes this AABB.

void	bbox_intersect_recursive (std::function< void(index_t)> action, const BOX &box, index_t node, index_t b, index_t e) const
	Computes all the elements that have a bbox that intersects a given bbox in a sub-tree of the AABB tree.

void	self_intersect_recursive (std::function< void(index_t, index_t)> action, index_t node1, index_t b1, index_t e1, index_t node2, index_t b2, index_t e2) const
	Computes all the pairs of intersecting elements for two sub-trees of the AABB tree.

void	other_intersect_recursive (std::function< void(index_t, index_t)> action, index_t node1, index_t b1, index_t e1, const AABB< BOX > *other, index_t node2, index_t b2, index_t e2) const
	Computes all the pairs of intersecting elements for two sub-trees of two AABB trees.

void	init_bboxes_recursive (index_t node_index, index_t b, index_t e, std::function< void(BOX &, index_t)> get_bbox)
	Computes the hierarchy of bounding boxes recursively.

Additional Inherited Members
Static Protected Member Functions inherited from GEO::AABB< BOX >
static index_t	max_node_index (index_t node_index, index_t b, index_t e)
	Computes the maximum node index in a subtree.

Protected Attributes inherited from GEO::MeshAABB3d
Mesh *	mesh_

Protected Attributes inherited from GEO::AABB< BOX >
index_t	nb_

vector< BOX >	bboxes_

Detailed Description

Axis Aligned Bounding Box tree of mesh facets in 3D.

Used to quickly compute facet intersection and to locate the nearest facet from 3d query points.

Definition at line 383 of file mesh_AABB.h.

Constructor & Destructor Documentation

◆ MeshFacetsAABB() [1/2]

GEO::MeshFacetsAABB::MeshFacetsAABB ( )

MeshFacetsAABB constructor.

Creates an uninitialized MeshFacetsAABB.

◆ MeshFacetsAABB() [2/2]

GEO::MeshFacetsAABB::MeshFacetsAABB	(	Mesh &	M,
		bool	reorder = `true`
	)

Creates the Axis Aligned Bounding Boxes tree.

Parameters

[in]	M	the input mesh. It can be modified, and will be triangulated (if not already a triangular mesh). The facets are re-ordered (using Morton's order, see mesh_reorder()).
[in]	reorder	if not set, Morton re-ordering is skipped (but it means that mesh_reorder() was previously called else the algorithm will be pretty unefficient).

Member Function Documentation

◆ compute_bbox_facet_bbox_intersections()

void GEO::MeshFacetsAABB::compute_bbox_facet_bbox_intersections	(	const Box &	box_in,
		std::function< void(index_t)>	action
	)		const

inline

Computes all the intersections between a given box and the bounding boxes of all the facets.

Parameters

[in] action a function that takes an index_t that is invoked for all facets that have a bounding box that intersects box_in.

Definition at line 461 of file mesh_AABB.h.

◆ compute_facet_bbox_intersections()

void GEO::MeshFacetsAABB::compute_facet_bbox_intersections ( std::function< void(index_t, index_t)> action ) const

inline

Computes all the pairs of intersecting facets.

Parameters

[in] action a function that takes two index_t's and that is invoked of all pairs of facets that have overlapping bounding boxes. triangles_intersections() needs to be called to detect the actual intersections.

Definition at line 444 of file mesh_AABB.h.

◆ get_nearest_facet_hint()

void GEO::MeshFacetsAABB::get_nearest_facet_hint	(	const vec3 &	p,
		index_t &	nearest_facet,
		vec3 &	nearest_point,
		double &	sq_dist
	)		const

protected

Computes a reasonable initialization for nearest facet search.

A good initialization makes the algorithm faster, by allowing early pruning of subtrees that provably do not contain the nearest neighbor.

Parameters

[in]	p	query point
[out]	nearest_facet	a facet reasonably near p
[out]	nearest_point	a point in nearest_facet
[out]	sq_dist	squared distance between p and nearest_point

◆ initialize()

void GEO::MeshFacetsAABB::initialize	(	Mesh &	M,
		bool	reorder = `true`
	)

Initializes the Axis Aligned Bounding Boxes tree.

Parameters

[in]	M	the input mesh. It can be modified, and will be triangulated (if not already a triangular mesh). The facets are re-ordered (using Morton's order, see mesh_reorder()).
[in]	reorder	if not set, Morton re-ordering is skipped (but it means that mesh_reorder() was previously called else the algorithm will be pretty unefficient).

◆ nearest_facet() [1/2]

index_t GEO::MeshFacetsAABB::nearest_facet ( const vec3 & p ) const

inline

Finds the nearest facet from an arbitrary 3d query point.

Parameters

[in] p query point

Returns: the index of the facet nearest to point p.

Definition at line 494 of file mesh_AABB.h.

◆ nearest_facet() [2/2]

index_t GEO::MeshFacetsAABB::nearest_facet	(	const vec3 &	p,
		vec3 &	nearest_point,
		double &	sq_dist
	)		const

inline

Finds the nearest facet from an arbitrary 3d query point.

Parameters

[in]	p	query point
[out]	nearest_point	nearest point on the surface
[out]	sq_dist	squared distance between p and the surface.

Returns: the index of the facet nearest to point p.

Definition at line 476 of file mesh_AABB.h.

◆ nearest_facet_recursive()

void GEO::MeshFacetsAABB::nearest_facet_recursive	(	const vec3 &	p,
		index_t &	nearest_facet,
		vec3 &	nearest_point,
		double &	sq_dist,
		index_t	n,
		index_t	b,
		index_t	e
	)		const

protected

The recursive function used by the implementation of nearest_facet().

The first call may use get_nearest_facet_hint() to initialize nearest_facet, nearest_point and sq_dist, as done in nearest_facet().

Parameters

[in]	p	query point
[in,out]	nearest_facet	the nearest facet so far,
[in,out]	nearest_point	a point in nearest_facet
[in,out]	sq_dist	squared distance between p and nearest_point
[in]	n	index of the current node in the AABB tree
[in]	b	index of the first facet in the subtree under node `n`
[in]	e	one position past the index of the last facet in the subtree under node `n`

◆ nearest_facet_with_hint()

void GEO::MeshFacetsAABB::nearest_facet_with_hint	(	const vec3 &	p,
		index_t &	nearest_facet,
		vec3 &	nearest_point,
		double &	sq_dist
	)		const

inline

Computes the nearest point and nearest facet from a query point, using user-specified hint.

The hint is specified as reasonable initial values of (nearest_facet, nearest_point, sq_dist). If multiple queries are done on a set of points that has spatial locality, the hint can be the result of the previous call.

Parameters

[in]	p	query point
[in,out]	nearest_facet	the nearest facet so far, or NO_FACET if not known yet
[in,out]	nearest_point	a point in nearest_facet
[in,out]	sq_dist	squared distance between p and nearest_point

Note: On entry, sq_dist needs to be equal to the squared distance between p and nearest_point (it is easy to forget to update it when calling it within a loop).

Definition at line 519 of file mesh_AABB.h.

◆ ray_all_intersections()

void GEO::MeshFacetsAABB::ray_all_intersections	(	const Ray &	R,
		std::function< void(const Intersection &)>	action
	)		const

Calls a user function for all ray-facet intersection.

Parameters

[in]	R	the ray
[in]	action	the function to be called

◆ ray_all_intersections_recursive()

void GEO::MeshFacetsAABB::ray_all_intersections_recursive	(	const Ray &	R,
		const vec3 &	dirinv,
		std::function< void(const Intersection &)>	action,
		index_t	n,
		index_t	b,
		index_t	e
	)		const

protected

The function used to implement ray_all_intersections()

Parameters

[in]	R	the ray
[in]	dirinv	precomputed 1/(q2.x-q1.x), 1/(q2.y-q1.y), 1/(q2.z-q1.z)
[in]	action	the function to be called
[in]	n	index of the current node in the AABB tree
[in]	b	index of the first facet in the subtree under node `n`
[in]	e	one position past the index of the last facet in the subtree under node `n`

◆ ray_intersection()

bool GEO::MeshFacetsAABB::ray_intersection	(	const Ray &	R,
		double	tmax = `Numeric::max_float64()`,
		index_t	ignore_f = `NO_INDEX`
	)		const

Tests whether there exists an intersection between a ray and the mesh.

Parameters

[in]	R	the ray.
[in]	tmax	optional maximum parameter of the intersection along the ray.
[in]	ignore_f	optional facet to be ignored in intersection tests.

Return values

true	if there was an intersection.
false	otherwise.

◆ ray_intersection_recursive()

bool GEO::MeshFacetsAABB::ray_intersection_recursive	(	const Ray &	R,
		const vec3 &	dirinv,
		double	max_t,
		index_t	ignore_f,
		index_t	n,
		index_t	b,
		index_t	e
	)		const

protected

The recursive function used by the implementation of ray_intersection()

Parameters

[in]	R	the ray
[in]	dirinv	precomputed 1/(q2.x-q1.x), 1/(q2.y-q1.y), 1/(q2.z-q1.z)
[in]	max_t	the maximum value of t for an intersection
[in]	ignore_f	facet index to be ignored in tests
[in]	n	index of the current node in the AABB tree
[in]	b	index of the first facet in the subtree under node `n`
[in]	e	one position past the index of the last facet in the subtree under node `n`

Return values

true	if their was an intersection
false	otherwise

◆ ray_nearest_intersection()

bool GEO::MeshFacetsAABB::ray_nearest_intersection	(	const Ray &	R,
		Intersection &	I
	)		const

Computes the nearest intersection along a ray.

Parameters

[in]	R	the ray
[in,out]	I	the intersection. If I.t is set, then intersections further away than I.t are ignored. If I.f is set, then intersection with facet f is ignored.

Return values

true	if there was an intersection.
false	otherwise.

◆ ray_nearest_intersection_recursive()

void GEO::MeshFacetsAABB::ray_nearest_intersection_recursive	(	const Ray &	R,
		const vec3 &	dirinv,
		Intersection &	I,
		index_t	ignore_f,
		index_t	n,
		index_t	b,
		index_t	e,
		index_t	coord
	)		const

protected

The recursive function used by the implementation of ray_nearest_intersection()

Parameters

[in]	R	the ray
[in]	dirinv	precomputed 1/(q2.x-q1.x), 1/(q2.y-q1.y), 1/(q2.z-q1.z)
[in,out]	I	the parameters of the nearest intersection computed so-far. All intersections further away than I.t are ignored.
[in]	ignore_f	facet index to be ignored in tests
[in]	n	index of the current node in the AABB tree
[in]	b	index of the first facet in the subtree under node `n`
[in]	e	one position past the index of the last facet in the subtree under node `n`
[in]	coord	the current splitting coordinate, one of 0,1,2

◆ segment_intersection()

bool GEO::MeshFacetsAABB::segment_intersection	(	const vec3 &	q1,
		const vec3 &	q2
	)		const

inline

Tests whether this surface mesh has an intersection with a segment.

Parameters

[in] q1,q2 the two extremities of the segment.

Return values

true	if there exists an intersection between [q1 , q2] and a facet of the mesh.
false	otherwise.

Definition at line 585 of file mesh_AABB.h.

◆ segment_nearest_intersection()

bool GEO::MeshFacetsAABB::segment_nearest_intersection	(	const vec3 &	q1,
		const vec3 &	q2,
		double &	t,
		index_t &	f
	)		const

inline

Finds the intersection between a segment and a surface that is nearest to the first extremity of the segment.

Parameters

[in]	q1,q2	the two extremities of the segment.
[out]	t	if there was an intersection, it is tq2 + (1-t)q1
[out]	f	the intersected nearest facet or NO_INDEX if there was no intersection.

Return values

true	if there exists at least an intersection between [q1 , q2] and a facet of the mesh.
false	otherwise.

Definition at line 600 of file mesh_AABB.h.

◆ squared_distance()

double GEO::MeshFacetsAABB::squared_distance ( const vec3 & p ) const

inline

Computes the distance between an arbitrary 3d query point and the surface.

Parameters

[in] p query point

Returns: the squared distance between p and the surface.

Definition at line 541 of file mesh_AABB.h.

The documentation for this class was generated from the following file:

geogram/mesh/mesh_AABB.h

Classes

Public Member Functions

Protected Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ MeshFacetsAABB() [1/2]

◆ MeshFacetsAABB() [2/2]

Member Function Documentation

◆ compute_bbox_facet_bbox_intersections()

◆ compute_facet_bbox_intersections()

◆ get_nearest_facet_hint()

◆ initialize()

◆ nearest_facet() [1/2]

◆ nearest_facet() [2/2]

◆ nearest_facet_recursive()

◆ nearest_facet_with_hint()

◆ ray_all_intersections()

◆ ray_all_intersections_recursive()

◆ ray_intersection()

◆ ray_intersection_recursive()

◆ ray_nearest_intersection()

◆ ray_nearest_intersection_recursive()

◆ segment_intersection()

◆ segment_nearest_intersection()

◆ squared_distance()