基于多级线性结构和规则分块的虚拟八叉树

提出一种基于多级线性结构和规则分块、无指针/无位置码的虚拟八叉树模型,具有高效的结点访问效率和存储空间压缩效率,实现了指针八叉树在时间效率、线性八叉树在空间效率两方面优势的统一。新模型能够对三维实体及其内部的非均质属性进行建模,可以保证各种可视化与分析算法的处理效率,在空间信息系统和体图形学等实体建模相关的领域中具有重要的研究意义和应用价值。     

基于体模型优化的虚拟试衣算法

针对目前虚拟试衣人体模型存在的精度和时效上的问题,提出了一种基于体素八叉树的优化的体模型的高效、真实感强的虚拟试衣算法。将空间划分为若干体素,与人体表面相交的体素构成人体表面模型,且体素采用八叉树结构存储。通过Kinect采集的人物的深度图像来计算八叉树中体素的符号距离函数(SDF);使用Marching cube融合图像彩色纹理并渲染出逼真的三维人体模型;提出了碰撞检测响应算法。实验结果表明,提出的方法增强了人物模型的真实感,八叉树结构有效缩短了碰撞检测时间,具有较强的实用价值。     

点云数据在深度学习中表示方法的研究

为了实现在深度学习中能够端到端表示点云模型,提出基于八叉树和K-D树（OctKD）的点云数据表示方法。该方法将无组织的点云转换为体素空间,在体素空间对三维模型进行八叉树剖分,改进了八叉树编码方式;构建节点间的邻接关系,在GPU端并行构建八叉树;为了克服八叉树编码检索效率低的问题,采用三维K-D树索引单个三维空间点。实验结果表明该方法能够真实反映模型本身的细节特征,提高了点云模型的构造时间和检索效率。这种新的数据结构实现将点云转换为卷积神经网络可以接收的数据形式。     

基于海量地震数据的多分辨率扩展八叉树模型

针对现有PC硬件条件的限制和地震数据的海量特征,提出一种基于扩展八叉树的分块多层多分辨率模型。该模型保存了叶节点属性和中间节点属性,实现多分辨率建模,采用基于Morton码的数据块索引方式来提高查询效率。实验结果表明,该模型是一种高效的海量地震数据组织方式,在地质建模领域具有较高的应用价值。     

基于优化八叉树的场景视锥体裁剪算法

大体量3D模型容易导致浏览器端渲染帧数低、显示卡顿及资源消耗大等问题,其原因是这类模型通常包含数以亿计的三角面片,在有限的时间内无法实现快速加载与渲染。针对此类问题,提出一种基于优化八叉树的场景视锥体裁剪算法。该算法采用地址码（Morton码）、节点视距标准和按需增量划分技术,使得八叉树具有自适应性与良好的压缩效率;采用双层包围体和基础相交测试技术,提高视锥体裁剪的精确性,整体上实现提升渲染帧数、显示流畅的目标。高速列车实例模型研究表明,与传统八叉树视锥体裁剪算法相比,所提算法平均渲染帧数上提高了约14帧,空间压缩率提高了37.8个百分点。     

一种新的移动机器人环境模型

环境建模是移动机器人路径规划的基础．针对部分 已知或完全未知的环境,本文提出一种基于位置码的四叉树环境模型,通过建立四叉树节点 位置码与其笛卡尔坐标的一一对应关系,将对四叉树的操作转换到位置码空间,从而简化了 对四叉树的操作．文中研究了基于位置码的四叉树的重要操作,并给出了详细的算法;基于 该模型,作者利用A*算法进行路径规划的仿真研究,仿真结果证明了该模型的有效性．     

针对全空子数据体的GPU体绘制

目的 体绘制是3维数据可视化的主要方法之一。用于体绘制的数据体中包含有大量的空体素,导致光线投射算法进行没有意义的重采样计算,必然降低绘制算法效率。针对全空子数据体体绘制低效问题,提出基于GPU体高效绘制方法。方法 利用八叉树数据结构组织数据,有效管理包含许多空体素的子数据体。通过绘制八叉树非全空叶子节点子数据体表面,使光线投射算法中起始和终止重采样位置更接近数据体中的可视部分,同时根据八叉树全空节点子数据体判定纹理查询结果,计算合适的跳跃步长,快速跳过八叉树中全空节点子数据体。结果 当数据体中空体素较多时,确定合适的八叉树深度,有效地跳过数据体中的空体素,减少体绘制运算量,实现对原基于体包围盒表面绘制的GPU光线投射算法的加速。结论 设计不透明度函数,凸显数据体中层位面,并将算法成功应用于地震数据可视化,取得很好应用效果。     

基于线性四叉树的快速邻域查询算法

邻域查询是位置服务系统的核心技术,它的实现取决于空间对象数据模型.根据空间对象分布构建的四叉树模型,以及线性四叉树中位置码的使用,提出了一种新的基于线性四叉树的快速邻域查询算法.该算法根据满四叉树结点编码思想对线性四叉树的Morton码进行了改进,并增加了表示四叉树所有结点状态的序列,通过网格模型的邻域查询算法实现了线性四叉树的快速邻域查询.     

基于块段模型的三维GIS混合数据结构模型研究*

为了有效地表示三维GIS空间实体,在地质块段模型的基础上,提出了基于八叉树和四面体格网的混合数据结构模型(block octree tetrahedron,BOT模型).采用BOT模型生成算法对块段模型进行重新分割,八叉树作整体描述,四面体格网作局部精确描述,并以不同的灰度值表示不同的单元块属性.同时,为节省存储空间,提出了线性BOT编码技术.实验结果表明,BOT模型充分发挥了八叉树和四面体格网的优点,可以在不增加存储空间的前提下实现对三维目标更高效、更精确的表达.     

基于线性八叉树的快速直接体绘制算法

提出了基于线性八叉树的加速体绘制算法.利用线性八叉树对物体进行空间剖分,光线投射法跨越体数据集中的空体素,以提高绘制的速度.针对光线穿越体数据时的特殊情况,改进线性八叉树邻域查找的方法,特别是不同尺寸的邻域查找方法,克服了层次八叉树邻域查找的低效率,同时提出了光线离开平面的简洁判定方法,方便光线下一个采样点的计算.实验结果表明,该算法能够有效地提高绘制的速度.     

大规模点云内外存调度绘制技术

为实现大规模点云的快速绘制,提出以部分内存访问机制为基础、以节点点数上限为叶节点形成条件的平衡八叉树存储结构。设计点云内外存调度绘制流程,包括节点可见性判断、内外存数据调度和点云绘制等环节。为提高可见性判断的效率,在视点与节点距离、夹角约束条件的基础上给出节点可视半径约束。利用实测大规模点云数据进行实验,结果证明,该技术可以在有限的内存资源条件下,以较小的内存消耗实现上亿级规模点云从整体到局部的流畅绘制。     

基于面向对象八叉树的飞机虚拟维修场景渲染

为了加速大规模虚拟场景的渲染速度,采用基于面向对象八叉树的方法对场景进行渲染。该方法将面向对象技术与传统八叉树技术相结合,采用面向对象八叉树剖分虚拟场景,对场景进行管理;将物体结构树的最小零部件作为最小存储单元,采用叶节点保存对象信息,减小树的存储量和处理时间,降低算法的计算负担;在面向对象八叉树的基础上,采用模型遮挡裁剪算法对位于视域范围内的模型进行遮挡裁剪,减小实际渲染的物体数量,提高渲染速率。通过对飞机虚拟维修场景进行渲染实验,证明了该方法的有效性。     

基于GPU的八叉树结构纹理研究与应用

八叉树结构纹理的应用很好地解决了复杂模型表面2D纹理映射的不足,GPU的高速发展,为八叉树结构纹理在GPU上的现实提供了解决方案。本文将八叉树结构纹理编码为2D纹理,并以节点的广度优先遍历方式在GPU上进行存储,在片段程序访问时提出一种自顶向下的查找方法。实验证明,本文方法取得了准确的纹理映射效果并提高了效率。该方法可以应用于任何需要在复杂物体表面上存储信息的情况。     

Parallel display of objects represented by linear octrees

The storage, display, and manipulation of three dimensional volumetric information requires large amounts of computing resources, both in terms of memory, and processing power. Most existing serial algorithms that display 3-D objects on a 2-D screen are found to be too slow to process the large amounts of volume data in a reasonable time. Hence, one way to increase the performance of the display algorithm is to process individual volume elements (voxels) in parallel. The first part of this paper presents a brief over view of the linear octree data structure which represents 3-D objects by an eight-way branching tree, while the second part focusses on the parallel display of such objects. We have shown that, for an object represented by a linear octree and enclosed in a 2ⁿ×2ⁿ×2ⁿ universe, the maximum number of voxels that can be processed in parallel is 3ⁿ, and the maximum number of time steps required to display such an object is 4ⁿ. This paper presents a set of formulae which identify the processing element (PE) as well as the time step in which a given linear octree node is processed. Similarly, a procedure which determines the locational code of a linear octree node which must be processed by a given PE, at some specific time step, is presented, along with a strategy for determining whether a PE is active or idle     

BW-VSDS:大容量、可扩展、高性能和高可靠性的网络虚拟存储系统

设计并实现了一个大容量、可扩展、高性能和高可靠性的网络虚拟存储系--BW-VSDS.和其他网络存储系统对比,它有如下的特点:1)采用带内元数据管理和带外数据访问的虚拟存储管理架构,存储管理更灵活,并且系统扩展性更好;2)在单个节点内部的多个虚拟卷、多个虚拟池和多个网络存储设备上利用存储虚拟化技术重构得到面向多种存储应用的网络虚拟存储设备,实现了3层的层次化存储虚拟化模型,对内共享存储设备的容量和带宽,对外提供不同属性的虚拟磁盘;3)采用写时按需分配策略提高了存储空间的利用率,使用数据块重组提高了I/O读写性能;4)使用设备链表和位图实现了层叠式虚拟快照,支持增量快照、写时拷贝和写时重定向机制,实现源卷和快照卷的数据共享;5)提出结合带外存储虚拟化管理的后端集中的带外冗余管理结构,数据读写直接访问存储节点,冗余管理节点在磁盘上以日志方式缓存从存储节点镜像写的数据,然后在后台进行RAID5冗余计算,提高了活跃数据的可靠性,减轻了冗余计算对写性能的影响.     

一种基于小波变换的三维体数据压缩算法

该文结合三维小波变换与八叉树算法,提出了一种新的三维体数据压缩算法。该算法利用小波的多分辩率分析能力对体数据进行压缩,同时结合了八叉树特点对体数据进行编码、存储与重构。实际应用表明该算法能较好地对体数据进行压缩,并且能快速地进行重构和随机地访问体单元数据。     

Fast Generation of Pointerless Octree Duals

Geometry processing applications frequently rely on octree structures, since they provide simple and efficient hierarchies for discrete data. However, octrees do not guarantee direct continuous interpolation of this data inside its nodes. This motivates the use of the octree's dual structure, which is one of the simplest continuous hierarchical structures. With the emergence of pointerless representations, with their ability to reduce memory footprint and adapt to parallel architectures, the generation of duals of pointerless octrees becomes a natural challenge. This work proposes strategies for dual generation of static or dynamic pointerless octrees. Experimentally, those methods enjoy the memory reduction of pointerless representations and speed up the execution by several factors compared to the usual recursive generation.     

采用八叉树和OSG分页结点的海量点云三维可视化

针对现有海量点云可视化方法存在索引构建时间长、内存占用大等问题，研究一种八叉树索引结合OSG分页结点的快速可视化方法，可在占用较小内存的基础上快速建立点云索引并实时调度。采用八叉树索引结构对海量点云进行数据组织，建立各层级的八叉树结点并以文件映射的方式分块保存，对结点文件重组织转换为支持OSG渲染引擎的多分辨率点云数据。采用基于OSG分页结点的实时调度技术，对海量点云进行高质量可视化。与目前两款主流的点云数据处理商业软件进行实验对比分析，结果表明所提方法具有索引建立速度快、内存占用小等优点，同时可视化交互更加流畅，适用于各种配置计算机下海量点云数据的调度管理与实时可视化。     

基于线性八叉树的光线投射体绘制算法改进研究

体视化是地学信息三维可视化研究的前沿技术之一，体绘制算法的效率直接关系到体视化的效果。本文在研究已有光线投射体绘制改进算法的基础上，提出利用线性八叉树数据结构对光线投射体绘制算法进行改进研究，不仅实现了体数据的压缩。而且能对压缩体数据进行直接体视化。在PC机上的实验表明，该方法具有时间复杂度与数据复杂度基本无关的特点．加速效果明显。最后，文章指出了该方法的适用范围。