Broadphase with markers

[ED209]

I'v implemented a broadphase from Gino's book with stab counters. I sneak peaked into the SOLID lib. to fully understand how it works. Implementation was a litle confusing tho cause in the book the counters represent overlaps to the left of the endpoint but in SOLID its to the right of the endpoint in oposite direction. So far so good untill i stumbled on this post from Erwin:

1) adding/removing objects in larger batches, and presort this batch in advance
2) for single queries and single add/removal: using marker objects

Add marker objects in the broadphase, and just search for the closest marker object, and insert from there.

Stabbing numbers are fine too, but the approach easily breaks if there are large objects in the broadphase.

This marker thing looks interesting. Erwin can you please explain how it works?

[Erwin Coumans]

For performance of single shot queries (just checking broadphase overlap with an arbitrary AABB, without inserting this AABB) I think using marker objects works better then stabbing numbers.

Single shot queries, you can insert marker objects at evenly distributed over your space, and then first do a quick search for the nearest marker object, and start searching the broadphase using that marker's information. Normally, you would start searching from the begin/end of each axis, and swap until you are at the right location. Now, you start from this marker objects begin/end point. So a marker object can be any object in the broadphase, but instead of using any objects, just choose a set of marker objects, that you inserted at convenient locations.

As usual, when time allows, I will add a demo to Bullet to demonstrate this 'marker' idea.

Erwin


Note 0:
For add/remove objects, batching up all objects, and presorting them works best. The approximate cost become O(m log(m)) + O(n). This is respectively the sorting cost of m new objects + batch inserting cost, which become linear in the total number of objects.

Note 1:
I discussed it a while ago with Gino, and he doesn't use stab counters in his latest (not released yet) Solid incarnation anymore either. He is using more 'temporal' /kinetic concepts now, which speed up regular queries a lot (see his recent GDC presentations). So the relative motion of the begin/end points. Very similar to Dan Coming's http://graphics.idav.ucdavis.edu/resear ... weep_prune

[ED209]

Thanks alot for the reply i will look into those papers and try to implement it right away. I knew there was something fishy with those stab counters i didn't like them from the start.