Archived

This topic is now archived and is closed to further replies.

Efficient Visibilty Culling in Scene Graphs

This topic is 5672 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I''ve been reading OGL Game Programming and was wondering how one can efficiently do visibility culling within a simple scene graph structure like the one presented in the book. This would include the culling of interactive objects within the game world like other players, objects, enemies etc... Any Ideas, links etc.. would be greatly appreciated. Cheers <Fish>{

Share this post


Link to post
Share on other sites
A bsp tree for static scenery
A sphere-tree, oct-tree, quad-tree, or a variant there-of for dynamic content.

Essentially, you have a tree of nodes, and each node knows how big it is (and every parent node encompasses all of its children). Then you take the viewing frustrum and perform a collison detection against the world with it. Whatever collides, is rendered.

There's also portal engines, which cull further using in-game geometry to determine what is visible. It needs to know where the "windows" (i.e. portals) are, culls geometry inside of those nodes, then re-adds (unculls?) geometry visible from the portal.
Suppose you had a hut with a window. Using a portal engine, you could render just the stuff visible inside the hut, instead of rendering everything instead the hut and relying on the z-buffer to cull unvisible pixels. Again it uses collision detection, but this time using a reduced viewing frustrum projected into the hut through the portal.
Once you have a portal engine, using a render-to-texture technique, you can make 'magic mirrors' that look into other areas of the world, or even have them act like real mirrors. Just add fog or environment mapping (or both) to the rendered texture. It's an expensive effect, but it looks cool.

nVidia has been pound thier heads screaming "BATCH" at everyone looking for performance, so it seems like you should transverse a portion of your scene graph, render it, then continue transversing the graph.

(Is unvisible a word?)

Try searching in the graphics programming forum, for more information about any of those topics.

Magmai Kai Holmlor

"Oh, like you've never written buggy code" - Lee

[Look for information | GDNet Start Here | GDNet Search Tool | GDNet FAQ | MSDN RTF[L] | SGI STL Docs | STFW | Asking Smart Questions ]

[Free C++ Libraries | Boost | ACE | Loki | MTL | Blitz++ | wxWindows]


[edited by - Magmai Kai Holmlor on June 5, 2002 6:23:55 PM]

Share this post


Link to post
Share on other sites
I understand bsp pvs but the thing that''s currently worrying me is what about the other objects (players,objects,etc) ? Should these be stored in a different tree structure ? How would one structure a tree made up of say .. quake mdls ? And how the heck does one frustrum cull in a tree made up of models ? I''ve checked online using google and couldn''t find anything helpfull !
arrghhh

<Fish>{

Share this post


Link to post
Share on other sites
quote:
Original post by Magmai Kai Holmlor
A sphere-tree, oct-tree, quad-tree, or a variant there-of for dynamic content.


I believe Quake3 uses bounding cylinders for its models; then you need to know where on the map each player is (a center <x,y,z>. You can perform the CD from that - the cylinder will either be in or out of the viewing frustrum.

Share this post


Link to post
Share on other sites
I''m sorry I must be incredibly dense or something... but I still don''t get it.
Everyone seems to say that when you have your scenegraph you put the world as the root node and the other objects as children. Well the way I have it is with the bsprender-worldclass as a root node and all that''s left in the graph is one model which is a QMDL class attached to the root node as a child. Now when the system renders it calls the root which renders the bsp with pvs and then goes on to render the model. If I had a scene graph with a bsp level and 5 models what would that look like (tree-structure) ? The way I understand it, it doesn''t seem correct It feels clumbsy. I keep on finding these wierd scene graph APIs online which have graphs with camera and other wierd objects in them. This is all getting severly confusing !!

<Fish>{

Share this post


Link to post
Share on other sites
I imagine Quake doesn''t use a heirarchial scene graph. There''s probably just the bsp tree for the level, an array of players, and an array of projectiles.

You could always render everything - but that''s not very fast.

Instead, you use a bsp tree to only render the map poly''s you need to. Then loop through the array of players; if any part of them is in the viewing frustrum, render them. Again, you would rely on the hardware z-buffer to make certain it is drawn correctly. (same goes for projectiles)

To test to see if an object is in the viewing frustrum, you just need to check which side of six planes the object is on (the 6 planes that delineate the viewing frustrum). It should be very similar math to what''s in your bsp parser.


root
|
+-bsp map
|
+-player1
|
+-player2
|
+-player3
|
...
|
+-projectile1
|
+-projectile2
|
...


With a Quake style game you can make it flat, because there''s not that many objects.


root
|
+-bsp map
|
+-oct-tree (same size as map extents)
|
+-quadrant1
| |
| +-quadrant1.1
| |
| +-quadrant1.2
| |
| ...
|
+-quadrant2
| |
| +-quadrant2.1
| | |
| | +-player1
| |
| +-quadrant2.2
| |
| ...
|
+-quadrant3
|
+-quadrant4
|
+-quadrant5
|
+-quadrant6
|
+-quadrant7
| |
| +-quadrant7.1
| |
| +-quadrant7.2
| |
| +-rocketF34A90CD
|
+-quadrant8


an oct-tree break the world cube into 8 smaller cubes, recursively. If quadrant1 fails to collide with the viewing frustrum, you know all the quadrant1.x''s also fail to collide, so you don''t need to check stuff in them. When a quadrant does collide, you check it''s children.

Search for articles on this site and others, I''m sure they''ll go into far more detail than I am willing to

Share this post


Link to post
Share on other sites