ѧ
JOURNAL OF SOFTWARE
1999 10 12  Vol.10 No.12 1999



һ͹ײĿ㷨
䡡ƽΪ
ժҪ֮ײײӦĻҲһϵͳܴ.ˣоײ㷨ײӦʵʱԾҪ.һ㷨⻷м⵽ײʱӦô㷨ײӦ֮ǰټ֮׼ȷײʱ䣬ܼʱ֮ײ.
ؼʡײ㣬ײӦײ⣬ʵ.
ͼšTP391
A Fast Algorithm to Calculate Collision Point Between Convex Polygons
WANG Zhao-qi1ZHAO Qin-ping2WANG Cheng-wei3
1(Institute of Computing Technology The Chinese Academy of Sciences Beijing 100080)
2(Department of Computer Science and Engineering Beijing University of Aeronautics and Astronautics Beijing 100083)
3(Science and Technology Committee General Department PLA Beijing 100034)
Abstract Collision point is basic information to physically-based collision response, but collision point finding is a burden task, which make real-time collision response very difficult. In this paper, the authors give an algorithm to find the very fast collision time and the collision points between two objects represented by convex polygon prior to collision response.
Key wordsCollision point, collision response, collision detection, virtual reality.
⻷м⵽ײ󣬽ײӦ֮ǰҪ֪Ϣ1ݣ ֮׼ȷײʱ䣻 ײʱ֮ײ.
еһЩ2,3Уü⵽ײʱΪײʱ.ʵϣ֮Ų.ͼ1ʾtiʱ̣ͼ1(a)ʾO1O2룻tʱ̣ͼ1(b)ʾO1O2ʼӴti<t<ti+1ti+1ʱ̣ͼ1(c)ʾO1O2֮䷢˴͸.ti+1ʱ̼⵽ײʱtʱ֮㷢ײ.ײʱ䲽dt=(ti+1-ti)ϴʱõײʱҲϴ󣬴Ӷײܲ׼ȷ.Ϊ߼㾫ȣҪײⲻʵʱײӦʵ.⣬֮ײ忪ʼӴʱ壬Ѿ͸ʱ֮ײһȷ.ˣٶ׼ȷؼ֮ײʱt䣬ʱ֮ײǽʵʱײӦҪ.

ͼ1
James K. Hahnķ2ǽʱ䲽dt=(ti+1-ti)ȡֵǳСdtʱĽٶΪ0.ȡdt̫С⻷ʵʱҪ.ȡdtϴʱܼĽٶΪ0.Madhav K. Ponamgiͨ̾ȷǷײ3.ľΪ0ʱཻ.Ϊ˱֤ÿμ⵽ײ֮ľΪ0ȻҪСʱ䲽dt˻ӰײӦʵʱ.Ϊҵ׼ȷײʱײ㣬Harmut Keller˽еΪ򼸺壬塢ȣַͨܵ.
һּ͹ײʱײĿ㷨FCPF(fast collision points finding).⵽⻷ĳti+1ʱ̷ײʱFCPF㷨Ըٶv1v2ͽٶȦ12ټ緢ײʱt䣬ҳʱ֮ײ.
1͹ײFCPF㷨
1.1
O1O2⻷е͹壬O1O2t0ʱ̲ײt1ʱײ(t0t1ֻһײ.O1O2ĵٶȷֱΪv1v2ٶȷֱΪ1ͦ2.v1v21ͦ2(t0t1 ʱھΪ.
1.2ۻ
1. һƽFָһnƽΪƽ.䷨ָһΪƽ棬һΪ.ڶ棬Լ䷨ָⲿ.
1. O1O2Ƿϵ1.1л.l=P1P2O1һߣFO2һ棬lF(t0t1ཻlFཻʱtc(t0t1ݣཻ֮һͼ2ʾ.

ͼ2
(1) lһ˵PiFڲཻ(lFıཻ)
(2) lFһཻһP
(3) lFཻһ߶P1P2.
2. O1O2Ƿϵ1.1л壬ཻʱΪTc(t0t1.l=P1P2O1һߣFO2һ.lF(t0t1ڵཻʱΪtctcTc.tc>Tc
(1) l=P1P2һ˵Pii=1,2tcʱFཻFڲ
a lһPjλFʱO1ڶPiڱбһl䣬Fཻʱtc<tc
b lһPjλFʱO2дһFFPiFཻʱtc<tc.
(2) ltcʱFһlཻڵP3αһֳ
a O2PһڵFFlFཻʱtc<tc
b O1PһڵF䣬lFཻʱtc<tc
c a롴bllཻlһ˵Pilһ˵PjO2Pĸ.ʱO2һFFPiFཻʱtc<tc.
(3) ltcʱFཻһ߶P1P2䣬3αһ
a O2P1P2䴦һڵF䣬lFཻʱtc<tc
b O2P1P2Fһl䣬O1lһڵF䣬lFཻʱtc<tc
c a롴bһPilĶ˵㣬Pi=P1.O2һFFP1Fཻʱtc<tc.
1.3FCPF㷨
⵽⻷֮䷢ײʱֱ͹O1O2ʾȡһһlһһFlO1FO2lFཻ.lFཻʱtclFཻ.ɶ1֪lFֻཻ3.ÿΣǷʹtc>TcΣǷtc<tcO1O2tcʱཻ.ûУtcO1O2ཻʱTc.tcΪµtcѰҸСtc.Tc󣬱ཻĵ㣬Щ㼴Ϊײ.㷨1FCPF㷨.
㷨1. FCPF㷨.
(1) ʼ
tc=t1+1; ȡһt1ֵ
R=;R ʾײ.ײ͡ײ㼯
S={l,F,O1};SдΣʼʱΪһ֪ıཻʵ
(2) SΪʱ
(3) ȡSĵ1Ԫe
(4) e=l,F,O1 ཻʱ
O1еlO2еFཻʱtc;
tc>tc,ת(2);
tc=tc,Rµײ㣩,ת(2);δʱ޸S
Ρtc<tc,
tc=tc;RRټµײ
Case 1: lĶ˵P1FཻF루Fıཻ
lһ˵P2λF
L={O1P1ı߼}
S={l,F,O1|lL};
S={l,P2,O2}
Case 2: lFһl佻ڵP
2={O2P}
1={O1P}
PlһP1lһP2PO2渺S={l,P1,O2}
S=;S={l,F,O1|Fʦ2}{l,F,O2|Fʦ1}S;
Case 3: l Fཻһ߶P1P2
lFıl1ཻڵP1䣨P1lFڲĽ㣬l1=.ʱP1==P1;
lFıl2ཻڵP2 P2lFڲĽ㣬l2=.ʱP2==P2;
S1=(l1==)?{l,P1,O2}:;
S2=(l2==)?{l,P2,O2}:;
22={O2P2䴦};
21={O2P1䴦};
12={O1P2䴦};
11={O1P1䴦};
S={l,F,O1Fʦ21Ȧ22}{l1,F,O2Fʦ11}{l2,F,O2Fʦ12}S1S2;
(5) e=l,P,O ཻʱ
PỌPOཻʱtc估ཻ֮ĶF
tc<tcS={l,F,O1}S;tc=tc;R=;
(6)
ת2.
1.4PO㷨
FCPF㷨У(5)Ҫһ壨O1ϵĶPһOO2ཻʱtc估Oཻ.PO㷨һ̵ϸ㷨.
(1) tmax=tc tcΪǰཻ֪ʱ̣
(2) ȡO2 һFPF棻
(3) Pڣt0,tmaxʱFƽཻʱt䣬󽻵P(t) PһFཻPO2ཻ
(4) ȡLΪFı߼
(5) WHILE L
ȡlL
lP(t)Ĺϵ
P(t)l
ȡFlڵΪF
tmax=t
ת(3)
(6) END WHILE
(7) PO2FཻཻʱΪt.
2㷨
FCPF㷨lFཻʱ̵Ĺ̼PO㷨PFƽཻʱ̵Ĺֵ̿ɣʱ临ĸ޹.
2.1㷨Ŀֹ()
FCPF㷨лɶͬtcǽЩtc˳Ϊһ{tcn}.FCPF㷨ֹ֪㷨ĿֹԵȼڸ㷨{tcn}Tc.֤{tcn}޲Tc.
1. ͬһtc㷨ֻ޸״̬.
֤FCPFһѭ̣ͬһtc㷨ѭĲtcӦļSԪظ.SԪظһ.FCPF㷨ѭʱtc仯ؼSеһԪ.ˣͬһtcFCPF㷨ֻѭ޲.Ҳ˵ͬһtc㷨ֻ޸״̬.
2. {tcn}.
֤赱ǰtc=ti.FCPF㷨ĵڣ4֪tc<tctcԭtcti+1.ˣеiti>ti+1{tcn}½.⣬еtiti>t0{tcn}½t0.ԣ{tcn}һ½½У.
3. {tcn}޲.
֤FCPF㷨УһtcO1O2һlO2O1ཻʱ.ͬtcӦڲͬı.tcĸO1O2֮ı.O1O2ΪȷĶ壬ȷġ޵ģԣO1O2֮ıҲһ.ɴ˿֪tcĸ޵ģ{tcn}һУȻ޲.
3֪,{tcn}޲Tc.
2.2㷨ʱ临
FCPF㷨ӵڣ26һѭ.ѭ{tcn}Tc̣ѭ{tcn}TcNt.ΪÿtcӦһཻıԣˣ{tcn}TcNtᳬཻı.⵽ײʱײO1O2ཻıֱΪn1m1n2m2ཻın1m2+n1m2.ԣNt<n1m2+n1m2.n=max(n1,n2)m=max(m1, m2)㷨µʱ临ΪO(nm).
һ˵ײʱ䲽dt=t1-t0С֮䷢ཻıߺȻҲ٣NtС.ʹdtϴʱFCPF㷨Ȼ׼ȷؼײʱt估ײ㣬ҿЧ͹ԣʹPO㷨.
3ʵϸ
FCPF㷨ֵ̿ɣ1 O1һABO2һFཻʱ̣2 O1ĶPO2һFཻʱ.O1O2Ƿϵ1.1л͹.ABO1һߣFO2һ.
3.1ϵ
ϵϵԭΪO3λֱΪi,jk.
οϵοϵԭȡO2ģԼΪO2.2=0ʱοϵ3λ䣺i=ij=jk=k20ʱȡkΪ2ĵλK=2/2ijֱȡk䴹ֱλi,jk乹ϵ.ϱ꣨Rʾڲοϵеıʾ.磺r(R)P(R)Ϊ͵ڲοϵеıʾ.
2=0ʱοϵΪϵƽϵ.20ʱοϵΪϵƽתϵ.i,jkʵtĺǼit,jtktΪtʱ̲οϵ3λ.i0,j0k0ʾt0ʱ̲οϵ3λ.
裺i0,j0, k0T=A0i, j, kTУ
(1)
3.2P,ABFڲοϵеķ
O1ĶPڲοϵе˶Ϊ
(2)
A,Bڲοϵе˶̷ֱΪ
(3)
(4)
߶ABtʱڵֱڲοϵеķΪ
(5)
t(t0,t1,uʣ0,1,ȡnΪO2FķQΪFһ㣬FڲοϵеķΪ
(6)
3.3ABFཻʱ
ABFཻʱ̼ʽ(5)ʽ(6)ʽ䣨t0,t1ʹuʣ0, 1ݵСt.
3.4PFƽཻʱ
Pڣt0, tmaxFƽཻʱtʽ(2)ʽ(6)ʽڣt0,tmaxڵСt.
4ܽ
һּ͹ײĿ㷨.㷨Կ״͹ľȷײʱײ㣬˻ԵʵʱײӦһҪ.㷨ص㣺(1) ⵽ײʱʹ֮ѷĴ͸㷨ܼ֮׼ȷײʱײ;(2) ֮жײʱ㷨ҳеײ㣻(3) ײʱƽƣҿת(4) ΪһĶ嶼ԷֽΪ͹ϣˣ㷨Ծʵ޸ģӦһΣкܺõͨ.
*оõ863߿ƼĿ͹ҿƼ塱Ŀ.
߼飺䣬1966ʿҪоΪʵ.
ƽ1948ʿڣʿʦҪоΪ˹ܣʵ.
Ϊ1933ڣʿʦйԺԺʿҪоΪģּϵͳ棬˹ܣʵ.
ͨѶϵ:䣬100080,2704
ߵλ䡡йѧԺ㼼о100080
ƽպѧѧ빤ϵ100083
ΪйžװѧίԱᡡ100034
E-mail: zqwang@ict.ac.cn
ο
1䣬ƽΪ.⻷Եıʾ봦.о뷢չ.199835297101(Wang Zhao-qi, Zhao Qin-ping, Wang Cheng-wei. Study on representing and handling physical properties of objects in a virtual environment. Computer Research and Development, 199835297101)
2Hahn J K. Realistic animation of rigid bodies. ACM SIGGRAPH, 1988,22(4):299308
3Lin Ming C. Efficient collision detection for animation and robotics Ph.D. Thesis. Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, 199
1998-10-14յԭ,1999-01-11յ޸ĸ
