https://i.sstatic.net/L7Zmz.jpg
Hey there!
For the past month, I've been diligently researching various sources in hopes of finding a solution to my unique problem. Here's the issue I'm grappling with:
In the context of a mesh represented as buffer geometry (comprising 32-bit arrays of vertex coordinates and indices along with additional arrays like vertex normals, UVs, or tangents), how can I calculate a signed distance function (SDF) for a uniform grid of points surrounding the geometry?
Specifically, my goal is to create something akin to a MetaBall object within 3D engines such as Cinema4D or Blender. While I've successfully implemented distance functions for simple geometric primitives, generating an SDF for arbitrary meshes has proven challenging due to the brute force approach required - testing distances for every triangle against each grid point results in performance issues when dealing with complex meshes.
Upon further research, I came across tree-like structures like Octrees, KD-trees, BSP-trees, or AABB-trees. Additionally, I encountered articles on the Fast-Sweeping algorithm, designed to solve the Eikonal equation, which involves setting grid points along the boundary (or nearest to the mesh) to 0 and others to infinity before iteratively solving the hyperbolic boundary value problem using Gauss-Seidel iterations. I also discovered an open-source implementation of a mesh SDF method within the CGAL library. Another avenue considered was leveraging shader libraries like GLSL for GPU-accelerated tree construction, although I lack experience working with shaders in JS or TS projects.
My challenge lies not only in selecting the optimal method but in effectively implementing it. For instance:
If I were to pursue the Fast-Marching Method, I would need to iterate through all triangles and, for each one, cycle through individual grid points to interpolate values based on intersected cell vertices. This approach appears time-consuming and unsuitable for real-time applications.
While exploring examples of Ray Marching SDF computation in Unity, I stumbled upon GPU-based computations capabilities without fully grasping the parallel computing limitations or processes involved. Is it feasible to parallelize distance computations per triangle and subsequently sort these distances for each grid point efficiently? And if so, how could I integrate this into a TypeScript project?
Considering the creation of an AABB-tree around mesh triangles, locating the closest leaf from a given grid point and calculating the Euclidean distance to the contained triangle seems promising. However, the complexity analysis suggests potential drawbacks compared to a brute force approach, leading me to question its effectiveness.
As I contemplate merging multiple approaches, the overwhelming nature of the task becomes evident. The prospect of utilizing the CGAL library or adapting it for my project presents challenges due to dependency complexities within the existing C++ codebase. Has anyone navigated a similar terrain before? What recommendations do you have?
Appreciate any insights shared.