基于渐近网格的三维建筑模型简化方法应用

孔垂柳

(吉林建筑工程学院 计算机科学与工程学院，长春 130118)

基于渐近网格的三维建筑模型简化方法应用

孔垂柳

(吉林建筑工程学院 计算机科学与工程学院，长春 130118)

在城市空间三维表现中，针对复杂自然景观的地形地貌大多采用不规则三角网TIN模型表现。为节约存储空间，在参照JPEG压缩技术中的用户兴趣域编码思想(ROI)结合边收缩算法的基础上，实现用户兴趣域以外的其它区域进行简化，只对用户兴趣域保持较高分辨率。本算法在简化过程中同时生成过程文件，保证了模型连续多分辨率的重建。

三维模型;网格简化;渐进网格;用户兴趣域

在数字城市可视化技术研究中，三维数据建模始终担当着城市物态文化的数字表现技术核心。自然景观中地形地貌的呈现不规则的自由曲面大多采用三角形网格模型表示，为了表现追求质感真实，随之而来的就是构建的模型数据量巨大，给计算机绘制带来了压力。为了解决海量数据与有限的计算能力之间的矛盾，于是需要对三角形网格模型的模型进行简化。

近年来，国内外对网格模型简化方法的研究已取得了阶段性成果，有基于小波分解理论的网格简化方法和基于顶点聚类的网格简化方法［1］;还有Schroeder提出的基于顶点删除的网格简化方法［2］;Hoppe等提出了基于边收缩的网格简化方法因其高效性成为常用的选择。在实际应用中，用户通常可能只对网格的部分区域感兴趣，并希望该区域保有较高的分辨率，而其它区域只要达到基本的视觉要求即可。常见的网格简化算法并未区分对用户兴趣域和非用户兴趣域，而将全体区域是同等对待的，所以网格还有进一步简化的可能和必要。用户兴趣域(ROI，region of interest)编码技术已经成熟的引用在图像和视频编码领域。三维模型简化领域中，引入ROI编码思想，作为三维模型进一步简化新方法应用，保证用户兴趣域的高分辨率，能在满足用户可视化要求的前提下更有效地节约存储空间。

1 边收缩算法与渐进网格

1.1 边收缩算法

在图形学中，三角形网格为表示大量立体形状和自由曲面的常用方法.所谓三角形网格就是一组三角形构建片面的集合，大小不同的三角形共同构成了一个物体的表面，模型的分辨率越高则采用的三角形数量就越多。

边收缩算法一种基于迭代点对收缩的网格简化方法［3］.迭代点对收缩方法的原理是:每次迭代地从网格中选定一对顶点，然后将二者合并成为一个新的顶点，当要求选定的顶点是一条边的2个端点时，就称为“边收缩”。

如图1所示，网格中删除的边为e1=＜v1，v2＞，则它的2个顶点v1，v2被合并为新顶点V0，与这条边相邻的2个三角形也同时被删除，如果e1在边界上，则对应只删除1个三角形。随着边收缩操作的进行，网格模型中三角形逐渐减少，网格分辨率也就随之降低。一般通过设定边的权值来选择删除。

图1 边收缩算法原理

边收缩算法主要步骤为:

(1)依照预定规则为每条边的边赋权值W(e);

(2)选择权最小的边(Vi，Vj)进行边收缩操作，删除边(Vi，Vj)及其相邻三角形;

(3)更新待删除边的集合;

(4)如果满足结束条件则退出，否则转(1)，继续下一次边收缩操作。

边收缩算法的结束条件一般为可设定为以下两种情况:①边收缩引入的误差达到一定阈值δ;②被删除的顶点数满足一定要求(数目γ或比例β);结束条件中的各个参数需要依据先验知识设定。

1.2 渐进网格

在边收缩算法的基础上，Hoppe提出了渐进网格(Progressive Mesh)的构造方法［4］。所谓的渐进网格PM由1个粗糙的简化网格Mr和1个顶点信息记录列表组成的，列表内容即{Mr，Vsplit0，Vsplit1，Vsplitn－1}。这个列表数据依次记录删除的点及次序，也就是原始网格M简化成Mr的渐进过程。渐进网格算法包括网格简化和网格重构互逆过程组成。

首先，网格的简化是通过边收缩操作实现的.每次边收缩运算，使原始网格M中的1条边及其相邻三角形被删除，网格的分辨率也降低，最后得到了简化后的较粗糙网格Mr和一系列细节信息记录。而网格的恢复是边收缩操作的逆操作—点分裂操作完成的，点分裂的次序也是根据{Vsplit0，Vsplit1，….Vsplitn－1}细节信息记录，重新向网格中插入顶点和三角形，最后恢复出具有原始分辨率的网格。

2 ROI编码思想

ROI(Region of Intersting)编码技术是JPEG2000标准提出的一种新技术［5］，其基本思想是:对用户兴趣域进行低压缩比甚至是无损压缩编码以求获得高质量的重建图像，而对其它区域采用较高压缩率以求节省存储空间。在图像编码中，ROI编码技术通过对用户兴趣域产生ROI掩模，将原始图像划分为用户兴趣域和非用户兴趣域。

用户兴趣域建立ROI掩模移植入三维网格中，将三维模型的顶点集和边集划分为用户兴趣域顶点集、边集和非用户兴趣域顶点集、边集，从而实现非兴趣域的三维模型简化。

3 模型的简化过程实施

在边收缩算法的基础上，根据用户兴趣点，将三维网格划分为用户兴趣域和非用户兴趣域.在简化过程中，尽量避免用户兴趣域的边收缩，从而对用户兴趣域保持较高的分辨率.

算法步骤如下:

(1)对原始网格M进行预处理，建立顶点集合Vertexes(M)，三角形集合Triangles(M)和边集合Edges(M);

(2)根据用户输入兴趣点Vf，为三维网格M建立用户兴趣域。

设MV(Vertex)，ME(Edge)分别表示网格M的顶点集掩模和边集掩模，V f为用户输入兴趣点，V和E分别表示M的任意顶点和任意边，且V≠V f，E_index1和E_index2分别为边E的两个顶点，判断V是否为用户兴趣域，我们则采用向量间距离是否小于给定的约束。

我们为了减少计算量，将定义V与Vf间的标准化距离为mahatton距离:

顶点集掩模和边集掩模作为三维网格顶点集和边集用户兴趣域的映射用1和0表示，只要有一个顶点在兴趣域中，我们就认定此边E属于用户兴趣域，不在化简范围内，于是原始网格被划分为用户兴趣域和非用户兴趣域。

(3)对网格的每条边e分配边权V(e)

对三角网格的用户兴趣域和非用户兴趣域采用不同的边权定义方案.对非用户兴趣域，采用最短边策略定义边权，用边长作为权值［6］。为了突出用户兴趣域中边的重要性，定义用户兴趣域中边的权值为所有的非用户兴趣域边长的最大值与自身的边长之和。

(4)从边集合中选取具有最小边权的边做边收缩;

(5)重复执行步骤(4)，直至达到用户要求时结束，我们在实验中设置了被删除的顶点数与原总顶点的比例β小于预定值为结束要求。

4 结语

随着我国城市化工业化进程发展，城市景观围绕城市人文主题呈现个性化衍变。复杂的不规则建筑几何体的三维表现依旧是数字城市的基础性研究工作。本文利用渐近网格的思想实现了一种将建筑实体分区域化简作为降低数据量和追求真实感的一种折衷方案，较好的完成了吉林市东南部城乡区域全景三维模拟展示。

［1］卢威，曾定浩，潘金贵.支持外观属性保持的三维网格模型简化［J］.软件学报，2009(3):243－245.

［2］宋正阳，胡玉清，谢传节.关于多属性三维网络压缩与传输问题的研究［J］.计算机技术与发展，2009(2):196－198.

［3］薛冰，王莉莉，沈哲.基于网格分割的带纹理模型细节保持化简方法［J］.计算机辅助设计与图形学学报，2010(12):55－58.

［4］万定生，倪海涛.基于代价函数三角网格模型动态简化算法研究［J］.计算机工程与应用，2009(7):209－210.

［5］官倩宁，田卉，覃团发.基于ROI多特征和相关反馈的图像检索算法［J］.计算机科学，2008(5):261－263.

［6］朱英浩，张剑清，张祖勋.基于摄像机及线划图的网上三维场景［J］.计算机仿真，2007(11):236－239.

责任编辑:吴旭云

Application of simplification of three-dimensional architecture model based on asymptotic grid

KONG Chui-liu
(1.College of Computer Science and Technology，Jilin Institute of Architecture and Civil Engineering，Changchun 130118，China)

While displaying city space in the three-dimensional way，it is common to present natural landscapes by using the triangulated irregular network(TIN)model.In order to save storage space，the problem is solved on the basis of border contraction algorithm combining with the conception of domain of user interest(ROI)in JPEG compression technique.We simplify the reign beyond the interest of users to maintain a high resolution.A document is generated while the algorithm is simplified，which ensures the reconstruction of the continuous multi-resolution model.

three-dimensional model;mesh simplification;asymptotic grid;domain of user interest

TP391

A

1009－3907(2011)06－0029－03

2011-03-30

吉林建筑工程学院青年科技发展基金项目(J20091053)

孔垂柳(1972-)，女，吉林长春人，副教授，硕士，主要从事软计算方面的研究。