Interactive Sculpting with Deformable Nonuniform B-splines

COMPUTER forumGRAPHICSVolume 16 (1997 ), number 4 pp. 191–199 Interactive Sculpting with Deformable Nonuniform B-splines Tzvetomir Ivanov Vassilev Department of Computer Science, Queen Mary and Westfield College, Mile End Road, London E1 4NS, UK Department of Informatics, University of Rousse, 8 Studentska St, 7017 Rousse, Bulgaria, e-mail :ceco!ami.ru.acad.bg Abstract This paper describes an efficient method for manipulating deformable B-spline surfaces, based on minimizing an energy functional. The major benefit of the proposed new fairness norm is that it preserŠes the natural representation of the B-spline surface control points (a two dimensional array)which has an efficiency adŠantage oŠer other methods. The designer uses forces as a main sculpting tool and is free to specify a single force, a set of isolated forces, forces situated on a line or curŠe or area of the deformable surface. The user is allowed to modify seŠeral parameters and in this way to change the physical properties of the object. Keywords : nonuniform B-splines, curve and surface energy minimization, interactive sculpting. 1. Introduction A necessary feature of a modern CAD system is the facility for interactive free-form design, i.e. to supply the user with tools and techniques for interactive manipu- lation of the shape of an object. The simplest approach is to allow the user to manipulate the control points of the designed object (curve, surface or volume) and in this way to change its shape. Although this is the easiest and fastest way from amathematical point of view, it does not prove to be very appealing for designers. Themain reason is that when the portion of the object that is to be deformed includes many control points, the task of the user becomes tedious and in some cases even impossible. For a more detailed description of other drawbacks see Hsu et al." The main objective of the work presented in this paper is to develop a method for interactive sculpting of a B- spline surface (or curve), using direct manipulation on the object, rather than its controls. The technique has to preserve the two dimensionality of the array of the control points and to allow a real time sculpting even when a large portion of the object is deformed. One of the approaches for direct manipulation, de- scribed in the literature"–&, is to use mathematical means to compute the new position of the control points. Hsu, Hughes andKaufman" gave the user the freedom tomove a single point or a set of points on the object to a new position. They use a least squares method to solve the under-determined system for the new control points. The method is local because for cubic B-spline curves when a single point is moved only the closest four control points are affected. This drawback was removed by Finkelstein and Salesin# applying multiresolution analysis. The method of Fowler and Bartels$,% concerns not only points but also tangents and the twist vector. A length-minimum solution is applied to the under-determined system. The scheme proposed by Rappoport et al.& uses Kalman filtering to compute the new control points. Its main advantage is that the constraints are not exact but probabilistic. A completely different approach to these methods is so called ‘‘physical modelling’’. Here the designed object is enriched with a behaviour governed by physical laws. Due to this fact physics-based techniques possess a higher degree of flexibility and freedom than the pure math- ematical solutions. A lot of research has been done recently in this field. Bloor and Wilson’ obtained a B- spline surface as an approximate numerical solution to partial differential equations. Thingvold and Cohen( suggested a deformable B-spline surface, whose control points were represented as mass points connected with elastic springs and hinges. Celniker and Gossard) suggested an interesting energy functional for free-form # The Eurographics Association 1997. Published by Blackwell Publishers, 108 Cowley Road, Oxford OX4 1JF, UK and 350 Main Street, Malden, MA 02148, USA. 191 192 T. VassileŠ } InteractiŠe Sculpting with Deformable Nonuniform B-splines shape design, based on minimizing the finite-element stretching and bending energy terms. The used a Hermite polynomial basis for representing curves and triangular patches for surfaces. Later Celniker andWelch* extended the idea for point and curve constraints on a B-spline surface. The method of minimization of curvature"! or of the thin plate and the membrane energy""–"% has also been widely used. A common drawback of almost all existing methods for minimizing an energy functional in the context of B- spline surfaces),*,""–"$ is that the natural representation of the control points (a two dimensional array) is not preserved. They are rearranged in a column vector which, as proved by Farin"&, is more time consuming. In general, if we have to compute a subarray of (n‹n) control points and if they are rearranged in a vector, the number of computations is O(n’). It can be reduced to O(n%) if we keep the points organized in a two dimensional array"&. This paper describes a method for interactive sculpting of a nonuniform B-spline surface using a physics-based modelling approach. The energy functional is similar to those described in the literature),*,"#,"$ but it preserves the two dimensional array representation of the control points. Due to this fact and other details in the norm, the number of the computations is reduced to O(n$). Since the application of forces rather than new positions is the main sculpting tool, the technique possesses the softness typical of the method of Rappoport et al.& Throughout this paper, italic lower-case letters, such as x and x(u), are reserved for scalar values or functions, and bold lower-case letters, such as w or w(u), for geometric row vectors or vector functions with length 3 (3D points or forces). Bold upper-case letters, such as K, indicate matrices or column vectors in matrix equations. A column of n points (or forces) is in fact a (n‹3) matrix. The rest of the paper is organized as follows. In section 2 we describe a deformable B-spline curve, including evaluation of the fairness norm and the forcing vector, solving for a single force and set of forces and moving a single point of the curve to a new position. Section 3 extends the scheme for B-spline surfaces. In section 4 an approach for evaluating the integrals for the nonuniform case is described. Section 5 presents the results and section 6 concludes the paper. 2. Deformable B-spline Curve Let w(u)fl [x(u), z(u)] be a space curve parameterized by u and let f(u) denote the applied sculpting forces on it. Celniker and Gossard) suggested the following energy functional for curves Efl& curve [aw0 #(u)›bw$ #(u)fi2f(u)w(u)] du, (1) wherew0 (u) andw$ (u) are the first and second derivatives in respect to the parameter u. The energy E in (1) can be subdivided in two parts EflE " fiE # : E " fl& curve [aw# #(u)›bw$ #(u)] du (2) E # fl 2& curve r(u)w(u) du. (3) E " represents the energy of the curve itself and its natural resistance to deformations while E # is the energy due to the applied forces. The curve energy is expressed as a weighted sum of its stretching and bending terms, where a and b are freely selected coefficients. First we shall try to evaluate (2) and (3) for a single B-spline segment and then by application of the finite element method the global energy can be found through summation. 2.1. Evaluating the Fairness Norm A single cubic B-spline segment can be written as w s (u)fl VT s B s , whereV s is the column vector of control points and B s is a column vector of the B-spline basis functions. Evaluating integral (2) for the function w s , will result in the following quadratic form E "s flVT s K s V s (4) where K s is a (4‹4) symmetric matrix, whose entries are calculated evaluating integral (2). E "s is called a ‘‘ local fairness norm’’ and K s is the ‘‘ local stiffness matrix ’’ for the segment w s (u). K s can be represented as a weighted sum of its stretching and bending terms, i.e. K s flaK "s ›bK #s . (5) In case of a uniform knot distribution and by using de Boor’s formula"’ one can easily find the entries of the matrices in (5) directly computing K "s fl&u" u ! BJ s BJ T s du, K #s fl&u" u ! B> s B> T s du. (6) The exact values of K "s and K #s are given by Vassilev"(. Now, after we have expressed the local fairness norm E "s for a single segment, the global fairness norm E " for a B-spline curve can be found as a sum of the local fairness norms over each of the B-spline polynomial segments. The expression for E " can be written as E " flVTKV (KflaK " ›bK # ), (7) whereV is the vector of control points for the spline curve and K is a quadratic symmetric band matrix obtained from the local stiffness matrices. 2.2. Evaluating the Forcing Vector In order to calculate (3) first an analytical expression for the force vector f(u) should be available. To simplify the # The Eurographics Association 1997 T. VassileŠ } InteractiŠe Sculpting with Deformable Nonuniform B-splines 193 Figure 1: A force acting on a single B-spline segment is a linear interpolation of forces applied at the ends. model we assume that f is a linear interpolation of the forces applied at the end of the polynomial segment (see Figure 1) f(u)fl u " fiu u " fiu ! f ! › ufiu ! u " fiu ! f " flSTF s , (8) where S is a vector of interpolating scaling functions and FT s fl [fT ! fT " ]. After computing the integral (3) using the formula (8) one can derive the following result for the local segment forcing energy E #s fl 2VT s C s F s , (9) where V s is the local vector of control points and C s is a (4‹2) coefficient matrix whose entries are calculated from C s fl&u" u ! B s ST du. (10) Evaluating (10) for the uniform case gives C s fl 1 120 A B 33 4 22 1 22 1 33 4 C D . (11) The product C s F s is also called a ‘‘ local forcing vector’’. After we have an expression for the local forcing vector, applying the finite element principal, the global forcing energy becomes E # fl 2VTCF, (12) where V is the vector of control points with length n, F is the global end forces vector with length (nfi2) and C is a [n‹(nfi2)] matrix derived through summation from the local coefficient matrices. Now we are ready to rewrite once again (1) but this time in matrix form: EflVTKVfi2VTCF. (13) Minimizing (13) will ensure the smoothness and the fairness of the resulting curve.K is symmetric and positive definite, so the minimum can be found simply by setting the gradient of E equal to zero KVflCF. (14) According to (14), to every control point v i there corresponds an end force f i−" , except for v ! , v " and v n−" , v n to which correspond only f ! and f n−# . As a consequence, a B-spline curve can be modified only by changing its end forces vector F. This means that any arbitrary force has to be replaced by two other applied at the ends. A natural question here is whether we lose accuracy by doing this. The answer is no, because the only way to modify a B- spline curve is to move a control point which is, in fact, to change its corresponding end force. 2.3. Solving for a Single Force Suppose we have a static state of the curve with control vector V ! and forces F ! , i.e. KV ! flCF ! . The physical meaning of the vector F ! is the set of forces that makes the curve occupy a particular shape in the space, i.e. it represents the geometric constraints. If no forces are applied (F ! 3 0) then the curve will contract to a single point, the origin of the coordinate system (0, 0, 0). Let us now change the force vector to a new value F " . Then the control points will also change to V " , i.e. KV " flCF " . Subtracting the equalities corresponding to the two states results in the following system: KDVflCDF, (15) where DF represents the change in the applied forces and DV is the change in the control points due to these forces. Let us now assume that a single force ffl ( f x , f y , f z ) is acting on the curve point w f flw(u f ). As mentioned in the previous section, f has to be divided into two components (ffl f ! ›f " ). It is quite straightforward to suppose that they are with the same direction and magnitudes depending on the distance from the end to w f . The simplest choice is shown in Figure 2, where f ! fl u " fiu f u " fiu ! f f " fl u f fiu ! u " fiu ! f. (16) Now the right hand side of (15) changes to CDFflCf ! ›Cf " flC ! f›C " fflC f f. Let r be the number of the control points that are to be changed. It controls the breadth of the change and can be specified by the user. Then the system is expressed as K r DV r flC f f, (17) where K r is the system matrix with dimension (r‹r), retrieved from the global stiffness matrix, DV r is the unknown vector of the displacement in the control points and C f is a coefficient vector corresponding to the force f. Equation (17) is equivalent to three systems of the typeK r # The Eurographics Association 1997 194 T. VassileŠ } InteractiŠe Sculpting with Deformable Nonuniform B-splines Figure 2: A force acting on a B-spline segment is replaced by two other applied at the ends. DV rx flC f f x , one for each spatial component. However, since f x , f y , f z are scalars, it is sufficient to find the solution V c of the system K r VflC f and then DV r flV c f. (18) Once the displacement vector DV has been found the new vector of control points is V " flV ! ›DV. 2.4. Moving a Curve Point to a New Position Applying a force on a curve point will move the point in a desired direction but the exact new position cannot be predicted. However the user might want to move the point to a specified new target. Then we have to compute the magnitude of a force that will do the desired change. Suppose we want to move a curve point p ! flw(u f ) to a new position p " . Then from the B-spline curve formula one can write BTDVflDp, (19) where Dpfl p " fip ! . Using (18), (19) changes to BTV c ffl Dp and the expression for computing the necessary force becomes ffl Dp BTV c . (20) Note that the value in the denominator is not a vector but a scalar product of two vectors. 2.5. Solving for a Set of Forces If the user specifies not only one but a set of forces f i , ifl 1,… , s, two different approaches are possible. The first is to compute each displacement vector DV i , due to the force f i , and then the global displacement DV is, due to the linearity, the sum of the separate DV i . However, if the number of forces is large (s" 4) it is more efficient to keep the equations of the type (15) and solve three systems for the different spatial components. 3. Deformable B-spline Surface Let w(u, Š)fl [x(u, Š), y(u, Š), z(u, Š)] be a surface parameterized by u and Š, and let f(u, Š) denote the applied sculpting forces on it. Most of the energy functionals suggested in the literature),*,"#–"% are expressed as the weighted sum of the norms of the first and second partial derivatives. In this paper the following integral, containing derivatives up to fourth order, is considered Efl&& surface [c " w# u ›c # w# v ›c $ w# uu ›c % w# uv ›c & w# vv › c ’ w# uuv ›c ( w# uvv ›c ) w# uuvv fi2fw] du dŠ, (21) where the suffixes mean partial derivatives in respect to the parameters u and Š. This choice has two main advantages. First, higher order derivatives suppose a fairer surface, and second, it simplifies the computational process. Analogously to the curve case the surface energy can be split in two parts EflE " fiE # , E " representing the natural surface resistance to deformations and E # the forcing energy. 3.1. Evaluating the Fairness Norm As mentioned in the introduction, our main goal when calculating the fairness norm will be to preserve the two dimensionality of the array of control points. The equation of a tensor product B-spline surface is w(u, Š)flBT u VB v , (22) where V is a (m‹n) matrix of the controls points and B u and B v are vectors containing the B-spline basis functions for the parameters u and Š respectively. Now evaluating integral (21) for E " and then finding the gradient in respect to V leads to ¡E " fl 2(c " K "u VK !v ›c # K !u VK "v ›c $ K #u VK !v › c % K "u VK "v ›c & K !u VK #v ›c ’ K #u VK "v › c ( K "u VK #v ›c ) K #u VK #v ). (23) Here the matrices K "u , K "v , K #u , K #v are the same as for a B-spline curve, see (7). The suffix shows the knot sequence (parameter) for which they are calculated. A complete derivation of (23) can be found inVassilev"(. Thematrices K !u and K !v are new and appear only for a B-spline surface. Their entries are computed evaluating K !u fl&u" u ! B u BT u du, K !v fl&v" v ! B v BT v dŠ. (24) It is quite obvious that expression (23) is too com- plicated to be useful for any practical application. If we add the term 2c ! K !u VK !v we arrive at the following approximation to (23) ¡E " fl 2K u VK v , (25) # The Eurographics Association 1997 T. VassileŠ } InteractiŠe Sculpting with Deformable Nonuniform B-splines 195 where K u fl c u K !u ›a u K "u ›b u K #u , and K v fl c v K !v ›a v K "v ›b v K #v (c ! fl c u c v , c " fla u c v ,… , c ) fl b u b v ). The fairness norm (25) has the following interesting properties : E If c’a, b, c u c v K !u VK !v can be neglected and (25) is a good approximation of (23), containing all its terms. E While the highest order of the derivatives in the literature),*,"#,"$ is only two, in (25) it is four (b u b v K #u VK #v ). This supposes a smoother and fairer resulting surface. E Most of the described functionals),*,"#,"$ have two parameters to control the physical properties of the surface : a represents resistance to stretching and b to bending. In (25) another control parameter appears, c. As the various experiments the author conducted showed, it has themeaning of hardness of the material. The bigger the value of c the harder the surface and consequently the narrower the deformation. E The new proposed fairness norm has two stiffness matrices, one in direction of the parameter u and another one for Š. This gives users the opportunity to design nonisotropic materials, i.e. with different properties in the two different directions. E The expression is quite simple and hence suitable for practical applications. As we shall see later it leads to a simple system which can be solved very fast. Note: The terms corresponding to c are in addition to those for the curve case and appear only for surfaces. However, the experiments showed that if added to the curve energy they have the same influence as for the surface case. 3.2. Evaluating the Forcing Matrix When calculating the forcing matrix we shall follow the same approach as we did for curves : first evaluating for a single B-spline patch and then uniting all the elements in a global expression. As shown in Figure 3 a force applied anywhere on the patch we replace with a bilinear interpolation of the forces applied at the four ends f(u, Š)flST u F p S v , (26) where S u and S v are vectors with the interpolation scaling functions in direction u and Š respectively and F p is a (2‹2) matrix of the forces. Evaluating the forcing part of integral (21), substituting f with (26) and finding the gradient in respect to the control points gives the following matrix expression ¡E #p fl 2C su F p CT sv . (27) Here C su and C sv are the same as for a curve segment, see (9) and (10). Applying the finite element principle