40#ifndef GEOGRAM_MESH_MESH_AABB
41#define GEOGRAM_MESH_MESH_AABB
60 template <
class BOX>
class AABB {
97 std::function<
void(
index_t)> action,
const BOX& box,
165 if(b1 + 1 == e1 && b2 + 1 == e2) {
174 if(e2 - b2 > e1 - b1) {
175 index_t m2 = b2 + (e2 - b2) / 2;
177 index_t node2_r = 2 * node2 + 1;
181 index_t m1 = b1 + (e1 - b1) / 2;
183 index_t node1_r = 2 * node1 + 1;
227 if(b1 + 1 == e1 && b2 + 1 == e2) {
236 if(e2 - b2 > e1 - b1) {
237 index_t m2 = b2 + (e2 - b2) / 2;
239 index_t node2_r = 2 * node2 + 1;
241 action, node1, b1, e1, other, node2_l, b2, m2
244 action, node1, b1, e1, other, node2_r, m2, e2
247 index_t m1 = b1 + (e1 - b1) / 2;
249 index_t node1_r = 2 * node1 + 1;
251 action, node1_l, b1, m1, other, node2, b2, e2
254 action, node1_r, m1, e1, other, node2, b2, e2
273 index_t childl = 2 * node_index;
274 index_t childr = 2 * node_index + 1;
303 index_t childl = 2 * node_index;
304 index_t childr = 2 * node_index + 1;
311 bbox_union(bboxes_[node_index], bboxes_[childl], bboxes_[childr]);
319 typedef AABB<Box2d> AABB2d;
320 typedef AABB<Box3d> AABB3d;
390 t(Numeric::max_float64()),
445 self_intersect_recursive(
447 1, 0, mesh_->facets.nb(),
448 1, 0, mesh_->facets.nb()
460 const Box& box_in, std::function<
void(
index_t)> action
462 bbox_intersect_recursive(
463 action, box_in, 1, 0, mesh_->facets.nb()
475 const vec3& p,
vec3& nearest_point,
double& sq_dist
478 get_nearest_facet_hint(p, nearest_facet, nearest_point, sq_dist);
479 nearest_facet_recursive(
481 nearest_facet, nearest_point, sq_dist,
482 1, 0, mesh_->facets.nb()
484 return nearest_facet;
495 return nearest_facet(p, nearest_point, sq_dist);
519 index_t& nearest_facet,
vec3& nearest_point,
double& sq_dist
521 if(nearest_facet == NO_FACET) {
522 get_nearest_facet_hint(
523 p, nearest_facet, nearest_point, sq_dist
526 nearest_facet_recursive(
528 nearest_facet, nearest_point, sq_dist,
529 1, 0, mesh_->facets.nb()
542 nearest_facet(p, nearest_point, result);
559 double tmax = Numeric::max_float64(),
584 return ray_intersection(
Ray(q1, q2-q1), 1.0);
604 bool result = ray_nearest_intersection(R,I);
637 index_t& nearest_facet,
vec3& nearest_point,
double& sq_dist
659 index_t& nearest_facet,
vec3& nearest_point,
double& sq_dist,
717 const Ray& R,
const vec3& dirinv,
777 return containing_tet_recursive(
778 p, 1, 0, mesh_->cells.nb()
791 std::function<
void(
index_t)> action
793 bbox_intersect_recursive(
794 action, box_in, 1, 0, mesh_->cells.nb()
808 containing_bboxes_recursive(
809 action, p, 1, 0, mesh_->cells.nb()
823 self_intersect_recursive(
825 1, 0, mesh_->cells.nb(),
826 1, 0, mesh_->cells.nb()
843 other_intersect_recursive(
845 1, 0, mesh_->cells.nb(),
847 1, 0, other->mesh_->cells.
nb()
890 std::function<
void(
index_t)> action,
897 if(!bboxes_[node].contains(p)) {
912 containing_bboxes_recursive(action, p, node_l, b, m);
913 containing_bboxes_recursive(action, p, node_r, m, e);
970 return containing_triangle_recursive(
971 p, 1, 0, mesh_->facets.nb()
984 std::function<
void(
index_t)> action
986 bbox_intersect_recursive(
987 action, box_in, 1, 0, mesh_->facets.nb()
1001 containing_bboxes_recursive(
1002 action, p, 1, 0, mesh_->facets.nb()
1016 self_intersect_recursive(
1018 1, 0, mesh_->facets.nb(),
1019 1, 0, mesh_->facets.nb()
1036 other_intersect_recursive(
1038 1, 0, mesh_->facets.nb(),
1040 1, 0, other->mesh_->facets.
nb()
1083 std::function<
void(
index_t)> action,
1090 if(!bboxes_[node].contains(p)) {
1103 index_t node_r = 2 * node + 1;
1105 containing_bboxes_recursive(action, p, node_l, b, m);
1106 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.