CODEWITHSUNDEEP
3dcollision-detectioncgal
dim_tz
dim_tz

Reputation: 1531

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:

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.

Upvotes: 2

Views: 2841

Answers (2)

David G.
David G.

Reputation: 371

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

Upvotes: 1

lrineau
lrineau

Reputation: 6274

  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.

Upvotes: 3

Related Questions