构造实体几何网格
如果我使用构造实体几何技术构建形状，如何构建用于渲染的线框网格？ 我知道直接渲染 CSG 形状的算法，但我想将其转换为线框网格一次，以便我可以“正常”渲染它
以添加更多细节。给定形状的描述，例如“这里是立方体，这里与球体相交，这里减去圆柱体”，我希望能够计算多边形网格。
If I construct a shape using constructive solid geometry techniques, how can I construct a wireframe mesh for rendering?
I'm aware of algorithms for directly rendering CSG shapes, but I want to convert it into a wireframe mesh just once so that I can render it "normally"
To add a little more detail. Given a description of a shape such as "A cube here, intersection with a sphere here, subtract a cylinder here" I want to be able to calculate a polygon mesh.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
有两种主要方法。如果您有一组多边形形状，则可以为每个形状创建一个 BSP 树，然后可以合并 BSP 树。来自维基百科，
该论文位于合并 BSP 树产生多面体集合运算。
或者，每个形状可以表示为空间上的函数（例如到表面的有符号距离）。只要将曲面定义为函数等于 0 的位置，就可以使用 (MIN == junction)、(MAX == union) 和 (NEGATION = not) 运算符组合函数来模拟集合运算。然后可以使用诸如移动立方体之类的技术将所得表面提取为组合函数等于零的位置。还可以使用更好的表面提取方法，例如双行进立方体或双轮廓。当然，这将导致真实 CSG 表面的离散近似。我建议使用双重轮廓，因为它能够重建清晰的特征，例如立方体的角。
There are two main approaches. If you have a set of polygonal shapes, it is possible to create a BSP tree for each shape, then the BSP trees can be merged. From Wikipedia,
The paper is found here Merging BSP trees yields polyhedral set operations.
Alternatively, each shape can be represented as a function over space (for example signed distance to the surface). As long as the surface is defined as where the function is equal to zero, the functions can then be combined using (MIN == intersection), (MAX == union), and (NEGATION = not) operators to mimic the set operations. The resulting surface can then be extracted as the positions where the combined function is equal to zero using a technique like Marching Cubes. Better surface extraction methods like Dual Marching Cubes or Dual Contouring can also be used. This will, of course, result in a discrete approximation of the true CSG surface. I suggest using Dual Contouring, because it is able to reconstruct sharp features like the corners of cubes .
这些库似乎可以满足您的要求：
www.solidgraphics.com/SolidKit/
carve-csg.com/
gts.sourceforge.net/
These libraries seems to do what you want:
www.solidgraphics.com/SolidKit/
carve-csg.com/
gts.sourceforge.net/
另请参阅“三角多面体的构造立体几何”(1990) Philip M. Hubbard doi:10.1.1.34.9374
See also "Constructive Solid Geometry for Triangulated Polyhedra" (1990) Philip M. Hubbard doi:10.1.1.34.9374
这里是一些 Google 学术搜索链接，可能会有用的。
据我所知，其基本思想是从 CSG 模型中可用的体积数据生成点云，然后使用一些更常见的算法生成 3D 面网格以适合该点云。
编辑：进一步研究，这种操作称为“从CSG到B-Rep（边界表示）的转换”。搜索该字符串会得到一个有用的 PDF：
http://www.scielo。 br/pdf/jbsmse/v29n4/a01v29n4.pdf
而且，有关更多信息，关键算法称为“行进立方体算法”。本质上，CSG 模型用于创建具有体素的对象的体积模型，然后使用 Marching Cubes 算法根据体素数据创建 3D 网格。
Here are some Google Scholar links which may be of use.
From what I can tell of the abstracts, the basic idea is to generate a point cloud from the volumetric data available in the CSG model, and then use some more common algorithms to generate a mesh of faces in 3D to fit that point cloud.
Edit: Doing some further research, this kind of operation is called "conversion from CSG to B-Rep (boundary representation)". Searches on that string lead to a useful PDF:
http://www.scielo.br/pdf/jbsmse/v29n4/a01v29n4.pdf
And, for further information, the key algorithm is called the "Marching Cubes Algorithm". Essentially, the CSG model is used to create a volumetric model of the object with voxels, and then the Marching Cubes algorithm is used to create a 3D mesh out of the voxel data.
您可以尝试对每个基元进行三角测量（四面体化），然后对四面体网格执行布尔运算，这“更容易”，因为您只需要担心四面体-四面体运算。然后您可以执行边界提取以获得 B-rep。由于您通过分析了解基元的形状，因此您可以构造基元的自定义四面体以满足您的需求，而不是依赖网格生成库。
例如，假设您的对象是立方体和圆柱体的并集，并且假设您有两个对象的四面体化。为了计算结果对象的边界表示，首先标记每个基本对象的四面体的所有边界面。然后，执行并集操作：如果两个四面体不相交，则无需执行任何操作；两个四面体必须存在于所得的多面体中。如果它们相交，那么就有很多情况（可能是十几个左右）需要处理。在每种情况下，两个四面体的体积都需要以尊重表面约束的方式重新三角化。由于您只需要担心四面体，而不是更复杂的形状，因此这变得更加容易。在此过程中需要维护边界面标签，以便在最终的四面体集合中可以提取边界面以形成表面的三角形网格。
You could try to triangulate (tetrahedralize) each primitive, then perform the boolean operations on the tetrahedral mesh, which is "easier" since you only need to worry about tetrahedron-tetrahedron operations. Then you can perform boundary extraction to get the B-rep. Since you know the shapes of your primitives analytically, you can construct custom tetrahedralizations of your primitives to suit your needs instead of relying on a mesh generation library.
For example, suppose your object was the union of a cube and a cylinder, and suppose you have a tetrahedralization of both objects. In order to compute the boundary representation of the resulting object, you first label all the boundary facets of the tetrahedra of each primitive object. Then, you perform the union operation: if two tetrahedra are disjoint, then nothing needs to be done; both tetrahedra must exist in the resulting polyhedron. If they intersect, then there are a number of cases (probably on the order of a dozen or so) that need to be handled. In each of these cases, the volume of the two tetrahedra needs to be re-triangulated in a way that respects the surface constraints. This is made somewhat easier by the fact that you only need to worry about tetrahedra, as opposed to more complicated shapes. The boundary facet labels need to be maintained in the process so that in the final collection of tetrahedra, the boundary facets can be extracted to form a triangle mesh of the surface.
我很幸运地使用了 BRL-CAD 应用程序 MGED，在其中我可以通过使用 CSG 相交平面来构造凸多面体，然后使用命令行 g-stl 命令提取边界表示。检查http://brlcad.org/
马尔科姆
I've had some luck with the BRL-CAD application MGED where I can construct a convex polyhedron by intersecting planes using CSG then extract the boundary representation using the command-line g-stl command. Check http://brlcad.org/
Malcolm
如果您可以将输入基元转换为多面体网格，那么您可以使用 libigl 的 C++ 网格布尔例程。下面计算一个网格 (VA,FA) 和另一个网格 (VB,FB) 的并集：
其中 VA 是顶点位置的 #VA x 3 矩阵，FA 是 VA 中三角形索引的 #FA x 3 矩阵，并且很快。 libigl 中使用的技术与 Joe 的回答中提到的两种技术不同。所有三角形对都相互相交（使用空间加速度），然后将生成的子三角形分类为属于输出表面或不属于输出表面。
If you can convert you input primitives to polyhedral meshes then you could use libigl's C++ mesh boolean routines. The following computes the union of a mesh (VA,FA) and another mesh (VB,FB):
where VA is a #VA by 3 matrix of vertex positions and FA is a #FA by 3 matrix of triangle indices into VA, and so on. The technique used in libigl is different from those two mentioned in Joe's answer. All pairs of triangles are intersected against each other (using spatial acceleration) and then resulting sub-triangles are categorized as belonging to the output surface or not.