gpt4 book ai didi

typescript - 计算三角形网格的 SDF 的最有效方法

转载 作者:行者123 更新时间:2023-12-03 14:55:31 26 4
gpt4 key购买 nike

SDF from triangles, edges and vertices

你好。

在过去的一个月里,我一直在从各种来源收集信息,但没有找到适合我的特定问题的想法。所以这里是问题的表述:

给定一个缓冲区几何形式的网格(顶点坐标和顶点索引的 32 位数组 + 附加数组,例如顶点法线、uvs 或切线),计算围绕网格的均匀点网格的有符号距离函数 (SDF)几何学。

更具体地说,我打算在 Maxon 的 Cinema4D 或 Blender 等 3D 引擎中创建类似于 MetaBall 对象的东西。我已经成功地为所有几何图元实现了距离函数,但是任意网格 SDF 需要我实现一种蛮力方法 - 测试每个网格点的每个网格三角形的距离 - 当然,对于复杂的,这会变得非常慢网格。

现在,我回想起来,这些问题中的大多数都需要构建一个树状结构,例如八叉树、KD 树、BSP 树或 AABB 树。然后找了几篇所谓的Fast-Sweeping algorithm (用于求解 Eikonal 方程),它首先需要用 0 填充位于边界上的网格点(在我的情况下为网格,或最接近网格),其余网格点为大值(无穷大),然后求解非-迭代线性双曲边值问题(Gauss-Seidel)。我还在 CGAL library 中找到了网格 SDF 方法的开源实现.或者,我也考虑过使用一些着色器库(如 GLSL),也许尝试使用 GPU 构建树,但我从未在 JS 或 TS 项目中使用过着色器。

我一直坚持的步骤不仅仅是选择最好的选择,而且实际上实际上至少有效地使用了这些方法中的一种。例如:

  • 如果我想实现 Fast-Marching Method ,我必须遍历所有三角形,然后对于每个三角形,遍历所有网格点 Gijk,并使用类似于 Marching Cubes 查找表的东西来查找网格单元格交叉点(但有更多选项),我会插入值对于相交的单元格顶点,接近于 0。我有一种感觉,这会花费不必要的时间,并且被证明不适合实时更新。
  • 我设法找到了一些 Ray Marching SDF 的例子Unity 中的计算。此外,由于我从未尝试过直接在 GPU 上计算任何东西,因此我不知道例如并行计算的限制实际上是什么,我也不了解此类计算是如何进行的。我可以并行计算到每个三角形的距离,然后对每个网格点 Gijk 的所有距离进行快速排序吗?如果是这样,我如何将它包含到 TypeScript 项目中?
  • 假设我构建了一个 AABB-tree围绕网格中的所有三角形(应该是 O(n * log(n)) ),然后给定一个网格点 Gijk(假设树根是一个包含 Gijk 和所有三角形的框),我会搜索最近的叶子并计算到包含在其中的三角形的欧几里得距离(或者如果有多个,则选择)。 (如果我弄错了,请纠正我)搜索应该是 O(log(n)),如果用户移动网格,更新将花费 O(n),其中 n 是三角形的数量。因此,如果 m 是网格大小,那么整个 SDF 计算将是 O(m * n * log(n)) ?这看起来不像是对 O(n * m) 蛮力方法的改进,但也许我把复杂性弄错了。

  • 我想过结合多种方法,但这似乎非常耗时。我还考虑过使用 CGAL 库,或者可能出于我的项目的目的对其进行重构,但我发现由于库内的所有依赖关系,很难理解 C++ 代码。
    你们中有人做过类似的事情吗?你会推荐什么?

    谢谢你的所有见解。

    最佳答案

    我使用由三(四)个主要步骤概述的方法解决了这个问题:

  • 生成网格三角形汤的AABB树
  • 每当立方体与网格相交(使用 AABB 树快速相交)形成八叉树时,使用 AABB 树分割规则边界立方体。当分割到达叶子时,计算精确的平方距离(立方体质心到三角形)并取最小的平方根,将其写入基于立方体最小-最大坐标的规则网格。
  • 使用网格相交体素上的精确距离值和其他地方的大值,运行快速扫描算法 8 次并用距离值填充标量网格。
  • (可选)填充否定距离网格的外部体素,以确保标记的初始体素(具有精确值)轮廓内的体素具有负号(不幸的是,这是分辨率 > 100^3 的网格最慢的部分)

  • 要更详细地了解我的计算时间实现,请随时阅读我的​​博客文章:
    https://mshgrid.com/blog/
    感谢您的点赞和评论:)。

    关于typescript - 计算三角形网格的 SDF 的最有效方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58100765/

    26 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com