gdalgorithms-list

[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

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

[Ben Sunshine-H. <sn...@gm...>]

On Tue, Feb 2, 2010 at 7:54 PM, Samuel Moll <sam...@go...> wrote:
> 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?

Take a look at "Voronoi Diagrams of Moving Points", link below.
Remember that the Voronoi tessellation is the dual of the Delaunay
triangulation, which in general tends not to produce many slivers.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.8944

Ben

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
>

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

[<Pau...@sc...>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

Hi Samuel,

At first glance this approach seems pretty complex and expensive for a 
broad phase? I can't see how you can do this without triangulation and 
thats not a cheap operation. Even then, you have to intersect polygons 
against AABBs which is actually quite a costly operation - not that far 
away from a full narrow phase.

I would recommend sweep and prune, or multi-sweep and prune if your worlds 
are huge. We used sweep and prune in little big planet psp and it worked 
quite well.

Just my 2p :)

Cheers, Paul.

Samuel Moll <sam...@go...> wrote on 03/02/2010 14:38:46:

> @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
> >
> 
> 
- ------------------------------------------------------------------------------
> 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

**********************************************************************
This email and any files transmitted with it are confidential and intended 
solely for the use of the individual or entity to whom they are addressed. 
If you have received this email in error please notify pos...@sc...
This footnote also confirms that this email message has been checked for 
all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United 
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: US-ASCII

wsBVAwUBS2xEHXajGqjtoMHxAQi/iQf+LA826T+HJfDyYpXe89DM3tx1H9bBBbME
ND94GJj6Gbd93YNNgfXfYQV1kkyKKE+jyRG0IrQmrd3UaKIb2176hHkRfeDtmuJQ
LH9W45L9ePp9kLYqadveQv0CKME8Vy9Bg9MlmTtDYp56eLUa7A0uUHVFmRaJmExK
AgmZLio9fiuR14bUqHXXik50Wk7kwXcOt0sWQqSO0HPmXyLFGgCRiNF1TSzxjPZA
hK7dbKzoS772s6UyT6QHqeD3B5XE6J4cJCY0utNNxMeNCcVUaP0CcS+5//IlfGZn
ZcFZOvLJGoY2Mt9h1JDFWY3blmWLla+7mrGWWAag7aqCdtg2U02pYQ==
=pGyB
-----END PGP SIGNATURE-----

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

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

> At first glance this approach seems pretty complex and expensive for a
> broad phase? I can't see how you can do this without triangulation and
> thats not a cheap operation.

The triangulation is maintained incrementally -- normally it doesn't
change, so it only needs to be checked if it is still valid every
frame. If it changes, it only needs to be recalculated partially. This
is an O(n+something for the changed part) operation.

> Even then, you have to intersect polygons
> against AABBs which is actually quite a costly operation - not that far
> away from a full narrow phase.

Using circles makes it a bit cheaper (that's one of the reasons why I
want to use circles as bounding volumes), it's something like 6
line-circle intersection tests per object on average. But yes, the
cost per object is quite high compared to other methods.

> I would recommend sweep and prune, or multi-sweep and prune if your worlds
> are huge. We used sweep and prune in little big planet psp and it worked
> quite well.

I guess by multi-sweep you mean doing the sweeping on more than one
axis? How do you combine the results of the sweeps, for example for
100x100 objects arranged in a grid?

My motivation for trying this is that all broad phase algorithms I
know of are far away from a O(n) running time and have other
limitations. The triangulation method doesn't have any limitations on
object sizes or distribution and should have an expected O(n) running
time (and memory requirement) if neighborhood relations between
objects don't change too much in one frame.

Maybe the cost per object is too high to be competitive with other
methods like SnP. But for a very high number of objects it will
definitely be better. In any case it is worth trying out...


Greets,
Samuel

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

[<Pau...@sc...>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

> The triangulation is maintained incrementally -- normally it doesn't
> change, so it only needs to be checked if it is still valid every
> frame. If it changes, it only needs to be recalculated partially. This
> is an O(n+something for the changed part) operation.

I thought triangulation was a O(n^2) problem at least? (looks it up on 
wikipedia) ahh, i see there is talk of triangulating a simple polygon in 
O(n), but i'm not sure a connected graph of all objects constitutes a 
simple polygon?

> Using circles makes it a bit cheaper (that's one of the reasons why I
> want to use circles as bounding volumes), it's something like 6

The trouble with circles is that they don't fit the kind of triangles that 
a convex decomposition algorithm spits out very well, since they can be 
long and thin. We used AABBs in the end.

> I guess by multi-sweep you mean doing the sweeping on more than one
> axis? How do you combine the results of the sweeps, for example for
> 100x100 objects arranged in a grid?

Multi-sweep is where you divide your (huge) world up into a small number 
of chunks (rectangles in 2d) and then do regular sweep and prune in each 
chunk. This gets around the clustering problem where far away objects can 
cause a lot of clustered entries on one axis. We just used regular SAP for 
the record :)

> My motivation for trying this is that all broad phase algorithms I
> know of are far away from a O(n) running time and have other

The most important thing to keep in mind is that a good broad-phase 
algorithm should do zero work when nothing moves in the world.

> Maybe the cost per object is too high to be competitive with other
> methods like SnP. But for a very high number of objects it will
> definitely be better. In any case it is worth trying out...

Are all your objects always moving in your world? How many objects are you 
talking about?

Cheers, Paul.
**********************************************************************
This email and any files transmitted with it are confidential and intended 
solely for the use of the individual or entity to whom they are addressed. 
If you have received this email in error please notify pos...@sc...
This footnote also confirms that this email message has been checked for 
all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United 
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: US-ASCII

wsBVAwUBS2/eAHajGqjtoMHxAQjybQf/UrQsqYNvEQN82/slrWd8LwdOQchc2X4v
GlwZ8lfHhMH7JB0uFnRPmgyd/pvIlj/q8JFi0SL+m0wrQNemw9Y0DvVhj3FNyk6M
ezSqU5MvjVc6H6+Bp3ZGXDOWyCpgYW5FBENI8OKHkirv2YgC3Lk4iYAxIx/HPQPo
6zIbXpL1eBIM53BrcYR1WHHU57NwqHxHOZjjM6KYIt+M/vzX/fi0UFiKN4lhFkNf
fOKhgdWgUsmCIFDUV/j3z+CnsCMfFSqgevSd2sDy78O5dx7rZrs+nBaSvsN31+AN
IoyQVqD/RAdoXGNfGR1GxQcoGIDOU92fjijoBYOGgA/DQUzkC4lomw==
=pibX
-----END PGP SIGNATURE-----

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

[Simon F. <sim...@po...>]

Pau...@sc... wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
> 
>> The triangulation is maintained incrementally -- normally it doesn't
>> change, so it only needs to be checked if it is still valid every
>> frame. If it changes, it only needs to be recalculated partially.
>> This is an O(n+something for the changed part) operation.
> 
> I thought triangulation was a O(n^2) problem at least? (looks it up on
> wikipedia) ahh, i see there is talk of triangulating a simple polygon
> in O(n), but i'm not sure a connected graph of all objects
> constitutes a simple polygon?  

Drifting a bit OT, but from what I've read, the O(n) triangulation
algorithm of simple polygons is said to be very complicated. Although
wikipedia does have a link to a claimed simple, linear time,
triangulation algorithm, until I someone posts a copy of the paper that
is in English, I'll take it with a grain of salt. :)

FWIW, there are O(n log* n) algorithms (the star is important) which are
fairly simple to implement and are pretty much indistinguishable from
O(n). 

Again, apologies for going a little OT.

Simon

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

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

> I thought triangulation was a O(n^2) problem at least? (looks it up on
> wikipedia) ahh, i see there is talk of triangulating a simple polygon in
> O(n), but i'm not sure a connected graph of all objects constitutes a
> simple polygon?

You can do Delaunay-Triangulation in O(n*logn), but the point is that
I need to maintain a triangulation of moving points -- that's entirely
different from constructing one from scratch.

> The most important thing to keep in mind is that a good broad-phase
> algorithm should do zero work when nothing moves in the world.
> Are all your objects always moving in your world? How many objects are you
> talking about?

I should have mentioned that I'm writing a 2D space shooter, so all
the objects are moving all the time. And I'll have like 200 objects or
so.

Samuel

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

[<Pau...@sc...>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

> I should have mentioned that I'm writing a 2D space shooter, so all
> the objects are moving all the time. And I'll have like 200 objects or
> so.

Ahhh, ok - are you on a platform with reasonably quick memory (good caches 
etc)? Have you tried just gridding up your world (screen?) using a quite 
large cell size and do a simple bounding volume check in each cell 
location?

The advantage of the grid is that you don't need to do any work until 
objects move from one cell into another. Of course if your objects are all 
wildly different sizes this can get tricky - there are hierarchical grid 
methods to cope with this but they have their own limitations...

Cheers, Paul.
**********************************************************************
This email and any files transmitted with it are confidential and intended 
solely for the use of the individual or entity to whom they are addressed. 
If you have received this email in error please notify pos...@sc...
This footnote also confirms that this email message has been checked for 
all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United 
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: US-ASCII

wsBVAwUBS3EsOXajGqjtoMHxAQg4Fwf/RaCRsxE3qeBXKLjeVULeDqeVF0nQTZlB
ZHeSkQvQ+OLgjdJpVyZsCvCAnrU7zOBS+Zu+6MzDUSi1yRZMver7Nhzfz17d7fLk
tI6QLDkKzntTIMVhXjpMfxWqkLuHYElYfYzPbUQDSkLk1nhfg64alPQeFVse2huq
lPUwrdbL7VMNGXIcMlGScXK8xcVu1MADhZVg+2gfMUOxZrx4gv/F6qIaVVaXF3gE
dcGiSuccFinF1pq5GT5ax3/aoK3i3AREkaz6ktXjTI4AvC/1iCBF5WzPqAwUpQUo
5gOTOw3IijTM31cqU1nx3fa9h79rPx91KVnd7DjJAL3G6lneZ+jEtg==
=tWrz
-----END PGP SIGNATURE-----

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

[Sebastian S. <seb...@gm...>]

On Tue, Feb 9, 2010 at 9:35 AM, <Pau...@sc...> wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
>
> > I should have mentioned that I'm writing a 2D space shooter, so all
> > the objects are moving all the time. And I'll have like 200 objects or
> > so.
>
> Ahhh, ok - are you on a platform with reasonably quick memory (good caches
> etc)? Have you tried just gridding up your world (screen?) using a quite
> large cell size and do a simple bounding volume check in each cell
> location?
>

Or even use a fairly small cell size (the size of the largest objects), and
store cells with objects in them in a hashmap from the cell coordinate to a
list of objects. That way you can have an infinite grid and you only need
storage proportional to the number of non-empty cells for the grid itself.

Of course a simple BV hierarchy (e.g. AABB-tree, BIH, etc.) works too, since
you can usually adjust it to remain valid without doing a full re-insert
each frame.

I suspect that a simple SaP will outdo all of these though. It's just that
much simpler.

-- 
Sebastian Sylvan