Occlusion algorithms collection

Question

The occlusion algorithm is necessary in CAD and game industry. And they are different in the two industries I think. My questions are:

1. What kind of occlusion algorithms are applied respectively in the two indurstries?
2. and what is the difference?

I am working on CAD software development, and the occlusion algorithm we have adopted is - set the object identifier as its color (a integer) and then render the scene, at last, read the pixel to find out the visible objects. The performance is not so good, so I want to get some good ideas here. Thanks.

---

After read the anwsers, I want to clarify that the occlusion algorithms here means "occlusion culling" - find out visible surface or entities before send them into the pipeline.

With google, I have found a algorithm at gamasutra. Any other good ideas or findings? Thanks.

Lian

It sounds like you are using an item buffer: #499101 That's not a bad algorithm but will have some issues at the visual edges. – Trina

Answer 1

It stuck me that most of the answers so far only discuss image-order occlusion. I'm not entirely sure for CAD, but in games occlusion starts at a much higher level, using BSP trees, oct trees and/or portal rendering to quickly determine the objects that appear within the viewing frustum.

Truncated

+1. DirectX/OpenGL already does a decent job of drawing just the things you see (via a Z-buffer). If you wish to limit the amount of stuff you're rendering to get a better performance you have to look into one of these algorithms. – Rosalbarosalee

Yes; but apart from pixel based occlusion, D3D nor OpenGL do scene graph "magic". Clipping and culling isn't enough to justify sending all the polygons known to the rendering device, since clipping scales somewhat linearly. – Truncated

Answer 2

In games occlusion is done behind the scene using one of two 3D libraries: DirectX or OpenGL. To get into specifics, occlusion is done using a Z buffer. Each point has a Z component, points that are closer occlude points that are further away.

The occlusion algorithm is usually done in hardware by a dedicated 3D graphics processing chip that implements DirectX or OpenGL functions. A game program using DirectX or OpenGL will draw objects in 3D space, and have the OpenGL/DirectX library render the scene taking into account projection and occlusion.

Eveland

Answer 3

The term you should search on is hidden surface removal.

Realtime rendering usually takes advantage of one simple method of hidden surface removal: backface culling. Each poly will have a "surface normal" point that is pre-calculate at a set distance from the surface. By checking the angle of the surface normal with respect to the camera, you'd know that the surface is facing away, and therefore does not need to be rendered.

Here's some interactive flash-based demos and explanations.

Fiber

This process is necessary, but not sufficient. Any concave object will still need to have the surfaces rendered in the correct order, and if one object appears in front of another, then simple backface culling doesn't help. – Bijection

I named backface culling because Z-buffering was already mentioned. If I wrote any more, then I'd just be mostly reiterating the Wikipedia page I linked. – Fiber

Answer 4

Hardware pixel Z-Buffering is by far the simplest technique, however in high-density object scenes you can still be trying to render the same pixel multiple times, which may become a performance problem in some situations. - You certainly need to make sure that you're not mapping and texturing thousands of objects that just aren't visible.

I'm currently thinking about this issue in one of my projects, I've found this stimulated a few ideas: http://www.cs.tau.ac.il/~dcor/Graphics/adv-slides/short-image-based-culling.pdf

Bijection