algorithm - 将 3d 网格分解为 2d 网

Question

假设您有一个 3 维对象，以某种常见文件格式表示为 3d 网格。您将如何设计一种算法将网格分解为一个或多个 2d“网”——即，可以剪切和折叠以创建原始 3d 对象的 2 维表示。

除其他事项外，该算法还需要考虑:

• 任何给定对象的多种可能分解
• 处理将网格装入固定大小的 Canvas (纸张)。
• 识别网络中的两个面板何时重叠(因此无效)。
• 如果由于重叠或页面大小限制而无法将一个网格表示为一个单独的网络，则将它们分成多个网络。
• 在适当的位置生成标签，用于附加相邻的面孔。

明显的退化情况是简单地为每个面创建一个网，在一半的边缘上有标签。显然，这并不理想:理想情况是单个连续网络。复杂形状的实际情况可能介于两者之间。

我意识到找到最佳网络(最少的网络/最少的页面)可能在计算上很昂贵，但是找到“足够好”的网络的良好启发式就足够了。

Answer 1

当我读到你的问题时，我想到了“自动纸艺算法”这个词。所以我用谷歌搜索并找到了Papercraft Models using Generalized Cylinders (pdf) 作者:Massarwi 等人。

We propose a new method for producing unfolded papercraft patterns of rounded toy animal figures from triangulated meshes by means of strip-based approximation. Although in principle a triangulated model can be unfolded simply by retaining as much as possible of its connectivity while checking for intersecting triangles in the unfolded plane, creating a pattern with tens of thousands of triangles is unrealistic. Our approach is to approximate the mesh model by a set of continuous triangle strips with no internal vertices. Initially, we subdivide our mesh into parts corresponding to the features of the model. We segment each part into zonal regions, grouping triangles which are similar topological distances from the part boundary. We generate triangle strips by simplifying the mesh while retaining the borders of the zonal regions and additional cut-lines. The pattern is then created simply by unfolding the set of strips. The distinguishing feature of our method is that we approximate a mesh model by a set of continuous strips, not by other ruled surfaces such as parts of cones or cylinders. Thus, the approximated unfolded pattern can be generated using only mesh operations and a simple unfolding algorithm. Furthermore, a set of strips can be crafted just by bending the paper (without breaking edges) and can represent smooth features of the original mesh models.

还有一篇更早的相关论文叫做Paper craft models from meshes (9MB pdf) 作者:Shatz 等人。

This paper introduces an algorithm for segmenting a mesh into developable approximations. The algorithm can be used in various applications in CAD and computer graphics. This paper focuses on paper crafting and demonstrates that the algorithm generates approximations that are developable, easy to cut, and can be glued together. It is also shown that the error between the given model and the paper model is small.

来源:http://www.ee.technion.ac.il/~ayellet/images/sel-papers-pic-5.jpg