论文研究-基于动态八叉树的移动几何体实时节点判断方法的改进 .pdf

所需积分/C币:7 2019-08-16 584KB .PDF
评分

基于动态八叉树的移动几何体实时节点判断方法的改进,李红波,吴雨芯,现有基于八叉树空间划分(OSD)方法的应用中,动态物体移动后相应部分的树形结构重建速度太慢,多节点标记方法渲染下模型逼真度不够�
山国武花论文在丝 表所示。 表动态八叉树节点数据结构 节点类型 节点数据结构字段摧述 非叶节点 标志空间大小空间中心子节点指针 叶节点链表头结点父节点指针链表首地址叶节点个数 叶点链表内节点 中心半径类型下一物体指针 为了避免八叉树一直循环划分,必须建立评价系统,即找出场景的最人尺寸并以此尺寸 建立第一个立方体,规定八叉树划分的最大深度 和叶节点包含最大三角面数量 建立每个节点的 如果节点深度小于最大深度且包含的三角面数量大于, 则该节点继续划分为个子节点,直到满足要求 移动物体多节点标记处理 当复杂的游戏场景中存在移动物体时,游戏引擎就需要能实时的定位到物体的位置,因 为场景会随着物体的移动而发生改变。八叉树通过指针数组将空间甲的所有物体用文件的形 式保存起来,每个节点内部有自己的物体指针链。当移动物体从节点移动到节点 时,多节点标记描述如下:设是节点的包围盒信息, 表小节点的深度 表 小当前是第几个节点, 表小节点内物体指针链首地址 表小此节点的八 个子节点。现假设物体是水平移动,即节点和处于同一深度的相邻节点(不一定是 叶节点),其存储结构如图所示。物体从移动到的某一时刻刚好在和之间, 此时将物体的唯一标示同时插入到节点、之中,绘制的时候每个节点只需负责包 含在自身内部的那部分三角面即可。以此类推,移动物体每经过一个节点时进行同样的操作, 当物体完全离开节点后将它的信息从链表中删除。 图节点存储结构 动态物体所属节点判断方法的改进 本文研究思路 为提高相应树形结构的重建速度和模型真度,首先利用动态八叉树节点内物体指针链 表确定移动物体与节点的位置关系,用于判断并记录需要处理的邻域节点。接着利用节 点包围盒的松散性,获取移动物体几何中心点,确定动态八叉树的划分因子。然后提出扩展 节点松散包围盒的方法确定物体插入节点。改进方法如图所小。 山国武技论文在丝 物体位 置检测 物体与邻或节 动态八叉树下 点关系检测 移动物体检测 物体几何中心点 计算物体与节 点几何属性 「不司深度划分 节点边长 物体所属节点 判所 松散包围盒扩展 重叠区域计算 半径范围计算 图本文方法研究结构图 Fig 3 Approach of 移动物体实时节点插入计算 在绘制游戏场景时,某一时刻移动模型在两个空间区域都有一韶分模型。如果一个视锥 的平面正好和那两个空间区域之间的平面重合,这时就有可能因为模型挂在另一个节点 而此节点不予绘制,于是两个节点都没有绘制,这显然不合理 现假设物体从节点移动到节点时,那么它与节点 的实时关系有三种 完全包含于节点并与节点不相交(图):完全包含于节点并与节点不相交 (图);与节点、都相交(图)。 包含于节点 包含于节点 与、节点相交 图移动物体与节点关系 物体单独包含在或者节点时,无需扩展松散包围盒,节点中存放唯一标示该对象 几何体的信息,场景更新时,只需要进行八叉树节点的删除与增加操作,即可完成物体 的移动。当物体移动到两个节点之间时,就需要对物体的几何信息进行计算。在游戏场景中, 通常会利用包围盒的方式将移动对象包围起来,方便处理对象与场景的交互。要获取移动物 体的中心点,只需求得该物体的包围盒中心点即可。场景中的对象是由众多三角面片拼接而 成,而一个三角面是由三个顶点构成。因此设物体由个顶点组成,顶点坐标分别定义 为 ,由此可以得到包围该物体的长方体,它的两 个对角点分别为 ,其中 ,对于 和可类似求出,这样便可求得包围盒中 心点坐标为 五“ M“三 动态八叉树划分空间时,尽量将物体加到底层的节点中,可以节省后续的计算量。但对 于动态对象而言,频繁的在各个节点区域移动,这给八叉树的更新带来了额外的开销。物体 山国武花论文在丝 移动到区域、之间的平面吋,此吋物体在两个节点都有部分模型,为了方使描述,利用 其侧面示意图进行分析(图)。八叉树节点松散包围盒扩展处理方法是将节点、的包 围盒同时扩大适当距窝,让互相之间有一定的重叠区域,如果物体包含在重叠区域内(图 ,根据物体的中心点以及边界距离确定物体插入哪一个节点。如果物体大于节点的亘 叠区域(图),则将其放到父节点中去。 包含在重叠区域 大于重叠区域 图物体与重叠区域关系 算法描述 移动物体实时节点插入算法描述如下。 输入:三维静态场景模型,灯光与环境光,摄像机初始角度与坐标 移动物体模型。 输出:场景存储文件,插入节点 步骤:初始化场景,获取场景根节点尺寸。由于动态八叉树中节点的包围体仍然是 一个立方体,设立方体边长为,划分因子为。 步骤:根据评价系统划分三维场景,建立动态八叉树,生成节点指针链表及叶节点内 物体指针链表,将划分后的场景以文件的形式保存 步骤:求得不同深度的节点包闱盒边长,取得移动物体中心点、半径,确定划分因 根据八叉树的划分原理,深度为的节点包围体边长Z=kxw/2,则此节点所能容纳的 物体最大半径为配=是x/24,节点扩大后中心点与以前的中心点相同。又根据 提出的当时,物体移动后进行更新操作的时间复杂度为,且节点扩展后的松 散包围盒达到最小。 步骤:根据物体的半径及中心点的位置,判断物体与重叠区域的关系。在深度 为已知时,比较距物体中心最近的节点,将物体插入此节点。 如果Rkx/2+,则物体包含在重叠区域内,取k,此时只需比较到节点 中心点的距离,因为物体所在的节点仅与其位置有关 如果>kxw/24+,则物体大于重叠区域,将物体插入到、共同的父节点。 步骤:物体继续移动后场景更新,动态八叉树不再淸足评价系统,则返回步骤,算 法退出。 改进方法的运行时间消耗分析如下:由于动态八叉树循环划分过程的停止条件为节点的 最大深度大于 且最大三角面片数小于,故通过计算改进方法中指令重复执行 的次数可得其时间复杂度为。此外,从空间利用效率看,改进方法所占用空间大小主 要由输入所占空间决定(场景初始尺寸),故其空间复杂度为 山国武花论文在丝 实验结果及分析 八叉树划分效率直接体现在场景的加载时间、任意三角面的检索、物体移动时八叉树的 更新时间及游戏的绘制帧率,针对这几项关键的因素,将本文方法与节点多次标记算法进 了比较。实验平台为机一台、小米手机一部,其中电脑: 内存,显卡 ;小米手机屏幕 像素, 处理器 ,内存。本文采用游戏引擎建立了两个规模大小不同的场景,场 景(图)中共有三角面个,顶点个,该场景比较简单,数据量较小;场 景(图)中共有三角面 个,顶点个 场景 场景 图不同规模场景 实验采用场景进行单个移动物体对比测试,结果如图所示。图为多节点标记 方法绘制效果,可以看到部分边缘有锯齿现象,整体色彩比较亮丽,但过于刺眼,画面不够 真实。图为本文采用扩展节点松散包围盒方法的绘制效果,很明显色彩更加柔和,画面 真实感更足。 多节点标记 本文方法 图单个移动物体效果对比 实验采用场景进行测试对比,结果如图所示,日的是比较存在多个移动物体的复 杂场景中画面的渲染效率和处理速度。图为引擎利用八叉树剖分后,包含移动物体的节 点对其进行标记,加载耗时比较严重,渲染时天空体边缘岀现锯齿现象。 多节点标记 本文方法 图多个移动物体效果对比 山国武花论文在丝 为了进步验让本文方法的有效性,在实验过程中记录了包含单个移动物体和多个移动 物体的不同场景的平均加载时间和处理速度,结果如表所示 表不同移动物体数量的场景处理速度对比 头 平均加载时间 平均绘制咴数 场景 多节点标记本文方法多节点标记本文方法 场景 场景 仔细观察图~可以看出,多节点标记方法利用消耗更多的内存资源米节省处理时间。 但是,当复杂场景中出现多个移动物体时,这种以空间换时间的处理手段效果不佳,它忽略 了过多的指针数组査找也需要耗时。更换天空体背景后图边缘会出现锯齿问题,其原因 是没有考虑八叉树的严格分割会出现部分空节点,这些空节点与包含大量三角面片的相邻节 点分辨率就会不一样。本文提出的方法利用了八叉树节点的松散性,将涉及移动物体的节点 适当扩大并使其有一定重叠区域,在不增加内存资源消耗的基础上,考虑了空节点的可利用 性,从一定程度上避免了复杂交错的指针调用。从表还可以看出,随着游戏场景的三角面 片和顶点数的增加,平均加载时间明显变长,但场景的绘制速度并没有减慢。这是由于引擎 第一次加载数据需要遍历八叉树并建立索引,将划分好的场景数据按照指定顺序送入缓冲区 并进行绘制,所以会比较耗时。但是,在数据装载以后进行检索和绘制,效率会得到很大的 提高 结论 本文针对动态八叉树划分游戏场景后,场景中移动物体正好处在两个节点空间区域之间 的平面上的问题,提出了扩展节点松散包围盒并使其有一定重叠区域的方法,该方法根据物 体与重叠区域的关系及物体中心点离节点的距离米确定物体所属节点。当物体的位置发生变 化时只涉及相关节点,所以场景的更新无需遍历整个八叉树,有效的缩短了场景更新时间。 在下一步工作中,由于手机资源的局限性,游戏绘制帧率还比较低,我们将优化引擎处理模 型纹理部分代码,同时根据节点包围盒边长确定节点扩ˆ大的距离,从而更精确的控制移动物 体的位置变化,提高涫染速度。 参考文献 余文勇李亚军陈幼平等虚拟现实场景中基于人叉树的网格简化方法计算机工程与应用 周俊玮万宇万饪根等一种基于八叉树的包围盒碰撞检测方法计算机应用与软件 傅由甲动态八叉树在复杂场景设计中的应用系统仿真学报 滐爱民梁哓辉丁卓一种基于松散八叉树的复杂场景可见性裁剪算法计算机辅助设计与图形学 学报 賁展鹏鲍苏苏刘耀辉基于线性八叉树的快速直接休绘制算法讣算杌应用与软件 山国武技论文在丝 十瑞雪安銈成基于混合空间剖分八叉树场景管坦技术的研究电脑开发与应用 王功明郭新宇赵春江等基于面冋对象八叉树的虚拟漫游碰撞检测计算机工程 吴楷改春万旺跟等游戏引擎八叉树预处理算法设汁微计算机信息 游戏编程凊粹王叔礼张磊译北京人民邮电出版社

...展开详情
立即下载 最低0.43元/次 学生认证VIP会员7折
举报 举报 收藏 收藏
分享
279KB
论文研究-基于k-means聚类算法的研究 .pdf

基于k-means聚类算法的研究,黄韬,刘胜辉,本文首先分析研究聚类分析方法,对多种聚类分析算法进行分析比较,讨论各自的优点和不足,同时针对原k-means算法的聚类结果受随机��

2019-08-15
428KB
论文研究-基于虚拟化及重定向技术的Android沙箱设计与实现 .pdf

基于虚拟化及重定向技术的Android沙箱设计与实现,崔海娜,张天乐,随着移动设备的普及,移动企业管理(EMM)作为解决企业移动化安全和管理问题的产品应运而生。EMM的移动性管理元素之一--移动内容管�

2019-08-22
240KB
论文研究-基于情感信息收集-抽取架构的文本情感分析网络 .pdf

基于情感信息收集-抽取架构的文本情感分析网络,郭豪,双锴,近些年来,文本的情感分类作为自然语言处理领域的关键任务得到了越来越多的关注,基于深度学习的网络模型在该任务中取得了很大的成�

2019-08-18
269KB
论文研究-基于FPGA的多功能扫频信号源的设计 .pdf

基于FPGA的多功能扫频信号源的设计,刘颢阳,李绍胜,扫频信号源是扫频仪主要功能部件,对其实现方法进行研究有重要意义。本文给出了一种由FPGA与DAC组合的扫频信号源设计方案。信号源��

2019-08-15
942KB
论文研究-基于微信公共平台的小型图书馆管理系统的设计与实现 .pdf

基于微信公共平台的小型图书馆管理系统的设计与实现,许鹏,范春晓,从互联网的思维方式上考虑,结合微信公共号对外提供的接口和服务,综合利用开源的开发框架和新兴的WEB服务技术,设计并实现了基于��

2019-08-17
424KB
论文研究-基于JsSIP实现SIP网页客户端 .pdf

基于JsSIP实现SIP网页客户端,高嵬,孙其博,JsSIP是使用Javascript脚本语言实现的开源SIP协议栈,是目前广泛应用的各种基于SIP协议的Web音视频通信终端的基础库�

2019-08-22
194KB
论文研究-基于WinCE的智能车载仪表的设计 .pdf

基于WinCE的智能车载仪表的设计,韩琨,郝继飞,针对当前汽车仪表的发展趋势,设计了一款基于WinCE操作系统的智能车载仪表。智能车载仪表可以通过CAN总线接受汽车各个部件的ECU的信�

2019-08-20
1.56MB
论文研究-基于深度学习的人脸识别算法研究 .pdf

基于深度学习的人脸识别算法研究,赵学斌,张雷,传统的人脸识别算法主要是基于图像的浅层特征提取,比如LBP、SIFT、HOG等图像特征描述算子,然后进行多种浅层特征融合,PCA降维之后��

2019-08-16
426KB
论文研究-基于Android平台的电子书阅读器的设计与实现 .pdf

基于Android平台的电子书阅读器的设计与实现,赖穆彬,邹仕洪,本文主要阐述了在android平台上十分流行的电子书阅读器的设计与实现,具有智能断章,翻页特效,场景模式切换,阅读字体调节,用户��

2019-08-16
255KB
论文研究-基于CUDA技术的运动估计算法加速 .pdf

基于CUDA技术的运动估计算法加速,刘婷,程荣辉,运动估计模块是数字图像/视频处理中最重要的模块之一,它的处理技术直接决定了图像/视频处理的效果,快速有效的运动估计算法是现�

2019-08-18
305KB
论文研究-基于加权跳数的DV-HOP定位算法 .pdf

基于加权跳数的DV-HOP定位算法,白进京,周先菊,节点定位技术在无线传感器网络中占据至关重要的地位,如何提高定位精度是本文的研究的目的。本文深入分析了DV-Hop(Distance Vector-Hop��

2019-08-21
290KB
论文研究-基于LSTM神经网络的股价短期预测模型 .pdf

基于LSTM神经网络的股价短期预测模型,成烯,钟波,股价预测是时间序列预测领域最具有挑战性的问题,准确预测股价能够帮助投资者降低风险,提高收益。本文应用LSTM神经网络对股价指��

2019-08-14
533KB
论文研究-基于WiFi的环境监测系统设计 .pdf

基于WiFi的环境监测系统设计,李山,,WiFi(Wireless Fidelity)技术具备传输速率高、传播距离远、覆盖范围广等特点,在无线局域网应用中得到了迅猛的发展。本文设计并实现了一�

2019-08-16
473KB
论文研究-基于I-7188的EIB网关的设计与实现 .pdf

基于I-7188的EIB网关的设计与实现,何欣,黄涛,EIB网关对智能家居的集成应用推广具有极其重要的意义。本文通过研究EIB(European Installation Bus)协议及其外部通信机制,提出基于I-7188��

2019-08-16
613KB
论文研究-基于React的前端组件化研究与设计 .pdf

基于React的前端组件化研究与设计,周兴宇,卞佳丽,随着互联网行业的快速发展,Web应用更加庞大和复杂,对用户体验和交互有着越来越高的需求,对前端技术不断提出新的要求。React是一�

2019-08-20
1.67MB
论文研究-基于深度学习的不可见图像隐写术 .pdf

基于深度学习的不可见图像隐写术,董士琪,刘建毅,隐写术和隐写分析是信息安全领域中的一个重要分支——信息隐藏的主要内容,二者在对抗中不断发展进步。近年来已经有大量的工作将��

2019-08-15
256KB
论文研究-基于可信度的不确定性推理的研究与应用 .pdf

基于可信度的不确定性推理的研究与应用,杨阿琴,,本文将基于可信度的不确定性推理其运用到民航机务维修差错预警专家系统中进行研究中,并在Jess推理引擎的基础上,研究了具体的知��

2019-08-16
202KB
论文研究-基于PSO算法的 -SVM算法参数优化 .pdf

基于PSO算法的 -SVM算法参数优化,王洁,白静,在v-SVM算法参数选择中,现多采用反复试验的方法,局限性较大且操作复杂。因此,本文采用了粒子群算法来优化v-SVM中的参数,并将之��

2019-08-16
394KB
论文研究-基于数字图像处理的车牌识别技术的研究 .pdf

基于数字图像处理的车牌识别技术的研究,彭运生,王晨升,车牌识别系统(License Plate Recognition 简称LPR)技术广泛应用于智能交通系统中,一般分为车牌预处理、定位、字符分割和字符识别四个主�

2019-08-20
265KB
论文研究-基于JDBC的数据库访问研究 .pdf

基于JDBC的数据库访问研究,于宁宁,赵宗平,JDBC兼具有强大的数据处理功能,它可以处理各种不同类型的数据源,同时具有极其简单、易用的编程接口,因而得到了广泛的应用。为��

2019-08-15
img

关注 私信 TA的资源

上传资源赚积分,得勋章
相关内容推荐