三维纸模型的建立

摘要：为了满足儿童折纸方案的设计以及动态显示典型的三维折纸过程的需要，基于实体几何模型的半边表示法，设计一个支持纸的折叠的计算模型。该计算模型包括当前纸态的几何与拓扑数据结构，并能够实现折叠的操作过程以及相关的功能。利用该计算模型的数据结构，结合图形学和计算几何中的基本算法实现纸的折叠。

关键词：数据结构 计算模型 三维折纸

Abstract：For satisfying the requirements of design of children's origami projects and dynamic demonstration of classic folding processes in 3D, based on the data structure similar to the half-edged structure in solid modeling and use the half edge node as the core node, it designs a computational model for simulating paper's folding. The model consists of a data structure for geometrically and topologically representing the current paper configuration, the implementing of the process of operations and related functions. Using this model structure, with the combining graphics and computational geometry basic algorithms can realize paper' folding.

Key words：data structure; Computational model; origami in 3D

1 基本约定

笔者约定参与折叠的虚拟纸是没有厚度的平面多边形，分为正面与反面，两面的颜色可以不同。。在折叠过程中，折出的纸面(facet)也看作平面多边形，它们的面积总和与初始纸张的面积相等，即不考虑由于折痕造成的面积损失。

对于折叠操作，先给出一些基本的定义。简单折叠[1,2] (simple fold)：即折叠只能沿着一条直线进行，折叠的角度是在-180°到180°之间。简单折叠中还包括一类特殊的折叠－平直折叠(flat fold)：即折叠只能沿着一条直线进行且折叠的角度都是180°。其中把这条直线叫做折叠线(folding line)。约定平直折叠折出的纸面相互贴合在一起，之间距离为0。值得注意的是简单折叠所能达到的纸态是受限制的，但是有相当一部分儿童折纸都采用简单折叠。

纸态[3](paper configuration)是指初始纸张(初始纸态)经过折叠所能达到的所有状态。纸态是一个特殊的几何实体，是纸面以及它们之间拓扑邻接关系的集合。用S来表示第i个折纸状态，F来表示对应于S的第i个折纸步骤。一个折纸的过程表示如下：

S0S1 S2…Sn

纸态是由N(N≥1)个纸面组成的，纸面的几何形态就是一个多边形，假设它自身不相交、封闭且包含一条轮廓线。如果单纯从表示的角度，它可以表示为一组由n个顶点构成的有序点列：{v0，v1，…，vn+1}。

2 纸态的数据结构及其表示

定义的纸态是由多个纸面构成的，而每个纸面又是由一系列有序的顶点连接而成。可以在双链三表结构的基础上对其进行存储即在计算机内分别存储基本图形单元的顶点、棱边、纸面一共三张表格。并且用双向链表将表格元素连接起来。

顶点是三维空间中的点，也是纸结构的构成中最基本的元素。它由顶点的x，y，z坐标、标志着顶点数目的序号、顶点的前驱顶点、后继顶点、以及它在屏幕上的坐标组成。

纸态中的每个纸面是由顶点链构成，为了描述构成纸面的顶点，设计了一个描述纸面中被使用顶点的数据结构，将它定义为Vertex_Use。

纸态是由多个纸面构成的，每个纸面都是由一系列有序的顶点构成。它与几何模型中的Face相似，它除了由纸面的序号和一系列有序的Vertex_Use连接构成，还包括该纸态中纸面的前驱纸面，纸面的后继纸面。

在纸结构中还增加了Crease结构来描述折叠过程中产生的折痕。一条折痕的存在至少对应于纸态中一个纸面的两个顶点，也可能有多个纸面的折痕重合的情况。折痕是由折线与纸面的多边形边界的交点，记录折痕主要是在折叠显示的时侯进行绘制，突出折纸的效果。

Origami结构是用来描述当前纸态，它包括当前纸态所有的纸面和所有的顶点，可以通过首顶点的指针遍历当前纸态的所有顶点，通过首纸面的指针遍历当前纸态的所有的纸面。

纸态的数据结构中没有边的结构，实际上有序的顶点连接后就构成了边，但在折叠的过程中并不需要对边结构进行直接的处理，为了节省数据的存储，所以我们不定义边结构。

3 结论

对现有折纸算法进行研究，并在此基础上建立了纸的计算模型,并实现了该模型的数据表示和内容存储。

参考文献：

[1]Demaine E D,Demaine M L. Thomas Hull. Recent results in computational origami[C]. Origami, 2002, 3-16.

[2]Demaine E D, Demaine M L, Mitchell J S B. Folding at silhouettes and wrapping polyhedral packages: New results in computational origami. In Proceedings of the 15th Annual ACM Symposium on Computational Geometry, Miami Beach, Florida, June 1999.

[3]Erik D D，Martin L D. Recent Results in Computational Origami[D]. Waterloo: University of Waterloo, 1998 .