典型算法的可视化研究（精选6篇）
典型算法的可视化研究 篇1
0 引 言
三维可视化指利用计算机图形学技术、图像处理技术、虚拟现实技术将抽象数据以具体三维图形方式绘制到屏幕上,使人以更加直观的方式去理解。在虚拟现实场景中,地形需要的数据通常是以TB计算的海量数据。虽然计算机硬件在不断地发展,但是对复杂度近乎无限的室外地形场景而言,处理能力还是显得非常有限。因此在渲染过程中,尽可能地简化模型的复杂度(LOD)已经成为现代VR系统的一个重要的目标。
早期的LOD算法都是工作在静态网格上的,随着处理器能力的不断提高,动态LOD算法有了较大的发展。文献[1]最早提出基于视点的连续LOD算法,使用四叉树来表示地形数据,通过为四叉树节点定义一个误差标准来决定是否需要继续简化。90年代后期,出现了一批GPU友好算法,这些算法的特点是不再刻意地追求多边形数量的消减,更多考虑的是发挥现代显卡一次可以绘制大量多边形的批量绘制能力。如文献[2]提出的Geomipmap Block LOD算法、文献[3]提出的Aggregated LOD算法。
1 Geometry Clipmap算法基本原理
Geometry Clipmap思想来源于一种称之为Texture Clipmap的技术。Texture Clipmap技术是Mip-Texture(多级纹理)技术的改进。传统的Mip-Texture是将源纹理生成的一系列纹理一次性加载到内存当中去。而地形整体纹理一般是覆盖整个地形的一张巨大纹理,在生成一系列分辨率较低的纹理之后没办法一次性装入内存。Clipmap通过巧妙地改变内存中纹理的存储结构及更新方式解决这个问题。Texture Clipmap的内存组织如图1所示。在内存中分配一系列固定大小的内存块,每个内存块存储着纹理的一种分辨率表示,从下到上分辨率递增。Clipmap Pyramid中的内容与传统的Mip-Texture一样,但是Clipmap Stack中就只存储大分辨率纹理的一部分,即当前视点下需要被精确显示的那一部分[4]。
Geometry Clipmap技术将高程图作为一张纹理来保存,在顶点着色器中通过高程纹理获得具体的高程数据[5]。因为显存中存放着不同分辨率的高程纹理数据,所以显示的时候可以依据视点相关的原则,在离视点近的部分用精度最高的高程纹理显示,离得远的部分用精度较低的高程纹理显示,最终形成一个嵌套的显示结构,如图2所示。
2 高程纹理数据生成
2.1 原始数据处理
原始的高程数据来源于自动生成的模拟数据或者航空拍摄的高程图。它们的共同特点是包含海量的高度数据。高度数据本质上来说是一个(x ,y ,h)三元组的组合,其中x,y为当前经纬度坐标,用整数表示,h为当前点的高度数据,单位为米。根据不同的可视化系统需求,x,y可以定义为不同的单位。现实中的x,y都是连续的,但是由于渲染引擎的需要,x,y都需要被离散化。中间的x,y可以通过合适的插值方式获得。
在数据预处理过程中,首先要确定一个最大的可视化范围R,来作为最粗糙的高程数据可以表达的最大范围,其他的层次的高程纹理可以表示的范围依次递减。在Geometry Clipmap算法中,精度高的纹理处于精度低的纹理的中间位置,因此采样点个数N不能取成2的幂次方。而必须取成2的幂次方加1或减1,才能保证下一层的纹理位于本层纹理的中间。此处的N被称为Clipmap Size,即每层高程纹理的采样点个数。
其实需要确定纹理的层数L,即整个渲染过程中地形需要使用几层精度不同的纹理。对于L的确定不仅要考虑最大范围R,还要考虑视点的位置以及最终渲染结果的精度要求。总的原则为L越小,系统的渲染效率越高,但是摄像机离地面的距离就必须越远,否则的话会出现精度丢失的现象,而L越大,摄像机就可以离地面越近,固定大小的显示面积表达的细节就越丰富,但是随之产生的后果就是内存与显存的消耗,以及CPU与GPU消耗的增加。
层次与最大范围决定好以后,就可以从原始的高程纹理中通过重新采样形成一系列大小相等但精度不同的高程纹理层次,其原理如图3所示。
不同精度纹理的生成可以在渲染过程中自动进行,也可以在渲染过程时在纹理更新过程中自动生成。前者会增加一些预处理时间,并多消耗一些显存空间,各层次纹理在内存中存有一份,渲染时只要更新到显存中,就可以使用,纹理更新算法也在内存中实现。通过CoptyToSurface技术更新到显存。而后者内存中只有一份最原始的高程图数据,在渲染过程中自动生成当前所需的全部高程纹理,移动时,只需要在显存中更新各层纹理数据即可,省掉了一些内存与显存的数据传送的操作,但是更新过程中,需要在GPU内进行纹理采样及滤波操作。由于现在显卡硬件的限制,顶点着色器中的高程纹理采样动作对系统资源消耗比较高,可能会对渲染效率有所影响。具体选择哪种方式取决于所使用的硬件特征。
2.2 数据更新算法
高程数据的更新包含在主存中的原始高程数据以及各不同精度层次的高程纹理的更新,更新算法主要在CPU中进行,随着视点的移动,获得截止上次更新为止的移动信息,根据这些信息从原始的高程文件中把要更新的纹理读出来后刷新到内存中的层次纹理数据中,更新为渐近式的,通过将纹理寻址方式设置成循环寻址方式,使用不变的部分保持不变,只更新需要变化的部分,以节省内存与显存之间的数据传输量,更新结束后,通过D3D的RenderToTexture或者CopyToSurface技术,将更新后的数据刷新到显存中以供渲染使用,具体的更新原理如图4所示。
3 地形渲染
3.1 渲染流程图
基于Geometry Clipmap算法的大规模地形模拟系统的渲染流程图如5所示。Geometry Clipmap算法的核心是使用现代显卡中的GPU处理芯片快速地完成高程数据的裁剪与混合。它对运行环境有一定的要求,即显卡必须支持SM3.0(Shader Model 3.0)架构,即可以在顶点着色器中实现顶点纹理数据的读取及操作。
3.2 GPU渲染说明
渲染过程是将从高程纹理中取得高程值,最终显示到屏幕的过程。该渲染流程与传统渲染流程相比的优势在于,除了第一部分的高程纹理的更新过程,大部分的操作都是在GPU中完成。而现代显卡中可以包含128甚至更多个流处理器,计算量极大的运算都由GPU并行完成,因而整个渲染过程中可以保持一个相对来说较高的FPS值以及低的CPU占用率。通过这种方式,可以把宝贵的CPU资源节省下来,用到AI及逻辑控制等方面。
该算法对运行环境有一定的要求,即显卡必须支持SM3.0(Shader Model 3.0)架构,在SM3.0架构下,用户可以直接在顶点着色器中对纹理进行寻址,即在顶点着色器中实现顶点纹理数据的读取及操作,而这也是该算法的一个前提条件。
顶点高程数据由于存储在纹理当中,在顶点着色器中根据当前所处的经纬度坐标快速地索引。正式使用时,该高程数据获得于卫星高程数据,但由于本程序只作演示使用,故高程数据由程序自动生成,使用perlin嗓音算法,生成类似于连续山川地貌的高程值。高程纹理也可以通过RenderToTexture技术由pixelshader自动生成。
调用GPU有两种方法,一种是基于微软的DirectX技术,一种是OpenGL技术。本文中的实验采用DirectX 9.0实现,与GPU交互的接口主要封装在ID3DEffectX接口中,ID3DEffectX的简单用法如下:
3.3 边界消除算法
消除边界的方法就是在边界的两个不同细节带之间引入一片过渡区,过渡区的大小可以预先指定。在过渡区中,节点的高程值并不仅仅是从本层中获得,而是取本层与邻接层高程图中的相同位置的高程值进行插值,插值因子取决于当前位置离地形块中心点的距离。因为逻辑上地形块的中心点位于当前视点处,所以只要判断当前位置与视点的距离即可,通过分别计算X轴方向和Y方向的插值因子,可以得到两个插值因子,最终的插值因子取较大的那个。插值因子a的计算公式如下:
a=max(ax,ay)
其中ax , ay分别为在X,Y轴方向计算的插值因子;x , y为当前位置的坐标值;xv , yv是当前视点的坐标值;n为clipmap size(即每层高程纹理的采样尺寸);w为过渡带的长度。clamp的含义如下,其中l<h:
插值因子a得出后,最终的高程值计算公式如下:
z=(1-a)×zc+a×zn
其中z为最终的高程值,zc为当前层的高程值,zn为相邻精度较低层的高程值,图6显示了每层中需要进行高程混合的区域。
3.4 顶点缓冲与索引缓冲
渲染过程中,所有渲染到的3D模型都需要顶点缓冲区来存储。而顶点缓中区是存放在显存中的,传统的地形渲染算法的一大问题就需要大量的显卡空间来存储当前渲染的场景的地形网格数据。这不仅大大地消耗了有限的显存空间,还给显存与内存中的带宽增加了负担。
分析Geometry Clipmap的渲染流程不难发现,由于高程数据是在顶点着色器中计算完成的,故可以使用固定大小的一块顶点缓冲区来进行渲染,通过多次调用DP函数,在每次调用时设置不同的位置与偏移以及当前的层次信息,即所谓的缩放值。一块顶点缓冲区就可以完成整个地形的渲染动作。这样就把对显存的占有率压缩到最低。
具体的划分方式如图7所示,在渲染过程中,除了中心精度最高的实心距形区域外,其他的环状区域都可以分为小块的渲染单位以及一些退化三角形填充区域。每个小块的区域可用一块固定大小的顶点缓冲区来表示。同一层的不同小块的差别只在于它们的偏移位置不同,而不同层的同一步块的差别则只在于它们的缩放值不同。
故渲染过程中可以只使用一小块缓冲区,在过程中设置不同的参数值,多次调用DP动作,就可以实现完整的地形块的绘制。
对于每个细节层次,需要调用14次DP操作。其中12次是用于绘制主要部分,其他2次是用于填充缺口。在场景漫游时,视锥体以外的部分都可以被裁剪掉,剪裁示意图如图8所示。平均每一层只要调用4次DP操作就可以了,加上中心实心矩形的绘制,平均下来,每一帧需要调用6L+5次DP操作,其中L是当前的精度层次。
在渲染某个层次的地形块时,顶点数量相同,但是其他参数不同的情况下,可以考虑使用几何实例技术来减小DP操作的调用次数。所谓几何实例技术就是当对顶点相同的,但其他属性不同的多个3D模型渲染时,只需要把除顶点数据以外的其他属性打包到一个顶点数组中,然后调用一次DP动作,就可以同时渲染出多个模型。通过这种技术减少了DP的调用次数,提高了渲染效率。如果考虑到使用几何实例技术,地形块的DP次数能够缩减到3L+2次。图9是当使用几何实例技术时,显存中的顶点数据分布图。
4 实验及分析
4.1 效果载图
使用上述的渲染算法开发出来一个可以渲染超大规模地形的地形渲染演示程序。图10与图11分别是该演示程序在正常渲染模式与线框渲染模式下的效果截图。
4.2 结果分析
本文完整地实现了一个基于Geometry Clipmap算法的渲染引擎。运行及开发环境如表1和表2所示。
实验程序的高程数据使用perlin噪音函数生成,可以模拟无限地形,该实验用的地形数据范围为40000×40000,视点高度在1000-2000的高度范围,经过该引擎,平时浏览时绘制的三角面片数大约为20000左右,帧频率在120-140之间。表3为不同位置的FPS与绘制的三角形个数及CPU占用率。
表4对扩展后的Geometry Clipmap算法、原始的Geometry Clipmap算法及传统的基于四叉树的LOD算法的特点进行了比较。从表中数据可以得知,基于Geometry Clipmap的算法充分发挥了GPU的优势,与传统的算法相比,不仅能得到更高的三角形吞吐量,还可以获得更高的FPS。当视点移动时,渲染的三角形数量相对来说比较稳定,而传统的四叉树算法渲染的三角形数量与视点位置有关。
综上所述,基于Geometry Clipmap的算法与传统算法相比,更有效地利用了系统资源。渲染同等数据量的三角形时可以极大地提高渲染效率,并且获得稳定的渲染帧率。
5 结 语
本文完整地阐述了基于Geometry Clipmap技术的大规模地形渲染流程及算法,并在此基础上对此算法进行了补充与扩展,使之成为一个完整的大规模地形可视化的解决方案,增加了地形数据调度模块,对海量数据的内存外存管理给出了完整的解决方案,改进了内存中Clipmap堆栈的数据结构,取消了原始算法中Clipmay pyramid部分,并将渐进纹理更新技术用于原始纹理信息的更新,使之完全变成一种海量数据下的LOD解决方案,将Geometry Instancing技术引入渲染过程,进一步提高了渲染速度。
参考文献
[1] Lindstrom P,Koller D,Ribarsky W,et al.Real-time,continuous level of detail rendering of height fields[C]//ACM SIGGRAPH 1996.USA:ACM,1996:109-118.
[2]Willem H D B.Fast.Terrain Rendering Using Geometrical Mip-map-ping[EB/OL].2001-02-12.[2006-10].http://www.flipcode.com/tutorials/geomipmaps.pdf.
[3] Levenber G J.Fast view-dependent 1evel-of-detai1 rendering using cached geometry[C]//Proceedings of IEEE Visua1ization2OO2,Bo ston,USA:IEEE Press,2002:259-266.
[4] Hoppe.Geometry Clipmap:Terrain Rendering Using Nested Regular Grids[C]//ACM Siggraph,2004.USA:ACM,2004.
[5]Asirvatham A,Hoppe H.Terrain Rendering Using GPU-Based Geome-try Clipmap[M].Addison-Wesley,2005:27-45.
典型算法的可视化研究 篇2
关键词：计算机图形学,算法,模板,交互式,可视化
计算机图形学Computer Graphics简称“CG”,它是计算机技术与电视技术、图形图像处理技术相互融合的结果,使用主流的可视化编程平台VC++2005所开发的图形,与使用Turbo C语言开发的图形相比,不仅可以显示真彩色,而且可以实现交互式绘图,它又突破了传统计算机图形学的教学模式(理论文本加静态图片)的枯燥性、抽像性的限制。基于此,提出了一种模板把CG中各种图形生成的算法以可视化的方法、动态交互式展现出来,实践证明,通过此模板,学生能容易理解图形生成的算法原理过程,激发了学习CG的兴趣,从而极大地提高教学质量。
1 VC++绘制图形常见方法
1.1 使用On Draw成员函数
该方法只需要在源程序Test View.cpp的On Draw成员函数中直接书写绘图语句。操作简单,但无法控制函数的调用,它常用于对屏幕已有图形进行旋转、消隐、光照和纹理映射等操作。
1.2 使用CDC*p DC的菜单调用方式
在MFC框架中的“视图(View)”菜单中,打开“解决方案资源管理器(Solution Explorer)”子菜单,双击Test View.cpp,在该文件最后添加成员函数Drawmy Line()的定义:
在“解决方案资源管理器(Solution Explorer)”中,双击“Test.h”,在该文件中“public:”下面添加成员函数声明:void Drawmy Line();
在菜单中添加菜单函数On MENU Drawmy Line()调用Drawmy Line()成员函数。
该方法需要在头文件Test View.h中声明成员函数Drawmy Line(),在源程序Test View.cpp中定义成员函数Drawmy Line()。在Drawmy Line()函数中使用了CDC类指针对象,需要调用和释放设备上下文。
1.3 使用CClient DC dc(this)的菜单调用方式
成员函数Drawmy Line()的声明和菜单的调用同第二种方法的[2]和[3],在Test View.cpp文件中修改Drawmy Line()成员函数的定义:
该方法也需要在头文件Test View.h中声明成员函数Drawmy Line(),在源程序Test View.cpp中定义成员函数Drawmy Line()。不同点只是使用显示器客户区设备上下文类定义了客户区对象dc,并使用客户区的this指针对dc对象进行初始化,使dc对象指向显示器的客户区,这种方法不需要调用和释放设备上下文。与前述两个方法相比,第三种方法更易理解,实现更简单。
2 基于VC++2005环境开发的一个金刚石图案应用案例
2.1 案例需求
2.1.1 案例描述
将半径为r的圆周n等份,然后用直线将各等分点隔点相连,形成的图形称为“金刚石”图案。
2.1.2 功能说明
1)单击绘图菜单或工具栏图标,弹出对话框(如图3)读入圆的等分点个数和圆的半径,以屏幕客户区中心为圆心绘制金刚石图案。
2)程序运行界面如图4。
2.2 案例分析
该案例设计一个P2D类,用于存放各个点的double型(x,y),最大分点不会超过50个,用P2D类定义了大小为50的P2D类对象数组p[50]。关键在于内层循环设计时不要进行进行重复直线连接,以等分点n=5为例,连接情况如图5和表1所示。
为此,设计一个二重循环,代表队起点的外层循环从i=0循环到i=n-2,代表终点的内层循环从j=i+1循环到i=n-1。以p[i].x,p[i].y作为起点,以p[j].x,p[j].y作为终点绘制连线。
3 详细设计[4]
3.1 点类设计
该实例以Test为项目名称,主要设计了P2D类,并通过视图菜单中的类视图子菜单选中Test项目右键添加一个名为P2D的C++类,并且为了保证运算精度,在P2D中添加double成员变量x,y;
3.2 对话框类设计
在资源视图中右键选择Dialog中的插入Dialog,在对话框内添加静态文本和编辑框控件Edit Control修改属性,设计后的对话框如图6,分别右击对话框中两个编辑框,依次添加类型为double的成员变量m_n(表示等分点个数)、m_r(代表圆的半径)。
3.3 CTest View类视图设计
在类视图中右键选择CTest View,并添加成员变量和成员函数,Test View.h声明如下:
3.4 菜单设计
3.4.1 设置菜单ID
在资源视图中双击Menu中的IDR_MAINFRAME,添加“绘图”菜单及其二级菜单“金刚石图案开始制作”,并通过属性设置其ID为ID_Diamond。
3.4.2 设置菜单函数
在类视图中右键选取CTest View的属性,在事件中为ID_Diamon添加On Diamon事件,并添加如下代码控制绘图操作:
3.4.5 工具图标设置
在资源视图中选取Toolbar下的IDR_MAINFRAME并添加相应的图标,然后选中添加后的图标,在其属性中把其ID改为ID_Diamond(该例以绘图操作为例),以实现图标和子菜单的关联,同样的方法设置其他图标与菜单的关联。至此一个完整的计算机图形算法的模板生成了。
4 结束语
CG算法开发模板紧跟主流开发环境,实现可视化的设计,人性化的界面,通过简单和修改,也适合于Bezier曲线算法、B样条曲线等其他图形,实践证明,通过此模板,学生能容易理解图形生成的算法原理过程,激发了学习CG的兴趣,从而极大地提高教学质量。因此这对计算机图形学的研究和教学意义重大。
参考文献
[1]孙家广,胡事民.计算机图形学基础教程[M].北京:清华大学出版社,2008.
[2]郑海鹰,李爱光,张新慧,等.计算机图形学与数字地图制图[M].郑州:解放军信息工程大学测绘学院,2004.
[3]霍顿,Visual C++2005入门经典[M].李颂华,康会光,译.北京:清华大学出版社,2007.
典型算法的可视化研究 篇3
Web服务器集群是由多台配置与性能各异的Web服务器共同构成的协同工作集群。该集群通过一个统一的外部端口,向Internet网络上的用户提供服务,大量的用户访问请求被分派到各个服务器节点上进行分布式处理。因此,在面对海量用户请求时,精确评价各个节点的实时处理能力并合理分配访问请求,实现系统各节点负载均衡,避免部分节点因用户访问请求量超出其处理能力而造成系统局部过载,就成为当前Web服务器集群领域的研究重点。
1 Web 集群负载均衡技术
在集群系统中,各个服务器作为节点加入集群体系中通过一个统一的对外接口共同为客户端提供网络服务,而负载均衡技术是此类系统得以正常运行的技术保障,负载均衡技术首先对各个节点的性能与运算速度进行有效的评估,将各个节点的性能与运算能力通过数学模型转化为可以进行量化表述的权值,在基于权值评价的前提下,向各个节点合理的分配访问请求。根据各服务器的实际处理能力来分配负载,保证每一个节点服务器都具有良好的响应速度。
2 Web 集群负载均衡的典型算法分析与改进
在集群系统收到来自大量客户端的密集访问的情况下,集群系统会依据负载均衡调度算法向集群中的各个节点均衡分派访问请求将整个系统所面临的访问压力分摊到各个节点服务器上去,在这个分派服务请求的过程并不是简单的基于节点数量的平均分派,而是在基于对各个服务器的运算能力、当前负载以及工作性能进行分析与评估的前提下进行的。最终实现在多个节点上合理分摊负载的操作。
2.1 基于 LVS 的权值分配调度算法
当前服务器集群中使用较广泛的是LVS技术。在LVS架构中,作为集群系统对外接口的负载均衡器收到客户端发来的任务请求时,负载均衡器会根据管理人员配置的负载均衡调度算法在负载均衡器上进行请求任务的调度分配,将用户发来的任务请求数据包转发至系统中的某一台节点服务器进行处理。
2.2 算法分析
LVS中的负载均衡算法中最具有代表性动态权值分配调度算法是加权最小连接调度算法。服务器集群系统存在着许多构机节点,这些节点的配置、性能各不相同,加权最小连接调度算法会评估每台服务器节点的实际处理能力来测算各个节点在负载均衡算法中所需进行参照的权值。下面对此算法的执行做一个简单的介绍:
用{Sn,S1,...,Si,Sn—1,}来表示服务器集群中的各个节点,W(Si)表示集群中的某个节点Si的权值,Si节点当前的任务连接数则用C(Si)来表示。那么整个集群的全部连接数可以表示为:,假设负载均衡器从集群中选择一个节点Sm作为当前准备接收请求任务的服务器。若经过计算,W(Sm)=0,那么该节点就被标记为当前无法使用。若Sm节点当前可以接收并处理转发来的请求任务,那么可依据公式(2.1)来确定其可以作为备选服务器为客户端提供服务。
设Csum为常量,则公式(2.1)的可简化为公式(2.2):
如果某个节点服务器的权值越接近为0,那么表示该服务器越有可能接近过载的状态。因此公式(2.2)可优化为公式(2.3):
2.3 算法的改进
以上算法是基于集群中节点服务器的连接数量来设计的,并未考虑其它的影响因素。在对服务器集群运行的实际案例进行分析后可知,仅仅考虑某一个参数设计的算法无法对服务器节当前的真实负载状况进行准确的描述。针对这个问题,本文在以上算法中加入了新的服务器节点权值分配调度算法用以改进它的性能。为避免新算法本身造成的系统开销过大的现象出现。所以在新的权值分配调度算法中我们仅引入了2个新的与节点服务器相关的运算参数:处理器(CPU)资源利用率、内存资源空闲率。
假设在服务器集群系统Sn,S1,...,Sn—1中有一台节点服务器Si。对于Si节点的CPU利用率,我们以C(Si)来表示,内存空闲率用M(Si)表示,对服务器节点的权值则以W(Si)来表示。当W(Si)=0时,则表示Si当前的状态为不可用。我们在此设计了权值表达函数F(Si),此函数包含的参数为以C(Si)和M(Si),参数以C(Si)和M(Si)的值被限制在区间(0,1)里。函数F(Si)如(2.5)所示:
函数中的参数K1+K2=1。当边界条件值被满足时,可推导出公示(2.6):
当然,K1与K2不可能同时都为0。在真实的系统运行过程中, CPU和内存的占用在同一个时间段内都临近峰值属于小概率事件。进而可以推导出,1-C(Si) (CPU的空闲率)和M(Si)(内存的空闲率)同时为0(即二者都全部未被占用)的情况也极少有可能会出现。所以F(Si)的值为0的可能性也较小。所以,只有当服务器节点故障或停运时,该服务器节点的权值才有可能为0。
2.4 改进算法的实现
在新的算 法公式中 , 我们将Web服务器集 群以S={S0,S1,…,Sn-1}来描述,某一节点服务器Si的权值设为W(Si),本分配周期中的前驱服务器序号用j来表示,当前需要进行处理的权值为cv,集群系统中各节点的最高权值为Max(S),Gcds(S)函数的功能是以集群中的所有节点权值为参数进行运算并求出它们的最大公约数,算法开始时系统的初始权值cvs与服务器序号j的值都设置为0。即节点权值被设置为0时,节点不参与负载均衡。
在向集群中的节点服务器分配负载任务的实现过程中,为保证能够向合理的各个节点分发负载任务,我们在算法中采用了Hash散列函数来实现运算结果的均匀分布。
static inline unsigned hashkey(unsigned intdest_ipaddr)
{int I, j;
for(i=low;i<=up;i++)
{ for(j=0;j<= HASH_H;j++)
{dest_ipaddr *=(dest_ ipaddr * 2654335741) & HASH_TAB_MASK;}}
return (dest_ ipaddr * 2654335741) & HASH_TAB_MASK; }
3 测试与结果分析
在Web服务器系统集群负载均衡的模拟运行过程中,我们使用了Web Capacitys Analysis Tools负载生成工具在各个客户端上模拟了大量的并发用户访问请求,对各个整个集群系统的服务器负载响应情况进行了测试,最终的测试统计结果如下表3.1所示。
由上表可以看出,当请求次数逐渐增加时,平均响应时间变化很大,即本算法负载均衡优势很明显。
4 结语
本文对服务器集群负载均衡系统也做出了深入的剖析,全面的分析动态权值分配算法的原理,并在实验环境下设计并测试了文章中提出的负载均衡的改进算法。实验结果表明,改进后的算法有执行效率高,占用系统资源少的优点,并且能够在Web服务器集群中流畅运行;同时,能够支持集群节点的扩容。在集群中服务器节点数量较多,节点之间性能差异较大的情况下,这种优势更加明显。
参考文献
[1]李明咏.负载动态分组负载均衡算法研究[J].郑州工业学院学报,2012,11(31).
[2]叶坤.基于Qo S的云负载均衡机制的研究[J].小型微型计算机系统,2011,10(17).
典型算法的可视化研究 篇4
所谓“查找”就是在一个含有众多的数据元素(或记录)的查找表中找到某个特定的“数据元素(或记录)”。若表中存在这样的一个记录,则称查找是成功的,可以给出整个记录的信息,或指示该记录在查找表中的位置;若表中不存在关键字等于给定值的记录,则称查找不成功,可以给出查找不成功的相应信息。
1 折半查找算法介绍
在计算机中进行查找的方法随数据结构的不同而不同。折半查找方法适用于查找存储在有序的线性表中的记录,其查找过程为:先确定待查记录所在的范围,然后以该范围内的中间记录的关键字和给定的关键字进行比较,若相等,则查找成功;若给定的关键字小于中间记录的关键字,则舍弃掉线性表的后半部分以缩小范围继续查找;若给定的关键字大于中间记录的关键字,则舍弃掉线性表的前半部分以缩小范围继续查找。循环直到新的区间位置记录的关键字等于给定值或者查找区间的大小小于零时(表明查找不成功)为止。
折半查找算法的描述如下:
2 用C#实现的动态演示程序
打开Visual Studio 2005,新建一个Visual C#Windows应用程序项目,项目名称为Binary Search,将默认窗体名称Form1改为Binary Search Form,在窗体上添加一个Panel控件,作为动态演示折半查找过程的平台,添加两个Timer控件,设置其Interval属性为1000,用来代替算法中的循环和查找比较过程,用Timer控件的定时特点来达到动态演示的效果。程序中的主要代码如下,为了有助于读者更好的理解,在其中添加了比较详细的注释:
3 程序运行界面效果
程序运行的界面效果如图1所示,从图中可以清楚地看到已经被舍弃掉的部分和还没查找完的部分,初始的数据以红色背景色和黄色前景色显示,查找范围的第一个和最后一个数据以黄色背景色和红色前景色标出,查找范围中的中间元素以蓝色背景色和白色前景色标出,舍弃掉的部分以系统背景色和黑色前景色显示。程序通过视觉变换和延时形成了动态演示查找过程的效果。如果运行时感到效果不理想,可以将数组容量设置的大一些,同时可以适当调整两个定时器的时间间隔,以控制查找的速度,从而可以更好的体会折半查找的过程。
4 结束语
算法一般是比较抽象的,我们在学习算法时,大多是通过老师根据一个具体的例子用粉笔在黑板上对算法的实现过程进行讲解,或通过教材上的描述进行自学,掌握起来非常不容易。在具体编程时一般只会看到算法实现的结果,而看不到算法的实现过程,缺乏直观性和生动性,学生难以接受。本文用C#编程对折半查找算法的实现过程进行了可视化的动态演示,有助于读者更好地掌握这一算法的基本思想,同时也希望能起到抛砖引玉的作用,大家共同开发一些算法的可视化演示程序,让初学者能够从中受益。
参考文献
[1]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,1997.
[2]王晓东.计算机算法设计与分析[M].北京:电子工业出版社,2006.
[3]李继武.Visual C#.NET项目开发实战[M].北京:清华大学出版社,2007.
典型算法的可视化研究 篇5
1 三维可视化算法教学的作用
在高职院校的程序设计课程教学中,教学内容有一定的抽象性,如果只是采用单一的教学形式,学生很难真正理解程序设计的知识要点。把动画技术灵活应用在程序设计的算法教学中,通过动画的形式来形象表现出各种算法思想,这样学生在对算法的理解上就会更为形象和直观,对不同算法的执行过程有清晰掌握,最重要的是,学生在课后也可以利用网络课程,借助网络资源和工具来学习和探索新的算法[1]。
我们以“VB课程”为例来对三维可视化算法教学的应用进行分析,结合已有的应用案例可以总结出它的应用作用:
首先,对于当前很多高职院校中,非计算机专业学生在对程序设计基础教学时所存在的算法难问题,提供了一种十分有效的解决方案,它的应用使学生的学习思维有了新的变化,可以通过新的思路来正确理解算法教学的内涵。其次,培养学生的学习兴趣和逻辑思维能力。动画形式可以使算法思想表达更为形象,使学生可以更好的理解,从而增强对算法的认识和学习兴趣,同时形象化的演示算法的执行过程,降低了它的理解难度,使学生的思维灵活性得到提升,更具有创新性和探索性。第三,转变了程序设计课程的教学理念和教学方式。这种独特的教学方法可以改变原有抽象枯燥的算法课程,学生对于这种算法的印象是生动形象的,会使记忆更为深刻,减少了在理解上的难度,使教学效果更为良好。
2 三维可视化算法的教学实施
2.1 教学资源建设
在对算法基本思想和执行过程熟料掌握的基础上,可以利用动画设计软件设计出形象的三维场景模型,对算法的思想和执行过程形象化表达出,之后再利用专门的软件来添加相应的字幕予以说明,最后输出作品。
2.2 对三维动画技术和程序设计课程进行有机融合
在三维可视化算法动画制作完成之后,要使它的应用效果最大化发挥,就需要教师对课堂教学的内容和过程进行精心设计,按照课堂的内容进行适时和以恰当的方式将它们和程序设计基础课程的原有课堂教学资源的基础上进行有效整合,然后将其应用于教学实践中。
在课前准备阶段,教师要按照编制好的三维可视化算法动画中的情景合理创设情景故事,之后再把算法思想文字说明以PPT形式进行准备,最后把设计好的三维算法动画通过链接来融入到课堂教学的课件中[2]。
在正式教学过程中,教师要对所教学的算法知识的必要基础知识进行温习,之后顺其自然的把之前准备的情景故事引入到教学内容中。例如对于数组排序的算法教学,教师就可以先引导学生对数组的基本知识进行回顾,例如它的含义、数组的输入和输出,之后再介绍数组的具体应用,然后再对现实生活中排序的情景故事进行利用,此时就可以充分发挥学生的积极性,进行相关讨论,先得到学生的排序方法和排序依据,之后教师再根据学生的意见和方法进行客观点评,最后再明确排序算法的基本概念,同时利用介绍数组排序常用到的选择法和冒泡法来对两种算法和算法思想进行合理排序,在这一过程中可以先采用文字形式来对这两种算法进行讲解,这样可以使同学对算法思想的含义有一个系统的认识,之后再利用动画进一步加深记忆和理解,最后掌握算法的基本思想。
2.3 结合学生的建议进行算法完善和优化
在算法课程教学完成之后,还要对学生的学习效果和意见进行调查和总结,之后再对调查的结果进行分析,再对存在的问题进行改进,从而使算法动画资源更具有可执行性,更能发挥应有的教学效果。
3 总结
高职院校程序设计课程教学具有抽象性特征,采用单一的教学形式和方法很难使学生真正掌握算法教学的内涵和要点,采用三维可视化教学模式,可以通过形象生动的教学形式来调动学生学习兴趣,从而提高课堂教学效果。
参考文献
[1]王梅亮.三维可视化算法教学在程序设计课程中的应用研究[J].电脑知识与技术,2014,(14):3355-3357.
典型算法的可视化研究 篇6
三维地形可视化技术近年来一直是相关研究领域的热点。随着各种测量技术的发展,更高分辨率的地形数据的获得成为可能,然而随之带来的海量数据也对三维地形可视化技术提出了更高要求。尽管近年来图形硬件性能得到了飞速发展,但仍无法直接实时地进行海量数据的可视化。
1 海量数据的可视化算法的工作
主要包括以下三个方面。
1.1 基于视点的LOD
简单来说,多细节层次(Level of Details,简称LOD)就是对三维物体建立多种细节层次、多种精度的模型用于不同的需要,以加速其绘制的技术。
LOD技术最早在1976年由Clark提出。从1992年开始,国内外学者相继提出了各种LOD模型生成算法。
各LOD算法按照构网元素可分为基于规则格网(RSN)和不规则三角网(TIN)两类。基于规则格网的代表算法有1996年Lindstrom[1]提出的基于视点的连续细节层次(CLOD)算法等。基于不规则三角网的代表算法有1998年Hoppe[2]将其1992提出的渐进网格(PM)算法应用到地形多分辨率而得到的基于视点的渐进格网(VDPM)算法。另外YoonSig Kang等[3]提出的基于分区的地形简化算法也非常有参考价值。
按照主要层次数据生成的时间可分为基于视点的动态LOD和静态LOD。动态LOD的特点是根据视点的位置对地形数据进行实时的粗化或者细化来获得不同的细节层次,上面所说的绝大多数算法都属于此类[1,2];静态LOD的特点是通过预处理生成多个层次的数据,当视点改变时只调用相应层次的数据即可。对比动态LOD,静态LOD预先生成了大部分数据,其优点是可以大大减小实时CPU的计算量,缺点是需要使用更多外存和更多与外存的数据交换。
1.2 外部存储算法
海量的数据不能一次装入到内存,所以需要外部存储算法,也就是out-of-core。各种out-of-core算法都力求找到一种好的数据构,使得减少与外存交互的频率。同时,合理使用多线程在这也非常重要。
1.3 Open GL加速
对三维引擎的使用进行优化会大大影响到可视化的速度。目前业界多数使用Open GL作为三维可视化的引擎,也一定程度地对其使用进行了优化。Vanecek[4]提出了一种Delaunay条带化(Stripification)的算法,大大减少了传输给图形硬件的顶点数和图形硬件需要计算的顶点数。苏虎等[5]提到了三角形条带化和扇形化(triangle fan)。
本文采用了业界少用的kd树,并对以上三方面进行优化,提出了一种高效的、切实可行的大规模地形可视化算法。
2 算法原理
本文算法可视化的对象是不规则的点云和由其生成的TIN。算法分两阶段:(1)离线多分辨率层次点云数据的生成;(2)实时的基于视点点云和三角网的更新及可视化。
2.1 离线多分辨率层次点云数据的生成
算法本阶段将点云数据划分为若干个近似方块,再分别对各个块内的点云进行kd树分层,然后存入到外存的一个文件中。
其中划分方块的方法参考Yoon-Sig Kang等[6]提出的基于分区的地形简化算法。同时,块与块之间有狭窄的重叠区,用于实时生成无缝的TIN块。
2.1.1 用kd树对点云数据进行剖分
kd树是一种由二叉树推广而来的用于多维检索的树的结构形式(k即空间的维数)。它与二叉树不同的是它的每个结点表示k维空间的一个点,并且每一层都根据该层的分辨器对相应对象做出分枝决策。
本文没采用业界常用的四叉树或者二叉树,原因是对于不规则的点云,kd树有以下优点:按层分出的数据更能体现地形的趋势;完全平衡树;分层非常灵活简单。当然,kd树也有它的缺陷,如在配合使用纹理数据方面比较复杂。
图1为用常规四叉树、自适应四叉树和kd树(k=2)对点云进行空间剖分的效果图比较,剖分要求每个区内有三个点。可以发现,kd树在空间剖分的灵活性和平衡性上有很大优势,同时用kd树所需要的区更少。
另外,本文对kd树进行两点改进:不严格交替按x、y方向划分空间,而是按照当前空间内的长轴划分。图2是改进的前后的比较。
针对该改进,图2左边为改进前的空间剖分图,右边为改进后的空间剖分图。(a)(b)(c)(d)分别为对空间的第一到第四次剖分,可以看出改进后剖分出的区域更加集中,更能体现点云的趋势了。
2.1.2 外部存储算法:预先生成静态数据
由上面得到的各个分块内的分层点云数据,分别按照层次顺序组织成若干数组,存入缓冲文件。
如图3,缓冲文件包括文件头、块索引区和主体数据区三部分。由块索引区可以找出对应块在主体数据区的位置,从而读取或者写入数据。
本文的外部存储算法有以下特点:
(1)只存储点云数据。由于本算法允许剔除点云,这样必然改变原先的三角网,若保存三角数据将大大增加内外存数据交换而导致性能下降。同时只存储点云还能大大减少外存空间。
(2)多线程。一条写文件线程和多条用于生成分块分层点云数据的线程,可以充分利用计算机资源,加快速度。
2.2 实时的基于视点点云和三角网的更新及可视化
2.2.1 简化的基于视点分辨率算法
图4为基于视点的屏幕误差原理图。图4中l是长度为l的物体,d为该物体距离视点的距离,α为视野角度,Np为屏幕一边总像素数,np为该物体投影到屏幕后占用的像素数。于是有:
当np<1时,长度为l的物体在屏幕上已经不能分辨了,即距离小于l的两点只需要显示其中一点。
本文对此进行简化,当块内当前层的平均点距小于l时,则使用更粗糙的层,使得块内该层次的平均点距恰大于l。
于是,可预先计算每块中各层平均点距。当视点改变时,根据公式(2)计算每块需要的平均点距,对比预先计算好的各层平均点距就可获得当前需要显示的层数,再取出该层数据(点云或更新的三角形)发送给图形硬件完成绘制。这个过程可能需要更新三角形,但总的来说CPU的计算量较小。
2.2.2 简化的视见体
文献[5]提到视见体的裁剪占在整个计算中占有相当的比重,对其的简化很有必要。
本文算法参考文献[7],判断是否在视见体内的最小单位不是每个点,而是每个块。且只要块的一部分在视见体内,则该块需要显示。这样减少了计算和判断,但增加了一些数据的绘制。这实质上是大大降低了CPU的计算,增加了一些GPU的计算。对于现中高端的GPU的计算能力已经大大高于高端的CPU的状况来说,这样做能提高整体的速度。
2.2.3 基于视点的实时更新三角形
(1)层次地构建Delaunay三角网
本文算法对三角形的更新使用的不是Hoppe[2]的压缩和分裂操作,而是Oscar[8]的方法:(1)层次地构建Delaunay三角网的算法;(2)内存中保存各层次三角网的拓扑结构数据,来实现基于视点的实时更新三角网的功能。
其优点有:(1)避免因剔除点而要进行的更新压缩和分裂数据的复杂操作;(2)保存三角形的拓扑结构数据为下面要提到的三角网条带化算法—一种可以大大加速绘制的算法,提供基础。
其缺点是需要更大的内存。
(2)三角网条带化
一般情况下,要绘制n个三角形,需要提供3n个顶点,但如果将三角形如下条带化,则只需要n+2个顶点。如图5。
三角网条带化,可以减少将近2/3的顶点的开销,这包括存储带宽的减少和包括几何变换、光照、裁剪等运算。可以粗略认为GPU提高到原来3倍的速度。许多文献[1,4]都提出了三角网条带化算法。
本文算法根据三角形之间的相邻关系,利用它们可以找出一条完整的三角网条带。算法步骤如下:
(1)找起始三角形。在三角网边界上找一个其三边都有相邻三角形的三角形A,选择它的一个相邻三角形B,该三角形须有一边无相邻三角形。将B作为起始三角形。
(2)找三角形链。从B开始沿着A的反方向,根据相邻关系依次查找出下一相邻三角形中偏向外的一个,加入三角形链条。
(3)结束。当找不到更多三角形时,结束。
2.2.4 外部存储算法:动态交换点云数据
随着视点视线的变化,需动态地从外存中读入点云。该部分有以下特点:
(1)多线程,和第一阶段类似。
(2)内存中有两个“数据池”。内存中开辟两块空间:一存储静态粗略数据,另一存储动态精细数据。静态池主要用减少内外存数据交换和减少视觉停顿感;动态池主要用于预读动态精细数据,保证显示质量。
这样的数据结构式为点云交互剔除操作设计的,对于大范围的地形漫游,没有多少益处,相反地需要更多的内存。
2.2.5 Open GL加速
对三维引擎使用的优化也有很多文献[4,5]。主要集中在使用三角形条带或三角形扇。
本文在此基础上增加了顶点数组缓冲区对象(VBO)的使用。
(1)三角形条带。绘制一个三角网,如果它包含n个三角形,使用一般的方法,就需要给图形硬件传输并让其对3n个顶点进行各种运算(几何变换、光照、裁剪等);而将三角形条带化了,只需要n+2个顶点被传输和进行运算。这相当于减少了将近2/3的开销,性能将得到大大的提升。
(2)顶点数组缓冲区对象。当需要显示的顶点数据不变,使用传统的顶点数组(VA)仍需不断从内存向图形硬件传输相同的数据,这既不必要也会降低性能。使用顶点数组缓冲区对象,可将顶点等数据存储在图形硬件中,在重复渲染顶点(如从不同角度观看)时将能获得较好的性能。
3 实验结果
本文使用一长3.2 km,宽0.3 km的河道及周边的高密度点云数据来测试以上算法。该数据共有2 404 613个点,全分辨率实时生成4 062 096个三角形。实验运行的硬件配置:CPU为i7Q840 1.87 GHz,4 G内存,显卡Quadro FX 3 800 M,17英寸显示器分辨率为1 440×900。软件环境:Fedora 14,gtk3。整个地形浏览过程十分流畅,平均帧率达到60帧/s。以下为各分别率下的某一区域三角网效果对比图。
(分辨率一,总点云数:2 404 613,总三角形数:4 062 096)(分辨率五,总点云数:144 921,总三角形数:285 794)(分辨率六,总点云数:72 704,总三角形数:144 834)(分辨率七,总点云数:36 352,总三角形数:72 552)
图6可看出,当点云数大量减少时,三角网仍能很好地体现地形趋势,但仍有欠缺,主要表现在平坦的地形和变化大的地形点的密度差别不大。这说明使用kd树作为空间数据剖分是合理的。
4 结束语
以往的算法,几乎都是增加CPU的计算量,以减少GPU的工作量。而现在的CPU和GPU的计算能力比较多年以前已经有很大变化,这将很大影响算法的设计。本文的算法比较侧重在GPU计算能力的利用上,这是比较符合当今的现实的。
本文的算法和实现还有相当多需要改善的地方。以后主要在以下几方面进行改进:
(1)生成层次三角网使用GPU的多线程加速;
(2)分辨率改变时(层次更换)会有跳跃感。现考虑改进数据结构,使层次并不在某一阈值整体切换,而是在多个阈值进行部分切换。
(3)在简化地形过程中充分考虑地形复杂度的因素,提高低分辨率时地形质量,这或许是简单改变kd树所不能达到的,目前仍在考虑各种可能的方案。
摘要：大地形实时可视化在GIS、虚拟现实、仿真、游戏等领域有大量应用。对已有算法进行综合和改进,提出了一种简单、快速的实时大规模三维地形绘制算法。该算法主要包括:对所有数据进行空间分块(tile);块内采用改进后的kd树进行进一步空间剖分;方便三维数据交互显示操作的“静态池”和“动态池”数据结构;针对海量数据的外部存储(out-of-core)技术;加速OpenGL的优化方法等。算法运行良好,在微机上达到较高的帧率和较好的显示效果。
关键词：三维地形,kd树,外部存储算法,OpenGL,分块
参考文献
[1] Lindstrom P,Koller D,Ribarsky W,et al.Real-time,continuouslevel of detail rendering of height fields:Proceedings of ACMSIG-GRAPH,1996.[S.l.]:[s.n.],1996:109—118
[2] Hoppe H.Smooth view-dependent level-of-detail control and itsapplication to terrain rendering:SIGGRAPH,1997.Los Angeles:Siggraph,1997:189—198
[3] Kand Y,Lee T,Yang S,et al.A fast digital terrain simpli?cationalgorithm with a partitioning method:Proceedings of HPC,2000.[S.l.]:[s.n.],2000:613—618
[4] Vaneccek P,Kolingerova I.Fast delaunay stripification.Proceedingsof the 19th spring conference on Computer graphics,2003.[S.l.]:[s.n.],2003:24—26
[5]苏虎,周美玉.一种大规模地形的实时绘制算法.武汉大学学报(工学版)2003;36(03):81—85
[6] Pajarola R.Efficient data structures.In:Ed.Gross M,Pfister H.Point-Based Graphics.UK:Elsevier Inc,2007:152—154
[7]王源,刘建永,江南,等.视点相关实时LoD地形模型动态构网算法.测绘学报,2003;32(01):47—52
【典型算法的可视化研究】推荐阅读：
路径规划典型算法07-02
遗传算法的收敛性研究09-18
实验一 典型环节的模拟研究06-10
网络可靠性的算法研究10-24
以能力培养为导向的算法教学研究05-10
典型案例研究06-08
遗传算法研究概述07-19
中文分词算法研究06-14
数据压缩算法研究08-19
RSA算法研究08-28