GC 1 multisided B�zier surfaces

Engineering with Computers (1997) 13:222-234 9 1997Springer-Verlag London Limited

Engineering C~'~puters

GC ~ Multisided Bezier Surfaces X. Ye, 1 H. N o w a c k i 2 and N. M. Patrikalakis 1 1MassachusettsInstitute ofTechnology,Department ofOceanEngineering,Cambridge,USA;2 Instituteof Marine Technology,Technical University of Berlin, Germany

Abstract. This paper presents a new method for 9eneratin9 a tangent-plane continuous (GC t) multisided surface with an arbitrary number of sides. The method 9enerates piecewise biquintic tensor product Bdzier patches which join each other with Gl-continuity and which interpolate the 9iven vector-valued first order cross-derivative functions along the boundary curves. The problem of the twist-compatibility of the surface patches at the center points is solved through the construction of normal-curvature continuous starlines and by the way the twists of surface patches are generated. This avoids the inter-relationship amono the starlines and the twists of surface patches at the center points. The 9eneration of the center points and the starlines has many degrees of freedom which can be used to modify and improve the quality of the resultin9 surface patches. The method can be used in various 9eometric modelin9 applications such as fillin9 n-sided holes, smoothin9 vertices of polyhedral solids, blendin9 multiple surfaces, and modeIin9 surface over irregular polyhedral line and curve meshes.

Keywords. Biquintic B6zier patches; CAD; CAGD; CAM; G 1 continuity; GC ~ and GC 2 modifications; GC 1 surface simplexes; Multisided surfaces; Twistcompatibility

1. Introduction In state-of-the-art solid and surface modelers, nonuniform rational B-spline (NURBS) surfaces, and their special cases B6zier surface patches, are the most commonly used surfaces. In fact, NURBS are becoming the neutral standard form in industry for representing and exchanging free-form surface data between different CAD/CAM systems. Unfortunately, NURBS surfaces only can be applied to rectangular grids. However, geometric objects, even simple ones, Correspondence and offprint requests to. Professor N. M. Patrikalakis, Department of Ocean Engineering, MassachusettsInstitute of Technology,Room 5-428,77 MassachusettsAvenue,Cambridge, MA 0213 9-4307,USA.

often have complex shapes that cannot be represented by rectangular gridded surfaces, e.g. triangular, pentagonal and hexagonal surfaces used in rounding corners of solid objects. The problem of modeling n-sided surfaces has already been widely studied. Various modeling methods have been proposed. Surveys can be found in [1-4]. In [5] a method is introduced to generate quadratic triangular and pentagonal surfaces under so-called Sabin nets. Surfaces under this method have simple quadratic first order cross-derivative functions. In [6] the S-patch is developed as an extension for both the tensor product and triangular B6zier patches. An S-patch has a relatively high degree and complicated form. In [9] the S-patch is used to generate so-called generalized B-spline surfaces over irregular topological Sabin nets. There has been much work on modeling n-sided surfaces using blending techniques. These methods include the overlap patches proposed in Varady [8], the patch simplexes introduced in Hahn [9] and the G-spline developed in H611ig and M6gerle [10]. There are also many efforts in modeling n-sided surfaces by composing B6zier patches from given boundary data. Bicubic GC I n-sided surfaces can be generated if the boundary curves, the center points, and the starlines (i.e. extra boundary curves of the surface patches) are solved and modified according to the special sets of solutions to the twist-compatibility conditions [2, 1 I-t7]. These methods accept boundary curves as input. Most of them have at least one of the following requirements: (1) the uniformity of the starlines (i.e. all the tangents of the starlines have an equal length and all the angles subtended by two consecutive starlines are equal); (2) further splitting and modification of neighboring surface patches; and (3) different handling of triangular and n-sided surfaces with n _> 5. To generate an n-sided surface with fixed boundary curves and starlines being individually generated without considering any of the above requirements, high degree surface patches should be

GC 1 Multisided B6zier Surfaces

used. In Jones [18], biquintic B6zier patches are used. However, this method cannot be easily extended to interpolating first order cross-derivative functions which is highly desired in practical applications. The method developed in Sarraga [19], which uses bisextic surface patches for generating n-sided surfaces with an odd number of sides, overcomes this limitation. N-sided surfaces can also be generated using rational patches with incompatible twists [20,21] using Gregory patches proposed in Gregory [22, 23] or by parametrizing surface patches singularly, as in Beeker [24]. Due to the singularities, surfaces generated by these approaches cannot be integrated easily into existing state-of-the-art CAD systems. Recursive subdivision of polyhedral meshes is proposed in Catmull and Clark [25]. It was later extended to interpolating vertices with normals in Nasri [26]. The resulting object is a faceted sculptured object without an analytical mathematical representation. There are also algebraic approaches to generating n-sided surfaces, e.g. in Li et al. [27], where high order functional spline surfaces are used. In this paper, a new method for generating a G C ~ multisided surface complex is proposed. In the new method, piecewise biquintic tensor product B6zier patches are used. These surface patches interpolate the given boundary curves and the vector-valued first order cross-derivative functions along these boundary curves. They join G C ~ along the starlines. The problem of twist-compatibility of surface patches at the center point is solved automatically by requiring normalcurvature continuity of the starlines at the center point and by constructing the twists of surface patches at the center point accordingly. In this manner, the inter-relationship among the starlines and the twists of surface patches at the center points is avoided. The method starts with the subdivision of the (up to quintic) boundary curves and the corresponding given (up to quintic) first order cross-derivative functions. Then, the center point is generated by a linear combination of corner points and the point which minimizes the sum of squared distances with the corner planes. Then, initial quadratic starlines are generated and are modified to be coplanar at the center point as in [4, 28]. The starlines are adjusted to be cubic, further modified to be normal-curvature continuous at the center point as in [4,28], and finally adjusted to be quartic. The twists of the surface patches at the center point are generated accordingly, so that the compatibility conditions imposed on the twists of the surface patches at the center point are automatically satisfied. By taking the coefficient functions as the quadratic functions in [4, 29, 30], the first order cross-derivative functions of surface

223 patches along the starlines are generated and the boundary and first layer B6zier control points of the surface patches are calculated. For each rectangular surface patch the remaining four interior control points are taken based on the computed control points according to the Coons-Boolean sum approach, as in [4, 29-31]. Examples for the generation of G C ~ triangular, pentagonal and hexagonal B6zier surfaces with given boundary curves and corresponding first order cross-derivative functions are given to illustrate the method developed. These surfaces, together with their neighboring tensor product B6zier patches, from which the given first order cross-derivative functions are obtained, are also shown. They form overall G C ~ surface complexes.

2. P r e p r o c e s s i n g

2.1. The Input As shown in Fig. 1, assume that the corner points of an n-sided surface S are {Pi: i = 1, 2 . . . . . n}. Let the boundary curves of S be {C~(t~):0 < ti-< 1, i = 1 , 2 , . . . , n } , and the first order cross-derivative functions of S be {D~(t~): 0 _< ti _< 1, i = 1, 2 . . . . . n}. C~(t~) and Di(ti) are given vector-valued polynomial functions with degrees less than or equal to 5. They are all degree-elevated to quintic (degree 5) functions.1 The boundary curves are oriented, so that C~ starts at the corner point Pi and ends at P~+I (see Fig. 1):2 Pi = Ci-1(1) = Ci(0)

(1)

Let the interior B6zier control points of C~ be {Xil, Xi2, Xi3, X~4}. Then

c,(t,) = PiBo'(t,) + X,IB (t,) + X,2BS (t,) + X~3B~(ti) + X~4B~(t~) + P~+lB55(t~)

(2)

where B'~(t) is the jth Bernstein basis function of degree m: B~(t) = ( 7 ) ( 1 - t ) " - J t

(3)

j.

The n-sided surface S is required to have compatible twists at the corner points Pv This is true for A degree m B6zier function with control coefficients{&: i = 0, 1, 2,..., rn} can be degree-elevatedto a degree m + I B6zier function with control coefficients m+ l-i

tl m + l

di+

i

di+l:i=O, 1 , 2 , . . . , m + l

}

.

m+l 2 The cyclic rule on the index is used in this paper, e.g. Po = P., and P~+I = P1.

X. Ye et al.

224 PI

Pn

Pn P2

/

X

-Din i Pi

C~(li)

Pi+l

Pi

Pi+t

9 : Boundary control points of the boundary curves; [] : First layer control points for the first order cross~lerivatives.

Fig. 1. The input of the surface generation process includes the boundary control points and the first layer control points for the first order cross-derivative functions along the b o u n d a r y curves.

blending vertices of solid objects. Furthermore, in order to represent the surface S as a piecewise polynomial surface to facilitate CAD data integration, the twists of S are required to be compatible everywhere on S in the entire n-sided polygonal domain. That is to say, O2S - -

~32S -

~?ti- l c3ti Ot~c~ti-1

(4)

at every point on S. The twists at the corner point P~ calculated from the first order cross-derivative functions of S along C~_ 1 and C~ should be the same. Therefore, as shown in Fig. 1, the twist control point Q~ for Pi should be unique, and 328

.

.

~tl- l t~tl

c~28

.

.

6~ti6~tl - t

25(Qi - x i_ 1, 4 - xil + Pi)

(5) Now, let the remaining two first layer control points of the n-sided surface S along the boundary curve C i be Y~I and Y~2. Then, the first order cross-derivative function Di(ti) of S along Ci(ti) is

Fig. 2. Subdivision of the boundary curves and the first order cross-derivative functions to obtain the two boundary curves and the first order cross-derivative funcions of the surface patches of the n-sided surface along these boundary curves, The center point P and starlines L~, together with the tangential and twist vectors (drawn in dashed lines), which are needed in tile surface construction, are also shown.

of S with respect to Cr i.e.

as the control points,

E,(t,) = Xi_i,4B~(ti) + Q~B~(ti) + YaB25(ti) + Y.,2B~(t0 + Q,+~B](t~) + Xi+l. lB~(ti) 2.2. Subdivision o f B o u n d a r y Curves and Cross-Derivatives

The subdivision of the boundary curves and the first order cross-derivative functions along these boundary curves into two curves and two vector-valued functions, respectively, provides two boundary curves and the first order cross-derivative functions of n rectangular surface patches {Si: i = 1, 2. . . . . n} of the n-sided surface S along the boundary curves, as shown in Fig. 2. For i = 1,2 . . . . . n, the quintic B6zier boundary curve C~(t~) is subdivided 3 into two quintic 3 A degree n B6zier functions with control coefficients {dj: i = 0, 1, 2, . . . . m} can be subdivided at a parameter t , into two degree n B6zier fianctions with the following control coefficients, respectively:

dkB'~(t,) : i = 00 I, 2 . . . . , n

D,(t,) = 5[E/(t,) - Ci(ti)]

(6)

k.k=0

and

where, as shown in Fig. 1, Ei(ti) is the quintic B6zier curve which takes the first layer control points

(7)

in-i

i E d,-~B'~-k(t*):i

= O, !, 2 .....

n .

GC i MultisidedB6zier Surfaces

225 P~

B6zier curves Cio(ti) and C i l ( t i ) at Mi = Ci(0.5). Then, the vector-valued quintic function Ei(t~) is subdivided into two vector-valued quintic functions Eio(ti) and Eil(ti) at ti = 0.5, and the first order cross-derivative functions of surface patches S~ and S~+ i along their boundary c u r v e s Cio(ti) and Cil(tl) a r e the following vector-valued quintic functions Dio(ti) and Did(h), respectively: Dio(t,) = 2.5[Eio(t,) -- Cio(t,) ]

(8)

Dil(ti) = 2.5[Ei~(t,) - Ci~(t,)]

(9)

Notice that the factor 2.5 comes from the factor 5 in Eq. (6) and the fact that the parametric domains of the surface patches are halved with respect to the original n-sided surface in each parametric direction.

,r, j [2

'

""

~

3

~"

Pz

1

"""

(a)

3. Generation of the Center Point The construction of the center point P is essential for the shape of the resulting surface patches, since P is involved in the generation of both starlines and surface patches later on. In the modeling methods in refs [ 11-17] for modeling n-sided surfaces, P is determined and fixed from the twist-compatibility conditions which will be given in Section 6. Our experience has shown that the quality of the resulting surface patches is very sensitive to P, and therefore should be taken in a predictable way. Thus, it is highly desired that P can be adjusted flexibly. Recall that in smoothing a vertex V of a polyhedral solid, the center point P of the vertex-smoothing surface S is usually taken as a linear combination of V and the average of the corner points of {Pi: i = 1, 2. . . . . n} of S, as shown in Fig. 3. That is to say, P=(1-a)

-1 ~ P i + e V

ni=l

(10)

A similar method can be used to generate the center point P of S in the general case. For the polyhedral solid, the vertex V is the intersection of the corner planes {II~, i = 1, 2. . . . . n}, as shown in Fig. 3. In the general case, these planes do not exist any more. But we can construct the corner planes IIi by taking the plane formed by Pi, X i - L 4 and Xi~ (Fig. 1). These planes do not generally intersect at one point. If they do, the intersection point will be taken as V. In general, V is taken to minimize the sum of the squared distance from a point to these planes as follows: ~, d 2 = ~ d2(V, Hi) = min i=i

(11)

i=1

Let Ni = (Nix, Niy, Niz)T be the unit normal vector of

P3

1"2

(b)

Fig. 3. (a) The center point in a vertex-smoothing surface; (b) the center point of a general n-sided surface by an approach similar to that in (a). the plane Hi, and Pi = (Pix, Ply, Piz) v. From Eq. (11), we have NV = G (12) where

i=1

i=l

i=1

i=l

i=l

i=l

i=l

i=l

i=l

N =

(13)

and G = (ZT=l pniN~x, ~7= i pniNi,, ZT= i pniN~z) T and pni= Pi" Ni. In most applications, the coefficient matrix N is full-ranked and a unique solution for V can be obtained from Eq. (12). However, special care should be taken for cases in which the solution of Eq. (12) is not unique or does not exist. An example

226

X. Ye et al.

of such a case is a single line parallel to all the corner planes II~, e.g. where l i t contain the sides of an n-sided prism. In this case, the solution set will be a line. The coefficient e in Eq. (10) is a shape parameter which can be used to adjust the shape of the resulting surface patches. It is usually chosen between 0.0 and 1.0. Our experience shows that e = 0.5 is usually a good choice.

4. Optimal

GC 1

Modification of Starlines

After the center point P has been generated, the starline L~(s~) can be taken initially as the quadratic curve with the endpoints taken as the center point P and the parametric middle point Mi = C~o(1) = C~o(0), and the tangential vector at M~ taken as Tm~ = Dio(1 ) = Dio(O), i.e.

L,(s,) = PBoZ(s,) + (M, + 89

+ M~B~(s,) (14)

Let T, = 2(M, - P) + Tmz

(15)

and U~ = {U~, Uiy, Uiz}T = Ti/JTII be the tangent and its unit direction of L~ in Eq. (14) at the center point P. They are optimally modified to be coplanar (GC ~) as in Ye [4], and Ye and Nowacki [28J as follows: E = ~ (Uf.N) 2 = rain ~=~

eigenvector. In our implementation 2 is chosen as the greatest real eigenvalue. After the unit normal vector N has been determined, the tangent T~ and the unit tangent U~ of L~ at P are modified to be their projection vectors in the tangent-plane at P (Fig. 4), i.e. U~ ~ = U i - (U~-N)N,

5. Optimal

= !

(17)

Using the well-known Lagrangr minimization principle, the above minimization problem can be converted to the following eigenprobl~m: (Uv - 2I)N = 0

(20)

Modification of Starlines

After the GC ~ modification of the starlines at P, the starlines are adjusted correspondingly to interpolate the newly generated coplanar tanget T~~w in Eq. (20), which we denoted as T~. Correspondingly, we denote U}'~w in Eq. (20) as Ui, The starline becomes the following cubic curve: ! 3 Li(si) = PB~(si) + (P~ + ~Ti)Bl(si)

(18)

where

GC 2

T~*w = !T~iU~

(16)

with the constraint that + N, +

Fig. 4. Optima!ly GC ~ modification of startines at the center point P: (1) the normal vector N of the tangent plane at P is optimally determined by solving an eigenvalue-eigenvector problem; (2) the tangents {Ti: i = I . . . . . n} are modified to their projections in the tangent plane.

+ (M, + 89

+ M~B~(s,) (21)

\ Let i=0

i=0

i=0

T T / = 6(Mi - P) - 4Ti + 2Tmg

(22)

(19)

=

i=O

i=0

i=0

i=O

i=O

i=O

is a 3 x 3 symmetric matrix, 2 is the Lagrange factor and I is the 3 x 3 identity matrix. It is clear from Eq. (18) that 2 must be one of the real eigenvalues of the matrix (Tr,4 and N is the corresponding unit * Since [7~ is a 3 x 3 matrix, it is guaranteed that [7T has at least one real eigenvalue.

and U U i = {UUix, UU~r, UO}~}T = TTi/IT~I 2 be the second order derivatives and its normalization with respect to the tangent of L i at P. They are optimally modified to be normal-curvature continuous (GC 2) as in [4, 28] as follows. First, two perpendicular unit vectors fJo and fJ1 in the tangent-plane at P are fixed, e.g. taken as U o and N x U o. Then, the projections p~ and ql of U~ onto fYo and U1, respectively, are calculated. The coefficients of the second fundamental form of the

GC' Multisided B6zier Surfaces

227

Fig. 5. Optimally normal-curvature continuous modification of curves at the center point P: (1) the second fundamental form of the associated surface S at P is optimally determined by solving a minimization problem; (2) the normal curvatures of the tangents to S at P are computed and the curves are modified to have these normal curvatures to S at P.

associated surface s at P are obtained by minimizing the sum of the squared errors of the normal projections of UU i, i.e. (dkl)2 = ~ ( k , - UU~'N) 2 = rain i=0

By denoting TTp ~win Eq. (28) as TT~, the final starlines are taken as

Li(sl) = PB~(s,) + (P~ + 88 ! * + (Pi + 89 + 7~TTi)B2(si) (m i + 88 + MiB~(s,)

(23)

i=0

where k~ is the normal curvature of U~ at P:

ki = p20~ 1 + p~q~(2912) +

q2922

(24)

and dk~ is the difference between the normal curvature ki and the projection U U i ' N (Fig. 5) and {g11, g12, g22} are the coefficients of the second fundamental form of the associated surface at P. Therefore, g11, 2gla and g22 are the solution of the following 3 x 3 linear equation system: (25)

Uo6 = B.

In most applications the coefficient matrix G is full-ranked and Eq. (25) has a unique solution. However, it is not clear if Eq. (25) is guaranteed to be solvable on geometric grounds. The coefficient matrix G might be singular in some cases, although we have never experienced such situations. As an important byproduct, after obtaining the coefficients g11, g12, g22 the Gaussian (K) and mean (H) curvatures of the n surface patches at P can be calculated as follows: 6

K = gllg22 - g~2 n = 89

where

E p4 i=1

~, P~qi i=1

P~qi i=l

~i=1

i=l

~ p2q2 i=i

~p{q2 i=1

~. P~q~ ~ piq3

(26)

i=1

piq 3

(29)

+ g2~)

(30)

From these curvature measures we can predict the quality of the resulting surface patches at a very early stage. If necessary, e.g. in the case of K < 0, we may change the factor a in Eq. (10) to better choose the center point P.

~" q~

6. Twists and Twist Compatibility

i=1

is a 3 x 3 symmetric matrix and

~ piqi(UU,'N), Bn = {1:1 ~ P/2(UUi'N)' i=1 q~(UU~'N)

(27)

i=1

Then, UU~ and TTi are modified as follows: UU~ ~w = kiN;

TT~~w = kilTil2N

(28)

5 The normal-curvature continuity of a set of curves meeting at a c o m m o n point P is defined by the curvature continuity of each curve with a so-called associate surface at P. For more detail, see

refs [4, 28].

The compatibility of the twists of surface patches at the center points is the essential problem in generating GC 1 n-sided surfaces by composing B6zier surface patches. Different solutions to the compatibility conditions result in a different number of surface patches with different parametric degrees. Mathematically, the problem is to ensure the independence of the differentiation sequences of the 6 With the current parametrization of the associated surface at P, the coefficients of the first fundamental form of the associated surface are"

e11=Uo'Uo=l

e12=fJo'fJl=0

e22=fJ,'fJ,=l

X. Ye et at,

228

second order mixed partial derivatives (twists) of all the surface patches {S~ (si, s~_ a): i = 1, 2. . . . . n} at the center point P (see Fig. 2). In other words, at P

Vi-

O2Si

OzSi

OSi-leSi P - - ~S/~S/_I P

(31)

To see the problem in more detail, let us first consider the G ~ continuity of S~ and S~+ x at the center point P and along the starline Li(si) (Fig. 2). At the point P, because of the coplanarity of the tangents of the starlines, we have T i + 1 = eiTi_ 1 + f~T i

(32)

where e~ and f~ are scalars which are determined by the signed areas

al = area (P, P + Ti- 2, P + Ti); b i = area(P, P + Ti-~, P + Ti+~) as follows [11]: ai + 1 e i

--

; f~-

bi

ai

ai

elez"'en_le

n = (--1)"

(33)

Therefore, (34)

Along the starline L,(si) we have 0Si+ 1(0, Si)

OSi(si, O)

- Ei(si)-

~si + 1

+ Fi(s,)Li(si)

(35)

&i -

where Ei(sl) and F~(s~) are coefficient functions with Ei(0) = ei and F~(0) = f , and the symbol' denotes the first order derivative. 7 Differentiating Eq. (35) with respect to s~ and then letting si = 0, we have Vi+~ = e~Vi + fiTT~ + wiTi-1 + h~Ti

(36)

where wi = E;(O) and hi = F;(O). Recursively using Eq. (36) for i = n, n - 1 , . . . , 1, letting d, = 1 and di = d~+~ei+l; i = n - 1, n - 2 , . . . , 0 , and using Eq. (34), we have (1 - (-1)")V1 = ~ di(f~TTi + wiTi-1 + hiTi) i=1

(37) If n is an odd number then V~ can be determined by Eq. (37) and {V~: i = 2, 3. . . . . n} can be obtained by recursively using Eq. (36). Otherwise, if n is an even number then we obtain the following so-called twist-compatibility condition: 7

Ei(si) < 0 with the current orientations of the surface patches.

d~(f~TTi + w~Ti-i + lhTi) = O

(38)

i=1

Therefore, the second order derivatives of the starlines and the first order derivatives of the coefficient functions at the center point P are interdependent and cannot be chosen independently. From Eqs (37) and (38) the twists of the surface patches and the second order derivatives of the starlines at the center point P can be solved. In this manner, surface patches with poor quality can be generated. Furthermore, there is no shape parameter to modify these surface patches. We present here a constructive method to ensure Eq. (36) and thus Eqs (37) and (38). Since in our case, the starlines are normal-curvature continuous at P, and the second order derivatives of the starlines have only components in the direction of the normal vector N (see Eq. (28)), if we choose w~ = hi = 0 and the twists as Vi = [ P i - l P i g l l -t- (Pi-lqi + Piqi-1)g12

+ qi- lqig22]N

(39)

then both sides of Eq. (36) have zero projections onto the tangent-plane at P. The normal components of both sides of Eq. (36) are also equal. This can be verified from Eqs (28) and (39) and from the relationship between { ( e ; , f ) : i = 1,2 . . . . . n} and {(p~, qi):i = 1, 2 , . . . , n}, which is induced by representations of the tangents in terms of U0, U1 and in Eq. (32). Our method for determining TT~ by Eq. (28) and Vi by Eq. (39) avoids the complicated interrelationship between the staflines, the twists and the coefficient functions.

7. Generation of the Resulting Biquintic Btzier Patches We are now ready to generate the first order cross-derivative functions of the surface patches along the starlines. Remember that the coefficient functions E~(si) and Fi(s~) should satisfy the following conditions (see Section 6): Ei(0) = ei E~(1) = - 1 F~(0)=f

5(1)=0

E~(0) = E~(1) = 0

(40)

F~(O)=F~(1)=0

(41)

It is natural to construct two cubic Hermite polynomial functions for E~(s~) and F~(s~). But in this case, bisextic polynomial surface patches must be used. To model the n-sided surface S with possibly low degree surface patches, we adopt the method used in refs [4, 29, 30]. The essence of the method is to use the quadratic rational coefficient functions with the

GC ~ Multisided B6zier Surfaces

229

denominator w(s) = (1 - s) 2 + s z and the concept of ,basic first order cross-derivative functions to convert the rational computation into polynomial computation. That is to say, E~(sl) =

ei(1 -- si) 2 -- s~ f/(1 -- si) 2 w(si) , F~(sl)w(si) (42)

and

aSi(s. O) - [(1 - sl) 2 + s/2]D,(si)

(43)

~si - 1

aSi+ 1(o, si) --

[ei(1

--

s2]DB(Si)

si) 2 --

~si + 1

(44)

4- f~(l - - si)2L;(si)

where DB(sl) is the so-called cubic basic first order cross-derivative function along the starline Li(s~) as follows: DB(si) = T i_ 1B3(si) + l(5Ti_~ + Vi)B3(si) + Vm,)B~(si) + DmiB](si)

89

As shown in Fig. 6, after degree-elevation of the starlines from quartic to quintic we obtain the corresponding boundary Brzier control points of the surface patches. The first layer Brzier control points of the surface patches with respect to the starlines can be generated by adding the corresponding boundary control points and one-fifth of the control vectors of the first order cross-derivative functions along the starlines. For every surface patch there are still four interior Brzier control points which are not involved in the G 1 continuity of the surface patches. They are free and remain to be determined. They can be chosen and adjusted by the user. We present here a method according to refs [4, 29-31] using the Coons-Boolean sum scheme. For a biquintic Brzier patch with known B6zier control points { Q i j , (i,J) e [0, 5] x [0, 5] [2, 3] x [2, 3]}, the interior four unknown Brzier control points can be chosen from these known control points as follows:

Qij = (45)

~

1=0.1,4,5

-

~i(l)Q, +

~, ~

~

qgj(k)Qkj

k=O, 1,4,5

~),(1)4)i(k)Qkt

(49)

k,1=0,1,4, 5

where Din,

=

-

C~o(1

) =

-

C~1(0

)

and Vmi = -D~o(1) = - D h ( 0 ) (see Fig. 2). Therefore aSi(s,, 0) _ T~_ iBm(s,) + (T,_! +

1vi)e5(si)

+ ~o(Ti- 1 + 5Omi + Vmi)BzS(s,) + t ( O m i + 5Ti-, + Vi)B53(si) + (Dmf + 89

+ DmiB5(s,)

(46)

To compute the vector-valued function in Eq. (44), we notice that from Eq. (29), L~(s,) = T,Bo3(S,) + (T, + 89 + TTm, B3(si) - Tm, B33(si)

(47)

where TTmi = 4(P - Mi) - 2T i + Tml - ATTi. By using Eqs (32), (35) (with gi = hi = 0), and (47), from Eq. (45), we have aSi+ I(0, si)

c3si+ 1 = T,+tB~(s~) + (Ti+ ~ + ~Vi+~)B~(si)

+ 11o[ei(5Dmi + Vmi) - Ti- 1 + fiTTm,]B3(si) + ~o[eiDm~ - (5T,_ 1 + Vi) - fiTmi]B~(si) -

(Din, + 89

- DmiB~(s,)

(48)

Fig. 6. The construction of the Brzier control points of the surface patches. Those points marked by a solid circle are the given boundary control points; those marked by a solid square are the first layer control points determined by the given first order cross-derivative functions along the boundary curves; those marked by a hollow circle are the center point and the control points of the starlines; those marked by a hollow square are the first layer control points determined by the first order cross-derivative functions along the starlines; and those marked by a hollow square containing a circle are those control points that are not involved in the Gl-continuity of the surface patches. They are free, and can be taken as linear combinations of the control points already obtained by the Coons-Boolean sum approach.

230

X. Ye e~ al.

with ~b2 = (-0.3, t.0, 0.0, 0.0, 0.5, -0.2), ~b3 = (-0.2, 0.5, 0.0, 0.0, 1.0, -0.3)

8. Examples This section shows some GC ~ multisided B6zier surfaces and surface complexes generated by the

method developed in this paper. The input to these examples are the boundary mesh curves and the first order cross-derivative functions along these boundary curves. The surfaces are composed of n biquintic B6zier surface patches. The shape parameter ~ in Eq. (10) for these surfaces is 0.5. The figures are displayed by PgaXn'ELES, a geometric modeling and interrogation system developed in the MIT Ocean Engineering Design Laboratory, see Abrams et at. [32]. Figure 7 shows a triangular surface composed of three biquintic tensor product B6zier patches and its offset surface. Figure 7(a) shows the triangular surface and Fig. 7(b) shows an offset of the surface. The position continuity of the offset surface verifies that the original triangular surface is GC ~. Curvature analysis shows that these B6zier surface patches are convex surface patches.

I

(a) A G C 1

triangular surface. 3'

(a) Control meshes of a G C ~" pentagonal surface.

(b) An offset of the triangular surface. Fig. 7. A triangular surface composed of three bJquintic Brzier patches and its offset surface. The position continuity of the offset verifies the GX-continuity of the original triangular surface.

(b) The pentagonal surface. Fig. 8. A pentagonal surface composed of five biquintic B~zier patches and their control meshes.

GC ~

Multisided B6zier Surfaces

231

Figure 8 shows a pentagonal surface composed of five biquintic tensor product B6zier patches. Figure 8(a) shows the control meshes and Fig. 8(b) shows the pentagonal surface. Figure 9 shows a hexagonal surface composed of six biquintic tensor product B6zier patches. Figure 9(a) shows the control meshes, and Fig. 9(b) shows the hexagonal surface. Figure 10 shows an example of a hexagonal surface blending three triangular surfaces along three boundary curves. These surfaces together form an

9

9 ..............,,......._.....,. .

i..

.

.. .~.-

:

"~'""~''"~"

,.._.~ .........

!

-j'

~-~

.4

~o

;'

)*:i.o

~ "

d

Fig. 10. A hexagonal surface blending three triangular surfaces. 9. . -

.

"

9

.L

"

9 i.'._.

~

...~

....... ;~- ..i

4

""

' *

*

'.

.':" " '-..

. ~

"d

overall G C 1 surface complex. Figure 11 shows a different view of their neighboring rectangular surfaces, from which the first order cross-derivative functions of the triangular and hexagonal surfaces are obtained. The new surface complex in Fig. 11 is also G C 1.

(a) Control meshes of a

GC

1

hexagonal

surface.

A more complicated example is shown in Fig. 12, in which a hexagonal surface and a pentagonal surface, which join at a corner point, are connected by three triangular surfaces. These surfaces form an overall G C 1 surface complex.

9. Summary

(b) The hexagonal surface. Fig. 9. A hexagonal surface composed of six biquintic B6zier patches and their control meshes.

In this paper, we have developed a new method for generating G C 1 multisided B6zier surfaces. The method generates piecewise biquintic tensor product B6zier patches which join each other with G 1continuity along the starlines and which interpolate the given vector-valued first order crossderivative functions along these boundary curves. The problem of twist-compatibility of surface patches at the center points is solved by requiting normalcurvature continuity of the starlines at the center points and by the way the twists of the surface patches at the center points are constructed. In this manner, the inter-relationship among the starlines and the twists of surface patches at the center points is avoided.

232

X. Ye et al.

Fig. 11. An overall G C 1 surface complex consisting of a hexagonal surface which blends the three triangular surfaces shown in Fig. 10, shown here from a different view, and their neighboring rectangular surfaces.

Fig. 12. An overall G C 1 surface complex consists of a hexagonal surface, a pentagonal surface and three triangular surfaces.

GC 1

Multisided Brzier Surfaces

The main features of the method are: 1. The surface patches are compatible with existing solid modelers. Therefore, no extra software is needed for the interrogation, visualization or exchange of the surface data. 2. Compared with similar methods using bisextic patches, it uses lower degree surface patches and can be used in generating multisided surfaces with an arbitrary number of sides. 3. Compared with similar methods using bicubic patches, it interpolates not only the given boundary curves but atso the vector-valued first order cross-derivative functions. Furthermore, it offers more flexibility by allowing variation of the degrees of the given cross-derivative functions, and the degrees of freedom in the generation of center points and starlines. The method can be used in various modeling situations such as: filling of n-sided holes with first order cross-derivative boundary conditions. 2. G C 1 multisided blending of rectangular and multisided surfaces. 3. G C 1 smoothing of corners of polyhedral solids. 4. The generation of overall G C 1 surface complexes over irregular polyhedral line and curve meshes. 1. G C I

The idea of requiring higher order continuity of starlines at the center points has been extended to generate G C 2 multisided surfaces in [4, 33].

Acknowledgments The basic idea of this work was developed when the first author was pursuing his PhD at the Technical University of Berlin, Germany. The first author is very grateful to Prof. J. Hoschek for his careful comments on his PhD thesis. He would like also to thank Prof. C. Chryssostomidis for his support. Mr S. L. Abrams assisted in editing the paper. Finally, partial funding for this work at MIT was obtained from MIT Sea Grant College Program and the National Science Foundation under grant No. IRI-9224640.

References 1. Varady, T. (1987) Survey and new results in n-sided patch generation, The Mathematics of Surfaces II (Martin, R. R., Editor). Oxford University Press, Oxford, 203-235 2. Gregory, J. A.; Lau, V. K. H.; Zhou, J. (1990) Smooth parametric surfaces and n-sided patches. Computation of Curves and Surfaces (Dahmen, W., Gasca, M. and Micchelli, C. A., Editors). Kluwer Academic Publishers, Dordrecht, 457-498

233 3. Du, W.-H.; Schmitt, F. J. M. (1990) On the G~ continuity of piecewise B+zier surfaces: a review with new results, Computer Aided Design, 22(9), 556-573 4. Ye, X. (1994) Construction and Verification of Smooth Free-Form Surfaces Generated by Compatible Interpolation of Arbitrary Meshes. Springer, Berlin 5. Sabin, M. A. (1983) Non-rectangular surface patches suitable for inclusion in a B-spline surface. Proceedings of EUROGRAPHICS'83, (ten Hagen, P. J., Editor). 57-69 6. Loop, C. T.; DeRose, T. D. (1989) A multisided generalization of B~zier surfaces, ACM Transactions on Graphics, 8(3), 204-234 7. Loop, C. T.; DeRose, T. D. (1990) Generalized B-spline surfaces of arbitrary topology, Computer Graphics, 24(4), 347-356 8. Varady, T. (1991) Overlap patches: a new scheme for interpolating curve networks with n-sided regions, Computer Aided Geometric Design, 8, 7-27 9. Hahn, J. M. (1989) Geometric continuous patch complexes, Computer Aided Geometric Design, 6(1), 55-67 10. Hrllig, K.; Mrgerle, H. (1990) G-splines, Computer Aided Geometric Design, 7, 197-207 11. Liang, Y.; Ye, X.; Fang, S. (1988) G 1 smoothing solid objects by bicubic B~zier patches. EUROGRAPHICS'88, (Duce, D. A. and Jancene, P., Editors). North-Holland Publishing Company, Amsterdam, 343-355 t2. Peters, J. (1990a) Smooth mesh interpolation with cubic patches, Computer Aided Design, 22(2), 109-120 13. Peters, J. (1990b) Local cubic and bicubic C 1 surface interpolation with linearly varying boundary normal, Computer Aided Design, 7, 499-516 14. Peters, J. (1993) Smoothing free-form surfaces over irregular meshes generalizing quadratic splines, Computer Aided Geometric Design, 10, 347-361 15. Wijk, J. J. V. (1986) Bicubic patches for approximating non-rectangular control-point meshes, Computer Aided Geometric Design, 3, 1-13 16. Gregory, J. A.; Zhou, J. (1994) Filling polygonal holes with bicubic patches, Computer Aided Geometric Design, 11, 391-410 17. Zhon, J.; Lau, V. K. H. (1994) An arbitrary rectangular patch network scheme for free-form surface modeling. IMA Mathematics of Surfaces VI (Mullineux, G., Editor). Claredon Press, Oxford, UK, 397-410, September 1994 18. Jones, A. K. (1988) Nonrectangnlar surface patches with curvature continuity, Computer Aided Design, 20(6), 325-335 19. Sarraga, R. F. (1987) G~ interpolation of generally unrestricted cubic Brzier curves, Computer Aided Geometric Design, 4(1-2), 23-39 20. Chiyokura, H.; Kimura, F. (1983) Design of solids with free-form surfaces, Computer Graphics 17(3), 289-298 21. Chiyokura, H. (1987) An extended rounding operation for modelling solids with free-form surfaces, IEEE Computer Graphics and Applications, 7(12), 27-36 22. Gregory, J. A. (1974) Smooth interpolation without twist constraints, Computer Aided Geometric Design (Barnhill, R. E. and Riesenfeld, R. F., Editors). Academic Press, New York, 71-88 23. Gregory, J. A. (1983) C a rectangular and non-rectangular surface patches. Surfaces in Computer Aided Geometric Design (Barnhill, R. E. and Brhm, W., Editors). North-Holland, Netherlands, 25-33 24. Beeker, E. (1986) Smoothing of shapes designed with free-form surfaces, Computer Aided Design, 18(4), 224-232

234 25. Catmull, E. E.; Clark, J. H. (1978) Recursively generated B-spline surfaces on arbitrary topological meshes, Computer Aided Design, 10(6), 350-355 26. Nasri, A. (1991) Interpolation on irregular networks with normal conditions, Computer Aided Geometric Design, 8, 89-96 27. Li, J.; Hoschek, J.; Hartmann. E. (1990) G"-1 functional splines for interpolation and approximation of curves, surfaces and solids, Computer Aided Geometric Design, 7(4), 209-220 28. Ye, X.; Nowacki, H. (1995) Optimal tangent-plane and curvature continuous modification of curves at a common nodepoint. Advances in Design Automation 1995: Proceedings of the 1995 ASME Design Engineering Technical Conference (Azarm, S. et al. Editors). ASME, September 1995, 49-56 29. Ye, X. (1995a) Generating B6zier points for curves and surfaces from boundary information, Computer Aided Design, 27(12), 875-885 30. Ye, X. (1995b) G1 smooth interpolation of curve meshes using rational B6zier patches. Proceedings of the 4th International

X. Ye et aL

31.

32.

33.

34.

35.

Conferences on CAD and Graphics, Wuhan, China, October 1995, SPIE (in press) Ye, X.; Nowacki, H. (1994a) G1 interpolation of rectangular cubic curve meshes using biquintic B6zier patches. IMA Mathematics of Surfaces VI (Mullineux, G., Editor) Claredon Press, Oxford, UK, 429-451, September 1994 Abrams, S. L.; Bardis, L.; Chryssostomidis, C.; Patrikalakis, N. M.; Tuohy, S. T.; Wolter, F.-E.; Zhou, J. (1995) The geometric modeling and interrogation system Praxiteles, Journal of Ship Production, 11(2), 116-131 Ye, X.; Nowacki, H. (1994b) Ensuring compatibility of G2-continuous surface patches around a nodepoint, Computer Aided Geometric Design (in press) Goodman, T. N. T., Lee, S. L. (1987) Geometrically continuous surfaces defined parametrically from pieeewise polynomials, (Martin, R, Editor) The Mathematics of Surfaces II, Clarendon Press, Oxford, 343-361 Majid, A. A. (1991) Smooth piecewise surfaces on arbitrary polyhedral mesh, PhD thesis, Universiti Sains Malaysia