共查询到18条相似文献,搜索用时 171 毫秒
1.
BSP数据结构已经在大规模的游戏引擎产品中取得了突破性的成功,但是在现实应用中还有许多需要实际改进后才能应用。为此,改进BSP开发出一种简单、灵活的解决方案,即虚拟BSP(vBSP)来解决应用实际应用。通过研究并改进原始的BSP树,意在使BSP树简单化、实用化,并可以减少算法的复杂度,降低其它改进算法的负面影响。基于“空间换时间”的思想,通过开辟引用存储空间而不是直接分割BSP树的方法,最终达到提高算法的实用性。 相似文献
2.
3.
针对稠密采样的网格模型.提出一种基于面片中心点索引的新的场景BSP树结构.与常规RSP树构造方式不同,文中RSP树以面片中心点位置作为场景中各面片二叉分类的依据,避免了常规BSP树构造方法中因分割与削分平面相交的面片引起的场景复杂度的增加,大大简化了BSP树的构造过程.实验结果表明:对稠密网格场景,文中的BSP树比常规方式构造的BSP树任加速光线跟踪算法中的求交测试具有明显的优势. 相似文献
4.
5.
BSP树是图形学领域中用来加速大规模场景计算的重要手段之一.经典BSP树的构造策略是以形体表面的三角形本身作为分割平面,使得树的复杂度非常高,预处理时间长,所以一般适合于室内场景的渲染或碰撞检测.这里针对由许多小模型组成的大规模室外场景的渲染,给出一种构造物体级BSP树并利用其进行渲染的方法.这种方法在视点改变时无需更改BSP树,在视野范围不大的情况下,可以极大地提高渲染速度.实验结果证明了这种方法的有效性. 相似文献
6.
游戏地图的算法在整个游戏设计中占有重要地位。通过对游戏地图算法的研究,本文对游戏地图贴图算法中的效率问题进行了分析,提出了改进算法,并在Visual C++的环境下实现。通过改进地图图块的存储方法,将地图图块的句柄和地图图块的索引值等数据以二叉排序树结构的方式存储,使动态树可以随游戏的进度动态地往地图上添加图块,结构灵活,速度快。 相似文献
7.
Dijkstra算法是求解嵌入式GIS系统中最短路径的经典算法,通过对Dijkstra算法进行分析,改变图的存储结构和搜索方法,采用基于矩形限制区域的二叉排序树改进算法,减少了内存存储空间,缩短了查询时间,在一定程度上优化了最短路径的计算过程,实际数据测试也表明了该算法的有效性。 相似文献
8.
提出动态规划法构建最优二叉查找树的算法模型,并对其进行改进,构造实例表明算法的有效性。 相似文献
9.
本文通过叙述哈夫曼编码在通讯、网络、数据压缩、图像处理中的应用及实现哈夫曼编码的二叉哈夫曼树的生成算法,论述引入三叉哈夫曼树的优点及实现三叉哈夫曼树的算法,给出生成三叉哈夫曼树的C源程序。 相似文献
10.
二叉链表有一个致命的缺点,即不容易显示到屏幕上。对传统的二叉树遍历算法进行改进,解决了二叉链表的输出问题,使数据结构中树的逻辑结构显示得以实现。并进而揭示出树的输出结果与逻辑结构间的几何关系。 相似文献
11.
This paper presents a new method for evaluating boolean set operations between Binary Space Partition (BSP) trees. Our algorithm has many desirable features, including both numerical robustness and O(n) output sensitive time complexity, while simultaneously admitting a straightforward implementation. To achieve these properties, we present two key algorithmic improvements. The first is a method for eliminating null regions within a BSP tree using linear programming. This replaces previous techniques based on polygon cutting and tree splitting. The second is an improved method for compressing BSP trees based on a similar approach within binary decision diagrams. The performance of the new method is analyzed both theoretically and experimentally. Given the importance of boolean set operations, our algorithms can be directly applied to many problems in graphics, CAD and computational geometry. 相似文献
12.
Computing Dynamic Changes to BSP Trees 总被引:3,自引:0,他引:3
This paper investigates a new method for dynamically changing Binary Space Partition (BSP) trees. A BSP tree representation of a 3D polygonal scene provides an ideal data structure for rapidly performing the hidden surface computations involved in changing the viewpoint. However, BSP trees have generally been thought to be unsuitable for applications where the geometry of objects in the scene changes dynamically. The purpose of this paper is to introduce a dynamic BSP tree algorithm which does allow for such changes, and which maintains the simplicity and integrity of the BSP tree representation. The algorithm is extended to include dynamic changes to shadows. We calibrate the algorithms by transforming a range of objects in a scene, and reporting on the observed timing results. 相似文献
13.
14.
对景物密集的复杂场景 ,提出了基于主要遮挡物的动态可见性算法 .该算法通过场景中预先定义的主要遮挡物 ,动态地形成一个遮挡树 ,位于遮挡树遮挡区域中的景物将被剔除 .当场景按照 BSP树组织 ,并按从前向后的顺序绘制场景时 ,算法具有高效率 .对主要遮挡物采用简化的遮挡物代理 ,对盒子类型的遮挡物提出了一种有效的简化算法 .该算法已经被“RTG三维图形开发工具包”采用 ,经实际验证 ,对复杂场景 ,该算法可以明显地提高绘制速度 相似文献
15.
16.
The Priority Face Determination Tree for Hidden Surface Removal 总被引:1,自引:0,他引:1
Many virtual environments are built from a set of polygons that form the basis of objects in the scene. Using priority-list algorithms, the sequence in which these polygons are drawn is dependent upon the location of an observer; the polygons must be ordered correctly before a realistic image can be displayed. It is necessary for a scene to be drawn correctly in real time from all locations before the observer can move interactively around the scene with complete freedom.
The binary-space partitioning (BSP) tree developed by Fuchs, Kedem and Naylor in 1980 stores the view independent priority of a set of polygons which can be used to obtain the correct order for any given view-point. However, the number of polygons grows significantly due to the BSP splitting stage, increasing the number of nodes in the tree. This affects linearly the number of tests necessary to traverse the tree to obtain the priority of the set of polygons.
The algorithm presented here is built using its associated BSP tree, but attempts to reduce the number of tests to, log4/3 n , at the cost of a tree of size of O ( N 1.5log4/3 n −1 ), where n is the initial number of polygons in the scene, and N the resulting number after BSP splitting. To achieve the increase in run-time efficiency, a height plane is used to restrict the view point of the observer to a fixed height, but the key to the efficiency of the algorithm is in the use of polygonal dependencies . In the scene; if we know our location relative to the front or back of a polygon, then our position relative to one-quarter of the remaining polygons, in the expected worst-case, can be determined. 相似文献
The binary-space partitioning (BSP) tree developed by Fuchs, Kedem and Naylor in 1980 stores the view independent priority of a set of polygons which can be used to obtain the correct order for any given view-point. However, the number of polygons grows significantly due to the BSP splitting stage, increasing the number of nodes in the tree. This affects linearly the number of tests necessary to traverse the tree to obtain the priority of the set of polygons.
The algorithm presented here is built using its associated BSP tree, but attempts to reduce the number of tests to, log
17.