• Create Account

### #Actualmaxgpgpu

Posted 04 March 2012 - 10:13 AM

I am almost ready to start adding physics to my 3D simulation/game engine, but have one last (but very annoying) job to perform in collision detection. That is, finding "first contact" time and positions. This is the time when the colliding objects first touched, and the locations (points, edges, faces) on the two colliding objects that were touching at first contact.

The existing, highly optimized collision detection process has up to 3 phases:
#1: broad-phase - rejects all object pairs whose AABBs do not overlap.
#2: narrow-phase convex - rejects all object pairs whose convex hulls do not intersect.
#3: narrow-phase concave/arbitrary - finds exact intersections of arbitrary shapes with concave features.

#2 performs the usual GJK algorithm, and has all the intermediate values GJK has computed when it finds intersection.

#3 is not performed unless one or both objects have concave features (or it isn't known whether they do). If #3 is performed, it finds every intersection between any triangle vertex or edge and any triangle vertex, edge or face on the other object. #3 is amazingly efficient given what a difficult problem exact intersection between arbitrarily irregular objects is, but is several times slower than GJK. Therefore I need to find first contact in stage #2 before possibly moving on to iterating #3. Note that the majority of the outside surface of most arbitrarily irregular objects is still locally convex, and thus the answer from #2 is usually correct even for arbitrarily irregular "concave" objects.

I rather doubt there is a general algorithm to compute first contact time and position for arbitrarily irregular "concave" objects as supported by #3. So let's forget that for the moment and assume we compute first contact when the GJK technique of #2 finds two convex objects overlap (whether one or both have concave features or not).

We've optimized the hell out of our GJK routine, and it is fast as blazes. So I'm not terribly concerned if a computed "first contact time" is not exact --- we'll just take the result, move the objects back to the computed "first contact" time, and perform the GJK routine again... iteratively... until the distances become "close enough". I assume this will be necessary anyway, since one or both of the objects may be moving and/or rotating, which I assume means no fast, efficient and precise algorithm exists.

Once this last bit gets done, it's on to collision response AKA physics. Believe it or not, I can't wait!

### #2maxgpgpu

Posted 03 March 2012 - 11:09 AM

I am almost ready to start adding physics to my 3D simulation/game engine, but have one last (but very annoying) job to perform in collision detection. That is, finding "first contact" time and positions. This is the time when the colliding objects first touched, and the locations (points, edges, faces) on the two colliding objects that were touching at first contact.

The existing, highly optimized collision detection process has up to 3 phases:
#1: broad-phase - rejects all object pairs whose AABBs do not overlap.
#2: narrow-phase convex - rejects all object pairs whose convex hulls do not intersect.
#3: narrow-phase concave/arbitrary - finds exact intersections of arbitrary shapes with concave features.

#2 performs the usual GJK algorithm, and has all the intermediate values GJK has computed when it finds intersection.

#3 is not performed unless one or both objects have concave features (or it isn't known whether they do). If #3 is performed, it finds every intersection between any triangle vertex or edge and any triangle vertex, edge or face on the other object. #3 is amazingly efficient given what a difficult problem exact intersection between arbitrarily irregular objects is, but it is still several times slower than GJK. Therefore I need to find first contact in stage #2 before possibly moving on to iterating #3. Note that the majority of the outside surface of most arbitrarily irregular objects is still locally convex, and thus the answer from #2 is usually correct even for arbitrarily irregular "concave" objects.

I rather doubt there is a general algorithm to compute first contact time and position for arbitrarily irregular "concave" objects as supported by #3. So let's forget that for the moment and assume we compute first contact when the GJK technique of #2 finds two convex objects overlap (whether one or both have concave features or not).

We've optimized the hell out of our GJK routine, and it is fast as blazes. So I'm not terribly concerned if a computed "first contact time" is not exact --- we'll just take the result, move the objects back to the computed "first contact" time, and perform the GJK routine again... iteratively... until the distances become "close enough". I assume this will be necessary anyway, since one or both of the objects may be moving and/or rotating, which I assume means no fast, efficient and precise algorithm exists.

Once this last bit gets done, it's on to collision response AKA physics. Believe it or not, I can't wait!

### #1maxgpgpu

Posted 03 March 2012 - 11:05 AM

I am almost ready to start adding physics to my 3D simulation/game engine, but have one last (but very annoying) job to perform in collision detection. That is, finding "first contact" time and positions. This is the time when the colliding objects first touched, and the locations (points, edges, faces) on the two colliding objects that were touching at first contact.

The existing, highly optimized collision detection process has up to 3 phases:
#1: broad-phase - rejects all object pairs whose AABBs do not overlap.
#2: narrow-phase convex - rejects all object pairs whose convex hulls do not intersect.
#3: narrow-phase concave/arbitrary - finds exact intersections of arbitrary shapes with concave features.

#2 performs the usual GJK algorithm, and has all the intermediate values GJK has computed when it finds intersection.

#3 is not performed unless one or both objects have concave features (or it isn't known whether they do). If #3 is performed, it finds every intersection between any triangle vertex or edge and any triangle vertex, edge or face on the other object.

I rather doubt there is a general algorithm to compute first contact time and position for arbitrarily irregular "concave" objects as supported by #3. So let's forget that for the moment and assume we compute first contact when the GJK technique of #2 finds two convex objects overlap (whether one or both have concave features or not).

We've optimized the hell out of our GJK routine, and it is fast as blazes. So I'm not terribly concerned if a computed "first contact time" is not exact --- we'll just take the result, move the objects back to the computed "first contact" time, and perform the GJK routine again... iteratively... until the distances become "close enough". I assume this will be necessary anyway, since one or both of the objects may be moving and/or rotating, which I assume means no fast, efficient and precise algorithm exists.

Once this last bit gets done, it's on to collision response AKA physics. Believe it or not, I can't wait!

PARTNERS