Provide access to list of active objects

[GoogleCodeExporter]

It will also help improve performance internally, when iterating over 
arrays of all objects.

Original issue reported on code.google.com by erwin.coumans on 4 Nov 2008 at 10:54

[GoogleCodeExporter]

Now there is:

btCollisionObjectArray& btCollisionWorld::getActiveObjects();

http://code.google.com/p/bullet/source/detail?r=1472

Original comment by erwin.coumans on 7 Nov 2008 at 3:39

• Changed state: Fixed

[GoogleCodeExporter]

getActiveObjects has been removed, it was not reliable.

Island / (de) activation will be improved for Bullet 2.74.

Original comment by erwin.coumans on 11 Nov 2008 at 4:04

• Changed state: New
• Added labels: Milestone-2.74
• Removed labels: Milestone-2.73

[GoogleCodeExporter]

getActiveObjects has been removed, it was not reliable.

delay: Island / (de) activation will be improved for Bullet 2.75.

Original comment by erwin.coumans on 12 Feb 2009 at 11:14

• Added labels: Milestone-2.75
• Removed labels: Milestone-2.74

[GoogleCodeExporter]

Why not use two body lists? 

1. Static Bodies
2. Non static bodies

This would speed up things without much changes. 

Original comment by linz...@gmx.de on 13 Feb 2009 at 12:47

[GoogleCodeExporter]

"Why not use two body lists?"

This would still present a problem for large numbers of sleeping objects.  This 
seems 
somewhat related to issue 73, and I suspect that the solutions could be 
somewhat 
similar.

Original comment by Alex.Sil...@gmail.com on 23 Mar 2009 at 12:36

[GoogleCodeExporter]

I don't see any benefit to mix up sleeping objects and static objects.
Static objects should go in a seperate list and sleeping objects should be 
handled by
the island manager.

Original comment by linz...@gmx.de on 26 Mar 2009 at 2:19

[GoogleCodeExporter]

Original comment by erwin.coumans on 6 May 2009 at 7:17

• Added labels: Milestone-2.76
• Removed labels: Milestone-2.75

[GoogleCodeExporter]

Small improvement: added new array that only contain non-static rigid bodies:
http://code.google.com/p/bullet/source/detail?r=1691

Iterative over this array in most cases, instead of over all collision objects.

Note: for performance it is better to add static geometry as btCollisionObject, 
instead 
of btRigidBody with mass 0!

Original comment by erwin.coumans on 11 Jun 2009 at 1:25

[GoogleCodeExporter]

Thanks a lot Erwin. In our game the performance increase due to this 'small
improvement' was 400%. It had around 1500 static objects and a handful of 
dynamic.

Original comment by linz...@gmx.de on 12 Jun 2009 at 10:11

[GoogleCodeExporter]

An array of static objects is internally used now, but no separate array for 
sleeping 
objects. We are now focussing on Bullet 3.x and stabilize Bullet 2.x. We might 
address 
the issue in 3.x, if really necessary.

Original comment by erwin.coumans on 18 Dec 2009 at 1:08

• Changed state: WontFix
• Removed labels: Milestone-2.76

[GoogleCodeExporter]

Are seperate arrays for active,sleeping, static and kinematic bodies still on 
track for Bullet 3.x?

Although the STATIC_SIMULATION_ISLAND_OPTIMIZATION flag takes care of not 
updating static/kinematic bodies Bullet still needs to iterate over all bodies 
in the world. With large worlds this becomes quickly a bottleneck.

Original comment by linz...@gmx.de on 10 Mar 2011 at 9:07

[GoogleCodeExporter]

These kinds of things are really big performance issues for some environments. 
The VR environment I work on has sixty thousand or more interactive objects, 
but most are at rest most of the time. That's not even static geometry. We had 
to work a physics engine pipeline that eliminated the overhead of all static 
AND resting bodies from the runtime of the engine. I'm writing a paper this.

It's not enough just to have a way of traversing the set of active bodies, 
though that's necessary. The internals of the physics engine has to NEVER 
traverse the set of resting bodies under any conditions. Bullet does a really 
good job of reducing the overhead of the major stages (narrow phase CD & 
constraint solving) when islands are at rest, and resting/activating at the 
island-level is good. But you have to retool how other things are done such as 
the broad phase, contact group ("island") generation, and a lot of "little" 
stages where presently bullet traverses the object set.

Our reworked physics engine was based originally on ODE, though only the 
quickstep constraint solver remains of that now. I've thought about modifying 
Bullet the same way, BUT:

1. The work isn't very isolatable, so I might be stepping on a lot of other 
people's toes.
2. It may get in the way of other priorities that Coumans et. al. are working 
on.
3. I've never contributed to Bullet and am not in the inner circle, and don't 
know how that would go down.
4. There may be compromises, but I believe it's possible to keep the same high 
performance under high-activity as well.

The performance is awesome when most objects are at rest. Physics engine takes 
almost no time. We never looked back...

Daniel

Original comment by daniel.j...@gmail.com on 23 May 2011 at 11:01

[GoogleCodeExporter]

Hi Daniel, can you keep us up-to-date on your work?

"The internals of the physics engine has to NEVER traverse the set of resting 
bodies under any conditions."

The easiest way to achieve this using Bullet is to remove sleeping objects from 
the world, and only keep a special proxy object. Whenever active objects 
collide against such proxy object, the sleeping object gets inserted into the 
world. Several shipping games used this optimization. Sleeping objects can even 
be deleted, to reduce memory overhead a lot. It would be good to add a demo 
showing how to implement this.

Original comment by erwin.coumans on 24 May 2011 at 1:42

[GoogleCodeExporter]

to be more precise: only keep a special proxy object in the broadphase.

Original comment by erwin.coumans on 24 May 2011 at 1:43

[GoogleCodeExporter]

That is interesting. We implemented something somewhat similar using a Bullet 
physics accelerator on a Cell blade. We'd actually use our broad phase on the 
standard PC hardware, then use that to maintain the set of objects that Bullet 
knows about: active objects and objects overlapping active objects in the broad 
phase. Then we'd have Bullet do its thing and get results back. The remaining 
text has nothing to do with this.

There are some advantages to what we're doing now as compared to broad phase 
proxies, though our method does use more memory. When a resting island is 
disturbed by collision with an active object, all of the contact information 
between objects in the island is cached and available, with new contact info 
from the active object added to it. There is no physics cycle where we have 
incomplete constraints, nor do you have to go back and recompute them (though I 
suppose this could be an option for lower memory use). You also don't have to 
dynamically add/remove objects each cycle, though Bullet seems to do this much 
more quickly than ODE did.

You can reduce memory use for resting bodies by using a different struct/format 
for bodies based upon state (physics-active, ik-moving, physics-resting, 
ik-unmoving). This becomes more natural when you need to separate them anyway. 
This is practically equivalent to deleting objects since you're storing them in 
a "compact form" with the minimum info that you'd need to restore them anyway. 
Better, perhaps, because only a full activation (narrow phase collision) 
restores the object's memory use (by changing state), rather than just 
requiring a broad phase overlap. Developers wouldn't have to apply changes to 
the system to get better performance or memory use for environments with many 
objects at rest. And I don't see it slowing down any other case (of course I 
could be wrong).

So when using these broad phase proxies, I guess that objects are added after 
broad phase processing and before narrow phase, in the middle of the physics 
cycle? The alternative would be skipping a cycle, and I'm not sure what the 
effect of missing some constraints in a processing cycle are. Which brings me 
to another question: Bullet skips narrow phase collision detection between 
pairs of sleeping bodies, so there are no constraints generated between them. 
If that island is activated by a collision with an active body, those 
constraints aren't available until next cycle? So are the constraints of that 
contact group incomplete/inaccurate until the next time step? If that *is* the 
case, I guess that it's not a serious issue?

I will send you a copy of my paper when it's finished, if you're interested.

Daniel

Original comment by daniel.j...@gmail.com on 24 May 2011 at 3:46

[GoogleCodeExporter]

The Bullet broadphase have a addPair and removePair. When adding a pair that 
involves a 'sleeping' proxy, the sleeping object will be activated, the proxy 
type changes, and an actual pair will be generated. So there is no delay/cycle 
skipped, all constraints are fine.  In 2003 we used this for a PS2 game and 
objects were streamed from cdrom. Sleeping objects only consumed the memory of 
a world transform.

Given this info, are there specific benefits to your approach?

Original comment by erwin.coumans on 24 May 2011 at 3:57

[GoogleCodeExporter]

Today I did a quick refactor of Bullet, maintaining an array of 'active' rigid 
bodies, and an attempt of never traversing non-active rigid bodies.

I got rid of almost all non-active rigid body traversals, except for one, in 
the island generation. This can also be removed, by storing the 'active' flag 
in the overlapping pairs (at creation), and incrementally updating this flag 
when needed.

In the optimized case, you still need to traverse over all overlapping pairs. 
It seems best to separate 'active' overlapping pairs and 'non-active' 
overlapping pairs, so the narrowphase only processes the 'active' overlapping 
pairs (having at least one active body).

Of course, in the worst case, all objects are connected and sleeping and a 
single object wakes up: in that case, you need to traverse all.

Either way, I'm interested in your work. Perhaps you want to start a topic in 
the Bullet physics forums, so others can read about it too (this issue tracker 
is fairly invisible to most)?

Original comment by erwin.coumans on 24 May 2011 at 9:07

[GoogleCodeExporter]

By the way, the performance dropped from 25ms to 4ms when creating 40000 
sleeping boxes (non-overlapping) in the air. I could cleanup the code and move 
it in trunk if there is enough interest.

Original comment by erwin.coumans on 24 May 2011 at 9:14

• Changed state: Accepted

[GoogleCodeExporter]

Continued the conversation with my reply in the Bullet forums here:

http://bulletphysics.org/Bullet/phpBB3/viewtopic.php?f=4&t=6833

Daniel

Original comment by daniel.j...@gmail.com on 24 May 2011 at 10:04

[GoogleCodeExporter]

Focus is shifting to Bullet 3.x so new features are moved to a new issue 
tracker:

https://github.com/erwincoumans/experiments/issues/3

(most updates to Bullet 2.x will be bug fixes and maintenance)

Original comment by erwin.coumans on 1 Nov 2011 at 4:18

• Changed state: WontFix