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;
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);
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.
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.