用于镶嵌变形的曲线演化方案

女士们，先生们，老少爷们儿们！在下张大少。

本文探讨如何对拼花地板变形中构成边缘的曲线进行美观的演化的问题。在正方形拼块简单排列的框架内，我探索了基于网格、迭代函数系统和迷宫路径的曲线演化模型。

1 引言

拼花变形是威廉·赫夫（William Huff）在60年代初发明的一种平面设计风格[4，第10章]。每个设计都是一种平面上的 "空间动画"，是一种拼块沿着一个（有时是两个）维度逐渐演变的过程。在一份未发表的手稿[5]中，Huff指出了与埃舍尔的变形艺术的美学联系。拼花地板的变形旨在成为抽象的形式练习。他工作室里的例子都是白色背景上的黑色线条画。

在以前的工作中[6]，我研究了与构建拼花变形有关的数学挑战。我选择在等面体翻转的背景下看待这个问题，这是一类表现力强但在算法上可操作的由单一形状的副本构成的平面翻转[7]。给出两个任意的等面体原型。我问是否存在一个能在关键帧之间平滑插值的拼块补丁。随着两个画格的拼块共享较少的几何属性，我定义了这个问题的一连串越来越难的变化。

以前的工作主要关注识别对应的边的问题，期望任何插值算法都可以应用于发现的对应边。那篇论文中的所有例子都是用一种理想化的算法在两条片状多边形路径之间进行基于长度的线性内插，这种方法的一个例子见图1。在本文中，我考虑了一个正交问题。也就是说，我假设拼块布局是固定的，边缘对应关系是微不足道的，并专注于不同的可能插值算法和它们提供的美学可能性。

为了本文的目的，我考虑由拓扑类型（44）的单一等面体拼块（其中所有拼块都是四边形，每个顶点周围都有四面体）构成的拼花变形。此外，我将拼块的顶点固定为一个正方形晶格。所有这些拼块都可以通过系统地修改，所有这样的密铺都可以通过系统地修改单位方格的无限规则密铺的边来构造。我还假定，目标是将原型的最初直边 "进化 "为更复杂的形状（而不是在两个任意原型之间变形）。在这种情况下，大多数拼块理论的考虑变得微不足道；剩下的就是选择如何进行拼块边缘的演变。在这里，我提出了三种有希望的曲线演化的可能性，生成有趣的拼花变形。它们是：一种基于网格的、以离散步骤演化的方法（第3节），一种基于迭代函数系统的方法（第4节），以及一种基于迷宫式路径演化的方法（第5节）。

图1：拼花变形的一个例子，通过一个简单的分段多边形路径的线性插值构造，定义了一个原始拼块的边缘。在本文中所有的拼花变形中，图的左侧是等面体拼块类型。

2拼花地板变形框架

本文中的拼花变形是基于对等面体拼块边缘的操作，其拓扑结构(44)和拼块顶点固定在一个方形晶格中。我已经开发了一个软件库，用于表示属于这一类的原型的形状，并用于渲染所产生的变形。该库使用先前描述的数据结构和算法[7]来表示边的形状，在内部共享边的表示，以表达拼块边界的冗余度。渲染算法认识到，每块拼块都与无限网格中的一个正方形对齐。该拼块的方向是由正方形的八个对称性之一给出的，可以通过给出一个由水平和垂直平移重复的矩形网格的方向来紧凑地编码。

与以前的工作不同，每个拼块边缘都由一个额外的时间参数t在[0,1]的范围内进行参数化，允许边缘在不同的时间值下被查询时进行演变。每一个被放置的原型副本都会取代一个无限方格中的某个单位方格。这个正方形边缘的中点的（x，y）坐标被传递给一个 "参数空间"，一个为平面上的每一个点分配时间值的函数。一个典型的参数空间会在最终将被绘制的拼花变形的最小和最大x位置之间线性插值时间值。这些时间值被传递给参数化的边缘，所产生的曲线被串联起来以产生被放置的拼块的边界。

3 基于网格的曲线

在Huff记录的拼花地板变形中，我们发现有几种情况，即通过连续增加小单位的方形凹陷，使直的拼块边缘演变为曲折的路径。这种方法在对图案的所有改变都必须通过手工计算和绘制的情况下是自然的。当然，这也是一种很适合软件实现的技术。

让平面被无限的单位正方形网格覆盖，并沿着正方形的边画一条简单的连接直线路径。路径上具有一条或多条边的任何正方形都可以用于定义对路径的修改，方法是强制它沿着当前不在路径上的边绕着正方形行进。结果只取决于最初位于路径上的正方形的边的数量(我们禁止会产生带有循环或自相交的路径的修改)。图2中的例子总结了可能的局部修改。

图2：与正方形网格边缘的路径相邻的正方形所引起的三种可能的修饰。每对图中的左图显示了初始曲线，并突出了定义修改的正方形。右图显示的是修改后的曲线。

图3：基于网格的演化路径的发展演示。最初的直线路径在左边显示为一个正方形网格。网格中的方块被编号，以表示它们的编辑将被应用于初始曲线的顺序（具有相同编号的方块可以以任何合法的顺序应用）。右边的序列显示了由这种编号产生的所有路径。底部的一排拼块显示了对IH41型样品原型的两个边缘使用这一曲线的情况。

现在可以通过一系列这样的修改来构建进化路径。沿着正方形网格中的n个连续边放置初始直的路径P0。然后，我们选择一个正方形序列{s1，...，sm}，约束条件是sk与通过应用由s1，...，sk-1定义的修改而获得的路径相邻。只要路径不会形成环路或自交点，结果就是m条新路径P1，...，Pm从一条直线段演化而来。要在时间t评估这条曲线，我们只需返回Pmt。

在实践中，我们可以提供更大的灵活性和表现力。最重要的是，几个方块可以被组合在一起，以便它们的修改被 "同时 "应用（相对于t）。图3显示了一条具有这种额外属性的演化曲线。在图的底部，路径演化的六个阶段中的每一个都重复了三次。还要注意的是，在一连串的修改中，一个方块可以被访问不止一次；第二次访问只是将第一次的效果逆转。

我创建了一个交互式工具，在这个工具中，一个n×n的正方形等面体原型被嵌入一个正方形网格中。设计者以任何顺序选择网格方块，并可以根据所产生的路径预览拼花地板的变形。该工具将设计者限制在合法的方格（那些与当前原型边界相邻的方格，并且不会导致非法的拼块形状）。系统会自动将任何局部编辑传播到拼块边界上所有与对称性和可铺设性有关的位置。

由此产生的拼花地板变形具有机械的直线外观。对我来说，最吸引人的结果是通过继续修改原拼块的边界，直到拼块内部不包含任何2 × 2方格。图4是基于IH41等面体类型的简单示例；图5中有更多示例。

图4：通过基于网格的路径的离散修改构建的拼花变形的示例。在这种情况下，时间参数由“tent”函数控制，该函数在设计中心为1，在边缘为0。此图(以及论文中的其他图)中的最终几何图形是在Adobe Illustrator中编辑的，以调整线条宽度并使用颜色渐变填充图块。

图5：通过方形网格路径的离散修改构建的拼花变形的更多示例。

4 迭代函数系统

一种流行的、有吸引力的演变曲线的技术是使用迭代函数系统（IFS），它将曲线的细节逐渐增加，在极限中产生一个分形。在这种情况下，IFS只是一条从(0,0)到(1,0)的片状线性路径。通过反复用整个路径的适当转换副本替换其每一段，该路径可以被细化到任何数量的世代（见图6）。变换可以选择在该段上进行反射，也可以对该段完全不进行替换。

图6：一个简单的迭代函数系统。最上面一行显示的是用八条等长的线段组成的路径替换一条线段的规则。底部一行显示的是这个规则的零、一、二和三次应用后的路径。这条规则被用来构建图7中的顶部拼花变形。

在这一点上，似乎很自然地采取了一连串的路径，每条路径都是通过替换其前身而构建的，并将它们作为单一进化曲线的离散步骤，就像上一节所说的那样。然而，我发现IFS中各代之间的过渡过于突然，无法产生美观的拼花变形。一个简单的折衷办法取得了令人满意的结果：我们将路径序列从t=0到t=1均匀地隔开，并在t的中间值的相邻关键帧之间进行线性插值。虽然线性插值的结果是可以接受的，但可能有一些插值算法更适合这项特殊的任务。一个更智能的算法会考虑到一个片段和它在未来几代中的 "后代 "之间的局部关系，对于任何t值，都可能包含来自几个（或所有）未来几代的指数递减的细节。

图7显示了通过给原型中的所有边分配一个单一的迭代函数系统而产生的三个拼花变形的例子。图8显示了另外一个基于希尔伯特曲线的例子；这需要额外的工作，因为其替换规则不像普通迭代函数系统那样简单。

图7：基于连续几代迭代函数系统之间的线性插值的拼花变形的三个例子。

图8：基于希尔伯特曲线的生成步骤的拼花变形。

5 迷宫式曲线

在构建迷宫的背景下，Pedersen和Singh开发了一种几何模拟，将简单的初始曲线演化成曲折的有机形式[10]。在他们的算法中，曲线上的点经历了布朗运动和几何平滑，并受到其他点的物理吸引和排斥力。这些力受到化学中伦纳德-琼斯势的启发，导致附近的点寻求一个 "静止距离"，在这个距离中，吸引力和排斥力被抵消。这种算法产生的曲线让人想起TSP艺术[8]和哈特增长形式[3]中的形状，尽管Pedersen和Singh提供了大量的（空间变化的）调整参数，可以产生更独特的结果。

我采用了Pedersen和Singh的算法来制作具有迷宫边界的等面体原型。原型边界根据它们的模拟而演变，但也有一些重要的例外。首先，正方形的角点必须保持固定，因为在最终的拼花地板变形中，这些角点将成为密铺顶点。其次，由于边缘匹配和内部拼块对称，边界包含冗余信息。密铺边界上一个点的新位置必须考虑到不仅对该点施加的吸引力和排斥力，而且还必须考虑对其所有冗余副本施加的吸引力和排斥力。这些单独的力可以加在一起，以获得点及其副本的单个共享表示的最终位移。

仿真被允许运行，直到达到一个理想的最终形式（通常是几百到几千次迭代，基于一个足够小的时间步长，以避免数值不稳定）。仿真过程中创建的每一个拼块轮廓都会保存一个快照。一旦模拟完成，快照的一个子集，在时间上均匀间隔，被提取出来并作为关键帧使用。由于模拟的固有平滑性，关键帧之间没有必要进行插值。

图9显示了三个有机拼花地板变形的例子。

图9：基于Pedersen和Singh的有机迷宫式增长算法的三个拼花变形实例。

6结论

本文探讨了拼花地板变形设计空间的一小部分。我有意减少了作为设计框架的拼块的自由度，并在这种情况下专注于曲线演化的三个独立算法。即使在这个领域中，也可以发现各种各样的审美机会，这表明拼花地板变形的更大世界可以作为艺术灵感的无穷源泉。

本文描述的软件框架可以通过多种自然方式进行扩展。未来工作最明显的路径是探索曲线演化或变换的其他算法。在计算机图形学中，人们一直认为曲线的线性插值会产生不美观的结果。更有原则的方法，如Sederberg等人的方法。[11]或者尽可能严格的方法[1]可能更健壮，更美观。我还想试验曲线简化算法，例如标准的Douglas-Peucker方法[2]或Mi等人最近的抽象技术。[9]。

给出一个更丰富的曲线演化策略工具包，还应该可以在空间上(在单个块的不同边缘上)或在时间上(在单个边上按顺序，随着时间的推移)并列多个算法。

参考文献

[1] Marc Alexa, Daniel Cohen-Or, and David Levin. As-rigid-as-possible shape interpolation. In SIGGRAPH ’00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques, pages 157–164, New York, NY, USA, 2000. ACM Press/Addison-Wesley Publishing Co.

[2] David Douglas and Thomas Peucker. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. The Canadian Cartographer, 10(2):112–122, 1973.

[3] George Hart. Growth forms. In Craig S. Kaplan and Reza Sarhangi, editors, Proceedings of Bridges 2009: Mathematics, Music, Art, Architecture, Culture, pages 207–214. InType Libra, 2009.

[4] Douglas Hofstadter. Metamagical Themas: Questing for the Essence of Mind and Pattern. Bantam Books, 1986.

[5] William S. Huff. The Parquet Deformations, from the Basic Design Studio of William S. Huff at Carnegie-Mellon University, Hochschule fur Gestaltung and State University of New York at Buffalo from 1960 to 1980. Unpublished.

[6] Craig S. Kaplan. Metamorphosis in Escher’s art. In Bridges 2008: Mathematical Connections in Art, Music and Science, pages 39–46, 2008.

[7] Craig S. Kaplan. Introductory Tiling Theory for Computer Graphics. Morgan & Claypool, 2009.

[8] Craig S. Kaplan and Robert Bosch. TSP art. In Bridges 2005: Mathematical Connections in Art, Music and Science, pages 301–308, 2005.

[9] Xiaofeng Mi, Doug DeCarlo, and Matthew Stone. Abstraction of 2d shapes in terms of parts. In NPAR ’09: Proceedings of the 7th International Symposium on Non-Photorealistic Animation and Rendering, pages 15–24, New York, NY, USA, 2009. ACM.

[10] Hans Pedersen and Karan Singh. Organic labyrinths and mazes. In NPAR ’06: Proceedings of the 4th international symposium on Non-photorealistic animation and rendering, pages 79–86. ACM Press,2006.

[11] Thomas W. Sederberg, Peisheng Gao, Guojin Wang, and Hong Mu. 2D shape blending: An intrinsic solution to the vertex path problem. In James T. Kajiya, editor, Computer Graphics (SIGGRAPH ’93 Proceedings), volume 27, pages 15–18, August 1993.

[12] Craig S. Kaplan, Curve Evolution Schemes for Parquet Deformations

青山不改，绿水长流，在下告退。

转发随意，转载请联系张大少本尊。