2

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.

Community
  • 1
  • 1
dim_tz
  • 1,451
  • 5
  • 20
  • 37

2 Answers2

3
  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.
Community
  • 1
  • 1
lrineau
  • 6,036
  • 3
  • 34
  • 47
  • Thank you Irineau! The 1st question/answer should be in the way you mention, otherwise things can get really slow, but the creation of the trees under the hood is not mentioned in the documentation explicitly, so thank you for throwing some light there! – dim_tz Apr 07 '14 at 15:01
  • Regarding the 2nd question/answer, what you say is for sure the only thing that I could imagine, but I wonder if it is optimal, in this sense: The tree structure is needed in order to avoid checking objects that are far away and don't have any chance of colliding at the present time frame, so throwing the triangles of all objects in one vector would probably result in some speeding up (trees are still used) but maybe not in the optimal way (top tree-nodes include triangles of specific objects/object_groups). Do you have any idea about this? Thanks again! – dim_tz Apr 07 '14 at 15:01
  • Actually, the bbox intersection package already has one function that can deal with two vectors of bboxes. The link I used in my answer points to that version. The suggestion I made was for the case where you have more than two set of bboxes. – lrineau Apr 07 '14 at 15:13
  • True, having two sets of bboxes is a bit limited (?) for real applications, where usually one has n-number of bboxes. So I agree that your suggestion is probably more generic. – dim_tz Apr 07 '14 at 15:19
1

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))
);
David G.
  • 371
  • 4
  • 11