ѧ
JOURNAL OF SOFTWARE
1999 19 3  Vol.19 No.3 1999



Bzierߵڵ
ܷ ſ˾
ժҪоϺͱ༭еķֶBzierߵļ.3BzierߵĽڵԼϵ㷨.ʵ˷ֶߵBzierʾ,ϸѧ֤.ѱӦõ.
ؼʡBzier,չ,ڵ,,Bzierʾ.
ͼšTP391
Three Kinds of Node-reduce Operator on 3rd Order Bzier Curve
CAO Feng ZHANG Ke-jun
(National Key Laboratory of Text Processing Institute of Computer Science and TechnologyBeijing University Beijing 100871)
Abstract The simplification of Bzier curves in fitting and editing is discussed, three kinds of node-reduce operators are defined, and the algorithms based on them are given in this paper. The simplest Bzier expression can be gotten through the algorithms, and a strict proof is given. These algorithms have been already used in the developing software.
Key wordsBzier curve, extension of curves, node, node-reduce operator, simplest Bzier expression.
żͼƵѸٷչ,ǾҪͼתΪͼ,Ա޸.ģͼɨתTrueType,вݸͼλȾӦõʵ.ͼλؼļ׷.淽Ӧ˵,Ŀǰʳı׼PostScript֧Bzier,ҪBzierõͼ,,þٵĵ㾡ȷϾͳ˺.һͼ༭,ҲBzierʾ,õBzier̫ĿƵ,мĲ.ĸ3Bzier߽ڵ,ЧʵBzierߵļ.ڷƸϵͳ,ӦЩ,ȡ˱ȹͬõЧ.
1 һЩǺ
ǽҪоƽϵBzier߶(ڸߴεBzier,ɽתΪBzier߶Σ1).Bzierߵһʿɲף2,3.4Աʾ.p0,p1,p2,p3,p0Ϊʼ,p3Ϊֹ,p1,p2ΪƵ,p0,p3ֳΪڵ.ĲΪ
C(t)=(1-t)3.p0+3(1-t)2.t.p1+3(1-t).t2.p2+t3.p3 (0t1)
ӶB1=b=(p0,p1,p2,p3)p0,p1,p2,p3R2ʾƽеBzier߶.
Ϊ˷,ڱĵĳЩطCԵļǺšʾBzier߶еĽڵ.,bΪBzier߶,bB1,bp0,ʾbĳʼ,bp1ʾbĵ1Ƶ,.,Bzier߶b(p0,p1,p2,p3),ڲ,Ϊ,ʾڿ,ʾ.
Bk=bk=(b1,b2,...,bk)biB1(i=0,...,k)bip3=bi+1p0(i=0,...,k-1)ΪkBzier.ΪƽзֶBzierߵļ,ĵųBzierߵ˻,4ƽڵ㹲ߵ.
1.1. Bzier߶εչ
b1,b2B1,b1Ϊb2һ,b2Ϊb1չ.
1 b1p0=b2p0,b1,b2йͬʼ,b2Ϊb1չ.
2 b1p3=b2p3,b1,b2йͬյ,b2Ϊb1ĸչ.
2 ѧ
2.1. չ
b1,b2B1,b2Ϊb1չĳֱҪΪ:kʣ0,1,ʹã,Ǽb1=(p0,p1,p2,p3),b2=(p0,p1,p2,p3).
(1) p0=p0;
(2) -p0+p1=(-p0+p1);
(3) p0-2p1+p2=(p0-2p1+p2);
(4) -p0+3p1-3p2+p3=(-p0+3p1-3p2+p3).
֤:1 .b1,b2Ŀƽڵ4,b1ϵÿһt=t0,
Cb1(t0)=(1-t0)3.p0+3(1-t0)2.t0.p1+3(1-t0).t20.p2+t30.p3,
Ǿҵb2ϵĵ,t=kt0֮Ӧ.
Cb2(kt0)=(1-kt0)3.p0+3(1-kt0)2.kt0.p1+3(1-kt0).k2t20.p2+k3t30.p3.
֤,Cb2(kt0)=Cb1(t0),Bzier߶b1Ϊb2һ,1,b2Ϊb1չ.
2 Ҫ.ն,b2Ϊb1չ,Ϊ߶εһ.b1ֹp3Bzier߶b2ϵĲΪk,ɵb1ĲΪ
Cb1=(1-kt)3.p0+3(1-kt)2kt.p1+3(1-kt).k2t2.p2+k3t3.p3.
=(1-t)3p0+3(1-t)2tp1+3(1-t).t2p2+t3p3.
Ƚt,t2,t3ϵͳ֪(1)(4).

2.1. b2Ϊb1չ,Ҷ2.1еkֵΪt0,b2Ϊb1t0չ.
Ϊ˱,ǶBzier߶B1ƽ4D0,D1,D2,D3,b(p0,p1,p2,p3)B1,
D0(b)=p0;
D1(b)=-p0+p1;
D2(b)=p0-2p1+p2;
D3(b)=-p0+3p1-3p2+p3.
ô,1ɼ򵥵Ϊ:b1,b2B1,b2Ϊb1ĳҪ:kʣ0,1,ʹ
D0(b2)=D0(b1), D1(b2)=D1(b1), D2(b2)=D2(b1), D3(b2)=D3(b1).
2.1. bk1,bk2,bB1,bk1Ϊbk1չ,bk2Ϊbk2չ,k1k2,bk2Ϊbk1k2/k1չɶ2.1,֤.
2.1,Bzier߶εչΨһ,ͼ1ʾ.

ͼ1
2.2. ߶Σb+kΪBzier߶bkչΪbȫչ.
2.1. b+ϵһ߶ξΪBzier.
һ߶c,ȡ㹻Сk,ʹcbk,bkΪBzier,cΪBzier.
2.3. b1,b2B1,ҾΪƽĳһȫչߵһ,b1,b2Ϊͬ.ͬϵΪȼ۹ϵ,ɶ֪,ͬϵ㷴ԺͶԳ.֤ͬϵĴ.
2.2. ͬϵΪȼ۹ϵ.
ֻ֤ͬϵԼ.b1,b2Ϊͬ,b2,b3Ϊͬ.ͬϵĶ,b1,b2һȫչߣΪC+1.Ȼb1㣨յ㣩ʼC+1򲿷ּΪb+1ͼ2ʾ.ͬ,b2㣨յ㣩ʼC+1ǲ߼Ϊb+2,b+1,b+2ΪC+1һ,b+1,b+2C+1,b+1b+2b+2b+1.b+2,b+3,Ҳͬ,b+2b+3b+3b+2.Ӷܹ4:

ͼ2
1 b+1b+2,b+2b+3,b+1b+2b+3,b+1b+3,Ӷb1,b3Ϊb+3еһ,b1,b3Ϊͬ.
2 b+2b+1,b+3b+2,b+3b+1,ͬ1,b1,b3Ϊͬ.
3 b+1b+2,b+3b+2,b+1,b+3Ϊb+2һ,Ӷb1,b3Ϊb+2һ,b1,b3Ϊͬ.
4 b+2b+1,b+2b+3,b+1b+3,b+3b+1,b1,b3Ϊͬ,֤Ȼb+1b+3b+3b+1.b+1b+3b+3b+1,b+2Ϊb+1b+3Ĺͬ,b2=b2(p0,p1,p2,p3),b+1Ϊpb1,b+3Ϊpb3,ͼ3ʾ.

ͼ3
ɴ˿֪,Ϊչ,Ϊչ.2.1֪,Ϊչ,p3pb3Ϊչ.b+1b+3b+3b+1ì.
 
3 1ڵӼ㷨
3.1 1ڵN1ȷڵӣ
ǶB2ϵĵ1ڵN1,B2ϵķֶBzierߣb1,b2,b1,b2B1,
1 b1p3=b2p0,b1,b2Ϊͬ,b1b2ڵb1p3,N(b1,b2)=,Bzier߶ΣΪb+1b1p0b2p3һ,ʱƣb1,b2N1ϲ.
2 ,N1b1,b2=b1,b2.
3.2 ڽӵBzier߶μ㷨
BkеkBzierߣb1,b2,...,bk,ResultBΪ,CurBΪǰBzier߶,㷨:
1 CurB=b1,i=2.
2 ik,ת(4).
3 ڵN1ӦõCurB,bi.
a N1CurB,bi=CurB,bi,Bzier߶CurBResult,CurB=bi,i++;ת2.
b ,N1CurB,biԼΪBzier߶b,CurB=b,i++;ת2.
4 ,b1,b2,...,bkԼ洢Result.
3.2.1. bBk,㷨򻯺ķֶBzierߵĽڵ.
֤:֤Resultb1,b2,...,bnΪ㷨ý,һֶַBzier߱ʾb1,b2,...,bk,kn.
Resultb1,b2,...,bnΪ㷨Ľ,bi,bi+1ܳΪĳһBzierߵ,򽫻ᱻ㷨ڣ3ϲ.
kn,һBzierbi(ik)ԽResultеĽڵbjյ.ͼ4ʾ,bjΪͬ,ΪbiͬbiΪչ,biΪͬ,bj+1Ϊͬ.

ͼ4
ӶͬϵĵԿ֪,bjbj+1Ϊͬ,bj,bj+1ڽڵbjp3,ʣbj,bj+1ɱڵԼ,Resultb1,...,bnΪ㷨N1Ľì.
ɶ3.2.1,ֶBzier,ǿ㷨ķֶαʾ.
3.3 B2ϵN1ӵľʵ
B2ϵ߶Σb1,b2,b1(p0,p1,p2,p3),b2(p3,p4,p5,p6),b1,b2N1ϲ,ɶ,p6b+1,Ϊչ.
Ϊ1/kչ,ɶ1֪,k
(-p0+3p1-3p2+p3).k3+(3p0-6p1+3p2).k2+(-3p0+3p1).k+p0-p6=0.
ȡ̵xͶӰ,ɿʽk.֤ʽyͶӰ,㷽,b1,b2N1ϲ,N1b1,b2=b1,b2.㷽,ʾp6ڵȫչb+1,b+1Bzier߶εĿƵp4p5.
p4=p4,p5=p5 ,N1b1,b2=.,N1b1,b2=b1,b2.
,ظBzierߵż㷨.
4 23ڵ
ʵӦ,ڵN1źܴľ,ҪĽڵ.
4.1 2ڵN2
Ըģ0,ڣb1,b2B2,b1(p0,p1,p2,p3),b2(p3,p4,p5,p6),ηkֵ
(-p0+3p1-3p2+p3).k3+(3p0-6p1+3p2).k2+(-3p0+3p1).k+p0-p6x=0.
kֵ֮һ
(-p0+3p1-3p2+p3).k3+(3p0-6p1+3p2).k2+(-3p0+3p1).k+p0-p6,
Сpʾpԭľ,b1kչΪb+,յΪp6,b+Ĳ(Ϊb)ĿƵΪp4,p5.p4-p4,p5-p5,N2b1,b2= b.,N2b1,b2=b1,b2.
2N2˵N1ʵӦеı.ʵӦ,رǶBzierߵĽ༭,Ҫ֤߹⻬ǿڵ.ڴҪ,Ǹ˵3ڵ.
4.2 3ڵN3
ڣb1,b2B2,ǶN3,b1=b1(p0,p1,p2,p3),b2=b2(p3,p4,p5,p6).
1 Bzier߶b,Ϊp0,յΪp6,루b1,b2p0,p6,ͬĵλʸ,N3b1,b2=b.
2 ,N3b1,b2=b1,b2.
N3ľʵ.
Ϊb1p0,Ϊb2յp6.
bB1,ʹN3b1,b2=b,bƵΪp1,p2.N3,ɼ
(1)
,
(2)
ɻΪһĴη.ʵL10,L20,N3b1,b2=bbĿƵʽ(1)ã,,N3b1,b2=b1,b2.
N2N3滻㷨N1,͵õ˻N2N3Ľڵ㷨.
5  
ʵӦжԷֶBzierҪ,Ǹ3BzierߵĽڵԼ3ӵ㷨.ڻN1ӵ㷨,֤˾ķֶBzierΪBzier߱,Ϊʵ,ǸN1N2ԼǿN3.ʵӦȡ˺ܺõЧ.
߲ܷ,1971,ʿ,ҪоΪɫϵͳͼͼ.ſ˾,1971,ʿ,ҪоΪýϵͳ.
ͨѶϵ:ܷ, 100871,ѧѧо
ߵλѧѧоϢصʵҡ 100871
ο
1Eck M. Least squares degree reduction of Bzier curves. Computer Aided Design, 1995,27(11):845851
2,ҵ,Ⱥ.ͼѧ̳.:ѧ,1994
(Tang Rong-xi, Wang Jia-ye, Peng Qun-sheng. A Course on Computer Graphics. Beijing: Science Press, 1994)
3ҹ,.ͼѧ(2).:廪ѧ,1996
(Sun Jia-guang, Yang Chang-gui. Computer Graphics(2nd ed.). Beijing: Tsinghua University Press, 1996)
1998-03-03ո壩
