Figure 1：CPMesh优化后的曲面。黑色线为优化后的网格三角面边线，蓝色线为InCircle Packing（每个三角形的内切圆）红色线为Circle Packing，绿色线为三角形的对偶。（作者自制）

Circle Packing在各个领域中的应用

相信很多参数化设计师对于Circle Packing这个概念早已不感到陌生，若干年前Daniel Piker就在他的神作Kangaroo中引入了圆堆碰撞相关的Goals来实现这种形式的优化。类似图2所示，很多数字艺术家痴迷于Circle Packing的形式美，他们用不同大小的圆（通常将圆的半径和图案的某个像素的颜色相关联），通过碰撞的方法来实现彼此互相相切，形成美丽的图案。然而，该算法不仅仅是能得到这些形式，它还能作为一种优化目标，来给网格带来某些特定的性能。

Figure 2：以Circle Packing算法为概念的艺术创作图片来源：https://houdinigubbins.wordpress.com/2017/04/23/circle-packing/

Circle Packing还跟折纸相关的算法有着密切的联系。麻省理工学院就有开设几何折叠算法（Geometraic Folding Algorithms）课程，主讲教授为Erik D.Demaine，一个有意思的结论是数学理论证明，如果纸足够大，没有厚度，你可以折出任何你想要的形状。想了解关于这方面的信息可以点击由清华纸艺社的推送《Circle Packing设计理论简介》

Figure 3：Circle Packing算法与折纸图片来源：《Circle Packing设计理论简介》

如图4，是曲面间的拟共形映射。在这方面的研究，笔者知识覆盖面有限，这方面仍在学习当中，暂且不谈，挂在这里只是为了让大家知道Circle Packing里还有很多有意思的研究方向。

Figure 4：曲面间的拟共形映射。左帧曲面的每一个小圆盘区域都映射到右侧椭圆盘区域。椭圆域的偏心率和方向给出了Beltrami系数，Beltrami系数决定了映射。图片来源：《拟共形映射理论 Quasi-Conformal Mapping (I)》，作者：顾险峰，公众号：老顾谈几何

Circle Packing（准确的说是CPMesh优化）在建筑幕墙中也有广泛应用。在建筑幕墙中，玻璃-钢结构的幕墙可以看作是网格顶点、边和面的物理实现，相反，网格是这种结构的数学抽象。经过CP Mesh优化衍生得到的对偶网格可以得到无扭曲节点（Torsion-Free Nodes）：如图5、7所示，无扭曲节点中的梁单元中心的平面是共轴的，这样我们可以沿着网格边来布置梁单元。从结构的角度看，这种无扭曲节点可以消除幕墙节点的扭转，增强节点稳定性、简化节点构造和制造。一般来讲，幕墙中最理想的状态是板与板之间的力的方向要在曲面以内，如果有垂直于幕墙板法向上的力时，嵌板的抵抗能力较差。因此消除扭转的作用是十分重要的。
无扭曲节点可以确定一个公共轴（要知道无轴节点在建造和制造的处理要比有轴节点复杂得多，见图6），可以提高对幕墙的预制和可控能力，并与多层网格兼容。它也可以结合平板优化和支撑结构（使用具有平面和无扭曲节点性质的网格是非常理想的），能够产生一个水密的玻璃-纲结构。事实上CP Mesh优化并不是幕墙优化的主流做法，关于这个问题和幕墙的其他相关技术在后续关于PQ Mesh的章节还会提到。

Figure 5：一个无扭曲支撑节点，这里中心平面和同一轴相交图片来源：《Isogonal moulding surfaces: A family of shapes for high node congruence in free-form structures》

Figure 6：一个无轴节点图片来源：《Architectural Geometry》

Figure 7：(a) 无扭曲支撑结构示意图。(b) 阿布扎比亚斯总督酒店幕墙上的无扭曲支撑节点。对于每一条边和顶点的四边形网格，我们能够得到平面和一个线，均在平面上。阿布扎比亚斯总督酒店的外部幕墙参考了这种支撑结构方式，使构件与每个节点之间形成了一个很好的连接关系（见图7(b)）。具有无扭曲节点的网格也称为圆锥网格，因为属于同一节点的所有面都与同一圆锥相切。图片来源：《Geometry and Freeform Architecture》

CP Mesh优化原理

CP Mesh（Circle Packing Mesh）最初是为了使建筑和设计中的自由曲面合理化（生成无扭曲节点）而开发的，如图8所示，它是一个三角形网格，绘制其内切圆可以形成一种Packing，以每个顶点为圆心，顶点到内切圆切点的距离为半径绘制球，这样就又得到了一个球Packing，以内切圆的中心轴线彼此相连又能够产生一种六边形的无扭曲的支撑结构。为了计算优化CP Mesh，我们首先需要建立一个基于原始网格的优化问题。因此这里需要通过建立一个能量函数来实现的，它必须能够测量Circle Packing特性、优化网格到原始网格的距离以及优化网格的边界到原始网格边界的距离。换句话说，无论我们使用什么能量函数，总是会对原始网格产生偏差，因此这个优化并不能对任意曲面有效，只能产生近似的Circle Packing。在描述这个优化算法前，我们先来了解一下CP Mesh相关的几何性质。

Figure 8：CPMesh是一种三角形网格，三角面片的内切圆（橙色圆）形成一个Packing。蓝色球体是以网格顶点为中心，与相邻三角形的内切圆正交，也构成了一个Packing。内切圆的中心轴线彼此相连又定义了一个六边形的无扭矩支撑结构(红色结构)。图片来源：《Packing circles and spheres on surfaces》

CP Mesh的几何性质

首先定义一个三角形，其顶点用 $v_1$ 、 $v_2$ 、 $v_3$ 表示，它的边被其内切圆（Incircle）相切于点 $t_{12}$ 、 $t_{23}$ 、 $t_{13}$ （如图9）。这些切点到顶点vi的距离用ri表示，举个例子， $r_1=||v_1-t_{12}|| = ||v_1-t_{13}||$ （角平分线性质定理）。边长 $l_{ij} = ||v_i-v_j||$ ，这就得到了 $l_{ij} = r_i+r_j, 2r_i=l_{ij}+l_{ik}-l_{jk}. (1)$

Figure 9：我们介绍了一个CP Mesh中一对相邻三角形中的定义：顶点，各内切圆的切点，距离。并且这里、、和是共面的。图片来源：《Packing circles and spheres on surfaces》

Ball Packing：我们以顶点 $v_i$ 邻接的三角形为例，如果我们想生成Ball Packing，那么通过顶点 $v_i$ 的所有边上的切点 $t_i$ 的距离 $r_i$ 必须是相同的。因此，在三角网格中 $r_i$ 是一个与顶点相关的值，我们以顶点 $v_i$ 为球心， $r_i$ 为半径就可以得到一个球 $S_i$ ，它与三角形网格相切于 $t_i$ 并正交于所有内切圆。因此可以说，Ball Packing正交于Incircle Packing。

当然，这里的Ball Packing和Incircle Packing是互逆的：显然任何Incircle和正交球的集合都能产生CP Mesh，每个球对应了一个网格顶点，内切圆对应了网格面，这样就形成了一种对偶（Dual）关系。当我们用这个Incircle-Ball的集合来表示CP Mesh时，它就可以变成一个莫比乌斯几何体（Mobius Geometry）的对象：莫比乌斯变换（Mobius transformation）能够将圆映射到另一个圆，将球映射到另一个球，并保留其正交性。因此它也能够将CP Mesh映射到另一个CP Mesh上，这一点的延申下去就可以回到上文提到的拟共形映射问题（如图4）。

在任意曲面上实现精准的Circle Packing是不可能的。这是因为相互接触的圆位于一个公共球面上，它们的旋转轴是共面的。因此，如图10，三对内切圆的轴线要么通过一个公共点，要么是平行的。进一步则可以推出，包含这些相切圆的精准Packing的所有圆要么共球，要么共面。对于四边形组合的Circle Packing不受此限制，但是只能适用于等温曲面（Isothermic Surfaces）。

Figure 10：三对内切圆的轴线要么通过一个公共点，要么是平行的。图片来源：作者自制

如图9，在CP Mesh中，我们看到两个三角形，和具有共同的边。通过(1)来表示边的长度时，我们马上能看到相反边的长度和满足等式

反之亦然，如果等式(2)成立，那么两个内切圆相切于公共点。为了证明这一点，我们将和分别关联到三角形顶点和上（两个内切圆是否交于一点未知，即和是否成立未知）。现在由条件(2)，可知，因此可推出和。

Figure 11：一种由Incircle Packing衍生出的Pattern，它由三角形、平面四边形和非平面六边形组成，由CP Mesh通过连接Incircle的部分切点得到。图片来源：《Packing circles and spheres on surfaces》

在平面上，一个满足条件(2)的四边形可以找到其内切圆，在空间中，条件(2)有一个有趣的结论：定义两共面直线 $v_2v_4$ 和 $t_{12}t_{14}$ 交于点c（可能在无穷远处），将一个内切圆通过中心c投影到其他三角形的平面上，就会得到另一个内切圆（因为三条切线和两三角形的两个公共点定义了一个圆锥）。因此直线 $t_{23}t_{34}$ 也经过点c，交点 $t_{12},t_{23},t_{34},t_{14}$ 是共面的（见图9、11），它们也位于包含两个内切圆的球上，因此四个点还位于以c为圆心的圆上。

Figure 12：以A为轴的双曲面H。图片来源：《Packing circles and spheres on surfaces》

另外，如图12，如果圆 $c$ 的轴 $A$ 与四边形每条边的夹角相等，那么所有的边都位于一个以 $A$ 为轴的双曲面 $H$ 上。进一步推出，距离 $t_{ij}$ 恒定的 $v_iv_j$ 边缘上的新点 $w_{ij}$ 位于一个公共圆上。

优化算法

为了对任意自由曲面生成近似的CP Mesh，论文《Packing circles and spheres on surfaces》中提出了一个优化算法来优化给定初始网格的顶点。目标函数为
$F=λ_1f_{cp}+λ_2f_{prox}+λ_3f_{prox}^∂. (3)$
这里的 $f_{cp}$ 描述了内切圆的属性， $f_{prox}$ 描述了网格到参考曲面的贴合度， $f_{prox}^∂$ 描述了网格边界到参考曲面边界的贴合度。根据(2)我们令
$f_{cp} =\sum_{interior\ edges\ v_iv_j }{(l_{ik}+l_{jm}-l_{kj}-l_{im})^2},(4)$
这里的 $v_iv_jv_k$ 和 $v_iv_jv_m$ 表示两三角形相邻于边 $v_iv_j$ ，对于另一个目标函数，我们使用半径 $r_i$ 作为附加变量，并用 $f_{cp}$ 替换得到
$f_{bp} = \sum_{edges\ v_iv_j }{(||v_i-v_j||-r_i-r_j)^2},(5)$
对于(3)中的定义，我们使用符号 $\pi$ 和 $\pi'$ 来分别表示曲面 $Φ$ 和它的边界曲线 $∂Φ$ 上的最近投影点。然后用 $τ_x$ 表示 $Φ$ 上的点 $x$ 的切平面，用 $T_x$ 表示 $∂Φ$ 上的点 $x$ 的切向量。令
$f_{prox}=\sum_{vertices\ vi}{dist(v_i,τ_{\pi(vi)})^2},f_{prox}^∂=\sum_{bdry\ vertices\ vi}{dist(v_i,T_{\pi'(vi)})^2}$

对于给定网格的顶点坐标，其优化（令 $F$ -> $min$ ）是一个非线性最小二乘问题。对于该问题的求解在论文中推荐使用CHOLMOD进行稀疏Cholesky因式分解。求解相关文献请查阅论文《CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate》由于篇幅所限，具体求解细节不再过多阐述。
关于CP Mesh的优化，我已经将该功能在Grasshopper中实现，并集成到插件Ameba中（见图13）。Youtube上也有在houdini上实现该论文优化算法的全过程：https://www.youtube.com/watch?v=d9V2efTXC54

Figure 13：CP Mesh优化在Grasshopper中的实现

CP Mesh优化的应用

通过连接内切圆的中心我们可以很容易得到一个对偶网格（如图8中的红色结构，对偶网格是以六边形为主的网格，其网格边数取决于三角网格顶点价数）。如图14，我们可以将梁沿着对偶网格的边布置，其相交节点处的轴线就是内切圆的轴（因为相邻内切圆的轴位于一个公共平面上，并与这些内切圆的公切线正交），因此这样形成的结构是一个无扭曲结构。

Figure 14：对偶网格的无扭曲支撑结构。图片来源：《Packing circles and spheres on surfaces》

另一方面，CP Mesh也可用于优化网格本身，赋予原始网格和对偶网格以正交性、非交叉性和凸性。这在离散微分几何中十分重要：正交性确保了拉普拉斯算子具有良好的数值质量（后面章节还会再提到）。在使用对偶算法时，我们常将对偶网格的顶点放在原始网格的外心，但是如果我们的三角网格包含钝角三角形时，这样产生的对偶网格可能出现交叉，为了避免这个问题，我们可以采用重心对偶而不是外心对偶，但这又不能满足正交性和凸性。所以简而言之，CP Mesh优化能近乎完美地解决这些问题（图15）。

图16和图17展示了Evolute Tools团队设计的一个景观装置的设计及优化过程。其实这两张图我在几年前就见过了，但是当时一直不懂其中的意义，直到看到了《Packing circles and spheres on surfaces》，才慢慢看懂了他们的作品。

Figure 15：(a) 三角网格。(b1) 三角网格的外心对偶。(b2) 由于三角网格中存在钝角三角形，其外心在三角形外，因此产生了交叉。(c) 基于重心的对偶不会产生交叉，但是它不具备正交性。(d) 将对偶顶点投影到对应三角形的边上。(e) CP Mesh优化。(f) Incircle Packing。(g) 基于CP Mesh优化后的对偶网格。图片来源：https://houdinigubbins.wordpress.com/2017/06/07/cp-meshes/

Figure 16：左上：设计师输入的原始曲面。右上：主曲率分析。左中：粗糙网格划分。右中：网格细分。左下：CP Mesh优化和对偶。右下：CP Mesh与其产生的对偶网格特写。图片来源：《Evolute Tools Primer》

Figure 17：左上：六边形网格。右上：旋转边使他们相互连接（因为每个六边形的每个节点都是无扭曲节点，共轴的特性使它们都各自对应了一个旋转轴）。左中：挤出厚度，深化设计。右中：生成建造细节。下图：建成的KREOP装置（位于伦敦）图片来源：《Evolute Tools Primer》

最后，让我们用这个Circle Packing填充的艺术图案来结束本文，Mesh is Art。

Figure 18：使用Circle Packing创造的艺术图案图片来源：https://www.pinterest.com/pin/413275703299868385/

参考文献

《Packing circles and spheres on surfaces》
《Geometry and Freeform Architecture》
《Architectural Geometry》
《CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate》
《Isogonal moulding surfaces: A family of shapes for high node congruence in free-form structures》
《Evolute Tools Primer》

Mesh is Art（5）：Circle Packing Mesh优化及其应用