Print

发布时间: 2018-09-16
摘要点击次数:
全文下载次数:
DOI: 10.11834/jig.180015
2018 | Volume 23 | Number 9




    计算机图形学    




  <<上一篇 




  下一篇>> 





多样化实时刚体破碎模拟
expand article info 吕长建1, 曹力1,2, 火净泽1, 刘晓平1,2
1. 合肥工业大学计算机与信息学院, 合肥 230601;
2. 工业安全与应急技术安徽省重点实验室, 合肥 230009

摘要

目的 现有刚体破碎仿真模拟中,基于物理受力分析的方法往往难以应用在对实时性要求较高的场景中;而基于非物理方法的破碎模拟,破碎效果大多缺乏多样性。为了使得破碎模拟同时满足实时性和破碎效果多样化,提出了一种多样化实时刚体破碎模拟方法。方法 进行破碎模拟时首先由选定的种子点生成类型得到种子点集,采用Sweep Plane算法生成Voronoi图后基于Voronoi图信息对模型进行空间剖分;然后选择破碎时行为模拟方式,对物体破碎时所受外力进行模拟;最后对破碎时碰撞检测及碰撞后碎片的运动过程进行模拟并渲染显示。结果 通过组合不同的种子点生成类型和破碎时行为模拟方式,得到了多样化的刚体破碎效果。对单个刚体进行破碎模拟时,碎片数目不超过200个时帧率可以达到75帧/s,满足实时性的需求;对多个可破碎目标同时存在的复杂场景,破碎仿真模拟的平均帧率可以达到50帧/s,同样满足实时性要求;与现有方法对比的结果也验证了本文方法在计算效率和破碎效果多样性两方面达到了较好的平衡。结论 本文方法在满足实时性要求的同时,丰富了刚体破碎的效果,不同种子点生成类型和破碎时行为模拟方式的组合可以实现破碎效果多样性。

关键词

计算机仿真; 虚拟现实; 刚体破碎模拟; Voronoi图; 多样化破坏; 碰撞效果

Diversified real-time fracturing simulation of rigid body
expand article info Lyu Changjian1, Cao Li1,2, Huo Jingze1, Liu Xiaoping1,2
1. School of Computer and Information, Hefei University of Technology, Hefei 230601, China;
2. Anhui Province Key Laboratory of Industry Safety and Emergency Technology, Hefei 230009, China
Supported by: National Key R & D Program of China (2016YFC0800100); National Natural Science Foundation of China (61602146)

Abstract

Objective Fracturing has been widely applied in video games, films, and other industries. Fracturing simulation has attracted increasing attention in the field of computer graphics. Particularly, with the rapid development of virtual reality over the past few years, considerable demands have been placed on the diversity of fracturing results and real-time fracturing in a virtual scene. An improved fracturing result could significantly strengthen the realistic experience of players. In physics-based simulation method, the work of rigid body fracture simulation has been gradually conducted from the early inelastic deformation model to simulate the inelastic behavior to the mass-spring model and then to the fracture mechanism based on the tetrahedral model. To improve the realistic sense of fracturing effect as much as possible, numerous scholars have focused on enriching the detail expression of cracks during fracturing. During the continuous exploration of the simulation of physical phenomena in the real world, several physics engines have appeared in succession to simulate fragmentation and explosion in the real world. In recent years, significant progress has also been achieved in simulating the fragmentation of thin-plate type materials, such as paper, which renders the real-life fracturing phenomenon further varied on a computer. In the non-physical method of rigid body fracturing, the Voronoi diagram-based fracturing method plays a main role. However, the rigid body fracturing method has several disadvantages. First, the method based on physical force analysis does not work well in the situation where real-time is highly demanded, and the instant fracturing effect produced by the fracturing simulation based on non-physical method lacks diversity. Second, in most games, models often have been pre-fractured during their authoring time. When fracturing occurs, the original models are simply replaced by the pre-fractured one. This type of method significantly increases the authoring time of the designer and reduces the diversity. Most of the early works in film use the miniature model to simulate the crushing of large-scale scenes, such as the collapse of high-rise buildings. This type of method also lacks realism. To obtain real-time fracturing and diversified effects in fracturing simulation, a method applicable to diversified types is proposed, namely, a real-time rigid body fracturing method. Method During the fracturing simulation, the type of seed generation (three types of seed generation are available:completely random, evenly distributed with disturbance, and radiation) should be selected first. Then, sweep plane algorithm is used to generate the Voronoi diagram, based on which space partition is conducted on the model. During this process, to avoid the situation in which the seed points concentrated in a local area are too much or worse in the global area, sparse processing has been introduced:when multiple seed points are separated from each other by a certain threshold, the average value of the position of these seed points is selected as one seed point. Then, by means of a simulation pattern of fracture behavior (two types of simulation pattern:explosion and collapse), the external force when rigid-body fracturing is simulated and collision detection, following the impact process of the broken fragments, is also simulated. Finally, rendering and display follows. Result Through a combination of different seed point-generating types and simulation patterns of fracture behavior, the diversified effect of fracturing are simulated. The real-time requirement can be satisfied. In a single rigid-body model fracturing simulation, the frame rate can reach 75 fram/s with 200 broken fragments. In further complex scenarios (e.g., a building) where approximately 150 fracturing objectives with three types of materials are available, the frame rate can also reach 50 fram/s to cause the fracturing effect in this complex situation, not only to meet the diversity of fracturing effect but also to meet the real-time requirements, in the fracturing of different building components using different fracturing simulation types, through the combination of different types of seed point generation and fracture behavior simulation. A number of less affected parts from each other are broken at the same time. After comparison with some existing methods, the method used in this article achieves a better balance between computational efficiency (compared with the physics-based method) and diversity of fracturing effects (compared with the Voronoi-based method). Conclusion A real-time rigid-body fracturing method applicable to multi-fracturing effect is proposed in this paper. On the one hand, this method possesses a real-time feature, and on the other hand, it also contributes to enhancing the diversity of rigid body fracturing. By combining different seed point-generating types and simulation patterns of fracture behavior, diversified fracturing effects can be achieved. In our future work, this method will be further improved and optimized to be applied to highly complex fracturing simulation.

Key words

computer simulation; virtual reality; rigid body fracturing simulation; Voronoi diagram; diversified fracturing; collision effect

0 引言

破碎现象是物体受到外力后导致的损伤与毁坏,在游戏、仿真、虚拟现实等领域中有着大量应用,破碎效果极大影响着用户的真实感体验,也一直是计算机图形学中的一个研究热点。破碎模拟的真实感和实时性之间的平衡一直是该领域的一大难题,游戏中往往采用预破碎的方式,即在游戏制作过程中就已对模型进行了破碎处理,游戏中触发破碎事件时,则以预破碎的模型代替原始模型,虽然带来了快速可见的效果,但由于预破碎处理带来的破碎效果缺乏多样性,使得物理真实感大大降低,同时,复杂场景中的破坏行为也会极大增加内容制作的工作量;基于物理的方法虽然能得到真实感很强的破碎效果,但复杂的计算带来的时间开销使其难以适用于实时性场景中,同时破碎的物理仿真需要材料力学、断裂力学等理论基础,大大增加了实现难度。

计算机图形学领域对物体破碎的研究工作由来已久,希望从物理真实感角度仿真破碎机制和过程,Terzopoulos等人[1]做出了开创性工作,通过分析物体受力瞬间的形变,提出了一种简单的破碎机制;Norton等人[2]首次引入弹簧—质点模型对待破碎物体进行建模分析,并加入破碎后的碰撞检测和碰撞响应,使破碎效果的真实感得到进一步提升;在对脆性材料的破碎研究方面,Smith等人[3]在弹簧—质点模型基础上进行了改进,提出了一种快速、可控的模拟脆性材料破碎的方法,O′brien等人[4]提出了一种四面体有限元模型表示方法,并基于此对脆性材料进行应力分析,计算物体受力时的破坏点和破坏传播方向;O′brien等人[5]还将该方法拓展到塑性材料的破碎模拟中,同样得到了较好的模拟效果,但有限元方法包含大量的计算,使其难以应用在对时间有较高要求的场景之中;Parker等人[6]在改进四面体有限元方法的基础上,提出并设计了一种新的仿真模拟破碎的方法,并集成到物理引擎(digital molecular matter)中,在多个游戏作品中有不错的表现;在近几年的研究中,Busaryev等人[7]在对纸张、布料等类似材料的破碎中做出了较好的效果,其在有限元方法的基础上,结合材料自身特性,提出了一种自适应的破碎方法,可以模拟该类材料破裂时的撕裂感;Chen等人[8]和Hahn等人[9]在对生成细节更加丰富的破碎效果上提出了各自的方法,前者针对低分辨率下的破碎结果进行自适应优化,后者基于边界元方法模拟脆性材料的破碎,生成细节丰富的破碎表面;Hahn等人[10]还基于改进的边界元方法模拟了脆性材料的破碎。基于物理的方法虽然带来了较为精确的破碎仿真结果,但复杂的受力分析带来的时间开销使其难以应用在对实时性要求比较高的场景中。

在非物理方法方面,基于Voronoi图对模型进行空间划分模拟破碎的方法,在兼顾时间效率和真实感上取得了不错的效果。Parker等人[11]在对物体表面基于Voronoi图划分后得到了物体破裂的效果;宁江凡等人[12]提出一种基于预运算和Voronoi图的刚体破碎模拟方法,并对碎片的运动状态做了较好的模拟。这些工作满足了实时性要求和一定的真实感,但并未考虑到不同刚体对象的硬度与破碎形态区别,使得破碎效果缺乏多样性。

本文在现有方法基础上进行改进,提出了一种多样化的实时刚体破碎模拟方法,该方法在兼顾实时性和真实感的同时大大增加了刚体破碎效果的多样性,弥补了现有方法的不足。其中,多种种子点生成类型的提炼总结及多样化的破碎时行为的模拟是本文主要创新点。

1 破碎模拟

1.1 种子点选取

现有方法中单一的种子点生成类型是破碎效果缺乏多样性的原因之一。本文总结提出3种种子点生成类型,并在每种类型中提炼关键参数。对得到的种子点由Sweep Plane算法[13]构造Voronoi图。

1.1.1 Voronoi图生成

Sweep Plane算法构造Voronoi图的时间复杂度为${\rm{O}}(n{\rm{log}}\; n)$。对于当种子点数量过于密集时导致算法执行效率降低的情况,本文在实现时加入了种子点预处理过程,即当某个区域或全局内种子点过于密集时,进行稀疏化处理,对多个相互间距离小于某个阈值的种子点,取其位置平均值作为一个种子点进行处理。最终生成的Voronoi图中,包含了每个种子点所属区域的边界信息,映射回3维模型时,便可依据每个区域的边界对模型进行空间剖分。

下面是本文总结提出的3种种子点生成类型。

1.1.2 完全随机型

$ f = R\left( {b,t,n} \right) $ (1)

式中,$b({x_1}, {y_1})$$t({x_2}, {y_2})$为平面内2维坐标表示的种子点生成范围,以图 1为例,在长为$l$,宽为$w$的2维平面上生成种子点时,$b$$t$的取值范围为(0, 0)~($l$, $m$);$n$表示种子点个数。该种类型的种子点生成方式,以随机函数$R$($b$, $t$, $n$)生成一定数量的随机数$p$($x$, $y$),表示种子点坐标。考虑到现实世界中的破碎现象大多看起来杂乱无章,因此该类型种子点生成方式能模拟多数情形下物体破碎后的碎块形状。

图 1 完全随机型
Fig. 1 Completely random

1.1.3 均匀扰动型

该种类型的种子点生成方式,以均匀撒点添加扰动的方式生成最后的种子点集。

$ f = \frac{L}{s} + \lambda $ (2)

式中,$L$($l$, $w$)表示2维平面尺寸,$s$表示相邻种子点间隔值,$\lambda $表示扰动项,扰动项取值较大时会使得种子点分布过于稀疏甚至超出2维平面范围,为尽量避免此类情形,一般令扰动项取值范围在(0, $s$)之间。图 2所示为该种类型的种子点生成方式对应的平面划分结果。

图 2 均匀扰动型
Fig. 2 Evenly distributed with disturbance

1.1.4 放射型

$ f = d({p_i},O) - r;i = 1,2,3, \ldots ,n $ (3)

式中, ${p_i}({x_i}, {y_i})$为种子点位置,$O$为受力点位置,$d({p_i}, O)$${p_i}$$O$的欧氏距离(单位:m),$r$为常量,$n$为种子点数目。令$f=0$也即使种子点分布在以$O$为圆心,以$r$为半径的圆周上时,可以得到图 3所示的划分结果。

图 3 放射型
Fig. 3 Radiation

1.2 破碎时行为模拟

物体在外力影响下发生破碎后,会因所受外力的不同而产生多样化的运动过程。本文以如下方式添加物体所受外力,并通过总结常见破碎效果,给出爆炸式和坍塌式两种外力添加方式,即

$ E(T,{F_d},F) $

式中,$T$为目标物体,${F_d}$为力的方向,$F$为力的大小。

1.2.1 爆炸式

在爆炸式的破碎效果中,物体破碎后的各部分受到外力后获得较大的初始速度而运动。同时考虑到各部分距受力点远近不同,所以受到的外力大小不一,处于受力点中心的部分将受到更大的外力。计算各部分受到的外力$F$,即

$ {F_i} = \frac{F}{{1 + D({p_i},O)}} $ (4)

式中,$F$为初始外力,${F_i}$为第$i$个部分所受外力,${p_i}$为第$i$部分位置,$O$为受力点位置。${D({p_i}, O)}$为欧氏距离平方(单位:m2)。

1.2.2 坍塌式

对坍塌式破碎,采用自底向上、“分而治之”的破坏方式:即对受影响物体划分区域,不同区域采用不同的处理方式,即

$ {\mathit{\boldsymbol{P}}_c} = {\mathit{\boldsymbol{P}}_u} \cup {\mathit{\boldsymbol{P}}_d} $

式中,${\mathit{\boldsymbol{P}}_c}$表示模型整体,${\mathit{\boldsymbol{P}}_u}$表示模型上部分区域,${\mathit{\boldsymbol{P}}_d}$表示模型下部分区域。如图 4所示, 黄色线段以下为${\mathit{\boldsymbol{P}}_d}$区域,破坏时,由该部分开始,通过对该部分施加外力$F$使其位移(箭头表示区域内该部分所受外力方向,各部分在所受外力方向上添加一定扰动);黄色线段以上为${\mathit{\boldsymbol{P}}_u}$区域,对属于该区域的部分不添加外力,而是使其在重力作用下下落,形成坍塌效果。

图 4 坍塌式
Fig. 4 Collapse

同时,对破碎过程中的碰撞检测和碰撞后运动,本文在实现中基于Unity3D引擎进行模拟。该引擎以组件的方式提供了多种碰撞器,用以提供精准的碰撞检测,并可以高效计算每一帧中物体的运动状态,包括速度$v$, 角速度$\omega $等。

现将使用本文方法进行破碎模拟的过程总结如下,如图 5所示,对待破坏的3维刚体模型,首先根据选择的种子点生成类型获得种子点,生成Voronoi图后映射到3维模型进行空间剖分,然后选择破碎时行为模拟方式,最后结合Unity3D引擎进行碰撞检测及碰撞后运动过程模拟。

图 5 破碎模拟流程示意图
Fig. 5 Schematic diagram of fracturing simulation

2 实验结果与分析

本文在PC平台设计了实验并与相关文献中的方法进行对比,实验环境为Windows7 x64, Unity3D 5.4.3 (64 bit),硬件平台为Intel(R) Core(TM) i7-6700K CPU 4.00 GHz,内存8 GB, NVIDIA GeForce 960 GTX显卡。

2.1 多样化破碎仿真实验

图 6列出了使用本文方法通过组合不同的种子点生成类型($V$)和破碎时行为模拟方式($B$)时,得到的多样化破碎效果。图 6中T1, T2, T3分别代表完全随机型,均匀扰动型,放射型这3种种子点生成类型;Ⅰ,Ⅱ分别代表爆炸式、坍塌式两种破碎时行为模拟方式。

图 6 多样化破碎仿真效果
Fig. 6 Diversified fracturing simulation

Bradt等人[14]对玻璃受力时产生的裂纹形状进行了分析与总结,对比其结论与本文实验结果发现,放射型的种子点生成方式适合表现玻璃受外力时产生裂纹的效果;完全随机型的种子点生成方式与爆炸式的破碎时行为模拟适合表现玻璃、石块等材质类型的物体受外力时破碎的效果;对于均匀扰动型的种子点生成方式与坍塌式的破碎时行为模拟方法,则更适合表现高楼大厦、房屋等的倒塌效果。

可见,通过组合种子点生成类型与破碎时行为模拟方式,可以得到十分丰富的破碎效果。同时,使用本文方法进行表中破碎仿真实验时,碎片数目小于200时可以使运行时帧率达到75帧/s,碎片数目小于500时可以使运行帧率达到50帧/s,且破碎瞬间无明显卡顿现象。帧率统计基于整个破碎过程进行说明,该过程包含了破碎时模型剖分的计算。

2.2 多物体组合破碎仿真实验

图 7列出了采用本文方法进行多物体组合破碎仿真实验的结果,并给出了进行不同的破碎仿真实验时采用的种子点生成类型与破碎时行为模拟方式以及运行时帧率。

图 7 多物体组合破碎仿真效果
Fig. 7 Fracturing simulation with multi-targets

现实中的灾难场景以及游戏、虚拟现实等领域中的仿真场景,往往更加复杂多变,场景中可能存在多个受影响物体时发生破碎的情况,现有相关方法由于破碎效果的单一性和实时性等问题,难以应用在此类场景中。本文方法在破碎时对目标物体类型、受影响程度进行判断,采用不同的处理方式。如图 7砖墙破碎模拟效果图左图所示,对砖墙进行破碎时只对处于影响区域(以受力点为中心的某个圆形区域,图中黄色圆形标识)中的砖块进行处理,其中,距离受力点更近(图中红色框选砖块)的部分做破碎处理,其余部分(图中绿色框选砖块)则只施加外力,模拟受影响后的运动,相比曾亮等人[15]采用的局部预破碎模式,本文方法可以保证模拟过程更加高效;对整栋房屋的倒塌模拟,整个过程只需5 s,完全可以应用在实时场景中。

2.3 对比实验

本文还与相关文献中的方法进行了实验结果对比。图 8图 9分别为使用文献[10]、文献[12]的方法模拟小球碰撞目标物体时的破碎效果。图 10为使用本文方法组合不同的种子点生成类型和破碎时行为模拟方式得到的小球撞击目标物体时的破碎效果。通过对比3种方法(见表 1)可见,本文方法在满足实时性的前提下,还可以产生多样化的破碎效果。

图 8 文献[10]中方法模拟物体破碎效果
Fig. 8 Fracturing result with method in reference [10]
图 9 文献[12]中方法模拟物体破碎效果
Fig. 9 Fracturing result with method in reference [12]
图 10 本文方法模拟物体破碎效果
Fig. 10 Fracturing result with the method in this article

表 1 3种破碎方法对比
Table 1 Comparison of three fracturing methods

下载CSV
方法 破碎方法 实时性 多样性
文献[10] 基于物理模拟
文献[12] 基于Voronoi图
本文 基于Voronoi图

3 结论

本文对基于Voronoi图的刚体破碎方法进行改进,提出一种多样化实时刚体破碎模拟方法,通过组合不同的种子点生成类型和破碎时行为模拟方式得到了丰富的破碎效果。实验结果表明,该方法在满足实时性的要求上,极大丰富了破碎效果的多样性,基于游戏引擎的碰撞检测及碰撞后运动过程模拟,使破碎效果的真实感得到进一步提升。

在以后的研究中,将对该方法继续改进,使其可以适用于更复杂的场景仿真模拟;在更加复杂多变的场景中,多个破碎目标之间如何相互影响以及相互间影响对破坏方式带来的改变,会是未来工作的重点。

参考文献

  • [1] Terzopoulos D, Fleischer K. Modeling inelastic deformation:viscolelasticity, plasticity, fracture[J]. ACM SIGGRAPH Computer Graphics, 1988, 22(4): 269–278. [DOI:10.1145/378456.378522]
  • [2] Norton A, Turk G, Bacon B, et al. Animation of fracture by physical modeling[J]. Visual Computer, 1991, 7(4): 210–219. [DOI:10.1007/BF01900837]
  • [3] Smith J, Witkin A, David B. Fast and controllable simulation of the shattering of brittle objects[J]. Computer Graphics Forum, 2001, 20(2): 81–91. [DOI:10.1111/1467-8659.t01-1-00202]
  • [4] O'Brien J F, Hodgins J K. Graphical modeling and animation of brittle fracture[C]//Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques. New York, USA: ACM Press/Addison-Wesley Publishing Co, 1999: 137-146. [DOI:10.1145/311535.311550]
  • [5] O'Brien J F, Bargteil A W, Hodgins J K. Graphical modeling and animation of ductile fracture[J]. ACM Transactions on Graphics (TOG), 2002, 21(3): 291–294. [DOI:10.1145/566654.566579]
  • [6] Parker E G, O'Brien J F. Real-time deformation and fracture in a game environment[C]//Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. New Orleans, Louisiana, USA: ACM, 2009: 165-175. [DOI:10.1145/1599470.1599492]
  • [7] Busaryev O, Dey T K, Wang H M. Adaptive fracture simulation of multi-layered thin plates[J]. ACM Transactions on Graphics (TOG), 2013, 32(4): 52. [DOI:10.1145/2461912.2461920]
  • [8] Chen Z L, Yao M J, Feng R G, et al. Physics-inspired adaptive fracture refinement[J]. ACM Transactions on Graphics (TOG), 2014, 33(4): 113. [DOI:10.1145/2601097.2601115]
  • [9] Hahn Da, Wojtan C. High-resolution brittle fracture simulation with boundary elements[J]. ACM Transactions on Graphics (TOG), 2015, 34(4): 151. [DOI:10.1145/2766896]
  • [10] Hahn D, Wojtan C. Fast approximations for boundary element based brittle fracture simulation[J]. ACM Transactions on Graphics (TOG), 2016, 35(4): 104. [DOI:10.1145/2897824.2925902]
  • [11] Raghavachary S. Fracture generation on polygonal meshes using Voronoi polygons[C]//ACM SIGGRAPH 2002 Conference abstracts and Applications. New York, USA: ACM, 2002: 187. [DOI:10.1145/1242073.1242200]
  • [12] Ning J F, Lu S, Li S K. Real-time rigid body fracturing simulation based on Voronoi diagram[J]. Journal of Computer-Aided Design & Computer Graphics, 2011, 23(5): 825–832. [宁江凡, 路石, 李思昆. 基于Voronoi图的实时刚体破碎模拟[J]. 计算机辅助设计与图形学学报, 2011, 23(5): 825–832. ]
  • [13] Fortune S. A sweepline algorithm for Voronoi diagrams[J]. Algorithmica, 1987, 2(1-4): 153–174. [DOI:10.1007/BF01840357]
  • [14] Bradt R C. The fractography and crack patterns of broken glass[J]. Journal of Failure Analysis and Prevention, 2011, 11(2): 79–96. [DOI:10.1007/s11668-011-9432-5]
  • [15] Zeng L, Wu Y G. Volume based rigid body fracturing effect simulation[J]. Computer Engineering and Science, 2009, 31(S1): 260–262. [曾亮, 吴亚刚. 基于体元刚体破碎特效仿真[J]. 计算机工程与科学, 2009, 31(S1): 260–262. ] [DOI:10.3969/j.issn.1007-130X.2009.A1.074]
  • [16] Bao Z S, Hong J M, Teran J, et al. Fracturing rigid materials[J]. IEEE Transactions on Visualization and Computer Graphics, 2007, 13(2): 370–378. [DOI:10.1109/TVCG.2007.39]