（计算机科学与技术专业论文）三维网格的二次曲面提取技术研究.pdf

国防科学技术大学研究生院工学硕士学位论文 摘要 在计算机软硬件技术不断进步的同时，图形学领域的三维扫描和三维建模技 术也取得了长足进展。在反求工程、影视动画及电脑游戏等要求高细节三维模型 的领域，数字化的三维图形开始大量涌现，并得到广泛使用。用于计算机处理的 模型通常是先用扫描仪扫描实体模型得到散乱的点云集合，然后在此基础上生成 复杂的网格多面体，最后对这些网格多面体进行二次曲面提取，从而在计算机中 重建原实体模型。曲面提取技术极大地影响了重建模型的质量。因此，网格多面 体的二次曲面提取一直是图形学领域里的关键技术，是研究的热点课题。 首先，本文对目前国内外三维网格的二次曲面提取的背景知识、进展及其在 各个方面的应用情况进行了综述。介绍了各个典型算法的思想，说明其实现方法 和性能。 其次，本文提出了一种基于层次聚类的二次曲面的提取算法。该算法在把模 型曲面分解成具有指定特征小区域的基础上，将一给定形状逐级聚类为相连的区 域，这些区域可用归属于给定集的基本二次曲面来逼近。与区域增长自下向上的 局部贪婪策略不同，本文的层次聚类提取算法采用全局贪婪策略。算法的核心也 不在于基元聚类的扩张，而在于选择最优的聚类进行合并操作。 再次，本文提出一种快速的二次曲面体提取算法，使用一组重叠的椭球体来 逼近给定的三维网格模型。从而解决了以下两个问题：计算给定三维网格内部的 优化拟合椭球体；从巨量候选椭球体中选择最重要( 最小重复度) 的子集。 最后，对本文的研究工作进行总结，并指出了未来的研究方向。 主题词：二次曲面提取，三维网格，基元集，层次聚类 第i 页 国防科学技术大学研究生院工学硕士学位论文 a bs t r a c t w i 也t h ec o n t i n u o u sp r o g r e s so ft e c h n o l o g i e si nc o m p u t e rs o f t w a r ea n dh a r d w a r e ， 3 ds c a na n dm o d e l i n gt e c h n o l o g i e si ng r a p h i c sf i e l da l s oh a v em a d eg r e a ta d v a n c e s i n t h ef i e l d sr e q u i r i n gp r e c i s e3 dm o d e l s ，s u c ha sr e v e r s ee n g i n e e r i n g ，i m a g ea n i m a t i o n a n dc o m p u t e rg a m e s ，d i g i t i z e3 dg r a p h sa r ee m e r g i n gi nm u l t i t u d ea n dw i d e l ya p p l i e d f o rt h em o d e ls u b m i t t e dt oc o m p u t e rp r o c e s s i n g ，t h es o l i dm o d e li sf i r s t l ys c a n n e db y s c a n n e rt oo b t a i nm e s s yp o i n tc l o u ds w a r l t l ，b a s e do nw h i c hc o m p l e xm e s hp o l y h e d r o n s a r et h e ng e n e r a t e d f i n a l l y ，e x t r a c t i o no fq u a d r i cs u r f a c e sf r o mt h e s ep o l y h e d r o n si s p e r f o r m e dt or e c o n s t r u c ts o l i dm o d e lc o m p u t e r s u r f a c ee x t r a c t i o nt e c h n o l o g yh a sg r e a t i m p a c to nt h eq u a l i t yo fr e c o n s t r u c t e dm o d e l t h e r e f o r e ，e x t r a c t i o no fq u a d r i cs u r f a c e s f r o mm e s hp o l y h e d r o ni s a l w a y st h ek e yt e c h n o l o g yi ng r a p h i c sa n dh o tr e s e a r c h s u b j e c t f i r s t l y ，t h i st h e s i sr e v i e w e dt h eb a c k g r o u n dk n o w l e d g e ，p r o g r e s sa n da p p l i c a t i o no f r e c o v e r i n gq u a d r i c si n3 dm e s h e s t h ep r i n c i p l e so fe a c ht y p i c a la l g o r i t h m sw e r e i l l u s t r a t e d ，t h er e a l i z a t i o nm e t h o d sa n dp e r f o r m a n c e sw e r ea l s oe x p l a i n e d s e c o n d l y ，t h i st h e s i sd e v e l o p e d aq u a d r i c se x t r a c t i o n a l g o r i t h mb a s e d o n h i e r a r c h i c a lc l u s t e r i n g a f t e rt h em o d e ls u r f a c ew a sd i v i d e di n t os m a l lr e g i o n sw i t h d e s i g n a t e df e a t u r e s ，t h ea l g o r i t h mh i e r a r c h i c a l l y c l u s t e r e dt h e g i v e n s h a p ei n t o c o n n e c t e dr e g i o n s ，w h i c hc a nb ea p p r o x i m a t e db yb a s i cq u a d r i c sa s c r i b i n gt ot h eg i v e n s e t d i f f e r e n tf r o mt h e b o t t o m - u p l o c a lg r e e ds t r a t e g yi nr e g i o ni n c r e a s e ，o u r h i e r a r c h i c a lc l u s t e r i n ge x t r a c t i n ga l g o r i t h me m p l o y e dg l o b a lg r e e ds t r a t e g y i na d d i t i o n ， t h ec o r eo ft h i sa l g o r i t h mw a ss e ti ns e l e c t i n go p t i m a lc l u s t e r sf o rc o m b i n a t i o no p e r a t i o n , i n s t e a do fp r i m i t i v ec l u s t e re x t e n s i o n t h i r d l y ，af a s ta l g o r i t h mf o rt h ee x t r a c t i o no fq u a d r i cs u r f a c e sw a sp r o p o s e dt o a p p r o x i m a t et h eg i v e n3 dm e s hm o d e lb yag r o u po fo v e r l a p p e de l l i p s o i d s t h i s a l g o r i t h mc a l ls o l v et h e s et w op r o b l e m s ：c o m p u t i n gt h eo p t i m i z e df i t t i n ge l l i p s o i d i n s i d et h eg i v e n3 dm e s h ；s e l e c t i n gt h em o s ti m p o r t a n t ( m i n i m u mr e p e t i t i o n ) s u b s e t f r o ms u b s t a n t i v ec a n d i d a t ee l l i p s o i d s f i n a l l y ，t h er e s e a r c hw o r ki nt h i st h e s i sw a ss u m m a r i z e da n dt h ef u t u r er e s e a r c h d i r e c t i o nw a sp r o s p e c t e d k e yw o r d s ：e x t r a c t i o no fq u a d r i c ，s u r f a c e s3 dm e s h ，p r i m i t i v e s ，h i e r a r c h i c a l c l u s t e r 第i i 页 国防科学技术大学研究生院工学硕士学位论文 图目录 图1 1 根据提取结果对网格提取算法的分类4 图1 2 三维几何模型处理流程示意图一6 图2 1 空间曲面片s 及其上的微分参量1 0 图2 2 曲率示意图1o 图2 3 用网格圆弧来逼近曲面的示意图1 2 图2 4 用平均曲率与高斯曲面对平面类型的初步分类1 4 图2 5 通过h 、k 的符号得到的六种基本曲面类型1 5 图3 1 边折叠和半边折叠操作的工作原理2 5 图3 2 网格聚类图( 以直角三角形网格为例) 2 6 图3 3 二次曲面提取的光顺3 0 图3 4 基于层次聚类的基本二次曲面提取算法流程3 1 图3 5 对f a n d i s k 模型进行平面的单一提取3 5 图3 6 对b u n n y 网格模型进行平面的单一提取3 6 图3 7 对h o r s e 模型进行球面的单一提取3 7 图3 8 对a r m a d i l l o 模型进行球面的单一提取3 8 图3 9 对m u g 模型进行圆柱面的单一提取3 9 图3 1 0 对r a p t o r 模型进行圆柱面的单一提取4 0 图3 11 对d i n o s a u r 模型进行平面和球面的混合提取4 1 图3 1 2 对h a n d 模型进行平面和圆柱面的混合提取4 2 图3 1 3 对c a m e l 模型进行球面和圆柱面的混合提取。4 3 图3 1 4 对h a p p y - b u d d a h 模型进行平面、球面与圆柱面的混合提取4 4 图3 1 5 对f e l i n e 模型进行平面、球面与圆柱面的混合提取4 5 图3 1 6 各种曲面提取算法执行效果的比较4 6 图4 1 对b u n n y 模型进行椭球提取及与椭球树提取技术的比较5 4 第1 i l 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目：三缝圆整煎三达些亘量塑越盔盟塞 学位论文作者签名：董4 么苎l 日期： 洳7 年 弓月菇日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：三丝圈整丝三这些亘握亟挞垄叠窒 学位论文作者签名： 豳鲣日期：7 年弓月“日 作者指导撕豁坳一 魄砷年多月加 国防科学技术大学研究生院工学硕士学位论文 第一章绪论 随着计算机体系结构的改进、生产工艺的进步以及人们需求的不断提高，计 算机的计算能力、存储能力、信息交互能力等都有了长足的进步。特别是，随着 近年来三维激光扫描仪的广泛使用和计算机图形学不断取得新的成果以及网络带 宽的拓宽，使得三维数字模型的研究在反求工程、模型识别、医学图像、地质勘 探计算可视化以及影视娱乐、网络游戏等等广泛的领域发挥着越来越重要的作用。 可以说，三维数字几何技术在不久的将来会极大的解放人类的生产力、激发人们 的创新力，推动人类文明向前跨出新的一大步。 在本章中，首先介绍对三维网格进行二次曲面提取的应用需求和研究意义， 点出在离散三角形网格上提取二次曲面的难点，然后概述相关的背景知识，进而 详细的说明国内外的研究现状，接着总结本文的工作及创新点，本章的最后对文 章的结构做一个说明。 1 1 曲面提取的研究意义 对三维网格模型进行有意义的曲面片提取和表面重建是近年来研究的热点， 其思想来源于认知心理学的基本原理。心理学和心理物理学 2 1 相关研究表明，人 类对物体形状的识别很大程度上是基于人脑能自动的对对象进行特征识别。复杂 物体往往被看作是简单的基本元素或部件的组合，其中尖锐边缘、突出部位等局 部显著的形状特征，以较高的优势屏蔽了其他非显著特征，而这种显著特征的获 得，是人脑潜意识提取的结果。三维模型曲面提取，是指在三维模型形状描述问 题中，首先根据三维模型某种几何特征( 如其表面平均曲率、高斯曲率值或者脊 线、槽线等) 对其进行局部划分，然后分别计算划分后的模型子块的形状特征。 在应用需求方面，基于三维网格的二次曲面提取问题，来源于如下几个方面： 反求工程。如何对曲面的物体进行高效制造是现代工业的一个重要课题，而如 何更好的研究和借鉴已有的优秀成果是我们进行创新的必要准备，因此对现有 物体生成几何模型是图形学的一个重要课题这就是反求工程几何方面的 任务。当产品用c a g d ( 计算机辅助几何设计) 系统来设计时，由于在该系统 里物体是由简单几何形状的部分组合的，对产品进行并发的处理和修改将非常 容易。但是实际上，越来越多工业产品的表面被设计成自由形状，这意味着必 须先对实体进行数字化处理来建立反求工程的几何外表，只有建立适当的几何 模型后才能进行相应的后续处理。在反求工程中，对固体模型扫描得到3 d 深 度图的一个非常重要处理步骤是对输入的数据进行聚类，也就是原始数据中的 第1 页 国防科学技术大学研究生院工学硕士学位论文 点组理论上是属于单一的简单表面。 曲面重建和几何增强。从一个混乱的稀疏点集重建表面是许多场合要解决的问 题，比如计算机图形学、计算机可视化、计算化学等等。表面重建时，一般先 线性分割模型，而后用基于三角形等( 即三维网格) 简单的几何面片来重建曲 面。已有的大多数知名的方法是对输入数据进行插值来输出多边型网格。在一 般的应用里，比如低水平的机械制造，只采用简单形状( 平面、球面、圆柱面 等等) 的局部提取就足够了，但是自从大多数计算机图形组织采用线性分割模 型后，从基于三维网格的简单几何面片进行表面提取就显得越来越重要了。研 究表明大多数人造物体是能精确建模或者可以用小的简单面片群进行较好地 逼近。比如n o u r s e 等人【3 j 发现所有机械器件模型中的8 5 能很好的被平面、 锥面、球面和圆柱面来描述；若还容许使用超环面，则这个比率将高达9 5 。 近年来的研究认为从点云里提取一个线性的表面仅仅是更多全局处理的 第一个步骤即数据几何结构的充分还原，这意味点集里潜在的表面是一个 低阶的表面或者更复杂的b 一样条推理。 重叠区域模型的曲面提取。一般情况下，激光按距扫描系统得到的数据为扫描 对象的矩形方格，因此，在3 d 坐标系统里得到的模型具有重叠区域，必须先 定义参数来描述邻近模型中相应的参考点以区别重叠区域，然后在一个普通的 坐标系里用匹配的点来重建曲面【4 j 。如果没有改进的系统能将一些曲面对象 ( 比如圆柱体) 数字化，那么拓扑结构更复杂的物体( 采用已有的方法) 的数 据采集就不能完成。重叠区域图形匹配是计算机辅助几何设计( c a g d ) 和计 算机多视点采集数据点时正确构造有重叠情景模型方面的关键问题。 在普通3 d 坐标系统里放置有重叠区域的图形，传统重建模型的方法是先 定义参数来描述邻近图形中相应的点，然后在一个普通的坐标系里用匹配的点 来重建原始表面 5 】，这里所涉及的操作通常需要估计局部表面几何和复原简单 表面片。 在医学领域里，磁性共振和计算机x 线断层摄影术的发展使得人们拥有 了获取3 d 数据而不用侵入解剖就看透物体内部的能力。如果关注的重点不仅 仅在于可见的数据而想探索和分析数据( 比如血液流过病变的动脉模型) ，就 必须采用适当的方法来精确重现对象的图像。在工业或者内科图像的实际应用 中，采用体提取来解析数字化的对象是一种非常经济和可行的方法。 曲面概略图和代数曲面设计。c a g d 的一个主要工作是平滑曲线和曲面网格， 通常的处理方法是设置关键点曲线，进而推断插入值或者近似形状【6 】。由于三 维模型所包含的数据量相对而言是极其庞大的，因此在模型数据库里进行检索 时要想得到快速的响应就应该抽取合适的曲面概略图。另外在很多的三维动画 第2 页 国防科学技术大学研究生院工学硕士学位论文 和游戏动作的设定时，我们一般只对模型的骨架图进行操作从而得到模型相应 动作的效果。类似地，在工厂二维、三维c a d 设计得到的模型库中，也同样存 在着形状类似的、而不仅仅是文字索引之类的检索需求1 7 j 。 实体识别和匹配。实体识别的任务是确定组给定实体中哪一个出现在给定的 模型中，其关键在于从表征模型的数据库中找到匹配的模型。实体识别的一 个重要方面就是如何更好的定义三维形状描述子。2 0 0 4 年m p e g 7 定义的三 维形状描述子存在两个缺陷：一是只能表达局部集合形状，而忽略了空间整体 信息；二是相似性匹配时只考虑能够精确对应的特征，而不考虑邻近的形状信 剧8 i 。为了克服上述缺陷，三维形状描述子基于人类视觉识别符合显著局部特 征表达的假设，认为三维模型是由若干有体积的、闭合的、凸起及无孔的网格 流形曲面组成；因此首先对三维模型进行局部提取，建立分块的属性关系图， 保留分块模型之间的拓扑关联信息，然后采用图匹配的算、法【9 】衡量模型相似度。 每个三维形状描述子含有体积、方差、凸性等三个节点属性，以及中心、变 换两个边属性，需要5 8 2 b i t s 的存储空间。显然，三维模型识别的效率取决于 模型特征表示的有效性，三维模型局部提取是识别和匹配成功与否的关键所 在。 视频处理。基于局部识别和提取的三维模型技术已经列入m p e g 7 ，这标志着 巨大的产业前景。 综合目前的文献，我们发现对三维模型局部识别和曲面提取的研究还有许多 有待提高的地方。例如对显著特征的识别来说，多数工作存在不能得到有意义的 特征识别、识别结果不便于参数化、算法局限于面向特定的应用、面向具有特定 形状的模型等等缺附1 0 j 。 1 2 曲面提取的定义及分类 实际上，曲面提取可归结为这样一个问题：给定模型m ，其基本元素集合为s ( 点模型为点集合p ，体模型为体元集合v ，多边形网格模型为顶点集合v 、边集 合e 或面集合f ) ，分解为子模型的和= m o ，m i ，m k 1 ) ，它表示将s 分 为k 个( 不相交的) 子部分的组合。从而，模型曲面提取的核心在于如何提取集 合s 的各个子部分。显而易见，提取的策略依赖于特定的应用程序，曲面提取结 果的质量度量指标也无法统一定义。但是，依据s 的划分标准函数j ：2 s r ，各应 用的曲面提取问题可等同于优化问题。即，模型m 及其基本元素集合s ，m 的提 取即是寻找到k 个不重叠的部分s o ，s 1 ，s k - l 拼合成曲面s ，并使得划分标准函 数j = j ( s o ，s l ，s k 1 ) 在一定约束条件c 下取得极小值( 或极大值) 。约束集合c 定义了各子集s i 或子模型m i 所必须满足的限制条件，常见的有基( c a r d i n a l i t y ) 第3 页 国防科学技术大学研究生院工学硕士学位论文 约束、几何( g e o m c h i c ) 约束和拓扑( t o p o l o g i c a l ) 约束。划分函数往往根据模型 的某种属性来定义，常用的属性包括：平面性( p l a n a r i t y ，如l 2 距离范数、l 2 方 向范数、l ”距离范数或l 。方向范数) 、顶点法向夹角或二面角、高阶几何实体基 元( 如球、圆柱、圆锥、二次曲面和可展曲面) 、测地距离、曲率、凸性、骨架、 参数化属性和运动特征等等。从模型的对偶图角度来看，盐面的提取和图拼台是 一致的。也就是说，可按如下规则生成模型m 及其对偶图g 的双射关系：图g 的 节点代表集合s 的元素，根据模型m 中各元素的相邻关系定义图g 的边。实际实 验中，曲面提取时若i z l = k 且i s l = n ，在阶为k “的搜索空间中通过穷举来获得最优提 取结果是不切实际的。这意味着，若想在可行的时间内完成求解，必然诉诸于某 种近似算法( 如区域增长、层次聚类、迭代聚类、频谱分析和隐式方法) ，才可 能求得近似最优解。 根据不同的评价标准，模型局部表面提取的算；土可分为不同的种类。从交互 的角度来看，早期的= 维网格模型局部表面提取算法多为手工或者半自动提取， 近几年出现了自动提取的工作；从处理的对象来看，可将曲面提取算法分为体模 型提取、点模型提取l i 和多边形网格模型提取；根据提取得到的结果外形，模型 提取可分为块式与片式两类( 图l1 ) 。在模型提取的诸多分类中，块式与片式的 提取模式最能说明算法的研究目标，影响范围最广。 t 块式提取；b 片式提取 圈1l 根据提取结果对网格提取算法的分类 片式提取遵循模型( 通常为网格) 的平面性、尺寸或凸面等几何属性，将模型 分解为多个面片的组合。片式提取出现较早，已应用于参数化、几何形变、重 嘲格化、表面重建、网格简化和几何压缩等领域。特别是，在参数化与纹理映 射、几何图像等应用中，所生成的面片必须与圆盘同胚，且其( 2 d ) 参数化 要满足保真特性( 如保面积性、保角性和等距性) 。 块式提取又可称为有意义的局部提取或外形提取( s h a p ee x u a c t i o n ) 它将模 第4 页 国防科学技术大学研究生院工学硕士学位论文 型看作有意义的子部分的组合，子模型具有和其所在应用相关的组织结构和外 形。块式提取往往与人的视觉感知原理( 人类对物体形状进行识别时，部分地 基于显著特征的获得，复杂物体往往被看作简单的基本元素或组件的组合【1 2 】) 相一致，故引起了研究人员的进一步关注，其应用领域包括模型匹配与检索、 几何变形与动画等领域。 一般来说，我们公认以下三维网格模型表面提取的定义是适当的。设s 是具有n 个顶点的三维多边形网格模型。s o ，s l ，s k - 1 ，为s 的一个局部提取( 每个s i 称为s 的一个子块) ，当且仅当： v i ，1 f 七，sc s ； v f ，s j 是连通的； v f ，j ，f j ，1 f ，j k ，s 和s ，没有公共的面片，即它们的交集只能是顶 点或边。 除少数例外，几乎所有的3 d 数据提取算法都可以应用于局部区域图形。做很 小的调整，部分也能扩展到一般三维网格或全部区域图形。本节综述有三维网格 模型二次曲面提取相关知识的文献。首先介绍曲面片提取策略的不同可能性，再 用几类特殊的点和三角网格上的线来验证原始面片的提取。随之讲述一些著名的 提取二次曲面类型的方法，关注简单的自然二次曲面( 平面、球面、圆柱面) 。 最后验证通常的提取策略。 1 3 二次曲面提取需解决的问题 计算机3 d 图形学涉及很宽广的数学知识，并且必须将来自多个领域的知识和 方法综合在一起才能解决现有的问题。这些领域包括：几何学、线性代数、数值 分析、抽象代数、计算方法、数据结构和算法。计算机图形学所做的工作在很大 程度上就是把数学表达式转换成计算机能识别和处理的程序代码，数学表达式越 清晰简洁，对应的代码就越容易理解并且可以减少程序出错的可能性。但是由于 面对对象的复杂性和人们追求重建模型的精确性之间的矛盾，不可避免的导致图 形学里数学表达式越来越复杂。 一般情况下，采用形状测量设备获得的三维模型数据可分为两种形式：散乱 数据和结构数据。散乱数据仅包含点在空间的位置信息，通常称为“点云”，由三坐 标测量仪等得到，重构时没有任何附加信息可以利用，是一种最通用的数据形式； 结构数据除了含有点在空间的位置信息以外还含有其它附加信息，数据点之间在 重构时有邻接关系等拓扑信息可以利用。从点集重构曲面网格的任务是找到物体 的一种描述，这种描述不仅要包含曲面上的点，而且还要包含点与点之间连接关 第5 页 国防科学技术大学研究生院工学硕士学位论文 系之类的拓扑信息。在选择重构算法时需要考虑以下几个问题：1 ) 数据形式：2 ) 网格是逼近数据点，还是插值于数据点；3 ) 网格的拓扑要求( 要求封闭或可以带边) ； 4 ) 算法是基于体的方法，还是基于面的方法。 在离散三角形网格上进行二次曲面提取是本文的要解决的问题。利用计算机 来重建实物的三维模型时，经典的做法是采用贝塞尔曲面或者是n u r b s 曲面来逼 近点云所应表达的曲面，这就存在精确度的问题，研究表明对于自然物体表面要 使用贝塞尔曲面或者是n u r b $ 曲面来精确重建是不合适的，这是因为当数据采集 于任意外形实体时，由于决定性区域可能太小了或者有太多的裂缝，基于二次曲 面的分割就得不到可接受的结果，这个问题的解决依赖于我们进行更多的研究。 另一方面，在该领域里已发表的许多算法间样存在许多的局限性，不能很好的解 决现有的问题，这主要是因为问题的复杂性必须用到跨学科的知识才能较好的解 决，这也将是图形学领域今后研究的重点。 1 4 本文工作及主要创新点 二三维数字建模的过程通常是这样的：对一个给定的三维模型进行激光扫描得 到点云数据集，然后利用点云数据的几何特性得到三维网格模型。本文在嘲格模 型上进行曲面片类型的识别，接着用给定简单形状的二次曲面基元集来逼近表面 区域，进而探索用简单的几何体来描述模型实体( 图12 ) 。 黟j 蔑 。零。罐 。渤。匕 4 原b u n n y 模型；b 由a 进行激光押描得到的点云图；c 在b 的基础上处理得到的三维罔 格图：d 对网格模型进行曲面提取得到的效果图：e 用椭球体代替局部区域来逼近原模型。 图1 2 三维几何模型处理流程示意图 第6 页 国防科学技术大学研究生院工学硕士学位论文 本文的主要工作是提出了一种基于层次聚类的二次曲面的提取算法。与区域 增长自下向上的局部贪婪策略不同，本文的层次聚类提取算法采用全局贪婪策略。 该算法在把模型曲面分解成具有指定特征小区域的基础上，将一给定形状逐级聚 类为相连的区域，这些区域可用归属于给定集的基本二次曲面来逼近。算法的核 心也不在于基元聚类的扩张，而在于选择最优的聚类进行合并操作。我们用十一 个不同的三维网格模型对算法的稳定性和有效性进行了验证。 其次，本文提出一种快速的二次曲面体提取算法，使用一组重叠的椭球体来 逼近给定的三维网格模型。从而解决了以下两个问题：计算给定三维网格内部的 优化拟合椭球体；从巨量候选椭球体中选择最重要( 最小重复度) 的子集。 本文的主要贡献如下： 1 提出了二次曲面提取具体流程，在把模型曲面分解成具有指定特征小区域的 基础上，将一给定形状逐级聚类为相连的区域，这些区域可用归属于给定集 的基元集( p r i m i t i v e s ) 来逼近。所采用的基元类型属于二次曲面，在具体的 算法运行中，我们应用了平面、球面、圆柱面这三类基元。 2 研究了一个新的层次提取算法。与区域增长自下向上的局部贪婪策略不同， 本文的层次提取算法采用全局贪婪策略。算法的核心也不在于基元簇的扩张， 而在于选择最优的簇进行合并操作，这意味着层次提取的解空间树为一棵自 下向上构造出的二叉树。 3 提出一种简单可靠的二次曲面体提取技术：使用一组重叠的椭球体来逼近给 定的三维网格模型。这种几何表示意味着可以从非常小量的信息近似重构3 d 形状。这种方法解决了两个重要问题：计算给定三维网格内部的优化拟合椭 球体；从巨量候选椭球体中选择最重要( 最小重复度) 的子集。 1 5 论文结构 本篇论文共分五章。 第一章介绍课题背景，对曲面提取的定义与提取的分类做了介绍， 上说明本文的研究内容和意义，初步分析了曲面提取需要解决的问题， 文的主要工作，最后介绍论文的结构安排。 第二章具体分析了当前二次曲面提取技术的数学原理与研究现状， 阐述了当前有重要影响的提取算法的思路。 在此基础 概述了论 在回顾并 第三章详细阐述了一种基于层次聚类的二次曲面提取算法，介绍了该算法所 具有的优点，并且分析了算法所取得的实验结果。 第四章在第三章的基础上，进一步对三维网格模型进行研究，初步将在网格 曲面上的层次聚类思想应用到三维体模型上来。 第7 页 国防科学技术大学研究生院工学硕士学何论文 第五章对本文的工作进行总结， 最后是对关心与帮助我的老师、 并展望将来本领域的工作。 同学致谢。 第8 页 国防科学技术大学研究生院工学硕士学位论文 第二章二次曲面提取技术 目前，从有着正确二次曲面分界线实体的离散数据中提取二次曲面是计算机 图形学当前的研究热点之一。曲面提取是指根据一定的几何、拓扑或语义特征， 在封闭的三维几何模型上逐步提取一组数目有限、各自具有简单形状意义的、且 各自连通的子部分后，再将各个子部分依据原模型的严格拓扑关系有机拼合。这 是一个复杂的领域，因为既难于用公式表达又很难找到合适的求解方法。本章阐 明二次曲面提取的背景知识，总结各个典型算法的思想，说明其实现方法和性能， 二次曲面提取的基本概念、对既有工作进行总结，并提出未来的研究方向。 2 1 曲面提取的数学依据 从已有的研究来分析，微分几何是描述某一特殊点附近局部曲面性质最合适 的工具，因此微分几何在计算机视觉和对象识别里作为一个描述曲面的工具广泛 使用。由于微分对象的切线、法线、曲率和变形等等仅仅派生于一阶和二阶微分， 所以曲面上点的局部几何性质与二次曲面的性质非常吻合。在三维网格里使用微 分工具来进行局部估计，最有用的方法是使用网格连通性来代替纯拓扑属性。 2 1 1 曲面的微分几何定义 对于给定的曲面点集，一般先估算每个点的几何性质。假定s 为三维空间中 的曲面，p 为s 上的任一顶点，含p 点的三角型区域叫1 环近邻，1 环近邻点p ，的 集合用n 。p ，来表示，s 在点p 的单位法线定义为n ( 图2 1 ) 。关于s 的第一和第 二个基本原理公式为： l ( u ，v ，咖，d v ) = d x d x = d u7 。9 幽， ( 2 1 ) 1 1 ( u ，1 ，如，d v ) = 一d x d n = d u7 d d u ， ( 2 2 ) 在这里如= ( a u ，a v ) r ，汐= 巨主乏斟。= ( ：乏菝 公式( 2 1 ) 处理的是曲面上少数移动的点，把不变的参数曲面进行平移和旋转， 这不依赖于3 d 空间内的曲面s ，因此是曲面的固有特性。公式( 2 2 ) 计算参数空间 里单位法线的变化，这依赖于曲面s ，是曲面的外在特性。 设定t 是s 在点p 的切向量，即t n = 0 ，定义外形算子f l ( t ) = 一v ，n ，( v ，刀) 为n 在方向t 的方向导数。形状算子是线性的算子r 。一r 。，r 。是s 在p 处的空间切 线。s 在p 处沿t 方向的法曲率定义为t 和n 的交积： 第9 页 国防科学技术大学研究生院工学硕士学位论文 图2 1 空问曲面片s 及其上的微分参量 啪，= 等等 眩， p 处主曲率k i 和k 2 分别为t 的最大和最小值s 在p 处的主方向定义为单位 方向。j 和e 2 合成的方向。k l 和k 2 为形状算子的特征值，e 1 和e 2 是相应的特征向量。 平均曲率h 定义为法曲率的平均值，进一步利用欧拉公式，可咀简化为： h = ( e + r 2 ) 2 ( 24 ) 高斯曲率k 定义为两个主曲率的乘积： k = r l r2 ( 25 ) 同时，k 也是s 和h 的半微量( h a l f - f f a c e ) 。平均曲率h 和高斯曲率k 在对 曲面进行初步分类时很非常有用。( 图2 2 ) 。 “主曲率置。“学1 k ( r ) ；b 主曲率也2 “l i i l k o ) ；c 平均曲率日= 寺( 毛+ 岛) ：d 高斯 口率k = k ：。 图2 2 曲率示意圈 s 上平滑点p 的一般定义为：z = h ( x ，y ) ，z 轴由p 处的法线n 来定向。二 次曲面定义为调零方程： = = ( 品x2 + 2 h ：y x y4 - y 2 )( 2 6 ) 第1 0 页 ! k x 一 蔓k = n ， 国防科学技术大学研究生院工学硕士学位论文 在p 处s 近于二阶叫做主二次曲面或者密切二次曲面。由于k l 和k 2 是s 的特 征值，主二次曲面在主坐标系里可以这样来定义： 1 z = ( k 1x2 +k 2yz ) ( 2 7 ) 么 因此，主二次曲面就包含了曲面s 在p 处的所有几何信息。 2 1 2 局部曲面的几何估计 有了上面的基本定义后，我们再设定t 为用边界导向及三维网格化的曲面， 使得邻近网格有着指向相同侧面的法线。对于一个给定的二次曲面点集，大多数 的外形提取方法首先估计每一点的局部曲面的几何性质。因此，我们所要研究的 分段线性曲面在顶点p 的局部曲面几何估计等于计算p 处的扩张的d a r b o u x 框架 1 1 3 】，也就是计算： a 口= ( p ，q ，e 2 ，n ，k l ，k 2 ) ( 2 8 ) 计算d a r b o u x 框架的先决条件是最大限度的进行聚类以及鲁棒的外形重建算 法。外形重建算法所使用的主要元素均为微分几何参数，曲面重新参数化的关键 因素包括基于几何的聚类、网格简化和曲面降噪等等。由于数据天然的离散性， 重建分段光滑曲面的多面体模型是非常困难的。另外，像主曲率和主方向以及二 阶偏导数这些微分量，在计算和量化误差里很敏感，因此实际中局部估计的基本 计算必须改良成全局策略来处理。 为了鲁棒估计t 的局部表面几何性，计算每一个顶点p 处的主二次曲面是一 个好的开始。曲面提取里常用的两种估计策略是顶点法线估计和主二次曲面的拟 合估计： 顶点法线估计。计算曲面上顶点p 处的法线一般采用p 近邻法线的平均值。但 是也可以采用角度加权平均值，并且令w ie ( 谚是顶点p 处第i 级面片的角度) ， 但是当所有点在一个平滑曲面时将比不加权均值得到更差的估计。如果三角面 片是镶嵌式铺装于球体的，给定p 处的精确法线【1 4 】，可以这样推导权值： sin0 w f = 百百t - _ 上 ( 2 9 ) | | ppfii ippf + 1i 主二次曲面的拟合估计。为了鲁棒估计t 的局部曲面几何性，可以先计算每一 个顶点p 处的主二次曲面。这通常分解为两个子问题：估计曲面法线和估计主 方向。这采用旋转主二次曲面来完成，文献【1 5 i 介绍如何用局部曲面拟合来直接 估计主二次曲面，大致方法是把世界坐标系里数据点进行旋转，然后求解旋转 矩阵，得到的特征值和特征向量分别对应主曲率和主方向。但是，上述d a r b o u x 第1 1 页 国防科学技术大学研究生院工学硕士学位论文 框架的估计方法的精确性非常依赖于曲面法线的估计。如果p 处的曲面法线这 样估计： ( 一d ，一e ，1 ) 7 1 1 - i - d 2 + p 2 ( 2 1 0 ) 匹配得到了新的曲面拟合。重复上面的步骤，直到法线的方向递增量降到某一 容许的值。 文献 1 6 】介绍用圆弧来考虑局部逼近的方法。假设取样密集到可以忽略邻近点 之间的曲面曲率。珥、0 为邻近顶点只，的法线估计，认为圆西通过只和弓并且 在这些点与曲面相切( 也就是毛上只处的与乞处的乃是正交的) 。弓为毛的中 心，吒为两个项点的距离( 图2 3 ) 。因此，估算瓯的曲率c 驴值，如果勺 o 为凹 的区域，如果c ：l 0 ，则该曲面片上的点为 椭圆形；k 0 为双曲线：k = 0 并且h 0 时为抛物线：k = h = 0 时为平面( 图2 4 ， 图2 5 ) 。当然，日一k 图并不能适用于所有的二次曲面，例如，椭圆圆柱面和椭 圆锥面的k = 0 、h 0 为椭球面：bk 0 为双曲面：ck = 0 为可展曲面( 含平面、抛物面 图2 4 用平均衄率与高斯曲面对平面类型的初步分类 第1 4 页 国防科学技术大学研究生院工学硕士学位论文 2 2 2 高斯球 图2 5 通过h 、k 的符号得到的六种基本曲面类型 高斯球一般用来识别曲面类型，其中心思想就是一个理想圆柱面的法线向量 与其轴垂直。在高斯球面上，法线向量确定了一个大圆圈，为了检测圆柱面是否 较好地描述了所考虑的区域，顶点法线需投影到高斯球面，并且投影点的拟合是 一个平面。如果拟合得好，平面的法线就是圆柱面的轴。将数据点投影到与该轴 正交的平面上，并且这个圆圈的拟合给出了圆柱面的半径( 如果该区域确实是圆 柱形的，那么就将上述操作再重复一次) 。上述方法也可以用在圆锥面上，理想 圆锥面的法线向量确定高斯球面上的一个小圈，再将投影点拟合到一个平面，这 些投影点给出了圆锥轴的方向。小圈的半径等于s i n a ，a 是半直角。将数据点投影 到与轴向正交的平面上，就可以找到圆锥的标尺和顶点。最后，用最小二乘拟合 检测圆锥面。 v h r a d ye ta 1 【2 4 】根据点在高斯球面投影的密度来标记每个点，以点p 在高斯球 面上的投影为球心取两个同心球，计算各球内的点的数目，并估算点p 所在的曲 面的维数d ：d 踟，p 属于平面区域；d = i ，p 位于圆柱面或圆锥面；d - - 2 ，点p 在 球面片上。首先保留d o 那些点，然后识别这些点对应的平面子区域( 每一组点 对应一个子区域) ，再将这些点删除。接下来考虑d = i 的点。平移轴( 大圈) 可 用h o u g h 转换识别，相关圆柱面参数的计算如前。用类似的方法识别圆锥面。删 除平面、圆柱面和圆锥面上的点后，剩下的子区域属于可旋转的类型，球面片可 以被提取出来。最后的技巧是允许识别由几个可旋转的曲面平滑连接的子区域。 第1 5 页 国防科学技术大学研究生院工学硕士学位论文 2 2 3u e 分割器 d e u n i v e r s i t yo fe d i n b u r g h 分割器最初是为比较和评估距离图像分割器性能 而建立的【2 3 】。在8 0 个反映地面实况和客观性能测量的真实图像上测试了四种平面 分割算法，结论是u e 分割器是现有算法中性能最好的。虽然该研究只限于平面分 割器，但u e 算法实际上提取了二次曲面片。由于该算法在平面和其它二次曲面片 中都表现出色，所以在此详细描述该分割策略。 分割完整距离图像的u e 算法有三个主要成分。首先，要确定经历粗略分割的 数据。曲面片就来自粗略分割，从这些曲面片开始，执行区域增长，期间加一个 特殊约束可允许曲面片的边进行调整。最后，从分割结果提取拓扑信息，并将其 转化为b - r e p 。 在该算法的早期版本中，u e 的研究者们采用基于h k 图的初始分割，根据平 均曲率h 的组合符号和g a u s s i a n 曲率k 标记顶点属于某一特定表面类型。依据内、 外两个阈值将每个曲率值分类为负值、零、正值或未知。内阈值决定零的取值范 围，外阈值决定负和正值的范围限度。一旦这种基本分类被确定，那么类似标记 的顶点被归拢形成初始区域。第一个分割图是形态扩张并以一种特殊方式侵蚀来 填充小的未知区域、删除小区域、薄层分离相连的部分并为区域增长阶段提供种 子曲面片。 用基于h k 图的粗糙分割进行实验，发现算法的后续部分比前面的曲率分类 对算法的性能有更重要的影响。因此，在后来的分割器中选择更简单的方法对数 据进行初始分割【2 5 1 。形状分类