摘要: 目前，在计算机图形变形等应用中，为了包含能表现足够逼真度的细节，所使用的模型经常是高精度的。然而，直接控制这些高精度模型，需要累赘的操作，而且计算花销大。很多研究借助和原模型相似，但更简单的结构来控制原模型。许多变形研究使用了这种结构去进行变形控制。该结构包住整个原模型，且拥有更少的顶点，对二维物体是二维多边形，对三维模型是三维三角网格，通常称作“Cage ”，在此译作“控制笼”（注1）。在变形中使用控制笼的主要优点在于控制的简便性和计算的快速性。因此虽然控制笼有时有点复杂，但是许多变形方法还是选择使用它。一些变形转移方法也是基于控制笼的。
控制笼如此有用，但用户交互地构造控制笼却是很乏味和耗时的。更严重的是，当模型的拓扑结构复杂时，交互方法就难于构造一个反映模型形体的控制笼了。尽管用户对控制笼的需求和兴趣不断增长，但是至今自动构造控制笼的研究还并不多。具我们所能收集的资料显示，只有了两种自动构造控制笼的方法。于是，我们开展控制笼构造的研究。
根据最近的变形研究，我们总结出控制笼应有以下属性：
（1）包住原模型；
（2）没有自相交。
而且可以说，顶点数越少，和原模型越相似，那么控制笼越好。
因为控制笼是和原模型相似的简单结构，所以控制笼可以看作是从原模型简化而来。但是为了构造控制笼的简化方法，不像目标只是和原模型相似的传统简化方法，它需要考虑上面提到的控制笼属性。传统简化方法不能直接用于构造控制笼。
为了包住一个模型，可以借助那些计算模型外壳的包络方法。因此，结合简化方法和包络方法，是一种获得满足控制笼第一个属性的结构的方法。
为了去除简化结果的自相交，需要找出控制笼的面（在二维中是边，在三维中是三角形）可处的区域来设置新的面。Delaunay分割经常用来基于一些散乱点把点所在区域分割成多个子区域（在二维中是三角形，在三维中是四面体）。Delaunay分割可成为寻找控制笼新的面可处区域的方法。
本文介绍了一种构造控制笼的方法，可以为二维多边形（二维单连通模型的轮廓）和三维三角网格构造拥有上述两个属性的控制笼。该方法包括两个步骤：简化步骤和去除控制笼自相交步骤（Cage Self-Intersection Removal，简称CSIR）。
简化步骤从输入模型开始不断地进行迭代简化来得到包住输入模型的粗糙控制笼。在简化过程中，使用二次规划（Quadratic Programming）来产生每一个新顶点，并使用二次误差度量（Quadric Error Metric，简称QEM）来为迭代简化排次序。另外，还设计两个分别基于顶点曲率和面法向量的张量函数来调整简化次序，保持输入模型和粗糙控制笼的相似性。
CSIR步骤用于在粗糙控制笼存在自相交时去除自相交。在使用其它比如Marching Square的方法找出自相交区域后，CSIR步骤基于Delaunay分割来处理相交区域。先基于自相交区域的顶点进行Delaunay分割，获得该区域的子区域，然后挑选出在输入模型外面的子区域来设置控制笼的新面，从而得到无自相交的控制笼。
我们在Windows XP系统上基于Graphite的平台使用C++和Matlab实现了构造控制笼的方法，其中采用CGAL库来实现二次规划。文中介绍了多个构造实例。使用本文方法，用户还可以根据应用需求，像QEM简化方法一样，轻易控制控制笼的顶点个数。如果用户只是选定原模型的局部来构造控制笼，将可得到相应的局部控制笼。就像我们前面提到的，控制笼广泛用于变形。本文给出一些使用控制笼（二维和三维）变形的例子来显示我们的控制笼的有效性。
为了比较我们和另外两种方法，我们借助了Metro工具。Metro工具是一个熟知的公开图形工具，用于比较原模型和控制笼的相似度。对三种方法所构造的控制笼比较结果显示，使用相同的顶点数，我们的控制笼的Symmetric Hausdorff距离（用Metro算得）总是小于另外两种的，同时，该距离的最大值和平均值也比它们的小。这就表明，我们的方法构造的控制笼比它们的更好。变形结果也显示了使用我们的控制笼比另外两种方法的更加直观。
本文的主要贡献有如下三点：
1）迭代地简化输入模型，以此可以构造确定顶点数的粗糙控制笼。
2）设计了两个分别基于顶点曲率和面法向量的张量函数来保持形体相似。
3）提供了一个基于Delaunay分割的去除粗糙控制笼自相交的方法。