Geogram  Version 1.9.1
A programming library of geometric algorithms
GEO::MeshFacetsAABB Class Reference

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

#include <geogram/mesh/mesh_AABB.h>

Inheritance diagram for GEO::MeshFacetsAABB:
GEO::MeshAABB3d GEO::AABB< BOX >

Classes

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

Public Member Functions

 MeshFacetsAABB ()
 MeshFacetsAABB constructor. More...
 
void initialize (Mesh &M, bool reorder=true)
 Initializes the Axis Aligned Bounding Boxes tree. More...
 
 MeshFacetsAABB (Mesh &M, bool reorder=true)
 Creates the Axis Aligned Bounding Boxes tree. More...
 
void compute_facet_bbox_intersections (std::function< void(index_t, index_t)> action) const
 Computes all the pairs of intersecting facets. More...
 
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. More...
 
index_t nearest_facet (const vec3 &p, vec3 &nearest_point, double &sq_dist) const
 Finds the nearest facet from an arbitrary 3d query point. More...
 
index_t nearest_facet (const vec3 &p) const
 Finds the nearest facet from an arbitrary 3d query point. More...
 
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. More...
 
double squared_distance (const vec3 &p) const
 Computes the distance between an arbitrary 3d query point and the surface. More...
 
bool ray_intersection (const Ray &R, double tmax=Numeric::max_float64(), index_t ignore_f=index_t(-1)) const
 Tests whether there exists an intersection between a ray and the mesh. More...
 
bool ray_nearest_intersection (const Ray &R, Intersection &I) const
 Computes the nearest intersection along a ray. More...
 
bool segment_intersection (const vec3 &q1, const vec3 &q2) const
 Tests whether this surface mesh has an intersection with a segment. More...
 
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. More...
 
void ray_all_intersections (const Ray &R, std::function< void(const Intersection &)> action) const
 Calls a user function for all ray-facet intersection. More...
 
- Public Member Functions inherited from GEO::MeshAABB3d
 MeshAABB3d ()
 MeshAABB3d constructor.
 
const Meshmesh () const
 Gets the mesh. More...
 

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. More...
 
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(). More...
 
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() More...
 
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() More...
 
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() More...
 
- Protected Member Functions inherited from GEO::AABB< BOX >
void initialize (index_t nb, std::function< void(BOX &, index_t)> get_bbox)
 Initializes this AABB. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 

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. More...
 
- Protected Attributes inherited from GEO::MeshAABB3d
Meshmesh_
 
- 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]Mthe 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]reorderif 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]actiona 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]actiona 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]pquery point
[out]nearest_faceta facet reasonably near p
[out]nearest_pointa point in nearest_facet
[out]sq_distsquared 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]Mthe 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]reorderif 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]pquery 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]pquery point
[out]nearest_pointnearest point on the surface
[out]sq_distsquared 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]pquery point
[in,out]nearest_facetthe nearest facet so far,
[in,out]nearest_pointa point in nearest_facet
[in,out]sq_distsquared distance between p and nearest_point
[in]nindex of the current node in the AABB tree
[in]bindex of the first facet in the subtree under node n
[in]eone 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]pquery point
[in,out]nearest_facetthe nearest facet so far, or NO_FACET if not known yet
[in,out]nearest_pointa point in nearest_facet
[in,out]sq_distsquared 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]Rthe ray
[in]actionthe 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]Rthe ray
[in]dirinvprecomputed 1/(q2.x-q1.x), 1/(q2.y-q1.y), 1/(q2.z-q1.z)
[in]actionthe function to be called
[in]nindex of the current node in the AABB tree
[in]bindex of the first facet in the subtree under node n
[in]eone 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 = index_t(-1) 
) const

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

Parameters
[in]Rthe ray.
[in]tmaxoptional maximum parameter of the intersection along the ray.
[in]ignore_foptional facet to be ignored in intersection tests.
Return values
trueif there was an intersection.
falseotherwise.

◆ 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]Rthe ray
[in]dirinvprecomputed 1/(q2.x-q1.x), 1/(q2.y-q1.y), 1/(q2.z-q1.z)
[in]max_tthe maximum value of t for an intersection
[in]ignore_ffacet index to be ignored in tests
[in]nindex of the current node in the AABB tree
[in]bindex of the first facet in the subtree under node n
[in]eone position past the index of the last facet in the subtree under node n
Return values
trueif their was an intersection
falseotherwise

◆ ray_nearest_intersection()

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

Computes the nearest intersection along a ray.

Parameters
[in]Rthe ray
[in,out]Ithe 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
trueif there was an intersection.
falseotherwise.

◆ 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]Rthe ray
[in]dirinvprecomputed 1/(q2.x-q1.x), 1/(q2.y-q1.y), 1/(q2.z-q1.z)
[in,out]Ithe parameters of the nearest intersection computed so-far. All intersections further away than I.t are ignored.
[in]ignore_ffacet index to be ignored in tests
[in]nindex of the current node in the AABB tree
[in]bindex of the first facet in the subtree under node n
[in]eone position past the index of the last facet in the subtree under node n
[in]coordthe 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,q2the two extremities of the segment.
Return values
trueif there exists an intersection between [q1 , q2] and a facet of the mesh.
falseotherwise.

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,q2the two extremities of the segment.
[out]tif there was an intersection, it is t*q2 + (1-t)*q1
[out]fthe intersected nearest facet or index_t(-1) if there was no intersection.
Return values
trueif there exists at least an intersection between [q1 , q2] and a facet of the mesh.
falseotherwise.

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]pquery 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: