[Algorithms] incremental triangulation for 2D collision detection broadphase

[Samuel M. <sam...@go...>]

Hello all,

I need a broadphase collision detection algorithm for 2D rigid body
physics (continuous collision detection, but that shouldn't matter for
the broadphase...).

I have objects of wildly varying sizes, lots of free space and
possibly lots of clustering or even a single object very far away from
all the others, so a Quadtree (without some strange modifications,
wrapping the world came to mind) is not the best option.

What I came up with is to take all the objects positions and
triangulate this point set. Then for each triangle I determine which
objects it overlaps and test all these objects for collision.

This has a number of advantages, and I believe it could be competitive
to sweep and prune or Quadtrees (at least in 2D, in 3D its probably
not cool, but who knows?). I couldn't find anything about this method,
but if somebody already invented it I'd appreciate some pointers.

What I need now is an (efficient :D) algorithm for updating the
triangulation when the points move. i.e. given a valid triangulation
(no triangles overlap, triangulates the convex hull of all points) and
movement vectors for all points, how can I "repair" the old
triangulation?

The first part of the problem is how to maintain fat triangles
(slivers lead to poor collision rejection). I'm sure there are already
good algorithms to incrementally maintain a good triangulation, but I
couldn't find them. Also, the union of all triangles must stay convex.

The second problem is how to detect and remove triangle overlaps that
arise due to fast-moving objects. I have no idea how to do this
robustly (theoretically, the points could teleport arbitrarily)

I guess somebody already has solved this problem, but I could find no
relevant paper...

Of course I'll release the finished implementation as open source, or
try to incorporate it into Box2D if they want it and if it proves
faster than their existing spatial hashing ;)


Sincerely,
Samuel Moll