e-
ed
ng
or-
ls
ISPRS Commission III, Vol.34, Part 3A ,,Photogrammetric Computer Vision“, Graz, 2002
RECOGNITION AND RECONSTRUCTION OF SPECIAL SURFACES FROM POINT CLOUDS
Helmut Pottmann ?, Stefan Leopoldseder *, Johannes Wallner *, Martin Peternell b
2 Institute of Geometry, Vienna University of Technology, Wiedner Hauptstr. 8-10, A—1040 Wien, Austria -
(pottmann, leopoldseder, wallner)@geometrie.tuwien.ac.at
b Advanced Computer Vision GmbH, Wohllebengasse 6/5, A—1040 Wien, Austria - martin.peternell@arcs.ac.at
KEY WORDS: CAD, geometry, engineering, surface recognition, surface reconstruction, three-dimensional modeling.
ABSTRACT
Given a cloud of measurement points from the surface of a 3D object, we address the problem of recognizing and recon-
structing special surface types. We survey our work on this problem, which is based on approximation in the space of
lines and in the space of planes. Moreover, we discuss new generalizations which also use a recently developed technique
for parametric surface fitting with an active contour model.
1 INTRODUCTION
Modern 3D measurement devices (laser range scanners,
structured light based measurement, ...) produce a large
amount of 3D data of geometric objects. These data are
more or less structured point clouds. We have a variety of
methods for processing these clouds of points: triangula-
tion, mesh decimation (Garland Heckbert, 1997), reverse
engineering through surface fitting (Varady et al., 1998).
Together with rapid prototyping and 3D printing, we pos-
sess a complete chain for the emerging area of 3D technol-
ogy. For the essential steps such as data acquisition, CAD
model building, model modification and printing there are
already good solutions on the market.
Whereas the basic concepts and algorithms for 3D Vision
and Reverse Engineering of geometric objects are avail-
able, the degree of automation and intelligence in the sys-
tems still has to be increased. A reverse engineering sys-
tem should not just fit any surface to the data as long as it
is within tolerance. For several reasons including function-
ality and the choice of the right manufacturing tools, it is
important to recognize special shapes and build an accord-
ing CAD model (Varady et al., 1998).
In the present paper, we survey our recent progress on
the recognition and reconstruction of special surfaces from
point clouds. These surfaces are the basic shapes of any
CAD system (plane, sphere, cylinder and cone of revolu-
tion, torus) and more general surfaces with a simple kine-
matic generation. The latter surfaces are sweep surfaces
and include surfaces of revolution, helical surfaces, pipe
surfaces, developables surfaces, ruled surfaces and transla-
tional surfaces. The methodology combines results of clas-
sical geometry with techniques of geometric computing.
The main idea is to estimate surface normals (or equiv-
alently tangent planes) at the data points and then solve
certain approximation problems in the space of lines or the
space of planes, respectively.
We will first briefly introduce the basic geometric concepts
and then discuss their application to the recognition and re-
construction of special surfaces. Finally, we point to ongo-
ing research which also employs a type of 3D active con-
tours for surface approximation.
2 APPROXIMATION IN LINE SPACE: FITTING A
LINEAR COMPLEX TO A SET OF LINES
2. The linear line complex
Consider the motion of a rigid body in space. If x is a point
in Euclidean three-space, the symbol v(x) denotes the ve-
locity vector of that point of the moving body which is at
this moment at position x. Thus v(x) is a time-dependent
vector attached to the point x. It is well known that at some
instant t, a smooth motion has a velocity vector field of the
form
v(x) =C+ cx x, (1)
with vectors c, €, see e.g. (Bottema Roth, 1990). Thus the
velocity vector field (or the infinitesimal motion) at some
instant t is uniquely determined by the pair (e, c).
Of special interest are the uniform motions, whose veloc-
ity vector field is constant over time. It is well known
that apart from the trivial uniform motion, where nothing
moves at all and all velocities are zero, there are the fol-
lowing three cases:
1. Uniform translations have ¢ = o, but € Z o, i.e., all
velocity vectors equal €.
2. Uniform rotations with nonzero angular velocity
about a fixed axis. We have c - € — 0, but c Z o.
3. Uniform helical motions are the superposition of a
uniform rotation and a uniform translation parallel to
the rotation’s axis. They are characterized by ¢-¢ # 0.
If w is the angular velocity of the rotation, and v the
velocity of the translation, then p = v/w is called the
pitch of the helical motion. We use the convention
that w is nonnegative, that p > 0 for right-handed
helical motions, and that p « 0 for left-handed ones.
Formally, p = 0 means a uniform rotation and p = oo
is a translation.
All possible pairs (c, €) actually occur, so we can use these
three cases to classify the type of velocity vector field at
one instant of an arbitrary smooth motion: /nfinitesimal
translations are characterized by ¢ = o, and infinitesimal
A- 271
