Geogram
Version 1.9.1
A programming library of geometric algorithms
|
Axis Aligned Bounding Box tree of mesh facets in 3D. More...
#include <geogram/mesh/mesh_AABB.h>
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 Mesh * | mesh () 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 | |
Mesh * | mesh_ |
Protected Attributes inherited from GEO::AABB< BOX > | |
index_t | nb_ |
vector< BOX > | bboxes_ |
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.
GEO::MeshFacetsAABB::MeshFacetsAABB | ( | ) |
MeshFacetsAABB constructor.
Creates an uninitialized MeshFacetsAABB.
GEO::MeshFacetsAABB::MeshFacetsAABB | ( | Mesh & | M, |
bool | reorder = true |
||
) |
Creates the Axis Aligned Bounding Boxes tree.
[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). |
|
inline |
Computes all the intersections between a given box and the bounding boxes of all the facets.
[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.
|
inline |
Computes all the pairs of intersecting facets.
[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.
|
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.
[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 |
void GEO::MeshFacetsAABB::initialize | ( | Mesh & | M, |
bool | reorder = true |
||
) |
Initializes the Axis Aligned Bounding Boxes tree.
[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). |
Finds the nearest facet from an arbitrary 3d query point.
[in] | p | query point |
Definition at line 494 of file mesh_AABB.h.
|
inline |
Finds the nearest facet from an arbitrary 3d query point.
[in] | p | query point |
[out] | nearest_point | nearest point on the surface |
[out] | sq_dist | squared distance between p and the surface. |
Definition at line 476 of file mesh_AABB.h.
|
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().
[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 |
|
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.
[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 |
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.
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.
[in] | R | the ray |
[in] | action | the function to be called |
|
protected |
The function used to implement ray_all_intersections()
[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 |
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.
[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. |
true | if there was an intersection. |
false | otherwise. |
|
protected |
The recursive function used by the implementation of ray_intersection()
[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 |
true | if their was an intersection |
false | otherwise |
bool GEO::MeshFacetsAABB::ray_nearest_intersection | ( | const Ray & | R, |
Intersection & | I | ||
) | const |
Computes the nearest intersection along a ray.
[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. |
true | if there was an intersection. |
false | otherwise. |
|
protected |
The recursive function used by the implementation of ray_nearest_intersection()
[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 |
Tests whether this surface mesh has an intersection with a segment.
[in] | q1,q2 | the two extremities of the segment. |
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.
|
inline |
Finds the intersection between a segment and a surface that is nearest to the first extremity of the segment.
[in] | q1,q2 | the two extremities of the segment. |
[out] | t | if there was an intersection, it is t*q2 + (1-t)*q1 |
[out] | f | the intersected nearest facet or index_t(-1) if there was no intersection. |
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.
|
inline |
Computes the distance between an arbitrary 3d query point and the surface.
[in] | p | query point |
p
and the surface. Definition at line 541 of file mesh_AABB.h.