Re: incremental triangulation for 2D collision detection broadphase
Samuel Moll <[email protected]>
| Newsgroups | gmane.games.devel.algorithms |
|---|---|
| Message-ID | <[email protected]> |
> 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 ------------------------------------------------------------------------------ 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 [email protected] https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list