I have a mesh that I will be rendering (in software) from a few known camera orientations. As it turns out, given a mesh, there will typically be many faces that will never be visible (always occluded) when rendered from any of my preset camera orientations. I am thinking that it should be fairly practical to pre-process the mesh to remove any hidden geometry. Can anyone recommend a general approach to this problem? I do not have a z buffer, and would like to avoid per-pixel calculations if possible. My first inclination is to walk the vertices and cast rays toward my potential camera positions, checking for intersections with other faces. This sounds really slow (even for a preprocessing pass) without some sort of space partitioning structure such as a kd-tree or bsp organizing the faces. Are there any more obvious or simpler solutions I should be looking at? Thanks in advance.

Quote:Original post by Klapaucius
My first inclination is to walk the vertices and cast rays toward my potential camera positions, checking for intersections with other faces. This sounds really slow (even for a preprocessing pass) without some sort of space partitioning structure such as a kd-tree or bsp organizing the faces.

This won't work. It's possible for a face to be visible, even when none of it's vertices are.

Anyway, I would go with an image based approach anyway. It will be the easiest, it won't be that slow either, and you won't have to put any restrictions on your geometry (like having closed meshes or something).

Quote: This won't work. It's possible for a face to be visible, even when none of it's vertices are.

Ah, you are right of course. Thank you.

If you have just a small set of points and don't want to use a graphics card for whatever reason, I suggest simply ray-tracing from those view-points to find the visible surfaces. If you can use a graphics card, you can render the scene from you view points, setting the color to be the triangle index. You can read back the frame-buffer to get the visible set of triangles.

If you have a very large set of view points, or expect free rotation around the object, I suggest looking at a "from-region" method (for just a few viewpoints these are definitely overkill!). These typically compute the visible triangles from a volume in 3D space, but tend to be slow. The cost would amortize with enough viewpoints. You can set up your regions to be a partitioning of a bounding sphere. You can try this or this if speed is preferred over accuracy, or this if accuracy is paramount.

Quote:Original post by crowley9If you can use a graphics card, you can render the scene from you view points, setting the color to be the triangle index. You can read back the frame-buffer to get the visible set of triangles.

This is an interesting idea that I hadn't even considered. This specific application has to run without access to any graphics hardware, but I could render a pass like you suggest at startup fairly easily. This sounds more straightforward than adding a z buffer for my specific application. I think I will implement a variation of this to test right away.

Quote:If you have a very large set of view points, or expect free rotation around the object, I suggest looking at a "from-region" method

I agree that these methods are probably overkill in my case.

I have fewer than 10 potential view points, and a polygon count on the order of a few thousand. I am attempting to cull occluded faces because I need to rasterize in software on pretty underpowered machines, and I don't have much processing headroom.

Thanks for the pointers so far!

Quote:Original post by swiftcoderIf you have the graphics card at startup, where does it go?

Sorry, I don't think I was clear. I could render a pass at startup using the normal software rasterizer (using triangle index as color) to a bitmap, then use that to mark a list of faces as visible. Faces that didn't get rendered from any view would get flagged and deleted.

Quote:How underpowered are we talking? Even an eeepc with an Intel-integrated GMA 950 can render 50,000 triangles.

Very :) this is targeted at the flash 9 VM, potentially running on that GMA 950 PC. 50K polygons are pretty much out of the question for me :(

Quote:Original post by crowley9
If you can use a graphics card, you can render the scene from you view points, setting the color to be the triangle index. You can read back the frame-buffer to get the visible set of triangles.

As stated, I do not have access to a graphics card, but I took this same approach in software and it works great. Thanks for the hint!