基于BSP树的块体快速填充算法在矿山三维储量计算中的应用

生成块体模型是矿山三维储量计算中首先要解决的问题。针对传统方法效率低下及精度差的问题,提出了一种基于BSP树结构的三维块体模型快速填充算法。该算法适合于复杂矿体及地形约束下大数量级块体的生成,已成功应用于多个矿山的三维储量计算中,结果表明了该算法具有高效、准确、适用性强等特点。

简化球体的BSP剖分结构的快速碰撞检测

在动态场景中,碰撞检测遇到的最明显的问题就是需要对N个物体对进行两两求交测试,其时间复杂度达到O(N2)。提出了一种简化球体的BSP剖分结构的快速碰撞检测算法。首先用一种调度算法估计BSP树开始失衡的地方,再用一种策略来选择分割面,新结构在表示动态场景中不需要重新构建树,而是在保持树的平衡和合理的高度的同时通过自身的调节来达到更新。

BSP树与格网划分相结合的数字城市三维模型组织方法

日益增长的数字城市三维模型实时可视化显示需求对海量三维模型的高效组织与调度提出了很高的要求,文中基于前人研究成果提出空间分区二叉树(BSP树)与格网划分相结合的数字城市三维模型组织方法,并基于Unity3D采用视点相关的多线程动态调度策略进行了实践应用验证,结果表明该方法高效、可靠,能够满足海量数字城市三维模型的动态可视化与空间分析的需要。

基于深度缓存和BSP树技术的表面消隐技术研究

主要介绍了两种消隐技术,深度缓存算法是通过两个缓存来实现的,其中的一个是用来存放颜色的颜色缓存器,而另一个是用来存放深度的深度缓存器。BSP就是二叉空间分区树,将视景中要显示的多边形或者实物,使用二叉树的原理组织成一种数据结构,通过这种数据结构存储多边形(实物)。

基于BSP树的启发式阴影生成算法

阴影的生成在虚拟现实领域一直是个难题,特别是针对动态光源的大规模场景,目前还没有较成熟的阴影算法。通过对现有阴影生成算法和场景组织算法的研究,该文提出了基于二维空间分割树(BSP树)的启发式阴影生成算法:首先创建场景BSP树,随着观察者视点的改变,选取视剪裁体内的节点创建以光源为视点的遮挡体BSP树,然后通过对该BSP树的遍历拣选出阴影启发区内的物体,经过处理后BSP树只留下一些生成阴影必要的多边形大大减少了计算量,最后能够快速生成阴影。

基于BSP树的三维场景渲染方法研究

BSP树在计算机图形学中应用于视点运动三维场景显示的计算.一般BSP树以递归的方式对平面进行分割,但实际应用的三维场景复杂度较高,也就使得树的复杂度非常高,预处理时间长.文章针对三维场景模型渲染速度慢的问题,基于空间BSP树的理论基础,通过引入包围体的方法使场景中的物体能够快速实现空间二分树划分,进而提高渲染速度.通过实验比较直接渲染和包围体渲染的速度,验证了引入包围体能够缩短预处理时间,提高场景的渲染速度.

点云数据压缩中的边界特征检测

点云数据压缩是逆向工程产品建模中必要的数据预处理手段之一。常见的数据压缩算法未考虑点云边界数据点的保留问题,因此在大比例压缩过程中会出现边界数据丢失的情况从而破坏了数据的完整性。为此,提出了一种利用点云数据小邻域内点的相邻关系来检测边界特征点的算法。该算法能检测出点云数据的内、外边界特征点,同时对边界上的点进行排序,检测出边界特征点中的过渡点,最后构建点云轮廓的边界多边线。该算法不仅能满足在点云数据压缩过程中检测并保留边界特征点的要求,而且生成的边界多边线也为后面的3维模型重建奠定了基础。

数字人切片数据的硬件加速体绘制

实现了一个PC平台下的体绘制硬件加速算法,并对中国数字人、美国可视化人数据集进行可视化.预处理去除图像背景时,将图像从RGB颜色空间转换到YCbCr颜色空间,然后对Cb分量进行Otsu阈值化处理,用生成的二值图像作为掩码图像去除背景.为支持任意大小的体数据,采取了分块策略,并使用BSP树组织数据块,以生成正确的绘制顺序.此外还设计了一种基于图像的CIELUV颜色空间L分量的梯度向量场的传输函数,并取得了良好的绘制效果.

一种改进的点在多边形内外判断算法

为解决多边形内外算法中BSP树退化为链表的问题,提出一种改进的点在多边形内外的判断算法。在构建水平扫描线的BSP树之前,对水平扫描线按照Y值进行排序,将排好序的水平扫描线按照二分法的顺序插入到BSP树中,其查找时间复杂度为O(lbn)。实验结果表明,该算法在不增加BSP构建时间复杂度的前提下,能够保证BSP树的查找效果总是最优的,且简单易行,具有较好的通用性。

基于Director的交互式虚拟仿真系统

针对虚拟仿真系统的开发,设计了一套新方案.该方案利用软件Director M X的多种插件及其集成语言L ingo实现虚拟仿真系统的交互式操作,在满足一般性交互操作要求的同时避免使用OpenGL和C语言编程,大大降低了系统开发的复杂度.结合插件Havok研究了碰撞检测原理,根据实际虚拟仿真系统精度要求演变了BSP树分割法.

三维场景漫游中碰撞检测问题的研究与实现

碰撞检测问题是三维场景漫游的技术难点。论文在对国内外已有碰撞检测算法进行分析比较的基础上,针对三维城市景观系统的数据特点,提出了基于回避三角形分割的二叉空间分割算法的碰撞检测算法。经实践证明,该算法对于场景漫游过程中产生的碰撞问题,可以进行快速有效地检测。

基于混合数据结构的实时GPU光线跟踪算法

研究真实感图像的问题,光线跟踪算法是生成真实感图形的主要算法之一。为了解决光线跟踪算法计算量大、效率低下、对动态场景处理能力不足的问题,采用图形处理器(graphics processing unit,GPU)统一编程架构,提出了一种新的基于计算统一设备架构(Compute Unified Device Architecture,CUDA)编程模型的结合层次包围体(Bounding Volume Hierarchies,BVH)和kd-tree的光线跟踪方法,首先对场景进行启发式的层次包围体分割,随后在每一个层次包围体上做启发式的k维二叉树(k-dimensional tree,kd-tree)剖分,这样就形成了一种新的空间划分,有利于建立高效的空间数据结构,提高光线与场景物体的求交速度。新设计的算法易于扩展到动态场景的光线跟踪,而且具有更快的渲染速度,有利于在应用系统中集成和扩展。实验结果验证了算法的有效性。

求k邻域的体素栅格算法研究

给定一个度量空间中的一组数据点集,k邻域问题在于对于某个数据点求出按照该空间的距离度量离数据点最近的k个数据样本。目前主要有2种方法,一种是基于立方体分割形成的三维立方体体素索引数组的体素栅格(CG(CellGrid)方法,另一种方法是基于树索引结构的方法如kd-Tree等。论文主要研究经典CG方法及解决其内存消耗过多问题的两个改进方法:排序体素栅格(SCG)方法和投影体素栅格(PCG)方法。CG、SCG、PCG算法采用了改进的搜索方法,避免了传统CG算法[2-4]可能得到错误k邻域的问题。对三种算法的时空性能进行了分析比较,给出了相应的实验比较数据。

几种面消隐算法的比较

本文就目前现有面消隐算法进行了分类,对每类算法特点进行了总结。从每种算法本身的特点、消隐空间、排序效率和对场景的限制这几方面,重点分析比较了几种常用的面消隐算法。

三维模型的布尔运算研究

研究了三角形表面模型的布尔运算。传统的CSG算法是基于基本实体的布尔运算进行的,对于由三角形或多边形描述的表面模型的复杂模型运算则十分困难。通过构建模型的BSP树,利用BSP树的空间分割能力,把参与运算的模型分割成两部分,然后,根据交、并、差各种布尔运算,组合分割后的结果,实现了不规则三维模型的布尔运算。

大规模室外场景漫游中入口问题的研究

提出一种综合适用于室内外场景的、添加更多细节的快速漫游方法。将室外场景漫游的预处理四叉树中加入层级入口的视截体,从而可以和室内场景漫游的BSP算法有机地结合起来,以期可以成为综合性场景的一种漫游和渲染的解决方案。

脆性物体破碎效果实时仿真研究

通过对现实世界中脆性物体破碎现象的分析,实现了一种在虚拟场景中实时模拟物体破碎效果的方法。该方法采用三角面片模型对破碎物体进行建模,采用BSP树结构存储以实现三角面片的快速分类及检索。对模型进行预处理并使用平面进行切割,对切割所产生的多边形进行三维重建,得到新的完整的三角面片模型。对预处理所得的各个三角面片设置其初始位置、速度、角度等以实现物体破碎过程的实时仿真,引入碰撞检测以免碎片相互贯穿。

基于点索引的网格模型的层次结构

针对稠密采样的网格模型,提出一种基于面片中心点索引的新的场景BSP树结构.与常规BSP树构造方式不同,文中BSP树以面片中心点位置作为场景中各面片二叉分类的依据,避免了常规BSP树构造方法中因分割与剖分平面相交的面片引起的场景复杂度的增加,大大简化了BSP树的构造过程.实验结果表明:对稠密网格场景,文中的BSP树比常规方式构造的BSP树在加速光线跟踪算法中的求交测试具有明显的优势.

FDTD方法中目标的快速剖分

本文介绍了我们开发的应用FDTD计算复杂目标的RCS,通过对集群计算的特点研究,解决了电大目标的剖分问题。在本文的第二部分介绍利用集群进行FDTD计算,通过对试验数据进行对比分析可以得出在集群上进行FDTD计算RCS显著地减少了计算时间。实验证明该系统在模型剖分和计算RCS上具有较好的性能和实用价值。

一种基于点光源的三维阴影的实时生成算法

阴影的生成在体现虚拟现实环境的真实感程度方面起着重要的作用 ,但现有生成阴影的算法普遍速度较慢 ,不能适应实时绘制的要求 .该文提出了一种基于点光源的实时生成三维阴影的算法 .该算法的基本思想是基于在一个复杂的虚拟环境中 ,某一时段内只有少数多边形相对于光源发生形状的改变 ,从而导致相应阴影计算的改变 ,而大多数多边形相对于光源是静态的 .这样就有可能针对静态物体与动态物体分别作不同的处理 ,使尽可能少的多边形参与阴影计算 .方法是 ,先用 Tiling方法对静态场景进行预处理 ,确定相关阴影多边形集合 ,然后用 SVBSP(shadow volame BSP)树算法计算阴影 .文中所有算法均用 C++实现 ,运行于 IntelPentium 4 0 0微机平台 ,取得了较好的实验结果 .