CGAL Mesh(es) intersection/collision

问题:

I would like to have a collision detection module in my tracking pipeline, detecting when two different meshes collide/interpenetrate or if there is a self-penetration of an articulated mesh. Based on the depth of the penetration there should be a penalization that combats this phenomenon. I should get a list of the colliding faces/vertices in order to do so.

After examining several options, I decided to start working with CGAL.

In this link there is an interesting answer pointing to some examples. (this and this). The examples use AABBs (Axis-Aligned Bounding Boxes), which is the proposed way for non-rigid meshes, since a frequent update of them is needed. The examples are clear for the self-intersection case, but the following are not very clear to me:

• Apart from creating a B.Box for each triangles, I guess that there is no tree structure created under the hood to speed up the search process. Is it so? If yes, any hint to do so?
• In case of 2 separate meshes, I guess it's not nice to merge all triangles/boxes in one vector and follow the examples (though it is mentioned here as a solution, it doesn't sound so elegant). Any hint for a nice practice? Should one mix these examples, by creating trees of triangles/boxes? Although for the AABB tree it is mentioned that:

Note that this component is not suited to the problem of finding all intersecting pairs of objects. We refer to the component Intersecting Sequences of dD Iso-oriented Boxes which can find all intersecting pairs of iso-oriented boxes.

回答1:

1. The function CGAL::box_intersection_d creates segment trees on the fly, to speed the computation of pairs of intersecting AA-bounding boxes.
2. As far as I know, the recommended way is to merge the two surfaces in one vector of custom boxes, where the boxes have a field to indicate the identifier of the surface the triangle belongs to. That helps to quickly discard pairs of boxes from same surface.

回答2:

My response is really a comment on lrineau's informative answer, but it's a little long so I'm posting it as my own answer. CGAL's Polygon Mesh Processing package has a function called CGAL::Polygon_mesh_processing::do_intersect() that accepts two triangular meshes as input and returns a Boolean that describes whether the meshes intersect or not. Unfortunately, it doesn't tell you the pairs of intersecting faces.

However, do_intersect() internally calls an undocumented function CGAL::Polygon_mesh_processing::internal::compute_face_face_intersection() (which in turn calls CGAL::box_intersection_d()) that returns the pairs of intersecting faces into a vector. Here's some example code that shows how it can be called:

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;
typedef boost::graph_traits<Mesh>::face_descriptor face_descriptor;
typedef std::pair<face_descriptor, face_descriptor> face_descriptor_pair;
namespace PMP = CGAL::Polygon_mesh_processing;

Mesh mesh_a, mesh_b;
std::vector<face_descriptor_pair> tri_pairs;
PMP::internal::compute_face_face_intersection(
    mesh_a,
    mesh_b,
    std::back_inserter(tri_pairs),
    PMP::parameters::vertex_point_map(get(CGAL::vertex_point, mesh_a)),
    PMP::parameters::vertex_point_map(get(CGAL::vertex_point, mesh_b))
);