Detect and Remove Hidden Surfaces of a Mesh

Question

For the past few weeks, I have been working on an algorithm that finds hidden surfaces of complex meshes and removes them. These hidden surfaces are completely occluded, and will never be seen. Due to the nature of the meshes I'm working with, there are a ton of these hidden triangles. In some cases, there are more hidden surfaces than visible surfaces. As removing them manually is prohibitive for larger meshes, I am looking to automate this with software.

My current algorithm consists of:

1. Generating several points on the surface of a triangle.
2. For each point, generate a hemisphere sampler aligned to the normal of the triangle.
3. Cast rays up into the hemispheres.
4. If there are less than a certain number of rays unoccluded, I flag the triangle for deletion.

However, this algorithm is causing a lot of grief. It's very inconsistent. While some of the "occluded" faces are not found as occluded by the algorithm, I'm more worried about very visible faces that get removed due to issues with the current implementation. Therefore, I'm wondering about two things, mainly:

1. Is there a better way to find and remove these hidden surfaces than raytracing?
2. Should I investigate non-random ray generation? I'm currently generating random directions in a cosine-weighted hemisphere, which could be causing issues. The only reason I haven't investigated this is because I have yet to find an algorithm to generate evenly-spaced rays in a hemisphere.

Note: This is intended to be an object space algorithm. That is, visibility from any angle--not a fixed camera.

Answer 1

I've actually never implemented ray tracing, but I have a few suggestions anyhow. As your goal is to detect every hidden triangle, you could turn the problem around and instead find every visible triangle.

I'm thinking of something along the lines of either:

1. Ray trace from the outside and towards the centre/perpendicular to the surface, mark any triangle hit as visible.
2. Cull all others.

or

1. Choose a view of your model.
2. Rasterize the model, (for example using a different colour for each triangle).
3. Mark any triangle visible as visible.
4. Change the orientation and repeat.
5. Cull all non-visible triangles.

The advantage of the last one is that it should be relatively cheap to implement using a graphics API, if you can read/write the pixels reliably.

A disadvantage of both would be the resolution needed. Triangles inside small openings that should not be culled may still be, thus the number of rays may be prohibitive (in the first algorithm) or you will require very large off screen frame buffers (in the second).

Answer 2

A couple of ideas that may help.

1. Use a connectivity test to determine what is connected to your main model (if there is one).
2. Use a variant of Depth Peeling (I've used it to convert shells into voxels; once you know what is inside the models that you want to keep (the voxels), you can intersect the junk that you want to remove.)
3. Create a connectivity graph and prune the graph based on the complexity of connected groups.