3D Solid Model Reconstruction

-> -> 

Thomas Funkhouser


Correct and consistent representations of three-dimensional objects are required by applications as varied as modeling, simulation, visualization, CAD/CAM, and finite element analysis. However, most acquired 3D models, whether created by hand or by using automatic tools, contain errors and inconsistencies. They contain wrongly-oriented, intersecting, or overlapping polygons, cracks, and T-junctions; polygons are missing; and topological information is inconsistent. Solid modeling information is rarely available. Rather, polygon soup seems to be the rule. Problems arise from many sources, including designer errors or software errors in the modeling tool. These errors can be compounded by specific data exchange problems: (i) automated transfer between CAD formats (eg, IGES, STEP, DXF, binary files from CATIA or autoCAD), between B-spline or NURBS-based formats, or (ii) geometric transformation into an engineering analysis system (eg, triangular surface mesh).
Currently, techniques to reconstruct manifold models from acquired 3D models are not very robust. Existing methods either require user-input, assume that the polygons in the input set are consistently oriented, assume that most polygons are orthogonal, or use scene-relative tolerances to ``fill over'' cracks in the model. Boundary-based approaches that try to infer solid structures from how input polygons mesh together are likely to perform incorrectly in the presence of non-manifold geometry. Other approaches based on merging features within some tolerance of each other do not work well when the size of errors are larger than the smallest feature in the model. In this case, no suitable tolerance can be chosen that both fills cracks and preserves small features.
We are developing a system that automatically reconstructs a consistent 3D solid model and boundary representation from an arbitrary set of polygons (polygon soup). The system partitions space into convex polyhedral regions separated by planes supporting the input polygons. Solid regions are identified by solving a linear system of equations derived from rules based on the opacities of boundaries between regions: 1) two adjacent cells sharing a mostly transparent boundary are likely to have the same solidities (i.e., if one is solid, then the other is too), 2) two adjacent cells sharing a mostly opaque boundary are likely to have opposite solidities (i.e., if one is solid, then the other is not), and 3) the unbounded cells (i.e., the ones on the outside that contain a point at infinity) are not solid. Once solid regions have been identified, the system can output consistent solid model and boundary representations without intersecting, coplanar, or unconnected polygons.
This is joint work with T.M. Murali.

Related Publications: