Applications of Voronoi diagram in the Moving particle semi-implicit method

ZHOU Ziqi; SUN Yijie; SUN Zhongguo; XI Guang

doi:null

您当前的位置：

首页 >

文章列表页 >

Applications of Voronoi diagram in the Moving particle semi-implicit method

更新时间：2025-11-18

- Applications of Voronoi diagram in the Moving particle semi-implicit method
- JOURNAL OF XI’AN JIAOTONG UNIVERSITY (2025)
- 作者机构：
  
  西安交通大学能源与动力工程学院,陕西省西安市710049
- 作者简介：
- 基金信息：
- DOI：
  CLC：
- Received：14 August 2025，
  
  Revised：2025-10-27，
  
  Accepted：14 November 2025，
- 稿件说明：
移动端阅览
ZHOU Ziqi, SUN Yijie, SUN Zhongguo, et al. Applications of Voronoi diagram in the Moving particle semi-implicit method[J/OL]. JOURNAL OF XI’AN JIAOTONG UNIVERSITY, 2025.
DOI：

ZHOU Ziqi, SUN Yijie, SUN Zhongguo, et al. Applications of Voronoi diagram in the Moving particle semi-implicit method[J/OL]. JOURNAL OF XI’AN JIAOTONG UNIVERSITY, 2025. DOI：

摘要

为了优化移动粒子半隐式法的空间拓扑关系相关算法，本文将Voronoi图应用于移动粒子半隐式法（MPS）中的邻居粒子搜索、表面粒子判定及粒子迁移三个关键环节。通过构建粒子Voronoi图并利用其拓扑关系层级进行邻居粒子搜索；针对表面粒子识别问题，提出了基于Voronoi图单元结构的判别方法；结合Lloyd松弛法与格林-高斯公式，推导出基于Voronoi图的粒子迁移方法。结果表明：基于Voronoi图的粒子搜索相较于传统全配对方法有159倍以上效率提升；基于Voronoi图的粒子判断方法较传统数密度方法更准确，计算效率是几何判别法的43.3倍；基于Voronoi图的粒子迁移，相较于传统粒子迁移方式，能够有效减小系统扰动，在保持自由液面的光滑性与无重叠特性的同时也有6倍以上的计算效率优势。综上所述，Voronoi图的良好的空间分割特性在移动粒子半隐式法中具有良好的应用前景。

Abstract

To optimize the algorithms for establishing and analyzing spatial topology in the Moving Particle Semi-implicit (MPS) method

this paper applies the Voronoi diagram to three key components: neighbor particle search

surface particle detection

and particle shifting. The specific approaches are as follows: a particle Voronoi diagram is constructed to facilitate neighbor particle search by leveraging its inherent topological relationships; a novel method based on Voronoi cell structure is proposed to address the challenge of surface particle detection; and a particle shifting scheme derived from the Voronoi diagram is developed by integrating the Lloyd relaxation algorithm with the Green-Gauss formula. The results demonstrate that: the Voronoi-based particle search achieves an efficiency improvement of over 159 times compared to the traditional all-pair search method; the Voronoi-based surface particle detection is more accurate than the conventional particle number density method and computes 43.3 times faster than the geometric method; furthermore

the Voronoi-based particle shifting effectively reduces system disturbance while preserving the smoothness and non-overlapping characteristics of the free surface

also yielding a computational efficiency advantage exceeding 6 times compared to traditional shifting approaches. In conclusion

the proficient spatial partitioning properties of the Voronoi diagram present promising potential for its application within the MPS framework.

关键词

Keywords

references

Lucy LB . A numerical approach to the testing of the fission hypothesis [J ] . The Astronomical Journal , 1977 , 82 : 1013 - 1024 .

Gingold RA , Monaghan JJ . Smoothed particle hydrodynamics-theory and application to non- spherical stars [J ] . Monthly Notices of the Royal Astronomical Society , 1977 , 181 : 375 - 389 .

Koshizuka S , Oka Y . Moving-particle semi-implicit method for fragmentation of incompressible fluid [J ] . Nuclear Science and Engineering , 1996 , 123 ( 3 ): 421 - 434 .

Koshizuka S , Nobe A , Oka Y . Numerical analysis of breaking waves using the moving particle semi-implicit method [J ] . International Journal for Numerical Methods in Fluids , 1998 , 26 ( 7 ): 751 - 769 .

Colagrossi A , Landrini M , Numerical simulation of interfacial flows by smoothed particle hydrodynamics . J. Comput . Phys . 2003 , 191 ( 2 ) () : 448 – 475 .

Duan GT , Yamaji A , Sakai M , An incompressible–compressible Lagrangian particle method for bubble flows with a sharp density jump and boiling phase change , Comput . Method . Appl. Mech. Engrg . 372 ( 2020 ) 113425 .

Sun ZG , Xi G , Chen X , Mechanism Study of Deformation and Mass Transfer for Binary Droplet Collisions with Particle Method , Phys . Fluids . 21 (3) (2009).

Adami S , Hu XY , Adams NA . A transport-velocity formulation for smoothed particle hydrodynamics [J ] . Journal of Computational Physics , 2013 , 241 : 292 - 307 .

Zhang C , Hu XY , Adams NA . A generalized transport velocity formulation for smoothed particle hydrodynamics [J ] . Journal of Computational Physics , 2017 , 337 : 216 - 232 .

Jandaghian M , Shakibaeinia A . An enhanced weakly-compressible MPS method for free-surface flows [J ] . Computer Methods in Applied Mechanics and Engineering , 2020 , 360 : 112771 .

Sun YJ , Xi G , Sun ZG . A generic smoothed wall boundary in multi-resolution particle method for fluid–structure interaction problem [J ] . Computer Methods in Applied Mechanics and Engineering , 2021 , 378 : 113726 .

Sun YJ , Xi G , Sun ZG . A fully Lagrangian method for fluid–structure interaction problems with deformable floating structure [J ] . Journal of Fluids and Structures , 2019 , 90 : 379 - 395 .

张帅 , 解利军 , 郑耀 . 基于移动粒子半隐式法的表面张力模拟 [J ] . 计算力学学报 , 2011 ( 03 ): 345 - 349 .

Zhang S , Xie LJ , Zheng Y . Simulation of surface tension force using moving particle semi-implicit method [J ] . Chinese Journal of Computational Mechanics , 2011 , 28 ( 3 ): 345 - 349 .

Gou W , Zhang S , Zheng Y . Implementation of the moving particle semi-implicit method for free-surface flows on GPU clusters [J ] . Computer Physics Communications , 2019 , 244 : 13 - 24 .

Khayyer A , Gotoh H . Enhancement of stability and accuracy of the moving particle semi-implicit method [J ] . Journal of Computational Physics , 2011 , 230 ( 8 ): 3093 - 3118 .

D. J. Muñoz , V. Springel , R. Marcus , M. Vogelsberger , L. Hernquist , Multidimensional , Compressible Viscous Flow on a Moving Voronoi Mesh , Mon . Not . R. Astron. Soc . 2013 , 428 ( 1 ) : 254 – 279 .

Gaburro E , A unified framework for the solution of hyperbolic PDE systems using high order direct Arbitrary-Lagrangian–Eulerian schemes on moving unstructured meshes with topology change , Arch . Comput . Method E . 2021 , 28 ( 3 ) : 1249 – 1321 .

Chartrand C , Perot JB , A Method for Generating Moving , Orthogonal , Area Preserving Polygonal Meshes , J . Comput . Phys . 454 ( 2022 ) 110940 .

Zhou J X , Wen J B , Zhang H Y , et al . A nodal integration and post-processing technique based on Voronoi diagram for Galerkin meshless methods [J ] . Computer Methods in Applied Mechanics and Engineering , 2003 , 192 ( 35/36 ): 3831 - 3843 .

Fu L , Hu X Y , Adams N A . A physics-motivated Centroidal Voronoi Particle domain decomposition method [J ] . Journal of Computational Physics , 2017 , 335 : 718 - 735 .

Egorova M S , Dyachkov S A , Parshikov A N , et al . Parallel SPH modeling using dynamic domain decomposition and load balancing displacement of Voronoi subdomains [J ] . Computer Physics Communications , 2019 , 234 : 112 - 125 .

Ji Z , Fu L , Hu X Y , et al . A Lagrangian Inertial Centroidal Voronoi Particle method for dynamic load balancing in particle-based simulations [J ] . Computer Physics Communications , 2019 , 239 : 53 - 63 .

Hess S , Springel V . Particle hydrodynamics with tessellation techniques [J ] . Monthly Notices of the Royal Astronomical Society , 2010 , 406 ( 4 ): 2289 - 2311 .

Fernández-Gutiérrez D , Souto-Iglesias A , Zohdi T I . A hybrid Lagrangian Voronoi–SPH scheme [J ] . Computational Particle Mechanics , 2018 , 5 ( 3 ): 345 - 354 .

Fernández-Gutiérrez D , ZohdI T I . Delta Voronoi smoothed particle hydrodynamics, δ-VSPH [J ] . Journal of Computational Physics , 2020 , 401 : 109000 .

Zhou Z , Han P , Sun Y , Sun Zo , Xi G , Incompressible-compressible moving particle and moving Voronoi mesh method for multiphase flow , Journal of Computational Physics , Volume 537 , 2025 , 114062 .

Fortune S , A sweepline algorithm for Voronoi diagrams , Algorithmica . 2 ( 1987 ) 153 – 174 .

Han PD , Liu QX , Zhang K , et al . Enhanced Dirichlet boundary condition in MPS method for free-surface flow with negative pressure [J ] . Computers & Fluids , 2023 , 256 : 105820 .

韩沛东，刘启新，周子棋等．负压梯度下自由面流动模拟的无网格粒子法Dirichlet边界条件［J］．西安交通大学学报， 2022 , 56 ( 8 ): 141 - 148 .

Han PD , Liu QX , Zhou ZQ et al . Dirichlet boundary conditions in meshless particle methods for free surface flow Simulation under negative pressure gradient [J ] . Journal of Xi’an Jiaotong University , 2022 , 56 ( 8 ): 141 - 148 .

Shibata K , Masaie I , Kondo M , et al . Improved pressure calculation for the moving particle semi-implicit method [J ] . Computational Particle Mechanics , 2015 , 2 ( 1 ): 91 - 108 .

张凯 , 孙中国 , 席光 . 移动粒子半隐式法核函数特征对压力求解稳定性的影响 [J ] . 西安交通大学学报 , 2019 , 53 ( 9 ): 1 - 6 .

Zhang K , Sun ZG , Xi G . Influence of the kernel function characteristics on the stability of pressure solution of moving particle semi-implicit method [J ] . Journal of Xi’an Jiaotong University , 2019 , 53 ( 9 ): 1 - 6 .

Lloyd S . Least square quantization in PCM, IEEE Trans . Inform. Theory . 1982 , 28 : ) 129 – 137 .

Wu G Q , Tian H Y , Lu G , et al . ParVoro++: A scalable parallel algorithm for constructing 3D Voronoi tessellations based on kd-tree decomposition [J ] . Parallel Computing , 2023 , 115 : 102995 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Applications of Voronoi Diagram in the Moving Particle Semi-Implicit Method

A Modeling Method of 2D Complex Geometry for Particle Method

Study on the Thermodynamic Properties in the Anomalous Region of Supercritical Water

A Structure-Semantics-Residual Collaborative Image Compression Framework：Towards Privacy Protection and High-Fidelity Reconstruction

Effects of Steam Addition on the Swirl Combustion and Emission Characteristics of Cracked Ammonia

Related Author

ZHOU Ziqi

SUN Yijie

SUN Zhongguo

XI Guang

KANG Jiangnan

SUN Yijie

SUN Zhongguo

XI Guang

Related Institution

School of Energy and Power Engineering, Xi'an Jiaotong University

(School of Energy and Power Engineering, Xi'an Jiaotong University,,)

⁰