[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
GTC: visibility culling for scene graphs
I've been thinking about visibility culling. Since we seek to be able to do all
kinds of games efficiently, we most definetly need visibility culling. This is
necessary for FPS and CRPG.
The method I'm thinking about resembles something I saw a few years ago in
SIGGRAPH. I would need to revisit that paper to see what I can use.
After each object of the scene graph is rendered, a low resolution conservative
Z buffer is computed (I will call this a V-buffer for Visibility Buffer). For
this example, let's assume the screen resolution is 1000x1000 while the V-buffer
uses a 100x100 resolution. That means that each V-xel corresponds to a 10x10
grid of pixels. What we do is we take the max (furthest) Z value of each grid of
10x10 pixel and put it in the Z-buf. Then when we draw a new object, we take its
bounding box, project it and check if it lies entirely behind the V-buf. If it
does, it should not be drawn at all.
That's the basic idea. The paper used a hierarchy of V-bufs, like mipmaps, they
were of resolution 1x1, 2x2, 4x4, 8x8, etc... and each V-buf is obtained from
the next one in the obvious way.
For more efficiency, the objects in the scene graph should be rendered in
front-to-back order. This way the V-bufs will get filled in more rapidly and
more objects will be culled.
Now, glReadPixels can be used to read the depth buffer. However, the bandwidth
ramifications of this are icky for large pictures.
An alternative is a two-pass algorithm.
In the first pass, we only use a 64x64 piece of the frame buffer and then only
use the Z buffer. Objects are rendered as described above, but to the 64x64
buffer. After each object, the 64x64 buffer is read back and the V-bufs are
updated (the transfer is 16KB for 32 bit Z-buffer values, probably acceptable).
Objects in the scene graph are tagged according to whether or not they are
drawn. When we are done, we traverse the scene graph again in the same order,
but this time only draw objects that are tagged to be drawn.
The problem with this approach is that it's not exact; the Z value in the V bufs
is not generated using the maximum of the Z values in the corresponding full
resolution picture.
Another alternative is to make a SW renderer that only looks at Z value (that's
easy) and takes care to write conservative Z values (the maximal value for the
pixel, that's easy too). Then objects are rendered using that renderer. A low
resolution 64x64 picture can probably be generated extremely quickly even in
software. An additional optimization would be to allow to substitute a
simplified mesh for the real mesh for visibility determination purposes. The
simplified mesh would have to be strictly conservative (smaller). This would
give us the additional benefit of not having to xform all vertices for this
visibility culling step; in the future we hope that xform will be performed by
the HW so a SW xform of everything is a waste of time. In case we don't use
simplified meshes, the xformed vertices should be cached for use in the second
step, hopefully this would save us some time.
If any of you has a better idea for a general visibility culling algorithm,
please share your thoughts.
Sebastien Loisel -- McGill University -- Sun Microsystems
http://www.math.mcgill.ca/~loisel/
*************************************************************
To unsubscribe, send an e-mail to majordomo@gtc.seul.org with
unsubscribe gtc-dev in the body. http://gtc.seul.org/