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