M.Sc Student Shatz Idan Making 3D Paper-Craft Models from Meshes Department of Electrical Engineering Professor Ayellet Tal Abstract

This thesis introduces an algorithm for segmenting a mesh into developable approximations. The algorithm can be used in various applications in CAD and computer graphics, including texture mapping, model fabrication and paper crafting. This thesis focuses on the latter and demonstrates that the algorithm generates approximates 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.

This novel algorithm segments a given mesh into explicitly developable parts that can be easily cut and glued together. The algorithm has three key ideas. First, each segment is approximated by a surface that is guaranteed to be developable. Second, the approximates are modified so as to guarantee that neighboring approximates intersect at their boundaries, thus prohibiting stretching. Third, the algorithm extracts the analytical boundaries between the approximates, making the boundaries intuitive and easy to cut and glue.

The algorithm begins with an initial over-segmentation of the mesh into trivial developable segments. This initial segmentation is iteratively modified, by decreasing the number of segments, while increasing the error. Each such iteration approximate the current segments, by fitting each segment to a conic(/plane), using weights specific to our problem. Once the segmentation is determined, the approximates are modified, in order to accommodate for “good” boundaries. Then, the analytical boundaries between the approximates are iteratively computed by a novel procedure, which is proved to converged to the analytical boundaries, therefore not restricting the boundaries to pass through edges of the original mesh.

We present some results of the algorithm, which demonstrate the following properties:

1.      Each part is developable and can be unfolded into a paper.

2.      The boundaries are easy to cut and glue.

3.      Visually, the difference between the paper-craft model and the mesh is pretty small.

4.      The number of pieces is relatively small.

In addition to satisfying the necessary Requirements 1-4, our algorithm has other benefits. First, the user can set parameters that indicate the required level of difficulty. Thus, the algorithm trades-off error for the number of pieces. Second, thin parts are modeled as planar surfaces. Third, symmetry and meaningful components are exploited, which facilitate the understanding of the user. Fourth, the resulting models are smooth. Finally, regions with many details are allocated more pieces than regions

with few details.