Culling interior triangles

Question

I have an array of thousands of quads; 4-sided 3D polygons. All I know are the coordinates of the quad corners.

A subset of these quads define the closed outer shell of a 3D shape. The remaining quads are on the inside of this closed solid.

How do I figure out which quads are part of the shell and which quads are part of the interior? This is not performance critical code.

---

Edit: Further constraints on the shape of the shell

• There are no holes inside the shape, it is a single surface.
• It contains both convex and concave portions.
• I have a few points which are known to be on the inside of the shell.

Answer 1

How about this?

Calculate the normal vector of a quad (call this the 'current' quad). Do an intersection test with that vector and all the remaining quads. If it intersects another quad in the positive portion of the vector you know the current quad is an internal quad. Repeat for all the remaining quads.

This assumes the quads 'face' outward.

Answer 2

This might be hard to implement if your shape self intersects, but if you can find one quad that you know is on the surface (possibly one furthest away from the centroid) then map out concentric circles of quads around it. Then find a continuous ring of quads outside that and so on, until you end up at the "opposite" side. If your quads intersect, or are internally connected, then that's more difficult. I'd try breaking apart those which intersect, then find all the possible smooth surfaces, and pick the one with the greatest internal volume.