3D Solid Model Reconstruction
->
-> 
Thomas Funkhouser
Overview:
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: