一种基于符号形式文法的三维建模方法

邹青青, 姚保峰,夏 伟,陈 晨

(蚌埠学院计算机工程学院，安徽 蚌埠 233030)

三维场景建模的技术核心是根据研究对象的三维空间信息构造其立体模型，尤其是几何模型，并利用相关建模软件或编程语言生成该模型的图形显示，然后对其进行各种操作和处理[1]。目前，国内外对现实世界的三维虚拟场景构建方法做了很多重要的研究工作，主要方法有：直接利用一组图片作为输入，通过合成新视点全景图像来建立三维模型，以达到在三维场景中虚拟漫游的效果[2]；另一类方法是使用激光扫描设备获取物体表面大量点云数据，采用数学方法对数据去噪、配准，最终完成被扫描对象的精确表面模型[3]；还有一类属传统三维建模方法，即基于几何的建模与绘制通过人机交互手段来辅助三维建模[4]。

上述建模方法各有特点，构建的虚拟场景仿真效果良好，且沉浸度高。实际应用中，当需建模型数量大幅增加时，采用上述方法所需的工作量也显著增加，即在模型批量构建问题上，这些方法的优势不明显。以刻画符号集的形式理论为基础，研究一种类比符号形式文法的三维模型文法，探究在该文法定义下虚拟场景模型的构建方法，并通过实验验证该方法的可行与效用。

1 建模流程

与传统三维建模系统采用的方法不同，基于符号形式文法的过程式建模方法利用文法规则描述模型的产生过程，其三维场景建模流程如图1所示。首先，获取现实世界物体的内外部信息，根据物体的几何特征抽象出物体的组织构造；其次，在物体概念模型的基础上，将形状组织方式转化为若干规则描述，执行规则的模型生成器输出现实物体的初步虚拟模型，随之完成纹理映射；为实现高质量仿真模型，第三个阶段根据需要对模型细化，修改规则，并补充纹理；最后，导出三维模型，实现场景交互功能，提供应用服务。

图1 基于符号形式文法的建模流程

2 模型生成方法

2.1 三维模型生成器的构造

符号形式文法是抽象化的语言通论文法，基于符号形式文法理论研究三维模型的构建方法，是研发三维模型生成器的理论基础。与乔姆斯基语言谱系文法定义相似，定义三维模型的符号形式文法为四元组(Vt，Vn，P，S)，记作：模型文法(Modeling Grammar)，文法四元素说明如下：

(1)Vt：终结符的非空有穷集，亦作基础形状集合，是模型演算的基础。

(2)Vn：非终结符的非空有穷集，由文法定义使用的标记符号组成，表示模型构造过程中的形体概念。

(3)P：形如α→β的产生式集，其中，α∈(Vt∪Vn)+，产生式左部不为空，即α≠ε，β∈(Vt∪Vn)*，定义模型的生成规则。

(4)S：开始符号，表示产生式推演从几何形状S开始，S∈(Vt∪Vn)集。

有别于语言的终结符号，基础形状符号设计为一个形状域结构体Scope，作为三维模型构建的最小单位，该域体属性由四部分组成：标识符、域原点坐标、描述大小的向量以及几何属性(如图2所示)，这些属性描述场景中跟随模型的定向包围域，模型的任何变换在域范围内发生。

struct Scope{ID_Type id;Coordinate O;SizeVector C;Geometry g; };//基础形状标识号//域原点位置信息//大小向量//几何体

图2Vt集元素的形状域与域结构说明

产生式集P的定义是形式文法建模决定因素，集合中的规则决定开始形状的变换过程，操作由几何面组成的形状，通过计算机描述并实现每个产生式规则的含义，迭代计算出最终模型并优化设计内容。在符号形式文法定义的基础上，建模程序变作一种利用新模型替换特定模型的过程，即：从文法的开始形状符号S开始，依据产生式的定义不断衍生新模型替换原有模型，直到生成模型目标。

根据三维模型基本特征，空间约束产生式集合主要包含的规则有：(1)缩放规则，改变模型比例；(2)位移规则，变换模型的形状域原点O坐标；(3)拆分规则，把模型从整体分成不同的组件；(4)拉伸规则，挤出高度，使模型从面变为体；(5)切割规则，将模型分层或分块；(6)补全规则，补全立面空缺部分；(7)替换规则，实现模型替换。模型文法各产生式的推演过程如表1所示。

表1 产生式的推演描述(以Vt={}为例)

文献[5-7]提出了CGA(Computer Generated Architecture)语言，该语言的语法由一组预定义语句以及带参函数构成，其程序脚本用于实现过程式建模。扩展CGA程序脚本描述模型文法产生式，采用C++语言实现三维模型生成器框架，CGA脚本作为生成器的输入，生成器依据脚本规则迭代运算，目标模型则是生成器的输出。以三维建筑模型的生成为例，CGA规则脚本包括：形状块挤压拉伸、分割立面、门窗处理以及生成屋顶坡面，图3展示了模型生成器的中间过程与输出结果。

图3 生成器的建模流程

2.2 纹理映射

纹理映射是将纹理图像的像素映射到屏幕像素空间的过程，其作用在于对景物表面纹理细节的模拟[8-9]。纹理的实现一定程度上简化模型的设计，同时又提高模型的真实感。应用语言集合正则表达式的描述方法构造纹理生成器，先描述模型表面纹理的组织规则，生成器翻译之，并于纹理空间计算纹理坐标，最后映射纹理至模型表面。符号形式文法与正则式形式不相同，但均能用于刻画符号集合，纹理组织表达式采用闭包运算表示模型表面的纹理复用过程，纹理集合的分析处理器采用递归下降法实现，流程如下：

Step 1. 将待填纹理记录成纹理空间的基础元素集合；

Step 2. 计算模型对象待处理面的UVW坐标，计算纹理的UV坐标；

Step 3. 纹理表达式转换成产生式形式，计算产生式各非终结符的开始纹理元素集；

Step 4. 依据开始纹理元素集，构造非终结符的概念函数P()，遇到产生式的递归部分则调用函数自身；

Step 5. 从矢量方向，依据开始纹理元素(若有)进行模型表面映射，遇非终结符号则直接调用非终结符函数P()，由函数递归完成纹理复用。

根据表2的纹理表达式映射纹理，效果如图4所示，待处理面域大小幅值不同，概念函数p()的递归次数不同，随之产生不同的纹理填充次数，如图4(b)和图4(c)所示，体现纹理分析器处理过程的自动化。

表2 纹理组织规则

(a) “c(ab) *c”组织 (b) “ba*b”组织7次递归 (c) “ba*b”组织2次递归图4 纹理映射效果

3 验证实验

3.1 单个物体精细模型

图5(a)显示了带跃层楼房的建模效果。图5(a)中模型由两部分构成：植物和建筑，两者均为模型生成器的输出，生成器的输入根据模型现实特征进行不同规则设计。

1) 植物模型。植物形态各异，造型多变，通过产生式推演生成植物模型的过程是：拆分规则作用于长方体，取前后左右四面经旋转规则与平移规则使之相交于面的平分线，成立体造型，面的透明属性置真值，并为其赋予植物纹理，保持模型域原点坐标Z轴绕垂直视点坐标，如图5(b)所示。采用分形法可以将植物的逼真度达到叶片级[10]，基于模型文法规则生成的植物对三维场景的贡献在于沉浸感，从实验中能观察出植物模型能达到较好仿真效果，相比而言，后者的计算时间更少。

2) 建筑模型。图5(a)中建筑体包含墙体、屋顶及烟囱三部分，使用的规则有拉伸、缩放、旋转及平移，作用于大小不同的几何面生成模型整体结构；拆分规则作用于墙体立面，按域原点坐标Y轴分出层，按域原点坐标X轴分出窗，拆分依据如图5(c)所示，转换成纹理表达式为：Y((X(c(ba)*c)e)*d)；沿Z轴拉伸层间墙沿，为模型的各部件赋予纹理，如图5(d)，调试纹理的UV坐标值，细化规则，修改参数，最终生成目标模型。

(a) 单个模型 (b) 植物模型 (c) 立面拆分 (d) 墙沿与屋顶纹理图5 模型效果与构造细节

3.2 批量模型生成

过原点垂直场景Z轴平面，循环生成相邻多边形，形状域大小向量(Scope.C(Cx，Cy，Cz=0))赋随机数，生成基础形状集合，如图6(a)；依据单个物体模型的建模方法，采用CGA语言编辑风格不同的模型规则脚本文件若干，图6(a)分成22个区域片，每个片区内选定一组规则集，作用于片区内坐标随机选定的形状域，批量生成模型，如图6(b)所示，模块与背景渲染效果如图6(c)所示。由计数结果得出，图6(c)场景中包含6 061个Scope域对象，505 264个形状块。在模型规则脚本设计完成的基础上，模型生成器输出图6中模型只需少量时间成本。

(a) 垂直Z轴面上的形状集 (b) 由五组不同风格的规则脚本生成的模型 (c) 场景渲染效果(视点为图b绕Z轴逆时针旋转90°)图6 三维场景批量建模

程序运行环境一致为前提，基于虚拟现实建模语言VRML(Virtual Reality Modeling Language)的场景构建与基于模型文法产生式的场景构建相比较：①生产效率对比。随着模型数量的增加，前者的消耗成本与模型数量成正比[11]，后者的工作量在于模型生产规则设计，描述规则被确定后，其建模成本受模型数量的影响较低；②优化方式对比。VRML对三维场景具有全局优化作用，模型的逐个优化过程代价较高，CGA脚本控制下的场景，无论规模大小，都由模型文法的产生式演算出，构造规则被优化，则全局被优化，后者方法本质上具有高效性。基于文法产生式的建模方法适用于模型批量生成，其模型生成器效率较高的原因是：模型点线面体的细节构造过程被模板化，目标模型则是模板实例，模板重用有利于模型的批量创建，同时，模板累积有利于模型重构。

3.3 场景交互

虚拟现实场景良好的交互功能促进良好的沉浸感，模型生成器输出的三维场景支持模型控制操作。更改形状域坐标支持模型平移与模型旋转，更改场景坐标与视角支持场景平移与场景旋转。与此同时，支持全视视点与正视视点查看场景，提供场景任意视点值的存储功能，各视点位置间插值实现场景动态漫游。支持位置查询功能：为基础形状块编号，增加名称字段，连同形状域原点位置属性一并录入数据库，根据基础块名称查询模型，并将当前视点切换为查询结果模型的正视视点，实现位置查询。

4 结论

符号形式文法是符号串集句法逻辑与结构规律的抽象表述，拓展符号形式文法的作用域，本文研究了三维模型文法的空间演化规则描述，基于模型文法产生式规则的迭代与复用以及正则表达式的递归分析给出了三维模型生成器的构造方法。

建模方法的可行性。由实验结果得出：在单个模型构造时，基于文法产生式建模能够生成仿真效果较好的细节模型；在多个模型构建时，该方法能够胜任大批量场景模型生成，并具有降低建模时间的意义。应用模型文法产生式创建的三维场景其模型结构与纹理沉浸度较高，在场景形状域数据的支持下，可实现场景控制、场景漫游及位置查询类交互功能。

建模方法的效用。与VRML语言相比较，扩展模型文法的脚本语言更易于完成模型重用与模型重构。在模型形体计算过程中，输入规则脚本后的模型生成器是有效且健壮的：目的性地集成构造模型文法的产生式规则，从而创建复杂程度不一的三维模型，是一种介乎于质量与速度之间的折中解决方法。

加载真实数据的场景视图服务是下一步研究工作。场景中的模型位置数据不具备真实性，将场景搭建于真实的地形、地图数据上，为基础形状域结构扩展空间数据信息，利用形式文法模型生成器批量建模的优势，建立与现实世界信息相符的虚拟场景，在场景视图服务中，由虚拟场景向用户提供真实的、丰富的空间数据资源，提供智能化的三维场景空间信息响应，是下一步研究思路。