面向虚拟装配的干涉检测关键技术研究
|
摘要
干涉检测技术是计算机图形学中的一个关键技术,在虚拟装配、虚拟手术、飞行导航、机器人路径规划和计算机游戏动画等领域中有着非常广泛的应用。这些应用领域通常要求系统能预计可能发生的干涉,并根据距离信息及时地对路径进行调整和变更,以避免可能发生的干涉。因此,对于这些应用领域来说,快速地判定对象的位置关系并提供一个准确的距离信息(分离距离、穿透深度和距离实现向量)成为图形学算法设计工作的首要任务。它不仅仅局限于某个特定问题,涉及到计算机科学、动力学、机械工程和数学等多个学科,对它展开研究具有重要的实践意义和理论价值。但是迄今为止这个课题仍然存在许多问题没有解决,特别是对计算精度要求很高的应用环境。本论文研究的目的是将扫描线技术、包围体层次树、分支限界策略、启发式搜索算法和非线性规划理论等应用到本课题的研究中,寻求本课题一些关键问题的快速和有效的解决方法。
本论文主要针对平面多边形、凸多面体和空间曲面这三种模型的干涉检测和距离求解问题进行了研究,并且获得了一些有意义的成果。
本论文的主要创新性工作如下:
1.提出了求解平面凸多边形最小平移距离的QuasiQuickHull算法—QQH算法。QQH算法在QuickHull算法基础上,利用面积计算对形态和进行隐式构造,解决了平面凸多边形的最小平移距离问题。算法先通过执行两次GJK(Gilbert-Johnson-Kerrthi)算法获得TCSO(translational C-space obstacle )对象M上的两互异顶点;再根据(三角形)面积计算获得与M内接的初始多边形P;然后确定P上距离原点最近的边,并通过面积计算搜索M上与最近边对应的对拓顶点;然后利用新搜索到的对拓顶点更新P的边界,迭代测试,直至找到M边界上距离原点最近的边或顶点为止。该方法给出了基于面积值判断的快速终止条件,避免了异常情形的特殊处理,并能通过区域测试快速判定两多边形是否发生干涉。
2.提出了判定平面简单多边形位置关系的扫描线算法。算法在包围体层次树干涉检测算法基础上,利用扫描线技术判定单调链的位置关系,解决了一般多边形之间的位置关系判定问题。该方法先对多边形进行单调链分解;然后对单调链构造包围盒层次树,并利用包围体层次树的干涉检测技术确定包围盒发生干涉的单调链对;再根据扫描线技术判定链对的位置关系;最后,根据链对的测试结果来精确判定多边形的位置关系。该方法能有效地区别边界接触和内部相交两种情形,并且提高了射线求交法判定多边形包含关系的稳定性。
3.提出了一种计算平面简单多边形分离距离的单调链配对算法。该算法在包围体层次树距离算法基础上,通过对单调链进行选择性配对来确定可能包含最近点对的子边界,解决了一般多边形之间的分离距离问题。该算法先根据多边形包围盒的位置关系初步确定对可能包含最近点的关联边界,并对多边形距离上界值进行初始化;然后,对关联边界进行单调性分解,并对单调性相同的链构造包围体层次树;再利用包围体层次树距离算法对单调性互异的链对进行选择性匹配,并根据最近获得的链对的几何信息来动态更新距离上界值;最后,利用层次树距离算法迭代计算单调链的距离,从而获得多边形的最近距离。该方法采用基于距离阈值的筛选策略对单调性互异的链对进行选择性匹配,减少了包围盒距离计算和边对距离计算的次数,从而大大提高了算法的效率。
4.提出了一种求解平面简单多边形穿透深度的平移向量算法。该算法在旋转标尺算法和边界凸分解技术基础上,通过搜索使得多边形刚好发生接触的最短平移向量来确定穿透深度的实现向量,解决了一般多边形之间的穿透深度问题。该算法首先对一般多边形构造凸包并计算凸包的穿透深度;然后,对多边形
Interference detection is an important technology of computer graphics, which is extensively used in the fields such as virtual assembly, virtual surgery, flight navigation, path planning of robots and animation. For above applications of computer graphics, both information of distance and detection of intersection are required to adjust the route/trajectory timely and avoid the possible interference. So, it is vital that determine the position between objects and provide distance information (separation, penetration depth and the witness vector) efficiently and accurately to fit the need of such applications. The research work, which is not limited to a special problem, involves many subjects such as computer science, dynamics, machine engineering and mathematics. Because of the great value in theory and practice, various new theories and algorithms have emerged in endlessly. However, so far many difficulties remain unresolved, especially in some applications that require an accurate measure. The objective of this research is to present new approaches for improving the performance of distance algorithm by use of some existing technologies such as sweeping line, bounding volume hiberarchy, branch limit strategy, heuristic searching and nonlinear programming theory. The research of the dissertation consists of the interference detection and distance computation for some typical models such as planar polygon, convex polyhedron and smooth surface, and some efficient algorithms are presented in the paper.
The principal research work and novelties are listed as follows:
1.A quasi QuickHull algorithm (QQH algorithm) computing the distance between planar convex polygons is presented in the dissertation. QQH algorithm, which is based on the QuickHull algorithm, solves the problem of minimum translational distance (MTD) between planar convex polygons by constructing the translational C-space obstacle (TCSO) M of both objects implicitly with computing directed area. Firstly, two different vertices are obtained by calling GJK (Gilbert-Johnson-Kerrthi) algorithm two times; secondly, the initial inner polygon P is calculated via (triangle) area computation; thirdly, the nearest edge on P distance to origin is determined and then the opposite vertex on M corresponds to the nearest edge is searched using area computation; finally, the boundary of P is updated by adding the new opposite vertex and carries out the above procedure repeatedly until the nearest edge or vertex on the border of M is found.QQH algorithm provides a fast terminate condition based on judging the area and avoids the special process for the exception, as well as determines whether interference occurs or not by region test.
2.A sweep line method to determine the position between two planar simple polygons is purposed in this paper. Based on intersection detection algorithm of bounding volume hierarchy tree (BVT), the method resolves the problem of relation determining for planar simple polygons by testing the position between monotone chains with sweep line technology. Firstly, the border of polygon is decomposed into a collection of monotone chains; secondly, the BVH of monotone chains are constructed respectively and the monotone chain-pairs whose bounding volume overlap are obtained using interference detection technology based on BVT; thirdly, the relation of a monotone chain-pair is decided through sweep line approach; finally, the accurate relation between polygons are achieved by the further test accord to the results from chain-pair test. The new method can distinguish just boundary touching from inner intersection, and the stability of ray shooting for checking whether one object contain the other is enhanced.
3.A new approach based on coupling monotone chains pairwse for computing the separation between planar simple polygons is put forward in the article. On the basis of BVT distance algorithm, the approach settles the separation problem between two separable simple polygons by coupling the monotone chains selectively to determine the possible sub-boundary where the nearest point lies with. Firstly, both the interested boundary
本论文主要针对平面多边形、凸多面体和空间曲面这三种模型的干涉检测和距离求解问题进行了研究,并且获得了一些有意义的成果。
本论文的主要创新性工作如下:
1.提出了求解平面凸多边形最小平移距离的QuasiQuickHull算法—QQH算法。QQH算法在QuickHull算法基础上,利用面积计算对形态和进行隐式构造,解决了平面凸多边形的最小平移距离问题。算法先通过执行两次GJK(Gilbert-Johnson-Kerrthi)算法获得TCSO(translational C-space obstacle )对象M上的两互异顶点;再根据(三角形)面积计算获得与M内接的初始多边形P;然后确定P上距离原点最近的边,并通过面积计算搜索M上与最近边对应的对拓顶点;然后利用新搜索到的对拓顶点更新P的边界,迭代测试,直至找到M边界上距离原点最近的边或顶点为止。该方法给出了基于面积值判断的快速终止条件,避免了异常情形的特殊处理,并能通过区域测试快速判定两多边形是否发生干涉。
2.提出了判定平面简单多边形位置关系的扫描线算法。算法在包围体层次树干涉检测算法基础上,利用扫描线技术判定单调链的位置关系,解决了一般多边形之间的位置关系判定问题。该方法先对多边形进行单调链分解;然后对单调链构造包围盒层次树,并利用包围体层次树的干涉检测技术确定包围盒发生干涉的单调链对;再根据扫描线技术判定链对的位置关系;最后,根据链对的测试结果来精确判定多边形的位置关系。该方法能有效地区别边界接触和内部相交两种情形,并且提高了射线求交法判定多边形包含关系的稳定性。
3.提出了一种计算平面简单多边形分离距离的单调链配对算法。该算法在包围体层次树距离算法基础上,通过对单调链进行选择性配对来确定可能包含最近点对的子边界,解决了一般多边形之间的分离距离问题。该算法先根据多边形包围盒的位置关系初步确定对可能包含最近点的关联边界,并对多边形距离上界值进行初始化;然后,对关联边界进行单调性分解,并对单调性相同的链构造包围体层次树;再利用包围体层次树距离算法对单调性互异的链对进行选择性匹配,并根据最近获得的链对的几何信息来动态更新距离上界值;最后,利用层次树距离算法迭代计算单调链的距离,从而获得多边形的最近距离。该方法采用基于距离阈值的筛选策略对单调性互异的链对进行选择性匹配,减少了包围盒距离计算和边对距离计算的次数,从而大大提高了算法的效率。
4.提出了一种求解平面简单多边形穿透深度的平移向量算法。该算法在旋转标尺算法和边界凸分解技术基础上,通过搜索使得多边形刚好发生接触的最短平移向量来确定穿透深度的实现向量,解决了一般多边形之间的穿透深度问题。该算法首先对一般多边形构造凸包并计算凸包的穿透深度;然后,对多边形
Interference detection is an important technology of computer graphics, which is extensively used in the fields such as virtual assembly, virtual surgery, flight navigation, path planning of robots and animation. For above applications of computer graphics, both information of distance and detection of intersection are required to adjust the route/trajectory timely and avoid the possible interference. So, it is vital that determine the position between objects and provide distance information (separation, penetration depth and the witness vector) efficiently and accurately to fit the need of such applications. The research work, which is not limited to a special problem, involves many subjects such as computer science, dynamics, machine engineering and mathematics. Because of the great value in theory and practice, various new theories and algorithms have emerged in endlessly. However, so far many difficulties remain unresolved, especially in some applications that require an accurate measure. The objective of this research is to present new approaches for improving the performance of distance algorithm by use of some existing technologies such as sweeping line, bounding volume hiberarchy, branch limit strategy, heuristic searching and nonlinear programming theory. The research of the dissertation consists of the interference detection and distance computation for some typical models such as planar polygon, convex polyhedron and smooth surface, and some efficient algorithms are presented in the paper.
The principal research work and novelties are listed as follows:
1.A quasi QuickHull algorithm (QQH algorithm) computing the distance between planar convex polygons is presented in the dissertation. QQH algorithm, which is based on the QuickHull algorithm, solves the problem of minimum translational distance (MTD) between planar convex polygons by constructing the translational C-space obstacle (TCSO) M of both objects implicitly with computing directed area. Firstly, two different vertices are obtained by calling GJK (Gilbert-Johnson-Kerrthi) algorithm two times; secondly, the initial inner polygon P is calculated via (triangle) area computation; thirdly, the nearest edge on P distance to origin is determined and then the opposite vertex on M corresponds to the nearest edge is searched using area computation; finally, the boundary of P is updated by adding the new opposite vertex and carries out the above procedure repeatedly until the nearest edge or vertex on the border of M is found.QQH algorithm provides a fast terminate condition based on judging the area and avoids the special process for the exception, as well as determines whether interference occurs or not by region test.
2.A sweep line method to determine the position between two planar simple polygons is purposed in this paper. Based on intersection detection algorithm of bounding volume hierarchy tree (BVT), the method resolves the problem of relation determining for planar simple polygons by testing the position between monotone chains with sweep line technology. Firstly, the border of polygon is decomposed into a collection of monotone chains; secondly, the BVH of monotone chains are constructed respectively and the monotone chain-pairs whose bounding volume overlap are obtained using interference detection technology based on BVT; thirdly, the relation of a monotone chain-pair is decided through sweep line approach; finally, the accurate relation between polygons are achieved by the further test accord to the results from chain-pair test. The new method can distinguish just boundary touching from inner intersection, and the stability of ray shooting for checking whether one object contain the other is enhanced.
3.A new approach based on coupling monotone chains pairwse for computing the separation between planar simple polygons is put forward in the article. On the basis of BVT distance algorithm, the approach settles the separation problem between two separable simple polygons by coupling the monotone chains selectively to determine the possible sub-boundary where the nearest point lies with. Firstly, both the interested boundary
引文
[1] A Fuhrmann,G Sobotka et al.Distance fields for rapid collision detection in physically based modeling[C]. In: proceeding of Graphics Conference, Keldysh Inst. of Applied Mathematics, 2003: 58-65.
[2] A Gregory, M C Lin. Fast and accurate collision detection for haptic interaction using a three degree-of-freedom force-feedback device[J]. Computational Geometry: Theory and Applications, 2000,15(1): 69-89.
[3] P Jimenez, F Thomas. 3D collision detection: a survey[J]. Computers & Graphics, 2001, 25(2): 269-285.
[4] A Foisy,W Hayward.A safe swept volume method for collision detection[A].The 6th International Symposium of Robtics Research,Pittsburgh,PE,1993,61-68.
[5] M Herman.Fast three-dimensional collision free motion planning[C]. In: proceedings of the IEEE International Conference on Robotics and Automation,1986,2:1056-1063.
[6] A G-Alonso, N Serrano, J Flaquer. Solving the collision detection problem [J]. IEEE Computer Graphics and Applications 1994; 14(3): 36-43
[7] P.M.Hubbard, Approximating polyhedra with spheres for time-critical collision detection[J], ACM Transactions On Computer Graphics,1996, 15(3): 179-210.
[8] H Samet. Applications of spatial data structures: Computer Graphics, Image Processing, and GIS[M]. Addison-Wesley, Reading, MA, 1990.
[9] K Hamada, Y Hori.Octree-based approach to real-time collision-free path planning for robot manipulator [C]. In: ACM96-MIE, 1996,705-10.
[10] G Schaufler, W Stürzlinger.A three-dimensional image cache for virtual reality[C]. EUROGRAPH’96, 1996,227-236.
[11] S Zhou, B J Christopher. Design and implementation of multi-scale databases [C]. In: Proc. of the 7th Int’l Symp. on Advances in Spatial and Temporal Databases. London: Springer-Verlag, 2001,365-386.
[12] S.Ar, B Chazelle. Self-customized BSP trees for collision detection[J]. Computational Geometry, 2000,15, 91-102
[13] K Chung, W Wen Ping. Quick collision detection of Polytopes in virtual environments[C]. In: Proc. of the ACM Symposium on Virtual Reality Software and Technology. ACM Press, 1996:125-132.
[14] 李学庆,孟祥旭等 基于启发式搜索分离向量的凸多面体碰撞检测[J].计算机学报,2003,26(7):837-847.
[15] K.P Bennett , O.L Mangasarian. Neural network training via linear programming(R). In PM Pardalos, editor,Advances in Optimization and Parallel Computing, 56-67. Elsevier Science Publishers BV, Amsterdam, 1992.
[16] E Flato, D Haperin. Robust and efficient construction of planar Minkowski sums[D]. Masters thesis, Tel Aviv University, 2000.
[17] E Fogel, D Halperin. Exact Minkowski sums of convex polyhedra[C]. Symposium on Computational Geometry 2005: 382-383.
[18] G Varadhan, D Manocha. Accurate Minkowski sum approximation of polyhedral models[C]. In: Pacific Conference on Computer Graphics and Applications, IEEE Computer Society, 2004,392-401.
[19] A Kual,M O’Conor,V Srinivasan. Computing Minkowski sums of regular polygons[C]. In: proceedings 3rd Canadian Conference of Computational Geometry, 1991,74-77.
[20] P K Agarwal,E Flato,D Halperin.Polygon decomposition for efficient construction of Minkowski sums[J]. Computational Geometry: Theory and Applications, 2002, 21, 39-61.
[21] Xueqing Li, Yi-King Choi, Wenping Wang. Collision detection of convex polyhedra based on duality transformation[R]. Tech Report TR-2005-01, Department of Computer Science, Hongkong University, 2005.
[22] D.P. Dobkin , D.G. Kirkpatrick. Fast detection of polyhedral intersection [J]. Theoretical Computer Science, 1983,27(3): 241-253.
[23] B. Chazelle. Triangulating a simple polygon in linear time [J]. Discrete Computational Geometry, 1991,6(5):485-524.
[24] P K. Agarwal , M Sharir. Red-blue intersection detection algorithms with applications to motion planning and collision detection[J]. SIAM Journal of Computational, 1990,19:297-321.
[25] B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane[J]. J. Assoc. Comput. Mach., 1992,39(1):1-54.
[26] T M. Chan. A simple trapezoid sweep algorithm for reporting red/blue segment intersections[C]. In Proc. 6th Canad. Conf. Comput. Geom. 1994,263-268.
[27] J Basch, J Erickson. Kinetic collision detection between two simple polygons [J]. Computational Geometry: Theory and Applications .2004, 27(3): 211-235.
[28] J Hershberger,S Suri. A pedestrian approach to ray shooting: Shoot a ray; take a walk [J]. Journal of Algorithms, 1995,18:403~431.
[29] D.M. Mount. Intersection detection and separators for simple polygons[C]. In: Proc. 8th Annu. ACM Sympos. Comput. Geom., 1992, 303-311.
[30] S Ehmann , M C. Lin. Accurate and fast proximity queries between polyhedra using convex surface decomposition[C]. In: proceedings of Eurographics’2001, 2001,20(3): 500-510.
[31] M C Lin, D Manocha,M Ponamgi. Fast algorithms for penetration and contact determination between non-convex polyhedral models[C]. In: proceedings of IEEE International Conference on Robotics and Automation,1995,2707-2712.
[32] H S Kim,H Ko et al. A collision detection for interactive assembly simulation[C]. In: proceedings of the 1997 IEEE international Symposium Assembly and Task Planning, Marina del Rey, CA, 1997,170-175.
[33] Gino Van Den Bergen, Efficient Collision detection of complex deformable models using AABB-Trees [J]. Journal of Graphics Tools, 1997, 2(4): 1-13.
[34] S Gottschalk, M C Lin, D Manocha. OBBTree: A hierarchical structure for interference detection[C]. In: Computer Graphics Proceeding, SIGGRAPH’96, 1996, 171-180.
[35] P M Hubbard. Real-time collision detection and time-critical computing[C]. In: proceedings of the First ACM Workshop on Simulation and Interaction in Virtual Environments, 1995, 92-96.
[36] M Klosowski, J Held, J. Mitchell, Evaluation of collision detection methods for virtual reality fly-throughs[C]. In: proceedings of the Seventh Canadian Conference on Computer Geometry, 1995, 3,205-210.
[37] S. Ehmann, M.C. Lin. Accurate and fast proximity queries between polyhedra using convex surface decomposition[C]. Comput. Graph. Forum. 2001, 20(3): 500-510.
[38] P Terdiman. Memory-optimized bounding-volume hierarchies [DB/OL].http://www.codercorner.com/Opcode.htm, 2001.
[39] E. Larsen, S Gottschalk, M. Lin, and D. Manocha. Fast proximity queries with swept sphere volumes[R]. Technical Report TR99-018, Department of Computer Science, University of North Carolina, 1999.
[40] S. Krishnan, A. Pattekar, M. Lin, and D. Manocha. Spherical shell: A higher order bounding volume for fast proximity queries[C]. In: Proc. 3rd Internat. Workshop Algorithmic Found. Robot. , 1998, 122-136.
[41] S. Cameron , R.K. Culley. Determining the minimum translational distance between two convex polyhedra[C]. In: proceedings of IEEE International Conference on Robotics and Automation,1986, 591-596.
[42] D. Dobkin, J. Hershberger et al. Computing the intersection-depth of polyhedra [J].Algorithmica, 1993, 9:518-533.
[43] E.G. Gilbert, D.W. Johnson, and S.S. Keerthi. A fast procedure for computing the distance between objects in three-dimensional space [J]. IEEE Journal of Robotics and Automation. 1988, RA-4: 193-203.
[44] C J Ong, E G. Gilbert. The Gilbert–Johnson–Keerthi distance algorithm: a fast version for incremental motions. In: proceeding of IEEE International Conference on Robotics and Automation, Albuquerque, Mexico, USA, 1997,1183~1189.
[45] S. Cameron. Enhancing GJK: Computing minimum and penetration distance between convex polyhedra[C]. In: proceedings of IEEE International Conference on Robotics and Automation, 1997, 3112-3117.
[46] G Bergen. A Fast and Robust GJK Implementation for Collision Detection of Convex Objects[J]. Journal of Graphics Tools, 1999,4(2): 7-25.
[47] G Bergen. Proximity queries and penetration depth computation on 3D game objects[C]. In: Proc. Game Developers Conf., 2001.
[48] M.C. Lin, J.F. Canny. Efficient algorithms for incremental distance computation[C]. In: proceedings of IEEE International Conference on Robotics and Automation, 1991, 1008-1014.
[49] L. Guibas, D. Hsu, and L. Zhang. H-Walk: Hierarchical distance computation for moving convex bodies[C]. In: Proc. 15th Annu. ACM Sympos. Comput. Geom., 1999, 265-273.
[50] S. Ehmann, M.C. Lin. Accelerated proximity queries between convex polyhedra using multi-level Voronoi marching[C]. In: Proc. IEEE/RSJ Internat. Conf. Intell. Robots Sys. , 2000, 2101-2106.
[51] M K Ponamgi, D Manocha et al. Incremental algorithms for collision detection between solid models[C]. In: Proc. ACM/Siggraph Symposium on Solid Modeling, 1995, 293-304.
[52] B. Mirtich. V-Clip: Fast and robust polyhedral collision detection [J]. ACM Trans. Graph., 1998, 17:177-208.
[53] J E. Bobrow. A direct minimization approach for obtainingthe distance between convex polyhedra[J]. International Journal of Robotics Research, 1989,8(3): 65-76.
[54] O Ma,M Nahon. A general method for computing the distance between convex polyhedra[C]. In: proceedings of ASME Conference on Advances in Design and Automation,1992,1(Pheonix,Arizona,USA),109-117.
[55] E.G. Gilbert , C.J. Ong. New distances for the separation and penetration of objects[C]. In: proceedings of IEEE International Conference on Robotics and Automation, 1994, 579-586.
[56] C J Ong, E Huang. An incremental version of growth distance[C]. In: proceedings of the IEEE International Conference On Robotics and Automation. Leuven, Belgium, 1998, 3671-3677.
[57] C J Ong, E Huang, S M Hong. A fast growth distance algorithm for incremental motions[J]. IEEE Transactions On Robotics and automation, 2000, 16( 6):880-890.
[58] S M Hong, J H Yeo. A fast procedure for computing incremental growth distances[J]. Robotica, 2000,18(4): 429-441.
[59] Y Jing. A neural network measuring the intersection of m-dimensional convex polyhedra (J). Automatica, 1995,31(4): 517-531.
[60] Y.J Kim, M .C Lin, D Monocha. Incremental penetration depth estimation between convex polytopes using dual-space expansion [J]. IEEE Transactions on Visualization and Computer Graphics, 2004,10(2): 152-163.
[61] P. Agarwal, L.J. Guibas et al. Penetration depth of two convex polytopes[C]. In 3rd. Nordic J. Computing, 2000,7:227-240.
[62] K Sridharan, S.S Keerthi. Computation of a penetration measure between 3D convex polyhedral objects for collision detection [J]. Journal of Robotic Systems, 2001(18): 623-631.
[63] 朱向阳,丁汉等.凸多面体之间的伪最小平移距离—Ⅰ.定义及其性质(J). 中国科学(E 辑), 2001, 31(2):128-136.
[64] Shih Ching-Long, Liu Jane-Yu. Computing the minimum directed distances between convex polyhedra (J). Journal of Information Science and Engineering, 1999,15(3): 353-373.
[65] F Chin,C A Wang.Optimal algorithms for the intersection and the minimum distance problem beteen planar polygons[J].IEEE Transactions on Computers,1983,C-32(12):1203-1207.
[66] N M Amato. Determining the separation of simple polygons[J]. International Journal of Computational Geometry & Applications, 1994, 4(4): 457-474.
[67] B. Chazelle. Triangulating a simple polygon in linear time. Discrete Comput. Geom.[J]. 1991(6): 485-524.
[68] LJ Guibas and R. Seidel, Computing Convolutions by Reciprocal Search[C]. Symposium. of Computational Geometry, 2001.
[69] S Quinlan.Efficient distance computation between non-convex objects[C]. In: proceedings of International Conference on Robotics and Automation, 1994, 3324-3329.
[70] D E. Johnson, E Cohen. A framework for efficient minimum distance computations[C]. In: Proceedings of IEEE International Conference on Robotics and Automation, Leuven, Belgium, 1998, 3678-3684.
[71] D E. Johnson, E Cohen. Bound coherence for minimum distance computations[C]. In: Proceedings of IEEE International Conference on Robotics and Automation, 1999,1843-1848.
[72] K Kawachi, H Suzuki. Distance computation between non-convex polyhedra at short range based on discrete Voronoi regions[C]. In: Proceedings of IEEE Geometric Modeling and Processing, Hong Kong, 2000,123-128.
[73] J A Carretero, M A Nahon et al. Solving distance problems with concave bodies using simulated annealing[C]. In: proceedings of the 2001 IEEE/RSI International Conference on Intelligent Robotics and Systems, Maui, Hawaii, USA, 2001,3:1507-1512.
[74] Y J. Kim, M A Otaduy et al. Fast penetration depth computation using rasterization hardware and hierarchical refinement[R]. UNC-CH Technical Report TR02-014,2002.
[75] Y.J Kim, M. A Otaduy et al. Fast penetration depth computation for physically-based animation [A]. In: Proceeding of ACM SIGGRAPH Symposium on Computer Animation[C], New York, USA, ACM Press, 2002, 23-32.
[76] A Hoff, A Zaferakis et al. Fast and simple geometric proximity queries using graphics hardware[C].in: proceedings of 2001 ACM Symposium on Iteractive 3D Graphics,2001, 145-148.
[77] B Heidelberger, M Teschner. Consistent penetration depth estimation for deformable collision response. In: Proc. Vision. Modeling, Visualization, 2004, 339-346.
[78] C J Ong.Distance Computation between smooth convex objects[C]. In: proceedings of IEEE International Conference On Robotics and Automation, Minnesota, USA, 1996, 785-790.
[79] E G Gilbert,C P Foo. Computing the distance between general convex objects in three-dimensional space [J]. IEEE Transactions on Robotics and Automation,1990,6(1):53-61.
[80] G J Hamlin,R B Kelley et al. Efficient distance calculation using the spherically-extended polytope(S-tope) model[C].In: proceedings of the 1992 IEEE International Conference on Robotics and Automation, Nice ,France,1992,2502-2507.
[81] J Tornero. Spherical-object representation and fast distance computation for robotics applications[C]. In: proceedings of IEEE International Conference on Robotics and Automation, Sacramento, California, USA, 1991,1601-1608.
[82] E J. Bernabeu, J Tornero. Hough transform for distance computation and collision avoidance [J]. IEEE Transactions on Robtics and Automation,2002,18(3):393-398.
[83] C Turnbull, S Cameron. Computing Distances Between NURBS-defined Convex Objects[C].in:proceedings of the 1998 IEEE International Conference on Robotics and Automation,Leuven, Belgium,1998,3685-3690.
[84] V Patoglu, R.B.Gillespie. Extremal distance maintenance for parametric curves and surfaces[C]. In: proceedings of IEEE International Conference on Robotics and Automation, Washington DC,USA, 2002, 2817-2823.
[85] F Thomas, C Turnbullet al. Computing signed distances between free-form objects[C]. In: proceedings of the 2000 IEEE International Conference on Robotics and Automation, San Francisco, USA, 2000,3713-3718.
[86] 刘浩.NURBS 曲面最短距离[D].南京航天航空大学,硕士论文,2002.
[87] 席光,蔡永林.用改进遗传算法求取曲面间最小距离[J]. 计算机辅助设计与图形学学报, 2002, 14(3):209-213.
[88] 任红民,毕惟红,吴庆标.自由曲面之间最短距离的一种新的改进遗传算法[J].计算机工程与应用, 2004, 23,62-64.
[89] J Rossignac, A Megahed, B.O Schneider. Interactive inspection of solids: cross-section and interferences. Computer Graphics, 1992, 26(2): 353~360.
[90] M Shinya, M Forgue. Interference detection through rasterization. Journal of Visualization and Computer Animation, 1991, 2:131~134.
[91] K Myszkowski, OG Okunev, TL Kunii. Fast collision detection between computer solids using rasterizinggraphics hardware. The Visual Computer, 1995, 11:497~511.
[92] G Baciu, SKW Wong, H Sun. RECODE: An image-based collision detection algorithm, Journal of Visualization and Computer Animation, 1999, 10(4): 181~192.
[93] NK Govindaraju, S Redon, MC Lin, D Manocha. CULLIDE: Interactive collision detection between complex models in large environments using graphics hardware. In Proc. ACM SIGGRAPH/Eurographics Workshop Graphics Hardware, 25-32, 2003.
[94] T Vassilev, B Spanlang, Y Chrysanthou. Fast cloth animation on walking avatars. Computer Graphics Forum, 2001, 20(3):260–267.
[95] KE Hoff III, A Zaferakis, MC Lin etal. Fast 3D geometric proximity queries between rigid and deformable models using graphics hardware acceleration. points at which edges intersect objects.Technical Report TR02-004, Department of Computer Science, University of North Carolina at Chapel Hill, 2002.
[96] B Heidelberger, M Teschner, M Gross. Volumetric collision detection for derformable objects. TR395 in Computer Science Department ETH Zurich, Switzerland, 2003.
[97] 范昭玮. 实时碰撞检测技术研究[D].浙江大学博士论文,2003.
[98] GT.Toussaint.Solving geometric problems with the rotating calipers[C].in: Proceedings of IEEE MELECON'83, Athens, Greece, 1983, A10.02/1-4.
[99] [CP/OL]http://www.lindo.com/downloads/LAPI-WINDOWS-IA32-4.0.zip.
[1] M.C Lin, J. F Canny. A fast algorithm for incremental distance calculation[C].In: Proceedings of IEEE International conference on Robotics and Automation, Sacramento, USA, 1991: 1008-1014.
[2] E.G Gilbert, D.W Johnson, S.S.Keerthi A fast procedure for computing the distance of complex objects in three-dimensional Space[J]. IEEE Journal of Robotics and Automation. 1998,4(2): 193-203.
[3] B. Mirtich. V-Clip: Fast and robust polyhedral collision detection [J]. ACM Trans. Graph., 1998, 17:177-208.
[4] S Cameron. Enhancing GJK: compute minimum and penetration distance between convex polyhedra[C]. In: Proceedings of IEEE International Conference on Robotics and Automation, Albuquerque, USA, 1997: 3112-3117.
[5] C J Ong , E G. Gilbert. The Gilbert–Johnson–Keerthi distance algorithm:a fast version for incremental motions. In: proceeding of IEEE International Conference on Robotics and Automation, Albuquerque, Mexico, USA, 1997,1183~1189.
[6] G. van Bergen, Proximity queries and penetration depth computation on 3D game objects [C]. In: Proceedings of Game Developers Conference, San Jose, USA,2001: 821-837.
[7] E.G. Gilbert , C.J. Ong. New distances for the separation and penetration of objects[C]. In: proceedings of IEEE International Conference on Robotics and Automation, 1994, 579-586.
[8] Y.J Kim, M.A Otaduy, M.C Lin. Fast penetration depth computation using rasterization hardware and hierarchical refinement[R]. Technical Report, UNC-Chapel Hill TR02-014, 2002.
[9] Y.J Kim, M. A Otaduy, M.C Lin. Fast penetration depth computation for physically-based animation [A]. In: Proceeding of ACM SIGGRAPH Symposium on Computer Animation[C], New York, USA, ACM Press, 2002, 23-32.
[10] Y.J Kim, M .C Lin, D Monocha. Incremental penetration depth estimation between convex polytopes using dual-space expansion[J]. IEEE Transactions on Visualization and Computer Graphics, 2004,10(2): 152-163.
[11] F.P. Preparata, M.I.Shamos. Computational geometry: An Introduction [M]. Springer-Verlag, New York, 1985.
[12] P.J Schneider, D.H Eberly. 计算机图形学几何工具算法祥解[M].周长发译.电子工业出版社,北京,2005.
[1] B. Chazelle. Triangulating a simple polygon in linear time[J]. Discrete Computational Geometry, 1991,6:485-524.
[2] D.M. Mount. Intersection detection and separators for simple polygons[C]. In: Proc. 8th Annu. ACM Sympos. Comput. Geom., 1992, 303-311.
[3] Gino Van Den Bergen, Efficient Collision detection of complex deformable models using AABB-Trees [J]. Journal of Graphics Tools, 1997, 2(4): 1-13.
[4] S Gottschalk, M C Lin, D Manocha. OBBTree: A Hierarchical Structure for Interference Detection[C]. In: Computer Graphics Proceeding, SIGGRAPH’96, 1996, 171-180.
[5] M Klosowski, J Held, J. Mitchell, Evaluation of collision detection methods for virtual reality fly-throughs[C]. In: proceedings of the Seventh Canadian Conference on Computer Geometry, 1995, 3,205-210.
[6] S. Ehmann, M.C. Lin. Accurate and fast proximity queries between polyhedra using convex surface decomposition[C]. Comput. Graph. Forum. 2001, 20(3): 500-510.
[7] S. Ehmann and M C Lin. Accurate and fast proximity queries between polyhedra using convex surface decomposition[C]. In: proceedings of Eurographics’2001, 2001,20(3): 500-510.
[8] M C Lin,D Manocha,M Ponamgi. Fast algorithms for penetration and contact determination between non-convex polyhedral models[C]. In: proceedings of IEEE International Conference on Robotics and Automation,1995,2707-2712.
[9] H S Kim,H Ko et al. A collision detection for interactive assembly simulation[C]. In: proceedings of the 1997 IEEE international Symposium Assembly and Task Planning, Marina del Rey, CA, 1997,170-175.
[10] P.K. Agarwal , M. Sharir. Red-blue intersection detection algorithms with applications to motion planning and collision detection[J]. SIAM Journal of Computational, 1990,19:297-321.
[11] B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane[J]. J. Assoc. Comput. Mach., 1992,39:1-54.
[12] K. Mulmuley. A fast planar partition algorithm[C]. In: Proceedings of the IEEE 29th Foundations of Computer Science, New York, 1988, 580-589.
[13] T M?ller .A fast triangle-triangle intersection test [J]. Journal of Graphics Tools, 1997,2(2): 25-30.
[14] U Manber 著,黄林鹏译.算法引论:一种创造性方法[M].北京:电子工业出版社,2005.
[1] F Chin,C A Wang.Optimal algorithms for the intersection and the minimum distance problem beteen planar polygons[J].IEEE Transactions on Computers,1983,C-32(12):1203-1207.
[2] N M Amato. Determining the separation of simple polygons[J]. International Journal of Computational Geometry & Applications, 1994, 4(4): 457-474.
[3] S Quinlan.Efficient distance computation between non-convex objects[C]. In: proceedings of International Conference on Robotics and Automation, 1994, 3324-3329.
[4] D E. Johnson , E Cohen. A framework for efficient minimum distance computations[C]. In: Proceedings of IEEE International Conference on Robotics and Automation, Leuven, Belgium, 1998, 3678-3684.
[5] 杨春成,张清浦,田向春等.顾及几何形状相似性的简单多边形最近距离计算方法[J].测绘学报, 2000,32(4): 311-318.
[6] K Kawachi , H Suzuki. Distance Computation between non-convex polyhedra at short range based on discrete Voronoi regions[C]. In: Proceedings of IEEE Geometric Modeling and Processing, Hong Kong, 2000,123-128.
[7] G.T. Toussaint.Solving geometric problems with the rotating calipers[C]. in:Proceedings of IEEE MELECON'83, Athens, Greece, 1983, A10.02/1-4.
[8] F.P. Preparata, M.I.Shamos. Computational geometry: An Introduction [M]. Springer-Verlag, New York, 1985.
[1] S. Cameron , R.K. Culley. Determining the minimum translational distance between two convex polyhedra[C]. In: proceedings of IEEE International Conference on Robotics and Automation,1986, 591-596.
[2] K. Sridharan S S. Keerthi. Computation of a penetration measure between 3D convex polyhedral objects for collision detection[J]. Journal of Robotic Systems, 2001(18): 623-631.
[3] D. Dobkin, J. Hershberger et al. Computing the intersection-depth of polyhedra [J].Algorithmica, 1993, 9:518-533.
[4] B Heidelberger, M Teschner. Consistent penetration depth estimation for deformable collision response. In: Proc. Vision. Modeling, Visualization, 2004 , 339-346,
[5] M. de Berg, M. van Kreveld, M. Overmars and O. Schwarzkopf. Computational Geometry, Algorithms and Applications[M], 2nd edition, Springer-Verlag, Berlin, 2000.
[6] E. Flato, D. Haperin. Robust and efficient construction of planar Minkowski sums[D]. Masters thesis, Tel Aviv University, 2000.
[7] G Varadhan, D Manocha. Accurate Minkowski sum approximation of polyhedral models[C]. In: Pacific Conference on Computer Graphics and Applications, IEEE Computer Society, 392-401
[8] Y J. Kim, M A Otaduy. Fast penetration depth computation using rasterization hardware and hierarchical refinement[R]. UNC-CH Technical Report ,TR02-014,2002.
[9] GT..Toussaint.Solving geometric problems with the rotating calipers[C]. in:Proceedings of IEEE MELECON'83, Athens, Greece, 1983, A10.02/1-4
[10] F.P. Preparata, M.I.Shamos. Computational geometry: An Introduction [M]. Springer-Verlag, New York, 1985.
[1] S.A Cameron, R.K Cully. Determining the minimum translation distance between two convex polyhedra(C), In: Proceeding of IEEE International Conference of Robot and Automations[C], San Francisco, CA, USA, 1986:591-596.
[2] M.C Lin, J.F Canny. Fast algorithm for incremental distance calculation(C), In: Proceeding of IEEE International Conference On Robotics and Automation, Sacramento, CA, USA, 1991:1008-1014.
[3] E.G Gilbert, D.W. Johnson, S.S. Keerthi. A Fast Procedure for computing the distance between complex objects in three-dimensional space (J). IEEE Journal of Robotics and Automation, 1988, 4(2): 193-203.
[4] Gino VAN Den Bergen. A fast and robust GJK implementation for collision detection of convex objects (J). Journal of Graphics Tools, 1999,4(2): 7-25.
[5] Y. J Kim, M.A Otaduy, M.C Lin. Fast penetration depth computation using rasterization hardware and hierarchical refinement[R]. Technical report, UNC-Chapel Hill TR02-014, Department of Computer Science, University of North Carolina, USA, North Carolina, Chapel Hill, 2002.
[6] Y.J Kim, M. A Otaduy, M.C Lin. Fast penetration depth computation for physically-based animation [A]. In: Proceeding of ACM SIGGRAPH Symposium on Computer Animation[C], New York, USA, ACM Press, 2002, 23-32.
[7] Y.J Kim, M .C Lin, D Monocha. Incremental penetration depth estimation between convex polytopes using dual-space expansion [J]. IEEE Transactions on Visualization and Computer Graphics, 2004,10(2): 152-163.
[8] 朱向阳,丁汉,熊有伦.凸多面体之间的伪最小平移距离—Ⅰ.定义及其性质(J). 中国科学(E 辑), 2001, 31(2):128~136.
[9] C.J Ong. A fast growth distance algorithm for incremental motions (J). IEEE Transactions On Robotics and Automation, 2000, 16(6): 880-890.
[10] K Sridharan. Efficient computation of a measure of depth between convex objects for graphics applications (J). Computers & Graphics, 2002,26(5): 785-793.
[11] SHIH CHING-LONG, LIU JANE-YU. Computing the minimum directed distances between convex polyhedra (J). Journal of Information Science and Engineering, 1999,15(3): 353-373.
[12] Y Jing. A neural network measuring the intersection of m-dimensional convex polyhedra (J). Automatica, 1995,31(4): 517~531.
[13] P. S Heckbert. Graphics Gems IV (M), Academic Press, Boston, 1994.
[14] [CP/OL]http://www.lindo.com/downloads/LAPI-WINDOWS-IA32-4.0.zip.
[15] K.P Bennett , O.L Mangasarian. Neural network training via linear programming(R). In PM Pardalos, editor, Advances in Optimization and Parallel Computing, p56-67. Elsevier Science Publishers BV, Amsterdam, 1992.
[1] E G Gilbert,C P Foo. Computing the distance between general convex objects in three-dimensional space [J]. IEEE Transactions on Robotics and Automation,1990,6(1):53-61.
[2] K A Sohna, B Jǘttler, M S Kim et al.Computing distances between surfaces using line geometry[C]. in: proceedings of IEEE the 10 th Pacific Conference on Computer Graphics and Applications, 2002: 236-245.
[3] C Lennerz, S schmoer. Efficient distance computation for quardratic curves and surfaces[C]. in:proceedings of the 2nd Conference on Geometric Modeling and Processing ,2002,60-69.
[4] C J Ong.Distance Computation between smooth convex objects[C]. In: proceedings of IEEE International Conference On Robotics and Automation, Minnesota, USA, 1996, 785-790.
[5] F Thomas, C Turnbullet al. Computing signed distances between free-form objects[C]. In: proceedings of the 2000 IEEE International Conference on Robotics and Automation, San Francisco, USA, 2000,3713-3718.
[6] C.Turnbull, S.Cameron..Computing distances between NURBS-defined convex objects[C]. in:proceedings of the 1998 IEEE International Conference on Robotics and Automation,Leuven, Belgium,1998,3685-3690.
[7] D E. Johnson, E Cohen. A framework for efficient minimum distance computations[C]. In: Proceedings of IEEE International Conference on Robotics and Automation, Leuven, Belgium, 1998, 3678-3684.
[8] 刘浩.NURBS 曲面最短距离[D].南京航天航空大学,硕士论文,2002.
[9] 席光,蔡永林.用改进遗传算法求取曲面间最小距离[J]. 计算机辅助设计与图形学学报, 2002, 14(3):209-213.
[10] 任红民,毕惟红,吴庆标.自由曲面之间最短距离的一种新的改进遗传算法[J].计算机工程与应用,2004,23,62-64.
[11] V Patoglu, R. B Gillespie. Extremal distance maintenance for parametric curves and surfaces[C]. In: proceedings of IEEE International Conference on Robotics and Automation, Washington DC,USA, 2002, 2817-2823.
[12] 熊范伦,邓超. 退火遗传算法及其应用[M],生物数学学报 2000,15(2):150-154.
[13] 何鑫,王昌全,李琼芳. 基于模拟退火遗传算法的土地利用结构优化模型[J].农业系统科学与综合研究,2004,20( 3): 215-27.
[14] 江娜,丁香乾,刘同义等.集装箱装载问题的模拟退火遗传算法[J].电子技术应用, 2005, 31(10) :14-16.
[2] A Gregory, M C Lin. Fast and accurate collision detection for haptic interaction using a three degree-of-freedom force-feedback device[J]. Computational Geometry: Theory and Applications, 2000,15(1): 69-89.
[3] P Jimenez, F Thomas. 3D collision detection: a survey[J]. Computers & Graphics, 2001, 25(2): 269-285.
[4] A Foisy,W Hayward.A safe swept volume method for collision detection[A].The 6th International Symposium of Robtics Research,Pittsburgh,PE,1993,61-68.
[5] M Herman.Fast three-dimensional collision free motion planning[C]. In: proceedings of the IEEE International Conference on Robotics and Automation,1986,2:1056-1063.
[6] A G-Alonso, N Serrano, J Flaquer. Solving the collision detection problem [J]. IEEE Computer Graphics and Applications 1994; 14(3): 36-43
[7] P.M.Hubbard, Approximating polyhedra with spheres for time-critical collision detection[J], ACM Transactions On Computer Graphics,1996, 15(3): 179-210.
[8] H Samet. Applications of spatial data structures: Computer Graphics, Image Processing, and GIS[M]. Addison-Wesley, Reading, MA, 1990.
[9] K Hamada, Y Hori.Octree-based approach to real-time collision-free path planning for robot manipulator [C]. In: ACM96-MIE, 1996,705-10.
[10] G Schaufler, W Stürzlinger.A three-dimensional image cache for virtual reality[C]. EUROGRAPH’96, 1996,227-236.
[11] S Zhou, B J Christopher. Design and implementation of multi-scale databases [C]. In: Proc. of the 7th Int’l Symp. on Advances in Spatial and Temporal Databases. London: Springer-Verlag, 2001,365-386.
[12] S.Ar, B Chazelle. Self-customized BSP trees for collision detection[J]. Computational Geometry, 2000,15, 91-102
[13] K Chung, W Wen Ping. Quick collision detection of Polytopes in virtual environments[C]. In: Proc. of the ACM Symposium on Virtual Reality Software and Technology. ACM Press, 1996:125-132.
[14] 李学庆,孟祥旭等 基于启发式搜索分离向量的凸多面体碰撞检测[J].计算机学报,2003,26(7):837-847.
[15] K.P Bennett , O.L Mangasarian. Neural network training via linear programming(R). In PM Pardalos, editor,Advances in Optimization and Parallel Computing, 56-67. Elsevier Science Publishers BV, Amsterdam, 1992.
[16] E Flato, D Haperin. Robust and efficient construction of planar Minkowski sums[D]. Masters thesis, Tel Aviv University, 2000.
[17] E Fogel, D Halperin. Exact Minkowski sums of convex polyhedra[C]. Symposium on Computational Geometry 2005: 382-383.
[18] G Varadhan, D Manocha. Accurate Minkowski sum approximation of polyhedral models[C]. In: Pacific Conference on Computer Graphics and Applications, IEEE Computer Society, 2004,392-401.
[19] A Kual,M O’Conor,V Srinivasan. Computing Minkowski sums of regular polygons[C]. In: proceedings 3rd Canadian Conference of Computational Geometry, 1991,74-77.
[20] P K Agarwal,E Flato,D Halperin.Polygon decomposition for efficient construction of Minkowski sums[J]. Computational Geometry: Theory and Applications, 2002, 21, 39-61.
[21] Xueqing Li, Yi-King Choi, Wenping Wang. Collision detection of convex polyhedra based on duality transformation[R]. Tech Report TR-2005-01, Department of Computer Science, Hongkong University, 2005.
[22] D.P. Dobkin , D.G. Kirkpatrick. Fast detection of polyhedral intersection [J]. Theoretical Computer Science, 1983,27(3): 241-253.
[23] B. Chazelle. Triangulating a simple polygon in linear time [J]. Discrete Computational Geometry, 1991,6(5):485-524.
[24] P K. Agarwal , M Sharir. Red-blue intersection detection algorithms with applications to motion planning and collision detection[J]. SIAM Journal of Computational, 1990,19:297-321.
[25] B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane[J]. J. Assoc. Comput. Mach., 1992,39(1):1-54.
[26] T M. Chan. A simple trapezoid sweep algorithm for reporting red/blue segment intersections[C]. In Proc. 6th Canad. Conf. Comput. Geom. 1994,263-268.
[27] J Basch, J Erickson. Kinetic collision detection between two simple polygons [J]. Computational Geometry: Theory and Applications .2004, 27(3): 211-235.
[28] J Hershberger,S Suri. A pedestrian approach to ray shooting: Shoot a ray; take a walk [J]. Journal of Algorithms, 1995,18:403~431.
[29] D.M. Mount. Intersection detection and separators for simple polygons[C]. In: Proc. 8th Annu. ACM Sympos. Comput. Geom., 1992, 303-311.
[30] S Ehmann , M C. Lin. Accurate and fast proximity queries between polyhedra using convex surface decomposition[C]. In: proceedings of Eurographics’2001, 2001,20(3): 500-510.
[31] M C Lin, D Manocha,M Ponamgi. Fast algorithms for penetration and contact determination between non-convex polyhedral models[C]. In: proceedings of IEEE International Conference on Robotics and Automation,1995,2707-2712.
[32] H S Kim,H Ko et al. A collision detection for interactive assembly simulation[C]. In: proceedings of the 1997 IEEE international Symposium Assembly and Task Planning, Marina del Rey, CA, 1997,170-175.
[33] Gino Van Den Bergen, Efficient Collision detection of complex deformable models using AABB-Trees [J]. Journal of Graphics Tools, 1997, 2(4): 1-13.
[34] S Gottschalk, M C Lin, D Manocha. OBBTree: A hierarchical structure for interference detection[C]. In: Computer Graphics Proceeding, SIGGRAPH’96, 1996, 171-180.
[35] P M Hubbard. Real-time collision detection and time-critical computing[C]. In: proceedings of the First ACM Workshop on Simulation and Interaction in Virtual Environments, 1995, 92-96.
[36] M Klosowski, J Held, J. Mitchell, Evaluation of collision detection methods for virtual reality fly-throughs[C]. In: proceedings of the Seventh Canadian Conference on Computer Geometry, 1995, 3,205-210.
[37] S. Ehmann, M.C. Lin. Accurate and fast proximity queries between polyhedra using convex surface decomposition[C]. Comput. Graph. Forum. 2001, 20(3): 500-510.
[38] P Terdiman. Memory-optimized bounding-volume hierarchies [DB/OL].http://www.codercorner.com/Opcode.htm, 2001.
[39] E. Larsen, S Gottschalk, M. Lin, and D. Manocha. Fast proximity queries with swept sphere volumes[R]. Technical Report TR99-018, Department of Computer Science, University of North Carolina, 1999.
[40] S. Krishnan, A. Pattekar, M. Lin, and D. Manocha. Spherical shell: A higher order bounding volume for fast proximity queries[C]. In: Proc. 3rd Internat. Workshop Algorithmic Found. Robot. , 1998, 122-136.
[41] S. Cameron , R.K. Culley. Determining the minimum translational distance between two convex polyhedra[C]. In: proceedings of IEEE International Conference on Robotics and Automation,1986, 591-596.
[42] D. Dobkin, J. Hershberger et al. Computing the intersection-depth of polyhedra [J].Algorithmica, 1993, 9:518-533.
[43] E.G. Gilbert, D.W. Johnson, and S.S. Keerthi. A fast procedure for computing the distance between objects in three-dimensional space [J]. IEEE Journal of Robotics and Automation. 1988, RA-4: 193-203.
[44] C J Ong, E G. Gilbert. The Gilbert–Johnson–Keerthi distance algorithm: a fast version for incremental motions. In: proceeding of IEEE International Conference on Robotics and Automation, Albuquerque, Mexico, USA, 1997,1183~1189.
[45] S. Cameron. Enhancing GJK: Computing minimum and penetration distance between convex polyhedra[C]. In: proceedings of IEEE International Conference on Robotics and Automation, 1997, 3112-3117.
[46] G Bergen. A Fast and Robust GJK Implementation for Collision Detection of Convex Objects[J]. Journal of Graphics Tools, 1999,4(2): 7-25.
[47] G Bergen. Proximity queries and penetration depth computation on 3D game objects[C]. In: Proc. Game Developers Conf., 2001.
[48] M.C. Lin, J.F. Canny. Efficient algorithms for incremental distance computation[C]. In: proceedings of IEEE International Conference on Robotics and Automation, 1991, 1008-1014.
[49] L. Guibas, D. Hsu, and L. Zhang. H-Walk: Hierarchical distance computation for moving convex bodies[C]. In: Proc. 15th Annu. ACM Sympos. Comput. Geom., 1999, 265-273.
[50] S. Ehmann, M.C. Lin. Accelerated proximity queries between convex polyhedra using multi-level Voronoi marching[C]. In: Proc. IEEE/RSJ Internat. Conf. Intell. Robots Sys. , 2000, 2101-2106.
[51] M K Ponamgi, D Manocha et al. Incremental algorithms for collision detection between solid models[C]. In: Proc. ACM/Siggraph Symposium on Solid Modeling, 1995, 293-304.
[52] B. Mirtich. V-Clip: Fast and robust polyhedral collision detection [J]. ACM Trans. Graph., 1998, 17:177-208.
[53] J E. Bobrow. A direct minimization approach for obtainingthe distance between convex polyhedra[J]. International Journal of Robotics Research, 1989,8(3): 65-76.
[54] O Ma,M Nahon. A general method for computing the distance between convex polyhedra[C]. In: proceedings of ASME Conference on Advances in Design and Automation,1992,1(Pheonix,Arizona,USA),109-117.
[55] E.G. Gilbert , C.J. Ong. New distances for the separation and penetration of objects[C]. In: proceedings of IEEE International Conference on Robotics and Automation, 1994, 579-586.
[56] C J Ong, E Huang. An incremental version of growth distance[C]. In: proceedings of the IEEE International Conference On Robotics and Automation. Leuven, Belgium, 1998, 3671-3677.
[57] C J Ong, E Huang, S M Hong. A fast growth distance algorithm for incremental motions[J]. IEEE Transactions On Robotics and automation, 2000, 16( 6):880-890.
[58] S M Hong, J H Yeo. A fast procedure for computing incremental growth distances[J]. Robotica, 2000,18(4): 429-441.
[59] Y Jing. A neural network measuring the intersection of m-dimensional convex polyhedra (J). Automatica, 1995,31(4): 517-531.
[60] Y.J Kim, M .C Lin, D Monocha. Incremental penetration depth estimation between convex polytopes using dual-space expansion [J]. IEEE Transactions on Visualization and Computer Graphics, 2004,10(2): 152-163.
[61] P. Agarwal, L.J. Guibas et al. Penetration depth of two convex polytopes[C]. In 3rd. Nordic J. Computing, 2000,7:227-240.
[62] K Sridharan, S.S Keerthi. Computation of a penetration measure between 3D convex polyhedral objects for collision detection [J]. Journal of Robotic Systems, 2001(18): 623-631.
[63] 朱向阳,丁汉等.凸多面体之间的伪最小平移距离—Ⅰ.定义及其性质(J). 中国科学(E 辑), 2001, 31(2):128-136.
[64] Shih Ching-Long, Liu Jane-Yu. Computing the minimum directed distances between convex polyhedra (J). Journal of Information Science and Engineering, 1999,15(3): 353-373.
[65] F Chin,C A Wang.Optimal algorithms for the intersection and the minimum distance problem beteen planar polygons[J].IEEE Transactions on Computers,1983,C-32(12):1203-1207.
[66] N M Amato. Determining the separation of simple polygons[J]. International Journal of Computational Geometry & Applications, 1994, 4(4): 457-474.
[67] B. Chazelle. Triangulating a simple polygon in linear time. Discrete Comput. Geom.[J]. 1991(6): 485-524.
[68] LJ Guibas and R. Seidel, Computing Convolutions by Reciprocal Search[C]. Symposium. of Computational Geometry, 2001.
[69] S Quinlan.Efficient distance computation between non-convex objects[C]. In: proceedings of International Conference on Robotics and Automation, 1994, 3324-3329.
[70] D E. Johnson, E Cohen. A framework for efficient minimum distance computations[C]. In: Proceedings of IEEE International Conference on Robotics and Automation, Leuven, Belgium, 1998, 3678-3684.
[71] D E. Johnson, E Cohen. Bound coherence for minimum distance computations[C]. In: Proceedings of IEEE International Conference on Robotics and Automation, 1999,1843-1848.
[72] K Kawachi, H Suzuki. Distance computation between non-convex polyhedra at short range based on discrete Voronoi regions[C]. In: Proceedings of IEEE Geometric Modeling and Processing, Hong Kong, 2000,123-128.
[73] J A Carretero, M A Nahon et al. Solving distance problems with concave bodies using simulated annealing[C]. In: proceedings of the 2001 IEEE/RSI International Conference on Intelligent Robotics and Systems, Maui, Hawaii, USA, 2001,3:1507-1512.
[74] Y J. Kim, M A Otaduy et al. Fast penetration depth computation using rasterization hardware and hierarchical refinement[R]. UNC-CH Technical Report TR02-014,2002.
[75] Y.J Kim, M. A Otaduy et al. Fast penetration depth computation for physically-based animation [A]. In: Proceeding of ACM SIGGRAPH Symposium on Computer Animation[C], New York, USA, ACM Press, 2002, 23-32.
[76] A Hoff, A Zaferakis et al. Fast and simple geometric proximity queries using graphics hardware[C].in: proceedings of 2001 ACM Symposium on Iteractive 3D Graphics,2001, 145-148.
[77] B Heidelberger, M Teschner. Consistent penetration depth estimation for deformable collision response. In: Proc. Vision. Modeling, Visualization, 2004, 339-346.
[78] C J Ong.Distance Computation between smooth convex objects[C]. In: proceedings of IEEE International Conference On Robotics and Automation, Minnesota, USA, 1996, 785-790.
[79] E G Gilbert,C P Foo. Computing the distance between general convex objects in three-dimensional space [J]. IEEE Transactions on Robotics and Automation,1990,6(1):53-61.
[80] G J Hamlin,R B Kelley et al. Efficient distance calculation using the spherically-extended polytope(S-tope) model[C].In: proceedings of the 1992 IEEE International Conference on Robotics and Automation, Nice ,France,1992,2502-2507.
[81] J Tornero. Spherical-object representation and fast distance computation for robotics applications[C]. In: proceedings of IEEE International Conference on Robotics and Automation, Sacramento, California, USA, 1991,1601-1608.
[82] E J. Bernabeu, J Tornero. Hough transform for distance computation and collision avoidance [J]. IEEE Transactions on Robtics and Automation,2002,18(3):393-398.
[83] C Turnbull, S Cameron. Computing Distances Between NURBS-defined Convex Objects[C].in:proceedings of the 1998 IEEE International Conference on Robotics and Automation,Leuven, Belgium,1998,3685-3690.
[84] V Patoglu, R.B.Gillespie. Extremal distance maintenance for parametric curves and surfaces[C]. In: proceedings of IEEE International Conference on Robotics and Automation, Washington DC,USA, 2002, 2817-2823.
[85] F Thomas, C Turnbullet al. Computing signed distances between free-form objects[C]. In: proceedings of the 2000 IEEE International Conference on Robotics and Automation, San Francisco, USA, 2000,3713-3718.
[86] 刘浩.NURBS 曲面最短距离[D].南京航天航空大学,硕士论文,2002.
[87] 席光,蔡永林.用改进遗传算法求取曲面间最小距离[J]. 计算机辅助设计与图形学学报, 2002, 14(3):209-213.
[88] 任红民,毕惟红,吴庆标.自由曲面之间最短距离的一种新的改进遗传算法[J].计算机工程与应用, 2004, 23,62-64.
[89] J Rossignac, A Megahed, B.O Schneider. Interactive inspection of solids: cross-section and interferences. Computer Graphics, 1992, 26(2): 353~360.
[90] M Shinya, M Forgue. Interference detection through rasterization. Journal of Visualization and Computer Animation, 1991, 2:131~134.
[91] K Myszkowski, OG Okunev, TL Kunii. Fast collision detection between computer solids using rasterizinggraphics hardware. The Visual Computer, 1995, 11:497~511.
[92] G Baciu, SKW Wong, H Sun. RECODE: An image-based collision detection algorithm, Journal of Visualization and Computer Animation, 1999, 10(4): 181~192.
[93] NK Govindaraju, S Redon, MC Lin, D Manocha. CULLIDE: Interactive collision detection between complex models in large environments using graphics hardware. In Proc. ACM SIGGRAPH/Eurographics Workshop Graphics Hardware, 25-32, 2003.
[94] T Vassilev, B Spanlang, Y Chrysanthou. Fast cloth animation on walking avatars. Computer Graphics Forum, 2001, 20(3):260–267.
[95] KE Hoff III, A Zaferakis, MC Lin etal. Fast 3D geometric proximity queries between rigid and deformable models using graphics hardware acceleration. points at which edges intersect objects.Technical Report TR02-004, Department of Computer Science, University of North Carolina at Chapel Hill, 2002.
[96] B Heidelberger, M Teschner, M Gross. Volumetric collision detection for derformable objects. TR395 in Computer Science Department ETH Zurich, Switzerland, 2003.
[97] 范昭玮. 实时碰撞检测技术研究[D].浙江大学博士论文,2003.
[98] GT.Toussaint.Solving geometric problems with the rotating calipers[C].in: Proceedings of IEEE MELECON'83, Athens, Greece, 1983, A10.02/1-4.
[99] [CP/OL]http://www.lindo.com/downloads/LAPI-WINDOWS-IA32-4.0.zip.
[1] M.C Lin, J. F Canny. A fast algorithm for incremental distance calculation[C].In: Proceedings of IEEE International conference on Robotics and Automation, Sacramento, USA, 1991: 1008-1014.
[2] E.G Gilbert, D.W Johnson, S.S.Keerthi A fast procedure for computing the distance of complex objects in three-dimensional Space[J]. IEEE Journal of Robotics and Automation. 1998,4(2): 193-203.
[3] B. Mirtich. V-Clip: Fast and robust polyhedral collision detection [J]. ACM Trans. Graph., 1998, 17:177-208.
[4] S Cameron. Enhancing GJK: compute minimum and penetration distance between convex polyhedra[C]. In: Proceedings of IEEE International Conference on Robotics and Automation, Albuquerque, USA, 1997: 3112-3117.
[5] C J Ong , E G. Gilbert. The Gilbert–Johnson–Keerthi distance algorithm:a fast version for incremental motions. In: proceeding of IEEE International Conference on Robotics and Automation, Albuquerque, Mexico, USA, 1997,1183~1189.
[6] G. van Bergen, Proximity queries and penetration depth computation on 3D game objects [C]. In: Proceedings of Game Developers Conference, San Jose, USA,2001: 821-837.
[7] E.G. Gilbert , C.J. Ong. New distances for the separation and penetration of objects[C]. In: proceedings of IEEE International Conference on Robotics and Automation, 1994, 579-586.
[8] Y.J Kim, M.A Otaduy, M.C Lin. Fast penetration depth computation using rasterization hardware and hierarchical refinement[R]. Technical Report, UNC-Chapel Hill TR02-014, 2002.
[9] Y.J Kim, M. A Otaduy, M.C Lin. Fast penetration depth computation for physically-based animation [A]. In: Proceeding of ACM SIGGRAPH Symposium on Computer Animation[C], New York, USA, ACM Press, 2002, 23-32.
[10] Y.J Kim, M .C Lin, D Monocha. Incremental penetration depth estimation between convex polytopes using dual-space expansion[J]. IEEE Transactions on Visualization and Computer Graphics, 2004,10(2): 152-163.
[11] F.P. Preparata, M.I.Shamos. Computational geometry: An Introduction [M]. Springer-Verlag, New York, 1985.
[12] P.J Schneider, D.H Eberly. 计算机图形学几何工具算法祥解[M].周长发译.电子工业出版社,北京,2005.
[1] B. Chazelle. Triangulating a simple polygon in linear time[J]. Discrete Computational Geometry, 1991,6:485-524.
[2] D.M. Mount. Intersection detection and separators for simple polygons[C]. In: Proc. 8th Annu. ACM Sympos. Comput. Geom., 1992, 303-311.
[3] Gino Van Den Bergen, Efficient Collision detection of complex deformable models using AABB-Trees [J]. Journal of Graphics Tools, 1997, 2(4): 1-13.
[4] S Gottschalk, M C Lin, D Manocha. OBBTree: A Hierarchical Structure for Interference Detection[C]. In: Computer Graphics Proceeding, SIGGRAPH’96, 1996, 171-180.
[5] M Klosowski, J Held, J. Mitchell, Evaluation of collision detection methods for virtual reality fly-throughs[C]. In: proceedings of the Seventh Canadian Conference on Computer Geometry, 1995, 3,205-210.
[6] S. Ehmann, M.C. Lin. Accurate and fast proximity queries between polyhedra using convex surface decomposition[C]. Comput. Graph. Forum. 2001, 20(3): 500-510.
[7] S. Ehmann and M C Lin. Accurate and fast proximity queries between polyhedra using convex surface decomposition[C]. In: proceedings of Eurographics’2001, 2001,20(3): 500-510.
[8] M C Lin,D Manocha,M Ponamgi. Fast algorithms for penetration and contact determination between non-convex polyhedral models[C]. In: proceedings of IEEE International Conference on Robotics and Automation,1995,2707-2712.
[9] H S Kim,H Ko et al. A collision detection for interactive assembly simulation[C]. In: proceedings of the 1997 IEEE international Symposium Assembly and Task Planning, Marina del Rey, CA, 1997,170-175.
[10] P.K. Agarwal , M. Sharir. Red-blue intersection detection algorithms with applications to motion planning and collision detection[J]. SIAM Journal of Computational, 1990,19:297-321.
[11] B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane[J]. J. Assoc. Comput. Mach., 1992,39:1-54.
[12] K. Mulmuley. A fast planar partition algorithm[C]. In: Proceedings of the IEEE 29th Foundations of Computer Science, New York, 1988, 580-589.
[13] T M?ller .A fast triangle-triangle intersection test [J]. Journal of Graphics Tools, 1997,2(2): 25-30.
[14] U Manber 著,黄林鹏译.算法引论:一种创造性方法[M].北京:电子工业出版社,2005.
[1] F Chin,C A Wang.Optimal algorithms for the intersection and the minimum distance problem beteen planar polygons[J].IEEE Transactions on Computers,1983,C-32(12):1203-1207.
[2] N M Amato. Determining the separation of simple polygons[J]. International Journal of Computational Geometry & Applications, 1994, 4(4): 457-474.
[3] S Quinlan.Efficient distance computation between non-convex objects[C]. In: proceedings of International Conference on Robotics and Automation, 1994, 3324-3329.
[4] D E. Johnson , E Cohen. A framework for efficient minimum distance computations[C]. In: Proceedings of IEEE International Conference on Robotics and Automation, Leuven, Belgium, 1998, 3678-3684.
[5] 杨春成,张清浦,田向春等.顾及几何形状相似性的简单多边形最近距离计算方法[J].测绘学报, 2000,32(4): 311-318.
[6] K Kawachi , H Suzuki. Distance Computation between non-convex polyhedra at short range based on discrete Voronoi regions[C]. In: Proceedings of IEEE Geometric Modeling and Processing, Hong Kong, 2000,123-128.
[7] G.T. Toussaint.Solving geometric problems with the rotating calipers[C]. in:Proceedings of IEEE MELECON'83, Athens, Greece, 1983, A10.02/1-4.
[8] F.P. Preparata, M.I.Shamos. Computational geometry: An Introduction [M]. Springer-Verlag, New York, 1985.
[1] S. Cameron , R.K. Culley. Determining the minimum translational distance between two convex polyhedra[C]. In: proceedings of IEEE International Conference on Robotics and Automation,1986, 591-596.
[2] K. Sridharan S S. Keerthi. Computation of a penetration measure between 3D convex polyhedral objects for collision detection[J]. Journal of Robotic Systems, 2001(18): 623-631.
[3] D. Dobkin, J. Hershberger et al. Computing the intersection-depth of polyhedra [J].Algorithmica, 1993, 9:518-533.
[4] B Heidelberger, M Teschner. Consistent penetration depth estimation for deformable collision response. In: Proc. Vision. Modeling, Visualization, 2004 , 339-346,
[5] M. de Berg, M. van Kreveld, M. Overmars and O. Schwarzkopf. Computational Geometry, Algorithms and Applications[M], 2nd edition, Springer-Verlag, Berlin, 2000.
[6] E. Flato, D. Haperin. Robust and efficient construction of planar Minkowski sums[D]. Masters thesis, Tel Aviv University, 2000.
[7] G Varadhan, D Manocha. Accurate Minkowski sum approximation of polyhedral models[C]. In: Pacific Conference on Computer Graphics and Applications, IEEE Computer Society, 392-401
[8] Y J. Kim, M A Otaduy. Fast penetration depth computation using rasterization hardware and hierarchical refinement[R]. UNC-CH Technical Report ,TR02-014,2002.
[9] GT..Toussaint.Solving geometric problems with the rotating calipers[C]. in:Proceedings of IEEE MELECON'83, Athens, Greece, 1983, A10.02/1-4
[10] F.P. Preparata, M.I.Shamos. Computational geometry: An Introduction [M]. Springer-Verlag, New York, 1985.
[1] S.A Cameron, R.K Cully. Determining the minimum translation distance between two convex polyhedra(C), In: Proceeding of IEEE International Conference of Robot and Automations[C], San Francisco, CA, USA, 1986:591-596.
[2] M.C Lin, J.F Canny. Fast algorithm for incremental distance calculation(C), In: Proceeding of IEEE International Conference On Robotics and Automation, Sacramento, CA, USA, 1991:1008-1014.
[3] E.G Gilbert, D.W. Johnson, S.S. Keerthi. A Fast Procedure for computing the distance between complex objects in three-dimensional space (J). IEEE Journal of Robotics and Automation, 1988, 4(2): 193-203.
[4] Gino VAN Den Bergen. A fast and robust GJK implementation for collision detection of convex objects (J). Journal of Graphics Tools, 1999,4(2): 7-25.
[5] Y. J Kim, M.A Otaduy, M.C Lin. Fast penetration depth computation using rasterization hardware and hierarchical refinement[R]. Technical report, UNC-Chapel Hill TR02-014, Department of Computer Science, University of North Carolina, USA, North Carolina, Chapel Hill, 2002.
[6] Y.J Kim, M. A Otaduy, M.C Lin. Fast penetration depth computation for physically-based animation [A]. In: Proceeding of ACM SIGGRAPH Symposium on Computer Animation[C], New York, USA, ACM Press, 2002, 23-32.
[7] Y.J Kim, M .C Lin, D Monocha. Incremental penetration depth estimation between convex polytopes using dual-space expansion [J]. IEEE Transactions on Visualization and Computer Graphics, 2004,10(2): 152-163.
[8] 朱向阳,丁汉,熊有伦.凸多面体之间的伪最小平移距离—Ⅰ.定义及其性质(J). 中国科学(E 辑), 2001, 31(2):128~136.
[9] C.J Ong. A fast growth distance algorithm for incremental motions (J). IEEE Transactions On Robotics and Automation, 2000, 16(6): 880-890.
[10] K Sridharan. Efficient computation of a measure of depth between convex objects for graphics applications (J). Computers & Graphics, 2002,26(5): 785-793.
[11] SHIH CHING-LONG, LIU JANE-YU. Computing the minimum directed distances between convex polyhedra (J). Journal of Information Science and Engineering, 1999,15(3): 353-373.
[12] Y Jing. A neural network measuring the intersection of m-dimensional convex polyhedra (J). Automatica, 1995,31(4): 517~531.
[13] P. S Heckbert. Graphics Gems IV (M), Academic Press, Boston, 1994.
[14] [CP/OL]http://www.lindo.com/downloads/LAPI-WINDOWS-IA32-4.0.zip.
[15] K.P Bennett , O.L Mangasarian. Neural network training via linear programming(R). In PM Pardalos, editor, Advances in Optimization and Parallel Computing, p56-67. Elsevier Science Publishers BV, Amsterdam, 1992.
[1] E G Gilbert,C P Foo. Computing the distance between general convex objects in three-dimensional space [J]. IEEE Transactions on Robotics and Automation,1990,6(1):53-61.
[2] K A Sohna, B Jǘttler, M S Kim et al.Computing distances between surfaces using line geometry[C]. in: proceedings of IEEE the 10 th Pacific Conference on Computer Graphics and Applications, 2002: 236-245.
[3] C Lennerz, S schmoer. Efficient distance computation for quardratic curves and surfaces[C]. in:proceedings of the 2nd Conference on Geometric Modeling and Processing ,2002,60-69.
[4] C J Ong.Distance Computation between smooth convex objects[C]. In: proceedings of IEEE International Conference On Robotics and Automation, Minnesota, USA, 1996, 785-790.
[5] F Thomas, C Turnbullet al. Computing signed distances between free-form objects[C]. In: proceedings of the 2000 IEEE International Conference on Robotics and Automation, San Francisco, USA, 2000,3713-3718.
[6] C.Turnbull, S.Cameron..Computing distances between NURBS-defined convex objects[C]. in:proceedings of the 1998 IEEE International Conference on Robotics and Automation,Leuven, Belgium,1998,3685-3690.
[7] D E. Johnson, E Cohen. A framework for efficient minimum distance computations[C]. In: Proceedings of IEEE International Conference on Robotics and Automation, Leuven, Belgium, 1998, 3678-3684.
[8] 刘浩.NURBS 曲面最短距离[D].南京航天航空大学,硕士论文,2002.
[9] 席光,蔡永林.用改进遗传算法求取曲面间最小距离[J]. 计算机辅助设计与图形学学报, 2002, 14(3):209-213.
[10] 任红民,毕惟红,吴庆标.自由曲面之间最短距离的一种新的改进遗传算法[J].计算机工程与应用,2004,23,62-64.
[11] V Patoglu, R. B Gillespie. Extremal distance maintenance for parametric curves and surfaces[C]. In: proceedings of IEEE International Conference on Robotics and Automation, Washington DC,USA, 2002, 2817-2823.
[12] 熊范伦,邓超. 退火遗传算法及其应用[M],生物数学学报 2000,15(2):150-154.
[13] 何鑫,王昌全,李琼芳. 基于模拟退火遗传算法的土地利用结构优化模型[J].农业系统科学与综合研究,2004,20( 3): 215-27.
[14] 江娜,丁香乾,刘同义等.集装箱装载问题的模拟退火遗传算法[J].电子技术应用, 2005, 31(10) :14-16.