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



ײо
־ǿ
ժҪ ֮ĸײͼѧ桢ʵȼеõ㷺о кҪ.´ƽеĿײ⡢ƶ⡢ײļ⡢ άռпײԼײȼײоͷչһȫ ײ㷨ЧʺͿɿԵ3㽨.
ؼʡ棬ײ·滮ɨ壬ռֽ.
ͼšTP391
A Survey of Collision Detection Problem
WANG Zhi-qiang HONG Jia-zhen YANG Hui
School of Civil Engineering and Mechanics Shanghai Jiaotong Uni versity Shanghai 200030
Abstract The interference and collision detection problem among objects is widely studied in graphics, simulation, animation and virtual reality technologies etc., and h as great signification. A comprehensive survey of study and development of colli sion problem is given in the field of the collision detection, the movable distr ict and the first collision part in 2D and the collision detection and collision avoidance in 3D.
Key wordsInterference, collision, path planning, swept solids, space partitioning.
żͼѧ漼Ӳķչøļʵ ģٴѳΪ.ܶרҺѧ߶оڶʾģеһҪ --֮ĸײۺʵʷҪֵо.ͼ ƶʱײڼͼѧCAD/CAM̬ϵͳģ⡢ѧԼʵʱ 沼ֵжŹ㷺Ӧ.
ײǣ浽ײײӦ.ײӦѧо ʱҪײо뷢չһȫ.ײľӦú 㷺,⻷ӦеķԱԱѵ˵·滮ѧϰ ʽϵͳװCADɵϵ.ײⰴ˶Ŀռ ɷΪάƽײάռײ.ƽĹ춼öʾ 㷨ҪһЩάĹȽϸӣ,ײ㷨ҲȽ .
ƽײоҪ3,ײƶײλļ .άռײоһпײײ.νײ ABڿռظ켣ƶʱǷײ.ƶAظĹ˶, Bײп˶.ײļǵAԸ˶ ˶,BײʱײʱĽӴλ.ײܾ ײ˶.ľʹ⼸,ײоͷչһȽ ȫ.
1 ƽײ
10רѧ߶ƽײоȡһЩܺõĽ 㷨.
TetsuyaToshiakiMarioһֳΪռռеķĿռƶ, ͼռͬʱǵײ1.㷨һԭû κռͬһ,ҲҪļײ.ңǵķ ,ÿͬռе3Dռжһ֣֪ ĸ巢ײ.
ChinWangоεཻС.ÿӱ͹Ķ ĵԣб͹n-κһ򵥷͹m-εཻ 2,о˵ཻʱһǷһȫ ⣬ʱ临ӶȶΪO(m+n).
СĶӼķоһ͹һƶʱǷ һ͹ηײ,б֧ߵķоһ͹һ͹ Ŀƶ3ݣʱ临ӶΪO(log(n+m))O(m+n)㷨 ڳ,Ƕŵ.
ƽŻоƽཻ͹PQPظƶ ʱQײ۰ȷPQײʱߵײĶͱ 4ݣʱ临ӶΪO(logm+logn)㷨.
ҵõоһε͹һβཻ£ȷ Ƿײײʱȷȫײλ5ݣʱ临ӶΪ O(m+n)㷨㷨ƹ㵽ȷԲߵĶ֮ײ λ.
컪͹ζ㼯ϵƫϵķж͹PƽƷʽ˶ʱǷQײж6.жײԵµĳ ֱҪʱ临ӶΪO(logn)㷨.
David Baraffоƽڶ͹εײ⣬ýηֽΪ͹ε ײ⣬ʵʻ͹εײ7.
⣬ƽף810о˶ײһЩ. һ㶼һ͹λһ򵥶ε͹һཻµ ײ⣬ε͹пཻʱ򵥶εײоý .
2 άռײ
ӶƽײоУɵõļ.ڿռ䣨3DΣ ǱԿ˷ѣҲƽײѵõо,˺ܶ 㷨,ڿռиЧ㷨һԭ.ܶѧƶоģά Ȥ.ĸռͬĿռ.ͨĸ ࣺ̬Ͷ̬ײ.̬ײض켣ƶĸ. ̬ײ㷨ֿɷΪࣺ жƶ֮Ƿײ༴ײ; ⵽ײĴڲȡʩй,Ҳײ.ھ̬㷨Ƕ ̬ײ㷨ĻȶԾ̬㷨ҪĽܣȻٶԿײ ײ.
2.1 ̬㷨
ʵʾģ͵Ĳͬʵ㷨¿ɷֳ.һ㷨Ҫ B-repģ.㷨ЧʵĹؼμٱԪص.ⷽ,Ganter11 ÿռָµĳ.һ㷨ԲģΪģ,ף12,13 İ˲㷨ף14ĲSphere㷨.ڲģ ڵļ֮ȱֱϵһϵĸûзӳ һνڵ״̬Ϣ޷Լ̽ŻԼٲҪ.
2.2 ײ
ʷҪ༼ڶ̬ײ.1༼һֻڸ켣Ϸþ ̬ⱻΪ⡱ķƶн켣Ϊܶʱ䲽 ÿһʱ䲽о̬,ж˶֮Ƿײ.Maruyama˶ ֮ľ̬ĵ1һ㷽15ݣһֵݹռָ㷨 һһཻ㷨.ȻBoyse˵1ֿõĵϵͳ16. 㼸ཻԼ˹淶ͷ.༼Ƕάཻ չ17,18.
2༼ǻڲ֮Ϊɨʵ塱.Щڸ켣ƶ ռеռ.еǸԵĹ켣нʱᷢײô ǸԵɨ彫ᾲ̬.ɨü򵥵ľ̬Զ̬ײв .ЩɨĲ˶ѧʵģ͵Ľ.ʵģ;жֱʾʽ, ʽɨ屻.ʵ弸ģͣCSGCameron19ݺWang 20ݶ.Cameronƶ̬ΪӴ⡱,չʱ-չ.ȻWa ngרעڷչðCSGɨ,ɨʵ.߽ʾģʽB- RepKorein21ݺGanter22оͷչ.Korein ļо˿켣.GanterɨʵĹ,һĹ ,͹.Ganterع켣ӦýҪһɨж̬ .Cameron23һԼķγɡS-߽硱,CSG ЧཻԷ.S-߽ͨCSGϴĴཻĴ.
ȻɨȤĹ⣬ڵļͼӲ,ⷽ ʺʵʱͼʾ.ɨ巽Ҳûеⷽеľײʱ .ɨײҪһĲɨʵ.
GanterIsarankuraչ˵ⷽ11ݣһֿռָķ ֿռָĿռ仮Ϊһӿռ䣬еĲ صֲ.,صڵеӿռ䶼ǵСֵ .Ȼڿռָ,ӿռĸӰ쵽ȷԺ㷨Ч. ӿռ䣬ķѴļʱ;ӿռĸ٣ᷢ©л .
HahnòΰΧмٶ峡ײ24.Moore Чײ㷨25ݣһʷֹ.һ ɱʾһϵƬײ㷨ձ.㷨ȱ,Ϊ һӵĵʱʷֿܲƬӰ㷨Ч.һ 㷨廷ײ.MooreWilhelems25ݸCyrus-Beck 㷨26һ͹ײ㷨ͨ嶥Ƿ໥ жǷײ.ھn͹塢ÿm, ʱ临ӶΪO(n2m2);ڰֽΪ͹.Baraff,H erzen˻ڲļײ㷨.BaraffײתΪһ ʽԼ̣ɴ˿ɷؾǷ27.Herzenֵ ڽӴ㴦㴦ĲֵжǷཻ,Ӧòϸּ2 8.DaiΪ͹ǡǺǣȻĵľǰ뾶֮͵Ĺϵ жǷײײȡǵĽ29.GanterIsara nkuraһֿռָķռеĿռ仮ֳһϵӿռ䣬 ײ޶صӿռнУصӿռԪضС ,Ӷһ˲ʱ11.µĴʱΪO(*N2/2)*N صĵԪܸ.ڿռָ㷨УӰ㷨ЧʵһҪǷ Ķ.վ,ŷĿӦܵĵԪ125%֮.Alonso, Serrano FlaqueröײӰԪݽṹһЩŻӿײ3 0ݣǵ㷨4ĸ棺(1) ײӰ(2) ÿ ֮ĸ棻(3) Ԫ֮ĸ棻(4) ֮ĸ.㷨Ļ˼ ÿһһ죬,ĳһ岻ײ,ͲؽĲ ԣӶɽʡʱ.
ᵽоҪԡӲ塱,״.ʵ,ԡӲ һЩҲӦڡġƷ.磬֯ĴͳƷ ӦƷ.HindsMcCartneyѵ漼Ӧ3DƹУ31. Bez,BricksAscoughڲװģϵͳаײӦ32. ˼,ǱڵĸݻתɶԳƵݻ,Ȼתݻռнйײ .ַĹؼ֮תF溯F-1Ĺ죬ת Ч,ַҲǼЧ.
2.3 ײ
ײϵײ˶.ײܿԷΪࣺ˶̬ ·滮;̬ײ㷨.
ײⷽҪ.һ෽Ҫھ̬ĳһ·. 㷨ҪӦ2Dռ.һ෽Ӧƶοռ.㷨ֻ ڽһε.һ棬Щھ̬·Ԥȼ.绷 ı䣬̶.Ǻܺķʱ.һ̬һ෽Ҳ Ч.෽ͨеһϵŸ·в,Ȼ һ˶.·ĲС½У˶ܹ򵥵ؿ. ҲǶһ⹹˶ײ滮.Dai29ķҲ ⷨ.ö˶ѧ·ֵ.ַŵ, ˶Ĺ޹.пǾֲ˶·ķȱ,һҪ ײͱ巢ײ.
˶·滮УÿλúٶȱԤ֪.ErdmannLozano-Pe rez33ѡȡûײ·ֹײ硰-ԡģ ʽ.ַÿ帳һȼȼһβһ·. ÿһ·ϵͳͶѾڵ·ཻ.緢ཻ͸ı ·ظ.ཻϵͳ,һȼ .
-ԡı--οռ䷽34Whitesides. 屻һ,ϰﰴƶСıɡ.ײ ֲ,ƶܹһ.ڡοռ䡱,ײ·ͨ ڳʼĿλɺϰĶֱ֮Ӷ.ּչ άռ,ڲϰʱҲҪĽ.
Cameronһ·滮֮Ϊάཻԡ35ݷ.ַ ʱҲΪһά.3D屻ʱά죬µ4D.ûм ⵽ײ·ײ.ַҪǸܿǵ״ ˶ĸӳ̶.״˶ֳкܺãǱȽϸӵ ·Ͳܺܺõش.
Cameronͬˡάཻԡһֱ.ȡһά,һ ʱɨµ3D36.ײôǵɨ һཻ.ֱַ,ȴо.еһǺرʾɨ,һ ڽʱȱټʱϢ.
·滮ǿ֮ǵĸ߾ȷ.ܵײ©ѡȡ· ŵ.ȻҲмȱ.һҪķҪԤ֪һλúٶ,һ ȱǼ㸴Ӷ.һЩ·滮һܴľ,ǽһƶ --뱣־ֹ.
ײ㷨ĵ2Ǿ̬ײⷽڼٵײ,һϵоֹ״̬, ȡʩ.Щ㷨ضʱ䳡϶,ȻЩʱƬڽཻ .屻ʱཻԾͼ֮κص.Էص λþͻᱻıģײ,Ȼظ.
Cameronһַײ⼼36.ַʱ ʱһϵʱ䲽ϵλãÿһʱ䲽Ƿཻ.һ ײ⵽巵صǰһײ״̬--ΪĿ洢--Ȼ ·ı,Աײ.
ʽһ־̬㷨Khatibģһ˹Ƴֹײ 37.ϵͳ,屻һĿ,ȻĿ˶.ϰﱻų ΧĿƶ.ƶӽһϰʱĿϰ ųĺʩ.ƶӽϰʱ,ų,ǵĺ ʹƶĿƶвϰ﷢ײ.
ַһȱ,ƳҪӼϰ.ڸ, ͱô׾.⣬ɽӽ̶ģ㷨ܵʧЧ.
KroughڼƳʱλöҰٶȵİ취չKhatibĹ38 .ַKhatibķһе帳һ֪ĺ͹涨ʵģ. Ҫ֪ⲿ˵,Լ̫.
BorensteinKoren39ݶһƶĻͬķ,ݻ˵Ĵ ݵǿų.ϰӽʱBorensteinKorenһ ϰųû˵ĴϰĴڵȷ. ԽһǽĴǽԽǿ,㷨ʩӵĳԽ.Ȼ ַƶ˵2Dռ.⣬ĴСðװڻϵĴ ķϢ.ַڼģ⻷.
HubbardΪ˱֤Զһײ㷨40.ϵͳУ÷ Χ.Χ֮ײ㷨ʵཻԵЧCPUʱ𽥾 .
EgbertWinklerΪڶжԶƶ֮Զײܽʵʱһ ָĽľ̬ײ㷨41.ַԳеԶزų˲ ƶ嶼ܵڽӰ.ƶ˴˽ӽʱ ǵųöʹǱ˴˷ֿ.㷨ѵľȷ .һѵڰ˲еСȷ.
̬ײ㷨ԽǲҪԤ֪λúٶȣҶ˶ ҲܹһȻķʽ.̬㷨ҪǵĲԣײ ܱ©.ʹһײһʱ䲽һʱ䲽,һ ཻ״̬ȫ˴˴͸һֲཻ״̬ʱƶľ㹻.
3 
ײҪԣõܶרѧߵĹעо˸ָķ ߼㷨ĿɿԺЧ.ҪǴ¼֣
(1) þΰΧлΰΧռײʱཻԣڴ¶ ײ.Ȼð˲Ԫռ䷨ȥְΧв.һ ˵ԪԶνпռĲμģ,ڽʵʱײʱһ Чķ
(2) õⷽײʱʱ䲽ϴʱͻᷢȫ͸ 㷨ȴδ.һȷķǲһάռ䣬 Ŀʼͽʱ䲽֮һ4D,ڴ͸ԣ
(3) ÿռͶӰķ,ͶӰһϹײ, ŵķ,һСһӦطŴ,Ӷײ.
˲༸ģڽײĿ֮ļθʱ,ȵ 㷨ЧʣȻһЩ,ʵģ,Ч㷨Ч.ģ, 粼Ͳ,ײʵʱΪҪȶα߽ ģʹö.
ʵʱײ෽Ҫһֺ̽оģ֮͡ײ ֮ĿռһԼӴ͸ֵ֮.,3Dռײ ʱӴж.
оõȻѧ͹Ҳʿר.
־ǿ,1971ʿ,ҪоΪ漰ӻ.
1 944,ʿʦҪоΪӻеϵͳ㶯ѧ.
 ,1972ʿ,ҪоΪӻеϵͳ㶯ѧ.
ͨѶϵ:ԣϺ200240Ϻͨѧ97100BA
ߵλϺͨѧѧѧԺϺ200030
E-mail: yh70643@online.sh.cn
ο
[1]Tetsuya U, Toshiaki O, Mario T. Collision detection in motion s imulation. Computer & Graphics, 1983,7(2):285293
[2]Chin F, Wang C A. Optimal algorithms for the intersection and the min imum distance problems between planar polygons. IEEE Transactions on Computers, 1983,C-32(12):12031207
[3].͹οƶԵб㷨.йѧA198717(12 )13011308
(Li Hui. An optimal algorithm for deciding movability of convex polygons. Chines e Science(A), 1987,17(12)13011308)
[4]ƽ,Ż.ȷ͹ƽʱײλ㷨.ѧ ,1992,15(3):171177
(Qin Zhong-ping, Zhang Huan-guo. An optimal algorithm of determining the touch parts between two colliding convex polygons. Chinese Journal of Computers, 1992 ,15(3):171177)
[5]ҵ.ƽϼ򵥶ƽʱȷײλ㷨.ѧ 1992,15(8):582588
(Wang Jia-ye. An optimal algorithm of finding first contact between translating polygons. Chinese Journal of Compu-ters, 1992,15(8):582588)
[6]컪.ж͹οײ㷨.ѧ199215(8):589 596
(Li Qing-hua. Optimal algorithm deciding possible collision of convex polygons. Chinese Journal of Computers, 1992,15(8):589596)
[7]David Baraff. Interactive simulation of solid rigid bodies. IEEE Computer Graphics & Applications, 1995,15(5):6375
[8]ƽŻ.תʱĿƶ.ѧ1994,17( 1):5257
(Qin Zhong-ping, Zhang Huan-guo, Gao Xiang. Rotational movability for polygons. Chinese Journal of Computers, 1994,17(1):5257)
[9]ƽŻ.εķԲ.ѧ1994,17(4):2 57263
(Qin Zhong-ping, Zhang Huan-guo. Direction and arc visibility for polygons. Ch inese Journal of Computers, 1994,17(4):257263)
[10]ƽŻ.ƽڶ߶̬ƶʱײж㷨. ѧ1997,20(6):567572
(Qin Zhong-ping, Zhang Huan-guo. Optimal algorithm for deciding collision of p olygons in rigid body displacement along curves. Chinese Journal of Computer s, 1997,20(6):567572)
[11]Ganter M A, Isarankura B P. Dynamic collision detection using space p artitioning. Journal of Mechanical Design, Transactions of the ASME, 1993,115(1) :150155
[12]Ahuja N, Nash C. Octree representations of moving objects. Computer V ision, Graphics and Image Processing, 1984,26(2):207216
[13]裬ܼ.ÿռָİ˲㷨.ѧ 1997,20(9):849854
(Wu Ming-hua, Yu Yong-xiang, Zhou Ji. An octree algorithm for collision detect ion using space partition. Chinese Journal of Computers, 1997,20(9):849854)
[14]Pobil A P del, Serna M A. A new representation for robotics and artif icial intelligent application. International Journal of Robotics & Automation, 1 994,9(1):1121
[15]Maruyama K. A procedure to determine intersection between polyhedral objects. International Journal of Computer and Information Science, 1972,1(2):21 9242
[16]Boyse J W. Interference detection among solids and surfaces. Communic ations of the ACM, 1979,22(1):39
[17]Preparata F P, Shamos M I. Computational Geometry--An Introduction. New York: Springer-Verlag, 1985
[18]Edelsbrunner H. Algorithms in Combinatorial Geometry. Berlin: Spring er-Verlag, 1987
[19]Cameron S A. A study of the clash detection problem in robotics. In: Fu K S ed. Proceedings of IEEE International Conference on Robotics and Automation. S t. Louis, Mo.: IEEE Computer Society Press, 1985. 488493
[20]Wang W P, Wang K K. Geometric modeling for swept volume of moving solids. IEEE Computer Graphics & Applications, 1986,6(12):817
[21]Korein J U. A geometric investigation of reach Ph.D. Thesis. Universit y of Pennsylvania, University of Microfilm #84-17323, 1984
[22]Ganter M A, Uicker J J. Dynamic collision detection using swept solids. AS ME Journal of Mechanisms, Transmissions and Automation in Design, 1986,108(4):54 9555
[23]Cameron S A. Efficient intersection tests for objects defined constructive ly. International Journal of Robotics Research, 1989,8(1):325
[24]Hahn J K. Realistic animation of rigid bodies. Computer Graphics, 1988,22( 4):299308
[25]Moore M, Wilhelms J. Collision detection and response for computer animati on. Computer Graphics, 1988,22(4):289298
[26]Rogers D F. Procedural Elements for Computer Graphics. New York: McGraw-H ill Book Company, 1985
[27]Baraff D. Analytical methods for dynamics simulation of non-penetrating r igid bodies. Computer Graphics, 1989,23(3):223232
[28]Herzen B U, Barr A H, Zatz H R. Geometric collisions for time-dependent p arametric surfaces. Computer Graphics, 1990,24(4):3948
[29]Dai F. Collision-free motion of an articulated kinematics chain in a dyna mic environment. IEEE Computer Graphics & Applications, 1989,9(1):7074
[30]Alonso A G, Serrano N, Flaquer J. Solving the collision detection problem. IEEE Computer Graphics & Applications, 1994,14(3):3643
[31]Hinds B K, McCartney J. Interactive garment design. Visual Computer, 1990, 6(2):5361
[32]Bez H E, Bricis A M, Ascough J. A collision detection method with applicat ions in CAD systems for the apparel industry. Computer-Aided Design, 1996,28(1) :2732
[33]Erdmann M, Lozano-Perez T. On multiple moving objects. In: Wesley M A ed. Proceedings of IEEE International Conference on Robotics and Automation. Piscat away, N J: IEEE Computer Society Press, 1986. 14191424
[34]Whitesides S H. Computational geometry and motion planning. In: Toussaint G T ed. Computational Geometry. North-Holland, Amsterdam: Elsevier Science Publ ish Company, 1985. 377427
[35]Cameron S. Collision detection by four-dimensional intersection testing. IEEE Transactions on Robotics and Automation, 1990,6(3):291302
[36]Cameron S. A study of the clash detection problem in robotics. In: Fu K S ed. Proceedings of IEEE International Conference on Robotics and Automation. Pis cataway, N J: IEEE Computer Society Press, 1985. 488493
[37]Khatib O. Real-time obstacle avoidance for manipulators and mobile robots . In: Fu K S ed. Proceedings of IEEE International Conference on Robotics and Au tomation. Piscataway, N J: IEEE Computer Society Press, 1985. 500505
[38]Krough B H. Integrated path planning and dynamic steering control from aut onomous vehicles. In: Wesley M A ed. Proceedings of IEEE International Conferenc e on Robotics and Automation. Piscataway, N J: IEEE Computer Society Press, 198 6. 16641669
[39]Borenstein J, Koren Y. Real-time obstacle avoidance for fast mobile robot s. IEEE Transactions on Systems, Man, and Cybernetics, 1989,19(5):11791187
[40]Hubbard P M. Collision detection for intersection graphics application. IE EE Transactions on Visualization and Compu-ter Graphics, 1995,1(3):218230
[41]Egbert P K, Winkler S H. Collision-free object movement using vector fiel ds. IEEE Computer Graphics & Applications, 1996,16(7):1824
1998-07-19յԭ,1998-12-15յ޸ĸ
