Methods for Generating and Manipulating 3-D Freeform Curves 利用統計を見る

(1)

Original Paper

Methods for Generating and Manipulating 3-D Freeform Curves

RyoKAGAMI MunetoKUBOTA SusumuFURUKAWA MakotoITOH

28. 8. 1998 received

Abstract Atechnique for generating freeform clirves is presented． And a method to determine the control points for a smooth curve passing through given points without solving simultaneous equations is discussed． The features of the methods are as follows． 1．Afreeform curve is generated by subdividing a given control polygon recursively． 2．The curve shape can be changed locally on any step of the subdividing procedure． 3．Any control point， which is determined for a smooth curve passing through a given point sequence， can be moved without changing the given points． Some illustrative curves generated by the methods’are shown and are compared with the

ones obtained by solving the simultaneous equations to determine the relationship between

び given polnts and control points． 1．Introduction The importance of a computer aided geometric de． sign（CAGD）system has increased amazingly in recent years・ The problem of defi ning and processing solidgeo17netric models of objects is especially important in this field． So，various researches have been developed and Inany solid modeling systelns have been made［1］． The system BUILD［2］，which was made by I．C、Braid， and TIPS−1［3］ constructed by N．Okino，are typical solid modelers among them． The probiem related to constructing solid models of objects with high quality curves or surfaces such as car bodies and brooches is important too． Three of the most widely used methods for curves or surfaces are B6zier，the B，spline and the NURBS（Non− Uniform Rational B−Spline）ones［4］． These methods have useful and desirable properties to define，manipulate and generate freeform curves and surfaces as follows．（1）Acurve shape approximates a given control polygon ’Department of Mechanical Systems Engineering 軸Koyo Electronics工ndustries Co，．Ltd．1230−1 Nlshiide，Oh▲zumi， Kitakoma 409−1501 ”“bhukyou University，101 Tokodachi， Kaizu， Toyota 470−0393 shape． For example，when a vertex of the control polygon is moved in a direction，the curve will telld to follow the llew position of the vertex．（2）Acurve hes completely within the convex hull of the COntrol vertiCeS． Moreover，aB−spline curve has a local property，ie，，even if a control poillt is moved，the curve segments far from this control poil）t are llot affected．一一 There are usually two ways for constructing curves and surfaces． One is that curves are determilled by giving control polygons． This method enables us to control a curve’shape as an artist，a stylist or a designer，because the curve is associated with the control polygon and the curve shape can be changed according to our intuitive feelings．・ The oth6r method is a curve fitting technique，in which curves are constrained to pass through given data points．This method will be useful to design functional freeform shapes，such as turbine blades and screw pro− pellers． According to this procedure，the control polygoll for a、 curve passing through a given point sequence is deter＿ mined first． Then the curve defined by the control poly一

(2)

gon is generated in the same manner as the first one． In the later case，the simultaneous equations that rep． resent the relationship between the given points and the control polygon have to be solved． This requirement is subject to such disadvantages，as time consuming to N get the solution and sometimes resulting curves with un． wanted undulations． This paper resQlves the problem in the two stepsl 1．a technique for generating a freefornl curve by subdi．− viding a control polygon recursively． 2．amethod for determining a control polygon for a curve passing through given points． These methods have the following advantages． 1）The curve shape can be locally changed on any step of the subdividing procedure． 2）Any control point can be moved without changillg the given points to pass through． Some illustrative examples of curves are shown and compared with ones obtained by solving the simultane． OUS eqUat10nS． 2．A Method for Generating a Curve In this section，a new method for a freeform curve which mimics a given control polygon is introduced． This subdivides． a control polygon and gets a new re− fined contro｝polygon recursively，until it becomes sufE− ciently close the curve segment． This type of approach to generating smooth curves or surfaces is called subdivision method or the knot inser− tion method in the case of B−spline curves． Chaiken proposed a method based on the idea of the recursive insertion of pseudo−knots into a B−spline． curve［5］． The process consists of starting with a polygon and successively knocking out the corners，until the re＿ fined polygon approximates a freeform curve suflliciently， This polygon converges to the B−spline curve according to the original polygon at the limit， Methods for surfaces are presented in the references［6− 10］．Doo and Sabin presented a subdivision method and discussed the behavior of the vicinity of the extraordi− nary point of the surface［8］． Narsi developed the methods for controlling the boundary curves of surfaces，interpolating points on ir− regular networks and determining the surface／surface in． tersections for the subdivision surfaces［9］． Micchelli and Prautzsch proposed a subdivision al− gorithm for the surfaces of rectangular and triangular Po Pl P。i

P2

P2 P2

P23

Fig．1The Recursive Subdivision Method fbr Generating Curves from a Control Polygon patches［10］． The algorithm is an extension of their curve generation method presented before， The new algorithm on the similar idea mentio．ned above is presented in this paper， Let，s denote the control vertices ｛」『b，P1，・・㍉・pn｝ as shown in Fig．1，whrer n is the number of the edges of the control polygon． The procedure generating a freeform curve is as follows． 1．The midpoint of each edge is designated by the follow． ing expression（Fig．1）．

Pi，i＋1→Pi＋Pi＋1）（i−・，1，・ヂ・・−1）（1）

ゾ 2．A new vertex、Pi associated with the point」Pいs deter． mined by the expression （2）．

ぢ＝君一1，沽、荒＋P”叶1，＠一輻・，…，−1）（・）

Here， w represents a weighting Parameter to control the curve shape． 3、VVe shall consider the point sequence ｛PO，PO，i，pl， Pl，2，一・，Pi＿1，i，Pi’， Pi，i＋1，…，Pn｝・・th・ new control polygon． If this control polygon is suffi− ciently close to the curve，this curve generating procedure will be quitted and we can consider that the control poillt sequance converges to the curve． Otherwise，the above procedures（1）and（2）are recursively iterated． This．type of a curve has the useful properties to gen− erate and manipulate the curve shape iteractively as fol− 10WS．（a）Who｝e curve lies inside the conv．ex hull polygon of the COntrOl VertiCeS．

(3)

December 1998 No．49 （b）The curve shape can be changed locally，ie．，even if the position of a control戸oint changes，the effect does not reach over the third’s from it． The property（a）is the same as that of B6zier and B．spline curves and（b）is the same as the B．splille，s． Now we shall investigate the other properties of the curves．（i）Convergent points Substitutingノ）i＿i，∠and 君，輌＋1 by 君＿1 and Pi＋1 re＿ spectively， the expression（2）becomes

互＝Pi−1＋（i6忽テ＋P’＋1・

（3） We shall consider that Pi moves to Pi’after a subdi− ・i・i・n・fth・gi・・n・・nt・・l p。lyg・n，and th・t’o、’ 香Eve・ tl_{Pi at the next step． Generally，we shall consider that} th・p・i・tヰm−1）m・ves t・巳（m）・ft・・th・m，th・・bdi・i− sion． Here，m represents the number of iteration of this ・ubdi・i・i・n p・・ced・・e． Th・n we exp・ess th・p・i・t巳（m）弓s

牢）＝ 1

｛Pi＿1（m−1） 2（2＋w）十（2十2ω）」隅（m−1）十Pi＋1（m−1）｝． H・・e，the symb・1・ぼm）・・e sub・tit・t・d・by・pi（m）． we can conclude that pi converges to Ri the expression（5）， Pi＿1十（2十w）・Pi→一∫⊃〉＋1 品＿ 4十ω （4）

Now

represented by （5） as m−→OO．（ii）Equation of the curves Consider the case of w＝2， The above expression（5） is reduced to the expression

R・一君一1＋4

s＋1（i＝ 1，・，・一，・−1）・（・） Namely，the control point Pi is reduced to a point oll the uniform 3rd order B−spline curve， And it can be easily seen that the new control point Pi，i＋1 represented by the expression（1）converges to a point on the same B−spline curve too． So，we can say that this subdivision procedure is equivalent to a knot insertion one in the case of the uniform 3rd order B．spline curves． Therefore，the equation coincides with that of the uniform 3rd order B−spline curves，whenωニ2， Similarly，it also coincides with the uniform 2nd order B−spline curve，when w＝0． However，the curve here does not seem to be expressed with a linear combination of P。 Pl 日1

信ω

P，r2ノ Plt P， r2ノ θηノ P2r2ノ

々2P，r17

Fig．2 A Transitive Control Point Sequence P2 these uniform 3rd order and 2nd order B−spline curves，（iii）Estimation of the error In order to estimate the difference between the m，th coiitrol polygon and the convergent one，we shall consider three control points as shown in Fig．2．ノ The points Po，Pi and P2 move to the points Po，1，Pl and Pl，2，which are designated by Po（1），Pl（1）and P2（1） respectively． Then the points Po（m），P1（m）and P2（m） are determined by the three successive points Po（m− 1），Pl（m−1）and P2（m−1）as expressed in Pb（m＿1）＋Pl（m−1） P。（m）＝ 2 1 Pl（m）＝｛P・（m−1） 2（2＋ω）十（2十2w）」）1（m−1）十P2（m−1）｝（7） Pl（m−1）十P2（m−1） P2（m）＝ 2 − These are the simultaneous difference equations with re− spect to the three unknown functions Po（m），Pl（m）and P2（m）and are solved as follows． Pl（in）P°（°）＋（2：’lf？｛lw．）1，（°）＋P2（°） P°（°）一芸（三゜）（2（，k．））m・（8） Here，Pi（0）（i＝O，1，2）are the initial given points Po，1『1 and P2 respectively． Since the convergent point of point Pl is the same as point Rl in expression（5），the differehce between Ri and ．P1（m）becomes Po 一 2 Pi＋P2

4十w

（ w2（2＋ω））∵ （9）

(4)

If w and m equal to 2 and 5 respectively，the difference becomes only about one thousandth of the vector（Po− 21つ1−←P2）／6． This means that we can get the refined polygon sufli− ciently close to a freeform curve only by 5 iterations of the recursive procedure．（iv）Practical use Practically，we had better use expression（5）to draw acurve with a given control polygon． Namely，after sev． eral iterations of the subdivision procedure，we calculate the convergent point sequence Rl，R2，．．’，Rm． Then we draw the curve with using them． Hereγηis the number of the points on the curve． 3．Curves Passing Through Given Points In this section，a new method to determine a control polygon of a smooth curve passing through given points is discussed， Expressioll（5）is changed into ． Pi＿1十（2十w）Pi十Pi＋1＝（4十w）Ri，（i＝1，2，・■・，n−1）．（10） These n−1expressions are the equations for determining control points Pi for thg smooth curve passing through agiven point sequence Ri（i＝0，1，2，’・㍉n）． But，the number of the equations are insufficient to solve，because the number of control points is greater than that of equations． So，we impose such boundary conditions on the starting and the end points as Po ＝ Ro and pn ＝ Rπ，respectively． Usually，these simultaneous equations can be solved in relatively short time． But，there are some．disadvantages in this method as follows． 1．It takes much computation time to solve the simulta． neous equations with regard to the control polygon of the smooth surface passing through given points． 2．The curves passing through given points have unex＿ pected undulations． 3．The curves have few fiexibilities． For examples，the curve shape can be modified only by changing the given points under this procedure， 4．When the number of given points is changed or any point of them is repositioned，the simultaneous equations have to be re＿solved again． In this section，a new method to overcome those disad− vantages，which can determine the control points without solving the simultaneous equations，is presented．

ρひ7

ρ2y rfneeノ Fig．3The case where a curve need not pass through the even numbered poillts Now，we shall consider the case where even numbered points are not necessary to be passed through（Fig．3）． The expressions（10）can be re−written to P2」＿3十（w十2）P2」＿2一トP：∼ゴ＿1 ＝（4十w）R2ゴ＿2 （unc・nstrαineの P2ゴ＿2→一（w一ト2）P2ゴ＿1十P2ゴ＝（4−Fw）R2」＿1 （11） ∫）2」＿1一ト（w十2）P2」十P2」＋1 ＝（4十w）∫∼2」（uηc・nst・ained） This means that the even numbered expressions are negligible． Then，expressions（11）can be reduced to … P2」＿3 ＝ P2」＿1 乃ゴ＋1 1

2十w

1 ｛（4＋ω）R2ゴー3’一 P2」．4 一 P2ゴ．2｝

2十w

1 ｛（4十w）R2ゴ＿1−∫）2ゴ＿2−P2ゴ｝（12）

2十ω

｛（4−←w）R2」＋1−P2」、−P2ゴ＋2｝ These expressionS me’an that P2j can be chosen arbitrar− ily． Then the odd numbered control points P2ゴ＿1（」＝ 1，2，・−tn／2）are determined automatically We shall call these even numberCd control points P2｝ additional control points，and the other control points

(5)

December 1998 Reports of the Faculty of Engineering， Yamanashi University _No．49

Pn．1

_{島輌侮・ノ}

1・n一アRf， n ／？2，0 Oo，1

rfreeノ

R2， 1

01

Fig．4The application of control points to connecting two curve segments smoothly P2ト1 normal control points，when it is necessary to em− phasize the difference between these two types of control polnts． The above discussion means that n normal control points are determined by introducing n arbitrary addi． tional control points when n points on a curve are given． In general，we can use a combination of the method of using the solutions of the simultaneous equations and this new method to determine the（normal）control の_polnts． For examples，consider the case where two curve seg． ments OI and C2 are connected smoothly（Fig．4）． Two addit▲onal control points are introduced near the con＿ necting point of the two curves in this case． Then，the simultaneous equations to determine the control points are described as follows． Pn−3十（w十2）」〔L＿2一トPn＿1：＝（4十w）ノ？1，n＿2 Pn−2→一（ω十2）Pn＿1十Pn＿1，n ＝ Pn−1，n十（w十2）Pn→一（20，i ＝：（？o，1十（w十2）（？i十（02 ＝ Q，十（w十2）（？2十（23 ：＝（13）（4十w）Rl，n＿1 （4十w）Rl，n （4十ω）R2，0 （14）（4−1一ω）」：12，1 （4＋w）R2，2（15） CI and C2 respectively． The points Pn＿1，n and（？o，i are the additional control points near the connecting point Pn（・＝（？o）of two curve segments． The numbers n十1and m十1are the numbers of control points for the curves CI and C2 respectively， Choosing Pn＿1，n and（？o，1 properly and．setting Po＝ Rl，o，the n−1simultaneous equations（13）with n−1 unknown variables Pi （i＝1，2，・一一，n−1）are sojved in− dependently on expressions（14）and（15）． The same dis− cussion is valid fOr expression （15）too． It is clear that control point Pn is determined by expression（14）． Since the positions of additional control points can be determined arbitrarily and no limitation exists in the number of additional control points，the shape of a curve can be controlled more flexibly． 4．Determining Additional Control Points Additional control points introduced in the previous section can be chosen arbitrarily． But unless their po− sitions are determined properly，the resulting curve may have unwanted properties． In this section，methods for determining additional control points will be discussed， According to the theory in the reference［11］， control points，輻e．，the solutions of equations（10）can be deter− mined approximately without solving the simultaneous equations． These approximated control points except the neighborhood of the start and end points are determined by the following expression 4 Pi＝V5R，＋Σ（Ri．ゴ＋R・一ゴ）・ゴ，（i＝1，2，…，・），（16）ゴ＝1 whereαequals to（一（2十ω）十W后（ω十4））／2． The middle point Pi，i＋10f the sub＿sequent control point」Pi and Pi＋1 may be chosen as an additional control point，when the siMilar curve shape obtained by solving the simultaneous equations is required， Here，we shall use the following expression（17）for the additional control points． P2…一（1＋E α）M・＋1一ξ9・＋、G・＋1 Rゴー1＋Rゴ＋Rゴ＋1 Gゴ＝ 3 （17） Where Pi（i＝0，1，2，…，n）and Qゴ（ゴ＝0，1，2，・一，m） represent the control points for the curves CI and C2 respectively． And R，，‘（i＝0，1，2，… ，n）and R2，ゴ（」＝ 0，1，2，… ，m） represent the given points on the curves Rゴ十Rゴ＋1 M」＋1＝ 2 （ゴ＝0，1，2，… ，n−1）， where Rゴand P21＋2 represent the．given points and the additional control points respectively．

(6)

ワ・．1 局．∫

弓．アP2

6 弓

_母．1 ら．7 Rf．2 Fig．5 A method of determining additional control points

v＝2

○：control points Fig．6 Examples of curves generated by the subdivision method This expression represents the geometric properties of the given point sequence to some extent as follows． Point Gゴis the centroid of three successive given points Rj＿1，Rj and Rj＋1 as shown in Fig．5． The point Mj＋1 is the midpoint between Rゴand Rゴ＋1． And additional con− t・・lp・i・t P・ゴ＋・i・th・midp・i・t・f G； and G；．、 wh・・e Gj and Gゴ＋1 are the extrapolating points of G1，ハ4，・＋1 and Gゴ＋1，Mj＋1 as shown in Fig・5 respectively． We can also control the curve shape by using this extrapolating ratioβ／α，but it is fixed on 1／2 in this paper indepen＿ dently on the weightω，because the curve shape can be modi且ed by moving additional control points． The idea of additional control points can be applied to tensor product surface description too． 5Jllustrative Examples Various illustrative examples are shown in this section． Fig．6shows various curves generated from a given controI point sequence， It shows ．that the curves approximate the given control polygon and becomes closer to the given control polygon，as the weight larger． ×：91ven points Fig．7The curve passing through the given point sequence generated by solving the simultaneous equatiolls（ the case where w＝2） w＝0 ×：91ven polnts Fig．8The curve generated by utilizing additional control POInts Fig．7 shows an example of the curve with predefined passing points，whose control points are obtained by solv− ing the simultaneous eqUations（10）， Fig．8 shows exam− ples of curves for various weights with regard to the same point sequence as the example shown ill Fig．7． Fig．9shows an example of the curve in the case where any given point is not repositioned but an additional control point． Fig，10 shows an example of connecting two curves smoothly without changing each curve shape except in the vicinity of the connecting Point． Applying the subdivision procedure to tensor product surfaces smooth surfaces can be easily generated， Fig．11 and Fig．12 show examples of such surfaces generated by using the additional control points． Fig．11 shows the surface with designated passing points，which is obtained without solving simultaneous equations． Fig．12shows an example of a rendering surface． The numbers of given points on the curves are 24 in this case，and the compu一

(7)

December 1998 No．49 （a）Before modifying the curve shape （b）After moving control poillts （a）Before connecting two curves （b）After connecting two curves ○：control points（including additional control P・ints） ×：91ven points Fig．9 A modification of curve shape without changing any glven polnt tation time to generate the curved surfaces is less than one second．s，by using a 32 bits personal computer． 6．Conclusions Anew subdivision algorithm for generating freeform curves Is presented and the properties of curves generated by this method are discussed． Additionallyla method．of determining a control polygon for a smooth curve pass− ing through given points without solving simultaneous equations is presented． The results are as follows． 1．Acurve is completely included in the convex hull poly． gon（or polyhedron in the case of a 3−D space curve） constructed by given control vertices． ×：91ven polnts Fig．10Connection of two curve segments（the case where w＝2） 2．Since a curve segment shape is determined by three or four subsequent controi points，the curve shape can be Modified or redefined locally． 3．The uniform 3rd order B−spline curves and its variation can be generate・d by changing the weight parameter． 4．Control points for a smooth curve（surface）passing through given points can be determined without solv− ing the simultaneous equations，by introducing additional control points．・ 5．By means of additional control points，acurve or a sur． face shapecan be changed locally without changing given ひ pomts． ’ The expression of the subdivision curves is not deter− mined in this paper． And there exist some ambiguities to determine additional control points． So，much discus−． sion and consideration on the equation of the curves and

(8)

、蕊’懸’慈崇≧ピ旧∨

慧i鷲鐵鐸

．総

、蟄くs、’“ シ

灘

Fig．11Acurved surface determined by the given poillts the method for determining additional control points are necessary． The applications to the higher order curves will be required on the next stage．

References

［1］Barsky B．A．：Computer Aided Geometric Design， bibliography with key words and classified index， Computer Graphics and Applications，Vbl．1，No．3， July（1981），pp．67−109 ［2］Braid I．C． and Lang C．A．： Computer Aided Design of Mechanical Components with Volume Building Bricks， Computer Languages for Nu− merical Control，Ed．by．J．Hatvany， North．Holland， Netherlands，（1973），pp．173−184 ［3］Okino N． et al：TIPS−1；Technical Information Pro， cessing System for Computer Aided Design， Draw− ing and Manufacturing， ibid．，（1973），pp．141−450 ［41．Farin G．：Curves and Surfaces for Computer Aided Geometric Design，（1988），Academic Press ［5］Chaiken G．：An Algorithm for High speed Curve Generation， Computer Graphics and Image Process− ing，3，（1974），pp．346−349 Fig．12An exam’垂撃?@of a rendering surface（the given points） case of 24 ［6］Doo D．W、H．：A Subdivision Algorithrri for Smooth− ing Down Irregular Shaped Polyhedrons， Proceed− ings International Conference on Interactive Tech− niques in CAD，（1978）， Bologna， Italy，（1978），pp．157− 165 ［7］Brunet P：Including Shape handles in Recursive Subdivision Surfaces， Computer Aided Geometric Design， Vol．5，（1988），pp．41−50 ［8］Doo D．W．H． and Sabin M．：Behaviour of Recursive Division Surface near Extraordinary Points， Com． puter Aided Design， VoLIO，No，6，（1978），pp．356−360 ［9］Narsi A．H．：Polyhedral Subdivision Meth6ds for Freeform Surfaces， ACM Transactions on Graphics， VoL6，No．1，（1987），pp．20−73 ［10］Micchelli C．A． and Prautzsch H．：Computing Sur− faces Invariant Under Subdivision， Computer Aided Geometric Design， Vol4，No．4，（1987），pp．321−328 ［11］Hosaka M， and I〈uroda M．：Asynthesis Theory of Curves and Surfaces for CAD， Information Process− ing in Japan， Vol．17，Noユ2，（1976），pp．1120−1127（in Japanese）」