内容发布更新时间 : 2024/6/29 13:45:16星期一 下面是文章的全部内容请认真阅读。

龙源期刊网 http://www.qikan.com.cn

基于OpenGL的3D分形树快速显示算法

作者：桂振东 王 琰

来源：《数字技术与应用》2009年第11期

[摘 要]树是虚拟场景中的重要景物之一。提出了一种用参数化的方法,在OpenGL环境下使用显示列表绘制三维分形树,同时生成树的各级LOD模型,使用视锥和四叉树相结合的方法进行可见性裁剪和选择适当的LOD模型层次绘制三维虚拟场景。 [关键词]LOD 显示列表 开放式图形库 分形 IFS

[中图分类号]P458[文献标识码]A[文章编号]1007-9416(2009)11-0100-03 1 引言

树木是自然界中常见的一类植物,由于其具有形状不规则、结构特征强、长势千姿百态的特点,因此对其进行模拟和造型比较困难。在构建虚拟场景时,树木又几乎是不可缺少的景物。树木的三维建模已成为计算机图形学一个重要的应用研究领域,广泛应用于虚拟现实、教学、娱乐、游戏等领域。然而树木包含大量的细节信息,以及光照和可见性影响,使得在绘制中将消耗较多的计算时间,因此提高硬件处理速度成为提高三维显示速度的有效方法。如使用GPU专门负责图形处理[1][2]。但高性能的硬件由于价格高昂而难于广泛应用。

软件方面典型的方法是在满足一定精度要求的前提下减少显示的数据量,如根据不同原则简化网格数据得到多分辨率模型的方法[3]。场景中的物体或者物体的不同部分,在不同的视点相对位置或不同的光照环境等条件下,表现出不同的清晰度,随着清晰度的降低,可以逐步简化原有的网格,即可用较少的多边形表示原物体。另外,应用OpengGL提供的显示列表机制是提高显示速度的有效途径[4]。

本文提出一种参数化分形树LOD模型构造算法,低级LOD模型作为树枝,通过仿射变换与树干组成高级LOD模型,各级LOD模型没有重复的生成过程,提高了分形树的显示速度,且保持了各级LOD模型的相似性。

2 基本原理及算法

龙源期刊网 http://www.qikan.com.cn

2.1 分形树LOD模型的参数化建模

任意一棵树木都是由若干树枝和树叶组成的,每一条树枝又是由若干分枝组成。因此分枝和树叶是树木最基本的组成单位。分形方法是根据植物的形态结构,利用了描述具有自相似性的数学功能来表现植物生长的拓扑及形态结构。文中采用迭代函数系统(Iterated Function System,IFS) 实现分形树的几何建模;适合多种形态的多叉树LOD模型的通用建模。 2.1.1 用参数化方法生成圆台树枝

因为图形设备对三角形的生成是最优化的,所以为了增加三维树模型的立体感和复杂场景中的显示速度,在绘制时树干和分枝都是以OpenGL三角形带生成的近似圆台为基本单位,需要确定圆台高,顶、底半径和分支高度等属性参数如下: (1)树干高度:Hight (2)树干底半径:R_Bottom (3)树干顶半径:R_Top

(4)树枝沿各坐标轴方向衰减系数: (5)树枝数:Num

(6)每个树枝位于树干的位置: Pos[Num]

根据不同结构形态的树,可以对基本参数作必要的调整,以便控制树的形态。 2.1.2 树枝坐标变换公式

树的生长方向为Z轴方向,首先,每个分枝在绘制时都以三维坐标原点为起点,每次绘制都使用沿Z轴平移变换把坐标原点平移到当前分枝点,绘制当前分枝。再绕Z方向旋转夹角度。设父树枝(干) 圆台的坐标为,当前树枝的坐标为,则当前树枝的坐标可由变换矩阵公式(1)得出: (1)

其中是IFS的仿射变换矩阵,分别表示当前树枝相对于父树枝在X ,Y ,Z方向上的缩放比例。是当前树枝绕Y方向旋转角度,当前树枝绕Z方向旋转角度,是当前树枝沿Z轴方向的平移距离。为增加树木的真实感,加入随机函数rand(),使树枝的长度和角度具有一定范围内的随机抖动。调用glTranslated()、glRotated()和glScaled() 函数进行平移、旋转和缩放变换操作,绘制分枝。

2.2 算法描述

龙源期刊网 http://www.qikan.com.cn

用表示树的第i级LOD模型,将顶端有三片树叶的树干作为,、表示树干上第i个分枝绕Y轴和Z轴的旋转角度,则的显示列表定义如下: glNewList(,GL_COMPILE);

glCallList(树干显示列表ID);//绘制树干 glTranslated(0,Hight,0);//绘制点移到树干顶端 for (i=0;i< Num;i++)//循环绘制分枝 {

glRotated(+rand(),0,1,0);//绕Y轴旋转 glTranslated(0,Pos[i],0);//沿Y轴平移 glRotated(+rand(),0,0,1);//沿Z轴旋转 glScaled();//缩放变换 glCallList();//使用绘制树枝 }

glEndList();

绘制一种形态的分形树LOD模型如图1所示。 2.3 可见性裁剪和LOD模型层次的确定

可见性裁剪方法是通过采用视锥体裁剪技术来裁剪掉可视区域之外的场景多边形,以加速场景绘制。此方法的时间复杂度与被裁减的图形实体数目成线性关系:

(为被裁减的图形实体数目)

所以,场景中的图形实体数目的增多,会增加可见性裁剪的计算时间,减低三维场景的显示速度。使用视锥体和四叉树相结合的方法进行可见性裁剪,时间复杂度与场景的分割密度有关而与被裁减图形实体的数目无关,在被裁减图形实体较多的情况下,可以提高三维场景的显示速度,方法如下:首先将四叉树的根节点包含整个场景的XOY平面,然后依次进行递归分割,将分形树