基于拓扑与几何分析的3D骨架提取.doc

基于拓扑与几何分析的3D骨架提取 一.课题背景 随着计算机图形学的迅速发展，对三维模型的研究日益深入。骨架作为形状表示的一种有效形式在三维模型的各个研究领域中被广泛采用。Blum 1967年给出了骨架的最初定义：骨架(中轴)是模型内部各个最大内切球中心的集合。它还有一个grassfire的模拟定义，从模型表面开始点火，各个方向上的火的相遇点所构成的集合。因为模型的骨架很好的保留了模型的拓扑连接性及其形态，所以经常被用于碰撞检测、三维动画、模型渲染、模型表面重建、模型检索等应用中，也有研究人员采用骨架为模型的分解做矫正。不同的应用，对于骨架应该保存的信息要求不完全相同，故而抽取思路也不完全相同。 对三维模型骨架的研究由来已久，出现过很多方法，有的是源于对二维图像的扩展，有的是针对三维模型提出的，大体上来说，有如下几类：(1)基于拓扑细化技术。该类算法主要应用于采用体表示的模型上，通过不断地进行不改变模型拓扑特性的体元素的削减来实现骨架抽取，因为模型的体表示数据量巨大，所以整个过程比较耗时。Gong等人提出过一种并行细化算法，通过先定义模型的简单顶点、删除谓词和两个细化元操作，在抽取算法中不断迭代两个元操作进行模型细化；(2)基于距离矩阵。它一般的计算对象要求也必须是体表示的模型，通过计算每个体元素的距离来求取模型的脊点。Sundar等人提出过基于该思想的一个算法思路，通过计算每个体元素到边界的最小距离来得到骨架点，Sundar采用该算法创建了一个模型检索系统；(3)亦有学者将二维图像领域中的Voronoi图技术引入到三维骨架抽取中，Dey等人提出过一种利用Voronoi图直接近似中轴的算法。因为对三维模型而言只有部分Voronoi顶点能够汇聚成骨架，所以他通过定义角度和比例这两个与大小、比重都无关的筛选标准来实现它的中轴近似算法，并证明该方法能够保证收敛；(4)基于Reeb图思想。该类算法首先在模型上定义一个连续函数，计算每个模型顶点的函数值，将具有相同函数值的顶点聚合成一个顶点，得到模型的骨架，其中著名的有Hilaga等人提出的MRG，Hilaga定义的连续函数为顶点到整个模型表面所有顶点的最短距离与面积之积的和。Julien Tierny等人使用了更加合理的标量函数计算方法。(5)基于模型分解。Lien[9]等人观察到对于保存模型连接性的分解过程就是一个骨架抽取的过程，所以提出了基于模型近似凸面体分解的骨架抽取算法，通过计算模型表面的桥识别模型表面的凹地，计算每个顶点的凹陷性，并对模型按照凹陷性进行分解，不断迭代该过程创建骨架。(6)其它类。Ma等人提出过基于可见互斥力的骨架抽取算法，它应用了物理学上的互斥力的概念来计算模型上的平衡点，最终得到模型的骨架。 二.赛题要求 从现有成熟的3D骨架提取方法中选择或使用自己创新的方法实现多边形网格表示的3D骨架提取。 三.实验要求 （1）开发环境不限，如可采用VC++/OpenGL或VC++/DirectX，也可采用其他如VB、Delphi等开发环境。 （2）三维数据模型要求选用目前国际上比较典型的、适合展示骨架提取效果的实体，如著名的huge_bunny、cow等进行演示，文件类型最好采用目前应用比较广泛的格式，如STL、3ds、wrl、ply等，评比测试时至少要随软件提交2个以上的模型文件。 （3）软件主窗口应能自适应的显示出用户选择的模型文件，具有平滑的光照效果，并能够通过鼠标进行常规的模型浏览操作，如旋转、缩放和平移等；能提供不同的图元浏览模式，如点模式、线框模式及面片模式。 示意图如下（线框显示模式）： （4）利用现有或自创方法抽取模型骨架并显示到窗口，最好能在不阻塞用户界面操作的条件下动态显示算法的执行过程。利用必要的技术突出显示骨架形态，比如以透明方式显示模型表面等。 （5）能力较强的小组在完成上述功能的前提下，若时间与精力允许，可实现一种基于此方法的应用，如基于骨架的动画或基于拓扑分析方法的模型分解、表面变形等。 （6）须提交一份软件设计说明书、一份软件使用说明书、软件源代码和软件安装文件。设计说明书和使用说明书的格式与内容自定。设计说明书中应详细论述所采取的方法与具体算法流程、关键技术、创新性等；使用说明书中需要包含软件安装说明。如果程序中包含较详尽的联机帮助，使用说明书可以适当简化。说明书中应注明，系统中所有引用的文字（尤其是算法部分）、图片及所用到的三维模型文件等的出处、制作者和版权所有者等需特别注明。 四.评比（测试）方式 （1）首先看程序是否能正常运行，即运行中出现的错误不能使程序退出、陷入死循环或造成死机。如果出现上述情况，可以重新运行，但总尝试次数不能超过三次。 （2）在正常运行的基础上，以创新性与最终提取的骨架效果为主要评价指标，在效果相近的情况下，自