高效解决复杂拓扑问题的显式界面追踪算法

doi:10.6040/j.issn.1672-3961.0.2016.028

摘要/Abstract

摘要： 为精确追踪具有复杂拓扑变化的自由界面,提出一种算法。该算法以显式的Lagrangian网格对自由界面进行建模,利用外部的速度场来移动界面网格,并且基于局部界面重构的技术来处理界面几何,有效地消除显式界面机制中常见的自相交等几何错误。算法利用体素网格来有效地检测拓扑事件的区域,在这些区域里对界面进行细分,将具有拓扑错误的界面部分替换为预定义的模板,并使用精确的缝合算法将重构的局部界面与区域外的原始界面连接起来。试验证明该算法可以快速无误的处理显式界面的拓扑变化,适合应用于液体的仿真动画。

关键词: 显式界面, 模板, 体素, 拓扑, 局部重构

Abstract: A new algorithm was put forth to accurately track the free surface with complex changing topology. This algorithm employed the explicit Lagrangian mesh to model the free surface, used the external velocity field to move the surface mesh and processed the surface geometry by using the local re-meshing techniques, which efficiently eliminated the self-intersection errors. By this algorithm, a voxel grid was used to effectively detect the regions where the topological events occurred. In the regions, the surface meshes were subdivided, the topologically incorrect meshes were replaced by the predefined templates and then an accurate sewing operation was performed to connect the reconstructed local meshes with the external meshes. Ultimately, the experimental results indicated that this algorithm could effectively handle the topological events of the explicit meshes, which was suitable for a liquid animation in the practical applications.

Key words: explicit surface, template, voxel, topology, local reconstruction

中图分类号:

TP391

侯燕,杨猛. 高效解决复杂拓扑问题的显式界面追踪算法[J]. 山东大学学报(工学版), 2016, 46(4): 15-20.

HOU Yan, YANG Meng. Highly efficient algorithm for tracking explicit surface to process complex topological events[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(4): 15-20.

参考文献

[1] OSHER S, SETHIAN J. Fronts propagating with curvature-dependent speed: Algorithms based on hamilton-jacobi formulations[J]. Journal of Computational Physics, 1988, 79(1):12-49.
[2] OSHER S, FEDKIW R. Level set methods and dynamic implicit surfaces[M]. New York, USA: Springer, 2003.
[3] 刘儒勋, 王志峰. 数值模拟方法和运动界面追踪[M].安徽:中国科学技术大学出版社, 2001: 187-190.
[4] JIANG G S, PENG D. Weighted ENO schemes for hamilton jacobi equations[J]. SIAM Journal on Scientific Computing, 2000, 21(6):2126-2143.
[5] SELLE A, FEDKIW R, KIM B, et al. An unconditionally stable maccormack method[J]. Journal of Scientific Computing, 2008, 35(2-3):350-371.
[6] SETHIAN J.A fast marching level set method for monotonically advancing fronts[J]. Proceedings of National Academic Science, 1996, 93(4):1591-1595.
[7] ZHAO Hongkai. A fast sweeping method for eikonal equations[J]. Mathematics of computation, 2005, 74(250):603-627.
[8] 周勇, 唐泽圣.用自适应的三线性逼近方法构造等值面[J].计算机学报, 1994,17(S1):1-10. ZHOU Yong, TANG Zesheng. Adaptive trilinear approximation to isosurfaces of data sets in 3D space[J]. Chinese Journal of Computers, 1994, 17(S1):1-10.
[9] 杨猛, 汪国平, 董士海.基于Level Set方法的曲线演化[J].软件学报, 2002, 13(9):1858-1865. YANG Meng, WANG Guoping, DONG Shihai. Curves evolving based on level set method[J]. Journal of software, 2002, 13(9):1858-1865.
[10] FOSTER N, FEDKIW R. Practical animation of liquids[C] // Proceedings of the 28th Annual Conference on Computer Graphics. New York, USA: ACM Press, 2001: 23-30.
[11] ENRIGHT D, MARSCHNER S, FEDKIW R. Animation and rendering of complex water surfaces[J]. ACM Transactions on Graphics, 2002, 21(3):736-744.
[12] BARGTEIL A W, GOKTEKIN T G, OBRIEN J F, et al. A semi-Lagrangian contouring method for fluid simulation[J]. ACM Transactions on Graphics, 2006, 25(1):19-38.
[13] LOSASSO F, SHINAR T, SELLE A, et al. Multiple interacting liquids[J]. ACM Transactions on Graphics, 2006, 25(3):812-819.
[14] ZHENG W, YONG J H, PAUL J C. Simulation of bubbles[J]. Graphical Models, 2009, 71(6):229-239.
[15] KIM B. Multi-Phase fluid simulations using regional level sets[J]. ACM Transactions on Graphics, 2010, 29(6):175.
[16] BROCHU T, BRIDSON R. Robust topological operations for dynamic explicit surfaces[J]. SIAM Journal on Scientific Computing, 2009, 31(4):2472-2493.
[17] MÜLLER M. Fast and robust tracking of fluid surfaces[C] //Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. New York, USA: ACM Press, 2009: 237-245.
[18] WOJTAN C, THÜREY N, GROSS M, et al. Deforming meshes that split and merge[J]. ACM Transactions on Graphics, 2009, 28(3):1-10.
[19] WOJTAN C, THÜREY N, GROSS M, et al. Physics-inspired topology changes for thin fluid features[J]. ACM Transactions on Graphics, 2010, 29(4):1-8.
[20] DA F, BATTY C, WOJTAN C, et al. Double bubbles sans toil and trouble: discrete circulation-preserving vortex sheets for soap films and foams[J]. ACM Transactions on Graphics, 2015, 34(4):1-9.

相关文章 15

[1]	丁筱玲,赵强,李贻斌,马昕. 基于模板匹配的改进型目标识别算法[J]. 山东大学学报(工学版), 2018, 48(2): 1-7.
[2]	邱路,叶银忠,姜春娣. 基于小波奇异熵和SOM神经网络的微电网系统故障诊断[J]. 山东大学学报(工学版), 2017, 47(5): 118-122.
[3]	王梦园,张雄,马亮,彭开香. 基于因果拓扑图的工业过程故障诊断[J]. 山东大学学报(工学版), 2017, 47(5): 187-194.
[4]	崔阳,张柯,姜斌. 具有切换拓扑结构的多智能体系统故障估计[J]. 山东大学学报(工学版), 2017, 47(5): 263-270.
[5]	郝崇清,王志宏. 基于复杂网络的癫痫脑电分类与分析[J]. 山东大学学报(工学版), 2017, 47(3): 8-15.
[6]	刘浩广,王海威,曾慧平,伍家驹. 高速公路网络演化模型的复杂性及连通性[J]. 山东大学学报(工学版), 2016, 46(4): 47-53.
[7]	雷正保, 宁寒. 新型柔性护栏端头结构的拓扑优化[J]. 山东大学学报(工学版), 2015, 45(6): 52-56.
[8]	王丹辉1,王安2*. 针对分组密码S盒的能量分析攻击效率研究[J]. 山东大学学报(工学版), 2014, 44(2): 6-11.
[9]	叶雯,云挺*,业宁. 基于点云数据的立木树干局部曲面拟合及拓扑结构[J]. 山东大学学报(工学版), 2013, 43(2): 42-47.
[10]	王艳超,杨立才*,刘澄玉. 基于模板匹配和镜像延拓的两阶段经验模态分解算法[J]. 山东大学学报(工学版), 2012, 42(6): 69-73.
[11]	王利平1,2,吕新虎2*,李光2,邓爱霞2. 基于RAFT聚合的蜂窝状有序多孔膜的制备及表征[J]. 山东大学学报(工学版), 2012, 42(5): 113-117.
[12]	黄金鑫1,张黎1,于春辉1,李庆民1,程艳2. 自供能转换器调理单元的等效建模与拓扑优化[J]. 山东大学学报(工学版), 2012, 42(2): 138-142.
[13]	于奎龙,范同祥*. 蝶翅二维光子晶体结构Y2O3:Eu3+的仿生制备[J]. 山东大学学报(工学版), 2012, 42(1): 121-126.
[14]	龚宇雷1,2,谭兴国2,李庆民2,王辉2,孙勇3. 用于电流输出型电压源逆变器的三相四线桥保护拓扑及参数选择方法[J]. 山东大学学报(工学版), 2011, 41(6): 128-135.
[15]	于江德1,周宏宇1,余正涛2. 汉语词性标注的特征工程[J]. 山东大学学报(工学版), 2011, 41(6): 12-17.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed