ѧ
JOURN AL OF SOFTWARE
1999ꡡ1010ڡVol.10No.101999



ľȷB-ɱ 
 Ⱥ
ժҪ ڼ뼸,ɱһҪļ״޸ķ.ĴλӺͺϵĹ۵̽һַ,ƬʾιΪB-ʱ,κԾȷرʾΪһBzierƬ,ΪB-3Ĵ֮.˷ĺɱƬ,Ƕ,Խ˶B-ɱεĵ.
ؼ ɱ,,λ,BzierƬ.
ͼ TP391
Accurate B-spline Free-Form Deformation of Polygonal Objects
FENG Jie-qing PENG Qun-sheng
(State Key Laboratory of CAD & CG Zhejiang University Hangzhou 310027)
Abstract Free-form deformation is an important geometric shape modification method in computer animation and geometric modeling. The authors explore it by means of functional composition via shifting operators in this paper. When the object to be deformed is represented by triangular meshes and the deformation tool is a B-spline volume, the deformed object can be accurately described as a set of triangular Bzier patches, whose degree is the sum of three directional degrees of the B-spline volume. The proposed method also solves the sample problem of free-form deformation, because free-form deformation acts on triangular meshes rather than points.
Key words Free-form deformation, functional composition, shifting operators, triangular Bzier patch.
ڼͼ,״޸һҪо.ûͨĶƶ߶ʩӱ任ķıļ״,ЩЧ޵,Եõӵ״.ƶĿ϶ʱ,ֱӲʽԵʮַ.ռηϺõؽ[1].
Barrֲεĸ[2].ķ,任ǳ,ǿռλõĺ,οɶľʾʽ.ɱ(free-form deformation,FFD)ĸSederbergParry[3],ַṩһΪһĿռη:ȱǶһмռ.мռ״仯ʱ,δݸǶе.[3],ÿռΪһԪBzier.ƹFFDĸ,½B-spline FFD[4],Extended FFD[5],Rational FFD[6],NURBS FFD[7]ԼContinuous FFD[8]ȷ.ЩFFDѭͬĴ:
(1) һ,ռͿƶ;
(2) ӳ䵽ռ;
(3) ͨ༭ƶʽı״;
(4) ǶڲռеӦ.
FFDƹ㻹:Animated FFD[9]ֱӲFFD[10]FFD[11]Dirichlet FFD[12],ЩĴ4вͬ.FFDĿռάιߵĻ,Ʊη[13]η[14,15]ͻڿռ㼰λԼĿռη[16],ֱжάһάάıοƹ.[17],BechmannвͬάιߵıηϸķͱȽ.
пռηǶľ弸αʾʽ,Ķƶ,޹.,ֻеÿһʱ,βǾȷ.Ȼ,Ŀǰķ,ۻĽǲܵõ,ԭڼֻɢʽʾ.ʾĶƶϡʱ,õǰķԵõıν,屣ֲ,˹ϵ仯.ʵӦ,ĲһҪ.Ϊֹ,ֻ[4]漰.ǵķ,ϵͳԶؼαߵеľȷԲֵ֮,ֵʱ,ǰξͻԲ붥ķʽܲ,ֱбߵĲСڸֵ.ַһ֮,ʽܱ֤⵽,Щ̻˱ε.
ڱ,ǽλӵĸ,úϵķ˶B-ɱεĲ.ǵķ,ȽB-ͨڵ㷨תΪֿBeizer;Ȼ,B-ĽڵԶʷֺǻ,ʹʷֺǻÿһƬϸλĳBzier֮;ͨƬӦBzier,õƬľȷν,һΪB-Ĵ֮͵BzierƬ.Ӧλ,Ϲʽϱ.BzierƬƶļͨde Casteljau㷨,֪,ֵȶ.̶ûĸԤ,㷨Զɵ.
ĵ1ڽλԼһB-Ķ巽.2ڽܶʷֺǻԤ.3ڽܻλӺ͹de Casteljau㷨ĺ㷨.Ƕ㷨Լʵ.
1λӼde Casteljau㷨
λ,BernsteinʽһָΪķʽ,BzierߡʿԼƵ[18].r(u,v,w)ΪһBzier,䶨Ϊ
, (1)
RijkR3.Eu,Ev,Ew,IΪλ,:

Ӧλ,(1)±ʾΪ
. (2)
ʽ(1)ʽ(2)ĵȼԿͨʽչõ֤,ڴ˴.
ǸFFDB-һֶ巽ʽ.ǱϵеİΧΪ.ͨûϵͳԶɵķʽ,ΧɵB-Ľڵu,v,wΪ
u={u0,uku,uku+1,unu,unu+ku},
kuΪB-uĴ,nuΪuĿƶĸ,˽ڵΪkuؽڵ.v,wĽڵv,wƶ.ڵȷĸֱΪku,kv,kwB-P(u,v,w)Ϊ
.
ڵĶ巽ŵ,ǰѴӳ䵽B-Ĳռʱ,ֵڲռеľֲȼ,Ӷʡӳʱļ.Ȼ,B-ͨڵ㷨תΪֿBzier[19].
2ʷֺǻ
ڱ,ǼƽƬ,ΪƬԱ֤.岻ǻĶ,ǿȶǻ.ʷǻB-Ĳռне,Ϊ,u,v,w¼x,y,z;ui,vj,wkxi,yj,zk.
P0P1P2ΪϵһƬ,ͼ1(a)ʾ,εP0P1,P1P2,P2P0Բ.ǲͳһ[0,1],¶:

ٶuڵƽx=xi(i=i0,,i1)ƬP0P1P2ཻ,ǵĿƽƬĽ,ڱֽߵԼ¶Ƭǻ,ʹÿһƬλһBzier֮.Ϊ,ȼƽƬĽ,еĽƬ3γһѭ;,ͨʵĸ㷨õһϵеƽ,ΪLoop;Ա3Loopǻ.ζv,wƵؽ.Ǿϸ㷨.

(a)3Խ,Բʾ߶,ͼеѭΪ
P0Q0P1Q1,Q0Q2P2Q2P0,ǵLoop㷨õ4Loopֱ
Ϊ:P0Q0Q0Q2Q2,Q0Q1Q0,Q1P1Q1,Q2P2Q2
(b)һ,ƬP0ȴVlistɾ;յõVlistΪQ0P1Q0P1Q0;Ӧ
LoopΪP1Q0Q0,Q0P2Q0.
2.1󽻼ѭ
Ϊ˱㷨,Ƚһڴ洢Ƭ㼰Ƭƽ潻ݽṹ,ʾ.
Struct vertex {
float x,y,z;/* space position coordinates */
float t; /* t parameter corresponding to edge parameterizations */
short int Vflag; /* 1 if triangle vertex; 2 if intersection points */
struct vertex *link; /* link between two intersections, NULL if triangle vertex */
struct vertex *next; /* for linked list */

ڽ֮ǰ,P0,P1,P2ȸtֵγһѭ,Vlist,3VflagΪ1,linkΪNULL,һ,һƽһƬĽΪ2,ʱ,Ľͨlink,VflagΪ2.ȻǸtֵСVlist.,ƬĶ㼰ƽ佻tֵСγһѭ,ͼ1(a)ʾ,ͬһƽͨlink,ϢһLoopǺҪ.
һЩ.ƽƬһһʱ,ƽ汻Ƭ޽.ƽ潻Ƭһ㼰öԵı,ͼ1(b)ʾ,ʱ,ȽƬĶVlistɾ,ȻٽVlist.
2.2Loop㷨
ڱ,ǽѭVlistLoop,ͼ1ʾ.һLoopɴһstartVʼ,startVVlistVflagֵΪ1һ.Vlistеĳ㱻ʹ,Vflagֵȥ1;еLoop֮,VlistԪصVflagֵΪ0.еƬ㱻һ,㱻.VlistԪص˳ȷ:Loopĵ1һΪƬı,һnextָ,Ȼ,һnextlinkָ뽻ʹ.ǰƬĵ,һһǽ(nextָȷ),ʹǰһõָnext.㷨صɵLoopĶ˳ԭƬ˳һ,Ҳ˵ԭƬ3˳ʱ뷽,LoopҲ˳ʱ뷽.һڻʱҪ,Ϊ˺BzierƬӦƬͬƵⷨ.
2.3ǻ
ݵ2.2е㷨,3Loop,ǵıֱΪ3,4,5.ڱΪ45Loop,Ǹݱ߳Сԭǻ.ıLoop,ѡ϶̵ĶԽ߽ǻ;Loop,ÿһԷԽ,5Խ,ѡб̵߳Ķǻ,ͼ2ʾ.

ͼ2ǻLoop
ıLoop,ѡ̵ĶԽ,BD,ɵƬΪABDBCD.Loop,ѡ̶Խߺ͵Ķ,b+e,ɵƬΪABC,ACD,ADE.
3ƽƬBzierĺ
徭ʷֺǻ֮,ÿһƬλĳBzier֮.P0P1P2ΪһƬ,3BzierľֲΪ(u0,v0,w0),(u1,v1,w1),(u2,v2,w2).ƬͨΪ
 (4)
(x,y,z)Ϊ.ʽ(4)ʽ(2),ǾͿԵõƬFFDľȷ.ĺһ㷨ٵȡϽ.
DeRoseоBernsteinʽĺ㷨[20,21],ǲ䲻ͬķ̽.ǽλӵĸ,ʹBernsteinʽĺƵøӼ.Ǹ1BzierƬ(ƽƬ)Bzierĺ㷨.Ĳʽ(4)ʽ(2)

Aui=(1-ui)I+uiEu,Avi+(1-vi)I+viEv,Awi=(1-wi)I+wiEw,i=0,1,2.ЩǺŴıʽ, R=(x,y,z)ԼΪ

N=nu+nv+nw,RijkΪ
 (5)
Ƶ֪,ϽһΪNBzierƬ,Ŀƶͨde Casteljau㷨.õBzierƬķԭⷨһ,ʿǵʷֺǻ㷨֤.
4㷨ʵ
ǶʷֺǻƬĴС޹ص,ǻĽ,һЩСƬ,ЩСƬ,ûбҪȷɱ,Ϊǲڲ.ھʵָ㷨ʱ,趨һֵ,Ƭ߾Сֵʱ,Ƭֻͨɱ,Ǳľȷɱ,ӶԽʡ.,ܻӴƬѷĸ.
һԽʡļ:ÿƬ,Ƿλĳƽ,3ľֲǷһ,,ǿԼ򻯼ƶĹ.,ĳƬ3uΪu=u*,ôBzierƬĴӦΪkv+kw,ku+kv+kw.
Ŀǰļͻϵͳ,û,Ϊʾٶ,ϵͳһ㶼ʾ߿ͼ.ڱ㷨,ҲԼľȷ߿,߶Bzierĸ,ΪһBzier.ƪ,ڴʡԸƵ.
ѾSGI Indyͼιվʵֱ㷨.ͼ35,(a)Ϊʼ;(b)Ϊֱӵɱν,ڶ,Ƭ;B-Ŀƶ㼰ͼõ߱ʾ;(c)Ϊڲռ侭ʷֺǻĽ,߱ʾB-ڵ;(d)Ϊȷν.

B-ĴΪ212,ƶΪ424,(b),ʼʱļƬκٹ,,(d),ǹ⻬.
ͼ3

B-ĴΪ122,ƶΪ422
ͼ4

B-ĴΪ211,ƶΪ422
ͼ5

5 
ڱ,ǽλƵ˶ľȷB-ɱν.һʺڱʷֺǻ,ȻоBzierƬBzier ĺ,ɱƬ,˾㷨.ʵ֤㷨ȷ.㷨׵ؼеĶ򼸺ϵͳ,Ӷḻ˼ֶ.Ϊһо:
(1) 㷨ֱƹ㵽RFFD[6],NURBS FFD[7],CFFD[8];
(2) ʾFFDȷ;
(3) ͵ľȷν,ҪǻڵԼĿռΡԼɱη.
עͣоõȻѧ
߼飺ࣺ1970,ʿ,оԱ,ҪоΪ,,ѧ
ӻ
Ⱥ1947,ʿ,,ʿʦ,ҪоΪʵͼ,
,ά,ͼ,ͼֽɨʶ
ߵλ㽭ѧCAD&CGصʵ  310027
E-mail: jqfeng@cad.zju.edu.cn
ο
Bechmann D. Space deformation survey. Computers and Graphics, 1994,18(4):571586 
Barr A. Global and local deformation of solid primitives. ACM Computer Graphics (Siggraph84), 1984,18(3):2130 
Sederberg T, Parry S. Free-form deformation of solid geometric models. ACM Computer Graphics (Siggraph86), 1985,20(4): 537541 
Griessmair J, Purgathofer W. Deformation of solids with trivariate B-splines. In: Hansmann et al eds. Proceedings of Eurographics89. North-Holland: Elsevier Science Publisher B.V., 1989. 137148 
Coquillart S. Extended free-form deformation: a sculpturing tool for 3D geometric modeling. ACM Computer Graphics (Siggraph90), 1990,24(4):187193 
Karla P, Mangli A et al. Simulation of facial muscle actions based on rational free-form deformation. Computer Graphics Forum (Eurographics92), 1992,2(3):5969 
Lamousin H, Waggenspack W. NURBS-based free-form deformation. IEEE Computer Graphics and Applications, 1994,4(9): 5965 
Bechmann D, Bertrand Y et al. Continuous free-form deformation. Computer Networks and ISDN Systems (special issue of Compugraphics96), 1997,27(14):17151725 
Coquillart S, Jancene P. Animated free-form deformations: an interactive animation technique. ACM Computer Graphics (Siggraph91), 1991,25(4):2326 
Hsu W, Hughes J et al. Direct manipulation on free-form deformation. ACM Computer Graphics (Siggraph92), 1992,26(2): 177184 
MacCracken R, Joy K. Free-Form deformation with lattice of arbitrary topology. ACM Computer Graphics (Siggaph96), 1996,30(3):181183 
Moccozet L, Magnenat-Thalmann N. Dirichlet free-form deformations and their application to hand simulation. In: Thalmann N ed. Proceedings of Computer Animation97. Geneva: IEEE Computer Society, 1997. 93102 
Feng Jie-qing, Ma Li-zhuang, Peng Qun-sheng. A new free-form deformation through the control of parametric surfaces. Computers and Graphics, 1996,20(4):531~539 
Lazarus F, Coquillart S et al. Axial deformation: an intuitive deformation technique. Computer-Aided Design, 1994,26(8): 607613 
Chang Y, Rockwood A. A generalized de Casteljau approach to 3D free-form deformation. ACM Computer Graphics (Siggraph97), 1997,30(3):187196 
Borrel P, Bechmann D. Deformation of N-dimensional objects. International Journal of Computational Geometry and Applications, 1991,1(4):137155 
Bechmann D. Multidimensional free-form deformation tools. In: de Sousa A, Hopgood B eds. State of the Art Report (Eurographics98). Lisbon, Portugal: Blackwell Publisher, 1998. 102110 
Chang Geng-zhe. Bernstein polynomial via the shifting operators. American Mathematical Monthly, 1984,91(10):634638 
Farin G. Curves and Surfaces for Computer-Aided Geometric Design. 2nd Edition, New York: Academic Press, 1990 
DeRose T. Compositing Bzier simplex. ACM Transactions on Graphics, 1988,7(3):198221 
DeRose T, Goldman R et al. Functional composition algorithms via blossoming. ACM Transactions on Graphics, 1993,12(3): 113135 
ո:1998-09-21޸:1998-12-01
