实体破碎特效仿真建模及其渲染技术研究与实现
|
摘要
实体破碎特效仿真在计算机图形学研究与虚拟现实应用环节中扮演着重要角色。随着可编程图形硬件的大众化投入使用,在数字游戏、影视动画等领域越来越需要复杂、真实感的诸如软体、粘性体、刚体形变及其破碎相关特效。软体、刚体的仿真本身是图形学界一个复杂的研究内容,目前在研究工作中存在的关键问题是学者们过于追求仿真视觉可信性,实时性难以解决。
本文在系统研究分析软体、刚体仿真成熟方法的基础上,针对破碎特效的需要,对基于质点弹簧系统和闭合气体压力模型的软体仿真、基于虚节点算法的软体多局部破碎特效进行了研究,对基于破碎模式、局部破碎、Voronoi破碎特征的相关破碎特效进行了研究,完成了相关算法与系统平台的实现。本文主要工作及取得的主要研究成果包括:
1)利用虚节点在仿真过程中改变网格拓扑结构的特性,提出基于虚节点的软体多局部破碎特效描述算法,并结合现有基于质点弹簧系统与闭合气体压力模型相结合的软体仿真成熟方法,实现了实时交互式软体破碎仿真平台。
2)设计了一种基于八叉树剖分的几何模型局部区域选择算法,利用八叉树结构对实体模型空间结构进行划分,采取交互式的方法选择实体模型具有空间连续性的局部区域,该区域的快速选择是后续研究刚体局部破碎特效的关键性环节。
3)提出一种刚体预破碎模式,将实体划分成内部空间连续、互不相交的几个子区域块,采用线性约束连接各子块和组成实体的块内基本元素。线性约束在仿真过程中进行能量传递,当实体与外界发生碰撞时,采用统一算法检测约束的能量承载情况,当它承载能量超过其阈值则该处约束发生断裂,约束的断裂导致子块分离形成破碎特效,不同程度的碰撞将会导致不同位置的约束断裂,进而形成不同程度的破碎特效。
4)设计实现了刚体局部破碎特效仿真方法,将局部区域选择算法抽取的子区域与实体剩余部分通过线性约束相连,子区域内的基本元素也通过线性约束进行连接,然后应用预破碎模式,实现了不同程度的实体破碎特效仿真。
5)设计基于破碎模式的刚体破碎特效,利用Voronoi图生成随机区域的特性进行子块划分,相关研究工作正在进行中。
Object fracturing effects simulation such as Soft Body and Rigid Body has played an important role in the Computer Graphics research and the Virtual Reality applications. As the GPU commonly used in most fields, complicated and realistic soft body, viscosity body, rigid body deformation as well as their fracture effects are largely needed in digital games, and in video animation. At the mean time, soft body and rigid body fracturing effects simulation has strongly attracted the heart of the researchers, and in fact it is complicated, the key problem is that reserarchers trend to focus on the visual reliability, the real-time feature is not solved.
We have analyzed the most popular method of soft body and rigid body simulation by the numbers, focusing on the requirement of the fracture effect, we researched the soft body simulation combined with mass-spring system and the pressure model; we researched the virtual node algorithm based multiple fracture effect on soft body simulation; we researched the fracture pattern, local fracture, Voronoi fracture feature based fracture effect, and finally we designed the exact algorithms and implemented the simulation platform. The contributions and relevant work in this paper are as follows:
Firstly, make use of the virtual node algorithm that is used to change mesh topology, we proposed the virtual node based multiple local fracture description algorithms, and later it is applied in the real-time interactive soft body simulation platform which use the popular mass-spring system and pressure model.
Secondly, we designed octree partition based local area choosing algorithm on the object’s geometric model, octree is used to structure the object, later we use interactive method to choose the continual local area on the surface, quick choosing local area is the key point of the later local fracturing effect research.
Thirdly, we proposed the rigid body pre-fracture pattern, object is separated into several spatial continual and non-intersect sub-blocks, and then line-constraint is used to connect the sub-block and the basic element in it. Line-constraint can transfer energy, when the object collides with the environment, we used a unified algorithm to detect how much energy the line-constraint transfers, when the value exceed the pre-fixed value it will break, and the broken constraint would lead to the separateness of the sub-block, which would form fracture, different degrees of collide will lead to different levels of fracture due to the location of the constraint.
Fourthy, we designed the local fracture simulation method, the local area choosing algorithm will extra the exact sub-area, line-constraints are used to connect the sub-area with the leaving area, and the basic element is connected by the constraint too. And later we apply the pre-fracture pattern, int the end we get different levels of fracturing effects.
Finally, we designed the fracture pattern based fracture effect, we use the voronoi diagram theory, and it is used to generate random sub-area, this is still in research for the future.
本文在系统研究分析软体、刚体仿真成熟方法的基础上,针对破碎特效的需要,对基于质点弹簧系统和闭合气体压力模型的软体仿真、基于虚节点算法的软体多局部破碎特效进行了研究,对基于破碎模式、局部破碎、Voronoi破碎特征的相关破碎特效进行了研究,完成了相关算法与系统平台的实现。本文主要工作及取得的主要研究成果包括:
1)利用虚节点在仿真过程中改变网格拓扑结构的特性,提出基于虚节点的软体多局部破碎特效描述算法,并结合现有基于质点弹簧系统与闭合气体压力模型相结合的软体仿真成熟方法,实现了实时交互式软体破碎仿真平台。
2)设计了一种基于八叉树剖分的几何模型局部区域选择算法,利用八叉树结构对实体模型空间结构进行划分,采取交互式的方法选择实体模型具有空间连续性的局部区域,该区域的快速选择是后续研究刚体局部破碎特效的关键性环节。
3)提出一种刚体预破碎模式,将实体划分成内部空间连续、互不相交的几个子区域块,采用线性约束连接各子块和组成实体的块内基本元素。线性约束在仿真过程中进行能量传递,当实体与外界发生碰撞时,采用统一算法检测约束的能量承载情况,当它承载能量超过其阈值则该处约束发生断裂,约束的断裂导致子块分离形成破碎特效,不同程度的碰撞将会导致不同位置的约束断裂,进而形成不同程度的破碎特效。
4)设计实现了刚体局部破碎特效仿真方法,将局部区域选择算法抽取的子区域与实体剩余部分通过线性约束相连,子区域内的基本元素也通过线性约束进行连接,然后应用预破碎模式,实现了不同程度的实体破碎特效仿真。
5)设计基于破碎模式的刚体破碎特效,利用Voronoi图生成随机区域的特性进行子块划分,相关研究工作正在进行中。
Object fracturing effects simulation such as Soft Body and Rigid Body has played an important role in the Computer Graphics research and the Virtual Reality applications. As the GPU commonly used in most fields, complicated and realistic soft body, viscosity body, rigid body deformation as well as their fracture effects are largely needed in digital games, and in video animation. At the mean time, soft body and rigid body fracturing effects simulation has strongly attracted the heart of the researchers, and in fact it is complicated, the key problem is that reserarchers trend to focus on the visual reliability, the real-time feature is not solved.
We have analyzed the most popular method of soft body and rigid body simulation by the numbers, focusing on the requirement of the fracture effect, we researched the soft body simulation combined with mass-spring system and the pressure model; we researched the virtual node algorithm based multiple fracture effect on soft body simulation; we researched the fracture pattern, local fracture, Voronoi fracture feature based fracture effect, and finally we designed the exact algorithms and implemented the simulation platform. The contributions and relevant work in this paper are as follows:
Firstly, make use of the virtual node algorithm that is used to change mesh topology, we proposed the virtual node based multiple local fracture description algorithms, and later it is applied in the real-time interactive soft body simulation platform which use the popular mass-spring system and pressure model.
Secondly, we designed octree partition based local area choosing algorithm on the object’s geometric model, octree is used to structure the object, later we use interactive method to choose the continual local area on the surface, quick choosing local area is the key point of the later local fracturing effect research.
Thirdly, we proposed the rigid body pre-fracture pattern, object is separated into several spatial continual and non-intersect sub-blocks, and then line-constraint is used to connect the sub-block and the basic element in it. Line-constraint can transfer energy, when the object collides with the environment, we used a unified algorithm to detect how much energy the line-constraint transfers, when the value exceed the pre-fixed value it will break, and the broken constraint would lead to the separateness of the sub-block, which would form fracture, different degrees of collide will lead to different levels of fracture due to the location of the constraint.
Fourthy, we designed the local fracture simulation method, the local area choosing algorithm will extra the exact sub-area, line-constraints are used to connect the sub-area with the leaving area, and the basic element is connected by the constraint too. And later we apply the pre-fracture pattern, int the end we get different levels of fracturing effects.
Finally, we designed the fracture pattern based fracture effect, we use the voronoi diagram theory, and it is used to generate random sub-area, this is still in research for the future.
引文
[1]孙家广.计算机图形学.清华大学出版社,1998.
[2]唐泽圣.三维数据场可视化.清华大学出版社,1999.
[3]谷宁.基于刚体特性的物理仿真引擎的设计与实现.东北师范大学硕士学位论文, 2009.
[4]康凤举.现代仿真技术与应用(第二版).国防工业出版社,2006.
[5]齐朝晖.多系统动力学.科学出版社,2007.
[6] ODE.http://www.ode.org/.
[7] Physx.http://www.nvidia.com/objdect/physx-new.html.
[8]魏迎梅,王甬,吴泉源,石教英.刚体在软体对象环境中的碰撞检测的研究.计算机学报,2001,24(8):802~808.
[9] Jesper M., Peder H., Thomas S. A GPU Accelerated Spring Mass System for Surgical Simulation. Medicine Meets Virtual Reality, 2005:342~348.
[10] LIU Xiao-ping, Cao Li, Chen Hao,Weng Xiao-yi. Pressure Model of Soft Body Collision Detection based on Octree. Journal of System Simulation 2006, 18(10):2903~2905.
[11] Jaruwan Mesit, Ratan K.Guha. Soft Body Simulation with Leaking Effect. Second Asia International Conference on Modeling & Simulation 2008.
[12] J. O'Brien, J. Hodgins. Graphical Modeling and Animation of Brittle Fracture. Proceedings of ACM SIGGRAPH 99,1999:137~146.
[13] Ohan Oda, Stephen Chenney. Fast Dynamic Fracture of Brittle Objects. Proceedings of ACM SIGGRAPH 2005,Poster. No.113.
[14] J.O'Brien, A.Bargteil, J.Hodgins. Graphical modeling and Animation of Ductile fracture. ACM Trans.Graph.2002.
[15] Neil Molino, Zhaosheng Bao, Ron Fedkiw. A Virtual Node Algorithm for Changing Mesh Topology During Simulation. SIGGRAPH 2004, ACM TOG 23, 2004:385~392.
[16] Zhaosheng Bao, Jeong-Mo Hong, Joseph Teran, et al. Fracturing Rigid Materials. IEEE Transactions on Visualization and Computer Graphics,2006,13(2):370-378.
[17] A. Norton, G. Turk, B. Bacon, J. Gerth, P. Sweeney. Animation of fracure by physical modeling. Visual Computing ,1991:210~219.
[18] K. Hirota, Y. Tanoue, T. Kaneko. Generation of crack patterns with a physical model. The Visual Compute, 1998.
[19] O. Mazarak, C. Martins, J. Amanatides. Animating exploding objects. Proc of Graph. Interface 1999, 1999.
[20] Jeffrey Smith, Andrew Witkin, David Baraff. Fast and Controllable Simulation ofthe Shattering of Brittle Objects. Computer Graphics Forum. 2001, 20(2):81~90.
[21] J.-P. Gourret, N.Magnenat-Thalmann, D.Thalmann. Simulation of object and human skin deformations in a grasping tast. Comput.Graph.(SIGGRAPH Proc),1989.
[22] G.Picinbono, H.Delingette, N.Ayache. Non-linear and anisotropic elastic soft tissue models for medical simulation. IEEE Int. Conf. Robot and Automation, 2001.
[23] D.Chen, D.Zeltzer. Pump it up: Computer animation of a biomechanically based model of muscle using finite element method. Comput.Graph.(SIGGRAPH Proc.), 1992.
[24] Matthias Muller, Markus Gross. Interactive Virtual Materials. Proceedings of Graphics Interface 2004:239~246.
[25] David Mould. Image-Guide Fracture. Proceedings of Graphics Interface 2005: 219~226.
[26] Jonathan Su, Craig Schroeder, Ronald Fedkiw. Energy Stability and Fracture for Frame Rate Rigid Body Simulations. Eurographics/ACM SIGGRAPH Symposium on Computer Animation, 2009:155~164.
[27] Joachim Georgii, Rüdiger Westermann. Mass-spring systems on the GPU. Simulation Modelling Practice and Theory, 2005, 11, 13(8): 693~702.
[28] Murat Balci, Hassan Foroosh. Real-time 3D Fire Simulation Using a Spring-Mass Model. IEEE International Multimedia Modeling Conference, 2006.
[29] Desbrun, M.P.Cani, and A.Barr. Adaptive simulation of soft bodies in real-time. Comp. Anim., 2000, 5:133~144.
[30] Andreas OFrank, I Alexander Twombly, et al. Finite Element Methods for real time Haptic Feedback of Soft-Tissue Models in Virtual Reality Simulators. Proceeding of IEEE Virtual Reality Conference, 2001:257~263.
[31] Maciey Matyka, Mark Ollila. Pressure Model of Soft Body Simulation. SIGRAD 2003, 2003, 11.
[32] Andrew Selle, Michael Lentine, Ronald Fedkiw. A Mass Spring Model for Hair Simulation. SIGGRAPH 2008, ACM TOG 27, 2008, 64.1~64.11.
[33] Nixon D., Lobb R. A fluid-based soft-object model. Com.Graph and App., IEEE, 2002, 22(4):68~75.
[34] Sean Curtis, Rasmus Tamstorf, Dinesh Manocha. Fast Collision Detection for Deformable Models using Representative-Triangles. Symposium on Interactive 3D Graphics and Games in I3D 2008.
[35]朱淮冰,金小刚,冯结清,彭群生.布料动画模拟综述.计算机辅助设计与图形学学报,2004,16(5):613~618.
[36] David Eberle, Oliver Strunk, Ronan O’Sullivan. A Procedural Approach toModeling Impact Damage. ACM SIGGRAPH 2003 Sketches & Applications., 2003.
[37] Hecker Chris Physics,Part 4:The Third Dimension.
[38]常高祥,徐晓刚.碰撞检测问题综述. CIDE2009会议论文集, 2009:189~195.
[39]范昭炜.实时碰撞检测技术研究.浙江大学,2003,10:15~30.
[40] YNGVE G., O’BRIEN J., HODGINS J. Animating explosions. In Proc. SIGGRAPH 2000, 2000(19):29~36.
[41] SI, H. 2000. Tetgen. A 3D Delaunay tetrahedral Mesh Generator,v.1.2 Users Manual. Technical Report. WeirStrass Institute for Applied Analysis and Stochastics.
[42] Dave Shreiner, Mason Woo, Jackie Neider, Tom Davis.OpenGL编程指南(原书第5版).机械工业出版社,2006.
[43] Sylvain Lefebvre, Samuel Hornus, Fabrice Neyret. Octree Textures on the GPU. GPU Gems 2. Addison Wesley, 2005:595-613.
[44] Havok. http://www.havok.com/
[45] GUENDELMAN E., BRIDSON R., FEDKIW R. Nonconvex rigid bodies with stacking. ACM Trans. Graph. (Proc. SIGGRAPH) 2003, 2003:871~878.
[46] KAUFMAN D., SUEDA S., JAMES D., PAI D. Staggered projections for frictional contact in multibody systems. ACM Transactions on Graphics (SIGGRAPH Asia 2008) , 2008(164):1~11.
[47] Saty Raghavachary. Fracture generation on polygonal meshes using Voronoi polygons. ACM SIGGRPAH 2002 Conference abstracts and applications, 2002:187-187.
[48]周培德.计算几何----算法设计与分析(第三版).清华大学出版社,2008.
[49] Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides.设计模式----可复用面向对象软件的基础.机械工业出版社,1994.8.
[50]谭庆平,齐治昌,宁洪.软件工程(第二版).高等教育出版社,2004.4.
[51] http://blog.csdn.net/scarletty/archive/2009/04/28/4133445.aspx
[52] http://blog.csdn.net/rickArkin/archive/2007/10/26/1845870.aspx
[2]唐泽圣.三维数据场可视化.清华大学出版社,1999.
[3]谷宁.基于刚体特性的物理仿真引擎的设计与实现.东北师范大学硕士学位论文, 2009.
[4]康凤举.现代仿真技术与应用(第二版).国防工业出版社,2006.
[5]齐朝晖.多系统动力学.科学出版社,2007.
[6] ODE.http://www.ode.org/.
[7] Physx.http://www.nvidia.com/objdect/physx-new.html.
[8]魏迎梅,王甬,吴泉源,石教英.刚体在软体对象环境中的碰撞检测的研究.计算机学报,2001,24(8):802~808.
[9] Jesper M., Peder H., Thomas S. A GPU Accelerated Spring Mass System for Surgical Simulation. Medicine Meets Virtual Reality, 2005:342~348.
[10] LIU Xiao-ping, Cao Li, Chen Hao,Weng Xiao-yi. Pressure Model of Soft Body Collision Detection based on Octree. Journal of System Simulation 2006, 18(10):2903~2905.
[11] Jaruwan Mesit, Ratan K.Guha. Soft Body Simulation with Leaking Effect. Second Asia International Conference on Modeling & Simulation 2008.
[12] J. O'Brien, J. Hodgins. Graphical Modeling and Animation of Brittle Fracture. Proceedings of ACM SIGGRAPH 99,1999:137~146.
[13] Ohan Oda, Stephen Chenney. Fast Dynamic Fracture of Brittle Objects. Proceedings of ACM SIGGRAPH 2005,Poster. No.113.
[14] J.O'Brien, A.Bargteil, J.Hodgins. Graphical modeling and Animation of Ductile fracture. ACM Trans.Graph.2002.
[15] Neil Molino, Zhaosheng Bao, Ron Fedkiw. A Virtual Node Algorithm for Changing Mesh Topology During Simulation. SIGGRAPH 2004, ACM TOG 23, 2004:385~392.
[16] Zhaosheng Bao, Jeong-Mo Hong, Joseph Teran, et al. Fracturing Rigid Materials. IEEE Transactions on Visualization and Computer Graphics,2006,13(2):370-378.
[17] A. Norton, G. Turk, B. Bacon, J. Gerth, P. Sweeney. Animation of fracure by physical modeling. Visual Computing ,1991:210~219.
[18] K. Hirota, Y. Tanoue, T. Kaneko. Generation of crack patterns with a physical model. The Visual Compute, 1998.
[19] O. Mazarak, C. Martins, J. Amanatides. Animating exploding objects. Proc of Graph. Interface 1999, 1999.
[20] Jeffrey Smith, Andrew Witkin, David Baraff. Fast and Controllable Simulation ofthe Shattering of Brittle Objects. Computer Graphics Forum. 2001, 20(2):81~90.
[21] J.-P. Gourret, N.Magnenat-Thalmann, D.Thalmann. Simulation of object and human skin deformations in a grasping tast. Comput.Graph.(SIGGRAPH Proc),1989.
[22] G.Picinbono, H.Delingette, N.Ayache. Non-linear and anisotropic elastic soft tissue models for medical simulation. IEEE Int. Conf. Robot and Automation, 2001.
[23] D.Chen, D.Zeltzer. Pump it up: Computer animation of a biomechanically based model of muscle using finite element method. Comput.Graph.(SIGGRAPH Proc.), 1992.
[24] Matthias Muller, Markus Gross. Interactive Virtual Materials. Proceedings of Graphics Interface 2004:239~246.
[25] David Mould. Image-Guide Fracture. Proceedings of Graphics Interface 2005: 219~226.
[26] Jonathan Su, Craig Schroeder, Ronald Fedkiw. Energy Stability and Fracture for Frame Rate Rigid Body Simulations. Eurographics/ACM SIGGRAPH Symposium on Computer Animation, 2009:155~164.
[27] Joachim Georgii, Rüdiger Westermann. Mass-spring systems on the GPU. Simulation Modelling Practice and Theory, 2005, 11, 13(8): 693~702.
[28] Murat Balci, Hassan Foroosh. Real-time 3D Fire Simulation Using a Spring-Mass Model. IEEE International Multimedia Modeling Conference, 2006.
[29] Desbrun, M.P.Cani, and A.Barr. Adaptive simulation of soft bodies in real-time. Comp. Anim., 2000, 5:133~144.
[30] Andreas OFrank, I Alexander Twombly, et al. Finite Element Methods for real time Haptic Feedback of Soft-Tissue Models in Virtual Reality Simulators. Proceeding of IEEE Virtual Reality Conference, 2001:257~263.
[31] Maciey Matyka, Mark Ollila. Pressure Model of Soft Body Simulation. SIGRAD 2003, 2003, 11.
[32] Andrew Selle, Michael Lentine, Ronald Fedkiw. A Mass Spring Model for Hair Simulation. SIGGRAPH 2008, ACM TOG 27, 2008, 64.1~64.11.
[33] Nixon D., Lobb R. A fluid-based soft-object model. Com.Graph and App., IEEE, 2002, 22(4):68~75.
[34] Sean Curtis, Rasmus Tamstorf, Dinesh Manocha. Fast Collision Detection for Deformable Models using Representative-Triangles. Symposium on Interactive 3D Graphics and Games in I3D 2008.
[35]朱淮冰,金小刚,冯结清,彭群生.布料动画模拟综述.计算机辅助设计与图形学学报,2004,16(5):613~618.
[36] David Eberle, Oliver Strunk, Ronan O’Sullivan. A Procedural Approach toModeling Impact Damage. ACM SIGGRAPH 2003 Sketches & Applications., 2003.
[37] Hecker Chris Physics,Part 4:The Third Dimension.
[38]常高祥,徐晓刚.碰撞检测问题综述. CIDE2009会议论文集, 2009:189~195.
[39]范昭炜.实时碰撞检测技术研究.浙江大学,2003,10:15~30.
[40] YNGVE G., O’BRIEN J., HODGINS J. Animating explosions. In Proc. SIGGRAPH 2000, 2000(19):29~36.
[41] SI, H. 2000. Tetgen. A 3D Delaunay tetrahedral Mesh Generator,v.1.2 Users Manual. Technical Report. WeirStrass Institute for Applied Analysis and Stochastics.
[42] Dave Shreiner, Mason Woo, Jackie Neider, Tom Davis.OpenGL编程指南(原书第5版).机械工业出版社,2006.
[43] Sylvain Lefebvre, Samuel Hornus, Fabrice Neyret. Octree Textures on the GPU. GPU Gems 2. Addison Wesley, 2005:595-613.
[44] Havok. http://www.havok.com/
[45] GUENDELMAN E., BRIDSON R., FEDKIW R. Nonconvex rigid bodies with stacking. ACM Trans. Graph. (Proc. SIGGRAPH) 2003, 2003:871~878.
[46] KAUFMAN D., SUEDA S., JAMES D., PAI D. Staggered projections for frictional contact in multibody systems. ACM Transactions on Graphics (SIGGRAPH Asia 2008) , 2008(164):1~11.
[47] Saty Raghavachary. Fracture generation on polygonal meshes using Voronoi polygons. ACM SIGGRPAH 2002 Conference abstracts and applications, 2002:187-187.
[48]周培德.计算几何----算法设计与分析(第三版).清华大学出版社,2008.
[49] Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides.设计模式----可复用面向对象软件的基础.机械工业出版社,1994.8.
[50]谭庆平,齐治昌,宁洪.软件工程(第二版).高等教育出版社,2004.4.
[51] http://blog.csdn.net/scarletty/archive/2009/04/28/4133445.aspx
[52] http://blog.csdn.net/rickArkin/archive/2007/10/26/1845870.aspx