基于并行的快速碰撞检测算法研究
|
摘要
为了解决虚拟环境的真实感问题,必须对虚拟环境进行实时的碰撞检测。本文围绕实时碰撞检测问题,就如何提高复杂场景下碰撞检测的效率进行了深入研究。着重探讨了如何利用并行技术来有效提高碰撞检测算法的效率。主要研究成果包括以下八个方面:
1.提出了一种基于分治和流水线技术的并行碰撞检测算法。采用并行算法中的流水线技术,通过划分进程来遍历任务树从而加速碰撞检测过程。同时在进程中也应用了多线程技术,因而能快速的检测到碰撞。
2.提出了一种基于混合包围体的OpenMP并行化碰撞检测算法。利用OpenMP并行模型来并行遍历混合包围体层次,进一步加速碰撞检测过程。提出了一种基于着色算法的并行碰撞检测算法,在并行机上采用多线程技术执行相同类别的任务树的遍历过程,在遍历过程中检测是否有碰撞发生。
3.提出了一种基于时空相关性的MPI并行碰撞检测算法。在空间分割和时空相关性基础上采用基于MPI的并行处理技术。并通过MPI并行处理方式将各子任务分配到各子进程执行。
4.提出了一种基于粒子群算法的并行碰撞检测算法。将OpenMP、MPI并行模型来并行化基于粒子群面向可变形物体的随机碰撞检测算法,提出了一种基于遗传算法的并行碰撞检测算法。采用一种快速的基于模拟退火遗传算法的碰撞检测技术,完成整个检测过程,然后将并行技术用于遗产算法,进一步加速碰撞检测的速度。
5.提出了一种改进的基于球体混合重建的并行碰撞检测算法。对球体混合表面提出一个子线性时间复杂性的重建过程,利用四元组构造变换范围,扩展了从线性到球形混合的构造变换方法,采用循环划分的方法完成由球体混合到线性混合的分解过程。然后采用OpenMP技术并行化上述算法,可以快速完成虚拟环境下复杂的碰撞检测问题。
As a classic and critical problem in the areas of computer graphics, virtual reality, computer games, animation, computer-aided design, robotics and virtual manufacturing and other fields, collision detection has been more concerned about over the years. At present, most of the geometric models in virtual reality are composed of thousands of basic geometric elements. With the increase of the geometric complexity of virtual environment, the calculating complexity of collision detection greatly increased, and the interaction of complex scenes consumes a large amount of computer resources, so collision detection often becomes a bottleneck in virtual environment. So how to design an efficient collision detection algorithm to meet the real-time accuracy and universality has become a serious problem currently.
With the rapid development of parallel computer, parallel technology has brought unprecedented opportunities and challenges for the researchers. There are so many parallel technologies have been used in collision detection algorithm, such as partition, pipelining, divide and conquer, symmetry breaking, MPI, OpenMP. But those technologies applied in collision detection are at the beginning.
Concerning the requirements of real-time and accurate collision detection in interactive system, we had an in-depth study of parallel technology and proposed several parallel collision detection algorithms. Then we use two parallel technologies MPI and OpenMP to parallel the collision detection algorithm based on particle swarm and the collision detection algorithm based on spherical blend reconstruction, at the same time, we compare several existed parallel algorithms from two aspects of the time efficiency and resource consumption. Our paper includes the following contents:
1) Parallel collision detection algorithm based on pipelining and divide-and-conquer: A parallel collision detection algorithm based on pipelining and divide-and-conquer is presented. The characteristic in this algorithm is as follows: at first, it builds Balance-BoxTrees for every objects in environment using divide-and-conquer technologies which are mostly primary technologies in parallel algorithm, then form traversing of a WorkTrees by traversing two BoxTrees and in this process it shares alike this task by each computer, also applies pipelining technologies which is also important in parallel algorithm and traversing the WorkTrees by dividing tenors. Because of the application of dividing tenors, our algorithm can apply multi-threads in tenors so that it can run on both single processor computer and multi-processor computer. So we can see the result about experiment data from Table 1 and Table 2 which can indicate the meaning about our research. As we use so many parallel technologies, this algorithm speeds up collision detection by a long way.
2) Parallel collision detection algorithm based on mixed BVH and OpenMP: First we incorporate the merits of both AABB bounding box and bounding spheres to construct a hybrid bounding representation of arbitrary non-convex polyhedra (S-AABB) for attaining speed, and then use OpenMP parallel programming model to traversal the built hybrid bounding volume hierarchy, so further accelerate the collision detection algorithm. At the same time, our algorithm can run on both single processor computer and multi-processor computer.
3) The comparison of the multiple parallel collision detection: We have shown that our two parallel algorithms are superior by comparing the four parallel collision detection algorithms such as MPI,Pipelining,OpenMP,SymmetryBreaking in terms of time efficiency, resource consumption and stability. Here MPI is the parallel collision detection algorithm based on MPI, Pipelining is the parallel collision detection algorithm based on pipelining, OpenMP is our first parallel collision detection algorithm based on OpenMP, SymmetryBreaking is our second parallel collision detection algorithm based on symmetry breaking.
4) A new parallel collision detection algorithm based on mixed BVH and symmetry breaking: At first, we incorporate the merits of both AABB bounding box and bounding spheres to construct a hybrid bounding representation of arbitrary non-convex polyhedra (S-AABB) for attaining speed, especially the S-AABB is balanced using divide-and-conquer technologies which are mostly primary technologies in parallel algorithm. Then we apply Symmetry Breaking—k-Colouring technology which is also important in parallel algorithm in order to reduce diffrernt categories, and assign them to different processors; Also multi-thread is used in multi-processor computer. At last, experiments results have shown that our algorithm is advantageous over other current typical collision detection such as I-COLLIDE regarding efficiency and accuracy, so can meets the real-time and accurate requirements in complex interactive virtual environment.
5) Parallel Collision Detection Algorithm Based on Temporal-spatial Coherence and MPI: We present an advanced algorithm which based on temporal-spatial coherence and spatial subdivision algorithm and adapt a parallel method based on MPI. At first, it subdivides the space into a series of voxels, compute the size and build the list of objects in the voxels by the state of the objects. It confirms the traversing orders of tree by using temporal-spatial coherence and dispatches every sub-task into sub-tenor by the parallel method based on MPI.This algorithm reduces the times of collision detection and the traversing depth of the bounding box’tree. The results of experiment prove that this method speeds up collision detection and guarantees its real-time performance.
6) Parallel collision detection based on particle swarm optimization algorithm: It combines stochastic collision detection and particle swarm optimization (PSO) Algorithm. Firstly, the algorithmsamples primitive pairs within the models to construct a discrete binary search space for PSO, by which user can balance performance and detection quality. In order to handle the deformation of models in the object space, a particle update process was added in the beginning of every time step, which handles the dynamic environments problem in search space caused by deformation. The algorithm is also very general that makes no assumption about the input model, which can be without topology information or even be“polygon soups”. It doesn’t need to store additional data structures either, so the memory cost is relative low. At last, we use two techniques MPI and OpenMP to parallel the above algorithm, so further improve the efficiency of the collision detection.
7) Parallel collision detection based on spherical blend reconstruction: We present a novel collision detection algorithm based on spherical blend skinning. A procedure is presented for refitting of bounding spheres for spherical blend skinning with sublinear time complexity, to construct rotation bound by a quaternion. This refitting operation is an extension of the refitting for linear blending. To complete decomposes from spherical blending to linear by rotational component. Although it is of course a little more difficult than in the linear case, the resulting algorithm is almost as easy to implement and the computation complexity of the presented algorithm is almost the same as that of the linear version.
8) Computing distance of two objects in space is a important aspect. Improving computing speed of distance of two convex polyhedrons can speed up collision detection. With convex Bounding volume hierarchies (BVHs) express convex polyhedron, conversing distance problem of two convex polyhedrons to non-linear programming problem. Using simulation anneal genetic algorithms solve it. Using receive criterion of simulation anneal intersect and vary. Algorithms Optimize time complexity. Finally in order to speed up the collision detection, we use parallel parallel to parallelize genetic algorithm.Result show that simulation anneal genetic algorithms especially the genetic algorithms parallel have better efficiency and more faster computing speed.
1.提出了一种基于分治和流水线技术的并行碰撞检测算法。采用并行算法中的流水线技术,通过划分进程来遍历任务树从而加速碰撞检测过程。同时在进程中也应用了多线程技术,因而能快速的检测到碰撞。
2.提出了一种基于混合包围体的OpenMP并行化碰撞检测算法。利用OpenMP并行模型来并行遍历混合包围体层次,进一步加速碰撞检测过程。提出了一种基于着色算法的并行碰撞检测算法,在并行机上采用多线程技术执行相同类别的任务树的遍历过程,在遍历过程中检测是否有碰撞发生。
3.提出了一种基于时空相关性的MPI并行碰撞检测算法。在空间分割和时空相关性基础上采用基于MPI的并行处理技术。并通过MPI并行处理方式将各子任务分配到各子进程执行。
4.提出了一种基于粒子群算法的并行碰撞检测算法。将OpenMP、MPI并行模型来并行化基于粒子群面向可变形物体的随机碰撞检测算法,提出了一种基于遗传算法的并行碰撞检测算法。采用一种快速的基于模拟退火遗传算法的碰撞检测技术,完成整个检测过程,然后将并行技术用于遗产算法,进一步加速碰撞检测的速度。
5.提出了一种改进的基于球体混合重建的并行碰撞检测算法。对球体混合表面提出一个子线性时间复杂性的重建过程,利用四元组构造变换范围,扩展了从线性到球形混合的构造变换方法,采用循环划分的方法完成由球体混合到线性混合的分解过程。然后采用OpenMP技术并行化上述算法,可以快速完成虚拟环境下复杂的碰撞检测问题。
As a classic and critical problem in the areas of computer graphics, virtual reality, computer games, animation, computer-aided design, robotics and virtual manufacturing and other fields, collision detection has been more concerned about over the years. At present, most of the geometric models in virtual reality are composed of thousands of basic geometric elements. With the increase of the geometric complexity of virtual environment, the calculating complexity of collision detection greatly increased, and the interaction of complex scenes consumes a large amount of computer resources, so collision detection often becomes a bottleneck in virtual environment. So how to design an efficient collision detection algorithm to meet the real-time accuracy and universality has become a serious problem currently.
With the rapid development of parallel computer, parallel technology has brought unprecedented opportunities and challenges for the researchers. There are so many parallel technologies have been used in collision detection algorithm, such as partition, pipelining, divide and conquer, symmetry breaking, MPI, OpenMP. But those technologies applied in collision detection are at the beginning.
Concerning the requirements of real-time and accurate collision detection in interactive system, we had an in-depth study of parallel technology and proposed several parallel collision detection algorithms. Then we use two parallel technologies MPI and OpenMP to parallel the collision detection algorithm based on particle swarm and the collision detection algorithm based on spherical blend reconstruction, at the same time, we compare several existed parallel algorithms from two aspects of the time efficiency and resource consumption. Our paper includes the following contents:
1) Parallel collision detection algorithm based on pipelining and divide-and-conquer: A parallel collision detection algorithm based on pipelining and divide-and-conquer is presented. The characteristic in this algorithm is as follows: at first, it builds Balance-BoxTrees for every objects in environment using divide-and-conquer technologies which are mostly primary technologies in parallel algorithm, then form traversing of a WorkTrees by traversing two BoxTrees and in this process it shares alike this task by each computer, also applies pipelining technologies which is also important in parallel algorithm and traversing the WorkTrees by dividing tenors. Because of the application of dividing tenors, our algorithm can apply multi-threads in tenors so that it can run on both single processor computer and multi-processor computer. So we can see the result about experiment data from Table 1 and Table 2 which can indicate the meaning about our research. As we use so many parallel technologies, this algorithm speeds up collision detection by a long way.
2) Parallel collision detection algorithm based on mixed BVH and OpenMP: First we incorporate the merits of both AABB bounding box and bounding spheres to construct a hybrid bounding representation of arbitrary non-convex polyhedra (S-AABB) for attaining speed, and then use OpenMP parallel programming model to traversal the built hybrid bounding volume hierarchy, so further accelerate the collision detection algorithm. At the same time, our algorithm can run on both single processor computer and multi-processor computer.
3) The comparison of the multiple parallel collision detection: We have shown that our two parallel algorithms are superior by comparing the four parallel collision detection algorithms such as MPI,Pipelining,OpenMP,SymmetryBreaking in terms of time efficiency, resource consumption and stability. Here MPI is the parallel collision detection algorithm based on MPI, Pipelining is the parallel collision detection algorithm based on pipelining, OpenMP is our first parallel collision detection algorithm based on OpenMP, SymmetryBreaking is our second parallel collision detection algorithm based on symmetry breaking.
4) A new parallel collision detection algorithm based on mixed BVH and symmetry breaking: At first, we incorporate the merits of both AABB bounding box and bounding spheres to construct a hybrid bounding representation of arbitrary non-convex polyhedra (S-AABB) for attaining speed, especially the S-AABB is balanced using divide-and-conquer technologies which are mostly primary technologies in parallel algorithm. Then we apply Symmetry Breaking—k-Colouring technology which is also important in parallel algorithm in order to reduce diffrernt categories, and assign them to different processors; Also multi-thread is used in multi-processor computer. At last, experiments results have shown that our algorithm is advantageous over other current typical collision detection such as I-COLLIDE regarding efficiency and accuracy, so can meets the real-time and accurate requirements in complex interactive virtual environment.
5) Parallel Collision Detection Algorithm Based on Temporal-spatial Coherence and MPI: We present an advanced algorithm which based on temporal-spatial coherence and spatial subdivision algorithm and adapt a parallel method based on MPI. At first, it subdivides the space into a series of voxels, compute the size and build the list of objects in the voxels by the state of the objects. It confirms the traversing orders of tree by using temporal-spatial coherence and dispatches every sub-task into sub-tenor by the parallel method based on MPI.This algorithm reduces the times of collision detection and the traversing depth of the bounding box’tree. The results of experiment prove that this method speeds up collision detection and guarantees its real-time performance.
6) Parallel collision detection based on particle swarm optimization algorithm: It combines stochastic collision detection and particle swarm optimization (PSO) Algorithm. Firstly, the algorithmsamples primitive pairs within the models to construct a discrete binary search space for PSO, by which user can balance performance and detection quality. In order to handle the deformation of models in the object space, a particle update process was added in the beginning of every time step, which handles the dynamic environments problem in search space caused by deformation. The algorithm is also very general that makes no assumption about the input model, which can be without topology information or even be“polygon soups”. It doesn’t need to store additional data structures either, so the memory cost is relative low. At last, we use two techniques MPI and OpenMP to parallel the above algorithm, so further improve the efficiency of the collision detection.
7) Parallel collision detection based on spherical blend reconstruction: We present a novel collision detection algorithm based on spherical blend skinning. A procedure is presented for refitting of bounding spheres for spherical blend skinning with sublinear time complexity, to construct rotation bound by a quaternion. This refitting operation is an extension of the refitting for linear blending. To complete decomposes from spherical blending to linear by rotational component. Although it is of course a little more difficult than in the linear case, the resulting algorithm is almost as easy to implement and the computation complexity of the presented algorithm is almost the same as that of the linear version.
8) Computing distance of two objects in space is a important aspect. Improving computing speed of distance of two convex polyhedrons can speed up collision detection. With convex Bounding volume hierarchies (BVHs) express convex polyhedron, conversing distance problem of two convex polyhedrons to non-linear programming problem. Using simulation anneal genetic algorithms solve it. Using receive criterion of simulation anneal intersect and vary. Algorithms Optimize time complexity. Finally in order to speed up the collision detection, we use parallel parallel to parallelize genetic algorithm.Result show that simulation anneal genetic algorithms especially the genetic algorithms parallel have better efficiency and more faster computing speed.
引文
[1] M.Moore and J.Wilhelms.Collision detection and response for computer animation[J]. ACM Computer Graphics,22 (4): 289~298, 1988.
[2] D.Baraff. Interactive simulation of solid rigid bodies[J]. IEEE Computer Graphics and Applications,15(3): 63~75, 1995.
[3] D.Baraff.Faxt contact force computation for nonpenetrating rigid bodies[J]. ACM Computer Graphics, 28(1): 23~34, 1994.
[4] V.V.Kamat.A survey of techniques for simulation of dynamic collision detection and response[J].Computer & Graphics, 17(4): 379~385,1993.
[5] J.M.Snyder. An interactive tool for placing curved surfaces without interpenetration[J]. ACM Computer Graphics, 29(4): 209~218, 1995.
[6] D.P. Dobkin and D.G.Kirkpatrick. A linear algorithm for determining the separation of convex polyhedra[J]. Journal of Algorithms, 12(6): 381~392, 1985.
[7] P.K.Agarwal, M.van Kreveld. Intersection queies for curved objects[C]. Proc. 7th Annual ACM Symposium on Computational Geometry, 41~50, 1991.
[8] B.Chazelle. An Optimal algorithm for intersection three-dimensional convex polyhedra[C]. Proc. 30th annual IEEE Symposium on Foundation Computer Science, 586~591, 1989.
[9] Stephen Cameron. Collision detection by four-dimensional intersection testing[J]. IEEE Transactions on Robotics and Automation, 6(3), 381~392,1990.
[10] J.Canny. Collision Detection for Moving Polyhedra[J]. IEEE Trans. Pattern Anal. Mach. Intell, 8(2): 200~209, 1986.
[11] Martim Courchesne and Nadia Magnenat.Versatile and Efficient Techniques for Simulating Cloth and Other Deformable Objects[J].ACM SIGGRPH,9(3):281~289,1990.
[12] J.L.Bentley. Multidimensional Binary Search Trees Used for Associative Searching[J].ACM Communications, 18(9): P509~517, 1975.
[13] M.Moore and J.Wilhelms. Collision detection and response for computer animation[J]. ACM Computer Graphics, 22 (4): P289~298, 1988.
[14] Gino Van Den Ber Gen. Efficient Collision Detection of Complex Deformable Models using AABB Trees[J]. Journal of Graphics Tools, 4(2): P1~13, 1999.
[15] Gottschalk S, L in M C, Manocha D. OBB Tree: A Hierarchical Structure for Rapid Interference Detection[C]. Computer Graphics, New Orleans, LA, USA, 1996, 182-189.
[16] H.Noborio, S.Fukuda and S.Arimoto. Fast Interference Check Method Using Octree Representation[J]. Advanced Robotics. 3(3): P193~212, 1989.
[17] B.Naylor, J.Amanatides, W.Thibault. Merging BSP Trees Yields Polyhedral Set Operations[J], ACM Computer Graphics (SIGGRAPH' 90 Proceedings), 24(2): P115~124, 1990.
[18] W.Thibault and B.Naylor. Set operations on Polyhedra Using Binary Space PartitioningTrees[J].ACM Computer Graphics, 21(4): P153~162, 1987.
[19] Stephen J.Adelson and Larry F.Hodges. Generating exact ray-traced animation frames by reprojection[J]. IEEE Computer Graphics and Applications, 15(3): P43~52, 1995.
[20] T.L.Kay and J.T.Kajiya. Ray tracing complex scenes[J]. ACM Computer Graphics, 20(4): P269~278, 1986.
[21] J.Goldsmith and J.Salmon. Automatic creation of object hierarchies for ray tracing[J]. IEEE Computer Graphics and Application, 7(1): P14~20, 1987.
[22] H.Weghorst, G.Hooper and D.P.Greenberg. Improved computational methods for ray tracing[J]. ACM Transaction on Computer Graphics, 3(1): P52~69, 1984.
[23] I.J.Palmer and R.L.Grimsdale. Collision detection for animation using sphere-trees[J]. Computer Graphics Forum, 14(2): P105~116, 1995.
[24] I.J.Palmer. Collision detection for animation: the use of the sphere-tree data structure[C].The Second Departmental Workshop on Computing Research, University of Bradford, 201-209,June 1995.
[25]魏迎梅.虚拟环境中碰撞检测问题的研究[D],长沙:国防科技大学,2000.
[26]范昭炜,万华根,高曙明.基于流的实时碰撞检测算法[J].软件学报, 15(10): 1505~1514,2004.
[27] Xinyu Zhang and Young J. Kim. Interactive Collision Detection for Deformable Models using Streaming AABBs[C]. In: Proc. of the ACM IEEE Transactions on Visualization and Computer Graphics. 3:318~329, 2007.
[28] Naga K. Govindaraju, Ming C. Lin, Dinesh Manocha, Quick-ULLIDE: Fast Inter- and Intra-Object Collision Detection using Graphica Processors[C]. Proceedings of the 2005 IEEE Conference on Virtual Reality, 59~66, 2005.
[29]王季,翟正军,蔡小斌.基于球深度纹理的实时碰撞检测算法[J],系统仿真学报, 19(11):P59~63, 2007.
[30] Dae-Hyun Kima, Han-Soo Choi. Hybrid bounding volume hierarchies for fast proximity queries[C]. ICMIT 2005: Information Systems and Signal Processing, 304-306, 2005.
[31]刘晓东,姚兰,邵付东,王颖.一种基于混合层次包围盒的快速碰撞检测算法[J].西安交通大学学报, 41(2):P141～144+157, 2007.
[32]朱元峰,孟军,谢光华,马文娟.基于复合层次包围盒的实时碰撞检测研究[J].系统仿真学报, 20(2):P372～377, 2008.
[33]李文辉,王天柱,王祎,秦忠,基于粒子群面向可变形物体的随机碰撞检测算法[J],系统仿真学报, 18(8):2206～2209, 2006.
[34]赵伟,李文辉,夏云飞.基于模拟退火遗传算法的凸多面体间碰撞检测算法研究[J]吉林大学学报(工学版), 38(3):P676~679, 2008.
[35]刘晓平,曹力.基于MPI的并行八叉树碰撞检测[J]计算机辅助设计与图形学学报, 19(2):P184~187+192, 2007.
[36]赵伟,何艳爽.一种快速的基于并行的碰撞检测算法[J],吉林大学学报(工学版),38(1):P152~157, 2008.
[37] Tomas Akenine-Moller, Eric Haines, Real-Time Rendering[M/OL]. A K Peters, Ltd. 2002. [2002-9-18]. http://www.realtimerendering.com/ http://users.volia.net/fajrvehr/
[38]范昭炜,实时碰撞检测技术研究[D],浙江:浙江大学,2003.
[39] Lin MC, Manocha D. Interactive geometric computations using graphics hardware[C]. International Conference on Robotics and Automation,201-205, 2002.
[40] Lin MC,Canny J. Efficient algorithms for incremental distance computation[C]. In Proceedings of the IEEE International Conference on Robotics and Automation, 1008~1014, 1991.
[41] Lin MC. Efficient Collision detection for animation and robotics[D].Ph.D. Thesis, Department of Electrical Engineering and Computer Science, University of California, Berkeley, 1993.
[42] Ponamgi MK, Cohen JD, Lin MC, Manocha D. Incremental algorithms for collision detection between polyhedral models[C]. In SIVE 95,The First Workshop on Simulation and Interaction in Virtual Environments, 1: 84~91, 1995.
[43] Gilbert EG, Johnson DW, Keerthi SS. A fast procedure for computing the distance between objects in three-dimensional space[C]. IEEE Journal on Robotics and Automation, 4: 193~203, 1988.
[44] A.Geria-Alonso, N.Serrano, J.Flaquer. Solving the collision detection problem[C], IEEE Computer, Graph, Appl, 205-207,May, 1994.
[45] M.Held, J.T.Klosowski, J.S.B.Mitchell. Evaluation of collision detection methods for virtual reality fly-throughs[C], In Pros.7th Canad, Conf.Comput.Geom, 151-159,1995.
[46] Shinya M, Forgue M. Interference detection through rasterization[J], Journal of Visualization and Computer Animation, 2: 131~134, 1991.
[47] Rossignac J, Megahed A, Schneider BO. Interactive inspection of solids: cross-section and interferences[J], Computer Graphics, 26(2): 353~360, 1992.
[48] Myszkowski K, Okunev OG, Kunii TL. Fast collision detection between computer solids using rasterizing graphics hardware[J]. The Visual Computer,11: P497~511, 1995.
[49] Baciu G, Wong WSK. Rendering in object interference detection on conventional graphics workstations[C]. In Proceedings of the Pacific Graphics, Seoul National University, Korea, October, P51~58,1995.
[50] Baciu G, Wong SKW, Sun H. RECODE: An image-based collision detection algorithm[J], Journal of Visualization and Computer Animation, 10(4): P181~192, 1999.
[51] Hoff III KE, Zaferakis A, Lin M, Manocha D. Fast and simple 2D geometric proximity queries using graphics hardware [J]. Proceedings of ACM Symposium on Interactive 3D Graphics,145-148, 2001.
[52] Kim YJ, Lin M, Manocha D. Fast penetration depth estimation using rasterization hardware and hierarchical refinement[C].In Symposium on Computational Geometry’2003,386-387, 2003.
[53] P.M Hubbud. Approximation polyhedra with spheres for time-critical collision detection[C]. ACM Trans.Graph, 15(3):179-210, July, 1996.
[54] N.Beckmann, H.-P.Kriegel, R.Schneider, B.seeger. The R-tree: An effient and robust access method for points and rectangles[C]. In Proc. ACM SIGMOD International Conference on Management of Data, 322-331,1990.
[55]魏迎梅,王涌,吴泉源,石教英.碰撞检测中的层次包围盒方法[J].计算机应用, 20(8):241-244, 2000.
[56] J.D.Cohen, M.C.Iin, D.Manochal. I-COLLIDE:Aninteractive and Exact Collision Detection System for Large-Scale Environments[C]. Proceedings of ACM Interactive 3D Graphics Conference, 189-196, 1995.
[57] Gvan den Bergen, Efficient Collision Detection of complex Deformable Model using AABB Trees[J], Journal of Graphics Tools, 2(4):l-13, 1997.
[58] http://www.cs.unc.edu/-geom/OBB/0BBT.html.
[59] Brian miritich, V-Clip: fast and robust polyhedral collision detection [J]. (MERL Technical Report 97-05), ACM Trans. On Graphies, July, 17(3):177-208, 1998.
[60] Hudson T, Lin M, Choen J, etal. V-collide: accelerated collision detection for VRML[C]. In: Proc. Of VRML Coference,1997.
[61] J. T. Kloswoski, M. Held, J. S. BMitchell, H. Sowiaral and K. Zikna. Efficient Collision Detection Using Bounding Volume Hirerachies of k-DOPs[J]. IEEE Transactions on Visualization and Computer Graphies, 4(1): 21-36,1998.
[62]高春晓,刘玉树.碰撞检测技术综述[J].计算机工程与应用, 38(5):9-11+40, 2002.
[63] Barry Wilkinson,Michael Allen.并行程序设计[M].陆鑫达等译,第2版,北京:机械工业出版社, 2005.
[64]陈国良.并行算法的设计与分析(修订版) [M].北京:高等教育出版社,2002.
[65]陈国良.并行计算—结构.算法.编程(修订版) [M].北京:高等教育出版社,2003.
[66]泥宗涛,余英林.基于分层包围盒的连续碰撞检测加速算法.计算机工程与应用[J], 36(10):4-26, 2000.
[67]范昭炜,万根华,高曙明.基于并行的快速碰撞检测算法[J].系统仿真学报,9(12): 548-552, 2000.
[68]刘晓东,姚兰,邵付东,王颖.一种基于混合层次包围盒的快速碰撞检测算法[J].交通大学学报, 41(2):141-144+157, 2007.
[69]范晓磊,谭桂臻.混合包围盒碰撞检测算法的研究[J].科技信息,10,12-13, 2007.
[70]蔡文军,陈虎.基于混合模型的碰撞检测优化算法研究[J].计算机与现代化,7,49-52, 2006.
[71]朱元峰,孟军,谢光华,马文娟.基于混合层次包围盒的实时碰撞检测研究[J].系统仿真学报, 20(2): 372-377, 2008.
[72] Ritter J. An efficient bounding sphere [C]. In Graphics Gems (edited by Andrew Glassner),Academic Press Professional, Inc. San Diego, CA, USA,301-303, 1990.
[73] Kin DJ, Guibas L J, Shin S J. Fast collision detection among multiple moving spheres[C]. IEEE Transactions on Visualization and Computer Graphics,4(3): 230-242,1998.
[74] Turk G. Interactive collision detection for molecular graphics[D].Computer Science Department, University of North Carolina at Chapel Hill,1989.
[75]徐鸣凯,丁友东,王肃.时空相关性在多物体碰撞检测中的应用[J].中国图象图形学报, 11(11):1704-1707, 2006.
[76]张蕾,杨波.并行粒子群优化算法的设计与实现[J].通信学报, 26(1):289-292, 2005.
[77] Kennedy J, Eberhart R. Particle Swarm Optimization[C], Proceeding of IEEE International Conference on Neural Networks, Perth, Australia, 223-226, 1995.
[78] K. Hoff, A.Zaferakis, D.Manocha. Fast and simple 2D geometric proximity queries using graphicsn hardware[C]. In: Int’l Conf. Interactive 3D Graphics, Berlin ACM Press, 145-1482001.
[79] T.Larrsson, T.Akenine. Efficient collision detection for models deformed by morphing [J]. The Visual Computer,19(2):164-174,2003.
[80] T Klugt, M Alexa. Bounding volumes for linearly interpolated shapes[C]. In: Proc of the 22nd Int’l conf on Computer Graphics. Crete, Greece: IEEE Computer Society Press, 134-139,2004.
[81] A Mohr, M Gleicher. Building efficient, accurate character skins from examples [J]. ACM Transaction on Graph(SIGGRAPH2003), 22(3):562-568, 2003,
[82] O Heim, C.S.Marshall, A.Lake. Fast collision detection for 3D bones-based articulated characters [J]. Game Programming Gems 4, (4):503-514,2004.
[83] J Hejl. Hardware skinning with quaternions [J]. Game Programming Gems 4, (4):487-495, 2004.
[84] L Kavan, J Zara. Fast collision detection for skeletally deformable models [J]. Computer Graphics Forum, 24(3):363-372,2005.
[85] D Eberly. a practical approach to real-time computer graphics[J]. 3D game engine design, (9): 25-29,2001.
[86] L Kavan, J Zara. Spherical blend skinning: A real-time deformation of articulated models[J]. ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, ACM Press, 9-16, 2005.
[87] B Gaertner. Fast and robust smallest enclosing balls[C]. In: Proc of the 7th Annual European Symposium on Algorithms. Prague: Springer Verlag press, 325-338,1999.
[88] J Brown, S Sorkin, C Bruyns, Latombe, et al. Real-time simulation of deformable objects: tools and application [C]. In: Proc of the 14th Int’l conf on Computer Animation. Seoul, South Korea: IEEE Computer Society Press, 228-258, 2001.
[89] Cameron S. A Comparison of two fast algorithms for computing the distance between convex polyhedron [J].IEEE transactions on Robotics and Automation, 13(6):915-920,1997.
[90] Bobrow J E. A direct minimization approach for obtaining the distance between convex polyhedron [J]. International Journal of Robo tics Research, 8(3):65-76, 1989.
[91] SelimSZ, Almohamad H A. Collision computation of moving bodies [J]. European Journal of Operational Research, 19(1):121-129,1999.
[92] L in M C, Manocha D. Fast interference detection between geometric models [J] The Visual Computer, 11(10):542-561, 1995.
[93] Gilbert E G, Johnson D W, Keerth i S S. A fast procedure for computing the distance between complex objects in three dimensional space [J]. IEEE Trans on Robotics and Automation, 4(2):193-203, 1988.
[94]谢政.非线性最优化[M].国防科技大学出版社,2003.9.
[95]李学庆.凸体间的碰撞检测研究[D].山东大学博士论文, 2002.
[96]谢政.非线性最优化[M].国防科技大学出版社, 2003.09.
[97]王小平,曹立明.遗传算法-理论、应用与软件实现[M].西安交通大学出版社, 2002.
[98]彭卓华.利用遗传算法求解一类非线性规划问题的最优解[M].数学理论与应用, 2002.09.
[99] [美]Zbigniew Michalewicz.周家驹,何险峰译.演化程序遗传算法和数据编码的结合[M].北京科技出版社,2000.
[100] James T.Klosowski, Martin Held. Efficient Collision Detection Using Bounding Volume Hierarchies of k-Dops[J].1996.
[101] GINO VAN DEN BER GEN. Efficient Collision Detection of Complex Deformable Models using AABB Trees [J]. Journal of Graphics Tools, 4(2):1-13, 1999.
[102] S. Gottschalk, M.C. Lin, D. Manocha. OBB tree: a hierarchical structure for rapid interference detection[C]. Proceedings of the ACM SIGGRAPH Conference on Computer Graphics, August 1996, New Orleans: ACM Press,171-180,1996.
[103] van den Bergen, G. Efficient collision detection of complex deformable models using AABB trees [J]. Journal of Graphics Tools, 2(4):1-13, 1997.
[104]王鹏,吕爽,聂治,谢千河等.并行计算应用及实战[M].机械工业出版社,2008.
[2] D.Baraff. Interactive simulation of solid rigid bodies[J]. IEEE Computer Graphics and Applications,15(3): 63~75, 1995.
[3] D.Baraff.Faxt contact force computation for nonpenetrating rigid bodies[J]. ACM Computer Graphics, 28(1): 23~34, 1994.
[4] V.V.Kamat.A survey of techniques for simulation of dynamic collision detection and response[J].Computer & Graphics, 17(4): 379~385,1993.
[5] J.M.Snyder. An interactive tool for placing curved surfaces without interpenetration[J]. ACM Computer Graphics, 29(4): 209~218, 1995.
[6] D.P. Dobkin and D.G.Kirkpatrick. A linear algorithm for determining the separation of convex polyhedra[J]. Journal of Algorithms, 12(6): 381~392, 1985.
[7] P.K.Agarwal, M.van Kreveld. Intersection queies for curved objects[C]. Proc. 7th Annual ACM Symposium on Computational Geometry, 41~50, 1991.
[8] B.Chazelle. An Optimal algorithm for intersection three-dimensional convex polyhedra[C]. Proc. 30th annual IEEE Symposium on Foundation Computer Science, 586~591, 1989.
[9] Stephen Cameron. Collision detection by four-dimensional intersection testing[J]. IEEE Transactions on Robotics and Automation, 6(3), 381~392,1990.
[10] J.Canny. Collision Detection for Moving Polyhedra[J]. IEEE Trans. Pattern Anal. Mach. Intell, 8(2): 200~209, 1986.
[11] Martim Courchesne and Nadia Magnenat.Versatile and Efficient Techniques for Simulating Cloth and Other Deformable Objects[J].ACM SIGGRPH,9(3):281~289,1990.
[12] J.L.Bentley. Multidimensional Binary Search Trees Used for Associative Searching[J].ACM Communications, 18(9): P509~517, 1975.
[13] M.Moore and J.Wilhelms. Collision detection and response for computer animation[J]. ACM Computer Graphics, 22 (4): P289~298, 1988.
[14] Gino Van Den Ber Gen. Efficient Collision Detection of Complex Deformable Models using AABB Trees[J]. Journal of Graphics Tools, 4(2): P1~13, 1999.
[15] Gottschalk S, L in M C, Manocha D. OBB Tree: A Hierarchical Structure for Rapid Interference Detection[C]. Computer Graphics, New Orleans, LA, USA, 1996, 182-189.
[16] H.Noborio, S.Fukuda and S.Arimoto. Fast Interference Check Method Using Octree Representation[J]. Advanced Robotics. 3(3): P193~212, 1989.
[17] B.Naylor, J.Amanatides, W.Thibault. Merging BSP Trees Yields Polyhedral Set Operations[J], ACM Computer Graphics (SIGGRAPH' 90 Proceedings), 24(2): P115~124, 1990.
[18] W.Thibault and B.Naylor. Set operations on Polyhedra Using Binary Space PartitioningTrees[J].ACM Computer Graphics, 21(4): P153~162, 1987.
[19] Stephen J.Adelson and Larry F.Hodges. Generating exact ray-traced animation frames by reprojection[J]. IEEE Computer Graphics and Applications, 15(3): P43~52, 1995.
[20] T.L.Kay and J.T.Kajiya. Ray tracing complex scenes[J]. ACM Computer Graphics, 20(4): P269~278, 1986.
[21] J.Goldsmith and J.Salmon. Automatic creation of object hierarchies for ray tracing[J]. IEEE Computer Graphics and Application, 7(1): P14~20, 1987.
[22] H.Weghorst, G.Hooper and D.P.Greenberg. Improved computational methods for ray tracing[J]. ACM Transaction on Computer Graphics, 3(1): P52~69, 1984.
[23] I.J.Palmer and R.L.Grimsdale. Collision detection for animation using sphere-trees[J]. Computer Graphics Forum, 14(2): P105~116, 1995.
[24] I.J.Palmer. Collision detection for animation: the use of the sphere-tree data structure[C].The Second Departmental Workshop on Computing Research, University of Bradford, 201-209,June 1995.
[25]魏迎梅.虚拟环境中碰撞检测问题的研究[D],长沙:国防科技大学,2000.
[26]范昭炜,万华根,高曙明.基于流的实时碰撞检测算法[J].软件学报, 15(10): 1505~1514,2004.
[27] Xinyu Zhang and Young J. Kim. Interactive Collision Detection for Deformable Models using Streaming AABBs[C]. In: Proc. of the ACM IEEE Transactions on Visualization and Computer Graphics. 3:318~329, 2007.
[28] Naga K. Govindaraju, Ming C. Lin, Dinesh Manocha, Quick-ULLIDE: Fast Inter- and Intra-Object Collision Detection using Graphica Processors[C]. Proceedings of the 2005 IEEE Conference on Virtual Reality, 59~66, 2005.
[29]王季,翟正军,蔡小斌.基于球深度纹理的实时碰撞检测算法[J],系统仿真学报, 19(11):P59~63, 2007.
[30] Dae-Hyun Kima, Han-Soo Choi. Hybrid bounding volume hierarchies for fast proximity queries[C]. ICMIT 2005: Information Systems and Signal Processing, 304-306, 2005.
[31]刘晓东,姚兰,邵付东,王颖.一种基于混合层次包围盒的快速碰撞检测算法[J].西安交通大学学报, 41(2):P141～144+157, 2007.
[32]朱元峰,孟军,谢光华,马文娟.基于复合层次包围盒的实时碰撞检测研究[J].系统仿真学报, 20(2):P372～377, 2008.
[33]李文辉,王天柱,王祎,秦忠,基于粒子群面向可变形物体的随机碰撞检测算法[J],系统仿真学报, 18(8):2206～2209, 2006.
[34]赵伟,李文辉,夏云飞.基于模拟退火遗传算法的凸多面体间碰撞检测算法研究[J]吉林大学学报(工学版), 38(3):P676~679, 2008.
[35]刘晓平,曹力.基于MPI的并行八叉树碰撞检测[J]计算机辅助设计与图形学学报, 19(2):P184~187+192, 2007.
[36]赵伟,何艳爽.一种快速的基于并行的碰撞检测算法[J],吉林大学学报(工学版),38(1):P152~157, 2008.
[37] Tomas Akenine-Moller, Eric Haines, Real-Time Rendering[M/OL]. A K Peters, Ltd. 2002. [2002-9-18]. http://www.realtimerendering.com/ http://users.volia.net/fajrvehr/
[38]范昭炜,实时碰撞检测技术研究[D],浙江:浙江大学,2003.
[39] Lin MC, Manocha D. Interactive geometric computations using graphics hardware[C]. International Conference on Robotics and Automation,201-205, 2002.
[40] Lin MC,Canny J. Efficient algorithms for incremental distance computation[C]. In Proceedings of the IEEE International Conference on Robotics and Automation, 1008~1014, 1991.
[41] Lin MC. Efficient Collision detection for animation and robotics[D].Ph.D. Thesis, Department of Electrical Engineering and Computer Science, University of California, Berkeley, 1993.
[42] Ponamgi MK, Cohen JD, Lin MC, Manocha D. Incremental algorithms for collision detection between polyhedral models[C]. In SIVE 95,The First Workshop on Simulation and Interaction in Virtual Environments, 1: 84~91, 1995.
[43] Gilbert EG, Johnson DW, Keerthi SS. A fast procedure for computing the distance between objects in three-dimensional space[C]. IEEE Journal on Robotics and Automation, 4: 193~203, 1988.
[44] A.Geria-Alonso, N.Serrano, J.Flaquer. Solving the collision detection problem[C], IEEE Computer, Graph, Appl, 205-207,May, 1994.
[45] M.Held, J.T.Klosowski, J.S.B.Mitchell. Evaluation of collision detection methods for virtual reality fly-throughs[C], In Pros.7th Canad, Conf.Comput.Geom, 151-159,1995.
[46] Shinya M, Forgue M. Interference detection through rasterization[J], Journal of Visualization and Computer Animation, 2: 131~134, 1991.
[47] Rossignac J, Megahed A, Schneider BO. Interactive inspection of solids: cross-section and interferences[J], Computer Graphics, 26(2): 353~360, 1992.
[48] Myszkowski K, Okunev OG, Kunii TL. Fast collision detection between computer solids using rasterizing graphics hardware[J]. The Visual Computer,11: P497~511, 1995.
[49] Baciu G, Wong WSK. Rendering in object interference detection on conventional graphics workstations[C]. In Proceedings of the Pacific Graphics, Seoul National University, Korea, October, P51~58,1995.
[50] Baciu G, Wong SKW, Sun H. RECODE: An image-based collision detection algorithm[J], Journal of Visualization and Computer Animation, 10(4): P181~192, 1999.
[51] Hoff III KE, Zaferakis A, Lin M, Manocha D. Fast and simple 2D geometric proximity queries using graphics hardware [J]. Proceedings of ACM Symposium on Interactive 3D Graphics,145-148, 2001.
[52] Kim YJ, Lin M, Manocha D. Fast penetration depth estimation using rasterization hardware and hierarchical refinement[C].In Symposium on Computational Geometry’2003,386-387, 2003.
[53] P.M Hubbud. Approximation polyhedra with spheres for time-critical collision detection[C]. ACM Trans.Graph, 15(3):179-210, July, 1996.
[54] N.Beckmann, H.-P.Kriegel, R.Schneider, B.seeger. The R-tree: An effient and robust access method for points and rectangles[C]. In Proc. ACM SIGMOD International Conference on Management of Data, 322-331,1990.
[55]魏迎梅,王涌,吴泉源,石教英.碰撞检测中的层次包围盒方法[J].计算机应用, 20(8):241-244, 2000.
[56] J.D.Cohen, M.C.Iin, D.Manochal. I-COLLIDE:Aninteractive and Exact Collision Detection System for Large-Scale Environments[C]. Proceedings of ACM Interactive 3D Graphics Conference, 189-196, 1995.
[57] Gvan den Bergen, Efficient Collision Detection of complex Deformable Model using AABB Trees[J], Journal of Graphics Tools, 2(4):l-13, 1997.
[58] http://www.cs.unc.edu/-geom/OBB/0BBT.html.
[59] Brian miritich, V-Clip: fast and robust polyhedral collision detection [J]. (MERL Technical Report 97-05), ACM Trans. On Graphies, July, 17(3):177-208, 1998.
[60] Hudson T, Lin M, Choen J, etal. V-collide: accelerated collision detection for VRML[C]. In: Proc. Of VRML Coference,1997.
[61] J. T. Kloswoski, M. Held, J. S. BMitchell, H. Sowiaral and K. Zikna. Efficient Collision Detection Using Bounding Volume Hirerachies of k-DOPs[J]. IEEE Transactions on Visualization and Computer Graphies, 4(1): 21-36,1998.
[62]高春晓,刘玉树.碰撞检测技术综述[J].计算机工程与应用, 38(5):9-11+40, 2002.
[63] Barry Wilkinson,Michael Allen.并行程序设计[M].陆鑫达等译,第2版,北京:机械工业出版社, 2005.
[64]陈国良.并行算法的设计与分析(修订版) [M].北京:高等教育出版社,2002.
[65]陈国良.并行计算—结构.算法.编程(修订版) [M].北京:高等教育出版社,2003.
[66]泥宗涛,余英林.基于分层包围盒的连续碰撞检测加速算法.计算机工程与应用[J], 36(10):4-26, 2000.
[67]范昭炜,万根华,高曙明.基于并行的快速碰撞检测算法[J].系统仿真学报,9(12): 548-552, 2000.
[68]刘晓东,姚兰,邵付东,王颖.一种基于混合层次包围盒的快速碰撞检测算法[J].交通大学学报, 41(2):141-144+157, 2007.
[69]范晓磊,谭桂臻.混合包围盒碰撞检测算法的研究[J].科技信息,10,12-13, 2007.
[70]蔡文军,陈虎.基于混合模型的碰撞检测优化算法研究[J].计算机与现代化,7,49-52, 2006.
[71]朱元峰,孟军,谢光华,马文娟.基于混合层次包围盒的实时碰撞检测研究[J].系统仿真学报, 20(2): 372-377, 2008.
[72] Ritter J. An efficient bounding sphere [C]. In Graphics Gems (edited by Andrew Glassner),Academic Press Professional, Inc. San Diego, CA, USA,301-303, 1990.
[73] Kin DJ, Guibas L J, Shin S J. Fast collision detection among multiple moving spheres[C]. IEEE Transactions on Visualization and Computer Graphics,4(3): 230-242,1998.
[74] Turk G. Interactive collision detection for molecular graphics[D].Computer Science Department, University of North Carolina at Chapel Hill,1989.
[75]徐鸣凯,丁友东,王肃.时空相关性在多物体碰撞检测中的应用[J].中国图象图形学报, 11(11):1704-1707, 2006.
[76]张蕾,杨波.并行粒子群优化算法的设计与实现[J].通信学报, 26(1):289-292, 2005.
[77] Kennedy J, Eberhart R. Particle Swarm Optimization[C], Proceeding of IEEE International Conference on Neural Networks, Perth, Australia, 223-226, 1995.
[78] K. Hoff, A.Zaferakis, D.Manocha. Fast and simple 2D geometric proximity queries using graphicsn hardware[C]. In: Int’l Conf. Interactive 3D Graphics, Berlin ACM Press, 145-1482001.
[79] T.Larrsson, T.Akenine. Efficient collision detection for models deformed by morphing [J]. The Visual Computer,19(2):164-174,2003.
[80] T Klugt, M Alexa. Bounding volumes for linearly interpolated shapes[C]. In: Proc of the 22nd Int’l conf on Computer Graphics. Crete, Greece: IEEE Computer Society Press, 134-139,2004.
[81] A Mohr, M Gleicher. Building efficient, accurate character skins from examples [J]. ACM Transaction on Graph(SIGGRAPH2003), 22(3):562-568, 2003,
[82] O Heim, C.S.Marshall, A.Lake. Fast collision detection for 3D bones-based articulated characters [J]. Game Programming Gems 4, (4):503-514,2004.
[83] J Hejl. Hardware skinning with quaternions [J]. Game Programming Gems 4, (4):487-495, 2004.
[84] L Kavan, J Zara. Fast collision detection for skeletally deformable models [J]. Computer Graphics Forum, 24(3):363-372,2005.
[85] D Eberly. a practical approach to real-time computer graphics[J]. 3D game engine design, (9): 25-29,2001.
[86] L Kavan, J Zara. Spherical blend skinning: A real-time deformation of articulated models[J]. ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, ACM Press, 9-16, 2005.
[87] B Gaertner. Fast and robust smallest enclosing balls[C]. In: Proc of the 7th Annual European Symposium on Algorithms. Prague: Springer Verlag press, 325-338,1999.
[88] J Brown, S Sorkin, C Bruyns, Latombe, et al. Real-time simulation of deformable objects: tools and application [C]. In: Proc of the 14th Int’l conf on Computer Animation. Seoul, South Korea: IEEE Computer Society Press, 228-258, 2001.
[89] Cameron S. A Comparison of two fast algorithms for computing the distance between convex polyhedron [J].IEEE transactions on Robotics and Automation, 13(6):915-920,1997.
[90] Bobrow J E. A direct minimization approach for obtaining the distance between convex polyhedron [J]. International Journal of Robo tics Research, 8(3):65-76, 1989.
[91] SelimSZ, Almohamad H A. Collision computation of moving bodies [J]. European Journal of Operational Research, 19(1):121-129,1999.
[92] L in M C, Manocha D. Fast interference detection between geometric models [J] The Visual Computer, 11(10):542-561, 1995.
[93] Gilbert E G, Johnson D W, Keerth i S S. A fast procedure for computing the distance between complex objects in three dimensional space [J]. IEEE Trans on Robotics and Automation, 4(2):193-203, 1988.
[94]谢政.非线性最优化[M].国防科技大学出版社,2003.9.
[95]李学庆.凸体间的碰撞检测研究[D].山东大学博士论文, 2002.
[96]谢政.非线性最优化[M].国防科技大学出版社, 2003.09.
[97]王小平,曹立明.遗传算法-理论、应用与软件实现[M].西安交通大学出版社, 2002.
[98]彭卓华.利用遗传算法求解一类非线性规划问题的最优解[M].数学理论与应用, 2002.09.
[99] [美]Zbigniew Michalewicz.周家驹,何险峰译.演化程序遗传算法和数据编码的结合[M].北京科技出版社,2000.
[100] James T.Klosowski, Martin Held. Efficient Collision Detection Using Bounding Volume Hierarchies of k-Dops[J].1996.
[101] GINO VAN DEN BER GEN. Efficient Collision Detection of Complex Deformable Models using AABB Trees [J]. Journal of Graphics Tools, 4(2):1-13, 1999.
[102] S. Gottschalk, M.C. Lin, D. Manocha. OBB tree: a hierarchical structure for rapid interference detection[C]. Proceedings of the ACM SIGGRAPH Conference on Computer Graphics, August 1996, New Orleans: ACM Press,171-180,1996.
[103] van den Bergen, G. Efficient collision detection of complex deformable models using AABB trees [J]. Journal of Graphics Tools, 2(4):1-13, 1997.
[104]王鹏,吕爽,聂治,谢千河等.并行计算应用及实战[M].机械工业出版社,2008.