32

如果我使用构造立体几何技术构建形状，我如何构建用于渲染的线框网格？我知道直接渲染 CSG 形状的算法，但我只想将它转换为线框网格，以便我可以“正常”渲染它

添加更多细节。给定形状的描述，例如“此处为立方体，此处与球体相交，此处减去圆柱体”，我希望能够计算多边形网格。

4

7 回答 7

22

有两种主要方法。如果您有一组多边形形状，则可以为每个形状创建一个 BSP 树，然后可以合并 BSP 树。来自维基百科，

1990 Naylor、Amanatides 和 Thibault 提供了一种算法，用于合并两个 bsp 树以从两个原始树中形成一个新的 bsp 树。这提供了许多好处，包括：将由 BSP 树表示的移动对象与静态环境（也由 BSP 树表示）相结合，对多面体进行非常有效的 CSG 操作，O(log n * log n) 中的精确碰撞检测，以及正确排序包含在两个相互穿透的物体中的透明表面（已用于 X 射线视觉效果）。

本文可在此处找到合并 BSP 树产生多面体集操作。

或者，每个形状都可以表示为空间上的函数（例如到表面的有符号距离）。只要将曲面定义为函数等于 0 的位置，就可以使用 (MIN == intersection)、(MAX == union) 和 (NEGATION = not) 运算符组合函数以模拟集合操作。然后可以使用诸如 Marching Cubes 之类的技术将生成的表面提取为组合函数等于 0 的位置。也可以使用更好的表面提取方法，例如 Dual Marching Cubes 或 Dual Contouring。当然，这将导致真实 CSG 表面的离散近似。我建议使用Dual Contouring，因为它能够重建尖锐的特征，例如立方体的角。

于 2010-01-04T23:40:51.633 回答
4

这些库似乎可以满足您的要求：

www.solidgraphics.com/SolidKit/carve-csg.com/gts.sourceforge.net/

于 2010-04-25T17:53:17.033 回答
3

另见“三角多面体的构造实体几何”（1990 年）Philip M. Hubbard doi:10.1.1.34.9374

于 2010-07-11T08:44:36.367 回答
2

以下是一些可能有用的 Google Scholar 链接。

根据我对摘要的了解，基本思想是从 CSG 模型中可用的体积数据生成点云，然后使用一些更常见的算法生成 3D 面网格以适应该点云。

编辑：做一些进一步的研究，这种操作称为“从 CSG 转换为 B-Rep（边界表示）”。对该字符串的搜索会产生一个有用的 PDF：

http://www.scielo.br/pdf/jbsmse/v29n4/a01v29n4.pdf

并且，为了进一步了解，关键算法被称为“ Marching Cubes Algorithm ”。本质上，CSG 模型用于创建具有体素的对象的体积模型，然后使用 Marching Cubes 算法从体素数据中创建 3D 网格。

于 2010-01-04T23:23:26.477 回答
1

如果您可以将输入基元转换为多面体网格，那么您可以使用 libigl 的 C++ 网格布尔例程。下面计算一个网格 (VA,FA) 和另一个网格 (VB,FB) 的并集：

igl::mesh_boolean(VA,FA,VB,FB,"union",VC,FC);

其中 VA 是顶点位置的#VA x 3 矩阵，FA 是 VA 的三角形索引的#FA x 3 矩阵，依此类推。libigl 中使用的技术与乔的回答中提到的两种不同。所有三角形对彼此相交（使用空间加速度），然后将生成的子三角形分类为是否属于输出表面。

于 2015-04-20T21:32:22.843 回答
1

您可以尝试对每个基元进行三角剖分（四面体化），然后对四面体网格执行布尔运算，这“更容易”，因为您只需要担心四面体-四面体运算。然后您可以执行边界提取以获取 B-rep。由于您通过分析了解图元的形状，因此您可以构建图元的自定义四面体以满足您的需求，而不是依赖网格生成库。

例如，假设您的对象是立方体和圆柱体的并集，并且假设您有两个对象的四面体。为了计算结果对象的边界表示，首先标记每个原始对象的四面体的所有边界面。然后，您执行并集操作：如果两个四面体不相交，则无需执行任何操作；两个四面体都必须存在于生成的多面体中。如果它们相交，则需要处理许多案例（可能大约十几个）。在每种情况下，两个四面体的体积都需要以尊重表面约束的方式重新进行三角剖分。由于您只需要担心四面体，而不是更复杂的形状，因此这有点容易。

于 2010-01-04T23:43:51.893 回答
1

我对 BRL-CAD 应用程序 MGED 很幸运，我可以通过使用 CSG 与平面相交来构造凸多面体，然后使用命令行 g-stl 命令提取边界表示。检查http://brlcad.org/ Malcolm

于 2012-05-08T00:03:01.733 回答