Using octrees for visibility testing, to use occlusion queries or something else
Author
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]
Author
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?
What methods do you use in your engine? Or should I use something else instead of octree?
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.
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)
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)
Author
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.
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.
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 ^^
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 ^^
Author
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]
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]
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) ^^
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) ^^
Author
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]
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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement