What is the fastest hidden-line removal algorithm

[Gregory]

Hi,

I am implementing my own hidden-line removal algorithm (not using GPU) and I am wondering if someone can recommend the fastest algorithm for scenes with moderate complexity (up to 5 partially occluding spheres, for example)

I currently have the standard z-buffer and it works fine for one object (for example one sphere). I have read about the hierarchical z buffer (Greene 93) and got impression it is faster only for scenes with large complexity.

The algorithm should work in real time (overlapping spheres can change their position or shape in a continuous motion)

Thank you
Gregory

[v71]

I wouldn't worry about 5 occluding spheres, visibility algorithm ranges from bsp, regular grids, octrees, kd-trees, quad-trees, portals and variations.
If your scene is composed of few moving object i would just drawn them, but if you need for some specific reason an occluding scheme i would do like this:
first i would sort object in relation to the viewer distance, then i would create an occluding frustum for each object and i would check iterative for each object if they fall in each other frustums, note that this would take
O( n^2 ) tests to be accomplished.
Another variation would be to use the new conditional rendering functions, which basically count how many pixels are hidden for each primitive you start the test with, and conditionally draw it without waiting for results from the gpu.

[Gregory]

Hi and thank you for the response.

What do you mean "If your scene is composed of few moving object i would just drawn them"? I need to hide the far objects, so I understant I would use the so called painter algorithm - drawing far objects first and then paining over them with near objects.

I will definitely check the occluding frustum, as you suggest.

Gregory

[TheNut]

v71 frustum approach is something I used before, except I did the comparison check during insertion sort. If it passes, then all objects in the list beyond the new object are retested for visibility. This way the algorithm rewards large fat occluders early on (if by chance you get them).

[Gregory]

Thanks,

Can you send me a link to v71 frustum approach? Google search picked something, but I am affaraid it did not find what I was looking for.

Gregory

[JarkkoL]

For software rendering, instead of z-buffer, you could also look into edge table or s-buffer.

[v71]

There isn't a former link to 'frusturum culling' , the appraoch is rather based
on my personal research in previous years.
first you need a function to construct a frustum from an object bounding box, the frustum needs to be oriented according to the viewer's orientation.
I also liked thenut's approach to check for occlusion during insertion sort.
I was just thinking to build a separating plane for each object and construct a sort of 'onthe fly bsp' as you walk the scene.

[Gregory]

Do you have a sense of the how much faster it will perform compared with the standard z buffer approach? All I am looking for is a faster algorithm to cull objects in really simple scenes.