PDA

View Full Version : Software Occlusion Culling



Cyrus The Evil
06-08-2006, 05:04 AM
Hi all.

I have a project to make a software occlusion culling, which restrict the using of hardware extensions such as NV_OCCLUSION_QUERY. Most of the occlusion algorithms I found use it, while the other didn't give me good pictures of how to do it. Can anyone help me how the occlusion culling be done?

I heard that there's a way of it using the stencil buffer, but I can't get how it can help to do an occlusion.

Btw, I plan to use it in an Octree data structure and after having Frustum Culling.

mikael_aronsson
06-08-2006, 06:35 AM
There are a number of libraries out there to do video decoding (most for MPEG video), but it all depends on your license demands.

Obli
06-08-2006, 12:14 PM
Originally posted by Cyrus The Evil:
I have a project to make a software occlusion culling, which restrict the using of hardware extensions such as NV_OCCLUSION_QUERY. Most of the occlusion algorithms I found use it, while the other didn't give me good pictures of how to do it. Can anyone help me how the occlusion culling be done?

I heard that there's a way of it using the stencil buffer, but I can't get how it can help to do an occlusion.I believe you must do it thuru portals, discarding everything comes near the rasterized pixels. You must obviously use less intensive geometry to make it work efficiently.

The other problem is that while NV_o_q, when correctly used, can give you resulting count for free, reading the results of the stencil comparation, no matter what, will cost at least a readback.

Cyrus The Evil
06-10-2006, 03:06 AM
Originally posted by mikael_aronsson:
There are a number of libraries out there to do video decoding (most for MPEG video), but it all depends on your license demands. Pardon me, but I don't do video decoding here. Thanks for the reply anyway. ^^


Originally posted by Obli:
I believe you must do it thuru portals, discarding everything comes near the rasterized pixels. You must obviously use less intensive geometry to make it work efficiently.

The other problem is that while NV_o_q, when correctly used, can give you resulting count for free, reading the results of the stencil comparation, no matter what, will cost at least a readback. My project is to have an occlusion culling for general purpose, so I believe portal won't suitable for it. Yet, the use of any occlusion extensions is forbidden (the credit goes to my teacher :mad: ), that's why I have to use much slower option.

Btw, I haven't mention yet that I need to know what's the best method to choose the best occluders. The only thing I can think of is to sort the triangles which pass the frustum culling and choose some biggest ones to be the occluders. However, I guess it's a very expensive operation in most case. Anyone?

jide
06-10-2006, 05:03 AM
If the credits go to your teacher then use extensions ! More simple, more fast, less headaches !

One way to do so is to find major occluders, using bounding boxes or bounding spheres and with throwing rays so that you can see if objects intersect your occluders. However there are some fall downs in doing so: a bounding cannot know if there are some holes in your objects. If there are holes, then try to split your geometry. Far objects suffer less this point.

Major occluders will generally be big objects in your scene. So if you only have triangles, you'll have to group them in meshes (which are here considered to be triangles sharing edges).

Hope that could help a bit.

Obli
06-10-2006, 12:22 PM
Well, the only thing you could try out is to split the computation along a bunch of frames... wait! Did I really wrote to split a per-frame task on a number of frames?

Why not? For some occluders, it may still work!
For example, if A covers B then you as long as you are in the "example" you cannot see B.
So, if you "don't get out of the line" and "A-B" doesn't change all the previous computations are still valid.
Well, I see this is more difficult. "the line" is in fact a frustum but... hey that's something!

This points me to another issue... do you have hints on the target machine or the crash test (occluder counts)?

As for the choosing the occluders, I would sort them from size at the beginning (loadup). Each time the camera is spawned, hiccup a bit and sort them by distance. Since the camera will then change position slowly, small swaps should do the trick of mantaining coherency.

Well, those are, after all, just words. Probably they are useless. I hope at least you can find inspiration from it!

Cyranose
06-10-2006, 01:29 PM
The easiest method is to simply render the frame using color tags. In other words, color each object or polygon uniquely (RGB = ID) and render.

Then read back the contents and make a histogram (count the number of times each color appears in the image). You can then tell what was drawn and how many pixels are visible. Make sure to disable all transparency, texture, and other color blending to get reliable results.

This method suffers mainly from the read-back time for the color buffer, but can be used to pre-compute visibility from sample viewpoints, say, a 3D grid in space.

Cyrus The Evil
06-16-2006, 10:00 PM
Thanks a lot to jide, Obli and Cyranose. You covered many aspects of my project and those really inspire me.

At last, I chose to use shadow frusta technique as T. Hudson has written it in his paper (http://www.cs.unc.edu/~walk/papers/hudson/shadow.pdf) which has no stencil buffer usage at all. If I have time I'll try to group the triangle occluders into mesh, just like jide said.

Thanks again for all your help. ^^