多分辨率BSP树的生成及应用

CAD和科学可视化应用要求能够让用户对复杂场景进行交互式显示或者处理 ,因此 ,多细节层次技术被广泛应用于图形系统中以提高处理效率 .通过构造一种新的 BSP( binary space partitioning tree)树形式来加速多细节层次模型的绘制 ,这种技术已成功地应用于所开发的多分辨率模型编辑系统 .同时 ,详细描述了新的 BSP树结构的构造和绘制过程 .

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

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

BSP树消隐算法的改进研究

BSP树算法是在三维景物空间中实现消隐的一种常见算法.BSP树消隐算法中的遍历算法通常是采用递归来实现,在实时虚拟环境具体实现时会导致很大的系统开销.本文在分析BSP树消隐算法中的BSP树的构造和遍历方法的基础上,以一种基于顺序存储结构的非递归算法来代替通常的递归算法,有效的提高了BSP树的遍历速度,提高了三维景物空间的消隐的生成速度,降低了场景中的景物表面多边形的存储空间,有利于实时虚拟环境中三维景物的快速生成.

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

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

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

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

基于物体级BSP树的大规模室外场景渲染

BSP树是图形学领域中用来加速大规模场景计算的重要手段之一。经典BSP树的构造策略是以形体表面的三角形本身作为分割平面,使得树的复杂度非常高,预处理时间长,所以一般适合于室内场景的渲染或碰撞检测。这里针对由许多小模型组成的大规模室外场景的渲染,给出一种构造物体级BSP树并利用其进行渲染的方法。这种方法在视点改变时无需更改BSP树,在视野范围不大的情况下,可以极大地提高渲染速度。实验结果证明了这种方法的有效性。

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

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

基于BSP的光线跟踪并行处理研究

提出了一种基于BSP树的光线跟踪并行处理方法。该方法通过分析视点与场景空间的关系,进行像素空间的划分,避免并行处理任务分配的盲目性;采用近似的NSOTA算法保证了任务分配的均衡性。试验表明,并行方法能大大提高光线跟踪的处理速度。

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

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

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

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

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

实现了一个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树分割法.

虚拟空间中的碰撞检测

为了在虚拟空间中模拟真实世界 ,碰撞检测的实现十分重要。其算法的性能直接影响整个应用系统的效果。

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

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

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

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

三维模型的布尔运算研究

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

基于多面体的空间查询及其应用

展示了一种多面体区域的多属性查询结构,通过把多面体区域映射成高维的矩形区域达到简化问题的目的,多面体查询区域和多面体约束通常来说可能是一种更好的查询选择,介绍了一种有效的多属性索引结构(p-树)以及遗传算法在空间查询中的应用。

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

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

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

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