摘要: 本文提出一个系统，能够有效地在任意形状的多边形模型表面上合成出各种动物斑纹的效果。这个系统采用“克隆镶嵌”（ Clonal Mosaic, CM ）模型来生成斑纹效果。 CM 模型是为了在任意表面上模拟细胞反应过程而提出的一种模型，它通过控制细胞的分裂、突变和排斥等行为，来生成细胞的空间分布，以模拟各种斑纹效果。这种方法可以生成逼真的动物斑纹，能与真实世界中的动物表皮斑纹相媲美。然而， CM 方法要求计算出细胞间在模型表面上的距离，而且细胞的运动也要限制在模型表面上，这使其计算代价很高。为此，本文的系统提出一种加速方法，将模型表面上各种 3D 几何平面转化到“规范化参考平面”（ Canonical Reference Plane Structure , CPRS ）上，从而将三维计算问题转化为易于处理的二维问题，以加快计算速度。同时，我们提出“局部松弛”的方法，以加快 CM 模拟中的松弛计算。大量实验验证了本文方法的效率。 1 克隆镶嵌模型 CM 模型用来在任意三维模型表面上模拟哺乳动物的表皮斑纹。这种方法可以模拟出点状斑纹、玫瑰形斑纹和带状斑纹等多种在哺乳动物表皮上常见的斑纹，这些斑纹效果是通过表皮细胞在空间上的不同分布而形成的。 一个 CM 细胞表示为给定区域内的一个点。在本文系统中，我们引入了多种类型的细胞，每种类型的细胞负责整个纹理图案中某一种颜色的合成效果。细胞的属性包括其颜色、分裂率、突变率和互斥值。分裂率控制细胞自分裂的频率，突变率控制细胞突变成另一种细胞的概率，互斥值用来定义任意两种类型细胞间互斥力的大小。 系统中的所有细胞都会根据它们的分裂率一分为二。如果不发生突变的话，子细胞会继承母细胞的所有属性。当分裂发生时，新产生的子细胞之间会互相排斥，这时就要进行相应的排斥计算以决定细胞的位置。这种排斥计算并定位细胞的过程称为“松弛过程”。 2 规范化参考平面结构 当已知细胞间的排斥力后， CM 模拟的效率主要取决于排斥计算的速度。其相关的处理比较复杂，因为细胞间的最短路径及其距离都需要在模型表面上进行计算。在对某目标细胞进行排斥计算时，其邻接面片上的细胞都要变换到该目标细胞所在的平面上。此时，基于一条边或一个顶点共享的任意两个相邻面片之间的变换矩阵可预计算，而基于多个相邻面片关联的两个邻近面片之间的变换，就由这些相邻面片之间的变换矩阵串联而成。邻近细胞间的距离就是它们在这个共同平面上的欧氏距离。 为提高效率，一种优化的处理方法是将面片的旋转信息保存为一个四元组，并当需要进行面片旋转时将这个四元组转化为变换矩阵。这样，在存储四个浮点数后，旋转计算时，只需要 12 次加法和 12 次乘法将四元组转为矩阵，并对一个顶点只进行 6 次加法和 9 次乘法。 为进一步提高速度，我们提出了一种称为“规范化参考平面”（ Canonical Reference Planes Structure , CRPS ）的数据结构。此数据结构中，模型的所有面片都被转换到一个共同的平面上，细胞间的变换和距离度量都在这个共同平面上进行。这样，就将三维计算问题简化成了便于操作的二维问题了。具体实现时，模型的所有面片都被转化到一张平行于 XZ 平面的共同平面上。由于去掉了 Y 坐标，所有面片都位于二维空间中。这些面片会互相重叠，其法向都指向 Y 轴方向。于是，细胞都位于这些二维空间中的面片上。在 CRPS 结构中，我们导出了邻域映射函数，以在排斥计算时正确地映射邻近面片。在邻域映射后，细胞间的距离就可以用它们在二维空间中的距离来度量。 以上操作，需要存储四个浮点数，但是细胞的转换计算从原来的 6 次加法和 9 次乘法简化到了 4 次加法和 4 次乘法。 3 局部松弛 CM 模拟的计算量主要来自于细胞间的排斥计算。传统的松弛算法会在每一步对模型表面上的所有细胞进行松弛计算（称为全局松弛）。这样会造成计算的冗余，因为那些细胞空间分布已经稳定的区域是不必进行松弛计算的。通常某区域内细胞分布的稳定状态只有当一个新的细胞加入时才会被打破，如果仅仅在这些稳定状态被打破的局部区域内才进行细胞松弛的计算，就可以有效地减少计算量。这种方法称为“局部松弛法”。 局部松弛法仅仅用来松弛由于细胞分裂而被打破的小块区域。在给定时间帧内所有被细胞分裂所打破的区域都被排列在一个表里，以逐个地处理。具体实现时，上述所说的区域就是某给定细胞的排斥半径内的所有邻接面片所组成的区域。每当一个细胞分裂发生时，我们可以查找出与新细胞所处面片邻接的所有面片，并将这些面片加入到一个松弛列表里（如果它们还没有被加入的话）。那些已经被松弛过的、并且已经形成稳定的细胞分布的面片，将从松弛列表里删除。全局松弛法和局部松弛法的模拟结果几乎一样，但局部松弛法的速度更快。