[转]基于四叉树(QuadTree)的LOD地形实现

时间:2022-09-22 08:10:50

实现基于四叉树的LOD地形时,我遇到的主要问题是如何修补地形裂缝。

本段我将描述使用LOD地形的优势,我实现LOD地形的思路,实现LOD地形核心模块的详细过程,以及修补地形裂缝的思路。

首先,LOD地形与一般地形不同:一般的地形是这样实现的:整个地形是一个三角形网格,一个513*513的地形包括513*513个顶点,512*512*2个三角形;在开始渲染地形之前,写入地形的顶点缓冲(vertexbuffer)和索引缓冲(indices buffer),顶点缓冲和索引缓冲都是数组;顶点缓冲存储的是地形的顶点,每个顶点的属性包括其自身的坐标;索引缓冲存储的是每一帧渲染的顶点的索引,在顶点缓冲中,每个顶点都有自己的索引,索引缓冲的元素便是存储于顶点缓冲中的元素的索引;每一帧渲染(Render或Draw)地形的时候,只根据索引缓冲便可渲染出地形,比如,一个3*3的地形,顶点缓冲中一共有9个元素,即9个顶点,若索引缓冲中存储的元素是{0,1,3},则渲染的是顶点缓冲中第0、1、3个顶点,渲染出的形状是部分地形:一个三角形,类似的,若索引缓冲中存储的元素是{0,1,3,1,3,4},则渲染出的形状是部分地形:由两个三角形拼接而成的正方形,若索引缓冲中存储的元素是{{0,1,3,}{1,3,4,}{1,2,4,}{2,4,5,}{3,4,6,}{4,6,7,}{4,5,7,}{5,7,8}},则渲染出的是完整的地形。LOD地形是这样实现的:整个地形也是一个三角形网格,与一般地形不同的是,LOD地形当中,距离摄像头(摄像头相当于我们的眼睛)较近的地方,地形的三角网格较多,距离摄像头较远的地形,地形的三角网格较少,这样在距离摄像头较近的地方,我们看到的地形就更细致更真实,在距离摄像头较远的地方,渲染出来的地形比较粗糙,但是我们看到的效果和用一般地形渲染远处地形呈现的效果一样,所以,LOD地形每一帧渲染的顶点个数小于一般地形每一帧渲染的顶点个数,其渲染速度比一般地形的渲染速度高。之所以选择LOD地形,是因为用一般地形的渲染方式渲染大型的地形会导致程序的运行效率比较低,而用LOD地形的渲染方式则会在渲染同样大小的地形时提高程序的运行效率。比如,只渲染512*512的一般地形时,程序的帧速率(FPS)是100帧/秒,而只渲染1024*1024的一般地形时,程序的帧速率降到20帧/秒。3D游戏不仅包括地形,而且包括其他场景,其他场景的渲染效率有时候较低,比如粒子系统、多层纹理映射等都会使程序的渲染效率降低。包括地形在内的整个场景的帧速率至少要达到30帧/秒,才能保证游戏的流畅度。所以,如果使用大型的地形,必须保证地形的帧速率达到90帧/秒以上,这样才能提高整个游戏场景的渲染效率。

其次,我在实现LOD地形时,选择的地形数据结构是四叉树(QuadTree),在开始渲染地形之前,首先写入整个地形的顶点缓冲、索引缓冲,在每一帧开始渲染地形之前,根据摄像头当前的坐标更新索引缓冲,然后根据索引缓冲渲染出地形,接下来我将详细介绍如何在每一帧更新索引缓冲。首先介绍四叉树,地形的四叉树结构QuadTreeData的核心属性:int类型的中心顶点的索引m_nCenter,int类型的左上、右上、左下、右下顶点的索引m_nCorner[4],QuadTreeData*类型的左上、右上、左下、右下四个孩子节点m_pChild[4],bool类型的真实叶子变量m_bRealLeaf,bool类型的虚拟叶子变量m_bVirtualLeaf。整个地形是一个四叉树,以下举例说明如何建造地形:一个5*5的地形,头节点的m_nCenter是12,m_nCorner[4]依次是0、4、20、24,m_pChild[0]的m_nCenter是6,m_nCorner[4]依次是0、2、10、12,m_pChild[1]、m_pChild[2]、m_pChild[3]的属性值可以此类推。以下是我定义的四叉树结构体:

typedef struct QuadTreeData  

float maxHeight;
float minHeight; vector<int> mCrackU;
vector<int> mCrackR;
vector<int> mCrackB;
vector<int> mCrackL; int m_nCenter; /// 四叉数保存的第一个值,某网格中心点的索引
int m_nCorner[]; /// 四叉树保存的第二个值 bool m_bVisible;
bool m_bVirtualLeaf; ///虚拟的叶子
bool m_bRealLeaf; ///真实的叶子,真实的叶子没有中心 int mLevel;
int mSelfCorner;
bool m_bHandled; vector<byte> mCode;
vector<byte> mCodeU;
vector<byte> mCodeB;
vector<byte> mCodeL;
vector<byte> mCodeR; double mGUID; QuadTreeData* m_pChild[];
QuadTreeData* m_pFather;
QuadTreeData* m_pAncester; QuadTreeData;

我们可以设定整个四叉树的最多层级,比如9,头结点的层级是0。若某个四叉树节点的m_nCorner[1]和m_nCorner[0]相差为1,或者该四叉树节点位于整个四叉树的第9层,则该四叉树节点为真实叶子,其m_bRealLeaf值为true,四个孩子节点的值均为空NULL,至此,整个地形的四叉树建造完成。更新索引缓冲时,首先更新虚拟叶子节点:遍历四叉树的每个节点,并评价每个节点:若该节点为真实节点,则该节点不可再分,将virtualLeaf设置为true;若该节点为虚拟节点,若该节点不满足评价公式(不可再细分),则将该节点的virtualLeaf设置为true。否则将virtualLeaf设置为false(评价公式:g=d/e×r×C1×C2 ,当g<1 ,则该节点可再分,virtualLeaf设置为false。其中,d表示节点和摄像机的距离;e表示节点边长;r=e/diff ,其中diff表示该节点四个角最大高度与最小高度的差值;C1 、C2 代表分辨率。);其次修补地形裂缝,大致思路是:四叉树的每个节点都有自己的huffman编码,通过huffman编码可以遍历到自己的位置,如下图所示:

[转]基于四叉树(QuadTree)的LOD地形实现

每个节点同等级的上、下、左、右兄弟节点的huffman编码可以根据自己处于父节点的位置(左上、右上、左下、右下)推导出来。在第一步更新了四叉树的虚拟叶子节点之后,遍历所有的虚拟叶子节,通过每个叶子节点的左上、右上、左下、右下兄弟节点的huffman编码找到每个叶子节点的兄弟节点,若兄弟节点的virtualLeaf值为false,则在兄弟节点与该节点共享的边上存在裂缝,进行修补:找出兄弟节点在该边因细分所添加的三角形网的顶点,将这些点的索引依次压入该节点该条边用于修补裂缝的点的链表。至此,修补裂缝结束;最后创建新的索引缓冲:遍历所有虚拟叶子节点,若该节点四个边的用于修补裂缝的点的列表均为空,则将该节点的索引压入索引缓冲,否则,将该节点存在裂缝的边的用于修补裂缝的点的链表作为构建地形的三角形网的顶点,压入该节点的索引。至此,索引缓冲更新完毕。

效果图如下:

[转]基于四叉树(QuadTree)的LOD地形实现

[转]基于四叉树(QuadTree)的LOD地形实现

原文链接:

Unity教程之-基于四叉树UQuadtree在Unity中实现场景资源的动态管理

最新-基于四叉树的LOD地形设计

基于四叉树(QuadTree)的LOD地形实现

面向GPU的多LOD因子的大规模场景可视化策略

[转]基于四叉树(QuadTree)的LOD地形实现的更多相关文章

  1. 回想四叉树LOD地形(上)

           唉.~事实上这是在差点儿相同一年前实现的东西,但当时没作好记录.放了那么久了,假设不做点总结的话,好像有点对不起自己,于是·········还是做点什么吧.        我脑洞比較小, ...

  2. &lbrack;译&rsqb;2D空间中使用四叉树Quadtree进行碰撞检测优化

    操作系统:Windows8.1 显卡:Nivida GTX965M 开发工具:Unity2017.2.0f3 原文出处 : Quick Tip: Use Quadtrees to Detect Lik ...

  3. C&plus;&plus;: 基于四叉树数据结构的自适应网格(初探)

    C++: 基于四叉树数据结构的自适应网格 二叉树是一种典型的非线性存储数据结构,查找效率可以达到\(O(log_2N)\),同样,这类树状结构存在许多种变体,详细参考邓俊辉老师的<数据结构C++ ...

  4. Ogre代码学习之1——Ogre中地形lod的基础:deltaHeight的计算

    Ogre的地形系统中的重要概念:高度差,英文HeightDeltas,表示某个完整细节中的顶点,在某个它被隐去的lod中被插值之后的高度和原始高度(即高度图中的高度)之差. DeltaHeight = ...

  5. 转&colon;Ogre TerrainGroup地形赏析

    1.1  参考 http://www.ogre3d.org/tikiwiki/tiki-index.php?page=Ogre+Terrain+System http://www.ogre3d.org ...

  6. WebGL简易教程&lpar;九&rpar;:综合实例:地形的绘制

    目录 1. 概述 2. 实例 2.1. TerrainViewer.html 2.2. TerrainViewer.js 3. 结果 4. 参考 1. 概述 在上一篇教程<WebGL简易教程(八 ...

  7. Ogre 1&period;8 terrain 和 paging 组件

    以下转自:http://hi.baidu.com/xocoder/item/e8d87cf53d87612b753c4cfd OGRE地形生成 OGRE可以通过两个接口来生成地形,分别是void Te ...

  8. 游戏引擎架构 &lpar;Jason Gregory 著&rpar;

    第一部分 基础 第1章 导论 (已看) 第2章 专业工具 (已看) 第3章 游戏软件工程基础 (已看) 第4章 游戏所需的三维数学 (已看) 第二部分 低阶引擎系统 第5章 游戏支持系统 (已看) 第 ...

  9. Cesium原理篇:2最长的一帧之网格划分

    上一篇我们从宏观上介绍了Cesium的渲染过程,本章延续上一章的内容,详细介绍一下Cesium网格划分的一些细节,包括如下几个方面: 流程 Tile四叉树的构建 LOD 流程 首先,通过上篇的类关系描 ...

随机推荐

  1. PostMan插件安装

    一直没装上postman,今天运气好,竟装上了 给大家show一下吧,也希望大家跟我一样走弯路甚至于走不过去!:) 1.下载Postman_v4.1.3.rar,这个是我测试验证并打包的: 加QQ群: ...

  2. DB天气app冲刺二阶段第九天

    今天是第九天了 不管怎么样也要收尾了赶紧,毕竟不可能做到尽善尽美了,时间不够了所以要把该砍掉的砍点,然后应对下周的大二同学的面试.尽量做好界面的美化工作这是最基本的了.毕竟我一直崇尚的就是UI设计了. ...

  3. sqlserver授予用户查看执行计划的权限

    sqlserver查看语句的执行计划是非常重要的,可以提高开发人员代码的质量.所以有必要授予开发人员对数据库查看执行计划的权限.   查看执行计划的权限属于数据库一级别的权限,具体例子如下   use ...

  4. 树莓派的&period;bashrc和&period;bash&lowbar;aliases文件

    在你的home文件夹中,你能够找到一个包括用户配置的隐藏文件.bashrc. 你能够依据自己的须要改动这个文件. 文件里为你提供了一些实用的调整设置.默认情况下当中一些设置是被凝视掉的. 比如,一些l ...

  5. C&num;关于HttpClient的应用(一):获取IP所在的地理位置信息

    public class IpHttpClient:BaseHttpClient { private String appKey; private const string HOST_PATH = & ...

  6. excel自动化翻译2

    Python爬虫视频教程零基础小白到scrapy爬虫高手-轻松入门 https://item.taobao.com/item.htm?spm=a1z38n.10677092.0.0.482434a6E ...

  7. shell中信号处理

    参考: Shell 脚本中信号处理实践 Linux Shell 的信号 trap 功能你必须知道的细节   在 unix 里,可能发生的每一种类型的事件都是由一个独立的信号来描述,每一个信号都是一个小 ...

  8. 译:1&period; 初识 Apache Axis2

    欢迎使用Apache Axis2 / Java Apache Axis2 是一个Web Service  SOAP / WSDL 引擎,它被广泛用于Apache Axis SOAP 栈. Apache ...

  9. Oracle批量插入数据SQL语句太长出错:无效的主机&sol;绑定变量名

    Oracle数据库,用mybatic批量插入数据: <insert id="saveBatch" parameterType="io.renren.entity.N ...

  10. inventor安装错误

    AUTODESK系列软件着实令人头疼,安装失败之后不能完全卸载!!!(比如maya,cad,3dsmax等).有时手动删除注册表重装之后还是会出现各种问题,每个版本的C++Runtime和.NET f ...