JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE) ›› 2016, Vol. 46 ›› Issue (4): 15-20.doi: 10.6040/j.issn.1672-3961.0.2016.028

Previous Articles     Next Articles

Highly efficient algorithm for tracking explicit surface to process complex topological events

HOU Yan1, YANG Meng2   

  1. 1. College of Information Science and Engineering, Qilu Normal University, Jinan 250013, Shandong, China;
    2. Institute of Automation, Chinese Academy of Sciences, Beijing 100190, China
  • Received:2016-01-19 Online:2016-08-20 Published:2016-01-19

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

CLC Number: 

  • TP391
[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.
[1] DING Xiaoling, ZHAO Qiang, LI Yibin, MA Xin. Modified target recognition algorithm based on template matching [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(2): 1-7.
[2] QIU Lu, YE Yinzhong, JIANG Chundi. Fault diagnostic method for micro-grid based on wavelet singularity entropy and SOM neural network [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(5): 118-122.
[3] HAO Chongqing, WANG Zhihong. Classification and analysis of epileptic EEG based on complex networks [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(3): 8-15.
[4] LIU Haoguang, WANG Haiwei, ZENG Huiping, WU Jiaju. The complicated characteristics and connecting performance of the highway network evolution model [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(4): 47-53.
[5] LEI Zhengbao, NING Han. Topology optimization of new flexible structure guardrail ends [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(6): 52-56.
[6] WANG Danhui1, WANG An2*. The efficiency of power analysis attack based on S-boxes of block ciphers [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2014, 44(2): 6-11.
[7] YE Wen, YUN Ting*, YE Ning. Local surface fitting and topology structure based on timber trunk of point cloud [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2013, 43(2): 42-47.
[8] WANG Yan-chao, YANG Li-cai*, LIU Cheng-yu. A two-stage EMD algorithm based on template matching and mirror extension [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(6): 69-73.
[9] WANG Li-ping1,2, Lü Xin-hu2*, LI Guang 2, DENG Ai-xia2. Preparation and characterization of honeycomb microporous films based on reversible addition fragmentation chain transfer (RAFT) polymerization [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(5): 113-117.
[10] HUANG Jin-xin1, ZHANG Li1, YU Chun-hui1, LI Qing-min1, CHENG Yan2. Equivalent modeling and topological optimization for the conditioning unit of an energy harvesting converter [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(2): 138-142.
[11] GONG Yu-lei1,2, TAN Xing-guo2, LI Qing-min2, WANG Hui2, SUN Yong3. A bridge-type protection topology for 3-phase 4-wire current  output inverters and its parameter selection method [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2011, 41(6): 128-135.
[12] YU Jiang-de1, ZHOU Hong-yu1, YU Zheng-tao2. Feature engineering for Chinese part-of-speech tagging [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2011, 41(6): 12-17.
[13] LIU Feng, SHI Yuan-chang*, ZHANG Bing-chang, SUN Li-bo. Preparation of straight and orderly polypyrrole microrods through soft template methods [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2011, 41(1): 62-65.
[14] LIU Hui-hui, FAN Tong-xiang *. Enhanced light harvesting and photocatalytic property of TiO2 architecture derived from butterfly wings [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2011, 41(1): 58-61.
[15] YU Jiang-de1, SUI Dan1, FAN Xiao-zhong2. Word-position-based tagging for Chinese word segmentation [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(5): 117-122.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] LI Ke,LIU Chang-chun,LI Tong-lei . Medical registration approach using improved maximization of mutual information[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 107 -110 .
[2] YUE Yuan-Zheng. Relaxation in glasses far from equilibrium[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(5): 1 -20 .
[3] CHENG Daizhan, LI Zhiqiang. A survey on linearization of nonlinear systems[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 26 -36 .
[4] WANG Yong, XIE Yudong. Gas control technology of largeflow pipe[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 70 -74 .
[5] LIU Xin 1, SONG Sili 1, WANG Xinhong 2. [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 98 -100 .
[6] . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 104 -107 .
[7] CHEN Huaxin, CHEN Shuanfa, WANG Binggang. The aging behavior and mechanism of base asphalts[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 125 -130 .
[8] . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 131 -136 .
[9] LI Shijin, WANG Shengte, HUANG Leping. Change detection with remote sensing images based on forward-backward heterogenicity[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(3): 1 -9 .
[10] ZHAO Ke-Jun, WANG Xin-Jun, LIU Xiang, CHOU Yi-Hong. Algorithms of continuous top-k join query over structured overlay networks[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(5): 32 -37 .