I have a finite region of 3D space that some (arbitrarily-shaped, concave) geometry occupies, and I need to identify whether that geometry forms a closed 3D volume (or multiple disjoint closed 3D volumes). That is, I need to identify if, and where, the geometry isn’t airtight. The geometry is, effectively, a series of one or more rooms (that are ideally closed).

My current strategy is, in a nutshell, to define a valid and invalid area of the entire 3D space, then identify whether there are any paths from the valid area to the invalid area.

To do this, I first find an AABB of the total geometry, double the extents of that AABB, and use the result as the root of an octree. Upon splitting twice, the resulting octree has a “shell” of octants that enclose the geometry, but are themselves empty. The geometry occupies the gooey, nougat center of the octree (the innermost 8 octants at subdivision level 2). After fully finding the leaf nodes of this octree, I run a connected component labelling algorithm to find connected components containing both shell, non-intersecting leaf nodes and nougat non-intersecting leaf nodes. If any connected components contain such a mix, the geometry is reported as having a leak.

This approach, however, reports false positives; all the negative space surrounding the (concave) geometry is filled with non-intersecting leaf nodes that don’t have any notion of being outside the geometry, but are still within the nougat of the tree and, consequently, result in the detection of a leak. I need to define whether an octree node should be contained within a volume bounded by intersecting leaf nodes, and whether it is bounded by intersecting leaf nodes. If there is a discrepancy between the two, I’ve not only found a leak, but the location of that leak.

I have one idea for proceeding, which is to create an alpha shape/complex to create a volume out of the intersecting leaf nodes while “closing up” holes, create another alpha shape constructed with an alpha of 0 (that is, with any holes preserved), then query both of these shapes with every non-intersecting leaf node to find the node’s containment status and note discrepancies between the alpha shapes. I can already see that this approach will, with the variation of the alpha value, erroneously capture certain non-intersecting leaf nodes and mark them as should be inside, and it will also fail to detect leaks that are of a size greater than the alpha value because these holes will not be closed up.


1 Answer 1


A mesh is airtight if every edge belongs to exactly two faces. It is a purely topological test.

But life can be made harder with multiple vertices having the same coordinates, degenerate faces where edges have been merged, self-intersecting surfaces...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.