Translation--Popup: Automatic Paper Architectures from 3D Models

论文翻译 siggraph

---

Popup: Automatic Paper Architectures from 3D Models

Popup: 从3D模型自动化构建纸结构

原文

http://cg.cs.tsinghua.edu.cn/people/~xianying/Papers/Popup/index.html

Abstract 摘要

“纸结构”是通过折叠和切割创造出来的3D纸建筑。纸结构的制作过程通常是劳动密集型和有着较高技能要求的，甚至在计算机辅助设计工具的帮助下也是如此。我们提出了一种基于用户给定3D模型的情况下生成纸结构的算法。此算法是建立在可以保证纸结构能够刚性并稳定形式弹出的平面布局公式，以及能够让3D平面弹起而从这个布局中得到的条件上。（The algorithm is grounded on geometric formulation of planar layout
for paper architectures that can be popped-up in a rigid and stable
manner, and sufficient conditions for a 3D surface to be poppedup
from such a planar layout.有待考虑）基于这些条件，我们的算法计算出一个包含两个集合的类。两个集合中包含平行的小块，这些小块拟合输入图形以保证可实现性。这个方法在一些纸结构例子上已经得到了验证，并且我们也展示出了一些真实模型。

KeyWords: paper architecture, pop-up, computer art, planar layout

1 Intrduction 引言

纸结构，也称为折纸结构，是用结合裁剪和折叠良好总方式创造出来的纸建筑。纸结构起源于20世纪80年代日本人Masahiro Chatani之手，流行于全世界的艺术家之间，尤其是Bianchini, Siliakus和Aysta三位。纸结构以各种各样的形式出现，比如问候卡片和桌面装饰，并且能够被“惊人的实现”[Chatani et al. 1987]。图2，展示了出自艺术家之手的一些样品。更多的展览可以在Ingrid Siliakus and Gerry Stormer的在线画廊中找到。
纸结构是通过把一张纸裁剪和折叠做出来的，存放时只要折叠纸的两端即可。当纸张打开时，3D的建筑就会“站起来”或者“弹出来”。与弹纸书类似，纸结构制作时也不需要胶合或拼接，那些对纸张裁剪和折叠样式设计产生额外的限制（所以称作平面布局）。更具有挑战性工作就是创造一个可以弹出为期望的3D样式的布局。市面上存在大量书本介绍设计弹出卡的机制[Birminghan 1997; Carter 1999; Cheong et al. 2009]，也有人开发了一些提供虚拟设计环境的计算机辅助设计工具[Lee et al. 1996; Glassner 2002; Hendrix and Eisenberg 2006; Mitani and Suzuki 2004a]。但是，用户最终还是要负责决定如何把裁剪和折叠的位置放在2D的纸张上，生成一个具有3D现实感弹出模型的2D布局是一个具有劳动密集和高度技能要求的工作。
本文中，我们提出了一种完全自动化的算法。这个算法可以按照用户给定的3D模型近似的生成纸结构。从而可以让新手能够方便地制作可以复杂的、可实现的纸结构（可以参看图1右边的例子）。我们的算法基于一个可以产生3D纸结构平面布局的新的集合公式。通常，布局中的区域需要保持刚性并且弹出的时候没有交叉，并且这个结构只需要用户拿着纸的两端而不需要其他帮助，就能够自己保持稳定。从公式出发，我们可以得到一类3D平面的充分条件。这些3D平面包含两个方向的小块，以确保平面布局可以正确地弹出。在这些条件的指导下，我们设计了一个基于网格的算法。这个算法可以从任何用户输入的模型自动产生一个3D的、可实现的纸结构，仅仅需要用户指定纸在模型的哪个方向。图1是一个例子。

Contribution 贡献

据我们所知，我们的算法是第一个可以自动模仿3D输入从而产生纸结构的方法。为了达到我们的目标，我们做了下面这些工作：

• 我们提出了一个种正式的集合公式，用来产生平面布局。这个布局可以刚性并且稳定弹出为纸结构。（第3部分）

• 我们为一类3D平面提出了充分条件。这类3D平面包含了朝向一个或两个方向的小块。这些条件可以保证平面布局能够以一个刚性和稳定的方式弹出。

• 我们提出了一个生成纸结构和相应的平面布局的算法。平面布局在保证可实现的前提下可以逼近任何给定的3D模型。

2 Related Work相关工作

纸工艺 不同类型的纸工艺在数学和可计算方面都有研究。这里我们简单复述一下主要工作。
日本折纸（Origami）是一项传统的日本折纸艺术。通常，日本折纸是“平折”（也就是纸张是平整不被破坏的）。“平折”使用一张纸，不剪也不用胶水。折叠算法和日本折纸的可折叠性已经被计算几何团队广泛研究了，我们向读者推荐近期的一本Demaine和O'Rourke写的书[2007]。更近一些的，Tachi[2009]提出了一种可以自动产生折纸设计的算法，可以产生任意的多面体平面。弧形折纸也在分析了可展开平面的基础上被考虑过[Kilian et al. 2008]。如果允许裁剪，那么纸结构就展现出一组不同于传统折纸的折叠和可折叠性问题，某些问题正是我们的工作需要解决的。
带状模型(Strip Modeling)被考虑用纸带或者可片状展开的平面来代替3D模型。Mitani和Suzuki[2004b] 提出了一种可以用纸带近似产生普通平面的方法。他们的算法基于网格简化，是一个被研究很多但仍然很热的一个话题[Garland and Heckbert 1997; Cohen et al. 1998; Wei and Lou 2010]。其他的方法也在[Shatz et al. 2006]和[Massarwi et al. 2007]中被提出。使用裁剪和切割，带状模型可以达到其他纸艺形式难以表现的复杂几何图形。
剪纸（paper-cutting）是一种用一张纸纸剪出典型样式和形象中国民间艺术。[Xu et al. 2007]提出了一种简单有效的依据给出输入自动化生成剪纸的算法。扩展到3D剪纸和交互式的剪纸动画设计也被仔细考虑过[Li et al. 2007]。
可计算纸结构
不同于其他纸艺形式，纸结构的算法解法很少有。多数的计算工作都在致力于创建一个计算机辅助的弹出工艺品的设计环境。Glassner引入了一个系统[Glassner 2002]可以交互式的设计单缝和v形折叠两种形式的弹出卡。类似的系统还有面向儿童的弹纸作坊（PopupWorkshop）[Hendrix and Eisenberg 2006]。可惜，这些系统会产生交叉的现象，而且需要由用户解决。Mitani和Suzuki[2004a]提出了一种用于纸结构设计的CAD系统，可以从构造机制上确保形状的有效和平面布局的可折叠性。此外，一个弹出条件也被提出，用来检查一种布局在纸打开时候是否可以直立展开。然而，这个条件不能在他们的系统中自动化地保证，因此用户需要通过尝试操作来判断。通常来说，判断一个给定的弹出艺术品是否可以被打开和关闭是一个NP难问题[Uehara and Teramoto 2006]。在我们工作中，提出了一个布局可以在纸张打开时直立稳定展现的充分条件，进一步给出了一个确保输出满足这个条件的算法。
有几种可以自动化的制作弹出艺术品或者纸结构的方法。Hara和Sugihara[2009]考虑了一种弹出问题的2D版本（给出一个多边形作为期望的弹出形状）并且提出了一种采用多边形分隔的解法。但是，这个解法需要粘贴一些纸张，而在纸结构中是不允许的。我们了解到由3D模型生成纸结构的工作只有Mitani et al.[2003]（日本的）。跟我们的方法相似，他们也是考虑使用空间网格去构造弹出面。但是，他们的算法简单地、阶梯状地造出3D的建筑，缺乏可弹出和稳定性的保证。相反，我们提出了一个更鲁棒的算法，基于可折叠性和稳定性的几何公式，可以产生与输入高度相似的结果。注意到结构模型的稳定性已经被Whiting et al.[2009]在程序模型中考虑过了，虽然这个模型相当原始并且稳定条件和我们的有很大不同。
Shape abstraction形状抽象
用纸结构去逼近一个3D模型是一种形状抽象的典型方式。前人在形状抽象中的工作大部分是基于平面块的分割[Lai et al. 2006; Shamir 2008; Lai et al. 2009]并且用原始的方法，比如quasi-developable或者nearly-flat patches[Julius et al. 2005; Yamauchi et al. 2005; Wang 2008 ;Mehra et al. 2009]，去逼近。我们的方法的结果可以看作一种应用了平行于纸张两端的平面块的特殊抽象。平行于纸张两端提供了额外的物理特性（比如可以从平面弹起）。

3 Formulations 公式

纸结构通过把一张纸切割和折叠进行制作。一个纸结构的平面布局是一个包括剪切线和折叠线的集合，这些线把纸分割成为若干区域。通常，有两片外部区域，称为后背(backdrop)和底面(ground)，他们交界于中部的折痕。当使用者沿中部的折线把后背和底面移动起来，其余的区域就顺着折叠轨迹“弹起”。

3.1 Layouts 布局

纸结构，或者说它们折叠结果，的平面布局通常被考虑成一种线性组成的3D平面。特别地，我们定义：
定义1：一个块级的线性平面（piece-wise linear surface，PLS）是一个平面集合。这个集合中的平面块没有交叉也没有覆盖，并且相邻的块共享一条直线边。
定义2：纸结构的平面布局（PLPA）T定义为满足如下条件的PLS：
1. T中的所有块是共平面的
2. T划定一个可能存在洞的矩形区域，并且
3. 存在两个块，称为后背和底面，这两个面与矩形的外边界相交并且沿矩形的中线作为交界
图3（a）是一个PLPA的例子。在PLPA中，我们称相邻块之间的边界为折叠线（图中的红色和蓝色线），其余的块边界为裁剪线（图中的黑线）。通常我们称后背和底面之间的折叠线为中央折叠线。

3.2 Foldable Layouts 可折叠布局

显而易见，不是所有的PLPA都是可以被折起来的。为了定义可折叠性，我们假设纸上除了边界之外都是用刚性材料（如金属）制成（边界使用铰链）。此外，我们认为纸是没有厚度的。这两条假设有助于我们将可折叠性和可实现性作为简单的几何属性进行公式化。请注意类似的假设在刚性折纸中也有[Belcastro and Hull 2002]。基于刚性假设，我们定义可折叠性为两个PLS之间的一种关系：
定义3： 给出两个PLS $S,T$，$S$被成为可以从$T$折叠得到，当存在一个连续映射$f:T \rightarrow S$满足如下条件：
1. $f(0) = T, f(1) = S$
2. 对任意的$t \in [0,1], f(t)$是一个PLS并且包含$T$中的刚性连续块

映射$f$称作从$T$到$S$的折叠变换

我们感兴趣的是可以“一直”可以被打开或者闭合的PLPA。我们称一个PLPA或则任意由PLPA得到PLS的中央折叠线的外角为折叠角（例如，PLPA的折叠角为0），注意，在我们的定义里严格来说一个PLPA不能够完全地闭合（也就是折叠角不能为180°），因为后背和底面不能够重合。因此，接下来我们公式化给出可折叠的布局：
定义4： 称一个PLPA $T$可以被折叠，当存在一个从$T$开始的折叠变换$f$，使折叠角单调地从$0$增加到$180°-\epsilon$,$\epsilon$为一任意的小角度。这个变换$f$就成为$T$的弹出变换，并且称任意一个$f(t),t\in[0,1]$为折叠可弹出的。
例如，图3（a）中的PLPA是可折叠的，一个折叠角为90°的折叠可弹出面在（b）给出

3.3 Realizable layouts可实现的布局

上文定义的可折叠PLPA在用户打开或者关闭后背和底面时或许并不能“弹出”。例如，PLPA可能包含跟后背或者底面连接的块，所以就需要额外的支撑。另外，弹出变换中也可能需要其他沿折叠线的力以使它们可以在现实中升起。理想状态下，我们不需要除了打开和关闭后背和底面之外的其他力，就能够制作出一个稳定的纸结构，并且打开或者关闭的每个阶段都可以在后背和底面都固定的情况下保持整个结构的稳定。
我们在上面的刚性假设下作出可实现性的定义。直觉上，一个PLS包含一些特定块，当PLS被折叠到其他状态而不能保证这些特定块不变，那么就认为这个PLS是稳定的。另外，如果PLPA在一个连续的折叠过程中的每个时间点都是稳定的，那么从前一个时刻到下一个时刻既不需要除了移动后背和底面的额外的力。正式地，我们定义：
定义5：给出一个PLS $S$和一个块子集$P \subset S$,称$S$对$P$是稳定的，当没有另一个PLS $S'\neq S$并且$S'$从$S$通过一个折叠变换$f$得到，而$P$在变换$f$中保持不动。
例如，图4（b）中的阶梯例子不是一个稳定的PLS，因为它可以连续的折成（c）的形状而不影响块的刚性。相反，图3（b）和图4（a）则是。最后我们定义可实现的布局：
定义6 一个PLPA $T$具有可实现性，当它是可折叠的，并存在一个$T$的折叠变换$f$，所有的$f(t),t \in [0,1]$是对后背和底面稳定的PLS。这个折叠变换$f$称为可实现的折叠变换，并且任意$f(t),t \in [0,1]$称为可实现弹出的。

4 Sufficient conditions充分条件

我们算法的目标是构建一个可实现的平面布局，在折起的时候去拟合给出3D模型。我们因此需要回答一个逆向的问题，给定一个3D平面（例如，一个PLS），它是可弹出实现的吗？
本文中，我们考虑了一种特殊的PLS，这种PLS可以继承充分、可计算的课可实现条件。这个条件可以指导我们的算法设计并且保证我们结果的正确性。
定义7 一个平行PLS $S_{v,w}$是一个所有块的法向要么是$v$要么是$w$,$v和w$是不相等的两个单位向量
例如，图3（b）和图4（a，b）都是平行的PLS且$v,w$是正交的。注意到大多数的纸结构都落入到这一类中，比如图2。我们先展示折叠可弹起的平行PLS的条件：
命题 1 考虑一个平行PLS $S_{v,w}$令$U=v \times w, V = w \times U, W = U \times v$（像图3（b）展示的那样）。如果$S_(v,w)$在$V + W$方向上向一个法向为$v$的平面进行的平行投影是PLPA那么$S_(v,w)$就是折叠可弹起的。
证明: 考虑在包含原点的平面上的平行投影$T$。我们会表明$T$是一个可折叠的PLPA通过构造一个从$T$开始经过$S_{v,w}$的折叠变换
我们可以如下表示$S_{v,w}$中的任意一点$x$:

$$x = (x_U, x_V, x_W) \cdot (U,V,W) \tag 1$$
注意$U,V,W$是线性相关的，因此分解因式不同。考虑如下连续映射$f$，$f(t)对t \in [0,1]$由如下点构成
$$x(t) = (x_U, x_V, x_W) \cdot (U,V(t\pi),W) \tag 2$$
对所有的点$x \in S_{v,w}$。这里，$V(\alpha) = w(\alpha) \times U$其中$w(\alpha)$是$v$绕$U$旋转$\alpha$度得到的向量。我们展示$f$的若干属性:

• $f(0) = T$。实际上，对于任一点$x \in S_{v,w}$,$x(0)$就在法向为$v$包含原点的平面上啊，并且$x-x(0) = x_V(V + W)$
• $f(t) = S_{v,w}$,对$t = \theta / \pi$其中$\theta$是$v,w$之间的角
• 对于任意$t\in[0,1)$, $f(t)$是不交叉的，因为因式不等(当$t>0$)并且PLPA有不相交的属性
• 变换$f$包含$S$中块的刚性。实际上，对于$S_{v,w}$中的同一块法向为$v或w$的块上的任意两点$x,y$，$x(t),y(t)$会落在共同的或者与$v(或w(t\pi))$正交的面上。并且，$||x - y|| = ||x(t) - y(t)||，t\in[0,1]$

所以，$f$是一个从$T$开始经过$S_{v,w}$的有效弹出变换，并且$S_{v,w}$是折叠可弹出的.$\square$

注意，命题1中的条件在给定的平行PLS中可被计算检查。我们的算法中，我们会构造一个平行PLS的特别的类，这个类在构造时就满足上面的条件。

进一步，我们有如下的充分条件可以使平行PLS被刚性和稳定的弹出：
命题 2 称一个满足 命题1 的平行 PLS $S_{v,w}$是可实现弹出的，当它进一步满足如下条件：$S_{v,w} = \{p_1,\dots, p_n\}$存在一个块序列，其中$p_1, p_2$对应于后背和底面，对任意$k\in[3,n]$，都有:
1. $p_k$连接两个平行的，不共面的块$p_i,p_j$其中$i,j \lt k,$或者
2. $p_k$连接到$p_{k+1}$,并且 $p_k, p_{k+1}$对应地连接到$p_i,p_j$其中$i,j \lt k$并且 $p_i, p_{k+1}$不共面

证明
我们首先给出满足上述两个条件的平行PLS $S$对应于$p_1,p_2$是稳定的。我们从两个方向观察。首先，当两个不共线的边固定，那么一个刚性块便会固定。第二，考虑两个刚性平面块$p_a, p_b$和公共边$e$。那么当存在$p_a$的边$e_a$,$p_b$的边$e_b$，其中$e,e_a$不共线，并且$e_a,e_b$固定，则$p_a$固定。根据这些观察，很容易归纳出$S_{v,w}$的块是稳定的。
根据命题1，$S_{v,w}$可以从PLPA $T$通过等式（2）定义的变换$f$得到。注意两个条件在变换过程中都是保持的，这些条件保证了块之间的连接性和平行性。因此，$T$是一个可实现的PLPA并且$S_{v,w}$是可实现弹起的。$\square$

例如，图4（a）中的平行PLS使用图中所标记的顺序，依据上面的条件判断可实现弹出的。相反的，在图4（b）中找不到这样的序列。

5 The algorithm 算法

我们方法的输入是一个用户指定后背和底面位置的3D模型。算法的输出是一个表现了可实现弹出的、拟合了输入模型的平行PLS的纸结构。本文中，我们焦点在于90°折叠角的平行PLS，这些PLS包含了大部分的模型，包括城市建筑。这个算法可以很容易的适配其他角度。为了在满足前面章节条件时更好地抓住模型的几何特性，我们分三步处理（像图5刻画的那样）：
1. 可折叠弹出的面：首先，我们算出一个初始的、拟合输入模型的平行PLS。它由笛卡尔网格中正交的面组成。这个初始化的PLS被成为“可视化PLS”。根据命题1，我们的构造过程可以保证折叠可弹出性（图5（b））。
2. 可实现弹出的面：接下来，我们进一步修改可见面，在保持它的可折叠性的情况下，满足命题2中的可实现性条件。这里采用的是一种贪心、区域增长的算法。
3. 几何细分：最后，上面在笛卡尔网格中计算出来的弯弯曲曲的平面在保持可实现性的前提下被细化。（图5（d））

5.1 Computing the visible surface 计算可视化面

我们算法输入是一个代表了3D矩形块的模型（可以被打开或关闭），以及用户指定的后背和底面平面。因为我们焦点在90°的折叠角，我们让后背和底面两个平面正交。不失一般性，我们假设它们是方形，对应于$XZ$和$XY$平面，中央折叠线在X轴的位置，就想图5（a）中所展示的那样。

为了构架一个90°折叠角的平行PLS，我们使用笛卡尔网格中与坐标轴对齐的面。我们构造一个$N \times N \times N$的全局网格，使用后背和底面作为两个面，并且标识出所有跟输入有关的方块。在所欲被标识的方块中，我们称所有跟$Y$或$Z$轴垂直的面或者落在后背或底面的面，为模型面。我们会选择这些面中的一个构造一个折叠可弹出的PLS。
为了满足命题1中的条件，关键的要求是平行PLS $S_{v,w}$沿特定方向的投影可以产生一个没有交叉的集合。沃尔玛呢的例子中，$v = (0, 0, 1), w = (0, 1, 0)$，投影方向为$(0, 1, 1)$。因为所有的弹出体通常是要从外部可见的，我们简单的认为从网格外看所有在(0, -1, -1)方向上可见的模型面都是“可见的”。这些面称为“可见面”，图5（b）中有展示。注意到这个观察方向，和坐标网格的全局排列，确保了所有的可见面是不连续的。由于后背和底面的边界部分也是可见面，它们的投影会产生一个矩形区域。因此课件面的集合是一个折叠可弹起的PLS，我们称为可见PLS。

5.2 Computing a popup-realizable surface 计算一个可实现弹出平面

可见PLS是一个折叠可弹出的PLS，它“包裹”在模型的外部。为了进一步保证可实现性，我们会构造一个PLS，它有可见PLS中的形状和可折叠性，同时也要满足命题2中的条件。

我们首先提出一个生成一类折叠可弹出PLS的方法，然后找出它们对应于可见PLS的错误。我们称所有在后背或底面的网格面$b$为基面，所有沿方向(0, -1, -1)投影到基面的面称为候选面，记作$H(b)$。可以看出，$H(b)$在$Y$或$Z$方向上可选的方向上产生了“阶梯状”，像图6中显示的那样。同样基于上面的讨论，任何一个基面有唯一对应的候选面的PLS，就是一个折叠可弹出的PLS。我们可以用如下方法，在观测叫方向上衡量任意的折叠可弹出的PLS $S$和可见PLS $S_0$的差异：

$$E(S, S_0) = \sum_{b \in B} ||S(b),S_0(b)||$$
其中$B$是所有基面的集合，$S(b),S_0(b)\in H(b)$对应于$S,S_0$中投影到$b$的面（图6）。 $||\cdot,\cdot||$表示两个面的中心的欧几里得距离。
我们适配了一种贪婪的、区域增长的方式去构造一个折叠可弹起的PLS $S$，在满足命题2中的块序列条件的前提下最小化上面的错误数。我们首先在$S$中包含后背和底面的块，这些块需要是后背和底面上的可视块，并且要连接到对应平面最外围的块（图7（b））。然后向内进行，每次向现存块中添加一个面(图7（e）);或者添加一个包含面的块，这个块得和现有块连接在一起（图7（c）（d）），添加的方法需要满足命题2中的条件。
特别地，我们维持一个包含与代价关联的两种元素的优先队列。我们称一个基面$b$可访问，当$b$在$S$中有一个候选面，否则称为不可访问。队列元素可以是临近于可访问基面的不可访问基面，或者是两个可见基面之间，拥有相同X坐标的不可访问基面组成的路径。对于第一种，S中平行且临近现存面基面的代价在所有的候选面中是最小的（例如，图7（e）中标识出的两个面是平行切临近于S中的现存面的）。对于第二种，令基面路径为$\{b_1,\dots,b_m\}$，其中只有$b_1,b_m$是可访问的。我们考虑所有的路径，每一条都由基面$b_i$对应的候选面$S(b_i)$组成，其中$i \in [2,m-1]$，这些路径以图8上面的某一种形式连接端点$S(b_1)和S(b_m)$（例如图7（c，d）中标识的路径）。基面的路径的代价在所有候选面中是最小的，如果存在的话。否则代价就是无穷大。每一次迭代中，最小代价的元素（们）会被从队列中移除，具有此代价的候选面被加入$S$，并且队列依此更新。队列为空时算法结束。

可以注意到算法的结束是有保证的，因为第一种类型的元素（即，添加一个面到现存的块）总是关联一个有限的代价。同时，图8上的路径模式保证新添加进$S$的块都满足命题2中的条件，因此$S$在算法结束之后就是可实现弹出的。图5（c）是一个结果的样例。

　5.3 Geometric refinement 几何细化

前两步的结果是一个可以从平面布局被刚性和稳定的形式弹出的面。然而，使用网格面导致块存在不整齐的边，既不好看也很难裁剪。最后一步，我们运用一个简单的操作在保持可实现性的前提下减轻这些不整齐。

把我们的可实现的PLS $S$的平面布局考虑为它以（0, 1, 1）方向在XY平面上的投影。布局的裁剪和折叠线落在拓展的笛卡尔网格的网格线上（图9左显示了一个例子）。通常，裁剪线（图中黑线）由$S$中不相邻的网格在XY平面投影出来的网格共享的线组成。裁剪线上的顶点p是由两个或者多个块的边界点投影得到的。我们称这些边界点为$p$的影。

为了平滑块的边界，我们通过调整块的边缘让它可以投影到修改过的边界，以此来平滑平面布局中的裁剪线。特别地，对于裁剪显中的每一个顶点$p$，我们会在XY平面上给他一个新的位置$p'$，通过顺着对应的块所在的平面移动$p$的影，让这个块投影在$p'$处。这很容易通过如下方式做到： 令$(\Delta x, \Delta y, 0) = p'-p$,如果$p$对应的边界点$q$在一个与XY平面平行的块上，那么$q$也按照向量$(\Delta x, \Delta y, 0)$，否则按照向量$(\Delta x, 0, \Delta y)$移动。注意如果$q$既在平行又在垂直的块上的话（比如投影到平面布局上折叠线的点），$q$只在X方向上移动。为了保证移动足够简单，并且避免在移动中产生交错，我们限制给每一个裁剪线上的点$p$一个“安全区”。像图9右边中展示的那样，如果顶点不在折叠线上，那么安全区是方形，否则是一条线段。注意顶点安全区内的所有点都可以作为新的块边界点的位置，并且保持面的可实现性。
为了平滑平面布局中的裁剪线，我们改进了把每一个顶点向它的相邻点的中心移动的标准可迭代的基于拉普拉斯的策略，依照安全区对其移动进行限制。为避免波动，我们每次迭代只移动一个顶点而不是同时移动。图5（d）显示了平滑之后的结果样例。

6 Results 成果

图10中展示了我们的实验成果，图1，图5,图12，图13是一些其他的成果。所有的模型都是从Google 3D Warehouse中得到的，且在体元化中令$N = 128$。看得到输入几何图形时，得到的纸结构拟合的很好。抓住了很多细节，比如空中花园的柱子（图1），纽约生活大楼的屋顶（图13）。因为我们的算法对包含在两个方向上平行块的纸结构的限制，模型中平行和竖直的面，在倾斜和弯曲平面来进行阶梯状折叠拟合时被很好的保留。（像图5中的埃菲尔铁塔，图10中的玉带桥，塞尔托教堂）。注意这些折叠样式在人工的纸结构中也出现了（图2中姬路城弯曲的穹顶）。
我们算法保证结果的可实现性，也就是说，每一个纸结构都能够刚性且稳定的从他们平面布局中弹出。为了证明可实现性，图11中展示了依照图1和图5中的布局制作的样品。他们弹出的过程在相关的视频中完整呈现。
我们方法也是高效的。本文中所有的例子都在1秒不到的时间内计算出来，计算机配置为Intel Core 2 Duo 3GHz，内存4G。因为这个方法可以给用户以即时反馈，所以对结果进行可交互的编辑是可能的。尽管制作一个全功能的可交互设计工具不在本论文讨论范围之内，我们目前的框架还是可以完成大部分的编辑操作。第一，用户可以指定后背和底面的位置。图12展示了不同位置时的例子。第二，用户可以修改平面布局中的裁剪线的位置，跟我们在平滑步骤中所做的类似，便于得到更文学化的块边缘。第三，用户可以选择布局中特定的区域剪掉，形成空洞。这两种操作都在图13中有体现，文学化的窗户和鸟是由剪切和调整建筑上的裁剪线倾斜得到的。

7 Conclusion and discussion 结论和讨论

本论文中，我们提出了一种关于纸结构的几何公式，集中在弹起过程中的刚性和稳定性，这些在实现制作这些东西的时候很重要。基于这个公式，我们可以给出让一类3D面可以被弹起的充分条件，并且进一步给出了一个在少量用户输入的情况下，可以把3D模型转换成纸结构的算法。这个算法在产生可实现的纸结构上是鲁棒的，也是高效的。我们展示了一系列建筑模型和根据这些模型制作的实物的例子。

不足 虽然目前的算法着力于可实现性，但是它并不能达到一个完全令人满意的“外形”，尤其是跟熟练的艺人制作的样品比起来（图2）。要注意的是，这些作品中经常用到极端抽象，像图2中的图书馆雕像，视觉上很有吸引力。达到很吸引人的效果根本上就是一个很有挑战的任务，这点在图形学其他方面不断地得到证实，比如图形分割和非拟真渲染。
当输入的模型大多数是水平和竖直的平面时，我们的算法表现最好，并且这是也被后背和底面完美支撑（传统建筑模型中可以得到验证）。当这些条件都没有满足，算法会很大程度地修改输入模型来保证可实现性。图14中，我们展示了两种极端例子，一个漂浮的方块和半个圆环。
第一个例子中，算法把方块“推向”角落，让他和后背和底面连接。第二个例子中，圆环中被围住的位置被“填满”了，以便于它可以被稳定地弹起。图15进一步展示了两种生物模型，可以看到结果，尽管模拟了输入，还是丢失了大量的特征（比如，兔子的头）。要想可靠地重做这些普通的图形，可能需要多于一张纸（像弹出纸的书那样）。
未来工作 我们的工作打开了很多未来有趣的研究方向的大门，这些研究可能在理论和算法方向都对现在的工作都有扩展。在理论方面，在生成稳定性和可折叠性方面仍然还有提升空间。例如，当前的稳定性条件（命题2）只是充分的，因此可能干扰了一些稳定条件。理想状态是找到一个充要条件，并且可以拿来判断一个给定的PLS（比如，通过其他计算机辅助工具做的）是否是稳定的。此外，找到使不平行PLS也有折叠性和稳定性的条件，可以让我们更好地表现模型中的斜面。更进一步，把纸的物理特性考虑进可实现性中，比如纸的厚度，质量和柔软程度。另外，探索我们对于PLS的定义，该如何放松才能允许在块之间有空隙，并且对于有质量的非刚性块该如何对可折叠性和稳定性公式化。
算法方面，我们打算首先探索除了现在的贪婪块增长算法之外的实现PLS的算法（5.2章节）。第二，几何细化步骤中（5.3章节），可以参考原始的模型，从而更好地保护模型特征。进一步的，像上面提到的，探索结合艺术家的抽象规则到我们的算法中以产生更艺术化的结果。最后，当前的工作很少考虑用户输入，下一步我们要设计一个集成交互系统，在保证可实现性的前提下给用户灵活的控制。这些控制应该包括调整模型不同部位的精细程度，在纸结构上更改块，交互式地创建新的折叠样式（比如一条缝和v形）

致谢