I want to efficiently find all triangles (e.g. facets of a polyhedral mesh) that are contained in or intersected by a volume (e.g. AABB or sphere query). I want to do this, if possible and reasonable, with CGALs built-in features.
My current solution is simple brute force: for all facets in mesh, check if distance of facet to ball center is smaller than the ball radius. I used a fuzzy sphere query of the KD-tree on the vertices before, but it was not accurate enough for my application. I need full sphere-triangle intersections.
The CGAL AABB tree (https://doc.cgal.org/latest/AABB_tree/index.html) seems like the best datastructure but I need the 3D linear Kernel which has no intersection test for triangles and any kind of volume (https://doc.cgal.org/latest/Kernel_23/group__intersection__linear__grp.html). The CGAL KD tree doesn't work because it can only contain points.
My ideas are:
Did I miss anything? Which solution would be the least effort?
Using some ideas from sloriot's answer, I was able to solve my problem.
Since the documentation of do_intersect() doesn't show an overload for Sphere_3 and Triangle_3, it's not surprising that the AABB tree doesn't support queries with Sphere_3.
However, the AABB tree supports queries with BBox_3, which is not mentioned in the do_intersect() docu.
Calling all_intersected_primitives() with the Bbox_3 returns all primitives of the AABB tree that are contained or intersection by the Bbox_3. This is a first good guess to get the actual intersections with the sphere.
With this optimization, I could reduce the query time from 20 ms (simple brute force) to 3 ms on a mesh with 100k faces where one query returns roughly 10 faces.
Here is the relevant code:
double r = CGAL::sqrt(patch_radius_squared);
CGAL::Bbox_3 query(
sphere_center.x() - r,
sphere_center.y() - r,
sphere_center.z() - r,
sphere_center.x() + r,
sphere_center.y() + r,
sphere_center.z() + r);
std::list<Tree::Primitive_id> primitives;
tree.all_intersected_primitives(query, std::back_inserter(primitives));
std::vector<Triangle_3> intersected_facets;
for (const Tree::Primitive_id& p : primitives)
{
// intersection with bb gives only a good first guess -> check actual intersection
if (CGAL::squared_distance(*p, sphere_center) <= patch_radius_squared)
{
intersected_facets.push_back(*p);
}
}