用于切片网格的算法或软件 [英] Algorithm or software for slicing a mesh

问题描述

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

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

解决方案

我的开源游戏库包含一个网格划分的实现。它与Irrlicht api一起工作，但可以重写，以适度的努力使用不同的API。

请参阅MeshTools :: splitMeshZ in 此网格切片实施的文件。

如果你只是想知道算法，这里是一个高级描述我做了什么：

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

使用平面将网格切割成仅仅一个左网格和右网格减少了特殊情况的数量，因为边缘在平面的一侧或另一侧，或它穿过平面，因此被切成恰好两片。

任何所需的切割配置可以简单地通过切割一次，取得所得到的网格之一并在另一位置再次切割，等等。特别是在你在部分描述的情况下，一个圆可以从球体切割一半球体，移动平面一小部分，切除另一半只留下一个薄带。 （你不能使用我写的代码将网格切割到字面上没有深度，但是你可以剪切一个网格，直到你设置浮点相等阈值为止）我认为我在我的代码中任意选择0.001）

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

好的，现在我们已经简化了问题，算法并没有那么糟糕：

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

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

• 所有三角形点都在左边：将三角形放在左边集合


• 所有点都在右侧：将三角形放在右侧集合


• 一个点是左，其他都是右：你拿着一个点，你最后拿着一个较小的三角形。将一个三角形放在左侧点组成的左侧点，以及边缘与平面交叉的两个点。



• 两个点为左，一个点为右。如果你拿着一个三角形的边缘，并跨越其他两个边缘切割，你留下一个梯形。把一个四边形放在左边，由你手中的两个点组成，再加上穿过切口的两个点。



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

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

其他。

• 不要使LERP的边缘过度复杂穿过切割平面。它不需要一个完整的线性插值，它实际上只是Highschool代数II：上升运行，乘一个比率




• （LERP'ed）点，以便在未剪切网格中共享顶点的三角形将共享剪切网格中的相应新顶点。




• 保存顶点共享，并且您正在使用三角形索引缓冲区，不幸的是，当您首次生成要放入左侧和右侧集合的形状时，您不知道索引。我使用一个名为PossibleVertex的类来表示未来的三角形索引号。




• 如果你要显示网格，仔细考虑你如何编码它可以确保生成的多边形使用与它们来自的三角形相同的缠绕顺序。当对四边形进行三角测量时，这变得特别棘手。




• 对于我的游戏，我想做一个扁平的丝带连接两个切割的网格。这就是为什么splitMeshZ产生3个网格，而不是只有两个。您可以使用中间网格物体，也可以忽略它。

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.

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

解决方案

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.

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

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.)

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.)

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.

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.

这篇关于用于切片网格的算法或软件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！