68三维模型分割（下）
关键词：三维模型分割
三维网格模型分割应用
三维检索中的网格模型分割算法
随着万维网的发展，在三维VRML1数据库
中寻找一个与给定物体形状相似的模型的应用
需求正变得越来越广泛，比如：计算生物学、
CAD、电子商务等等。形状描述子和基于特征
的表示是实体造型领域中基本的研究问题，它
们使对物体的识别和处理变得容易。因为形状
相似的模型有着相似的分割，所以基于分割的
形状描述子可以用于形状匹配。
2002年毕斯乔夫[37]提出从三维模型分割得
到的椭球集合中得到的某种统计信息（比如椭
球半径的平均方差或者标准方差，以及它们的
比率）。由于这些信息在不同的形状修改中都
保持不变，因此可以作为一种检索特征。但是
这个想法没有得到严格的理论或者实验证明。
2002年，扎克伯吉[65]在一个拥有388个
VRML三维网格模型的数据库上进行检索。首先他们将三维网格模型分割为数目不多的有意
义的分割片。然后评价每一个分割片形状，确
定它们之间的关系。为每个分割片建立属性
图，看作是与原模型关联的索引。当在数据库
中检索与给定网格模型相似的物体时，只是去
比较属性图相似的程度。
该方法检索结果的精确性较差；分割片属
性图比较采用图同构的匹配，计算量较大，且
是一个很困难的问题；从实验结果看，分割效
果显然还不够有意义，出现飞机、灯座等模型
被检索为与猫相似的结果；区分坐、立等姿态
不同的人体模型效果显然也很差（如图19）。
2003年戴伊[9]基于网格模型的拓扑信息，
给出名为“动力学系统”的形状特征描述方
法，并模拟连续形状给出了离散网格模型形状
特征的定义。实验表明，该算法十分有效地分
割二维及三维形状特征。
目前，基于几何以及拓扑信息的中轴线或
骨架等形状描述子也得到了广泛的研究，如基
于水平集[55]、拓扑持续性[69]、Shock图[15]、Reeb
图[54]和中轴线[56]等方法。这些形状描述可以从孙晓鹏中国科学院计算技术研究所
认知心理学、心理物理学认为：人类对形状的识别过程部分地基于分割，复杂形状
往往被看作是若干简单元素的组合。同时，在视觉识别过程中，显著形状特征以很高的
优势屏蔽了其它不显著特征。为了获取形状的显著特征，首先必须进行分割。
1 Virtual Reality Modeling Language，虚拟现实建模语言，一种在WWW中描述虚拟现实（VR）的工具，用来描述三维物体及其行为。其基本目标是建立互联网上的交互式三维多媒体，具有三维性、交互性、动态性、实时性等特征，能够在互联网或局域网上快速传递。该语言于1998年1月被正式批
准为国际标准（ISO/IEC14772-1:1997），是第一个用HTML发布的国际标准。（接上期）
69离散的体数据、以及边界表示数据（网格模
型）中抽取出来。对于后者，目前还没有什么
算法能得到精确、有效的结果[39]。但相信依据
拓扑信息进行分割得到的分布式形状描述子也
是一种值得尝试的三维模型检索思路。
几何压缩传输中的网格模型分割
健壮的网格模型压缩传输方法，必须保证
即使部分形状信息丢失，剩下的部分至少能够
得到一个逼近原始物体的重构，即，逼近的质
量下降梯度，要大大滞后于信息丢失梯度。
无论是层次结构的、或者是过程表示的多
边形网格模型，它们的缺陷是：必须保证严格
的拓扑信息一致性。顶点和面片之间的交叉引
用导致即使在传输中丢失了1%的网格数据，
也将无法从99%的剩余信息里重建网格模型的
任何一部分。对此可以考虑引入高度的冗余信
息，即使传输中丢失一定额度的数据，接收方
依然可以重构模型大部分。
问题的关键是将几何体分割为相互独立的
大块信息，这样接收方可以在不依赖相关索引
信息的情况下，重构流形的邻域关系。
为了避免接收方从点云重构模型的算法变
得复杂，早期的健壮传输方法总假设至少整体
拓扑信息可以无损地传送。一旦知道了粗糙的形状信息，接收方可以插入一些附加点生成逼
近网格模型。
2002年，毕斯乔夫[37,72]的工作把网格模型
分割为若干个椭球，每个椭球独立地、定义自
己的几何信息。由于椭球的互相重叠，冗余信
息由此产生。因此如果只有很少的椭球丢失，
网格模型的拓扑信息和整体形状不会产生大的
变化。冗余信息不会使存储需求增加，因为每
个椭球和三角网格中每个顶点一样，只需要9
个存储纯量。其传送过程如下：首先种子点采
样生成椭球集合；传送优化选择的椭球子集；
接收方抽取等值面重构逼近网格模型；以陆续
到来的原始网格顶点替换临时网格模型的顶点
（如图20）。
1996年，托比（Taubin）[46]首先在三维网
格模型几何压缩处理中应用傅立叶变换：由
任意拓扑结构的网络顶点邻接矩阵及其顶点价
数，得到网格Laplacian矩阵的定义及由其特征
向量构成的空间的正交基底，相对应的特征值
即为频率。三维网格顶点的坐标向量在该空间
的投影即为该网格模型的几何光谱。
2000年，卡尼尔（Karni）和考斯曼
（Gotsman）[47]将几何网格分割片光谱推广到压
缩问题上。光谱直接应用于定义几何网格的拓
扑信息时，会产生伪频率信息。而且对于大规
模的网格，由于在网格顶点数目多于1,000时，
Laplacian矩阵特征向量的计算几乎无法进行。图19 三维网格模型的分割检索
图20 基于椭球分割的三维网格模型压缩传输
70因此该工作在最小割边前提下，首先将网格模
型分割为有限数目的、各片顶点数目接近的分
割片。该方法有微小的压缩损失，且在分割片
边界出现人工算法痕迹。然后利用Tutte投影，
将由于各分割片拓扑不同而各异的网格分割
片基函数，统一为规整的6度网格分割片基函
数，提高了计算效率。由于分割方法的限制，
该算法只适用于没有尖锐边缘特征的光顺网格
模型。2003年艾尔夫斯（Alface）[38]提出了光
谱表示交叠方法：扩张分割片，使分割片之间
产生交叠。该工作（如图21）明显地改进了在
分割片边界上的人工算法痕迹。
高质量的网格压缩传送的前提是良好的网
格分割。
纹理贴图中的网格模型分割
如果网格模型的离散化足够精细，比如细
分网格，那么直接对顶点进行纹理绘制就足够
了。否则就要把网格模型分割为一组与圆盘同
胚的、便于进行参数化的分割片；再对每片非
折叠的分割片参数化；最后分割片在纹理空间
里拼接起来。
面向纹理的分割算法一般要求满足两个条
件：第一，分割片的不连续边界不能出现人工
算法痕迹；第二，分割片与圆盘同胚、而且不
引入太大的变形就可以参数化。但不要求有意
义的分割结果。
2001年，桑达[35]基于半边折叠的渐近网
格算法[70]，使用区域增长法对网格模型进行分割。首先网格模型的每一个面片都被看作是独
立的分割片。然后每个分割片与其邻接分割片
组对、合并。在最小合并计算量优先合并的原
则下，循环执行分割片对的合并操作，并更新
其他待合并分割片的计算量。当计算量超出用
户指定的阈值时，停止合并操作。分割片之间
的边界为逼近角点间直线段的最短路径，从而
减轻了锯齿情况（如图22）。
2002年，利维[39]给出的算法将网格模型分
割为具有自然形状的分割片，但仍然没有得到
有意义的分割结果。为了与圆盘同胚，该文自
动寻找位于网格模型高曲率区域的特征曲线，
避免在平坦区域内产生分割片边界，并增长分
割片使他们在特征曲线上相交，尽量获得尺寸
较大的分割片。
网格模型分割局部性会改善纹理映射、网
格参数化的扭曲效果。
动画与几何变形中的网格模型分割
影视动画制作中，多个对象间的几何变形
特技可以基于网格模型分割的局部区域预处理
来实现。如建立动画区域对应关系，对多个模
型进行“一致”分割，然后在多个模型的对应
分割片之间做变形，将提高动画制作的精度和
真实性；且每个无拓扑信息的面片模型都可用
来建立分割片对应；模型间的“一致”分割有
利于保持模型的总体特征。目前多数的自动对
应算法精度较低。手工交互指定对应关系的效
率又太低。
1996年，克里希纳默西[25]
的工作从高密
图21 基于分割的三维模型光谱压缩图22 面向纹理贴图的三维模型分割
71度、非规整、任意拓扑结构的多边形网格出
发，手工指定分割边界，构造张量积样条曲面
片的动画模型。首先在多边形网格的二维投影
空间交互选择一个顶点序列，然后自动地将顶
点序列关联到网格上最近的顶点上；对于序列
中前后两个顶点，计算在网格曲面上连接它们
的最短路径；对该路径在面片内部进行双三次
B样条曲面拟合、光顺、重新采样，得到分割
片在两个顶点之间的边界曲线。计算量的付出
依然是非常昂贵的。
1999年，格雷戈里等[30]在两个输入的多面
体表面网格上，交互选择多面体顶点，作为一
个对应链的端点。对应链上其他顶点通过计算
曲面上端点对之间最短路径上的顶点来确定，
得到由这些顶点和边构成的多面体表面网格的
连通子图。然后，算法将每一个多面体表面网
格分割为相同数目的分割片，每个分割片都与
圆盘同胚。最后在分割片之间建立映射、重
构、局部加细完成对应关系的建立；最后插值
实现两个多面体之间的变形（如图23）。
2002年，史拉夫曼[45]的工作不再限制输入
网格必须是零亏格、或者是二维流形的。算法
通过迭代，局部优化面片的归属来改进某些全
局函数，因此与图像分割K－均值聚类方法相
近。分割片的最终数目可以由用户预先指定，
从而避免了过度分割，且适用于动画制作的需
求。分割过程的关键在于确认给定的两个面片
是否属于同一个分割片。史拉夫曼提出新的网格模型分割方法和新的柱状分割片投影算法，
降低了工作量、提高了精度。其分割结果是非
层次（如图24）。
基于分割的变形对于保持模型的局部特征
有着重要的意义。局部投影算法能够产生精细
的对应区域，且能自动产生有意义的分割片。
模型简化中的网格模型分割
网格模型简化指把给定的一个有较多面片
的网格模型，处理为另一个保持原始模型形状
特征的、但具有较少面片数目和较大简化/变形
比的新模型。
三维网格模型分割显然可以被看作是一种
网格简化。基本思想是在简化中增加一个预处
理过程，先按模型显著特征将其分割为若干分
割片，然后在每个分割片内应用简化算法，由
此保持了模型的显著特征，如特征边、特征尖
锐以及其他精细的细节。比如把曲率变化剧烈
的区域作为分割边界，将曲率变化平缓的区域图23 动画制作中的交互分割
图24 变形中的聚类分割