|
A common problem in Reverse Engineering is that of creating a
computer model from an existing part. The part might be scanned with
a device like the laser range scanner, or points might be measured
on its surface via a mechanical probe. Sometimes, not only the
spatial location of points, but also some associated physical
property can be measured.
The problem of reconstructing from this data a topologically
consistent and geometrically accurate model of the object and of the
sampled physical property is the subject of this research.
An example of reconstruction is shown in the three images
above. The left image shows a set of 10,000 data points sampled form
the head of Spock [data courtesy of Cyberware. The original data
contained approximately 100,000 points obtained with a Cyberware Laser
Range Scanner]. The center image shows the reconstructed object. The
object surface is represented with a derivative (C1)
continuous collection of implicit polynomial patches, visible in the
right image.
  
The algorithm used for the example above is described in
C. Bajaj, F. Bernardini, and G. Xu.
Automatic reconstruction of surfaces and scalar fields from 3D scans.
Computer Graphics Proceedings, Annual Conference Series. Proceedings of SIGGRAPH 95,
pages 109-118. ACM SIGGRAPH,1995.
( pdf)
( ps.gz)
This method can deal with connected, orientable manifolds of
unrestricted topological type, given a sufficiently dense and uniform
sampling of the objects surface. It is capable of reconstructing both
the model and a scalar field over its surface. It uses regular
triangulations, power diagrams and weighted alpha-shapes for
efficiency of computation and theoretical soundness. It generates a
representation of the surface and the field based on barycentric
Bernstein-Bèzier polynomial implicit patches, that are guaranteed to
be smooth and single-sheeted.
A formal proof of sufficient conditions on the sampling to guarantee a
homeomorphic, error-bounded reconstruction appears in:
C. Bajaj, F. Bernardini, and G. Xu.,
``Reconstruction of Surfaces and Surfaces-on-Surfaces from Unorganized
Weighted Points''
Algorithmica, 19, (1997), 243-261.
(pdf)
Here's another example of a reconstructed object's surface from a
dense cloud of unorganized points. The data is from a set of
laser range scans (Courtesy of Stanford University Computer
Graphics Laboratory). Our method automatically selects an
optimal alpha shape and improves it in areas of insufficient
sampling density. Form left to right: points, alpha shape,
improved shape, a Phong rendering of the reconstruction.
 
 
Sometimes the values of a scalar fields are also known at the data
points. For example, A Cyberware Laser Range Scanner returns values
for the RGB components of the color at the samples points. Another
example might be an experiment in a wind-tunnel, in which the pressure
or temperature on the surface of a jet-engine is measured at several
locations. The pictures below show an example of a reconstructed
jet-engine and associated scalar field (in this case, pressure values
from a simulation). The data in this case has been generated in a
simulation and looks quite structured. The algorithm used in the
reconstruction howerever makes no assumptions on the structure of the
sampling. The points are treated as randomly scattered on the surface
of the object. The algorithm used in this example uses tensor-product
Bernstein-Bèzier polynomial implicit patches, and is based on an
adaptive, octree-like subdivision. For more details see
C. Bajaj, F. Bernardini, G. Xu
Adaptive Reconstruction of Surfaces and Scalar Fields from Dense Scattered Trivariate
Data
Technical Report 95-028, Purdue University, Computer Sciences
(1995)
(ps.gz)
(pdf)
The following pictures show the original data points, the
reconstructed object, the collection of surface patches and the
reconstructed scalar field. The field is visualized as a surface
(semi-transparent in the picture. The lines are isocontours of the
field) using the normal-projection method.
 
 
We have also developed an algorithm better suited to reconstruct
objects with sharp features, such as those of interest to Computer
Aided Design and Manufacturing. The algorithm is described in
F. Bernardini, C. Bajaj, J. Chen and D. Schikore. ``Automatic
Reconstruction of 3D CAD Models from Digital Scans''
Technical Report CSD-97-012, Department of Computer
Sciences, Purdue University, 1997. Submitted for
publication.
This algorithm is based on a three-step approach: We first extract a
fine triangle mesh from the data points. We then decimate the mesh,
while keeping the approximation error bounded. Finally, we fit degree
three A-patches to the reduced mesh. Sharp edges, curvilinear creases
and corners are automatically detected and reproduced in the final
surface.
The pictures below show various steps in the reconstruction algorithm:
   
   
The Surface Reconstruction Toolkit is based on X11/Motif for the
Graphical User Interface, and on OpenGL/Open Inventor for the
visualization of surfaces. It allows interaction with a set of
functionalities for reconstructing the surfaces and an associated
scalar field from scattered data. The user can select the method to be
used for preprocessing the data and for constructing a piecewise
polynomial approximation, the degree of the polynomials, and the upper
bound to the approximation error. The incremental approximation
process can be shown as a sequence of pictures (like the one shown in
the picture below), and saved in a movie
file.
|
