I am struggling with implementing collision detection for 2 shapes. The project where it is needed is constructive solid geometry. The catch is that I need a "precise" detection between 2 shapes. One is always convex and second is concave after modifying it.

I already tried to use collision detection based on bsp tree generated from a mesh (bsp tree is just a representation of a mesh in that form). In this approach I just checked whether at least one point behind a planes. If yes, then they are colliding

With second approach I tried to use polygon vs bsp tree. In this approach I checked if polygon behind or straddling. If at least one is doing so, then 2 meshes are colliding

The issue is that one of the shapes is modifiable(mesh A) and on collision I modify this mesh substruct with other mesh (mesh B). And after I update mesh with modifying mesh A with mesh B, the collison detection doesn't work anymore.

So, I am wondering, if there is other way to implement collision between mesh A and mesh B or I just introduced unnecessary complexity in my collision detection test and introduced a bug? Is there any algorithms that work on polygon soup A and polygon soup B? Or maybe there could be algorithm to calculate hull of meshes so that I could use gjk algorithm or sat? Note that mesh A and mesh B only consists of polygons and I don't think there is possibility of using bounding boxes for this. Sorry for some really bad English here. Thanks

  • \$\begingroup\$ What was wrong with your first approach? What caused your second approach to not "work anymore"? It sounds to me like you might need some robust algorithms from computational geometry adapted to floating point. This page describes the problem space well, though I'm not sure if JavaScript is directly useful to you — you didn't specify your tech stack. \$\endgroup\$
    – DMGregory
    Apr 10 at 7:23
  • \$\begingroup\$ @DMGregory if I am not modifying the mesh A with mesh B, collision works fine. But the issue is that when I actually modify mesh A. It could be modified only once on first collision. After that collision code is not working with modified mesh \$\endgroup\$ Apr 10 at 8:00
  • \$\begingroup\$ @DMGregory And I’m thinking about calculating hull and then use gjk or using collision between 2 polygon soup. But I am unfamiliar with calculating hull(here, I guess, concave hull and triangulation needed) or polygon soup collision \$\endgroup\$ Apr 10 at 8:04
  • 1
    \$\begingroup\$ What specifically about the modification causes the collision check to fail? Remember that we can't see any code you haven't included in your question, so we can't troubleshoot this bug for you in the current state — you'll need to do the legwork of isolating a Minimal Complete Verifiable Example. \$\endgroup\$
    – DMGregory
    Apr 10 at 8:48


You must log in to answer this question.

Browse other questions tagged .