C++ 用于切片网格的算法或软件

Algorithm or software for slicing a mesh

提问by dr_rk

What is the right approach for slicing a 3D mesh? The mesh are all closed surfaces and the slices need to be binary images of what's inside the mesh. So for example, a mesh representing a sphere and slice images are those of filled circles.

切片 3D 网格的正确方法是什么？网格都是封闭的表面，切片需要是网格内部的二进制图像。例如，表示球体和切片图像的网格是实心圆的网格。

I am looking for a software library or algorithm that I can integrate into my current C++ project.

我正在寻找可以集成到当前 C++ 项目中的软件库或算法。

回答by Dennis

My open source game library contains an implementation of mesh slicing. It works with the Irrlicht api, but could be rewritten to use a different API with a modest effort. You can use the code under the terms of the BSD license, or learn from it an implement your own.

我的开源游戏库包含网格切片的实现。它与 Irrlicht api 一起工作，但可以通过适度的努力重写以使用不同的 API。您可以在 BSD 许可条款下使用代码，或者从中学习并实现您自己的代码。

See MeshTools::splitMeshZ in this file for an implementation of mesh slicing.

有关网格切片的实现，请参阅此文件中的MeshTools::splitMeshZ 。

If you just want to know the algorithm, here's a high-level description of what I did:

如果你只是想知道算法，这里是我所做的高级描述：

I initially thought of using an axis-aligned bounding box to specify where to cut the mesh. This was problematic because it introduced many special-cases. For instance, an edge that crosses the corner of the box may be split into three pieces rather than just two.

我最初想到使用轴对齐的边界框来指定切割网格的位置。这是有问题的，因为它引入了许多特殊情况。例如，穿过盒子角落的边可能会被分成三块而不是两块。

Using a plane to cut the mesh into just a left mesh and a right mesh reduces the number of special cases, because an edge is either on one side of the plane or the other, or it crosses the plane and so is chopped into exactly two pieces.

使用平面将网格切割成一个左网格和一个右网格减少了特殊情况的数量，因为边要么在平面的一侧，要么在另一侧，或者它穿过平面，所以被切成两半件。

Any desired configuration of cuts can be made simply by cutting once, taking one of the resulting meshes and cutting it again in another location, and so forth. Specifically in the case you describe in the section, a circle could be cut from a sphere by cutting one half the sphere off, moving the plane a small amount and cutting off the other half leaving only a thin band. (You can't cut a mesh down to literally no depth with the code I wrote, but you could cut a mesh up to whatever you have set your floating point equality threshold to be. I think I arbitrarily chose 0.001 in my code.)

任何所需的切割配置都可以通过切割一次，取其中一个生成的网格并在另一个位置再次切割，等等来完成。特别是在您在本节中描述的情况下，可以通过将球体的一半切掉，将平面移动少量并切掉另一半只留下一条细带，从而从球体上切出一个圆。（你不能用我写的代码把一个网格切到几乎没有深度，但你可以把一个网格切到任何你设置的浮点相等阈值。我想我在我的代码中任意选择了 0.001。）

Using similar logic, any desired angle of the cutting plane can be achieved using a fixed plane; you just need to transform the mesh to rotate it relative to the fixed cutting plane, and then transform the result back. (For my game I only needed cuts perpendicular to the XY plane, so for simplicity I only allow the Z value of the cut to be set, and assume the cut is at that Z location.)

使用类似的逻辑，可以使用固定平面来实现切割平面的任何所需角度；您只需要转换网格以使其相对于固定切割平面旋转，然后将结果转换回来。（对于我的游戏，我只需要垂直于 XY 平面的切割，因此为简单起见，我只允许设置切割的 Z 值，并假设切割位于该 Z 位置。）

OK, now that we've simplified the problem, the algorithm is not so bad:

好的，现在我们已经简化了问题，算法还不错：

Starting condition: You have a cutting plane. You have a set of source triangles. You have two destination sets of polygons(not triangles; quads may be generated by cutting the triangle). The two destination sets are called Left and Right.

起始条件：您有一个切割平面。您有一组源三角形。您有两个目标多边形集（不是三角形；可以通过切割三角形生成四边形）。这两个目标集称为左和右。

Process: Iterate over three points of a triangle. Count the number of points that are less than the cutting plane. I will call those less than the cutting plane Left and those greater than the cutting plane Right. There are only a handful of cases:

过程：迭代三角形的三个点。计算小于切割平面的点数。我将小于切割平面的那些称为左，大于切割平面的称为右。只有少数几种情况：

• All triangle points are on the Left: put the triangle in the Left set
• All points are on the Right: put the triangle in the Right set
• One point is Left, others are Right: if you cut a triangle across two edges, and you were holding one of the points, you end up holding a smaller triangle. Put a triangle in the Left set made up of the Left point, and the two points where the edges crosses the plane. Put a quad in the Right set (see next case).

• Two points are Left, one point is Right. If you are holding an edge of a triangle and cut it across the other two edges, you are left holding a trapezoid. Put a quad in the Left set made up of the two points in your hand, plus the two points which cross the cut. Put a triangle in the right set (mirror image of case above).

• When finished, turn the quads into triangles by adding a link across the shortest part.

• 所有三角形的点都在左边：把三角形放在左边的集合中
• 所有点都在右边：把三角形放在右边
• 一点是左边，其他点是右边：如果你在两条边上切割一个三角形，并且你持有其中一个点，你最终会持有一个较小的三角形。在由左点和边与平面相交的两个点组成的左集合中放置一个三角形。将四边形放在 Right 组中（参见下一个案例）。

• 左边两点，右边一点。如果你拿着一个三角形的一条边并把它切过另外两条边，你就剩下一个梯形了。将一个四边形放在由您手中的两个点和与切割相交的两个点组成的左组中。将一个三角形放在正确的组中（上面案例的镜像）。

• 完成后，通过在最短部分添加链接将四边形变成三角形。

That's it. That's the basic algorithm. The actual code handles a few more cases such as what if an edge is exactly equal to the cut, what if a triangle is exactly on the edge, don't add degenerate polygons (e.g. a point with no body), etc.

就是这样。这就是基本算法。实际的代码处理了更多的情况，例如如果一条边与切割完全相等，如果三角形正好在边上，不要添加退化多边形（例如没有主体的点）等。

Misc. issues (all covered in the linked code):

杂项 问题（都包含在链接代码中）：

• Don't overcomplicate the math for LERP'ing the spot where the edge crosses the cutting plane. It doesn't need a full linear interpolation, it is actually just Highschool Algebra II: rise over run, times a ratio

• It is advantageous to cache the generated (LERP'ed) points so that triangles which shared vertices in the uncut mesh will share the corresponding new vertices in the cut mesh.

• If you are going to preserve vertex sharing, and you are using triangle index buffers, you unfortunately don't know the index yet when you first generate the shapes to put in the Left and Right sets. I use a class called "PossibleVertex" to represent a future triangle index number.

• If you are going to display the mesh, winding order matters. Careful thought about how you code it up can ensure the resulting polygons use the same winding order as the triangles they came from. This gets especially tricky when triangulating the quads. I can't remember the details but it's all handled in the linked code.

• For my game, I wanted to make a flat ribbon connecting two cut meshes. That's why splitMeshZ results in 3 meshes, rather than just two. You can use the middle mesh, or just ignore it.

• 不要使 LERP 的数学计算过于复杂，即边缘与切割平面相交的位置。它不需要完整的线性插值，它实际上只是高中代数 II：运行时上升，乘以比率

• 缓存生成的（LERP'ed）点是有利的，这样共享未切割网格中顶点的三角形将共享切割网格中相应的新顶点。

• 如果您打算保留顶点共享，并且您正在使用三角形索引缓冲区，那么遗憾的是，当您第一次生成要放入 Left 和 Right 集合的形状时，您还不知道索引。我使用一个名为“PossibleVertex”的类来表示未来的三角形索引号。

• 如果要显示网格，缠绕顺序很重要。仔细考虑如何编码可以确保生成的多边形使用与它们来自的三角形相同的缠绕顺序。在对四边形进行三角剖分时，这变得特别棘手。我不记得细节了，但都在链接的代码中处理了。

• 对于我的游戏，我想制作一条连接两个切割网格的扁平丝带。这就是 splitMeshZ 生成 3 个网格而不是两个网格的原因。您可以使用中间网格，也可以忽略它。

回答by rdminetto

A project in 3D mesh slicing (with a source code in C++):

一个 3D 网格切片项目（带有 C++ 源代码）：

http://www.dainf.ct.utfpr.edu.br/~rminetto/projects/slicing/

http://www.dainf.ct.utfpr.edu.br/~rminetto/projects/slicing/

回答by ryanm

I've outlined the algorithm to compute plane-volume intersections in this answer. An implementation in Java is provided.

我已经在这个答案中概述了计算平面体积交点的算法。提供了一个 Java 实现。

回答by hc_

I assume you are talking about triangle meshes?

我假设您在谈论三角形网格？

What's the "right" approach strongly depends on the specifics of your use case.

什么是“正确”的方法在很大程度上取决于您的用例的具体情况。

The OpenGL approach suggested by Jerry might work for you.

Jerry 建议的 OpenGL 方法可能适合您。

Another approach would be to explicitly compute the cuts. You could to this with CGAL. More specifically with its 3D kernel. It features a functionthat can compute intersections between all sorts of primitives, including a plane and a triangle. Using this function you can accurately compute your intersection outline and render it into an image. - This way you would not depend on OpenGL but on CGAL instead.

另一种方法是明确计算切割。你可以用CGAL做到这一点。更具体地说是它的 3D 内核。它具有一个功能，可以各种原语，包括平面和一个三角形之间计算交叉点。使用此功能，您可以准确计算您的交点轮廓并将其渲染为图像。- 这样你就不会依赖于 OpenGL，而是依赖于 CGAL。

回答by hc_

It would be faster (for yourself, not running-time) if you implement it yourself: These are the simple steps you need to do:

如果您自己实现它会更快（对于您自己，而不是运行时）：这些是您需要执行的简单步骤：

1-Extract all the triangles of the mesh

1-提取网格的所有三角形

2-For each triangle,

2-对于每个三角形，

2-1- check if any of triangle points are on the slice-plane,

2-1- 检查是否有任何三角形点在切片平面上，

2-2- if not, then for each of its three edges, find the intersection with your slice-plane (if there is any). You must either have 2 of them intersected with the plane or none.

2-2- 如果不是，那么对于它的三个边中的每一个，找到与切片平面的交点（如果有的话）。您必须让其中 2 个与平面相交，或者没有。

2-2-1 If 2 edges intersected with the plane, then you add a line between these 2 points on the plane.

2-2-1 如果 2 条边与平面相交，则在平面上的这 2 个点之间添加一条线。