混合数据模型在建筑物三维建模中的应用

王育坚，许承福，刘立平

(北京联合大学信息学院，北京 100101)

建筑物是城市中的主要地物，建筑物三维建模是计算机图形学、地理信息系统、摄影测量学及其相关学科研究的热点，并在虚拟现实、复杂场景设计、计算机视觉和三维GIS等领域得到了广泛应用［1-2］。建筑物三维建模方法直接影响到城市三维可视化的速度和效果，如何快捷、逼真地构建建筑物三维模型是很多研究人员重点研究的课题。笔者在分析了多种三维空间数据模型的基础上，针对建筑物的结构特点，提出了一种基于八叉树和NURBS的混合三维数据模型。

1 三维空间数据模型

空间数据模型是在实体概念的基础上发展起来的。近年来，国内外很多学者对三维空间数据模型理论和应用进行了深入的研究，提出了多种三维空间数据模型建模方法［3-4］。按照模型的存储元素类型分类，三维空间数据模型可分为栅格数据模型、矢量数据模型、栅格和矢量混合模型3类。按照模型的构成元素分类，三维空间数据模型可分为基于面元的模型、基于体元的模型和面元体元混合模型3类。

基于面元的模型是利用微小的面元素来描述空间实体的几何形态，通过表面表示形成实体的三维空间轮廓。基于面元的模型包括格网(Grid)、不规则三角形格网(TIN)、线框(Wire Frame)、边界表示(Boundary Representation)、断面(Section)和参数函数表示(Parameter Function)等。其中，基于三角形格网的模型已成为三维空间数据建模的通用方法。

基于体元的模型是以基本体元分割空间实体，将三维空间实体抽象为一系列邻接但不交叉的三维体元的集合，通过对体元的描述实现三维实体的空间表示。基于体元的模型包括四面体格网(TEN)、八叉树(Octree)、结构实体几何法(CSG)、三维栅格(Array)、块段(Block)、六面体(Hexahedral)、多面体(Polyhedral)和棱柱体(Prism)等。

基于面元模型的优点为数据存储量小，建模快捷，实体显示和更新的速度快，不足之处为不能描述实体的内部属性，难以进行实体的三维空间分析和查询。基于体元模型的优点为适于空间操作和分析，不足之处为数据结构复杂，存储空间大，建模速度慢。

面元模型和体元模型有不同的特点和适用对象，而混合模型综合了面元模型和体元模型的优点［5］，实际应用中可以根据实体的不同特性采用不同的混合模型。构造混合模型需要考虑以下3个维:模型的构成元素维，包括面元、体元和混合3种;存储类型维，包括栅格、矢量和混合3种;构成元素的形状维，包括规则、不规则和混合3种。研究者根据不同需要将这些维组合起来构造了多种混合模型［6-7］，有同一维上的混合模型，如TIN-CSG面和体混合模型、Octree-TEN矢量和栅格混合模型、混合面片的规则和不规则体素混合模型;还有不同维之间的混合模型，如TIN-Octree面和栅格的混合模型。

2 三维混合数据模型

2.1 八叉树结构

八叉树结构是一种规则的数据结构，通过用树结构对模型进行递归，按X、Y、Z 3个不同方向，将所要表示的三维空间实体V分割为8个大小相等的子立方体。然后根据每个子立方体中所含的目标来决定是否对子立方体继续进行8等分的划分。一直划分到每个子立方体被一个目标所充满，或没有目标，或其大小已成为预先定义的不可再分的体素为止。如图1所示，八叉树每个节点有8个子节点或者没有子节点。图1(c)中，小圆圈表示该立方体未被某个目标填满，需要继续划分。灰度小矩形表示该立方体被某个目标填满，空白小矩形表示该立方体中没有目标，这两种情况都不需继续划分。八叉树每个维度每划分一次，其分辨率都将增大到原来的两倍。

图1 八叉树结构

八叉树体素分解是将空间三维物体逐级分解，最终形成八叉树体素表示的结构。八叉树的主要优点为可以方便地实现物体的并、交、差等集合运算，适用于较规则实体的建模，但对于不规则实体的建模则不太适用［8］。

2.2 NURBS参数函数表示

参数函数表示的指导思想是利用有限的空间数据，构造一个函数的解析式，用这个解析式来生成新的空间点，用以逼近原有物体。参数函数表示包括解析函数模型和非解析函数模型。解析函数模型的优点为数学运算简便、数据存储量小，但复杂的空间对象很难用统一的函数参数方程来表达。为了克服解析函数的局限性，人们提出了非解析函数。B样条函数是比较实用的参数函数，具有存储量小、分析运算速度快、空间几何不变性等特点，是构建三维空间实体边界曲面的有效方法。

非均匀有理B样条(non-uniform rational B-splinc，NURBS)函数是在B样条函数基础上发展起来的，已被广泛应用于工程设计中。计算机图像处理技术的发展，推动了NURBS技术在三维建模领域中的应用［9］。

如图 2所示，一条 NURBS曲线 s(u)=(x(u)，y(u)，z(u))可通过式(1)表示:

图2 NURBS拟合曲线

式中:Pi=(xi，yi，zi)(i=0，1，…，n)为控制点;wi(i=0，1，…，n)为权因子;k为阶数;0，1，…，n)为B样条基函数，其递推定义如下:

u 向节点矢量为{u0，u1，…，un+k|ui≤ui+1，i=0，1，…，n+k-1|}。

si(u)(i=0，1，…，n)为由控制点分段拟合的曲线段，u∈［ui，ui+1］，i=k-1，k，…，n。

如图3所示，设一个 NURBS曲面给定了(n+1) ×(m+1)的网格控制点 Pij(0≤i＜n，0≤j＜m)，则该NURBS曲面可定义为:

式中:wij(0≤i＜n，0≤j＜m)为相应于控制点Pij的权因子;k、l为阶数;(0≤i≤n)和(0≤j≤m)分别是定义在u、v向节点向量:U={u0，u1，…，un+k|ui≤ ui+1，i=0，1，…，n+k-1}V={v0，v1，…，vm+l|vj≤ vj+1，i=0，1，…，m+l-1}

k、l阶 B样条基函数递推定义同式(2);Sij(u，v)表示拟合的曲面段，u∈［ui，ui+1］，i=k-1，k，…，n;v∈［vj，vj+1］，j=l-1，l，…，m。

图3 NURBS拟合曲面

2.3 建筑物三维混合数据模型

建筑物在几何和拓扑上有较大差异，传统的八叉树模型表示不规则的实体不够精确，很难用于各种类型建筑物的建模。针对城市建筑物种类繁多、结构复杂、信息量大的特点，笔者采用八叉树与NURBS曲面相结合的混合数据模型。

在混合数据模型中，利用八叉树对建筑物实体进行三维空间分割，利用NURBS拟合建筑物不规则的表面。当分割后的建筑物子体位于实体边界且外形不是规则立方体时，采用NURBS曲面描述该体元的表面，如图4所示。将实体转换为八叉树结构时，在边界灰度节点中加入子体的面、边、顶点信息，从而形成扩展的八叉树结构［10］。

空间分割首先采用八叉树空间分解法生成曲面离散点集，选取一个立方体包围盒圈定空间曲面，将包围盒作为八叉树的根节点来初始化八叉树数据结构。然后将该包围盒分解成8个子区域，作为大立方体的8个子节点，生成子体曲面上的空间离散点集。空间分割时注意采集实体不规则部分的外围散点，将不规则体元剖分成参数函数曲面，生成子体的NURBS曲面。

图4 八叉树-NURBS混合结构

混合结构用一个特殊的属性值实现八叉树与NURBS曲面的链接，若八叉树某节点编码的属性值为N，表示该节点关联一个局部的NURBS曲面。通过节点与对应的8个子节点体内的特征点相结合，形成局部NURBS曲面。实现时采用网格细化和求交切割的方法［11］，用不规则体元填充八叉树与表面模型之间的空隙，完成模型的自适应分割。

曲面模型的数学表示是一个带符号的代数距离函数，为了简化曲面建模，也可以采用一个均匀的双三次B样条函数［12］。假设在二维平面上有n个点(xi，yi)(i=1，2，…，n)，并有 hi=F(xi，yi)，这样在三维空间中可以构成一个点的集合P={(xi，yi，zi)}。构造一个均匀的双三次B样条曲面来逼近集合P，该双三次曲面片由覆盖在子节点的控制点网格φ来定义。设φij是网格φ中序号为ij的控制点的值，则由这些控制点定义的双三次B样条函数为:

式中:Bk、Bl为均匀双三次B样条基函数。

控制点阵列 φkl(k，l=0，1，2，3)决定了点(xc，yc)的函数值 f(xc，yc)，即有:

式中:s=xc-1;t=yc-1。

有许多组的值可以满足式(4)，根据最小二乘法原理，用伪逆矩阵可以求出一组解为:

2.4 建筑物数据结构

随着城市化进程的加快，城市建筑物的结构和形状不断发生变化。数据结构是三维建模的基础，必须设计出合理的数据结构，以便高效地存储建筑物的属性和几何数据。根据八叉树-NURBS混合三维数据模型，采用面向对象的程序设计语言C++为建筑物设计相应的数据结构，其形式化表示如下:

在存储结构上，采用扩展节点(面、边、顶点)和混合式的八叉树结构，在八叉树较高的层次上使用指针式结构建立节点的索引，而在较低的层次上按节点编码的大小排序，建立该局部空间内包含的所有非空叶节点的线性表。这样既减少了存储空间，又提高了显示的精度和搜索效率。

通过八叉树节点编码可以得到其对应的8个子节点，编码方案直接影响节点的存取效率。这里采用八进制前缀编码方案，即对同一父节点的8个兄弟节点，其具有最小(x，y，z)值的节点编号为0，相邻兄弟节点的编号沿x方向增加1，沿y方向增加2，沿z方向增加4，并将父节点的编码作为其8个子节点编码的前缀。为保证八叉树中每一节点编码的长度相同，在编码后增加一串区别于0～7八进制数的特殊字符“T”，使每个节点编码的长度均为树的最大深度H。这样，节点编码可表示为 q1q2…qiTT…T，其中 q1，q2，…，qi∈{0，1，…，7}，0≤i≤H。显然，q1q2…qn表示了空间最低层次(第n层)立方体网格单元，q1q2…qiTT…T表示了空间分割至第i层时的立方体网格。

实体模型的多个子体相互关联，多个子体结合成为模型总体。每个子体由一组节点和一个NURBS曲面重构形成，CreatNURBS()函数用于建立建筑物的NURBS曲面对象。一些八叉树叶节点可能被同一个NURBS曲面对象包含，即一个NURBS曲面对象可能同时与多个八叉树节点相关联。通过对八叉树按层次遍历逐步细分作用区域，在求交层中对区域内的每个节点进行精确的NURBS关联运算。实际应用中，有些建筑物的墙体或屋顶为曲面，需要采集或内插一些特征点，然后按一定的规则对建筑物的子体建立NURBS曲面模型。

3 基于OpenGL的建筑物三维可视化

模型系统以Visual C++6.0为开发平台，采用面向对象的建模方法，利用OpenGL技术实现实体的三维建模和可视化。在建立NURBS曲面模型时，以OpenGL的NURBS接口函数为基础，通过编写程序对节点相关联的NURBS曲面建模。NURBS对实体表面的拟合，主要通过计算控制点实现。先求出控制多边形的顶点，根据已知的数据拟合NURBS曲面，通过插值法最终实现所有子体表面的NURBS曲面构造。该模型系统不仅可以表达规则实体，也可以表达不规则实体，使用该模型系统生成的三维模型如图5所示。

图5 建筑物三维模型

对于简单结构建筑物的建模，混合模型并没有体现出比传统的八叉树模型更优越。但在处理不规则的建筑物时，在相同分辨率要求的前提下，混合模型对三维空间实体的分割次数要远远小于八叉树模型。如对弧面形状的建筑物，前者的分割次数为后者的1/8左右。因此，即使考虑NURBS曲面对象的建模，混合模型的数据存储量比八叉树模型少50%以上，相应的模型显示速度提高了20%，模型的精度也更高。

4 结论

笔者在对城市建筑物三维建模理论和方法进行深入研究的基础上，设计了一个基于八叉树和NURBS的混合数据模型系统。实践证明，该模型具有一定的实用性和可行性，可视化效果较好，具有较精确表示复杂空间实体的特点。由于数据结构的复杂性，该模型在判断何时需要构造NURBS曲面时，条件不够精确，理论和算法还需深入研究。

［1］THIELE A，CADARIO E，SCHULZ K，et a1.Building reconstruction from InSAR data by detail analysis of phase profiles［C］//The International Archives of the Photogrammetry，Remote Sensing and Spatial Information Sciences.Beijing:［s.n.］，2008:191-196.

［2］杨淼.基于图像的城市建筑物三维自动重建参数化建模方法研究［D］.青岛:中国海洋大学图书馆，2009.

［3］王彦兵，吴立新，李小娟.3维GIS空间建模方法评述［J］.中国图象图形学报，2007，12(8):1430-1434.

［4］KATSIANIS M，TSIPIDIS S，KOTSAKIS K，et a1.A 3D digital workflow for archaeological intra-site research using GIS［J］.Journal of Archaeological Science，2008，35(3):655-667.

［5］张传明，潘懋，徐绘宏.基于分块混合八叉树编码的海量体视化研究［J］.计算机工程，2007，33(14):33-78.

［6］吴慧欣，薛惠锋.基于块段模型的三维GIS混合数据结构模型研究［J］.计算机应用研究，2007，24(10):273-275.

［7］荆永滨，王李管，毕林，等.复杂矿体的块段模型建模算法［J］.华中科技大学学报:自然科学版，2010，38(2):97-100.

［8］FREY P J.Generation and adaptation of computational surface meshes from discrete anatomical data［J］.International Journal for Numerical Methods in Engineering，2004，60(2):1049-1074.

［9］HU S M，LI Y F，JU T，et a1.Modifying the shape of NURBS surfaces with geometric constraints［J］.Computer Aided Design，2001，33(12):903-912.

［10］郭锐锋，刘春辉，丁万夫.改进的八叉树模型在3D刀轨显示系统中的应用［J］.小型微型计算机系统，2010，31(2):373-376.

［11］任铭，李振平.基于八叉树与RBF神经网络的曲面三角网格生成［J］.中原工学院学报，2011，22(1):32-34.

［12］李鹏，刘永鸿.一种运用OpenGL快速构建三维模拟地形的方法［J］.计算机仿真，2005，22(12):174-177.