We’ve been exploring region discovery from triangle soup (i.e. identifying volumetric regions enclosed by a set of triangles).
- The first route we pursued was the vtkDiscoverRegions filter, but it is too slow for large inputs — it is serial and expects conforming input. It works by assigning a unique “region ID” to each side of each input triangle and merging pairs of region IDs along shared edges. This is followed by a firing rays from representative triangles of each remaining region to perform additional merging of outer shell surfaces with interior void surfaces and discover containment/nesting relations among regions.
- The second route was a parallelized version of the discover-region algorithm that still expects conformal input (which we produced by splitting faces at pendant nodes as a preprocessing step) and divides cells into regions using an octree. The octree was to provide quick stabbing queries for the nesting step and for identifying volumes containing a seed point. Here we ran into issues because at least some of the input geometry is not conformal due to differences in triangulation scale and interpenetration of surfaces.
- Now we are considering a third approach that is an approximate algorithm (that is, it will not provide a guarantee that the detected regions are the complete set of volumes nor that the detected volumes are disjoint from one another). However it will not require the input geometry to be conformal. Instead, it will work by:
i. Building an octree whose nodes contain cells they bound,
ii. Assigning unique “region IDs” to each octree-node’s corner points (instead of to sides of triangles),
iii. Firing rays between corner-points of octree nodes and merging the corner-points’ region IDs if the ray hits no triangles that overlap the octree node. For octree nodes that contain child nodes, we would need to fire additional rays that connect those corner
What remains will be sets of (octree-node corner) points that are accessible to one another by traveling along edges of the octree nodes (an approximation of path-connected points inside each volume).
The third approach is illustrated by this figure:
You can see how it is possible that there may be regions not sampled by any octree-node corner. However, when the lines have smoothly-changing sizes, this should not happen frequently.