A Scalable, Parallel Algorithm for Signed Distance Function Computation in a Novel Computer-Aided Engineering Framework

Abstract

This study presents an innovative approach to bridge the gap between computer-aided design (CAD) and computer-aided engineering (CAE) by utilizing the signed distance function (SDF) as a geometric representation for CAE. We propose an efficient parallel computation algorithm for generating the SDF representation from a CAD model. It comprises three components: the construction of a globally defined SDF from a given set of oriented point clouds through parallel computation of local SDFs, the application of a multi-resolution fast sweeping method to compute local SDFs, and the design of a three-dimensional interval tree to expedite SDF queries. The algorithm’s effectiveness and precision are substantiated through a series of experiments involving various CAD models. The numerical partial differential equation (PDE) results offer preliminary evidence of the feasibility and practicality of a novel CAE framework grounded on the SDF representation. This proposed method ultimately fosters a seamless integration between CAD and CAE through the SDF representation.

Keywords

Signed distance function / Computer-aided design / Computer-aided engineering / Parallel computation / 65D17 / 65M99

References

[1] COMSOL AB: COMSOL Multiphysics® v. 6.0, Stockholm, Sweden. https://cn.comsol.com/.

[2] Adalsteinsson D, Sethian JA. A fast level set method for propagating interfaces. J. Comput. Phys.. 1995, 118(2): 269-277.

[3] Bak S, McLaughlin J, Renzi D. Some improvements for the fast sweeping method. SIAM J. Sci. Comput.. 2010, 32(5): 2853-2874.

[4] Belyaev A, Fayolle P-A. An admm-based scheme for distance function approximation. Numer. Algorithms. 2020, 84: 983-996.

[5] Bender, J., Kugelstadt, T., Weiler, M., Koschier, D.: Volume maps: An implicit boundary representation for SPH. In: Proceedings of the 12th ACM SIGGRAPH Conference on Motion, Interaction and Games, pp. 1–10. (2019)

[6] Burtsev SV, Kuzmin YP. An efficient flood-filling algorithm. Comput. Graph.. 1993, 17(5): 549-561.

[7] Calakli F, Taubin G. SSD: smooth signed distance surface reconstruction. Comput. Graph. Forum. 2011, 30: 1993-2002.

[8] Calakli F, Taubin G. SSD-C: smooth signed distance colored surface reconstruction. 2012, New York, Springer

[9] Chabra R, Lenssen JE, Ilg E, Schmidt T, Straub J, Lovegrove S, Newcombe R. Deep Local Shapes: Learning Local SDF Priors for Detailed 3D Reconstruction. 2020, New York, Springer

[10] Chen, Z., Chen, S., Schmid, C., Laptev, I.: gSDF: Geometry-driven signed distance functions for 3D hand-object reconstruction. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 12890–12900. (2023)

[11] Chen J, Chi X, Yang Z. Bridging traditional and machine learning-based algorithms for solving PDEs: the random feature method. J. Mach. Learn.. 2022, 1(3): 268-298.

[12] Cheng Z, Liu S, Jiang Y, Lu J, Zhang M, Zhang S. A high order boundary scheme to simulate complex moving rigid body under impingement of shock wave. Appl. Math. Mech.. 2021, 42(6): 841-854.

[13] Chi X, Chen J, Yang Z. The random feature method for solving interface problems. Comput. Methods Appl. Mech. Eng.. 2024, 420. 116719

[14] Chopp DL. Computing minimal surfaces via level set curvature flow. 1991, Berkeley, University of California

[15] Chou, G., Bahat, Y., Heide, F.: Diffusion-SDF: Conditional generative modeling of signed distance functions. In: Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 2262–2272. (2023)

[16] Cui D, Wang B, Li M. Study of Mesh Generation for Complex Geometries. 2013, New York, Springer

[17] Detrixhe M, Gibou F. Hybrid massively parallel fast sweeping method for static Hamilton-Jacobi equations. J. Comput. Phys.. 2016, 322: 199-223.

[18] Detrixhe M, Gibou F, Min C. A parallel fast sweeping method for the Eikonal equation. J. Comput. Phys.. 2013, 237: 46-55.

[19] Diamantopoulos G, Hössinger A, Selberherr S, Weinbub J. A shared memory parallel multi-mesh fast marching method for re-distancing. Adv. Comput. Math.. 2019, 45: 2029-2045.

[20] Fayolle P-A, Belyaev AG. p-Laplace diffusion for distance function estimation, optimal transport approximation, and image enhancement. Comput. Aided Geom. Des.. 2018, 67: 1-20.

[21] Fredman ML, Tarjan RE. Fibonacci heaps and their uses in improved network optimization algorithms. J. Assoc. Comput. Mach.. 1987, 34(3): 596-615.

[22] Gomez H, De Lorenzis L. The variational collocation method. Comput. Methods Appl. Mech. Eng.. 2016, 309: 152-181.

[23] Gómez JV, Álvarez D, Garrido S, Moreno L. Fast methods for Eikonal equations: an experimental survey. IEEE Access. 2019, 7: 39005-39029.

[24] Hughes TJR, Cottrell JA, Bazilevs Y. Isogeometric analysis: CAD, finite elements, nurbs, exact geometry and mesh refinement. Comput. Methods Appl. Mech. Eng.. 2005, 194(39–41): 4135-4195.

[25] Jeong W-K, Whitaker RT. A fast iterative method for Eikonal equations. SIAM J. Sci. Comput.. 2008, 30(5): 2512-2534.

[26] Jones MW, Bærentzen JA, Sramek M. 3D distance fields: a survey of techniques and applications. IEEE Trans. Visual Comput. Graphics. 2006, 12(4): 581-599.

[27] Kazhdan, M., Bolitho, M., Hoppe, H.: Possion surface reconstruction. In: Proceedings of the Fourth Eurographics Symposium on Geometry Processing, pp. 61–70. (2006)

[28] Kim S. An O(N) level set method for Eikonal equations. SIAM J. Sci. Comput.. 2001, 22(6): 2178-2193.

[29] Koschier, D., Bender, J.: Density maps for improved SPH boundary handling. In: Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, pp. 1–10. (2017)

[30] Lai Z, Zhao J, Zhao S, Huang L. Signed distance field enhanced fully resolved cfd-dem for simulation of granular flows involving multiphase fluids and irregularly shaped particles. Comput. Methods Appl. Mech. Eng.. 2023, 414. 116195

[31] Li, X., Guo, X., Wang, H., He, Y., Gu, X., Qin, H.: Harmonic volumetric mapping for solid modeling applications. In: Proceedings of the 2007 ACM Symposium on Solid and Physical Modeling, pp. 109–120. (2007)

[32] Li, Y., Liu, Y., Lu, Y., Zhang, S., Cai, S., Zhang, Y.: High-fidelity 3D model compression based on key spheres. Preprint at arXiv:2201.07486 (2022)

[33] Ma, B., Zhou, J., Liu, Y.-S., Han, Z.: Towards better gradient consistency for neural signed distance functions via level set alignment. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition., pp. 17724–17734. (2023)

[34] Malik MR, Zang TA, Hussaini MY. A spectral collocation method for the Navier-Stokes equations. J. Comput. Phys.. 1985, 61(1): 64-88.

[35] Martin, T., Cohen, E., Kirby, M.: Volumetric parameterization and trivariate B-spline fitting using harmonic functions. In: Proceedings of the 2008 ACM Symposium on Solid and Physical Modeling, pp. 269–280. (2008)

[36] Osher S, Sethian JA. Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations. J. Comput. Phys.. 1988, 79(1): 12-49.

[37] Pal A, Pal M. Interval tree and its applications. Adv. Model. Optim.. 2009, 11(3): 221-224

[38] Park, J.J., Florence, P., Straub, J., Newcombe, R., Lovegrove, S.: DeepSDF: Learning continuous signed distance functions for shape representation. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 165–174. (2019)

[39] Peng C, Liu S, Yang Z. SDF-Based ILW: inverse lax-wendroff method with the signed distance function representation of the geometric boundary. Commun. Comput. Phys.. 2023, 33(2): 538-567.

[40] Rasch C, Satzger T. Remarks on the O(N) implementation of the fast marching method. J. Inst. Math. Appl.. 2009, 29(3): 806-813

[41] Sethian JA. A fast marching level set method for monotonically advancing fronts. Proc. Natl. Acad. Sci.. 1996, 93(4): 1591-1595.

[42] Shim, J., Kang, C., Joo, K.: Diffusion-based signed distance fields for 3D shape generation. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 20887–20897. (2023)

[43] Sitzmann V, Martel J, Bergman A, Lindell D, Wetzstein G. Implicit neural representations with periodic activation functions. Adv. Neural. Inf. Process. Syst.. 2020, 33: 7462-7473

[44] Sommer, C., Sang, L., Schubert, D., Cremers, D.: Gradient-SDF: A semi-implicit surface representation for 3D reconstruction. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 6280–6289 (2022)

[45] Taghavi R. Automatic, parallel and fault tolerant mesh generation from CAD. Eng. Comput.. 1996, 12(3): 178-185.

[46] Tang Y, Feng J. Multi-scale surface reconstruction based on a curvature-adaptive signed distance field. Comput. Graph.. 2018, 70: 28-38.

[47] Tsitsiklis J. Efficient algorithms for globally optimal trajectories. IEEE Trans. Autom. Control. 1995, 40: 1528-1538.

[48] Tugurlan, M.C.: Fast marching methods-parallel implementation and analysis. In: PhD thesis, Louisiana State University and Agricultural & Mechanical College (2008)

[49] Uzu A, Sugiura N, Masaki H. Development of a new mesh generation technique with reduced number of triangles for accurate CAE. Soc. Automot. Eng. Jpn. Rev.. 1995, 1(16): 101

[50] Weinbub, J., Hössinger, A.: Shared-memory parallelization of the fast marching method using an overlaping domain-decomposition approach. In: Proceedings of the 24th High Performance Computing Symposium, pp. 1–8. (2016)

[51] Winchenbach R, Akhunov R, Kolb A. Semi-analytic boundary handling below particle resolution for smoothed particle hydrodynamics. ACM Trans. Graph.. 2020, 3961-17.

[52] Xia, J., He, Y., Yin, X., Han, S., Gu, X.: Direct-product volumetric parameterization of handlebodies via harmonic fields. IEEE (2010)

[53] Xia J, He Y, Han S, Fu C-W, Luo F, Gu X. Parameterization of Star-shaped Volumes Using Green’s Functions. 2010, New York, Springer.

[54] Xu G, Mourrain B, Duvigneau R, Galligo A. Analysis-suitable volume parameterization of multi-block computational domain in isogeometric applications. Comput. Aided Des.. 2013, 45(2): 395-404.

[55] Yang J, Stern F. A highly scalable massively parallel fast marching method for the Eikonal equation. J. Comput. Phys.. 2017, 332: 333-362.

[56] Yao, S., Yang, F., Cheng, Y., Mozerov, M.G.: 3D shapes local geometry codes learning with SDF. In: Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 2110–2117. (2021)

[57] Yatziv L, Bartesaghi A, Sapiro G. O(N) implementation of the fast marching algorithm. J. Comput. Phys.. 2006, 212(2): 393-399.

[58] Zhang, J., Yao, Y., Quan, L.: Learning signed distance field for multi-view surface reconstruction. In: Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 6525–6534. (2021)

[59] Zhao H. A fast sweeping method for Eikonal equations. Math. Comput.. 2005, 74(250): 603-627.

[60] Zhao H. Parallel implementations of the fast sweeping method. J. Comput. Math.. 2007, 25: 421-429

[61] Zhu J, Shu C-W. A new type of multi-resolution WENO schemes with increasingly higher order of accuracy. J. Comput. Phys.. 2018, 375: 659-683.

Funding

National Key R&D Program of China(Nos. 2022YFA1005201)

National Key R&D Program of China(2022YFA1005203)

Key Laboratory of South China Sea Fishery Resources Exploitation and Utilization, Ministry of Agriculture and Rural Affairs, P. R. China(Nos. 92270205)

Major Project of Science & Technology of Anhui Province(Nos. 2023z020008)

RIGHTS & PERMISSIONS

School of Mathematical Sciences, University of Science and Technology of China and Springer-Verlag GmbH Germany, part of Springer Nature