建设性实体几何网格

Question

建设性实体几何网格

algorithmlanguage-agnosticgraphicsgeometrywireframe

33

如果我使用构造实体几何技术来构建一个形状，那么如何构建一个用于渲染的线框网格呢？我知道有直接渲染CSG形状的算法，但我想将其转换为线框网格，以便我可以正常地渲染它。

再补充一点细节。假设给定一个形状的描述，例如“这里是一个立方体，在这里与一个球相交，在这里减去一个圆柱体”，我希望能够计算出一个多边形网格。

- Martin

7个回答

4

这些库似乎可以满足你的需求：

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

- Roman

哇，我已经放弃这个问题会被回答了。幸运的是，你在我重新对这个项目产生兴趣时回答了我的问题。我会去检查一下它们是否符合我的需求。谢谢！ - Martin

GTS库是开源且快速的，看起来很棒。现在看看能否在C#中运行它 ;) - Martin

不幸的是，我无法使用C#使其工作。我还意识到我不能使用任何本地代码库，因为需要在Xbox上运行，所以只能使用托管代码 :( - Martin

SolidKit库也提供了.NET版本。但它不是免费的。 - Roman

3

请参考菲利普·M·哈伯德（Philip M. Hubbard）于1990年发表的文章《针对三角形多面体的建设性固体几何》。 doi:10.1.1.34.9374

- John Pritchard

2

这里是一些可能有用的Google学术链接。

从摘要中可以看出，基本思想是从CSG模型中可用的体积数据生成点云，然后使用一些更常见的算法在三维空间中生成面网格来适应该点云。

编辑：做进一步的研究，这种操作被称为“从CSG到B-Rep（边界表达）的转换”。搜索该字符串会导向一个有用的PDF文件：

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

而且，进一步的信息是，关键算法被称为“Marching Cubes Algorithm”。基本上，CSG模型用于使用体素创建物体的体积模型，然后使用Marching Cubes算法将体素数据转换为3D网格。

- e.James

1

如果您能将输入的基元转换为多面体网格，则可以使用libigl的C ++网格布尔运算例程。以下代码计算了网格（VA，FA）和另一个网格（VB，FB）的并集：

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

VA是一个#VA乘3的顶点位置矩阵，FA是一个#FA乘3的三角形索引矩阵，等等。libigl中使用的技术与Joe答案中提到的两种技术不同。所有的三角形对都会相互交叉（使用空间加速），然后产生的子三角形被归类为属于输出表面或不属于输出表面。

- Alec Jacobson

1

你可以尝试对每个基元进行三角剖分（四面体化），然后在四面体网格上执行布尔运算，这样会比较“容易”，因为你只需要考虑四面体-四面体的操作。然后，你可以执行边界提取以获取B-rep。由于你已经通过解析方法知道了你的基元形状，所以你可以构建定制的基元四面体化来满足你的需求，而不是依赖于网格生成库。

例如，假设您的对象是立方体和圆柱体的联合体，并且假设您有两个对象的四面体剖分。为了计算所得到的对象的边界表示，您首先标记每个原始对象的四面体的边界面。然后，进行联合操作：如果两个四面体不相交，则不需要执行任何操作；两个四面体都必须存在于结果多面体中。如果它们相交，则有许多情况（可能大约有十几种）需要处理。在这些情况中，需要以尊重表面约束的方式重新三角化两个四面体的体积。由于您只需要关注四面体而不是更复杂的形状，因此这使得事情变得更加容易。在过程中需要维护边界面标签，以便在最终的四面体集合中，可以提取边界面以形成表面的三角网格。

- Victor Liu

你能再详细解释一下吗？如果我理解正确的话，你是指为每个基本的CSG形状创建一个网格，然后在这些网格上进行集合操作吗？ - Martin

基本思想是使用更简单的原语（单纯形）执行操作，而不是实际的CSG原语。我添加了一个稍微详细的示例，但如何处理所有四面体-四面体相交的情况的实际细节比我在这里描述的要复杂得多（我从未实现过这样的方法，也没有看到过实现，但这个想法非常简单）。 - Victor Liu

我认为这根本没有减少复杂性。Tet-tet交点仍然很困难，而对于给定的表面进行四面体化最多也是不平凡的。 - Alec Jacobson

1

我在BRL-CAD应用程序MGED中有一些运气，可以使用CSG通过相交平面构造凸多面体，然后使用命令行g-stl命令提取边界表示。请查看http://brlcad.org/。马尔科姆

- Malcolm Lambert

我是通过谷歌搜索找到这个问题的。然后我看到你提到了g-stl工具。几年前，我曾尝试使用该工具将使用MGED构建的相对复杂的CSG模型转换为STL。当时是2009年，我使用的是BRL-CAD的Windows版本。但是这个过程总是会崩溃。自那以后，g-stl工具有没有进行任何改进？g-stl背后的算法是否被认为是健壮或优秀的？ - Ole Thomsen Buus

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Joe · Accepted Answer

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

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

该论文可在此处找到Merging BSP trees yields polyhedral set operations。

或者，每个形状可以表示为空间函数（例如到表面的符号距离）。只要将表面定义为函数等于零的位置，就可以使用（MIN ==交集），（MAX ==联合）和（NEGATION = not）运算符组合这些函数以模拟集合操作。然后，可以使用像Marching Cubes这样的技术提取组合函数等于零的位置作为结果表面。也可以使用更好的表面提取方法，例如Dual Marching Cubes或Dual Contouring。当然，这将导致真实CSG表面的离散近似。我建议使用Dual Contouring，因为它能够重构像立方体角落这样的尖锐特征。