Visibility Determination

I'm a fan of image-space occlusion culling techniques, which kind of boil down to rendering a version of the scene (that might be simplified using bounding volumes) to the a depth buffer. The depth buffer then represents the occlusion surface for the entire scene----anything that is occluded will not produce any pixels on top of this occlusion surface (approximately---to the depth buffer dimensions and with any error introduced by using bounding volumes to build the depth buffer). Then you can use hardware or software queries to see if a given bit of your world is occluded....just render, say, a box for every cell in your world. If the box produces a pixel that lies in front of the occlusion surface depth buffer, that cell is not occluded. If no such pixels are produced, that cell is occluded. Hierarchical depth buffer techniques, such as ATI's hierarchical Z or the University of North Carolina @ Chapel Hill's Hierarchical Occlusion Map (HOM, 1997) (and perhaps more advanced things) can be quite fast at doing these queries.

The HOM technique is very clever, and can be done pretty easily in pure software, or with programmable GPU's.

The reason I kind of prefer image-space techniques is twofold. First, you automatically get something called "occluder fusion", in which multiple occluders are blended together to far far more easily determine when a given object is occluded by multiple occluders, but not by any single occluder. And...when the world is very complex, image-space techniques have the potential to be far faster than object space occlusion culling. But, there are pros and cons to all techniques.

Interesting idea, but I still like object-space culling. I think it works better in my case.
I've almost figured a way to determine visibility when all regions are boxes: Say you have box1 and box2; You need to determine if any point of box2 is visible from some point of box1. For every pair (s1,s2) of sides of box1 and box2 such that s1 and s2 face each other do: build a transformation that projects s1 onto s2 (I still hadn't figured out how to do it, but it should be easy), clip every poly by planes of s1 and s2, and use the transformation to project every poly onto s1. Then you can just check if the projections cover s1 entirely. If they do, try another pair. Otherwise the boxes are visible to each other.
But I need a more general approach, or at least a faster one.
Thanks for any help.

Have you already considered a basic frustum culling based approach? Test if the boxes/spheres that enclose each cell are inside the frustum, if they are, render the contents of the cell (basic tree approach).

If you change your mind about graham's approach there are various occlusion query extensions implemented for OpenGL to solve this type of problem.

Here's a link to an nvidia extension, not sure if it is still up-to-date, but gives you an idea of what it is/does:

http://oss.sgi.com/projects/ogl-sample/registry/ARB/occlusion_query.txt

There should be others for ATI.

??? tthibault
How would you handle regions occluded by other polygons and objects? That's the whole point: I need a table that says which polys are visible from every region (not occluded by anything). What I'm actually asking is how to build such a table.

I have already implemented occlusion queries; I'm using Direct3D and thet have build-in mechanisms for this (if you can call D3DX a build-in library).