[PDF] Fitting curves and surfaces to point clouds in the presence of obstacles

106670_6FloryS_,Fittingcurvesandsurfacestopointcloud.pdf

Fitting curves and surfaces to point clouds in

the presence of obstacles

Simon Fl¨ory

Institute of Discrete Mathematics and Geometry, Vienna University ofTechnology,

Wiedner Hauptstraße 8-10, A-1040 Wien, Austria

Abstract

We consider the problem of fitting B-spline curves and surfaces to point clouds on taking real world obstacles into account at the same time. Therefor, we describe the fitting problem as optimization problem and employ an iterative procedure to solve it. The presence of obstacles poses constraints on this minimization process. We examine two families of obstacles: first, the point cloud itself is interpreted as obstacle, e.g. to approximate the data points" boundaries. Second, we define arbitrary regions the fitting must not penetrate. All constrained approximations are depicted for B-spline curves as well as for surfaces. Key words:Curve fitting, Surface fitting, Obstacles, Constrained optimization,

Surface trimming

1 Introduction

The wide spread of 3D laser scanning technology offers various possibilities to digitize real world objects and further process their virtual models on com- puters. One of the most common representation methods for the acquired measurement data is to store a high number of surface sample coordinates, often denoted to as thepoint cloud. Data processing knows an ever increasing number of ways to deal with such a discrete point set: noise removal, triangulation or registration to name only a few. A topic of special interest is to reduce the amount of information rep- resented by the numerous elements of such a data set and smooth thepoint cloud at the same time. For this purpose, a curve or surface isfittedto the Email address:floery@geometrie.tuwien.ac.at(Simon Fl¨ory). Preprint submitted to Elsevier Science 29 June 2006 point set and used to represent the measurement data henceforth.Less sur- prisingly, both curve and surface fitting are closely related and build upon the same basic considerations. Curve and surface fitting don"t state further what kind of fitting entity is employed. Due to their universality, free-form curves and surfaces are a popular choice and we focus on fittings with B-spline curves and surfaces below.

1.1 Related Work

Piecewise parametric functions have been used in curve fittingof point clouds for a long time. In one of the first works on this topic, (Cox, 1971) uses least squares, an error metric still popular today, to fit scattered data. A major challenge in curve fitting, if compared to a univariate function approximation, is to define those samples on the fitting entity the approximation error is measured in. If the data points are ordered, the chordal length method or the centripetal method (see e.g. (Hoschek and Lasser, 1993)) could be used forparametrization. (Hoschek, 1988) tackles the problem of unordered data with an iterative method of intrinsic parametrization and approximates the foot point computation by a first order term. Approximations ofhigher order (Hu and Wallner, 2005; Saux and Daniel, 2003) or an accurate foot point computation (Hoschek and Lasser, 1993) in each step are subject of discussion as well. In these foot points, the distance function of the curve is approximated. The most popular technique computes the squared distance from the data points to the foot points (Goshtasby, 2000; Hoschek, 1988; Plass and Stone, 1983). (Blake and Isard, 1998) improves these approaches by means of convergence rate and utilizes the squared distance from the data point to the tangent plane in the foot point as error term. Recently, (Wang et al., 2005)gave an thorough overview of existing curve fitting methods and described an algorithm based on a second order approximation of the squared distance function to solve the curve fitting problem. We will discuss this approach in more detail later. The problem of surface fitting has been addressed for years as well (see e.g. (Hayes and Halliday, 1974)) and has drawn a certain amount of attention in recent years. (Dierckx, 1993) give a comprehensive overview of curve and sur- face fitting techniques (scattered data fitting, mesh fitting and data smooth- ing) and is a good starting point for references to the older literature. (Dietz,

1995) extend the existing least squares approximations and discuss the use of

additional smoothing and regularization terms. (Greiner andHormann, 1996) consider the surface reconstruction with hierarchical tensor product B-spline surfaces and (Diebel et al., 2006) apply a Bayesian method for probable sur- 2 face reconstruction. The literature on this topic is extensive and we want to round up the review and refer to two recent publications (Wang et al., 2005;

Weiss et al., 2002) and the references therein.

Constrained curve or surface design is a widely investigated topic in com- puter aided geometric design. Often, constraints are imposed to increase the quality of the solution, simplify the obtained fitting (Rogers,1989), or en- sure certain geometric properties of the final approximation(Benk´o et al.,

2002; Bercovier and Jacobi, 1994). A detailed survey of constrained methods

in reverse engineering is given in (Fisher, 2004) and (V´arady and Martin,

2002). Besides these theoretical constraints, side conditions have been derived

from real world obstacles as well. (Myles and Peters, 2005) construct splines of prescribed smoothness obliged to stay in a channel with piecewise linear boundaries. In (Liu et al., 2005), a combination of surface fitting and regis- tration based on a squared distance minimization algorithm is discussed and applied to a constrained reverse engineering of CAD models. Moreover, it is a common problem in motion planning to deal with obstacles, see (Latombe,

1991).

1.2 Overview

The remaining parts of this work are organized as follows. After this introduc- tion and review of recent literature, we describe an efficient fitting algorithm by (Wang et al., 2005). We show how to formulate the curve fitting problem as optimization problem and generalize our discussion to surface fittings. We introduce real world obstacles to the reconstruction problemby first interpret- ing the point cloud itself as constraint. Second, we consider arbitrary regions of the embedding space a final solution must not penetrate. We conclude our discussion of curve and surface fitting in the presence of obstacleswith the presentation of a handful of results.

2 Unconstrained curve and surface fitting

Curve and surface fitting are closely related tasks. For this reason, we are going to define and discuss the curve fitting problem first and show how to generalize it to surface reconstructions later on. In the course of the subsequent discussion, we describe a general algorithm to solve the fitting problem and review a recent realization. 3

2.1 The curve fitting problemLetP={pk?R2:k= 1,...,n}be the point cloud under consideration and

letx(u) denote a parametric approximating curve, such as a B-spline curve. Assuming that knots and degree of this B-spline curve are fixed, wewrite x(u) =m? i=1N i(u)di,(1) whereNi(u) are the B-spline basis functions anddi?R2the control points. Fitting a curve to a point cloud means looking for a new position x c(u) =m ? i=1N i(u)(di+ci) (2) ofx(u) approximating the data points in a better way. For convenience, we summarize the displacementsciinto a single displacement vectorc.

2.2 Squared distance minimization algorithm for curve fitting

The single steps towards a solution of the curve fitting problem can be sum- marized in a general curve fitting algorithm. We call itgeneralas it doesn"t make any assumptions on the way the current fitting error is approximated.

The algorithm involves the following steps.

(1) Define a suitable initial position for the approximating B-spline curve x(u). (2) Assign each data pointpka parameter valueuksuch thatx(uk) is the closest point ofpkonx(u). (3) Describe the current fitting error in these foot pointsx(uk). (4) Compute the displacementscof the fitting curve by minimizing this approximation error. (5) Update the position of the approximating curve. If the fitting is of satis- factory quality (e.g. change of gradient below a certain threshold), stop.

Otherwise, continue at step 2.

Several error metrics have been proposed for a realization ofstep 3. Here, we want to describe the squared distance minimization error term by (Wang et al., 2005) which combines stability and good convergence speed of previous methods. Let (tk,nk) be the local Frenet frame in a foot pointfk=xc(uk) of a data pointpkon the approximating curvexc(u). Moreover,dk=?fk-pk? is the Euclidean distance fromfktopkandρk= 1/κkdenotes the inverse curvature ofxc(u) infk. We definedkto be negative ifpkand the curvature 4 (0,ρk) fkfkfkfkfkfkfkfkfkfkfkfkfkfkfkfkfk pkpkpkpkpkpkpkpkpkpkpkpkpkpkpkpkpkn k tktktktktktktktktktktktktktktktktk x(u)fkfkfkfkfkfkfkfkfkfkfkfkfkfkfkfkfk pkpkpkpkpkpkpkpkpkpkpkpkpkpkpkpkpkn k tktktktktktktktktktktktktktktktktk x c(u) Fig. 1. Fordk>0, the level sets of the squared distance minimization error term Q C kform ellipses (left). During a single iteration, the foot pointfkand thustkand n kremain fixed (right). center (0,ρk) are located on the same side of the curve and positive otherwise. Then, based on a second order Taylor approximation of the squared distance function, Q C k(c) =dk dk-ρk[(xc(uk)-pk)T·tk]2+ [(xc(uk)-pk)T·nk]2(3) measures the fitting error infk. We restrict Equ. (3) to the case 0< dkas we are in need of a positive definite function to take advantage ofthe theory of convex optimization. Forρk≤dk≤0, we omit the first summand Q C k(c) = [(xc(uk)-pk)T·nk]2(4) and approximate the squared distance function with the squareddistance to the tangent infk. A major characteristic of equations (3) and (4) is that they arequadraticin the unknown displacementscofxc(u). Thus, f(c) =n ? k=1QCk(c) (5) forms the objective function of a quadratic optimization problem and a so- lution is obtained by solving a system of linear equations. Another aspect of the minimization of Equ. (5) is that an optimal solution must not necessarily mean a visually pleasing solution. Indeed, simply minimizing Equ. (5) yields a degenerated and oscillating reconstruction. Therefore, a regularization or smoothing term is added. A popular choice is to use a simplified measure for the bending energy f(c) =n ? k=1QCk(c) +ws·? ?x??c(u)?2du,(6) which makes the objective function remain quadratic inc. 5

2.3 Squared distance minimization algorithm for surface fitting

The framework of the preceding section may be applied to surface fittings straight forward. Given a point cloudP={pk?R3:k= 1,...,n}the task is now to fit a parametric surfacex(u,v) best ontoP. It is a well known fact that the concept of B-spline curves can be extended to surfacesby a tensor product construct. We summarize the products of the B-spline basis functions into a single term, order the control pointsdij?R3in sequence and write x c(u,v) =m ? i=1?Ni(u,v)(di+ci) (7) for the displaced B-spline surface. A quadratic Taylor approximation of the squared distance function from a point to a surface is derived in (Liu et al., 2005) analog to curves. Let (n0,k,n1,k,n2,k) denote a local coordinate frame in a foot pointfk=xc(uk,vk), wheren0,kand n

1,kare the two principal curvature directions andn2,kthe unit surface nor-

mal. Moreover,dkis the distance fromfktopkandρi,k= 1/κi,k,i= 0,1, the inverse principal curvatures forn0,kandn1,k. Then, Q S k(c) =1 ? i=0d k dk-ρi,k[(xc(uk,vk)-pk)T·ni,k]2+[(xc(uk,vk)-pk)T·n2,k]2(8) yields a squared distance minimization error term for surface fitting, whereas we reduce to the squared tangent plane distance Q S k(c) = [(xc(uk,vk)-pk)T·n2,k]2(9) in the foot point again ifρi,k≤dk≤0 holds fori= 0 ori= 1 to obtain a positive definite quadratic form. Finally, we choose the approximating thin plate energy f(c) =n ? k=1QSk(c) +ws·?? ?x2uu(u,v) + 2x2uv(u,v) +x2vv(u,v)?2dudv(10) as smoothing term for surface reconstruction. In summary, surface fitting of point clouds means iterative minimization of an objective function quadratic in the unknown displacements of the control points again. 6

3 ObstaclesCurve and surface fitting so far simply headed for that final position of the

fitting entity approximating the elements of the point cloudbest (by means of a least squares minimization). However, one might be interested in recon- structing features of the discrete point set data different fromthis balance in residues, such as the borders of the point cloud under consideration. Moreover, the fitting in the preceding section was allowed to happen everywhere in the plane or space respectively. Indeed, a priori knowledge aboutthe solution or missing input data could restrict a final fitting to only a subset of the plane or space. These challenges are addressed by examining fittings in the presence of obsta- cles. On the one hand, we interpret the input point cloud itselfas obstacle and approximate its outer - and if it exists - inner border. On the other hand, we define arbitrary shaped subsets ofRd,d= 2,3, the final solution is obliged to avoid. As before, we focus our main discussion on curve fittings. The results, as will be shown, can be applied to surface fittings directly. As pointed out in Sec. 2, curve and surface fittings describe an optimization problem quadratic in its unknowns. Obstacles will introduce constraints to the minimization process and we will face aconstrainedoptimization problem.

3.1 Point clouds as obstacles

At first we regard the subject of discussion, the point cloud itself,as obstacle. By choosing appropriate linear constraints we aim at reconstructing the inner or outer border of the shape represented by the data points. Letxc(u) be the approximating B-spline curve. We compute the foot points f k=xc(uk) of the shortest distance from each data pointpkto the curve and orient the normalsnkin these samples such that they point outside. Then, (pk-xc(uk))T·nk≤0k= 1,...,n(11) restricts the fitting curve to approximate the extent or outerborder ofP. Equ. (11) requirespkto stay on the opposite side of the tangent inxc(uk) n kis pointing to. In order to stabilize the fitting, we might reduce the set of constraints to only that subset of data points within a certain distance to x c(u) 7 fkp kt k n k x c(u) Fig. 2. If we regard the point cloud as obstacle, any data pointpkis required to be located on the opposite side the normalnkis pointing to. If we apply the constraints of Equ. (11) to the objective function of Equ. (6) minimizef(c) =n ? k=1QCk(c) +ws·? ?x??c(u)?2du subject to (pk-xc(uk))T·nk≤0k= 1,...,n(12) we obtain a quadratic programming problem with linear constraints. Quadratic programming, as one of the closest related problems to linear programming, has received a certain amount of attention ever since. Considering that the dimension ofcin Equ. (12) is only two or three times the number of con- trol points ofxc(u) this optimization problem is rather small scaled from the viewpoint of optimization. However, the number of constraints may equal the possibly big number of elements in the point cloud. Therefore it might be favorable to solve the dual problem as it reduces the complexity of the con- straints while increasing the dimension of the problem at the same time. If we write the primal quadratic program of Equ. (12) in a moregeneral form, minimize 1

2xTHx+tTxH?R3m×3m,x,t?R3m

subject toAx-b≤0A?Rn×3m,b?Rn,(13) its Lagrange function is given by

L(x,λ) =1

2xTHx+tTx+λT(Ax-b)λ?Rn.(14)

The dual problem, defined as finding the maximum of the dual function q(λ) := infx?R3mL(x,λ) =-1

2λTQλ-qTλ-12tTH-1t(15)

(withQ=AH-1ATandq= (AH-1t+b)), is yet another quadratic program maximize-1

2λTQλ-qTλ

subject toλ≥0.(16) As for our optimization task strong duality holds, we focus on thedual prob- lem. 8 fOkfOkfOkfOkfOkfOkfOkfOkfOkfOkfOkfOkfOkfOkfOkfOkfOk Pn O kx c(u)sk Fig. 3. For any sample pointskwithin a certain distance (light shaded) to an obstacle (dark shaded), foot pointfOkand normalnOkare computed. The methods to solve linear constrained quadratic programs can be classified into two categories (see e.g. (Nocedal and Wright, 1999)). Active set methods have been the most important technique for a long time. They deal with the constraints by estimating and continuously updating a set of currently active side conditions. The generalization of interior point methods to quadratic pro- grams, which in contrast avoid the boundary of the feasible region, provided a second powerful method for the solution of quadratic programs.While active set methods are better suited for smaller scaled problems, interior point meth- ods are widely used for larger scaled optimization tasks. For these reasons, we decided in favor of an active set method (e.g. (Goldfarb and Idnani, 1982)) to solve the dual problem of Equ. (16).

3.2 General obstacles

Going a step further, we define regions the final fitting is not allowed to pen- etrate. We do not impose any further requirements on these obstacles others than we are able to determine a foot pointfOkon the obstacle"s boundary for anyp?R2and there exists an outward oriented normalnOkinfOk. Accord- ingly, the obstacles may be discrete point sets with normal information for each element or smooth bounded subsets ofR2. For a curve fitting in the presence of general obstacles, we first obtain samples s k=xc(uk) on the approximating B-spline curvexc(u). For anyskin distance to an obstacle below a certain threshold?d, the foot pointfOkand normalnOkinfOkare determined. Then, (fOk-xc(uk))T·nOk≤0?k:?sk-fOk? ≤?d(17) are suitable linear constraints to perform a curve fitting avoiding any general obstacles. If we add the constraints of Equ. (17) to Equ. (6), we get the 9 Fig. 4. Reconstruction of a point cloud"s boundary: initialsetup (left) and final approximations after 10 iterations (right). quadratic program with linear constraints minimizef(c) =n ? k=1QCk(c) +ws·? ?x??c(u)?2du subject to (fOk-xc(uk))T·nOk≤0?k:?sk-fOk? ≤?d(18) we solve with the methods described before. For stability reasons it will turn out to be advantageous to perform some unconstrained iterations first before any linear constraints are considered.

4 Results

We want to illustrate curve and surface fittings of point cloudsin the presence of obstacles with several examples. In the first part, we are goingto present curve fittings of artificial data in an abstract problem definition whereas we get more application specific in the second section where we consider surface fittings.

4.1 Curve fitting

The target point clouds throughout this section were createdby randomly sampling a user defined auxiliary B-spline curve and adding some Gaussian noise. The first example in Fig. 4 visualizes the reconstruction of such a point cloud"s boundaries. For this purpose, each element of the dataset itself poses a side condition in the optimization process of the curve fitting algorithm. In a first run, the constraints of Equ. (11) are applied to approximate the outer border of the point set. In a second fitting, the less or equal sign in these side 10 Fig. 5. Fitting a cubic B-spline curve to a point cloud in the presence of four gen- eral obstacles. For three different initial setups (top row), the corresponding final approximations after 25 iterations (bottom row) are shown. conditions was replaced (pk-xc(uk))T·nk≥0k= 1,...,n(19) to reconstruct the inner border while keeping the initial position and orien- tation of the curve"s normals the same. Finally, both approximations were summarized in a single plot. The smoothing weightwswas set to 0.0001 for the first iteration and halved at every succeeding step. The point cloud counted

500 elements and was approximated with a closed cubic B-splinecurve with

14 control points. The final result was achieved after 10 iterations for each

boundary. The second problem in Fig. 5 shows a curve fitting of point cloudsin the pres- ence of four smooth bounded obstacles. In a preprocessing step, an approxi- mated distance field from the obstacles" borders was computed ona uniform grid with a sweeping algorithm (Tsai, 2002). In each iteration, the distance values on this discretization were used to select a subset of samplepoints s k?xc(u) close to a forbidden region. For each selectedsk, a linear constraint as described in Equ. (17) was applied. Compared to the previous example, the point cloud was sparser and counted only 200 data points. Thefitting closed cubic B-spline curve is defined with 16 control points. The curve fit- ting was performed for three different initial positions of the approximating B-spline curve. The final approximations were achieved after25 overall itera- tions whereas the obstacles were ignored during the first 10 steps to stabilize the solution. The control polygons of the B-spline curves are depicted as dotted lines in the plots. For all three setups, the results are of comparable quality; the fittings are successful for a wide range of different initial positions. The regularization factorwswas set to 0.0005 and halved at each iteration step, 11 Fig. 6. Surface fitting of a point cloud under consideration of three general obstacles. The top row shows the initial setup without (left) and with (right) approximating B-spline surface. The bottom row visualizes the approximation after three iterations (left) and the trimmed final fitting after 10 iterations (right). too.

4.2 Surface fitting

The first example for a constrained surface fitting of point clouds is illustrated in Fig. 6. The point cloud represents a fragment surface of a broken statue that was digitized with a 3D laser scanner. We place three geometricprimitives (a sphere, a cylinder and a cube) close to the data set and ask for a B-spline surface reconstruction avoiding these objects. For this purpose, we first fit a plane to the point cloud and define the ini- tial position of the control points on a rectangular grid thereon. In order to prevent a shrinking of the approximating surface, we let it overlap the data set significantly and fix the outer frame of control points in thesubsequent optimization. Then, we employ the algorithm of Sec. 3.2 to compute a surface fitting not penetrating the obstacles. For a proper visualization, we trim the fitting B-spline surfaceto the extent 12

00.20.40.60.810

0.2 0.4 0.6 0.8 1 u v Fig. 7. Approximation of the parameters" boundary in (u,v) space for surface trim- ming. of the point cloud. Therefor, we determine the foot points ofthe point cloud"s elements on the final surface and consider the corresponding parameters in the (u,v) parameter space. There, the parameters form a point cloud themselves and the outer border of this point cloud is a good estimate for the boundary of the trimmed surface. Thus, we approximate the extent of the parameters with a B-spline curve (see Sec. 3.1) and let the resulting fitting curve define the boundary of parameters contributing to the trimmed surface.Fig. 6 visualizes the final result of the constrained, trimmed surface fitting and Fig. 7 shows the rough approximation of the parameters. The approximating B-spline surface counted 17×21 control points. The fitting was smoothed by a regularization factor ofws= 0.01 (halved at each step) and was accomplished after 10 iterations. In a second example, we want to illustrate the surface approximation of a point cloud"s outer boundary. Within this context, we are going to address a common problem in engineering. Consider the mechanical parts of an operat- ing machine, thus exposed to vibrations. If we are in need of a hull for such an object, we have to take into account all possible positions and wrap them with a surface. For our example, we use the CAD model of a pipe (see Fig. 8) and sample its surface in 2800 points. Then, we simulate the shaking of operation by applying some random translations to this point cloud, whereas translations in positive direction of two coordinate axis may be observed more frequently. We summarize the relocated data points into a single point set and compute an approximation of its outer boundary. The B-spline surface is closed with respect to one parameter and counted

15×22 control points. The final approximation was achieved after10 iterations.

The result was trimmed again, though the parameter domain ranges from 0 13 Fig. 8. Approximation of a point cloud"s outer boundary inR3with a B-spline sur- face: a CAD model (top left) is sampled and shaked (top right). The approximation after three iterations (bottom left) and the final result after 10 iterations (bottom right) are shown. to 1 in the closed parameter direction anyway and was bounded by lines in the other direction.wswas set to 0.01 as in the previous example and halved at each iteration step.

5 Conclusions and future research

We presented an algorithm for fitting curves and surfaces to point clouds in the presence of obstacles. We described the fitting problem as quadratic minimiza- tion problem and enhanced this setup in the following with linear constraints to take obstacles into account. We approximated the boundaries of a point cloud and computed a curve or surface fitting avoiding generalobstacles. Fi- nally, we illustrated our theoretical work with a handful of examples. The consideration of obstacles is of interest for various fieldsof geometric optimization. Especially constrained registration, meaninga registration of two or more point clouds without mutual penetration, is a topic this work will be extended to. Likewise, the error term describing the approximation 14 error will be focus of future work. Replacing the least squaresminimization by a fitting in theL1norm increases robustness whereas a more thorough examination of the error in the data acquiring step (3D laser scanning) should improve the quality of the final fitting significantly.

Acknowledgements

I would like to thank Helmut Pottmann for his valuable comments and sugges- tions throughout the development of this work. This researchwas supported by the Austrian Science Fund (FWF) as part of the project P16002-N05.

References

Benk´o, P., K´osa, G., V´arady, T., Andorb, L., Martin, R., 2002. Constrained fitting in reverse engineering. Comput. Aided Geom. Des. 19 (3),173-205. Bercovier, M., Jacobi, A., 1994. Minimization, constraints and composite B´ezier curves. Comput. Aided Geom. Des. 11 (5), 533-563. Blake, A., Isard, M., 1998. Active Contours: The Application of Techniques from Graphics, Vision, Control Theory and Statistics to Visual Tracking of Shapes in Motion. Springer-Verlag New York, Inc., Secaucus, NJ, USA. Cox, M. G., 1971. Curve fitting with piecewise polynomials. IMAJ Appl Math

8 (1), 36-52.

Diebel, J. R., Thrun, S., Br¨unig, M., 2006. A Bayesian methodfor probable surface reconstruction and decimation. ACM Trans. Graph. 25 (1), 39-59. Dierckx, P., 1993. Curve and surface fitting with splines. Oxford University

Press, Inc., New York, NY, USA.

Dietz, U., February 1995. Erzeugung glatter Fl¨achen aus Meßpunkten. Tech. Rep. 1717, Preprint Series, Department of Mathematics, Darmstadt TU. Fisher, R. B., 2004. Applying knowledge to reverse engineeringproblems.

Computer-Aided Design 36 (6), 501-510.

Goldfarb, D., Idnani, A., 1982. Dual and primal-dual methodsfor solving strictly convex quadratic programs. In: Numerical Analysis, Proceedings, Cocoyoc, Mexico 1981. Springer-Verlag, Berlin, pp. 226-239. Goshtasby, A. A., 2000. Grouping and parameterizing irregularly spaced points for curve fitting. ACM Trans. Graph. 19 (3), 185-203. Greiner, G., Hormann, K., 1996. Interpolating and approximating scattered

3D-data with hierarchical tensor product splines. In: Mehaute, A. L., Rabut,

C., Schumaker, L. L. (Eds.), Surface Fitting and Multiresolutional Methods.

Vanderbilt University Press, pp. 163-172.

Hayes, J. G., Halliday, J., 1974. The least-squares fitting of cubic spline sur- faces to general data sets. IMA J Appl Math 14 (1), 89-103. 15 Hoschek, J., 1988. Intrinsic parametrization for approximation. Comput.

Aided Geom. Des. 5 (1), 27-31.

Hoschek, J., Lasser, D., 1993. Fundamentals of Computer Aided Geometric

Design. AK Peters.

Hu, S.-M., Wallner, J., 2005. A second order algorithm for orthogonal projec- tion onto curves and surfaces. Comput. Aided Geom. Des. 22 (3), 251-260. Latombe, J.-C., 1991. Robot Motion Planning. Kluwer Academic Publishers,

Norwell, MA, USA.

Liu, Y., Pottmann, H., Wang, W., August 2005. Constrained 3D shape recon- struction using a combination of surface fitting and registration. Tech. Rep.

144, Geometry Preprint Series, Vienna Univ. of Technology.

Myles, A., Peters, J., 2005. Threading splines through 3D channels. Computer-

Aided Design 37 (2), 139-148.

Nocedal, J., Wright, S. J., 1999. Numerical Optimization. Springer. Plass, M., Stone, M., 1983. Curve-fitting with piecewise parametric cubics. In: SIGGRAPH "83: Proc. of the 10th annual conference on Computergraphics and interactive techniques. ACM Press, New York, NY, USA, pp. 229-239. Pottmann, H., Hofer, M., 2003. Geometry of the squared distance function to curves and surfaces. In: Hege, H.-C., Polthier, K. (Eds.), Visualization and

Mathematics III. Springer, pp. 223-244.

Pottmann, H., Leopoldseder, S., 2003. A concept for parametric surface fitting which avoids the parametrization problem. Comput. Aided Geom. Design

20, 343-362.

Rogers, D. F., 1989. Constrained B-spline curve and surface fitting. Comput.

Aided Des. 21 (10), 641-648.

Saux, E., Daniel, M., 2003. An improved Hoschek intrinsic parametrization.

Comput. Aided Geom. Des. 20 (8-9), 513-521.

Tsai, Y. R., 2002. Rapid and accurate computation of the distance function using grids. J. Comput. Phys. 178 (1), 175-195. V´arady, T., Martin, R. R., 2002. Reverse engineering. In: Handbook of Com- puter Aided Geometric Design. Elsevier, pp. 651-681. Wang, W., Pottmann, H., Liu, Y., August 2005. Fitting B-spline curves to point clouds by squared distance minimization. Tech. Rep. 143, Geometry

Preprint Series, Vienna Univ. of Technology.

Weiss, V., Andor, L., Renner, G., V´arady, T., 2002. Advanced surface fitting techniques. Comput. Aided Geom. Des. 19 (1), 19-42. 16