ѧ
Journal of Software
2000 Vol.11 No.1 P.49-53



ڻܷNurbs/
ҹ㡡ͨ⡡
ժҪNurbs/ڷϵֵȶ,Nurbs/ȱ.Ľڲ/󽻵Ļ(moving affine frame,MAF).MAFԭ,˷Nurbs/һ·.÷ֵȶԺЧϾڸִͳĵ,ӦƷάCADϵͳGEMS 5.0.
ؼʡܷ,Nurbs,CADϵͳ.
ͼšTP391
Computing the Parameters of Points on Nurbs Curves and Surfaces via Moving Affine Frame Method
HU Shi-minSUN Jia-guang
(National CAD Engineering CenterTsinghua UniversityBeijing100084)
HU Shi-minSUN Jia-guang
(Department of Computer Science and TechnologyTsinghua UniversityBeijing100084)
JIN Tong-guangWANG Guo-zhao
(Department of Applied MathematicsZhejiang UniversityHangzhou310027)
AbstractThe numerical instability in computing the parameters of the points on Nurbs curves/surfaces is a fatal disadvantage of Nurbs methods. In this paper, the authors introduce the moving affine frame (MAF) method for intersection calculation of parametric curves and surfaces. Based on the principle of a MAF method, a new method for computing the parameters of the points on Nurbs curves and surfaces is presented. The numerical stability and the efficiency of the method are better than all traditional iterative methods. The new method has been applied to the commercial 3D CAD system GEMS5.0.
Key wordsMoving affine frame (MAF) method, Nurbs surface, CAD system.
֪,,ߡĵ,CAGD(computer aided geometric design)㷨.ⷽྭ㷨,Bzier/de Casteljau㷨Nurbs/deBoor㷨.Щ㷨ǳ,ڸ㷨,Ƚȶ,Чʺܸߣ1,2.ǿ䷴,ڸ/ϵĵ,ηӦĲֵ.ڼ,ǳҪ,ԭ򣺢 ڼ,Ǳزٵ;ʵʾ,Ϊʵڽߴѷ,άռеĽ,,ԱɢƬʱ,ڽߴǺ.
Nurbs๫ϵŵ,CADͼѧԽԽ㷺Ӧ.Ҳȱ,Piegl3ܽģ ҪĴ洢Զ崫ͳ; ȨӵĲʵӦ,ܵºܻĲ; ĳЩôͳʽܱNurbs; ĳЩ㷨,練/ϵĲ,ֵȶ.ڷ/,ͳķǲNewton,Чʵ,׳.
֮һ1988󽻵Ļ(moving affine frame,MAF)4,MAFԭ,ߡһ·.÷нǿļֱ,ȶԺЧʾڴͳĵ.
1MAF
֪
(1)
(2)
ɢóʼ,ȡһأ
ʼΪ{M0,T0},M0ΪάռеĽ,ӦΪu0=(u01,u02),v0=(v01,v02);T0Ϊõĵλʸ,,T=N1N2,N1N2ΪS1S2ֱu0v0ķ,
(3)
M0T0ǰĲ,P=M0+T0,
(4)
ʽͬʱ,ɵõ
(5)




ͬ,æv1,v2,Ԧu=(u1,u2)ͦv=(v1,v2)Ϊ,õµĲu0  u0+uv0  v0+v,ǵõϵĵX0S1Y0S2.X0-Y0,ΪM0һ.,Ϊ󽻾.
PX0Y0Ĺ̳Ϊ任.
X0-Y0,Ҫ.X0Y0õһP0.£X0S1ƽ榰1,Y0S2ƽ榰2,1ɦ2ֱL,ͼ1ʾ,X0X0XTֱL,Y0Y0YTֱL,ȡ.X0Y0õһP0Ĺ̳Ϊе任.Ȼ,P0任,õϵĵX1S1Y1S2,X1-Y1,ΪM0һ.,е任任,ֱXn-Yn.MAF,μף4.

Fig.1
ͼ1
2Nurbs/
2.1߲
һNurbsߣ
(6)
Piǿƶ,WiӦƵȨ,Ni,k(t)Ϊڽڵ
T={t0,t1,...,tk,...,tn,...,tn+k}
ϵkB,ͨȡt0=t1=...=tk-1=0,tn+1=tn+2=...=tn+k=1.SΪP(t)ϵһ,ϣu,ʹP(u)=s.
ȷһƲu0,.
(1) òڵ㷨,NurbsP(t)תΪn-k+1Bzier.P(t)Ľڵؽڵ,Ӧ.
(2) ÿһBzier,жPǷ͹.͹,ɢBzier,ɢһȡΪ3,жPǷЩߵ͹,ԹƽƲu0.
˽Ʋu0,.
P(u0),P(u0)ֱL,SͶӰL,ΪQ,QL,
(7)
ǿu,

u0u0+u,ظ,ֱP(u0)-Q.
һ˵,23,ɵõΪȷĲ.
2.2
һŸNurbs棺
(8)
Pi,jǿƶ,Wi,jӦƵȨ,Ni,k(u),Ni,k(v)ΪڽڵU={u0,u1,...,uk,...,un...,un+k}V={v0,v1,...,vk,...,vm,...,um+k}ϵkB,SΪP(u,v)ϵһ,ϣu^,v^,ʹP(u^,v^)=S.
ȷһƲu0,v0,.
(1) òڵ㷨,NurbsP(u,v)תΪ(n-k+1)(m-k+1)ƬBzierƬ.P(u,v)Ľڵؽڵ,BzierƬƬӦ.
(2) ÿһBzierƬ,жPǷ͹.͹,ɢBzier,ɢһȡΪ3,жPǷЩƬ͹,ԹƽƲu0,v0.
˽Ʋu0,v0,.
P(u0,v0),P(u,v)ƽ榰,SͶӰ,ΪQ,Qڦ,
(9)
ʽ(9)ͬʱPu(u0,v0)Pv(u0,v0),
(10)
Ԫһη,



u0u0+u,v0v0+v,ظ,ֱP(u0,v0)-Q.ʵϵõµĽƲ,һ任Ĺ,伸ֱҪȽϴͳ.÷֤MAF,ڴ˲׸.
3/ʵ
1:߲.
һĽNurbs,8ƶֱΪ
(200,100,0),(100,100,0),(100,300,0),(400,300,0),
(400,100,0),(300,100,0),(300,200,0),(360,180,0);
ڵΪ{0,0,0,0,0.2,0.4,0.6,0.8,1,1,1,1};ȨӷֱΪ{1,1.2,1,0.8,1,1,1.2,1}.ڸϵĵ(117.36617392236,179.03032014373,0.00000000000000),ɢøõĽƲΪ0.125,3εõȷΪ0.1234567.1.
Table 1
1

TimesApproximate parameterError
10.123458892249810.00000219224981 
20.123456700004330.00000000000433
30.123456700000000

ٴ,ڽƲ,.
2:.
һ44Nurbs,74ֲ28ƶֱΪ:
(100,100,0),(130,180,30),(120,270,30),(90,360,0),
(180,120,30),(160,200,60),(190,320,60),(150,440,30),
(250,140,30),(230,200,60),(260,330,60),(240,400,30),
(330,100,0), (350,220,30),(340,290,30),(330,400,0),
(410,120,30),(380,200,60),(400,320,60),(390,440,30),
(460,140,30),(440,200,60),(460,330,60),(480,400,30),
(540,100,0), (570,220,30),(550,290,30),(575,400,0).
ڵֱΪ{0,0,0,0,0.25,0.5,0.75,1,1,1,1}{0,0,0,1,1,1};74ֲ28ȨӷֱΪ{1,1,1,1,1.2,1,1,0.8,1,1,1,1,1,0.81,1,0.65,1,1,1,1,1,1.6,0.89,1,1,1,1,1}.ڸϵĵ(277.34742334732,248.13730252438,28.748699053051),ɢýƲΪ(0.1275,0.375),ɵõȷΪ(0.123,0.456).2.
Table 2
2

TimesApproximate parameter
1(0.12605963537084,0.45777731019774)
2(0.12282564488140,0.45574907305541)
3(0.12299892247181,0.45599845953458)
4(0.12300011806077,0.45600008679545)
5(0.12300000072886,0.45600000053584)
6(0.12299999995893,0.45599999994129)
7(0.12300000000000,0.45600000000000)

ٴ,ڽƲ.
ӱ,÷нϸߵЧ,Ϊ,ͳͨҪ10βɽƲȷ.
оõȻѧNo.69902004863߿ƼĿNo.863-511-820-017͹ҡ塱ƼĿNo.96-A01-01-02
廪ѧCADġ100084廪ѧѧ뼼ϵ100084
ҹ㣨廪ѧCADġ100084廪ѧѧ뼼ϵ100084
ͨ⣨㽭ѧӦѧϵݡ310027
ѣ㽭ѧӦѧϵݡ310027
E-mail: shimin@tsinghua.edu.cn
ο
1Farin G. NURB Curves and Surfaces: from Projective Geometry to Practical Use. Wellesley, MA: A K Peters Ltd., 1994
2Hoschek J, Lasser D. Fundamentals of Computer Aided Geometric Design. Wellesley, MA: A K Peters Ltd., 1992
3Piegl L. On NURBS: a survey. IEEE Computer Graphics and Applications, 1991,11(1):5571
4Jin Tong-guang, Wang Guo-zhao. MAF method for intersection calculation between parametric surfaces. Technical Report, No.#8801057, Zhejiang University, 1988
1998-09-07ո
1999-01-12޸
