RE: [Algorithms] Pack My Spheres Up Your Frustum

[Ville M. <wi...@hy...>]

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