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;
392 t(Numeric::max_float64()),
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);
561 double tmax = Numeric::max_float64(),
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.
Common include file, providing basic definitions. Should be included before anything else by all head...
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.
Vector with aligned memory allocation.
index_t size() const
Gets the number of elements.
Geometric functions in 2d and 3d.
The class that represents a mesh.
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.