将 3d 网格分解为 2d 网络
假设您有一个 3 维对象，以某种常见文件格式表示为 3d 网格。 您将如何设计一种算法将网格分解为一个或多个 2d“网”，即可以剪切和折叠以创建原始 3d 对象的 2 维表示形式。
除其他事项外，该算法需要考虑：
- 任何给定对象的多种可能的分解
- 处理将网格拟合到固定大小的画布（纸张）中。
- 识别网络中的两个面板何时重叠（因此无效）。
- 如果由于重叠或页面大小限制而无法将网格表示为单个网络，则将网格分解为多个网络。
- 在适当的位置生成选项卡，用于连接相邻的面。
明显的退化情况是简单地为每个面创建一个网，并在一半边缘上设置标签。 显然，这并不理想：理想的情况是单个连续网络。 复杂形状的实际情况可能介于两者之间。
我意识到寻找最佳网络（最少的网络/最少的页面）可能在计算上很昂贵，但是寻找“足够好”网络的良好启发式就足够了。
Suppose you have a 3 dimensional object, represented as a 3d mesh in some common file format. How would you devise an algorithm to decompose the mesh into one or more 2d 'nets' - that is, a 2-dimensional representation that can be cut out and folded to create the original 3d object.
Amongst other things, the algorithm would need to account for:
- Multiple possible decompositions for any given object
- Handling fitting a mesh into fixed size canvases (sheets of paper).
- Recognizing when two panels in the net would overlap (and are thus invalid).
- Breaking a mesh up into multiple nets if they can't be represented as a single one, due to overlap or page size constraints.
- Generating tabs in the appropriate places, for attaching adjacent faces.
The obvious degenerate case is simply to create one net per face, with tabs on half the edges. This isn't ideal, obviously: The ideal case is a single continuous net. The reality for complex shapes is likely to be somewhere in the middle.
I realize that finding the optimal net (fewest nets / least pages) is probably computationally expensive, but a good heuristic for finding 'good enough' nets would suffice.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
当我读到你的问题时，我想到了“自动纸艺算法”这个词。 所以我用谷歌搜索并找到了使用通用圆柱体的纸艺模型（pdf）作者：Massarwi 等人。
还有一篇较早的相关论文，名为来自网格的纸工艺模型 (9MB pdf)，作者：Shatz 等人。
来源：http://www.ee .technion.ac.il/~ayellet/images/sel-papers-pic-5.jpg
When I read your question, the words "automatic papercraft algorithm" came to me. So I googled it and found Papercraft Models using Generalized Cylinders (pdf) by Massarwi et al.
There is also an earlier related paper called Paper craft models from meshes (9MB pdf) by Shatz et al.
Source: http://www.ee.technion.ac.il/~ayellet/images/sel-papers-pic-5.jpg
链接到的算法 eed3si9n 将从复杂的几何形状生成漂亮合理的纸艺网格。 如果您想完全按照建模方式展开网格（例如对于多面体模型），那么这里有一种相对简单的技术，可以按原样展开任何网格
从源网格构建一个图形，其中每个面都是图形中的一个顶点，如果两个顶点在网格中共享公共边，则它们是连接的。 当且仅当其中一个图没有循环时，即它是一棵树时，它才表示可展开的网格。
一棵好的树代表从起点到达最远面的最少折叠线，因为每次折叠都代表将在最终模型中累积的误差。 Dijkstra 算法在这里很好，但最小生成树不起作用。 由于每条边的权重相等，所有树都是最小生成树，即使是将网格展开成一个大螺旋的树也是如此。 当您将模型粘合在一起时，错误会不断累积，直到最后几个面根本不合适。
一旦你有了树，就开始在原点绘制你的起始面。 然后遍历树并通过计算新顶点作为两个圆的交点来添加新面，两个圆的半径对应于原始网格中边的长度。 选项卡的位置对应于原始网格中但不在可展平树中的边。
用户指定的切割可以在树步骤之前作为边缘删除来处理。
这种技术的一些缺点是它会很高兴地创建平面图案中的重叠部分，这取决于找到一个好的起始面。 我尝试 Floyd-Warshal 寻找一个最小直径的面作为起点，但它的 O(n^3) 行为导致咖啡休息时间过长。 可以通过将树的分支标记为“不完整”、跳过它并在所有不完整的面上重新运行算法来处理重叠部分。
The algorithms eed3si9n linked to will generate nice reasonable papercraft meshes from complicated geometry. If you'd like to unfold the mesh exactly as it is modeled, such as for polyhedra models, then here's a relatively simple technique for unfolding any mesh as it stand
Construct a graph from your source mesh where each face is a vertex in the graph, and two vertices are connected if they share a common edge in the mesh. One of these graphs represents an unfoldable mesh if and only if it has no loops, i.e. it is a tree.
A good tree represents the fewest fold lines to get to the farthest face from the starting point, since each fold represents error that will accumulate in the finished model. Dijkstra's algorithm is good here, but minimum spanning tree doesn't work. With each edge equally weighted all trees are minimum spanning trees, even one that would unfold your mesh into one big spiral. As you glued the model together, errors would build up until the last few faces didn't fit at all.
Once you have the tree, start by drawing your starting face at the origin. Then walk the tree and add the new faces by calculating the new vertex as the intersection of two circles with radii corresponding to the lengths of the edges in the original mesh. Locations for tabs correspond to edges that were in the original mesh, but are not in the flattenable tree.
User-specified cuts can be handled as edge deletions before the tree step.
Some downsides of this technique are that it will happily create overlapping parts in the flat pattern, and it is dependent on finding a good starting face. I tried Floyd-Warshal to find a minimum-diameter face to start from, but its O(n^3) behavior made for excessively long coffee breaks. The overlapping parts could be dealt with by marking that branch of the tree as "incomplete", skipping it, and re-running the algorithm on all incomplete faces again.
我知道这不是答案，但它是相关的。 前 SGI 图形专家 Paul Haeberli 的 Lamina 程序是这个问题的解决方案。
I know this is not an answer, but it is related. Ex-SGI graphics guy Paul Haeberli's Lamina program is a solution for this problem.