虚拟现实中碰撞检测技术的研究
|
摘要
实时碰撞检测是虚拟现实中一个非常关键的问题,其基本任务是确定两个或多个物体彼此之间是否发生接触、接触面积大小和穿透的深度。尽管针对碰撞检测已有了大量有价值的研究成果,但随着人们对交互实时性、场景真实性要求的不断提高,碰撞检测技术所面临的问题也日益突出,其中最核心的问题是如何有效地提高碰撞检测的速度。本文对碰撞检测相关技术进行了深入的研究,主要包括以下几个方面的内容:
首先,从图形硬件发展的历史开始,介绍和分析最新GPU在通用计算方面的应用及其技术原理和发展状况。
然后,对目前现有的碰撞检测算法进行了分类归纳,同时总结了一般碰撞检测算法所采用的总体框架,并着重介绍与分析了基于层次包围体树和基于图像空间的碰撞检测算法。
在此基础上,本文提出了一种基于GPU的对参数化表面的碰撞检测方法。通过使用几何图像表示的参数化表面,可以实时的生成GPU优化的包围体层次结构,然后在这个层次结构的基础上实现优化的基于GPU的层次碰撞检测算法。结果显示本方法可以有效的提高碰撞检测的速度。
Real time collision detection is one of the most important problems in the fields of virtual reality. Its fundamental task is to detect whether there are contacts or penetrations between two or among multiple objects. While, there have been many research achievements on solving the problem of collision detection, this problem is better to be solved with the more high demands of real time interactivity and realistic simulation of motions of virtual objects thereafter. This paper studies the technique of collision detection deeply. It contains the following parts:
Firstly, starting from a brief introduction to some historical events on graphics hardware development, a detail introduction and analysis will be given to the technique and the latest development of GPU for general purpose computations.
Secondly, this thesis reviews recent researches on collision detection and summarizes the general framework of a collision detection algorithm. Then it focuses on introducing and analyzing the collision detection algorithms based on bounding volume hierarchy and image space.
Finally, base on the above contents, the thesis describe a GPU-based collision detection method for parameterized surfaces by geometry images allows to generate GPU-optimized bounding volume hierarchies in real-time that serve as a basis for an optimized GPU-based hierarchical collision detection algorithm. The experimental results show that our method is faster than the CPU-based method.
首先,从图形硬件发展的历史开始,介绍和分析最新GPU在通用计算方面的应用及其技术原理和发展状况。
然后,对目前现有的碰撞检测算法进行了分类归纳,同时总结了一般碰撞检测算法所采用的总体框架,并着重介绍与分析了基于层次包围体树和基于图像空间的碰撞检测算法。
在此基础上,本文提出了一种基于GPU的对参数化表面的碰撞检测方法。通过使用几何图像表示的参数化表面,可以实时的生成GPU优化的包围体层次结构,然后在这个层次结构的基础上实现优化的基于GPU的层次碰撞检测算法。结果显示本方法可以有效的提高碰撞检测的速度。
Real time collision detection is one of the most important problems in the fields of virtual reality. Its fundamental task is to detect whether there are contacts or penetrations between two or among multiple objects. While, there have been many research achievements on solving the problem of collision detection, this problem is better to be solved with the more high demands of real time interactivity and realistic simulation of motions of virtual objects thereafter. This paper studies the technique of collision detection deeply. It contains the following parts:
Firstly, starting from a brief introduction to some historical events on graphics hardware development, a detail introduction and analysis will be given to the technique and the latest development of GPU for general purpose computations.
Secondly, this thesis reviews recent researches on collision detection and summarizes the general framework of a collision detection algorithm. Then it focuses on introducing and analyzing the collision detection algorithms based on bounding volume hierarchy and image space.
Finally, base on the above contents, the thesis describe a GPU-based collision detection method for parameterized surfaces by geometry images allows to generate GPU-optimized bounding volume hierarchies in real-time that serve as a basis for an optimized GPU-based hierarchical collision detection algorithm. The experimental results show that our method is faster than the CPU-based method.
引文
[1]A Smith,Y Kitamura,H Takemura,et al.A Simple and Efficient Method for Accurate Collision Detection among Deformable Polyhedral Objects in Arbitrary Motion.The IEEE Virtual Reality Annual International Symposium,1995,2:136-145
[2]Bergen.Efficient Collision Detection of Collision Deformable Models using AABB Trees.Journal of Graphics Tools,1997,2(4):1-14
[3]Yashifumi Kitamura,Andrew Smith,Haruo Takemura.A Realtime Algorithm for Accurate Collision Detection for Deformable Polyhedral Objects Presence Vol7.No.1 February 1998:36-52
[4]J Mezger,S Kimmerle,O Etzmub.Hierarchical Techniques in Collision Detection for Cloth Animation.Journal of WSCG11,2003,2:322-329
[5]Matthias Teschner,Bruno Heideleberger,Matthias Muller,et al.Optimized Spatial Hashing for Collision Detection of Deformable Objects Munish,Germany,Novermber,2003:19-21
[6]魏迎梅.虚拟环境中碰撞检测问题的研究:[博士学位论文].长沙:国防科技大学,2000
[7]范昭炜.实时碰撞检测技术研究:[博士学位论文].杭州:浙江大学,2003
[8][1]吴恩华,柳有权.基于图形处理器(GPU)的通用计算.计算机辅助设计与图形学学报,2004,16(5):601-612
[9]Clark James H.The geometry engine:A VLSI geometry system for graphics [A].In:Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH,Boston,1982.127-133
[10]Fuchs Herry,Poulton John.Pixel-planes:A VLSI-Oriented design for a raster graphics engine[J].VLSI Design,1981,2(3):20-28
[11]Eyles John,Austin John,Fuchs Henry,et al.Pixel-plane 4:A summary,advances in computer graphics hardware Ⅱ[A].Eurographic Seminars Tutorials and Perspectives in Computer Graphics,New York:Springer-Verlag,1988.183-208
[12]Fuchs Herry,Israel Laura,Poulton John,et al.Pixel-plane 5:A heterogeneous multiprocessor graphics system using processor-enhanced memories[A].In:Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH,Boston,1989.79-88
[13]Joao Luiz Dihl Comba,Dietrich Carlos A,Pagot Christian A,et al.Computation on GPUs:From a programmable pipeline to an efficient stream processor[J].Revista de Informatica Teoricae Aplicada,2003,X(2):41-70
[14]Kruger Jens,Westermann Rudiger.Linear algebra operators for GPU implementation of numerical algorithms[J].ACM Transactions on Graphics,2003,22(3):908-916
[15]Macedonia Michael.The GPU enters computing's mainstream[J].Computer,2003,36(10):106-108
[16]Venkatasubramanian Suresh.The graphics card as a stream computer[OL].
[17]Cohen Michael F,Chen Shenchang Eric,Wallace John R,et al.Aprogressive refinement approach to fast radiosity image generation[A].In:Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH,Atlanta,1988.75-84
[18]Lindholm Erik,Kilgard Mark J,Moreton Henry.A user-programmable vertex engine[A].In:Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH,Los Angeles,2001.149-158
[19]Harris Mark J,Coombe Greg,Scheuermann Thorsten,et al.Physically-based visual simulation on graphics hardware[A].In:Proceedings of Graphics Hardware,Saarbruchen,2002.109-118
[20]Bolz Jeff,Farmer Ian,Grinspun Eitan,et al.Sparse matrix solvers on the GPU:Conjugate gradients and multigrid[J].ACM Transactions on Graphics,2003,22(3):917-924
[21]Goddnight Nolan,Woolley Cliff,Luebke David,et al.A multigrid solver for boundary value problems using programmable graphics hardware[A].In:Proceedings of Graphics Hardware,San Diego,2003,102-111
[22]Hillesland Karl E,Molinov Sergey,Grzeszczuk Radek.Nonlinear optimization framework for image-based modeling on programmable graphics hardware[J].ACM Transactions on Graphics,2003,22(3):925-934
[23]吴恩华,柳有权.基于图形处理器(GPU)的通用计算[J].计算机辅助设计与图形学学报,2004,16(5):601-612
[24]吴恩华.图形处理器用于通用计算的技术、现状及其挑战.软件学报,2004,15(10):1493-1504
[25]张杨,诸昌铃,何太军.图形硬件通用计算技术的应用研究.计算机应用,2005,25(9):2192-2195
[26]Carr Nathan A,Hall Jesse D,Hart John C.The ray engine[A].In:Proceedings of Graphics Hardware,Saarbrucken,2002.37-46
[27]Purcell Timothy J,Donner Craig,Cammarano Mike,et al.Photon mapping on programmable graphics hardware[A].In:Proceedings of Graphics Hardware,San Diego,2003,41-50
[28]Hopf Matthias,Ertl Thomas.Accelerating 3D convolution using graphics hardware[A].In:Proceedings of IEEE Visualization,San Francisco,1999.471-474
[29]Hopf Matthias,Ertl Thomas.Hardware accelerated wavelet transformations [A].In:Proceedings of EG/IEEE TCVG Symposium on Visualization VisSym,Netherlands,2000.93-103
[30]Govindaraju Naga,Redon Stephane,Lin Ming C,et al.CULLIDE:Interactive collision detection between complex models in large environments using graphics hardware[A].In:Proceedings of Graphics Hardware,San Diego,2003,25-32
[31]Govindaraju Naga,Sud Avneesh,Yoon Sung-Eui,et al.Parallel occlusion culling for interactive walkthroughs using multiple GPUs[R].Carolina:University of North Carolina at Chapel Hill.UNC Computer Science Technical Report TR02-027,2002
[32]Wei Xiaoming,Zhao Ye,Fan Zhe,et al.Blowing in the wind[A].In:Proceedings of SIGGRAPH/Eurographics Symposium on Computer Animation,San Diego,2003.75-85
[33]Harris Mark J,Coombe Greg,Scheuermann Thorsten,et al.Simulation of cloud dynamics on graphics hardware[A].In:Proceedings of Graphics Hardware,Saarbrucken,2003.92-101
[34]Harris Mark J.Real-time cloud simulation and rendering[D].Chapel Hill:The University of North Carolina,2003
[35]Kim Theodore,Lin Ming C.Visual simulation of ice crystal growth[A].In:Proceedings of SIGGRAPH/Eurographics Symposium on Computer Animation,San Diego,2003.86-97
[36]李学庆.凸体碰撞检测问题的研究:[博士学位论文],济南:山东大学,2002
[37]徐春蕾.虚拟仿真环境中碰撞检测技术的研究与应用:[博士学位论文],长沙:国防科学技术大学,2000
[38]Cohen J,Lin MC,Manocha D,et al.I-COLLIDE:An interactive and exact collision detection system for large-scale environments.In Proceedings of ACM Interactive 3D Graphics Conference,Monterey,CA,USA,1995:189-196.
[39]Lin MC.Efficient Collision Detection for Animation and Robotics.Ph.D.Thesis,University of California,Berkeley,1993
[40]Andrew Witkin,David Baraff,Physically Based Modeling.Course 25 notes at SIGGRAPH 2001.
[41]Zachmann G.Optimizing the collision detection pipeline.In Proceedings of the First International Game Technology Conference(GTEC),Hong Kong,18-21January 2001
[42]Gottschalk S,Lin M,Manocha D.OBB-Tree:A Hierarchical Structure for Rapid Interference Detection.the Proceedings of ACM S IGGRAPH'96,1996:171-180
[43]Moller J,Goldman R.Combining algebraic rigor with geometric robustness for the detection and calculation of conic sections in the intersection of two quadric surfaces.In Proceedings of ACM Solid Modeling,1991:221-233
[44]Lin MC,Canny J.Efficient algorithms for incremental distance computation.In Proceedings of the IEEE International Conference on Robotics and Automation.1991:1008-1014
[45]Gilbert EG,Johnson DW,Keerthi SS.A fast procedure for computing the distance between objects in three-dimensional space.IEEE Journal on Robotics and Automation,1988,4:193-203
[46]Larsson T,Moller TA.Collision detection for continuously deforming bodies.In Proceedings of Eurographics'2001,2001,325-333
[47]Palmer I,Grimsdale R.Collision detection for animation using Sphere-Trees.Computer Graphics Forum,1995,14(2):105-116
[48]Hubbard PM.Real-time collision detection and time-critical computing.In SIVE 95, The First Workshop on Simulation and Interaction in Virtual Environments, Iowa City, Iowa. University of Iowa, informal proceedings, 1995,1:92-96
[49] Klosowski J, Held M, Mitchell JSB, et al. Efficient collision detection using bounding volume hierarchies of k-DOPs. IEEE Transaction On Visualization and Computer Graphics, 1998,4(1): 21-37
[50] Rossignac J, Megahed A. Schneider BO. Interactive inspection of solids: cross-section and interferences. Computer Graphics, 1992,26(2): 353-360
[51] Myszkowski K, Okunev OG, Kunii TL. Fast collision detection between computer solids using rasterizing graphics hardware. The Visual Computer, 1995,11:497-511
[52] Baciu G, Wong SKW, Sun H. RECODE: An image-based collision detection algorithm, Journal of Visualization and Computer Animation, 1999, 10(4): 181-192.
[53] Vassilev T, Spanlang B, Chrysanthou Y. Fast cloth animation on walking avatars. Computer Graphics Forum, 2001, 20(3): 260-267
[54] Hoff III KE, Zaferakis A, Lin M, et al. Fast and simple 2D geometric proximity queries using graphics hardware. In Proceedings of ACM Symposium on Interactive 3D Graphics, 2001: 145-148
[55] Kim YJ, Lin M, Manocha D. Fast penetration depth estimation using rasterization hardware and hierarchical refinement, In Symposium on Computational Geometry 2003, 2003: 386-387.
[56] Govindaraju NK, Redon S, Lin MC, et al. CULLIDE: Interactive collision detection between complex models in large environments using graphics hardware. Graphics Hardware, 2003
[57] Heidelberger B, Teschner M, Gross M. Volumetric collision detection for deformable objects. TR395 in Computer Science Department ETH Zurich, Switzerland, April 2003
[58] Gu X.F, Gortler S, Hoppe H. Geometry Image. In: Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, San Antonio Texas, USA, 2002: 355-361
[59] Tutte W. T, How to draw a graph. In: Proceedings London Mathematical Society, 1963, 13(52): 743-768
[60] Floater M. S, Parametrization and smooth approximation of surface triangulations. Computer Aided Geometric Design, 1997,14(3): 231-250
[61] Christer Ericson. Real-Time Collision Detection. San Francisco: Morgan Kaufmann Publisher, 2005. 172-175
[62] Alexander Grep, Michael Guthe, Reinhard Klein. GPU-based Collision Detection for Deformable Parameterized Surfaces. Computer Graphics Forum. 2006,25(3): 497-506
[63] Horn D. Stream reduction operations for GPGPU applications. In GPU Gems 2, 2005: 537-589
[64] H Weghorst, G Hooper, D P Greenberg. Improved computational methods for ray tracing. ACM Transaction on Computer Graphics. 1984, 3(1): 52-69
[2]Bergen.Efficient Collision Detection of Collision Deformable Models using AABB Trees.Journal of Graphics Tools,1997,2(4):1-14
[3]Yashifumi Kitamura,Andrew Smith,Haruo Takemura.A Realtime Algorithm for Accurate Collision Detection for Deformable Polyhedral Objects Presence Vol7.No.1 February 1998:36-52
[4]J Mezger,S Kimmerle,O Etzmub.Hierarchical Techniques in Collision Detection for Cloth Animation.Journal of WSCG11,2003,2:322-329
[5]Matthias Teschner,Bruno Heideleberger,Matthias Muller,et al.Optimized Spatial Hashing for Collision Detection of Deformable Objects Munish,Germany,Novermber,2003:19-21
[6]魏迎梅.虚拟环境中碰撞检测问题的研究:[博士学位论文].长沙:国防科技大学,2000
[7]范昭炜.实时碰撞检测技术研究:[博士学位论文].杭州:浙江大学,2003
[8][1]吴恩华,柳有权.基于图形处理器(GPU)的通用计算.计算机辅助设计与图形学学报,2004,16(5):601-612
[9]Clark James H.The geometry engine:A VLSI geometry system for graphics [A].In:Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH,Boston,1982.127-133
[10]Fuchs Herry,Poulton John.Pixel-planes:A VLSI-Oriented design for a raster graphics engine[J].VLSI Design,1981,2(3):20-28
[11]Eyles John,Austin John,Fuchs Henry,et al.Pixel-plane 4:A summary,advances in computer graphics hardware Ⅱ[A].Eurographic Seminars Tutorials and Perspectives in Computer Graphics,New York:Springer-Verlag,1988.183-208
[12]Fuchs Herry,Israel Laura,Poulton John,et al.Pixel-plane 5:A heterogeneous multiprocessor graphics system using processor-enhanced memories[A].In:Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH,Boston,1989.79-88
[13]Joao Luiz Dihl Comba,Dietrich Carlos A,Pagot Christian A,et al.Computation on GPUs:From a programmable pipeline to an efficient stream processor[J].Revista de Informatica Teoricae Aplicada,2003,X(2):41-70
[14]Kruger Jens,Westermann Rudiger.Linear algebra operators for GPU implementation of numerical algorithms[J].ACM Transactions on Graphics,2003,22(3):908-916
[15]Macedonia Michael.The GPU enters computing's mainstream[J].Computer,2003,36(10):106-108
[16]Venkatasubramanian Suresh.The graphics card as a stream computer[OL].
[17]Cohen Michael F,Chen Shenchang Eric,Wallace John R,et al.Aprogressive refinement approach to fast radiosity image generation[A].In:Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH,Atlanta,1988.75-84
[18]Lindholm Erik,Kilgard Mark J,Moreton Henry.A user-programmable vertex engine[A].In:Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH,Los Angeles,2001.149-158
[19]Harris Mark J,Coombe Greg,Scheuermann Thorsten,et al.Physically-based visual simulation on graphics hardware[A].In:Proceedings of Graphics Hardware,Saarbruchen,2002.109-118
[20]Bolz Jeff,Farmer Ian,Grinspun Eitan,et al.Sparse matrix solvers on the GPU:Conjugate gradients and multigrid[J].ACM Transactions on Graphics,2003,22(3):917-924
[21]Goddnight Nolan,Woolley Cliff,Luebke David,et al.A multigrid solver for boundary value problems using programmable graphics hardware[A].In:Proceedings of Graphics Hardware,San Diego,2003,102-111
[22]Hillesland Karl E,Molinov Sergey,Grzeszczuk Radek.Nonlinear optimization framework for image-based modeling on programmable graphics hardware[J].ACM Transactions on Graphics,2003,22(3):925-934
[23]吴恩华,柳有权.基于图形处理器(GPU)的通用计算[J].计算机辅助设计与图形学学报,2004,16(5):601-612
[24]吴恩华.图形处理器用于通用计算的技术、现状及其挑战.软件学报,2004,15(10):1493-1504
[25]张杨,诸昌铃,何太军.图形硬件通用计算技术的应用研究.计算机应用,2005,25(9):2192-2195
[26]Carr Nathan A,Hall Jesse D,Hart John C.The ray engine[A].In:Proceedings of Graphics Hardware,Saarbrucken,2002.37-46
[27]Purcell Timothy J,Donner Craig,Cammarano Mike,et al.Photon mapping on programmable graphics hardware[A].In:Proceedings of Graphics Hardware,San Diego,2003,41-50
[28]Hopf Matthias,Ertl Thomas.Accelerating 3D convolution using graphics hardware[A].In:Proceedings of IEEE Visualization,San Francisco,1999.471-474
[29]Hopf Matthias,Ertl Thomas.Hardware accelerated wavelet transformations [A].In:Proceedings of EG/IEEE TCVG Symposium on Visualization VisSym,Netherlands,2000.93-103
[30]Govindaraju Naga,Redon Stephane,Lin Ming C,et al.CULLIDE:Interactive collision detection between complex models in large environments using graphics hardware[A].In:Proceedings of Graphics Hardware,San Diego,2003,25-32
[31]Govindaraju Naga,Sud Avneesh,Yoon Sung-Eui,et al.Parallel occlusion culling for interactive walkthroughs using multiple GPUs[R].Carolina:University of North Carolina at Chapel Hill.UNC Computer Science Technical Report TR02-027,2002
[32]Wei Xiaoming,Zhao Ye,Fan Zhe,et al.Blowing in the wind[A].In:Proceedings of SIGGRAPH/Eurographics Symposium on Computer Animation,San Diego,2003.75-85
[33]Harris Mark J,Coombe Greg,Scheuermann Thorsten,et al.Simulation of cloud dynamics on graphics hardware[A].In:Proceedings of Graphics Hardware,Saarbrucken,2003.92-101
[34]Harris Mark J.Real-time cloud simulation and rendering[D].Chapel Hill:The University of North Carolina,2003
[35]Kim Theodore,Lin Ming C.Visual simulation of ice crystal growth[A].In:Proceedings of SIGGRAPH/Eurographics Symposium on Computer Animation,San Diego,2003.86-97
[36]李学庆.凸体碰撞检测问题的研究:[博士学位论文],济南:山东大学,2002
[37]徐春蕾.虚拟仿真环境中碰撞检测技术的研究与应用:[博士学位论文],长沙:国防科学技术大学,2000
[38]Cohen J,Lin MC,Manocha D,et al.I-COLLIDE:An interactive and exact collision detection system for large-scale environments.In Proceedings of ACM Interactive 3D Graphics Conference,Monterey,CA,USA,1995:189-196.
[39]Lin MC.Efficient Collision Detection for Animation and Robotics.Ph.D.Thesis,University of California,Berkeley,1993
[40]Andrew Witkin,David Baraff,Physically Based Modeling.Course 25 notes at SIGGRAPH 2001.
[41]Zachmann G.Optimizing the collision detection pipeline.In Proceedings of the First International Game Technology Conference(GTEC),Hong Kong,18-21January 2001
[42]Gottschalk S,Lin M,Manocha D.OBB-Tree:A Hierarchical Structure for Rapid Interference Detection.the Proceedings of ACM S IGGRAPH'96,1996:171-180
[43]Moller J,Goldman R.Combining algebraic rigor with geometric robustness for the detection and calculation of conic sections in the intersection of two quadric surfaces.In Proceedings of ACM Solid Modeling,1991:221-233
[44]Lin MC,Canny J.Efficient algorithms for incremental distance computation.In Proceedings of the IEEE International Conference on Robotics and Automation.1991:1008-1014
[45]Gilbert EG,Johnson DW,Keerthi SS.A fast procedure for computing the distance between objects in three-dimensional space.IEEE Journal on Robotics and Automation,1988,4:193-203
[46]Larsson T,Moller TA.Collision detection for continuously deforming bodies.In Proceedings of Eurographics'2001,2001,325-333
[47]Palmer I,Grimsdale R.Collision detection for animation using Sphere-Trees.Computer Graphics Forum,1995,14(2):105-116
[48]Hubbard PM.Real-time collision detection and time-critical computing.In SIVE 95, The First Workshop on Simulation and Interaction in Virtual Environments, Iowa City, Iowa. University of Iowa, informal proceedings, 1995,1:92-96
[49] Klosowski J, Held M, Mitchell JSB, et al. Efficient collision detection using bounding volume hierarchies of k-DOPs. IEEE Transaction On Visualization and Computer Graphics, 1998,4(1): 21-37
[50] Rossignac J, Megahed A. Schneider BO. Interactive inspection of solids: cross-section and interferences. Computer Graphics, 1992,26(2): 353-360
[51] Myszkowski K, Okunev OG, Kunii TL. Fast collision detection between computer solids using rasterizing graphics hardware. The Visual Computer, 1995,11:497-511
[52] Baciu G, Wong SKW, Sun H. RECODE: An image-based collision detection algorithm, Journal of Visualization and Computer Animation, 1999, 10(4): 181-192.
[53] Vassilev T, Spanlang B, Chrysanthou Y. Fast cloth animation on walking avatars. Computer Graphics Forum, 2001, 20(3): 260-267
[54] Hoff III KE, Zaferakis A, Lin M, et al. Fast and simple 2D geometric proximity queries using graphics hardware. In Proceedings of ACM Symposium on Interactive 3D Graphics, 2001: 145-148
[55] Kim YJ, Lin M, Manocha D. Fast penetration depth estimation using rasterization hardware and hierarchical refinement, In Symposium on Computational Geometry 2003, 2003: 386-387.
[56] Govindaraju NK, Redon S, Lin MC, et al. CULLIDE: Interactive collision detection between complex models in large environments using graphics hardware. Graphics Hardware, 2003
[57] Heidelberger B, Teschner M, Gross M. Volumetric collision detection for deformable objects. TR395 in Computer Science Department ETH Zurich, Switzerland, April 2003
[58] Gu X.F, Gortler S, Hoppe H. Geometry Image. In: Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, San Antonio Texas, USA, 2002: 355-361
[59] Tutte W. T, How to draw a graph. In: Proceedings London Mathematical Society, 1963, 13(52): 743-768
[60] Floater M. S, Parametrization and smooth approximation of surface triangulations. Computer Aided Geometric Design, 1997,14(3): 231-250
[61] Christer Ericson. Real-Time Collision Detection. San Francisco: Morgan Kaufmann Publisher, 2005. 172-175
[62] Alexander Grep, Michael Guthe, Reinhard Klein. GPU-based Collision Detection for Deformable Parameterized Surfaces. Computer Graphics Forum. 2006,25(3): 497-506
[63] Horn D. Stream reduction operations for GPGPU applications. In GPU Gems 2, 2005: 537-589
[64] H Weghorst, G Hooper, D P Greenberg. Improved computational methods for ray tracing. ACM Transaction on Computer Graphics. 1984, 3(1): 52-69