se 
ell 
5). 
nt 
ch 
58, 
re 
v 
oy 
VS 
3l 
ISPRS Commission III, Vol.34, Part 3A ,,Photogrammetric Computer Vision“, Graz, 2002 
  
Note that a developable surface is the envelope of a one- 
parameter family of planes. Given scattered data points, 
we may estimate tangent planes at data points and view 
them as points in dual space. Using a metric in the space 
of planes as discussed in section 3, we can fit a curve to the 
resulting point cloud and interpret it as dual model of an 
approximating developable surface (Peternell Pottmann, 
2001). 
4.4 Active contours for the reconstruction of ruled or 
translational surfaces 
An efficient approach to various approximation problems 
for curves and surfaces are active contour models, which 
are mainly used in Computer Vision and Image Processing. 
The origin of this technique is the seminal paper (Kass et 
al., 1988), where a variational formulation of parametric 
curves, called snakes, is presented for detecting contours in 
images. There are various other applications and a variety 
of extensions of the snake model (see e.g. (Blake Isard, 
1998, Malladi et al., 1995)). 
Recently we have developed an active contour type strat- 
egy for approximating a point cloud or a surface in any 
representation (^ model shape") by a B-spline surface or an- 
other surface type which can be written as linear combina- 
tion of bivariate basis functions (Pottmann Leopoldseder, 
2002). This technique is based on local quadratic approx- 
imants of the squared distance function to curves and sur- 
faces (Pottmann Hofer, 2002). There it is described how to 
compute for any point p € IR? such a local quadratic ap- 
proximant Fa,p. The surface approximation method pro- 
ceeds in the following steps: 
1. Initialize the active’ B-spline surface and determine 
the boundary conditions. This requires the computa- 
tion of an initial set of control points, the proper treat- 
ment of boundaries (e.g. by fixing vertices of a patch) 
and the avoidance of model shrinking during the fol- 
lowing steps. 
2. Repeatedly apply the following steps a.—c. until the 
approximation error or change in the approximation 
error falls below a user defined threshold: 
a. With the current control points, compute a set of 
points s, of the active surface, such that the shape 
of the active surface is well captured. For each of 
the points s;, determine a local quadratic approximant 
PF oT ps of the squared distance function to the 
model shape at the point s,. In an appropriate coordi- 
nate system, this has to be the graph of a nonnegative 
quadratic function, F#(x) > 0, Vx € R°. 
b. Compute displacement vectors for the control points 
by minimizing the functional 
N 
F 2 V FED) + MF, (11) 
k=1 
where s; denote the displaced surface points (which 
depend linearly on the unknown displacement vectors 
of the control points) and Fs denotes a smoothing 
functional which shall be quadratic in the unknown 
displacement vectors. Thus, our goal is to bring the 
new surface points s7 closer to the model shape than 
the old surface points sj. Since the points sj depend 
linearly on the unknown displacement vectors of the 
control points, both F E and F are quadratic in the un- 
knowns. 
We see that this step requires the minimization of a 
function F' which is quadratic in the displacement 
vectors of the control points. This amounts to the so- 
lution of a linear system of equations. 
c. With the displacement vectors from the previous step, 
update the control points of the active surface. 
An important advantage of the new technique is that it 
is not necessary to deal with the correspondence between 
points in the parameter domain and the data points. Thus 
problems where this correspondence is crucial can now be 
easier handled. 
One of these problems concerns the approximation of a 
given surface or point cloud by a ruled surface. Ruled sur- 
faces are interesting from various points of view (Pottmann 
Wallner, 2001). Because they carry a one-parameter fam- 
ily of straight lines, their use in architecture is much sim- 
pler than that of more general freeform shapes. They 
can be manufactured with wire EDM (Yang Lee, 1996), 
and the approximation with ruled surfaces also appears 
in the context of NC machining with a peripheral milling 
strategy and a cylindrical milling tool (Lee Koc, 1998). 
There is prior work on ruled surface approximation (Chen 
Pottmann, 1999, Hoschek Schwanecke, 1998, Pottmann 
Wallner, 2001). In the new surface approximation strategy 
we just have to use tensor product B-splines of bidegree 
(1,n) as active contours because these are ruled surfaces. 
Another application of the new approximation technique 
concerns the approximation of a given surface or point 
cloud by a translational surface. A translational surface 
x(u, v) is generated by a translatory motion of a curve c(u) 
along another curve d(v). Assuming that the two curves 
share a common point a = ¢(0) = d(0), the surface pa- 
rameterization is given by 
x(u,v) = c(u) + d(v) — a. (12) 
Translational surfaces are very well studied in classical ge- 
ometry. Because of the simple generation, they are used 
for various applications, e.g. in architecture. 
For the reconstruction of a translational surface from a 
point cloud, or the approximation of a given (not exactly 
translational) surface by a translational surface, the con- 
cepts of (Pottmann Leopoldseder, 2002) are again appli- 
cable. We note that a translational B-spline surface has 
control points which satisfy the constraints 
d;,; = dio + do,; — do,o- 
, 
A - 275