40 #ifndef GEOGRAM_MESH_MESH_AABB
41 #define GEOGRAM_MESH_MESH_AABB
60 template <
class BOX>
class AABB {
99 std::function<
void(
index_t)> action,
const BOX& box,
167 if(b1 + 1 == e1 && b2 + 1 == e2) {
176 if(e2 - b2 > e1 - b1) {
177 index_t m2 = b2 + (e2 - b2) / 2;
179 index_t node2_r = 2 * node2 + 1;
183 index_t m1 = b1 + (e1 - b1) / 2;
185 index_t node1_r = 2 * node1 + 1;
229 if(b1 + 1 == e1 && b2 + 1 == e2) {
238 if(e2 - b2 > e1 - b1) {
239 index_t m2 = b2 + (e2 - b2) / 2;
241 index_t node2_r = 2 * node2 + 1;
243 action, node1, b1, e1, other, node2_l, b2, m2
246 action, node1, b1, e1, other, node2_r, m2, e2
249 index_t m1 = b1 + (e1 - b1) / 2;
251 index_t node1_r = 2 * node1 + 1;
253 action, node1_l, b1, m1, other, node2, b2, e2
256 action, node1_r, m1, e1, other, node2, b2, e2
275 index_t childl = 2 * node_index;
276 index_t childr = 2 * node_index + 1;
305 index_t childl = 2 * node_index;
306 index_t childr = 2 * node_index + 1;
313 bbox_union(bboxes_[node_index], bboxes_[childl], bboxes_[childr]);
321 typedef AABB<Box2d> AABB2d;
322 typedef AABB<Box3d> AABB3d;
447 self_intersect_recursive(
449 1, 0, mesh_->facets.nb(),
450 1, 0, mesh_->facets.nb()
462 const Box& box_in, std::function<
void(
index_t)> action
464 bbox_intersect_recursive(
465 action, box_in, 1, 0, mesh_->facets.nb()
477 const vec3& p,
vec3& nearest_point,
double& sq_dist
480 get_nearest_facet_hint(p, nearest_facet, nearest_point, sq_dist);
481 nearest_facet_recursive(
483 nearest_facet, nearest_point, sq_dist,
484 1, 0, mesh_->facets.nb()
486 return nearest_facet;
497 return nearest_facet(p, nearest_point, sq_dist);
521 index_t& nearest_facet,
vec3& nearest_point,
double& sq_dist
523 if(nearest_facet == NO_FACET) {
524 get_nearest_facet_hint(
525 p, nearest_facet, nearest_point, sq_dist
528 nearest_facet_recursive(
530 nearest_facet, nearest_point, sq_dist,
531 1, 0, mesh_->facets.nb()
544 nearest_facet(p, nearest_point, result);
586 return ray_intersection(
Ray(q1, q2-q1), 1.0);
606 bool result = ray_nearest_intersection(R,I);
639 index_t& nearest_facet,
vec3& nearest_point,
double& sq_dist
661 index_t& nearest_facet,
vec3& nearest_point,
double& sq_dist,
719 const Ray& R,
const vec3& dirinv,
779 return containing_tet_recursive(
780 p, 1, 0, mesh_->cells.nb()
793 std::function<
void(
index_t)> action
795 bbox_intersect_recursive(
796 action, box_in, 1, 0, mesh_->cells.nb()
810 containing_bboxes_recursive(
811 action, p, 1, 0, mesh_->cells.nb()
825 self_intersect_recursive(
827 1, 0, mesh_->cells.nb(),
828 1, 0, mesh_->cells.nb()
845 other_intersect_recursive(
847 1, 0, mesh_->cells.nb(),
849 1, 0, other->mesh_->cells.
nb()
892 std::function<
void(
index_t)> action,
899 if(!bboxes_[node].contains(p)) {
914 containing_bboxes_recursive(action, p, node_l, b, m);
915 containing_bboxes_recursive(action, p, node_r, m, e);
972 return containing_triangle_recursive(
973 p, 1, 0, mesh_->facets.nb()
986 std::function<
void(
index_t)> action
988 bbox_intersect_recursive(
989 action, box_in, 1, 0, mesh_->facets.nb()
1001 const vec2& p, std::function<
void(
index_t)> action
1003 containing_bboxes_recursive(
1004 action, p, 1, 0, mesh_->facets.nb()
1018 self_intersect_recursive(
1020 1, 0, mesh_->facets.nb(),
1021 1, 0, mesh_->facets.nb()
1038 other_intersect_recursive(
1040 1, 0, mesh_->facets.nb(),
1042 1, 0, other->mesh_->facets.
nb()
1085 std::function<
void(
index_t)> action,
1092 if(!bboxes_[node].contains(p)) {
1105 index_t node_r = 2 * node + 1;
1107 containing_bboxes_recursive(action, p, node_l, b, m);
1108 containing_bboxes_recursive(action, p, node_r, m, e);
#define geo_debug_assert(x)
Verifies that a condition is met.
Base class for Axis Aligned Bounding Box trees.
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 tre...
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.
static index_t max_node_index(index_t node_index, index_t b, index_t e)
Computes the maximum node index in a subtree.
void initialize(index_t nb, std::function< void(BOX &, index_t)> get_bbox)
Initializes this AABB.
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.
Axis-aligned bounding box.
Axis-aligned bounding box.
Base class for Axis Aligned Bounding Box trees of mesh elements with 2d boxes.
const Mesh * mesh() const
Gets the mesh.
MeshAABB2d()
MeshAABB2d constructor.
Base class for Axis Aligned Bounding Box trees of mesh elements with 3d boxes.
const Mesh * mesh() const
Gets the mesh.
MeshAABB3d()
MeshAABB3d constructor.
Axis Aligned Bounding Box tree of mesh cells.
void compute_cell_bbox_intersections(std::function< void(index_t, index_t)> action) const
Computes all the pairs of intersecting cells.
void containing_boxes(const vec3 &p, std::function< void(index_t)> action) const
Finds all the cells such that their bounding box contain a point.
MeshCellsAABB(Mesh &M, bool reorder=true)
Creates the Axis Aligned Bounding Boxes tree.
MeshCellsAABB()
MeshCellsAABB constructor.
index_t containing_tet_recursive(const vec3 &p, index_t n, index_t b, index_t e) const
The recursive function used by the implementation of containing_tet().
void initialize(Mesh &M, bool reorder=true)
Initializes the Axis Aligned Bounding Boxes tree.
index_t containing_tet(const vec3 &p) const
Finds the index of a tetrahedron that contains a query point.
void compute_bbox_cell_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 cells.
void containing_bboxes_recursive(std::function< void(index_t)> action, const vec3 &p, index_t node, index_t b, index_t e) const
Computes all the cells that have a bbox that contain a given point in a sub-tree of the AABB tree.
void compute_other_cell_bbox_intersections(MeshCellsAABB *other, std::function< void(index_t, index_t)> action) const
Computes all the pairs of intersecting cells between this AABB and another one.
Axis Aligned Bounding Box tree of mesh facets in 2D.
void compute_facet_bbox_intersections(std::function< void(index_t, index_t)> action) const
Computes all the pairs of intersecting facets.
void compute_other_cell_bbox_intersections(MeshFacetsAABB2d *other, std::function< void(index_t, index_t)> action) const
Computes all the pairs of intersecting cells between this AABB and another one.
index_t containing_triangle_recursive(const vec2 &p, index_t n, index_t b, index_t e) const
The recursive function used by the implementation of containing_triangle().
MeshFacetsAABB2d()
MeshFacetsAABB2d constructor.
void compute_bbox_cell_bbox_intersections(const Box2d &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.
void containing_boxes(const vec2 &p, std::function< void(index_t)> action) const
Finds all the cells such that their bounding box contain a point.
MeshFacetsAABB2d(Mesh &M, bool reorder=true)
Creates the Axis Aligned Bounding Boxes tree.
void containing_bboxes_recursive(std::function< void(index_t)> action, const vec2 &p, index_t node, index_t b, index_t e) const
Computes all the cells that have a bbox that contain a given point in a sub-tree of the AABB tree.
void initialize(Mesh &M, bool reorder=true)
Initializes the Axis Aligned Bounding Boxes tree.
index_t containing_triangle(const vec2 &p) const
Finds the index of a facet that contains a query point.
Axis Aligned Bounding Box tree of mesh facets in 3D.
MeshFacetsAABB(Mesh &M, bool reorder=true)
Creates the Axis Aligned Bounding Boxes tree.
bool segment_intersection(const vec3 &q1, const vec3 &q2) const
Tests whether this surface mesh has an intersection with a segment.
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 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.
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()
double squared_distance(const vec3 &p) const
Computes the distance between an arbitrary 3d query point and the surface.
bool ray_nearest_intersection(const Ray &R, Intersection &I) const
Computes the nearest intersection along a ray.
MeshFacetsAABB()
MeshFacetsAABB constructor.
index_t nearest_facet(const vec3 &p, vec3 &nearest_point, double &sq_dist) const
Finds the nearest facet from an arbitrary 3d query point.
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.
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 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 ray_all_intersections(const Ray &R, std::function< void(const Intersection &)> action) const
Calls a user function for all ray-facet intersection.
void compute_facet_bbox_intersections(std::function< void(index_t, index_t)> action) const
Computes all the pairs of intersecting facets.
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(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.
index_t nearest_facet(const vec3 &p) const
Finds the nearest facet from an arbitrary 3d query point.
void initialize(Mesh &M, bool reorder=true)
Initializes the Axis Aligned Bounding Boxes tree.
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 ...
index_t nb() const
Gets the number of (sub-)elements.
index_t size() const
Gets the number of elements.
Common include file, providing basic definitions. Should be included before anything else by all head...
Geometric functions in 2d and 3d.
The class that represents a mesh.
float64 max_float64()
Gets 64 bits float maximum positive value.
Global Vorpaline namespace.
bool bboxes_overlap(const Box &B1, const Box &B2)
Tests whether two Boxes have a non-empty intersection.
void get_bbox(const Mesh &M, double *xyzmin, double *xyzmax)
Gets the bounding box of a mesh.
void bbox_union(Box &target, const Box &B1, const Box &B2)
Computes the smallest Box that encloses two Boxes.
geo_index_t index_t
The type for storing and manipulating indices.
Stores all the information related with a ray-facet intersection.
A Ray, in parametric form.