RE: [Algorithms] Pack My Spheres Up Your Frustum
Brought to you by:
vexxed72
|
From: Ville M. <wi...@hy...> - 2000-10-13 08:08:41
|
IMHO, in large and highly dynamic environments, maintaining a BVH (where nodes in the tree can overlap spatially) is way more complicated than maintaining a spatial subdivision (BSP-tree and all other variants discussed to death on this list during the last couple of weeks) where nodes cannot overlap. The only minor hassle with spatial subdivisions is that objects may overlap multiple nodes in the tree - thus mailslot/timestamp mechanisms must be used. When you design your spatial database to be "dynamic" in the first place, the cost of moving an object (i.e. related physics code, cost of fetching transformation matrix into cache, other math involved) becomes a far greater cost than maintaining the subdivision. In the following text I am speaking mostly about cases where you have queries that touch only a portion of the database, i.e. visibility queries (VF culling/occlusion culling) and other region-to-region queries.. 1. In many cases, only a subset of all objects move every frame. Worlds tend to have static parts. Thus classification of objects into dynamic and static can be quite worthwhile, because it is often better to "do more work" for objects that are assumed to be static. For example, we insert dynamic objects into the database based on their approximate bounding volume, but static objects are inserted "exactly", i.e. by their mesh data. The classification of objects should be run-time, we used a simple rule: all objects that have not been moved for a certain time period become static (and 'dynamic' when they are moved again). 2. The key for updating _large_ databases is lazy evaluation. You just don't update portions of the database that are not visible. In our case the database update is embedded into the visibility query - only nodes that are determined visible by VF/occlusion/etc. culling are updated; they push objects down to their immediate child nodes in hope that the children will be hidden. When a new object is inserted into the database, we just place it into the root node. It will be pushed down the correct place during the next query. 3. Even dynamic objects tend to have coherence in their motion. So, don't update the database by deleting/re-inserting an object. Instead "push it up in the tree" from its current node until it fits some node. Then let the next visibility query "push it down" to its new place. If that part of the world is hidden, the object won't be processed for a long time. 4. For dynamic objects use "motion bounds". Estimate a bounding volume that is likely to fit the object for a certain period of time and insert the object into the database using that volume. Whenever the object is moved, you just check whether it breaks its motion bound - if it doesn't, you don't have to perform any updates to the spatial database. Craig Gotsmann and Oded Sudarsky have some excellent papers on this subject -- their main approach is to use the physics engine to feed in some information about "guaranteed" temporal bounds, however I dislike this approach... 5. Use tabu counters to prevent work. In highly volatile visible portions of the scene some nodes would have to be updated every frame regardless of the optimizations above. You can use a "tabu counter" to prevent updating the node for a certain number of frames.. This is a way of saying "oh well, this branch has N objects and they are all going to be visible anyway, so maintaining the branches below this is just going to be a waste of time - let's bite the bullet and process the objects". cheers, -wili Ville Miettinen http://surrender3d.com/umbra -----Original Message----- From: gda...@li... [mailto:gda...@li...]On Behalf Of Pierre Terdiman Sent: Friday, October 13, 2000 02:48 To: gda...@li... Subject: Re: [Algorithms] Pack My Spheres Up Your Frustum Dave, I know all of that. We're just not speaking about the same things. I, at least, am not speaking about collision detection, and the OBB trees are particularly irrelevant for the scenario I was talking about. As a reminder, I was just wondering how to speed up the VFC of a lot of dynamic objects. Those objects have a new position each frame, and they're the leaf nodes of the hypothetical spatial tree we want to build. OBB tree? Certainly not since it would be the same, for example, as updating the OBB tree of a deformable mesh. An AABB or a sphere tree would probably be better, but as I was saying, updating such a tree usually is slower than just culling the node. It would only be a win if we could use the same tree for several frames, although the objects have moved. It would also be a win if the same tree was used for many purposes (say VFC, collisions, and some raytracing). A confused thread, anyway. Pierre ----- Original Message ----- From: Dave Eberly <eb...@ma...> To: <gda...@li...> Sent: Thursday, October 12, 2000 11:10 PM Subject: Re: [Algorithms] Pack My Spheres Up Your Frustum > From: "Pierre Terdiman" <p.t...@wa...> > > > > Errr, but you need the tree anyway! How would you update it without > > computing the transforms...? Don't forget all objects are moving, in our > > case. The tree needs updating each frame. > > My explanation appears to have been insufficient. In NetImmerse, for the > purposes of collision detection, a trimesh can have an associated OBB tree, > built as described in Gottschalk's SIGGRAPH article. Each OBB in the tree > stores model and world space data for the box. The trimesh can be moving, > so the associated OBB tree is moving. Suppose two trimeshes are to be > compared for intersection. The top level OBB of each OBB tree has its world > space data computed by transforming the model space data with the current > model-to-world transform. If the two world-space OBBs do not intersect, > then you do not recurse on the children of the top level nodes of the tree. > If you do not recurse, then there is no need for the world space data of the > children OBBs to be current since you are not going to use those OBBs on > this pass. > > The trimesh objects are leaf nodes in the NetImmerse scene graph. The OBB > trees are entities that are separate from that scene graph and are used only > for collision detection purposes. The scene graph itself uses spheres (or > other user-specified bounding volumes) for comparison of scene graph nodes. > The same spheres are used both for view frustum culling and collision > detection. The OBB trees only kick in if the application wants a finer > analysis of the proximity of the objects. > > -- > Dave Eberly > eb...@ma... > http://www.magic-software.com > > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list _______________________________________________ GDAlgorithms-list mailing list GDA...@li... http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list |