Detect hole in geometry

Question

I am working with a serialization pipeline. I am taking a model and exporting it. I do not wish to export any model with a hole in a face. How would I detect a hole and report a error?

I have access to all vertexes, edges, faces etc.

Here is a picture of what I mean.

As you can see there is a hole in the face. I am fairly new to geometry so please try to explain in layman terms.

Answer 1

If a 3D object is "simple", meaning that it doesn't have holes, it satisfies Euler's Formula for Polyhedra, V - E + F = 2 where V is the number of vertices in the figure, E is the number of edges, and F is the number of faces. If you can easily obtain those three numbers, you can calculate the formula V - E + F. If the result is not 2, the object has a hole (or some other pathology like a pinch). In fact, you can tell how many holes the object has by V - E + F: if the number is 0, it has one hole; if the number is -2, it has two holes; etc.

Calculating V, E, and F can be a little tricky because vertices are generally shared by two or more edges, and edges are generally shared by two faces. You don't want to overcount; if three edges meet in a single vertex, you only want to count the vertex once, not three times.

Not only that, but it's easy to make a mistake counting when the shapes have holes (which is exactly the case you're interested in). The easiest way to avoid making a mistake is to break the figure up into convex parts with e.g., triangulation.

The formula doesn't tell you which face has the hole, but if you know that the figure has a hole you can apply Euler's formula to each face individually, again with triangulation. In that case, faces without holes will have V - E + F = 1 where V,E,F are now restricted to the face in question. (the discrepancy with the previous formula is resolved if you count the region outside the face as another (infinite) face). Faces with holes will have V - E + F < 1.

For example, a triangle on the plane has V=3, E=3, and F=1 (the "face" of the triangle represented by its interior) giving V-E+F=1. On the other hand, a triangle with a similarly shaped triangular hole inside, in which corresponding vertices of inner and outer triangles are connected, will have V=6, E=9, and F=3 for V-E+F=0. I have broken the figure into three convex quadrilaterals in this case.

Most books on computer graphics have a discussion of this topic.

Answer 2

If I understand correctly, you want to detect polygons with holes. Now how polygons with holes are represented can vary with each software (some store separate internal contour lists). However, a common representation in 3D packages (including formats like OBJ) use a flat face vertices representation which tends to look like this:

... where 2,6 and 1,7 would be the same vertex index stored twice in the same polygon (the numbers in the picture indicate face point indices). Note that this edge from 1,7 to 2,6 could be hidden in some software, but it's there even if it's not visible if the software stores polygon vertices in a flat list of indices/pointers.

So a quick way to tell if a polygon has a hole with such representations given only face data (ex: from an OBJ file) is to see if it has duplicate entries for the vertex indices. If the same vertex index is repeated more than one time in a polygon, then it has a hole.

Now there is a case where you can find duplicated vertices for an empty inner contour, like so:

... where 2,4 are welded (same vertex). If you want to distinguish these cases, you can detect them when the edge connecting exterior contour to interior contour only has one vertex duplicated instead of two. In that case, the interior contour is empty and this polygon is just a funky one (perhaps created through a CSG/plane slicing operation).

If you want a really robust solution, it's worth writing a routine that "unflattens" these flat contour lists into multiple interior/exterior groups by splitting the list apart where the duplicate edges connecting one contour to another are found. If the interior groups have fewer than 3 vertices, then they're probably just funky polygons without a visually noticeable hole. If they have 3 or more, then they meet the criteria required to show a hole which you can see visually. In cases where the interior contours don't form a full-fledged hole, you can just toss the interior contour and keep the exterior contour (in which case it's like just keeping the 3-point triangle exterior in the above pic while tossing out those redundant vertices, kind of cleaning up the geometry in the process and giving you the triangle formed from {1, 2/4, 5}).

A simple solution you can apply if you don't mind exporting unwelded geometry as long as it isn't funky (no holes or interior contours) is to simply clone (make unique) vertices that are duplicates in a polygon, basically unwelding it, like so:

That's a little easier than a full-blown tessellation kind of solution, and it still ends up giving you polygons without any holes or separate interiors. I visually moved 2 and 4 apart for the sake of demonstration to emphasize that they're now separate vertices, but you don't have to do that (they can be coincident).

This kind of unwelding technique is also useful if you have a tessellator that doesn't support holes. You can apply this technique to unweld the polygon, tessellate it, then weld/merge back coincident vertices to give you the final result.