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

1. 合肥工业大学计算机与信息学院, 合肥 230601;
2. 工业安全与应急技术安徽省重点实验室, 合肥 230009
 收稿日期: 2018-01-08; 修回日期: 2018-03-12 基金项目: 国家重点研发计划基金项目（2016YFC0800100）；国家自然科学基金项目（61602146） 第一作者简介: 吕长建, 1991年生, 男, 硕士研究生, 主要研究方向为计算机图形学与可视化。E-mail:lcj_hfut@163.com;曹力, 男, 博士, 讲师, 硕士生导师, 主要研究方向为计算机图形学、计算几何。E-mail:lcao@hfut.edu.cn;火净泽, 男, 本科在读, 主要研究方向为图像处理与人机交互。E-mail:jzfire@foxmail.com. 中图法分类号: TP391.41 文献标识码: A 文章编号: 1006-8961(2018)09-1403-08

# 关键词

Diversified real-time fracturing simulation of rigid body
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

# 1.1.1 Voronoi图生成

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

# 1.1.2 完全随机型

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

# 1.1.3 均匀扰动型

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

# 1.1.4 放射型

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

# 1.2 破碎时行为模拟

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

# 1.2.1 爆炸式

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

# 1.2.2 坍塌式

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

# 2.3 对比实验

Table 1 Comparison of three fracturing methods

 方法 破碎方法 实时性 多样性 文献[10] 基于物理模拟 否 否 文献[12] 基于Voronoi图 是 否 本文 基于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]