ѧ
JOURNAL OF SOFTWARE
1999ꡡ1011ڡVol.10No.111999



Bzier󽻺Ͳüʵ
ʾӳ ҫ
ժҪBzierƬĿɷָ,˵ʼ;ͨ㡢߽Խȹ,ʵһʼ㽫ԽƬ߸ٳ.Ϊֵ,ٻ,ԽΪֵķ,Ÿ,ʵ˲üĿ.Խʾ,˷򵥡ɿ,ܹ͵Ҫ.
ؼʡBzier,BzierƬ,,.
ͼšTP391
Procedure of Intersection and Trimming for Composite Triangular Bzier Surface
LI Ji-jun KE Ying-lin CHENG Yao-dong
(Department of Mechanical Engineering Zhejiang University Hangzhou 310027)
Abstract Using the splitting property of tringular Bzier patch, the problems of iterating and initial intersection point calculating can be solved. By the procedures of near surface point iterating and border points traversing, the whole intersection curve traversing many patches can be traced from one initial intersection point. Inserting intersection points as measure points into surface, retriangulating grids, splitting triangular grids and measure points along intersection curve, the original surface can be trimmed into two composite triangular Bzier surfaces. The experimental results show that this method is simple, robust and applicable for surface modeling.
Key wordsComposite triangular Bzier surface, triangular Bzier patch, triangular grid, marching.
ڼ͡CAD/CAMеĹ㷺Ӧ,ļδ,󽻡üȳΪ㼸ео,ΪɸӲƷͼؼӹݵĻֶκͺϵͳҪָ.ΪüɵȻҪ֮һ.
Farin1ݶBzierƬϸо,˹CĸBzier;Choi2ϵͳؽɢֵ㽨GĸBzierĹ;ӳ֣3䲩ʿһ׼CĸBzierֵģ.ЩɹؽɢֵBzierֵ.ͨĸBzierһͬص:ÿBzierƬһӦ,ȴûӦĲ.ζûеһӦĸBzierڱҪ.ڴ,վ󽻵ľ,úͿǵBzierص,һЧĽ.ڸٷ4,5ݵŵ֪һ,ͨظٷǰһһ,Ӷٳ.ô,ÿϵһʼͳΪ󽻵Ĺؼ,ڴ,BzierƬķָԭ͵󾫵ķ,Ϻõؽ.ͨͱ߽ĸ,ɹ˽һƬһƬĿԽͼٵĹ.ַԽŸBzierһߵ,Ҳܹ߻Ͷ߷֧.
ڹ,Ʒ治ܻ򲻱ʾ,öƴ㲻ϵҪ,,üĴõҪ.ü,Ƚڲ0,1ݣ0,1ӳ,Ȼγɵü˹ϵ,üڻ⻷6,7,нüӳü㷨Ĺؼ,ǾеһӦһü.,޶ӦĸBzier,޷ӳϵ,ȻҲ޷ֲü.һص,ͨΪֵ뵽ֵ㼯,ɽݽṹҵýڵ2,3,ǻ,ԽΪֵķ,½Ϣ,γԭṹһµ,Ϻõؽᵽ.
1 Bzierĸ
1.1 BzierƬķָԭ
Pi(i=1,2,3)ǦT1T2T3ڵ3,PiڦT1T2T3Ϊ(ui,vi,wi)(i=1,2,3),릤T1T2T3һBzierƬ(ͼ1ʾBzierƬΪ),ǽԦP1P2P3ϵĲȤ,ϣʾΪP1P2P3ϵBzierƬ(ͼ2ʾ).

ͼ1 BzierƬ

ͼ2 BzierƬָʾ
PʦT1T2T3,PʦP1P2P3,PڦT1T2T3Ϊ(u,v,w),ڦP1P2P3Ϊ,

ʽΪԡϡá¡ ʾͬһ任ʽ,,

,µĿƶi,j,k(i+j+k=n)ļʽΪ
i,j,k=(u1E1+v1E2+w1E3)i(u2E1+v2E2+w2E3)j(u3E1+v3E2+w3E3)kf000.
1.2 ļ
ܼռһ㵽BzierƬR(u,v)(Ϊ)ķ2.ռһΪG,Ϊ˲õƬϾGĵR(u*,v*),ٶһʼ,ͼ3ʾ.

ͼ3 ļ

ΪʹeģС,Taylorչ






:
(1) ռGƬĳʼ;
(2) ƫ΢Ru,Rvd=G-;
(3) ʽ
(4) (ΪС),طת(2).
ͨ,һ23μɼȷĲֵu*v*.
1.3 ʼĵ󾫣4,8,9
оĸBzier,ҪÿƬһΪʼ(ԭ),ɲķ:ÿƬĿƶ(ͼ1ʾ)СΧ,ͨΧжƬǷཻ(ƬΪһ),ཻ,е㾫ȷĳʼ.һĽ,¼ֹͣ;,ÿƬзָ,γµ,ѶӦĸƬƽֵΪƲֵ,ӦϵеΪƽ,ԭƬϽе.ַм,ҪôжϳƬཻ,Ҫôܹһ,Ҫôڷָﵽƾʱ޷.ڵ3,Ǽ¼һпܵΪյĽƽ,㲻Ϊٵʼ,жϸǷǽߵļ.
ʼ,ʵϾǽõĽ.ܵķڳʼ,Ҳڸٹ.ͼ4ʾ,ΪR(u,v),S(s,t),ʼƽΪM,MR,SϵΪP,Q,P,QƽֱΪFR,FS,P,QеֱFR,FSĸƽ,3ƽ潻G,ͨG,λڸ,Ϊһ,,ĲֵΪĲֵ;GM,ظĹ.

ͼ4 ʼ
ǵĿһʼ,ƾ,0u,v,(u+v)1.ΪонƬ,Ľ㲻ɳֵΧ.ķ󽻵,пƽ˴ƽе,ĽֵС01,Щĳڳʼѡȡɵ,BzierƬķָͿԽ.
1.4 ߽ļ
߽ļµӦ:,ٵĽλƬĽ,ñ߽ļ㽫õ߽(߽),ͨıٲķƼ߽;,ñ߽ǰܵȡķ,ڵƬ,Ӷ˳ٳ.轻ΪR(u,v),S(s,t),Ϊ˼߽ϵĵ,R(u,v)-S(s,t)ģС,Taylorչ,ǿԵõµķ.


R(u,v)-S(s,t)(ΪСֵ)ʱ,ֹͣ.Ӧ3ʽ,ɷֱλu=0,v=0,w=0߽ϵĵ.
1.5 ٹ
оǸBzier,һ,ÿ߽ԽƬ.߽ͽļ㷽,ڽߵÿһ֧,һΪʼ,÷֧ں̲н©.ɢص,ʵؿBzierƬķָƾ,ϿԱ֤ٿÿϵһ.,ҲͨӲԸĽ.ǵ㷨Ա֤ĳ߶ֻҪһʼ,ͿԸٳ(,ÿƬֻһǿе).
һ,ƬϵķʸĲΪٵķ4,5,10:

cΪٷʸ,FR,FSΪ㴦Ƭķʸ.ڸٲѡ,4,5,10.
ǽÿƬĽһʼ,ʼ.
(1) ӳʼȡһ;
(2) ־ýstatus=1,ʾѾٴ;
(3) һǰһ,ýĵ󾫷;
(4) жǷ񳬳߽,ûг,ת(3),,;
(5) ñ߽ļ㷽߽,Ҽ¼1߽;
(6) еĽñ߽ķһڵԼϵһ,־ڵĽstatus=1;ǵ1߽1߽غ,жγɽ߻;Լ¼Ľд(Ϊ˲üı,1߽罻ǰĽɾȥ,֤ظ);ı߽,;,ת(3),;
(7) ֱеĽþΪֹ,¼еĽ. 
2 ڸBzierĲü
2.1 ڽߵɲü
촬ģߵȹҵķչ,Ϊ˹츴ӵ,ͨҪвü,ϵͳ,ཻԲü.֪,κһ涼һ߽绷ͼڱ߽绷Χɵ,ڲüΪü߽(ڱ߽),,ڽߵɲüɶ.
(1) ĳΪʱ;
(2) ĳߵ˵ڸ߽;
(3) ĳߵ˵ڸĳһڱ߽绷;
(4) ĳߵ˵ֱλ߽ͬһڱ߽;
(5) ĳߵĶ˵ֱλڱ߽;
(6) ߵĶ˵˳λ߽硢ڱ߽߽.
оĸBzier,߽ʱ뷽,ڱ߽˳ʱ뷽.,۶ںֱ߽,ߵĶ˵λĳBzierƬıʱ,ñߵBzierƬΪ;ߵĶ˵պĳBzierƬĽǵ,ͨýǵصıǷһߵBzierƬΪȷǷΪı߽.ַܿͿԱ߶εĿɲü.ڱ߽һ,ǲ˹ķʽѡȡɲüĽ߶Ĳü.
2.2 Ĳľǻ
ĳ()߶ηϲüʱ,ҪΪֵ뵽ֵ㼯.άռне,ҽ˳е,Ϊľǻ׼.
(1) ÿһ,жǷΪBzierƬϵĽǵ,,ҵýǵ,򽫸ýΪһµֵ뵽ֵ㼯;
(2) ݽڵBzierƬ,Ϣ,ҵýڵ,ڸм¼ý.
ֵ,ΪάԭBzierƬ˹ϵ,µǻԭ.
(1) Ľǵͽеı߽㹹ɱ߽,㹹ڲ;
(2) ף2,3нܵǻַǻ;
(3) ĵһϴʱ,ͼ5(a)ʾǻ;
(4) ĵ㴩Խʱ,ͼ5(b)ʾǻ;
(5) ߵĴ3ʱ,ͼ5(c)ʾǻ.

ͼ5 ǻ
ǻͬʱ,ԽΪʾɵ,Vi(i=1,2,3,4)Ϊ¼ĵ,ǻʱVi-1ViʾΪm-nSide=-1,Vi-1ViҲʾΪm-nSide=1,ǻʼΪm-nSide=0.ܵҪ,ǻ񲻵иǵ,ڳʵֵĹл,ǻķڴ˾Ӧ.
2.3 ü
ǻɺ,ǾͿԽеԽ߶Ϊз.
Trim-Seperate(){
if (m-nSide==1(or -1)){
if (m-nSide==0){
m-nSide=1(or -1);
Trim-Seperate();}
}
}
ָ3ڵ,õݹ麯ǴһԪؿʼ,ͿԽеΪ:m-nSide=1һm-nSide=-1һ.Ȼ,ԭֵз,뵽Ӧÿһ,±.
for (ԭBzierÿһֵ){
for (ÿһеÿһ){
if (Ľǵ==ֵ){
ֵ뵽µֵ㼯;
Ľǵ;}
}
}
,ؽ˹ϵ,ԵĸBzier.,ڰף2,3ݷ츴Bzierʱ,ֵķʸԭ̳еõ,ٽй,Ӷ֤˲ü̬.,һŸBzier汻üΪŸBzier.
3 ʾ
ͼ6ԸӵġֵɹʵʲɢҵõĸBzierͨ󽻡ü.ͼ6(a)ĳһÿ;ͼ6(b)ǵҶƬһԲõĽ;ͼ6(c)Ь鸵Ĳü;ͼ6(d)ĳͨܵĲü.ȻƬһߵļпܵ½߶εĶʧ,ǵĸٷԱ֤,ֻҪ֪ĳ߶ϵһ(ܸýλĸ),ͿԽؼ;ǻڱ߽һ,ֻҪȿƺ,ڹȫҪ.


(a)

(b)

(c)

(d)
ͼ6 õ
ĿоõҽʿרͲܹѧ.
߼飺ʾ,1967,ʿ,ҪоΪCAD/CAM,ͼѧ,󹤳,.
ӳ,1963,ʿ,ڣʿʦ,ҪоΪƷ,CAD/CAM,ݿӻ,ԭͼҽѧеӦ.
ҫ,1934,,ʿʦ,ҪоΪCIMS,CAD/CAM,Ƚ켼,е񶯼ṹѧ,źŴ.
ߵλ㽭ѧеѧϵݡ310027
ͨѶϵ:ʾ 310027,㽭ѧеѧϵ
ο
1 Farin G. Curves and Surfaces for Computer Aided Geometric Design (3rd). San Diego: Academic Press, 1991
2 Choi B K. Surface Modeling for CAD/CAM. New York: Elsevier Science Publishers, 1991
3 ӳ.ɢݵļͼӦо۲ʿѧλģ.Ͼպѧ,1992
(Ke Ying-lin. Geometric modeling for three-dimensional scattered data and its application studies Ph.D. Thesis. Nanjing University of Aeronautics and Astronautics, 1992)
4 Barnhill R E, Kersey S N. A marching method for parametric surface/surface intersection. Computer Aided Geometric Design, 1990,7:257280
5 Stoyanov Tz E. Marching along surface/surface intersection curves with an adaptive step length. Computer Aided Geometric Design, 1992,9:485489
6 Sheng X, Hirsch B E. Triangulation of trimmed surfaces in parametric space. Computer Aided Design, 1992,24(8):437444
7 Piegl, Les A, Tiller Wayne. Geometry-based triangulation of trimmed NURBS surfaces. Computer Aided Design, 1998,30(1):1118
8 Mullenheim G. Convergence of a surface/surface intersection algorithm. Computer Aided Geometric Design, 1990,7:415423
9 Mullenheim G. On determining start points for a surface/surface intersection algorithm. Computer Aided Geometric Design, 1991,8:401408
10 ,²,ƽ.ƽʷеӦ.ѧ,1997,20(12):10741080
(Ning Tao, Ma De-chang, Wang Ya-ping et al. Application of plane vector field and curvature analysis in surface intersection. Chinese Journal of Computers, 1997,20(12):10741080)
1998-09-07յԭ,1998-12-28յ޸ĸ
