Geogram Version 1.9.6
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. | |
MeshFacetsAABB (Mesh &M, AABBReorderMode reorder_mode) | |
Creates an Axis Aligned Bounding Boxes tree for facets. | |
MeshFacetsAABB (const Mesh &M) | |
Creates an Axis Aligned Bounding Boxes tree for facets. | |
void | initialize (Mesh &M, AABBReorderMode reorder_mode=AABB_INDIRECT) |
Initializes the Axis Aligned Bounding Boxes tree. | |
MeshFacetsAABB (Mesh &M, bool reorder) | |
void | initialize (Mesh &M, bool reorder) |
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. | |
index_t | nearest_facet_filtered (const vec3 &p, vec3 &nearest_point, double &sq_dist, std::function< bool(index_t)> filter) const |
Finds the nearest facet from an arbitrary 3d query point taken into account only certain facets. | |
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. | |
![]() | |
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(). | |
void | nearest_facet_recursive_filtered (const vec3 &p, index_t &nearest_facet, vec3 &nearest_point, double &sq_dist, index_t n, index_t b, index_t e, std::function< bool(index_t)> filter) const |
The recursive function used by the implementation of nearest_facet_filtered(). | |
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() | |
![]() | |
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. | |
bool | indirect () const |
Tests whether this AABB is indirect or in-place. | |
index_t | element_in_leaf (index_t i) const |
Gets the element stored in a leaf node. | |
Additional Inherited Members | |
![]() | |
static index_t | max_node_index (index_t node_index, index_t b, index_t e) |
Computes the maximum node index in a subtree. | |
![]() | |
Mesh * | mesh_ |
![]() | |
index_t | nb_ |
vector< BOX > | bboxes_ |
vector< index_t > | reorder_ |
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 417 of file mesh_AABB.h.
|
inline |
MeshFacetsAABB constructor.
Creates an uninitialized MeshFacetsAABB.
Definition at line 444 of file mesh_AABB.h.
|
inline |
Creates an Axis Aligned Bounding Boxes tree for facets.
[in] | M | the input mesh. It can be modified, and will be triangulated (if not already a triangular mesh). The facets are re-ordered depending on reorder_mode |
[in] | reorder_mode | one of
|
Definition at line 460 of file mesh_AABB.h.
|
inline |
Creates an Axis Aligned Bounding Boxes tree for facets.
Uses AABB_INDIRECT mode (order stored in separate vector).
[in] | M | a const reference to the input mesh. |
Definition at line 469 of file mesh_AABB.h.
|
inline |
Definition at line 490 of file mesh_AABB.h.
|
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 523 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 506 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, |
AABBReorderMode | reorder_mode = AABB_INDIRECT |
||
) |
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 depending on reorder_mode |
[in] | reorder_mode | one of
|
|
inline |
Definition at line 495 of file mesh_AABB.h.
Finds the nearest facet from an arbitrary 3d query point.
[in] | p | query point |
Definition at line 556 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 538 of file mesh_AABB.h.
|
inline |
Finds the nearest facet from an arbitrary 3d query point taken into account only certain facets.
[in] | p | query point |
[out] | nearest_point | nearest point on the surface |
[out] | sq_dist | squared distance between p and the surface. |
[in] | filter | a function that takes a facet index and that returns true if the facet should be taken into account or false otherwise. |
Definition at line 574 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 |
|
protected |
The recursive function used by the implementation of nearest_facet_filtered().
[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 |
[in] | filter | a function that takes a facet index and that returns true if the facet should be taken into account or false otherwise. |
|
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 608 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 = NO_INDEX |
||
) | 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 674 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 NO_INDEX 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 689 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 630 of file mesh_AABB.h.