1
\$\begingroup\$

I am implementing 2D collision detection, and trying to tackle the problem of concave polygon vs. shape.

The SAT works only for convex shapes.

I was wondering if the following approach is a viable strategy for concave polygons:

  1. Compute the convex hull of the polygon (using the gift wrapping algorithm, for example).

  2. The original concave polygon can be represented as the hull, "minus" (set intersection) the carved-out parts - which are also convex.

Then, I apply the SAT for every pair of convex polygons within colliding shapes; a collision between a hole and a "substance" region will nullify any previous collision result.

I hope this approach will be faster to compute than computing SAT between every pair of triangles (assuming the polygons were triangulated).

What do you think?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ How will you distinguish between cases where the collision touches only the "hole" portion of the hull (and should be discarded) versus ones where it touches both the hole and non-hole portions (and is then a true collision)? These two cases give you the same yes/no results for each convex pair involved, so you'd need another ingredient to distinguish them. \$\endgroup\$
    – DMGregory ♦
    Commented Apr 7 at 12:07

2 Answers 2

Reset to default
1
\$\begingroup\$

Your triangulated mesh already represents a convex hull with a cavity, there's no need to perform additional collision checks only to invalidate previous tests. This potentially means additional computation and possible false positives, as @DMGregory pointed out in the comments.

The approach you describe is called the broad phase of collision testing, where the physics engine identifies the potential colliding pairs to investigate further during the subsequent narrow phase.

During the broad phase, the physics engine uses fast collision tests to determine which bodies might intersect. They rely on using simple primitives (such as AABBs or spheres) that fully enclose the original mesh and testing for overlaps in a yes-or-no fashion: if the big, chunky wrapper doesn't collide with anything, then the smaller, higher-detail collision proxy won't either. No need for convex hulls at this time.

Then, during the narrow phase, the engine tests all previous potential pairs and performs the actual collision detection. Now, every game object is tested using its actual collider(s) and, depending on the pair's proxy shapes, the most appropriate collision detection algorithm is used, for example Cube vs. Cube, Sphere vs. Wall, or even AABB vs. Ray. Complex objects may now require the SAT for convex hulls or sub-meshes.

Further readings: Dirk Gregorius's talk Robust Contact Creation for Physics Simulations at GDC 2015 (here's a PDF version of the presentation) gives a solid overview of a physics step collision detection-wise, and may help you figure out an approach that works best for your needs.

\$\endgroup\$
2
  • \$\begingroup\$ Note that OP is trying to use convex-only collision detection without checking per-triangle of a mesh in the narrow phase. They're also working in 2D, not 3D. \$\endgroup\$
    – DMGregory ♦
    Commented Apr 8 at 16:07
  • \$\begingroup\$ I think you misunderstood the question. I am doing a multithreaded broad phase using spacial partitioning and bounding circles, which are invariant to rotation. My concern is with regards to the narrow phase - and concave vs concave shape in particular. I can create the collision manifold by running the SAT between every pair of triangles from the original polygon, but I wonder if there's a more economical fashion to break up the polygon. \$\endgroup\$
    – Eilan Laken
    Commented Apr 9 at 21:50
0
\$\begingroup\$

Follow up:

I am allowing polygons with holes, which themselves may be concave - this complicate the problem. Therefore, I think it would be a good idea to simply check pair-by-pair of triangles.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Have you considered instead using convex decomposition? Here you don't use polygons for the holes, instead you cut the concave "solid" polygons into convex pieces, which may be larger than a single triangle each if the geometry allows. This can drastically reduce the number of potential colliding pairs you need to check. \$\endgroup\$
    – DMGregory ♦
    Commented Apr 10 at 11:03
  • \$\begingroup\$ Given that you have triangulated the polygon, you can preprocess the triangles to get fewer convex polygons and reduce the number of detections. The commonly used algorithm is hertel-mehlhorn algorithm. \$\endgroup\$
    – Mangata
    Commented Apr 12 at 11:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .