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 回答