Direct Manipulations Of B-spline And Nurbs Curves

Advances in Engineering Software 31 (2000) 107–118 www.elsevier.com/locate/advengsoft

Direct manipulations of B-spline and NURBS curves M. Pourazady*, X. Xu Department of Mechanical, Industrial, and Manufacturing Engineering, University of Toledo, Nitscke Hall 4006, Toledo, OH 43606-3390, USA Received 28 October 1997; received in revised form 18 May 1999; accepted 18 May 1999

Abstract This paper presents a method for the direct manipulations of B-spline and non-uniform rational B-splines (NURBS) curves using geometric constraints. A deformable model is developed to define the deformation energy functional of B-spline and NURBS curves. The finite element method is used to minimize the deformation energy functional and solve for the deformed shape of curves subjected to constraints. This approach results in a set of linear equations for a B-spline curve and a set of non-linear equations for a NURBS curve. A perspective mapping is used to linearize the NURBS formulations. NURBS curves are first mapped from the 3D Cartesian coordinate space to the 4D homogeneous coordinate space, and transformed to 4D B-spline curves. After the manipulation in the 4D homogeneous coordinate space, the modified NURBS curves are then mapped back to the 3D Cartesian coordinate space. The approach is implemented by a prototype program, which is written in C, and runs under WINDOWS. Several examples are presented to demonstrate the capabilities of this approach. q 2000 Published by Elsevier Science Ltd. All rights reserved. Keywords: Non-uniform rational B-splines; 3D Cartesian coordinate; 4D B-spline curves; Direct manipulations of NURBS

1. Introduction Curve and surface design have many applications in manufacturing industries, such as automobile body design, ship hull design, etc. Over the past thirty years, different curves and surfaces representation forms have been proposed. Currently, B-splines and NURBS (non-uniform rational B-splines) are the most popular mathematical forms. NURBS offers a unified mathematical form not only for representation of free-form curves and surfaces, but also for the precise representation of close-form shapes such as lines, conics, quadrics, and surfaces of revolution. Further, the extra degrees of freedom NURBS offers—the weights, allow a large variety of shapes to be generated. Therefore, NURBS has become more and more popular in recent years. It has been an IGES standard since 1983, and many commercial CAD systems are based on the NURBS representation. Providing operations for modifying the shape of NURBS curves and surfaces is an important issue in curve and surface design. The desired shape of a curve or a surface is obtained through a complex and interactive process. It seldom happens that the initial design meet the required specifications, and the process of modification goes on * Corresponding author. Tel.: 1 1-419-530-8210; fax: 1 1-419-5308206.

until the shape of the curve and surface satisfies the requirements. Until now, all interactive design schemes proposed can be classified into two categories. One is the control point based method, which manipulates curves and surfaces by controlling the DOF (degrees of freedom) defining them and the other is the so-called direct manipulation method. In this method selected points on a curve or a surface are moved to new user defined locations. The first method [1–3] is still the prevalent method for interactive design of curves and surfaces in commercial systems. For example, B-splines are usually manipulated by moving their control points, and for NURBS, the extra degree of freedom called weights can be used to manipulate the shape of curves or surfaces. One of the problems with this technique is that the control points or weights are not directly related to the modified shape of curves or surfaces. Therefore, interactive design using this scheme is often cumbersome. Sometimes a large number of DOF must be manipulated in order to modify even a small piece of a curve segment. It is also not clear which DOF should be manipulated and how it should be manipulated. The direct manipulation method on the contrary provides the designer a higher level interface and shape design is more intuitive. In this scheme, users are allowed to specify arbitrary constraints on a curve or a surface. For example, the designer can pick points on a curve and move them to desired positions. The new DOF, which satisfy the specified

0965-9978/00/$ - see front matter q 2000 Published by Elsevier Science Ltd. All rights reserved. PII: S0965-997 8(99)00026-5

108

M. Pourazady, X. Xu / Advances in Engineering Software 31 (2000) 107–118

Fig. 1. B-spline basis functions.

constraints, are automatically computed. The direct manipulation method allows the designer a much better feel between the input (specified constraints) and the output (modified curve or surface). Current direct manipulation methods can be further classified into two categories: direct linear methods and physically based methods. 1.1. Direct linear methods (B-splines only) The goal of direct manipulation methods is to configure the DOF of curves and surfaces so that the deformed locations of the selected points match the specified target locations. As there are many DOF configurations that will yield the same target locations, certain criteria must be established in order to select a reasonable solution. In direct linear methods, least squares are adopted as the criteria, and the final solution is the one that moves the control points, the least. Forsey and Bartels [4] developed a method for the direct manipulation of hierarchical B-spline surfaces at B-spline joints. Bartels and Beatty [5] extended this method to allow B-spline curves to be manipulated at any point on the curve. Fowler and Bartels [6] extended this technique further to allow first and second derivatives at any points to be manipulated. Hsu et al. [7] proposed a method which allows multiple points to be moved to new locations simultaneously. Recently, Rappoport [8] proposed a probabilistic point constraint where he used Kalman filters to solve the system of probabilistic equations. The soft constraints he used are easier to satisfy and thus lead to smoother deformations. The representation forms used in all these references are B-spline curves or surfaces. Direct linear methods have not been developed for the manipulation of NURBS curves and surfaces. 1.2. Physically based methods In a physically based method, curves and surfaces are assigned some physical properties, such as stretching stiffness, bending stiffness, etc. They are allowed to stretch and bent as real objects. By applying forces and constraints, curves and surfaces are deformed and manipulated in an

intuitive way. This method was first applied in the computer vision area. Terzopoulos et al. [9,10] proposed elastically deformable models, and employed the elasticity theory to construct differential equations that model the behavior of non-rigid curves, and surfaces. Celniker and Gossard [11] developed a prototype system for interactive free-form design by minimization of the energy functional using finite-element method. Celniker and Welch [12] used Bsplines as representation forms and developed deformable B-splines with linear constraints. Terzopoulos and Qin [13] proposed dynamic NURBS, to model deformation of curves and surfaces. They developed physics-based models with properties such as mass distributions, deformation energies, etc. The non-linear equations of motion for a dynamic NURBS are derived based on Lagrangian dynamics and are integrated through time to predict the shape of an object in response to external forces. Faloutsos et al. [14] developed dynamic deformable models based on standard free form deformations. They used different deformation modes such as shear and bending modes to move or animate real life objects. The objective of this paper is to develop, and linearize a physically based method for direct manipulation of NURBS curves and surfaces. NURBS curves and surfaces are first linearized by mapping them into 4D space before any equation solving takes place. The resulting equations are then solved for the new DOF in 4D space, and finally mapped back to 3D space. 2. Direct manipulations of B-spline curves A B-spline curve is defined by the following equation: C…t† ˆ

n X

Ni;p …t†Pi ;

…1†

iˆ0

where Ni;p …t† are B-spline basis functions, Pi are vectors composed of x; y; z coordinates of the control points, p (degree 1 1) is the order of a B-spline curve, and ‰t0 ; t1 ; t2 ; …; tn1p Š is the knot vector which specifies the

M. Pourazady, X. Xu / Advances in Engineering Software 31 (2000) 107–118

109

P7 P2 P3

P1

P0

P6

P5

P4 n=8 k=4 Knot vector [0,0,0,0,0.1,0.3,0.5,0.7,0.9,1,1,1,1] Fig. 2. A B-spline curve.

surfaces are taken as real objects. Curves are taken as slender beams, and surfaces are taken as metal sheets, cloth, etc. When forces are applied on curves and surfaces, they will deform just as the real objects do. Some physical properties can be assigned to curves and surfaces. For example, for a curve, an a term which represents the curve’s ability to resist stretching, and a b term which represents the curve’s ability to resist bending can be associated. If forces are applied on a curve, the shape of the curve will be changed, just like a slender beam is stretched or bent. Fig. 4 shows the deformation of a curve subjected to an external force. Obviously, the extent of a curve’s deformation depends on two factors:

distribution of the parameter t along the curve. The relationship between the order of the curve p, the number of control points n 1 1, and the number of knots m 1 1 is given by m ˆ n 1 p:

…2†

B-spline basis functions Ni;p …t† are also called B-spline blending functions and are defined by ( 1 if ti # t , ti11 ; …3† Ni;1 …t† ˆ 0 otherwise Ni;p …t† ˆ

ti1p 2 t t 2 ti N …t† 1 N …t†: …4† ti1p11 2 ti i;p21 ti1p 2 ti11 i11;p21

Figs. 1 and 2 show B-spline basis functions, and a Bspline curve, respectively. B-spline curves have nice properties which make them suitable representation forms in computer aided geometric design. These properties can be generalized as, affine invariance, Convex hull, and local control properties. For example B-spline curves can be locally refined without changing their global shape. As shown in Fig. 3 the shape of a B-spline curve changes locally in the neighborhood of control points P6 and its new location P 06 :

1. The external forces and constraints. 2. The physical properties of the curve, e.g. a and b terms. Besides forces, constraint is another important tool in deformable models. We may want certain points on a curve to be fixed at particular positions. In this case applying forces to a curve will not help much. Although the specified requirements might be satisfied by applying different forces on a curve, generally a lot of trial and error is needed. Fortunately, constraints can be applied to satisfy these requirements. Constraints also have their counterparts in real objects. Consider a slender beam with both ends fixed, when forces are applied to it, its ends will remain at their original positions though other parts of it will deform. Fig. 5 shows a curve subjected to four constraints. Similarly to real objects, curves also have deformation energy stored inside them as they are deformed. Terzopoulos et al. [9] defined the deformation energy functional of a

2.1. Deformable models Deformable objects have many applications in the design of curves and surfaces. For example, slender beams deform in smooth curves when they are bent, and they are used to loft the ship hull because of this property. In a physically based curve and surface manipulation approach, curves and

P7 P2 P1

P0

P3

P6’

P4

P5

Fig. 3. Local control property of a B-spline curve.

P6

110

M. Pourazady, X. Xu / Advances in Engineering Software 31 (2000) 107–118

2.2. Finite element model of a deformable curve F (a)

: Point constraint

(b) Fig. 4. Deformation of a curve subjected to a force. (a) A curve subjected to a force. (b) The deformed curve.

curve as: "  !2 #  1Z 2C…t† 2 22 C…t† a 1b dt; UC ˆ 2 C 2t 2t2

…5†

where UC represents the deformation energy of a curve, C(t) represents arbitrary points on a curve as a function of the parameter t, a is the stretching stiffness, and b is the bending stiffness. By minimizing the energy functional UC, the shape of a deformable model can be obtained. The nice feature of a deformable model is that it simulates the physical behavior of real objects. The designer can foresee the modified shape of curves by imagining what the shape of real objects will be if they are subjected to forces and constraints. This is a big advantage over the control-points based manipulation approach. In the control point based approach, it is very hard for users to know beforehand what the shape will be after changing the position or weight of any control point. However in a physically based approach, users can modify and fine-tune the shape of curves interactively in an intuitive way. This requires less user input, and less trial and error is needed to achieve the desired effect.

The deformed shapes of B-spline curves are discussed first. The advantage of using B-splines are that their formulation is linear, and they are a special case of the more general NURBS form. Eq. (1) can be written in a matrix form as: 8 9 > P1 > > > > > > > > > > < P2 > = C…t† ˆ ‰B1;p …t†; B2;p …t†; …; Bn;p …t†Š . ˆ ‰BŠ‰PŠ; …6† > .. > > > > > > > > > > : > Pn ;n×3 where C(t) is a vector which represents the x; y; z components of a point on the B-spline curve, and can be written as: 8 9 Cx …t† > > > > < = …7† C…t† ˆ Cy …t† ; > > > > : ; Cz …t† where [B] is the blending matrix, and [P] represents the control points which can be written as: 3 2 P1;x P1;y P1;z 7 6 6 P2;x P2;y P2;z 7 7 6 7 6 : …8† 6 . .. 7 .. 7 6 . 7 6 . . . 5 4 Pn;x Pn;y Pn;z Using the energy functional defined by Eq. (5), and substituting Eq. (6) into Eq. (5), we get: #T " # " " 2 #T 1Z 2B T 2B T 2 B ‰PŠ 1 b‰PŠ a‰PŠ UC ˆ 2 C 2t 2t 2t2 " 

#T " # # ! " " Z 22 B 1 2B 2B T a ‰PŠ dt ˆ ‰PŠ 2 2t 2t 2t2 C "

22 B 1b 2t2

: Original location of a point on the curve (a)

: New location of a point on the curve

#T "

22 B 2t2

#!

# dt ‰PŠ:

…9†

Eq. (9) has the same form as the variational principle in finite element methods and can be written as Z ‰aŠT ‰KŠ‰aŠ; …10† U ˆ 12 V

where [K] is the stiffness matrix, and [a] an unknown vector. Eqs. (9) and (10) are compared to find " 2 #T " 2 #!     Z 2B T 2B 2 B 2 B dt: a 1b ‰KŠn×n ˆ 2t 2t 2t2 2t2 C (b) Fig. 5. Deformation of a curve subjected to constraints. (a) A curve subjected to constraints. (b) The deformed curve.

…11† The governing equations for a deformable B-spline model are obtained in a similar manner to those in static

M. Pourazady, X. Xu / Advances in Engineering Software 31 (2000) 107–118

2 1 and 1 1. The integrand is also changed from t to j . Z1 Zti 1 1 1 fi;j …t† dt ˆ …ti11 2 ti † fi;j 2 ti 21   1 1 …1 2 j†ti 1 …1 1 j†ti11 dj:  …17† 2 2

tn-k+1 Curve element ti ti+1

Fig. 6. Elements of a B-spline curve.

equilibrium problems. The system equation is given by ‰KŠn×n ‰PŠn×3 ˆ ‰f Šn×3 ;

111

…12†

This integral is now in the standard form of the Gauss quadrature method and can be evaluated numerically. In general a polynomial of degree 2n 2 1 is integrated exactly by n-point Gauss quadrature. B-spline functions are in fact polynomials, and for the most widely used quadratic and cubic B-splines, three Gauss points are sufficient to evaluate the above integrals exactly. This results in the following integration.

where [f] is a force vector and is related to the specified user geometric constraints. This equation can be simplified into three independent equations given by:

Zti 1 1

‰KŠ‰Px Š ˆ ‰fx Š;

Wk are Gaussian weights, and j k the Gaussian points. By using Eq. (18), all entries in the [K] matrix can be evaluated one by one.

‰KŠ‰Py Š ˆ ‰fy Š;

‰KŠ‰Pz Š ˆ ‰fz Š: …13†

Solving these equations, the new control point positions can be obtained such that the resulting B-spline curve satisfies the specified requirements. 2.3. Calculation of [K] matrix Gaussian quadrature is used to evaluate the integral given by Eq. (11). First, a B-spline curve is meshed into small curve segments, and each curve segment is regarded as an element. In this work, adjacent knot vectors are taken as an element, e.g. {ti ; ti11 } is an element (see Fig. 6).The entry i and j in the [K] matrix is given by ! Z 2Bi;p …t† 2Bj;p …t† 22 Bi;p …t† 22 Bj;p …t† 1b dt: a ki;j ˆ 2t 2t 2t 2t2 C …14† Let fi;j …t† ˆ a

2Bi;p …t† 2Bj;p …t† 22 Bi;p …t† 22 Bj;p …t† 1b ; 2t 2t 2t 2t2

…15†

Eq. (14) can be then written as ki;j ˆ

Z C

fi;j …t† dt ˆ

Zt1 t0

1

fi;j …t† dt 1

Ztn 1 p tn 1 p 2 1

Zt2 t1

fi;j …t† dt 1 …

fi;j …t† dt:

…16†

Eq. (15) can be evaluated using the De Boor algorithm [15] and each integral in Eq. (16) can be calculated using Gaussian quadrature. A transformation t ˆ …1=2†…1 2 j†ti 1 …1=2†…1 1 j†ti11 is used to change the integration limits to

ti

fi;j …t† dt ˆ

3 X

Wk fi;j …jk †:

…18†

kˆ1

2.4. Constraints Constraints are efficient tools in the direct manipulation approach. The basic idea of applying constraints is to fix some of the parameters on a curve. These parameters could be positions of points on curves, or tangent or normal vectors to points on curves. By applying constraints, every point on a curve can be taken as a “control point”, and thus it greatly increases the flexibility of curve manipulation. In a physically based manipulation approach, constraints are satisfied in the context of minimizing the deformation energy of curves. In other words a curve designed by the physically based manipulation method will have the fairest shape (smooth and realistic shape) among all the curves which satisfy the specified constraints. The constraint problem can be defined Q mathematically as follows. Given a function …x1 ; x2 ; …; xn †; and knowing that the variables x1 ; x2 ; …; xn have the relationship Q C…x1 ; x2 ; …; xn † ˆ 0; solve for x1 ; x2 ; …; xn which make …x1 ; x2 ; …; xn † stationary, and at the same time satisfy a set of equations Ci …x1 ; x2 ; …; xn † ˆ 0: There are similarities between constraints problem and design of curves. Q We may consider x1 ; x2 ; …; xn as the control points, …x1 ; x2 ; …; xn † as the deformation energy functional, and Ci…x1 ; x2 ; …; xn † ˆ 0 as the specified constraint on a curve. There are two methods to solve this problem. These are Langrange multiplier and penalty methods. Using Langrange multipliers, all the specified constraints can be satisfied exactly. However, its drawback is that the total number of unknowns will increase and therefore the total number of equations to be solved will increase. On the contrary, the penalty method does not possess this drawback, but it can only ensure the constraints to be satisfied approximately. In this work, we use the penalty method to make the program more interactive. In

112

M. Pourazady, X. Xu / Advances in Engineering Software 31 (2000) 107–118

When Eqs. (21) and (22) are substituted into Eq. (23), we get

P2 w=3.0 P1

w=1.0

U C ˆ

1 2

‰PŠT ‰KŠ‰PŠ 2 ‰PŠT {f } 1 a…‰B0 Š‰PŠ 2 C0 †2

ˆ

1 2

‰PŠT ‰KŠ‰PŠ 2 ‰PŠT {f } 1 ‰PŠT …a‰B0 ŠT ‰B0 Š†‰PŠ

2 2a‰B0 Š‰PŠC0 1 aC02 :

…24†

As 2‰B0 Š‰PŠC0 is a number, Eq. (24) can be written as U C ˆ

fact, as the penalty number increases the approximate solution obtained from the penalty method will converge to the exact solution. Consider Q once again the problem of obtaining stationary values of …x1 ; x2 ; …; xn †, with a set of constraint equations Ci …x1 ; x2 ; …; xn † ˆ 0: The constraint equations can be written in the vector form as: C T ˆ ‰C1 …x1 ; x2 ; …; xn †; C2 …x1 ; x2 ; …; xn †; …Š ˆ ‰C1 ; C2 ; …Š: …19† 1 1 … is always posiNote that the product C C ˆ tive. Clearly, when constraints are satisfied, CT C will also be zero, and the variation d…C T C† equals zero when C T C reaches its minimum, e.g. zero. Therefore, we can now write a new functional C12

Z Y  ˆ Y 1a C T …u†C…u† dV;

C22

1 2

‰PŠT ‰KŠ‰PŠ 2 ‰PŠT {f }:

…21†

Introducing a point constraint C…t0 † ˆ C0 results in the following equation: 8 9 > P0 > > > > > > > > > > < P1 > = ‰B0;p …t0 †B1;p …t0 †; …; Bn;p …t0 †Š . 2 C0 ˆ 0 > .. > > > > > > > > > > > : Pn ; or ‰B0 Š‰PŠ 2 C0 ˆ 0:

…22†

Taking the constraint into consideration, the deformation energy functional can now be modified to U C ˆ UC 1 a‰C 2 C0 Š2 :

 ˆ ‰KŠ 1 2a‰B0 ŠT ‰B0 Š; ‰KŠ

and

{f } ˆ {f } 1 2aC0 ‰B0 Š:

…26†

Eq. (25) is now written as  ˆ Uc

1 2

 ‰PŠT ‰KŠ‰PŠ 1 ‰PŠT {f }T :

…27†

This equation is in the standard form of the variational principle. From Eq. (27) we can write a set of linear equations.  ‰KŠ‰PŠ ˆ {f}:

…28†

This set of linear equations can be solved by a linear equation solver to find the new positions of the control points[P]. The vector {f} is associated with the specified user constraints. In the next section the same approach discussed here will be extended to develop a deformable model for NURBS curves.

…20†

wherein a is the penalty number. The deformation energy of B-spline curves have the form: Uˆ

…25†

To simplify this equation define

Fig. 7. Push/pull effect of weights in a NURBS curve.

T

‰PŠT …‰KŠ 1 2a‰B0 ŠT ‰B0 Š†‰PŠ 2 ‰PŠT …{f }

1 2aC0 ‰B0 Š†:

P3

P0

1 2

…23†

3. Direct manipulation of NURBS curves NURBS curves are rational forms of B-spline curves. They are defined as: n X

C…t† ˆ

Ni;p …t†wi Pi

iˆ0 n X

ˆ Ni;p …t†wi

n X

Ri;p …t†Pi ;

…29†

iˆ0

iˆ0

where Ni;p …t†wi : Ri;p …t† ˆ X n Nj;p …t†wj jˆ0

Ri;p …t† are the piecewise rational basis blending functions of NURBS curves, Ni;p …t† are the same blending functions defined earlier for a non-rational B-spline curve, and wi is the weight of the control point Pi and must be a non-negative real number. The weights offer NURBS curves extra degrees of freedom, which allow a large variety of shapes to be generated. Piegl [1] has given a geometric interpretation for these weights, and described their push/pull effect.

M. Pourazady, X. Xu / Advances in Engineering Software 31 (2000) 107–118

113

Hyperplane w=w0 P'h Ph

Hyperplane w=1 P' P

O

:

Original curve

: New h

curve after P is constrained to P'. 'h

Note: P and P are in the same hyperplane w=w0. Fig. 8. Perspective projection when weight of the constraint is unchanged.

As weights increase, a curve is pulled closer to its corresponding control points. As weights decrease, a curve is pushed away from its corresponding control points. Fig. 7 illustrates the push/pull effect of the weights. The weight of control point P2 is increased from 1.0 to 3.0, while the weights at the other control points are kept unchanged. While NURBS curves enjoy all the properties of non-rational B-spline curves, they also possess additional properties. For example NURBS curves can be used to represent precisely the close-form shapes such as conics, quadrics. NURBS curves are the generalization of the non-rational B-spline curves, and when all the weights are set to be equal, NURBS curves degenerate to non-rational B-spline curves.

3.1. 3D NURBS versus 4D B-splines The blending functions in the NURBS formulation incorporate the unknown weights wi, and therefore, following the procedure used to solve for the deformable B-spline curve will lead to a set of non-linear equations. Solving these equations will complicate the whole problem, and increase the computation cost. In this paper a homogenous coordinate system is introduced to map the 3D NURBS curve into 4D space. NURBS curves are transformed to 4D rational B-spline curves. Based on the linear deformable model developed for B-spline curves, NURBS curves are manipulated in the 4D

114

M. Pourazady, X. Xu / Advances in Engineering Software 31 (2000) 107–118

Hyperplane w=w0' P'h

Ph

Hyperplane w=w0

Hyperplane w=1

P' P

O

: Original curve : New curve after P is constrained to P'. h

Note: P is in hyperplane w=w0, h P' is in a different hyperplane w=w0'. Fig. 9. Perspective projection when weight of the constraint is unchanged.

homogenous space. Finally the modified curves are mapped back to the 3D Cartesian space. A detailed discussion of perspective mapping and 4D homogenous coordinate system is given in reference [3]. Any control point associated with a NURBS curve could be represented in a 4D homogeneous coordinate system with four coordinates …wx; wy; wz; w†. This point represents the Cartesian point …x; y; z† when it is normalized as …x; y; z; 1†. In fact, a NURBS curve in the 4D homogeneous coordinate system becomes a B-spline curve. Based on this idea a NURBS curve can be written in 4D homogeneous form as: C h …t† ˆ

n X

Ni;p …t†Phi ;

…30†

iˆ0

where C h …t† represents a NURBS curve in the 4D homogeneous coordinate space, and Phi are the control points in 4D

homogeneous space. The components of Phi are 8 9 wi Pix > > > > > > > > > < wi Piy > = h Pi ˆ : > > > wi Piz > > > > > > > : ; wi

…31†

We can see from Eq. (30) that the linear relationship between a NURBS curve and its control points is restored, and Eq. (30) has exactly the same form as the B-spline form, except Phi now has four components instead of three. One natural way to solve this problem is to manipulate the NURBS curve in 4D space, and then map it back to 3D space. 3.2. Linear model of a deformable NURBS curve A new set of control points defined by Eq. (31) is substituted in Eq. (13) to find the following four equations for a

M. Pourazady, X. Xu / Advances in Engineering Software 31 (2000) 107–118

115

DMCS user interface

File

Open

Save

View

Graphic

Exit

Redraw

Zoom

Manipulate

Construct

Eye Direction

Extrude

Revolve

Add Constr Del Constr

Weight

Fig. 10. The modulus of DMC program.

deformable NURBS curve. ‰KŠ‰Px Š ˆ ‰fx Š h

‰KŠ‰Py Š ˆ ‰fy Š h

‰KŠ‰Pw Šh ˆ ‰fw Š:

‰KŠ‰Pz Š ˆ ‰fz Š h

…32†

Similarly constraint equations for a NURBS curve in 4D homogeneous coordinates can be written in the following form: ‰BŠ‰Px Šh ˆ Cx w ‰BŠ‰Pw Šh ˆ w;

‰BŠ‰Py Šh ˆ Cy w

‰BŠ‰Pz Šh ˆ Cz w …34†

where Cx ; Cy ; Cz are coordinates of the constraint in 3D space, and w is the weight of the constraint in 4D homogeneous space. In view of the relationship between the 3D Cartesian coordinate and the 4D homogeneous coordinate, we can see that any value of w will ensure that the constraints are satisfied when a NURBS curve is mapped back into 3D space. This situation is illustrated in Fig. 8 where point O is the projection origin, and w ˆ 1, w ˆ w0 are two different projection planes. The hyperplane w ˆ 1 can be viewed as a 3D Cartesian space, and the hyperplane w ˆ w0 corresponds to a 4D homogenous space. If w remains at its original value, e.g. the constraint will remain in the same hyperplane as the original point then only the x; y; z coordinates of the new control points will change, while their weights will not change. If w changes, the constraint will move to a different hyperplane. This situation is illustrated in Fig. 9. In this case, both the x; y; z coordinates and the weights of the new control points will change, but the specified constraint is still satisfied. Therefore, by changing w, many different curves which satisfy the specified constraint can be generated. In solving Eq. (32), w is specified by the user, and the forth equation is solved first for the weights of the control points. These weights are then substituted back into the first three equations, so that this set of equations can be solved. In the program developed in this work, when the user specifies a constraint, the weight of this constraint remains at its original value, and the corresponding new curve will be solved and displayed. The user can change the weight value by selecting “Weight” command, then picking the constraint and moving the mouse. Moving the mouse

upwards increases the weight value, and moving the mouse downwards decreases the weight value. The difference between the new weight value and the original weight value depends on how much the mouse is moved. The new NURBS curve will be solved and displayed continuously as the user moves the mouse. All these curves satisfy the specified constraint, however the shape of the curve segment near the constraint changes. This process will continue until the user obtains a desired curve shape and releases the mouse button. By using this method, a large variety of shapes, which satisfies the specified constraints can be generated, and the user can choose the best one. Therefore, compared with B-spline curves, direct manipulations of NURBS curves are more flexible.

: Original locations of the constraints : Target locations of the constraints (a)

(b) Fig. 11. (a) Original B-spline curve. (b) Modified B-spline curve.

116

M. Pourazady, X. Xu / Advances in Engineering Software 31 (2000) 107–118

4. User interface To demonstrate and verify the curve manipulation scheme developed in this paper, a program called DMC (Direct Manipulation of Curves) has been developed. The program was developed using Borland C 1 1 4.5, and runs under Windows environment. The program is organized in a layered structure. The core of this structure is the data structure of B-spline, and NURBS curves, respectively. Upon each data structure lie the “File”, “View”, “Construct” and “Manipulation” modules. The outmost layer is the user interface, which consists of menus for input and output of data, graphic display and various manipulation operations. Fig. 10 illustrates the program structure. The “File” module provides four options: “Open”, “Save”, “Graphic file” and “Exit”. By choosing “Open” option, the user opens an input file, and the data defining a curve or surface are read into the memory. The curve to be modified is then displayed on the screen, and the user can start the design process. By choosing “Save” option, the data defining the modified curve will be written to an output file. If “Graphic file” option is picked, the image of the curve will be written to an DXF format data file, and this file can be imported into AutoCAD. In this way the image of a curve can be hard copied to a printer or a plotter. The “View” module provides users flexibility in viewing a curve under design. When the user opens an input file, initially, the curve is always fitted to the screen. The user can zoom in, zoom out and change views at any time by selecting the corresponding options. This will help the user to make the right decision in the design process. The “Construct” module is used to revolve or extrude curves into surfaces. By using this options, surfaces of revolution and surfaces of extrusion can be conveniently created from a cross-section curve, and surface design is simplified to curve design. The operations for manipulating curves are provided in the “Manipulation” module. By choosing “Add constraint”, the user applies a constraint on a curve under design. In curve design, the modified shape of a curve is immediately obtained and the screen is refreshed to show the new curve as the user moves a point on a curve to a new location. For NURBS curves, the “Weight” option is available to modify their shapes. The user first picks a constraint on a curve and then moves the mouse in the upper right or lower left directions. This results in an increase or decrease for the weight of a selected point.

5.1. Example 1: B-spline curve The first example is a B-spline curve. Its parameters are: Order of the curve p ˆ 4. Number of control points n ˆ 5. Knot vector tk ˆ ‰0:0; 0:0; 0:0; 0:0; 0:3; 0:7; 1:0; 1:0; 1:0; 1:0Š: To modify the shape of this curve, five constraints are applied. The original curve and the constraints are shown in Fig. 11(a). In this figure, squares denote the original locations of the constraints, and circles denote the target locations of these constraints. The modified B-spline curve is shown in Fig. 11(b). As shown here all the constraints on the modified curve are satisfied. 5.2. Example 2: NURBS curve This example presents the manipulation of a NURBS curve with the following parameters: 1. Order of the curve p ˆ 4, 2. Number of control points n ˆ 5.

(a)

(b)

5. Results To demonstrate the capability of the developed curve manipulation method, some examples are presented in this section. All the curves in these examples are manipulated by specifying constraints.

(c) Fig. 12. (a) Original NURBS curve. (b) Modified curve with uniform weights for the constraints. (c) Modified curve with different weights for the constraints.

M. Pourazady, X. Xu / Advances in Engineering Software 31 (2000) 107–118

117

A

B (a)

(b)

(a)

Fig. 13. (a) Initial underformed straight line. (b) Sihouette of a human face.

3. Knot vector tk ˆ ‰0:0; 0:0; 0:0; 0:0; 0:3; 0:7; 1:0; 1:0; 1:0; 1:0Š. Similar to Example 1, five constraints are applied. The original NURBS curve and the applied constraints are shown in Fig. 12(a). In the first case, all the weights of these constraints (circles show constraint locations) remain the same, and the modified NURBS curve is shown in Fig. 12(b). Clearly, the new curve satisfies the specified constraints. In the second case, the weight of the third constraint changes from 1.492517 to 3.900495, and the modified NURBS curve is shown in Fig. 12(c). This shows that the modified NURBS curve still satisfies the specified constraints, but the shape of the curve is totally different from the one given in Fig. 12(b). The shape of the curve near the third constraint is flatter now. Therefore there is more than one solution for this problem and a large variety of curves can be generated which satisfy the specified constraints. 5.3. Example 3: silhouette In this example, a silhouette of a human face is designed using a straight line. The design starts with an undeformed line defined by a cubic B-spline curve with eighteen control points. The curve is directly manipulated by dragging different points on the curve, to their new locations. This process continues until the final shape shown in Fig. 13 is generated.

(b) Fig. 14. (a) Cross section of the pot as a deformed NUBRS curve. (b) Surface model of the pot.

5.4. Example 4: pot

on the curve, the cross section of the pot is generated (Fig. 14(a)). Finally, the cross section curve is revolved to create the pot shown in Fig. 14(b).

In this example, a pot is designed as a surface of revolution. The surface design problem is simplified to a curve design problem by creating a cross section as a curve and then revolving it. The design starts from a straight line, with a cubic NURBS formulation. By applying five constraints

6. Conclusions A direct manipulation scheme for B-spline, and NURBS

118

M. Pourazady, X. Xu / Advances in Engineering Software 31 (2000) 107–118

curves using geometric constraints has been presented. The deformation energies of these parametric curves are determined and minimized based on the finite element method. Two deformable models are developed. One is a linear model for B-spline curves and the other is a non-linear model for NURBS curves. Perspective mapping is used to linearize the NURBS formulation. Based on a homogenous coordinate representation, a 3D NURBS curve is transformed into a 4D B-spline curve. The linear deformable model developed for a B-spline curve is then modified and used for a NURBS curve. By adjusting the weights of the constraints, a large variety of curves can be generated which satisfy the specified constraints. The deformable models used in the present scheme relates curves to real objects, and assigns them physical properties. A designer can easily foresee the shape of the modified curve by imagining what the shape of a real object will be if it is subjected to the same constraints. In the direct manipulation scheme, there is no need to manipulate the individual degrees of freedom of curves such as control points locations and weights and the design process is more intuitive.

References [1] Piegl L. Modifying the shape of rational B-splines. Part 1: curves. Computer aided design 1989;21(8):509–18.

[2] Piegl L. Modifying the shape of rational B-splines. Part 2: surfaces. Computer Aided Design 1989;21(9):538–46. [3] Au CK, Yuen MMF. Unified approach to NURBS curve shape modification. Computer Aided Design 1995;27(2):85–93. [4] Forsey DR, Bartels RH. Hierarchical B-spline refinement. Computer Graphics 1988;22(4):205–12. [5] Bartels R, Beatty J. A technique for the direct manipulation of spline curves. Proceedings of the Graphics Interface 89. Los Altos, CA: Morgan Kaufmann. 1989. p. 33–9. [6] Fowler B, Bartels R. Constraint based curve manipulation. Computer Graphics & Applications 1993:43–9. [7] Hsu WM, Hughes JF, Kaufmann H. Direct manipulation of free-form deformations. Computer Graphics 1992;26(2):177–84. [8] Rappoport A, Hel-Or Y, Werman M. Interactive design of smooth objects with probabilistic point constraints. ACM Transactions on Graphics 1994;13(2):156–76. [9] Terzopoulos D, Platt J, Barr A, Fleischer K. Elastically deformable models. Computer Graphics 1987;21(4):205–14. [10] Terzopoulos D, Fleischer K. Deformable models. Visual Computer 1988;4(6):306–31. [11] Celniker G, Gossard D. Deformable curve surface finite elements for free form shape design. Computer Graphics 1991;25(4):257–66. [12] Celniker G, Welch W. Linear constraints for deformable B-spline surfaces. Proceedings of the Symposium on Interactive 3D Graphics. New York: ACM, 1992. p. 165–70. [13] Terzopoulos D, Qin H. Dynamic NURBS with geometric constraints for interactive sculpting. ACM Transactions on Graphics 1994;13(2):103–36. [14] Faloutsos P, Van de Panne M, Terzopoulos D. Dynamic free-form deformations for animation synthesis. IEEE Transactions on Visualization and Computer Graphics 1997;3(3):201–12. [15] De Boor C. On calculating with B-splines. Journal of Approximation Theory 1972;6:50–62.