Sign in to follow this  
CadeF

Using octrees for visibility testing, to use occlusion queries or something else

Recommended Posts

Hi everyone, I have a simple question. In your engines, how do you traverse a quadtree to get the visibile polygons? My current method- For each node .bTest=False .bVisible=False Node[0].bTest=True For each node If .bTest then Occulsion query start Render as box Occulsion query end If Occulsion query result > 0 then .bVisible = true For each child node of node .bTest = true Next End if End Ef Next Is this the best way to go about doing it? Any suggestions on how I might improve it? [Edited by - CadeF on November 4, 2005 9:10:39 PM]

Share this post


Link to post
Share on other sites
Update - This might not be a good way. In my engine, there are some large open areas and some small open areas. If I stand in a corridor smaller than an octree node (the node around it), the octree node does not pass the depth test and thus the corridor I am in, is marked as not visible.

What methods do you use in your engine? Or should I use something else instead of octree?

Share this post


Link to post
Share on other sites
I've been looking into implementing occlusion culling in my current project which uses an octree as the underlying data structure for arranging the world geometry. From some of the advice I received when inquiring about this on another forum I was advised this paper on the subject which they had used as the basis for their own implementations. Might be worth reading to see if it's applicable for your own project.

Share this post


Link to post
Share on other sites
Hi,

If you have access to the book "GPU Gems 2", there's a good article on how to use hardware occlusion queries.

As for octrees, simple frustum culling (if a node isn't visible, discard all its children, if it's entirelly visible, display all the children without testing, and if half visible, recurse through the children) gives pretty good results in outdoor environnements. In Indoor levels, there is a lot of overdraw, so occlusion queries --or at least a better algo than frustum culling-- is required.

You can also precompute a PVS for your octree. There are many papers on the web dealing with algorithms to compute PVS for octrees / quadtrees. They are quite complicated, but if you manage to implement one of those, it gives really good results (better than occlusion query in the case of static geometries)

Back to occlusion query : When you query the result, it can introduce a lag. When rendering, (for ex, issuing a DIP call) the commands are buffered, and the CPU can continue with its code. The GPU don't necesseraly draw the data immediately. And if you query the occlusion results, you'll have to wait for the drawing to be done, and the GPU to give back the occlusion results. So you "break" parallelism between CPU and GPU with a "naive" implementation (that's what I understood from reading the chapter about occ. query ^^)

I can't explain how they do occ. query because I don't fully understand it (I'm not working on that part myself, so I don't have time to understand) But basically, they take advantage of time coherency (at a given fram, if something is visible, it's highly probable that it will still be visible next frame) and spacial hierarchy (to sort the node from front to back or vice versa easilly)

Share this post


Link to post
Share on other sites
Thanks :)

I've tried occulsion culling. Lets say I am standing in a small room. The smallest node is larger than the room. Thus, I cannot see the node when I am standing in the small room. And so the room turns invisible, as it's node doesn't pass the depth test. So, I'll look into other methods with octrees.

I am using a mix of indoor and outdoor. Not massive outdoor rolling terrains, but a few streets with tall buildings. Some of those buildings can be entered. Once I am far enough in the doorway, it loads the map of the interior of that building. That sort of stuff.

If anyone has played Deus Ex, I am using the New York street map, outside the Ton Hotel, the Paris outdoor area and the Hong Kong market for testing my quadtree.

Also, why are people (on this forum) generally against BSP trees? So many games use them. I personally haven't tried them yet.

What I do for the occulsion query test
-Clear ZBuffer
-Fill the ZBuffer with the map (If its not the first frame, the nodes from the last frame)
-Occulsion query from the current camera position & direction checks for visible nodes with Z-Write disabled, but Z-Read enabled.

Share this post


Link to post
Share on other sites
I'm not agaisnt BSP trees, but I remember it has some limitations : not good with big outdoor environements, and only usefull for static environement. Whereas occlusion query can be used with dynmic scenes and in almost any environement type.

On the other hand, octrees are a lot more simpler to use, and you can modify them at runtime (well, if there isn't too much changes that is)

Héhé, I'm lucky, I found the .pdf corresponding to the GPU Gems 2 article I told you about : Hardware occlusion query made usefull
Read it, you will probably find a lot of answers to your questions ^^

Share this post


Link to post
Share on other sites
Please define "not good" with outdoor enviroments. I just don't want to use it as the splitting makes more polygons and splitting around a circular pillar makes a ton of cuts.

Also, could I please have some code? That paper is sort of confusing. Or is it better if I used BSP trees or some other tree? What would be the best tree to use?

Thanks :)

[Edited by - CadeF on November 4, 2005 6:39:35 AM]

Share this post


Link to post
Share on other sites
Hmm define "not good" ... bad ? ^^
I mean : BSP is good in scenes where there is a lot of convex area, such as indoor environements because. It comes from the way a BSP is used (each leaf store a set of convex faces) But nowaday, I don't think "pure" BSP tree like that are still used. They use portals and such algorithms, and I don't know exactly how it works. BUT I know it still works better in indoor environement where there is a lot of occlusion and convex areas.

For the paper, I'm afraid you won't find a piece of code already working. But understanding it and applying it shouldn't be too difficult. And it's a good exercise (if you work in CG, you'll have to read a lot of those "boring" papers and implement them without any help) ^^

Share this post


Link to post
Share on other sites
How would a portal rendering system work? If I split a scene where the portals are. Instead of splitting a polygon, is it fine if I have the whole polygon in both the front and the back list of that portal?

I don't have a "closed map". I just have a polygon list, so I'm not sure if I can use bsp. Also, in some places, my poly count is very high so I do not want to split polygons or have to look at things at the polygon level.

I've got occlusion queries with octtrees to work, but the occulsion queries are slow.

[Edited by - CadeF on November 4, 2005 9:50:04 PM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this