变形物体碰撞检测技术研究
摘要
碰撞检测及其相关问题有着悠久的研究历史,在计算机图形学、计算几何、机器人学、CAD/CAM等研究领域具有十分重要的作用。近年来随着虚拟现实、分布交互仿真等技术的兴起,人们对交互的实时性、场景的真实性的要求越来越高,变形物体的实时碰撞检测成为了研究的热点。本文在对各类碰撞检测算法作出全面了解和透彻分析的基础上,从以下几个方面对变形物体的碰撞检测问题进行研究,提出新的检测碰撞的思想和方法,从而使碰撞检测技术有进一步的发展。
(1)从提高碰撞检测的实时性和通用性方面入手,将人工智能中经典的粒子群优化算法引入到碰撞检测领域,提出了应用粒子群优化算法的通用随机碰撞检测算法。该算法在继承一般碰撞检测算法优点的同时,突破了它们的局限性,不但能够在保证效率的前提下处理无拓扑物体的碰撞检测问题而且也可以处理任意物体表示模型之间的碰撞检测,具有较强的通用性;此外检测精度和速度可以人为的调整以满足不同应用的需求,增加了碰撞检测系统的灵活性。
(2)结合层次包围体树结构和随机碰撞检测算法的优点提出了一种大型复杂变形物体的快速碰撞检测方法。该算法利用层次包围体树快速剔除物体上不相交的区域,只在碰撞了的节点内进行智能搜索,既避免了单纯采用粒子群优化方法目标空间过大造成的搜索速度慢的缺点,又减少单纯使用层次包围体树的方法所消耗的大量存储空间和更新速度慢等问题。
(3)在分析研究虚拟装配领域的实际问题的基础上,针对虚拟装配系统中的变形物体的特点,提出了一种基于组件的碰撞检测技术。其中重点研究了基于物体OBB包围盒的组件层次包围体树的构建和更新问题,提出了快速的组件OBB包围盒的生成算法、求两OBB包围盒凸壳的快速算法和N个物体构成组件层次体树的建构与更新的方法。实验证明组件模型具有构建层次分明、运动更新简便、能完成自我碰撞检测等诸多优点。
Collision Detection (CD), also called Interference Detection or Contact Detection, is a fundamental operation used in a variety of areas such as computer graphics, computer animation, robotics, computational geometry, visualization and more. Efficient and exact collision detection is very important to improve reality and enhance immersion for virtual environment, because most often collision detection is performed in real-time environments that require an interaction with users. Frequently, the models that are used consist of very large geometric primitives that consume a lot of time to process, which often becomes the neck of bottle in the whole application. So how to improve the efficiency and accuracy is the main task to all researchers in this area.
The collision detection problem has been studied extensively in the literature and numerous collision detection methods have been extensively developed in this area. These approaches can be divided into two main classes of algorithms. The first one is feature-based which uses temporal and spatial coherence to maintain the close features. One example is to tile a grid of voxels and assign objects to the voxels that contain them. The second and most widely class uses hierarchical bounding volumes trees (BVHs). The idea is that levels of bounding volumes cover the objects. At the top level, the bounding volume bounds the entire model, and at the bottom one, it bounds primitives. In between, it bounds subsets of primitive. One of the design choices with BV trees is the type of BV. In the past, a wealth of BV types has been explored, such as spheres, AABBs, OBBs, DOPs, and Convex Hulls.
The known collision detection algorithms usually have been demonstrated to work
(1)从提高碰撞检测的实时性和通用性方面入手,将人工智能中经典的粒子群优化算法引入到碰撞检测领域,提出了应用粒子群优化算法的通用随机碰撞检测算法。该算法在继承一般碰撞检测算法优点的同时,突破了它们的局限性,不但能够在保证效率的前提下处理无拓扑物体的碰撞检测问题而且也可以处理任意物体表示模型之间的碰撞检测,具有较强的通用性;此外检测精度和速度可以人为的调整以满足不同应用的需求,增加了碰撞检测系统的灵活性。
(2)结合层次包围体树结构和随机碰撞检测算法的优点提出了一种大型复杂变形物体的快速碰撞检测方法。该算法利用层次包围体树快速剔除物体上不相交的区域,只在碰撞了的节点内进行智能搜索,既避免了单纯采用粒子群优化方法目标空间过大造成的搜索速度慢的缺点,又减少单纯使用层次包围体树的方法所消耗的大量存储空间和更新速度慢等问题。
(3)在分析研究虚拟装配领域的实际问题的基础上,针对虚拟装配系统中的变形物体的特点,提出了一种基于组件的碰撞检测技术。其中重点研究了基于物体OBB包围盒的组件层次包围体树的构建和更新问题,提出了快速的组件OBB包围盒的生成算法、求两OBB包围盒凸壳的快速算法和N个物体构成组件层次体树的建构与更新的方法。实验证明组件模型具有构建层次分明、运动更新简便、能完成自我碰撞检测等诸多优点。
Collision Detection (CD), also called Interference Detection or Contact Detection, is a fundamental operation used in a variety of areas such as computer graphics, computer animation, robotics, computational geometry, visualization and more. Efficient and exact collision detection is very important to improve reality and enhance immersion for virtual environment, because most often collision detection is performed in real-time environments that require an interaction with users. Frequently, the models that are used consist of very large geometric primitives that consume a lot of time to process, which often becomes the neck of bottle in the whole application. So how to improve the efficiency and accuracy is the main task to all researchers in this area.
The collision detection problem has been studied extensively in the literature and numerous collision detection methods have been extensively developed in this area. These approaches can be divided into two main classes of algorithms. The first one is feature-based which uses temporal and spatial coherence to maintain the close features. One example is to tile a grid of voxels and assign objects to the voxels that contain them. The second and most widely class uses hierarchical bounding volumes trees (BVHs). The idea is that levels of bounding volumes cover the objects. At the top level, the bounding volume bounds the entire model, and at the bottom one, it bounds primitives. In between, it bounds subsets of primitive. One of the design choices with BV trees is the type of BV. In the past, a wealth of BV types has been explored, such as spheres, AABBs, OBBs, DOPs, and Convex Hulls.
The known collision detection algorithms usually have been demonstrated to work
引文
[1] 范昭炜,实时碰撞检测技术研究,博士学位论文,浙江大学,2003.
[2] Samet H., Spatial data structures: quadtree, octrees and other hierarchical methods. Addison Wesley, 1989,23–27。
[3] Naylor BF, Amanatides JA, Thibault WC., Merging BSP trees yield polyhedral modeling results. In Proceedings of ACM SIGGRAPH, 1990, 115–124.
[4] McNeely W, Puterbaugh K, Troy J. , Six degree-of-freedom haptic rendering using voxel sampling. In Proceedings of Siggraph 1999,401–408.
[5] Hubbard, P. M., Approximating polyhedra with spheres for time critical collision detection. ACM Transactions on Graphics, 1996, 15(3).179–210.
[6] Van Den Bergen, Efficient collision detection of complex deformable models using AABB trees. Journal of Graphics Tools .1997, 2 (4) .1–13.
[7] Gottschalk S, Lin, M. C. and Manocha. D.,OBB Tree: a hierarchical structure for rapid interference detection. In SIGGRAPH 96 Conference Proceedings, Annual Conference Series, ACM SIGGRAPH, New Orleans, USA, Aug. 1996,171–180.
[8] James T. Klosowski., Efficient Collision Detection Using Bounding Volume Hierarchies of k-Dops[C], IEEE Transactions on Visualization and Computer Graphics, Vol. 4, No. 1,1998,26–27.
[9] 魏迎梅,吴泉源,石教英,碰撞检测中的固定方向凸壳包围盒的研究,软件学报12(7).2001,105–109.
[10] Ehmann S, Lin M C. , Accurate and fast proximity queries between polyhedra using convex surface decomposition. In Proceedings of the Eurographics Conference, Manchester, 2001, 500–510.
[11] Wan HG, Fan ZW, Gao SM, Peng QS, A parallel collision detection algorithm based on hybrid bounding volume hierarchy, in Proceedings of CAD&Graphics’ 2001, Kunming, China, 2001, 521–528.
[12] Larsson T., Akenine-M?LLER T., Collision detection for continuously deforming bodies. In Eurographics , 2001, 325–333.
[13] Mezger J., Kimmerle S., Etzmuss O.: Hierarchical Techniques in Collision Detection for Cloth Animation. Journal of WSCG , 2003, 322–329.
[14] F. Ganovelli, J. Dingliana, and C. O'Sullivan. Buckettree: Improving collision detection between deformable objects. SCCG2000 Spring Conf. on Comp. Graph-ics, 2000, 156–163.
[15] Bridson R., Marino S., Fedkiw R.: Simulation of clothing with folds and wrinkles. In Proc. ACM/Eurographics Symposium on Computer Animation , 2003, 28–36.
[16] Frisken S. F., Perry R. N., Rockwood P., Jones T. R., Adaptively sampled distance fields: A general representation of shape for computer graphics. SIGGRAPH 2000, Computer Graphics Proceedings (2000), 249–254.
[17] Bremer P.T., Porumbescu S., Kuester F., Hamann B., Joyk. I., MA K.-L., Virtual clay modeling using adaptive distance fields. In Proceedings of the 2002 International Conference on Imaging Science, Systems,and Technology ,2002,127.
[18] Heidelberger, B., Teschner, M., and Gross, M.. Detection of collisions and self-collisions using image-space techniques. Journal of WSCG12, 3, 2004, 145– 152.
[19] Govindaraju, N., Lin, M., and Manocha, D.. Fast and reliable collision detection using graphics hardware. Proc. of ACM VRST, 2004.
[20] Baciu, G., and Wong, S. 2002. Hardware-assisted self-collision for deformable models. ACM Symposium on VRST, 129–136.
[21] Navazo I, Ayala D, Brunet P. A geometric modeler based on the exact octree representation of polyhedra. Computer Graphics Forum,1986, 5(2): 91–104.
[22] J.L. Bentley. Multidimensional Binary Search Trees Used for Associative Searching. Communication of the ACM, 18(9), September 1975,509–517.
[23] Naylor BF, Amanatides JA, Thibault WC. Merging BSP trees yield polyhedral modeling results. In Proceedings of ACM SIGGRAPH, 1990, 115-124.
[24] W. Bouma, G. Vanecek, Jr. Collision Detection and Analysis in a Physical Based Simulation. Eurographics Workshop on Animation and Simulation,Vienna, 1991,191–203.
[25] D. Kim, L.J. Guibas, S. Shin. Fast Collision Detection Among Multiple Moving Spheres. IEEE Transactions on Visualisation and Computer Graphics, 4(3), July-September 1998, 230–242.
[26] Taosong He ,Fast Collision Detection Using QuOSPO Trees,Symposium on Interactive 3D Graphics, Proceedings of the 1999 symposium on Interactive 3D graphics.Atlanta, Georgia, United States,1999, 55–62.
[27] J H Clark. Hieraachical Geometric Models for Visible Surface Algorithms. Comm.ACM19(10), 1976 .
[28] 张茂军,虚拟现实系统,科学出版社,2001,第一版,2–8。
[29] S. Suri. Analyzing Bounding Boxes for Object Intersection ACM. Transactions on Graphics, Vol. 18, 1999, 257–277.
[30] Jiménez P, Thomas F, Torras C. Collision detection: a survey, Computers and Graphics, 2001, 25(2),269–285.
[31] Gottschalk.S, Collision Queries using Oriented Bounding Box, Doctorial Dissertation, Department of Computer Science, University of N. Carolina, Chapel Hill.. 2000. 41–47.
[32] Y. Tao, D. Papadias, and J. Sun. The tpr*-tree: An optimized spatio-temporal access method for predictive queries. In VLDB, 2003, 790-801.
[33] G. Turk. Interactive collision detection for molecular graphics. Technical Report TR90-014, University of North Carolina at Chapel Hill, 1990.
[34] B. Mirtich. Efficient algorithms for two-phase collision detection. Technical Report TR-97-23, Mitsubishi Electric Research Laboratory, 1997.
[35] M. Teschner, B. Heidelberger, M. Mueller, D. Pomeranets, and M. Gross. Optimized spatial hashing for collision detection of deformable objects. In Proceedings of Vision, Modeling, Visualization, 2003,47–54.
[36] R. G. Luque, J. L. D. Comba, and C. M. D. S. Freitas. Broad-phase collision detection using semi-adjusting bsp-trees. Proceedings of the 2005 symposium on Interactive 3D graphics and games, New York,NY, USA, ACM Press,2005 , 179–186.
[37] S. Gibson. Using distancemaps for smooth surface representation in sampled volumes . In Proceedings of IEEE Volume Visualization Symposium, 1998, 23–30.
[38] B. A. Payne and A.W. Toga. Distance field manipulation of surface models. IEEE Computer Graphics and Applications, 12(1), 1992, 65–71.
[39] R. Westermann, L. Kobbelt, and T. Ertl. ,Real-time exploration of regular volume data by adaptive reconstruction of isosurfaces. The Visual Computer, 15(2), 1999, 100–111.
[40] J. Wu and L. Kobbelt. Piecewise linear approximation of signed distance fields. In Proceedings of Vision, Modeling, Visualization, 2003, 513–520.
[41] J. A. Sethian. A fast marching level set method for monotonically advancing fronts. Proceedings of the National Academy of Science, 93(4), 1996, 1591–1595.
[42] M. W. Jones and R. Satherley. Using distance fields for object representation andrendering. In Proceedings of Eurographics, 2001, 37–44.
[43] K. E. Hoff III, J. Keyser, M. Lin, D. Manocha, and T. Culver. Fast computation of generalized Voronoi diagrams using graphics hardware. In Proceedings of ACM SIGGRAPH, 1999, 277–286.
[44] D. E. Breen, S. Mauch, R. T. Whitaker, and J. Mao. 3d metamorphosis between different types of geometric models. In Proceedings of Eurographics, 2001, 36–48.
[45] B. Eberhardt, O. Etzmuss, and M. Hauth. Implicit-explicit schemes for fast animation with particle systems. In Proceedings of Computer Animation and Simulation, 2000, 137–151.
[46] C. Sigg, R. Peikert, and M. Gross. Signed distance transform using graphics hardware. In Proceedings of IEEE Visualization. IEEE Computer Society Press, 2003, 83–90.
[47] A. Sud, M. A. Otaduy, and D. Manocha. Difi: Fast 3d distance field computation using graphics hardware. In Proceedings of Eurographics, 2004, 557–566.
[48] A. Fuhrmann, G. Sobotka, and C. Gross. Distance fields for rapid collision detection in physically based modeling. In Proceedings of GraphiCon, 2003, 58–65.
[49] S. Fisher and M. Lin. Deformed distance fields for simulation of nonpenetrating flexible bodies. In Proceedings of Computer Animation and Simulation, 2001, 99–111.
[50] T. Vassilev, B. Spanlang, and Y. Chrysanthou. Fast cloth animation on walking avatars. In Proceedings of Eurographics, 2001, 137–150.
[51] G. Baciu and W. S.K. Wong. Image-based collision detection for deformable cloth models. In IEEE Transactions on Visualization and Computer Graphics, volume M. ACM Press, 2004, 649–663.
[52] Shinya and M. Forgue. Interference detection through rasterization. The Journal of Visualization and Computer Animation, 1991, 132–134.
[53] G. Baciu, W. S.-K. Wong, and H. Sun. RECODE: an image–based collision detection algorithm. The Journal of Visualization and Computer Animation, 1999, 181–192.
[54] K. Myszkowski, O. Okunev, and T. Kunii. Fast collision detection between complex solids using rasterizing graphics hardware. The Visual Computer, 11(9), 1995, 497–512.
[55] J. C. Lombardo, M.-P. Cani, and F. Neyret. Real-time collision detection for virtual surgery. In Proceedings of Computer Animation.IEEE CS Press, 10(6), 1999,82–91.
[56] G. Baciu and W. S.-K. Wong. Image-based collision detection for deformablecloth models. In IEEE Transactions on Visualization and Computer Graphics, volume 10(6), ACM Press, 2004, 649–663.
[57] Y. Kim, M. Otaduy, M. Lin, and D. Manocha. Fast penetration depth computation for physically-based animation. In Proceedings of SIGGRAPH Symposium on Computer Animation, 2002, 23–31.
[58] B. Heidelberger, M. Teschner, and M. Gross. Real-time volumetric intersections of deforming objects. In Proceedings of Vision, Modeling, Visualization, 2003, 461–468.
[59] J. Shade, S. Gortler, L. W. He, and R. Szeliski. Layered depth images. In Proceedings of ACM SIGGRAPH, 1998, 231–242.
[60] Stefan Kimmerle,collision detection and post-processing for physical cloth simulation, Dissertation, Tübingen,2005,28–31.
[61] 彭喜元,彭宇, 戴毓丰, 群智能理论及应用,电子学报. 31(12A),2003,1982–1988.
[62] Parsopulos K. E., Vrahatis M. N.. Recent approaches to global optimization problems through particle swarm optimization. Nature Computing. Kluwer Academic Publishers. 2002, 235–306.
[63] Eberhart, R. and Kennedy, J. A new optimizer using particle swarm theory[C], Proc. 6 Int. Symposium on Micro Machine and Human Science, 1995, 39–43
[64] Kennedy, J. and Eberhart, R. Particle Swarm Optimization[C], IEEE International Conference on Neural Networks (Perth, Australia), IEEE Service Center, Piscataway, NJ, 1995, IV: 1942–1948
[65] 曹春红, 几何约束求解技术的研究, 博士论文, 吉林大学, 2005.
[66] Shi, Y. and Eberhart, R. A Modified Particle Swarm Optimizer[C], IEEE International Conference on Evolutionary Computation, Anchorage, Alaska, 1998, 63–79.
[67] Shi, Y. and Eberhart, R. C. Parameter selection in particle swarm optimization[C], Evolutionary Programming VII: Proceedings of the Seventh Annual Conference on Evolutionary Programming, New York, 1998, 591-600.
[68] Kennedy, J. The Behavior of Particles [M]. In V.W. Porto, N. Saravanan, D. Waagen, and A.E. Eiben, editors, Evolutionary Programming VII, Springer, 1998, 581–590.
[69] Carlisle, A., Dozier, G..An Off-The-Shelf PSO [C]. In Proceedings of the ParticleSwarm OptimizationWorkshop, 2001, 1–6
[70] 周 驰,高海兵,高 亮 等,粒子群优化算法,计算机应用研究,2003,21(12),5–11.
[71] V Pareto. Cours DEconomies politique, volume I and 11. Rouge, Lausanne, 1896.
[72] Carlisle A,Dozier G. Tracking Changing Extrema with Particle Swarm Optimizer[R]. Proceedings, ICAI, 2001.
[73] 汪晗,基于进化计算的多目标优化与决策方法研究, 硕士学位论文,国防科学技术大学, 2002,6–9.
[74] K. E. Parsopoulos, M. N. Vrahatis. Particle Swarm Optimization Method in Multiobjective Problems. Proceedings of the 2002 ACM symposium on Applied computing. Publisher ACM Press New York, NY, USA, 2002, 603–60.
[75] Mikkel T Jensen. Reducing the Run-Time Complexity of Multiobjective EAs: The NSGA-II and Other Algorithms, IEEE Transactions on Evolutionary Computation, Vol. 7, No. 5, October 2003, 503–515.
[76] James Kennedy,Russell C. Eberhart, Swarm intelligence. Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001.
[77] Xiaodong Li., A Non-dominated Sorting Particle Swarm Optimizer for Multiobjective Optimization. In Erick Cant et al. (editors), Genetic and Evolutionary Computation-GECCO , Springer, Lecture Notes in Computer Science Vol. 2723, July 2003, 37–41.
[78] Gregodo Toscano-Pulido and Carlos A. Coello Coello. Using Clustering Techniques to Improve the Performance of a Multi-Objective Particle Swarm Optimizer. In Proceedings of the Genetic and Evolutionary Computation Conference. Part I, Springer-Vedag, LNCS Vol. 3102, Seattle, Washington,USA, June 2004,255–237.
[79]Fieidsend, J.E., Singh, S. A Mufti-Objective.Algorithm Based upon Particle Swarm Optimization, an Efficient Data Stricture and Turbulence. In: Proceedings of the 2002U.K. Workshop on Computational Intelligence, Birmingham,UK,2002, 37–44.
[80] Thomas Bartz Beielstein, Philipp Limbourg, et al. Particle Swarm Optimizers for Pareto Opmization with Enhanced Archiving Techniques. In Proceedings of the 2003 Congress on Evolutionary Computation (CEC'2003), IEEE Press, Canberra, Australia, December 2003, 1780-1787.
[81] Mostaghim, S., Teich, J.. Strategies for Finding Good Local Guides in Multi-objective Particle Swarm Optimization (MOPSO). In:2003 IEEE Swarm Intelligence Symposium Proceedings, Indianapolis, Indiana, USA, IEEE Service Center, 2003,26–33.
[82] Carlisle A,Dozier G. ,Adapting Particle Swarm Optimization to Dynamic Environments[R].Proceedings,ICAI,2000, 429–434.
[83] Hu.X. and Eberhart,R.C. Tracking dynamic systems with PSO:where’s the cheese? Proceedings of the workshop on particle swarm opyimization. Pirdue School of Engineering and Technology,Indianapolis,IN,2001.
[84] Hu, X. and Eberhart, RC Adaptive particle swarm optimization: detection and response to dynamic systems. Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2002), Honolulu, Hawaii USA., 2002,1666–1670.
[85] Uno S., Slater M.: The sensitivity of presence to collision response. In Proc. of IEEE Virtual Reality Annual International Symposium (VRAIS) (Albuquerque, New Mexico, 1997, 95.
[86] BARZEL R., HUGHES J., WOOD D. N.: Plausible motion simulation for computer graphics animation. In Proceedings of the Eurographics Workshop Computer Animation and Simulation (1996), Boulic R., Hégron G., (Eds.),Springer, 1996,183–197.
[87] M. Teschner, S. Kimmerle, B. Heidelberger, G. Zachmann, L. Raghupathi, A. Fuhrmann, M.-P. Cani, F. Faure, N. Magnenat-Thalmann, W. Stra?er, and P. Volino , Collision Detection for Deformable Objects, Computer Graphics Forum, Volume 24, 2005,119–140.
[88] Klen J., Zachmann G.: Adb-trees: Controlling the error of time-critical collision detection. In 8th International Fall Workshop Vision, Modeling, and Visualization (VMV), Germany, 2003, 19–21.
[89] S. Guy and G. Debunne. Monte-carlo collision detection. Technical Report RR-5136, INRIA, 2004, 564–567.
[90] L. Raghupathi, L. Grisoni, F. Faure, D. Marchal, M.-P. Cani, and C. Chaillou. An intestine surgery simulator: Real-time collision processing and visualization. IEEE Transactions on Visualization and Computer Graphics, 2004, 708–718.
[91] J. D. Cohen, M. C. Lin, D. Manocha, and M. Ponamgi. I-COLLIDE: An interactive and exact collision detection system for large-scale environments.In Symposium on Interactive 3D Graphics, 1995, 189–196.
[92] L. J. Guibas, D. Hsu, and L. Zhang. H-walk: Hierarchical distance computation for moving convex bodies. In W. V. Oz and M. Yannakakis, editors, Proceedings of ACM Symposium on Computational Geometry, 1999, 265–273.
[93] S. Kimmerle, M. Nesme, and F. Faure., Hierarchy accelerated stochastic collision detection. In Proceedings of Vision, Modeling, Visualization, 2004, 307–314.
[94] Brits R , Engelbrchta P , Bergh F D. A niching particle swarm optimizer [A]. Proc Conf on Simulated Evolution and Learning[C]. Singapore : IEEE Inc , 2002.
[95] Ester M, Kriegel H P, Sander J , et al. Density based clustering in spatial databases, the algorithm gdbscan and its applications[J].Data Mining and Knowledge discovery, 1998 (2) ,169–194.
[96] 王俊年,申群太,沈洪远,周鲜成,一种改进的小生境微粒群算法,山东大学学报(工学版) 35(3),2005, 98–102.
[97]马帅,王腾蛟,唐世渭,杨冬青,高军,一种基于参考点和密度的快速聚类算法,软 件学报,2003,Vol.14, No.6, 123–128.
[98] Kaufan L, Rousseeuw PJ. Finding Groups in Data: an Introduction to Cluster Analysis. New York: John Wiley & Sons, 1990.
[99] Guha S, Rastogi R, Shim K. CURE: an efficient clustering algorithm for large databases. In: Haas LM, Tiwary A, eds. Proceedings of the ACM SIGMOD International Conference on Management of Data. Seattle: ACM Press, 1998. 73– 84.
[100]Agrawal R, Gehrke J, Gunopolos D, Raghavan P. Automatic subspace clustering of high dimensional data for data mining application. In: Haas LM, Tiwary A, eds. Proceedings of the ACM SIGMOD International Conference on Management of Data. Seattle: ACM Press, 1998, 94–105.
[101]M.C.Lin. Efficient Collision Detection for Animation and Robotics. PHD.theis, Department of Electrical Engineering and Computer Science, University of North California, Berkeley, 1993.
[102]M. Lin, D. Manocha, J. Cohen and S. Gottschalk. Collision Detection: Algorithms and Applications. Algorithms for Robotics Motion and Manipulation, 1996, 129–142.
[103]M. Lin and J.F.Canny. Efficient algorithms for incremental distance computation. IEEE Conference on Robotics and Automation., 1991,1008–1014.
[104]M. Ponamgi, D. Manocha and M. Lin. Incremental algorithms for collision detection between Polygonal models. IEEE Transactions on Visualization and Computer Graphics, 1997, 51–75.
[105]M.Lin and D. Manocha. Fast interference detection between geometric models. The Visual Computer, 1995, 542–561.
[106]Kelvin Chung. An Efficient Collision Detection Algorithm for Polytopes in Virtual Environments. M.Phil Thesis, Department of Computer Science, University of Hong Kong, 1996.
[107]K.Chung and W.Wang. Quick Elimination of Non-Interference Polytopes in Virtual Environments. 3rd European Workshop on Virtual Environments. 1996, 19–20.
[108]K.Chung and W.Wang. Quick Collision Detection of Polytopes in Virtual Environments. ACM Symposium on Virtual Reality Software and Technology. 1996, 1–4.
[109] G. van den Bergen. A Fast and Robust GJK Implementation for Collision Detection for Convex Object. Journal of Graphics Tools. 1997.
[110]魏英梅, 虚拟环境中碰撞检测问题的研究,博士毕业论文,国防科技大学, 2002.
[111] Peixing Li ,Li Cai-xia,Report:Statistical Method and Statistical Software For the Teaching in Mathematics and Computation Science School, Zhongshan University, Guangzhou, P.R.C. 2002.
[112]周培德,《计算几何—算法分析与设计》,清华大学出版社,2000年第一版.
[113]B. Barber, D. Dobkin, and H. Huhdanpaa. The quickhull algorithmfor convex hull.TechnicalReport GCG53, The Geometry Center, MN, 1993.57–77.
[114] I. Jolliffe. Principal Component Analysis. Springer Verlag, 1986.
[115] S.Gottschalk.RAPID: Robust and accurate polygon interference detection system. software library. 1996.
[2] Samet H., Spatial data structures: quadtree, octrees and other hierarchical methods. Addison Wesley, 1989,23–27。
[3] Naylor BF, Amanatides JA, Thibault WC., Merging BSP trees yield polyhedral modeling results. In Proceedings of ACM SIGGRAPH, 1990, 115–124.
[4] McNeely W, Puterbaugh K, Troy J. , Six degree-of-freedom haptic rendering using voxel sampling. In Proceedings of Siggraph 1999,401–408.
[5] Hubbard, P. M., Approximating polyhedra with spheres for time critical collision detection. ACM Transactions on Graphics, 1996, 15(3).179–210.
[6] Van Den Bergen, Efficient collision detection of complex deformable models using AABB trees. Journal of Graphics Tools .1997, 2 (4) .1–13.
[7] Gottschalk S, Lin, M. C. and Manocha. D.,OBB Tree: a hierarchical structure for rapid interference detection. In SIGGRAPH 96 Conference Proceedings, Annual Conference Series, ACM SIGGRAPH, New Orleans, USA, Aug. 1996,171–180.
[8] James T. Klosowski., Efficient Collision Detection Using Bounding Volume Hierarchies of k-Dops[C], IEEE Transactions on Visualization and Computer Graphics, Vol. 4, No. 1,1998,26–27.
[9] 魏迎梅,吴泉源,石教英,碰撞检测中的固定方向凸壳包围盒的研究,软件学报12(7).2001,105–109.
[10] Ehmann S, Lin M C. , Accurate and fast proximity queries between polyhedra using convex surface decomposition. In Proceedings of the Eurographics Conference, Manchester, 2001, 500–510.
[11] Wan HG, Fan ZW, Gao SM, Peng QS, A parallel collision detection algorithm based on hybrid bounding volume hierarchy, in Proceedings of CAD&Graphics’ 2001, Kunming, China, 2001, 521–528.
[12] Larsson T., Akenine-M?LLER T., Collision detection for continuously deforming bodies. In Eurographics , 2001, 325–333.
[13] Mezger J., Kimmerle S., Etzmuss O.: Hierarchical Techniques in Collision Detection for Cloth Animation. Journal of WSCG , 2003, 322–329.
[14] F. Ganovelli, J. Dingliana, and C. O'Sullivan. Buckettree: Improving collision detection between deformable objects. SCCG2000 Spring Conf. on Comp. Graph-ics, 2000, 156–163.
[15] Bridson R., Marino S., Fedkiw R.: Simulation of clothing with folds and wrinkles. In Proc. ACM/Eurographics Symposium on Computer Animation , 2003, 28–36.
[16] Frisken S. F., Perry R. N., Rockwood P., Jones T. R., Adaptively sampled distance fields: A general representation of shape for computer graphics. SIGGRAPH 2000, Computer Graphics Proceedings (2000), 249–254.
[17] Bremer P.T., Porumbescu S., Kuester F., Hamann B., Joyk. I., MA K.-L., Virtual clay modeling using adaptive distance fields. In Proceedings of the 2002 International Conference on Imaging Science, Systems,and Technology ,2002,127.
[18] Heidelberger, B., Teschner, M., and Gross, M.. Detection of collisions and self-collisions using image-space techniques. Journal of WSCG12, 3, 2004, 145– 152.
[19] Govindaraju, N., Lin, M., and Manocha, D.. Fast and reliable collision detection using graphics hardware. Proc. of ACM VRST, 2004.
[20] Baciu, G., and Wong, S. 2002. Hardware-assisted self-collision for deformable models. ACM Symposium on VRST, 129–136.
[21] Navazo I, Ayala D, Brunet P. A geometric modeler based on the exact octree representation of polyhedra. Computer Graphics Forum,1986, 5(2): 91–104.
[22] J.L. Bentley. Multidimensional Binary Search Trees Used for Associative Searching. Communication of the ACM, 18(9), September 1975,509–517.
[23] Naylor BF, Amanatides JA, Thibault WC. Merging BSP trees yield polyhedral modeling results. In Proceedings of ACM SIGGRAPH, 1990, 115-124.
[24] W. Bouma, G. Vanecek, Jr. Collision Detection and Analysis in a Physical Based Simulation. Eurographics Workshop on Animation and Simulation,Vienna, 1991,191–203.
[25] D. Kim, L.J. Guibas, S. Shin. Fast Collision Detection Among Multiple Moving Spheres. IEEE Transactions on Visualisation and Computer Graphics, 4(3), July-September 1998, 230–242.
[26] Taosong He ,Fast Collision Detection Using QuOSPO Trees,Symposium on Interactive 3D Graphics, Proceedings of the 1999 symposium on Interactive 3D graphics.Atlanta, Georgia, United States,1999, 55–62.
[27] J H Clark. Hieraachical Geometric Models for Visible Surface Algorithms. Comm.ACM19(10), 1976 .
[28] 张茂军,虚拟现实系统,科学出版社,2001,第一版,2–8。
[29] S. Suri. Analyzing Bounding Boxes for Object Intersection ACM. Transactions on Graphics, Vol. 18, 1999, 257–277.
[30] Jiménez P, Thomas F, Torras C. Collision detection: a survey, Computers and Graphics, 2001, 25(2),269–285.
[31] Gottschalk.S, Collision Queries using Oriented Bounding Box, Doctorial Dissertation, Department of Computer Science, University of N. Carolina, Chapel Hill.. 2000. 41–47.
[32] Y. Tao, D. Papadias, and J. Sun. The tpr*-tree: An optimized spatio-temporal access method for predictive queries. In VLDB, 2003, 790-801.
[33] G. Turk. Interactive collision detection for molecular graphics. Technical Report TR90-014, University of North Carolina at Chapel Hill, 1990.
[34] B. Mirtich. Efficient algorithms for two-phase collision detection. Technical Report TR-97-23, Mitsubishi Electric Research Laboratory, 1997.
[35] M. Teschner, B. Heidelberger, M. Mueller, D. Pomeranets, and M. Gross. Optimized spatial hashing for collision detection of deformable objects. In Proceedings of Vision, Modeling, Visualization, 2003,47–54.
[36] R. G. Luque, J. L. D. Comba, and C. M. D. S. Freitas. Broad-phase collision detection using semi-adjusting bsp-trees. Proceedings of the 2005 symposium on Interactive 3D graphics and games, New York,NY, USA, ACM Press,2005 , 179–186.
[37] S. Gibson. Using distancemaps for smooth surface representation in sampled volumes . In Proceedings of IEEE Volume Visualization Symposium, 1998, 23–30.
[38] B. A. Payne and A.W. Toga. Distance field manipulation of surface models. IEEE Computer Graphics and Applications, 12(1), 1992, 65–71.
[39] R. Westermann, L. Kobbelt, and T. Ertl. ,Real-time exploration of regular volume data by adaptive reconstruction of isosurfaces. The Visual Computer, 15(2), 1999, 100–111.
[40] J. Wu and L. Kobbelt. Piecewise linear approximation of signed distance fields. In Proceedings of Vision, Modeling, Visualization, 2003, 513–520.
[41] J. A. Sethian. A fast marching level set method for monotonically advancing fronts. Proceedings of the National Academy of Science, 93(4), 1996, 1591–1595.
[42] M. W. Jones and R. Satherley. Using distance fields for object representation andrendering. In Proceedings of Eurographics, 2001, 37–44.
[43] K. E. Hoff III, J. Keyser, M. Lin, D. Manocha, and T. Culver. Fast computation of generalized Voronoi diagrams using graphics hardware. In Proceedings of ACM SIGGRAPH, 1999, 277–286.
[44] D. E. Breen, S. Mauch, R. T. Whitaker, and J. Mao. 3d metamorphosis between different types of geometric models. In Proceedings of Eurographics, 2001, 36–48.
[45] B. Eberhardt, O. Etzmuss, and M. Hauth. Implicit-explicit schemes for fast animation with particle systems. In Proceedings of Computer Animation and Simulation, 2000, 137–151.
[46] C. Sigg, R. Peikert, and M. Gross. Signed distance transform using graphics hardware. In Proceedings of IEEE Visualization. IEEE Computer Society Press, 2003, 83–90.
[47] A. Sud, M. A. Otaduy, and D. Manocha. Difi: Fast 3d distance field computation using graphics hardware. In Proceedings of Eurographics, 2004, 557–566.
[48] A. Fuhrmann, G. Sobotka, and C. Gross. Distance fields for rapid collision detection in physically based modeling. In Proceedings of GraphiCon, 2003, 58–65.
[49] S. Fisher and M. Lin. Deformed distance fields for simulation of nonpenetrating flexible bodies. In Proceedings of Computer Animation and Simulation, 2001, 99–111.
[50] T. Vassilev, B. Spanlang, and Y. Chrysanthou. Fast cloth animation on walking avatars. In Proceedings of Eurographics, 2001, 137–150.
[51] G. Baciu and W. S.K. Wong. Image-based collision detection for deformable cloth models. In IEEE Transactions on Visualization and Computer Graphics, volume M. ACM Press, 2004, 649–663.
[52] Shinya and M. Forgue. Interference detection through rasterization. The Journal of Visualization and Computer Animation, 1991, 132–134.
[53] G. Baciu, W. S.-K. Wong, and H. Sun. RECODE: an image–based collision detection algorithm. The Journal of Visualization and Computer Animation, 1999, 181–192.
[54] K. Myszkowski, O. Okunev, and T. Kunii. Fast collision detection between complex solids using rasterizing graphics hardware. The Visual Computer, 11(9), 1995, 497–512.
[55] J. C. Lombardo, M.-P. Cani, and F. Neyret. Real-time collision detection for virtual surgery. In Proceedings of Computer Animation.IEEE CS Press, 10(6), 1999,82–91.
[56] G. Baciu and W. S.-K. Wong. Image-based collision detection for deformablecloth models. In IEEE Transactions on Visualization and Computer Graphics, volume 10(6), ACM Press, 2004, 649–663.
[57] Y. Kim, M. Otaduy, M. Lin, and D. Manocha. Fast penetration depth computation for physically-based animation. In Proceedings of SIGGRAPH Symposium on Computer Animation, 2002, 23–31.
[58] B. Heidelberger, M. Teschner, and M. Gross. Real-time volumetric intersections of deforming objects. In Proceedings of Vision, Modeling, Visualization, 2003, 461–468.
[59] J. Shade, S. Gortler, L. W. He, and R. Szeliski. Layered depth images. In Proceedings of ACM SIGGRAPH, 1998, 231–242.
[60] Stefan Kimmerle,collision detection and post-processing for physical cloth simulation, Dissertation, Tübingen,2005,28–31.
[61] 彭喜元,彭宇, 戴毓丰, 群智能理论及应用,电子学报. 31(12A),2003,1982–1988.
[62] Parsopulos K. E., Vrahatis M. N.. Recent approaches to global optimization problems through particle swarm optimization. Nature Computing. Kluwer Academic Publishers. 2002, 235–306.
[63] Eberhart, R. and Kennedy, J. A new optimizer using particle swarm theory[C], Proc. 6 Int. Symposium on Micro Machine and Human Science, 1995, 39–43
[64] Kennedy, J. and Eberhart, R. Particle Swarm Optimization[C], IEEE International Conference on Neural Networks (Perth, Australia), IEEE Service Center, Piscataway, NJ, 1995, IV: 1942–1948
[65] 曹春红, 几何约束求解技术的研究, 博士论文, 吉林大学, 2005.
[66] Shi, Y. and Eberhart, R. A Modified Particle Swarm Optimizer[C], IEEE International Conference on Evolutionary Computation, Anchorage, Alaska, 1998, 63–79.
[67] Shi, Y. and Eberhart, R. C. Parameter selection in particle swarm optimization[C], Evolutionary Programming VII: Proceedings of the Seventh Annual Conference on Evolutionary Programming, New York, 1998, 591-600.
[68] Kennedy, J. The Behavior of Particles [M]. In V.W. Porto, N. Saravanan, D. Waagen, and A.E. Eiben, editors, Evolutionary Programming VII, Springer, 1998, 581–590.
[69] Carlisle, A., Dozier, G..An Off-The-Shelf PSO [C]. In Proceedings of the ParticleSwarm OptimizationWorkshop, 2001, 1–6
[70] 周 驰,高海兵,高 亮 等,粒子群优化算法,计算机应用研究,2003,21(12),5–11.
[71] V Pareto. Cours DEconomies politique, volume I and 11. Rouge, Lausanne, 1896.
[72] Carlisle A,Dozier G. Tracking Changing Extrema with Particle Swarm Optimizer[R]. Proceedings, ICAI, 2001.
[73] 汪晗,基于进化计算的多目标优化与决策方法研究, 硕士学位论文,国防科学技术大学, 2002,6–9.
[74] K. E. Parsopoulos, M. N. Vrahatis. Particle Swarm Optimization Method in Multiobjective Problems. Proceedings of the 2002 ACM symposium on Applied computing. Publisher ACM Press New York, NY, USA, 2002, 603–60.
[75] Mikkel T Jensen. Reducing the Run-Time Complexity of Multiobjective EAs: The NSGA-II and Other Algorithms, IEEE Transactions on Evolutionary Computation, Vol. 7, No. 5, October 2003, 503–515.
[76] James Kennedy,Russell C. Eberhart, Swarm intelligence. Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001.
[77] Xiaodong Li., A Non-dominated Sorting Particle Swarm Optimizer for Multiobjective Optimization. In Erick Cant et al. (editors), Genetic and Evolutionary Computation-GECCO , Springer, Lecture Notes in Computer Science Vol. 2723, July 2003, 37–41.
[78] Gregodo Toscano-Pulido and Carlos A. Coello Coello. Using Clustering Techniques to Improve the Performance of a Multi-Objective Particle Swarm Optimizer. In Proceedings of the Genetic and Evolutionary Computation Conference. Part I, Springer-Vedag, LNCS Vol. 3102, Seattle, Washington,USA, June 2004,255–237.
[79]Fieidsend, J.E., Singh, S. A Mufti-Objective.Algorithm Based upon Particle Swarm Optimization, an Efficient Data Stricture and Turbulence. In: Proceedings of the 2002U.K. Workshop on Computational Intelligence, Birmingham,UK,2002, 37–44.
[80] Thomas Bartz Beielstein, Philipp Limbourg, et al. Particle Swarm Optimizers for Pareto Opmization with Enhanced Archiving Techniques. In Proceedings of the 2003 Congress on Evolutionary Computation (CEC'2003), IEEE Press, Canberra, Australia, December 2003, 1780-1787.
[81] Mostaghim, S., Teich, J.. Strategies for Finding Good Local Guides in Multi-objective Particle Swarm Optimization (MOPSO). In:2003 IEEE Swarm Intelligence Symposium Proceedings, Indianapolis, Indiana, USA, IEEE Service Center, 2003,26–33.
[82] Carlisle A,Dozier G. ,Adapting Particle Swarm Optimization to Dynamic Environments[R].Proceedings,ICAI,2000, 429–434.
[83] Hu.X. and Eberhart,R.C. Tracking dynamic systems with PSO:where’s the cheese? Proceedings of the workshop on particle swarm opyimization. Pirdue School of Engineering and Technology,Indianapolis,IN,2001.
[84] Hu, X. and Eberhart, RC Adaptive particle swarm optimization: detection and response to dynamic systems. Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2002), Honolulu, Hawaii USA., 2002,1666–1670.
[85] Uno S., Slater M.: The sensitivity of presence to collision response. In Proc. of IEEE Virtual Reality Annual International Symposium (VRAIS) (Albuquerque, New Mexico, 1997, 95.
[86] BARZEL R., HUGHES J., WOOD D. N.: Plausible motion simulation for computer graphics animation. In Proceedings of the Eurographics Workshop Computer Animation and Simulation (1996), Boulic R., Hégron G., (Eds.),Springer, 1996,183–197.
[87] M. Teschner, S. Kimmerle, B. Heidelberger, G. Zachmann, L. Raghupathi, A. Fuhrmann, M.-P. Cani, F. Faure, N. Magnenat-Thalmann, W. Stra?er, and P. Volino , Collision Detection for Deformable Objects, Computer Graphics Forum, Volume 24, 2005,119–140.
[88] Klen J., Zachmann G.: Adb-trees: Controlling the error of time-critical collision detection. In 8th International Fall Workshop Vision, Modeling, and Visualization (VMV), Germany, 2003, 19–21.
[89] S. Guy and G. Debunne. Monte-carlo collision detection. Technical Report RR-5136, INRIA, 2004, 564–567.
[90] L. Raghupathi, L. Grisoni, F. Faure, D. Marchal, M.-P. Cani, and C. Chaillou. An intestine surgery simulator: Real-time collision processing and visualization. IEEE Transactions on Visualization and Computer Graphics, 2004, 708–718.
[91] J. D. Cohen, M. C. Lin, D. Manocha, and M. Ponamgi. I-COLLIDE: An interactive and exact collision detection system for large-scale environments.In Symposium on Interactive 3D Graphics, 1995, 189–196.
[92] L. J. Guibas, D. Hsu, and L. Zhang. H-walk: Hierarchical distance computation for moving convex bodies. In W. V. Oz and M. Yannakakis, editors, Proceedings of ACM Symposium on Computational Geometry, 1999, 265–273.
[93] S. Kimmerle, M. Nesme, and F. Faure., Hierarchy accelerated stochastic collision detection. In Proceedings of Vision, Modeling, Visualization, 2004, 307–314.
[94] Brits R , Engelbrchta P , Bergh F D. A niching particle swarm optimizer [A]. Proc Conf on Simulated Evolution and Learning[C]. Singapore : IEEE Inc , 2002.
[95] Ester M, Kriegel H P, Sander J , et al. Density based clustering in spatial databases, the algorithm gdbscan and its applications[J].Data Mining and Knowledge discovery, 1998 (2) ,169–194.
[96] 王俊年,申群太,沈洪远,周鲜成,一种改进的小生境微粒群算法,山东大学学报(工学版) 35(3),2005, 98–102.
[97]马帅,王腾蛟,唐世渭,杨冬青,高军,一种基于参考点和密度的快速聚类算法,软 件学报,2003,Vol.14, No.6, 123–128.
[98] Kaufan L, Rousseeuw PJ. Finding Groups in Data: an Introduction to Cluster Analysis. New York: John Wiley & Sons, 1990.
[99] Guha S, Rastogi R, Shim K. CURE: an efficient clustering algorithm for large databases. In: Haas LM, Tiwary A, eds. Proceedings of the ACM SIGMOD International Conference on Management of Data. Seattle: ACM Press, 1998. 73– 84.
[100]Agrawal R, Gehrke J, Gunopolos D, Raghavan P. Automatic subspace clustering of high dimensional data for data mining application. In: Haas LM, Tiwary A, eds. Proceedings of the ACM SIGMOD International Conference on Management of Data. Seattle: ACM Press, 1998, 94–105.
[101]M.C.Lin. Efficient Collision Detection for Animation and Robotics. PHD.theis, Department of Electrical Engineering and Computer Science, University of North California, Berkeley, 1993.
[102]M. Lin, D. Manocha, J. Cohen and S. Gottschalk. Collision Detection: Algorithms and Applications. Algorithms for Robotics Motion and Manipulation, 1996, 129–142.
[103]M. Lin and J.F.Canny. Efficient algorithms for incremental distance computation. IEEE Conference on Robotics and Automation., 1991,1008–1014.
[104]M. Ponamgi, D. Manocha and M. Lin. Incremental algorithms for collision detection between Polygonal models. IEEE Transactions on Visualization and Computer Graphics, 1997, 51–75.
[105]M.Lin and D. Manocha. Fast interference detection between geometric models. The Visual Computer, 1995, 542–561.
[106]Kelvin Chung. An Efficient Collision Detection Algorithm for Polytopes in Virtual Environments. M.Phil Thesis, Department of Computer Science, University of Hong Kong, 1996.
[107]K.Chung and W.Wang. Quick Elimination of Non-Interference Polytopes in Virtual Environments. 3rd European Workshop on Virtual Environments. 1996, 19–20.
[108]K.Chung and W.Wang. Quick Collision Detection of Polytopes in Virtual Environments. ACM Symposium on Virtual Reality Software and Technology. 1996, 1–4.
[109] G. van den Bergen. A Fast and Robust GJK Implementation for Collision Detection for Convex Object. Journal of Graphics Tools. 1997.
[110]魏英梅, 虚拟环境中碰撞检测问题的研究,博士毕业论文,国防科技大学, 2002.
[111] Peixing Li ,Li Cai-xia,Report:Statistical Method and Statistical Software For the Teaching in Mathematics and Computation Science School, Zhongshan University, Guangzhou, P.R.C. 2002.
[112]周培德,《计算几何—算法分析与设计》,清华大学出版社,2000年第一版.
[113]B. Barber, D. Dobkin, and H. Huhdanpaa. The quickhull algorithmfor convex hull.TechnicalReport GCG53, The Geometry Center, MN, 1993.57–77.
[114] I. Jolliffe. Principal Component Analysis. Springer Verlag, 1986.
[115] S.Gottschalk.RAPID: Robust and accurate polygon interference detection system. software library. 1996.