Re: [Algorithms] incremental triangulation for 2D collision detection broadphase

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

@Ben: Thanks for the link, but I wanted to avoid doing full Delauney
triangulation since everything remotely Delauney-like suffices for
me... but I can probably use some of the methods in this paper.
@ Erwin: Thought I read somewhere that Box2D uses a hash... but the
source code looks alot like a AABB tree ;)


But I think I found something better, because I realized that I don't
really need a triangulation, only some partition for example using
polygons...

Okay, here's the outline to my approach:
Every objects center is a "node", around the node is this objects
bounding volume (I think I'll use circles).
Then you build a graph that partitions the plane into (convex and
concave) polygons (You could make the graph so that only triangles are
used). On every corner of a polygon is an object, no object is on the
inside of a polygon.

Now you test for every object which polygon its bounding volume
intersects. Obviously it intersects at least all polygons adjacent to
its node; if the bounding volumes are relatively tight, it should not
intersect more than these.
I think the average number of bounding volume tests for each object
should be around 6.

Now all nodes move, and if the graph changes its topology, it needs to
be repaired. This is the part where I have no concrete algorithm
yet... but I guess I'll find one. I'm relatively sure that this step
should be fast ;)

Then the graph is optimized: a few edges are swapped, inserted etc. to
avoid slivers and such. This should be easy.

Greets,
Samuel



On Wed, Feb 3, 2010 at 6:39 AM, Erwin Coumans <erw...@gm...> wrote:
>
> Hi Samuel,
>
> Box2d uses a dynamic AABB tree for the broadphase, based on the original
> implementation from our Bullet library in 3d.
>
> This tree is incrementally updated, faster than sweep and prune.
>
> No spatial hash.
>
> I'm interested in your approach. How do you 'triangulate' the centers, and
> compute connectivity?
>
> Thanks,
> Erwin
>
> Feel free to forward this to the list, I cannot mail to the list because of
> mail server issues.
>
> Sent from my iPhone
>
> On Feb 2, 2010, at 16:54, Samuel Moll <sam...@go...> wrote:
>
>> 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
>>
>>
>> ------------------------------------------------------------------------------
>> The Planet: dedicated and managed hosting, cloud storage, colocation
>> Stay online with enterprise data centers and the best network in the
>> business
>> Choose flexible plans and management services without long-term contracts
>> Personal 24x7 support from experience hosting pros just a phone call away.
>> http://p.sf.net/sfu/theplanet-com
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>