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

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.

Answer 2

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 3

Consider that all of the quads live inside a large sealed box. Pick one quad. Do raytracing; treat that quad as a light source, and treat all other quads as reflective and fuzzy, where a hit to a quad will send light in all directions from that surface, but not around corners.

If no light rays hit the external box after all nodes have had a chance to be hit, treat that quad as internal.

If it's convex, or internal quads didn't share edges with external quads, there are easier ways.

Answer 4

It can be done quite easily if the shape is convex. When the shape is concave it is much harder.

In the convex case find the centroid by computing the average of all of the points. This gives a point that is in the interior for which the following property holds:

If you project four rays from the centroid to each corner of a quad you define a pyramid cut into two parts, one part contains space interior to the shape and the other part defines space that might be exterior to the shape.

These two volumes give you a decision process to check if a quad is on the boundary or not. If any point from another quad occurs in the outside volume then the quad is not on the boundary and can be discarded as an interior quad.

Edit: Just seen your clarification above. In the harder case that the shape is concave then you need one of two things;

1. A description (parameterisation) of the shape that you can use to choose quads with, or
2. Some other property such as all of the boundary quads being contiguous

Further edit: Just realised that what you are describing would be a concave hull for the points. Try looking at some of the results in this search page.

Answer 5

You may be able to make your problem easier by reducing the number of quads that you have to deal with.

You know that some of the quads form a closed shell. Therefore, those quads are connected at their edges. If three mutually adjacent edges of a quad (that is, the edges form a closed loop) overlap the edge of another quad, then these quads might be part of the shell (these mutually adjacent edges serve as the boundary of a 2D region; let's call that region the "connected face" of the quad). Make a list of these "shell candidates". Now, look through this list and throw out any candidate who has an edge that does not overlap with another candidate (that is, the edge overlaps an edge of a quad that is not in the list). Repeat this culling process until you are no longer able to remove any quads. What you have left should be your shell. Create a "non-shell quads" list containing all of the quads not in the "shell" list.

Draw a bounding box (or sphere, ellipse, etc) around this shell. Now, look through your list of non-shell quads, and throw out any quads that lie outside of the bounding region. These are definitely not in the interior.

Take the remaining non-shell quads. These may or may not be in the interior of the shape. For each of these quads, draw lines perpendicular to the quad from the center of each face that end on the surface of the bounding shape. Trace each line and count how many times the line crosses through the "connected face" of a quad in your shell list. If this number is odd, then that vertex lies in the interior of the shape. If it is even, the vertex is on the exterior. You can determine whether a quad is inside or outside based on whether its vertices are inside or outside.