基于多索引树的阴影光线遍历算法

阴影光线求交计算是光线跟踪的重要计算瓶颈。然而,构造一棵能有效剔除阴影 光线冗余求交计算的标准树结构仍然十分困难。为区分遮挡和非遮挡的阴影光线,提出一种基 于多索引树的遍历方法,在节点中增加提升遍历速度的索引。首先,针对遮挡光线为尽快与图 元相交的遍历特征,选择性的将位于叶节点上、对光线遮挡概率高的图元索引到中间节点,促 使光线提前在树中层停止搜索。其次,针对非遮挡光线为尽快搜索最邻近节点的遍历特征,为 底层节点建立邻接索引,减少节点搜索空间。利用帧间相关性预测遮挡类型,采用相应遍历方 法进行针对性的加速。相比专有树结构的遍历算法,该算法将遍历时效率提升 20%以上,具有 更好的遍历性能,且预计算时间更少。     

Ray Specialized Contraction on Bounding Volume Hierarchies

In this paper we propose a simple but effective method to modify a BVH based on ray distribution for improved ray tracing performance. Our method starts with an initial BVH generated by any state‐of‐the‐art offline algorithm. Then by traversing a small set of sample rays we collect statistics at each node of the BVH. Finally, a simple but ultra‐fast BVH contraction algorithm modifies the initial binary BVH to a multi‐way BVH. The overall acceleration for ray‐primitive testing is about 25% for incoherent diffuse rays and 30% for shadow rays, which is significant as a data structure optimization. Similar results are also presented for packet ray tracing, and for Quad‐BVHs the improvement is 10% to 15%. The approach has the advantages of being simple, and compatible with almost any existing BVH and ray tracing techniques, and it require very little extra work to generate the modified tree.     

WSN中基于最小延时的数据汇集树构建与传输调度算法

针对现有的无线传感器网络数据汇集算法延时较大的不足,对最小延时数据汇集树和传输调度问题进行了研究。提出一种基于度约束的汇集树构建算法(DCAT)。该算法按照BFS方式遍历图,当遍历到每个节点时,通过确定哪些节点与汇点更近来确定潜在母节点集合。然后,选择图中度数最小的潜在母节点作为当前被遍历节点的母节点。此外,为了在给定的汇集树上进行高效的数据汇集,还提出两种新的基于贪婪的TDMA传输调度算法:WIRES-G和DCAT-Greedy。利用随机生成的不同规模的传感器网络,参照当前最新算法,对所提方法的性能进行了全面评估。结果表明,与当前最优算法相比,将所提调度算法与所提汇集树构建算法结合起来,可显著降低数据汇集的延时。     

无线传感器网络中基于最小延时的数据汇集树构建与传输调度算法

无线传感器网络的数据通信模式问题是目前的研究热点,针对现有的无线传感器网络数据汇集算法延时较大这一不足,对最小延时数据汇集树和传输调度问题进行了研究。提出一种基于度约束的汇集树构建算法(DCAT)。该算法按照 BFS 方式遍历图,当遍历到每个节点时,通过确定哪些节点与汇点更近来确定潜在母节点集合。然后,选择图中度数最小的潜在母节点作为当前被遍历节点的母节点。此外,为了在给定的汇集树上进行高效地数据汇集,还提出两种新的基于贪婪的TDMA传输调度算法：WIRES-G 和 DCAT-Greedy。利用随机生成的不同规模的传感器网络,参照当前最新算法,对文中方法的性能进行了全面评估。结果表明,与当前最优算法相比,文中调度算法与文中汇集树构建算法结合起来,可显著降低数据汇集的延时。     

二叉树遍历的通用递归算法研究与实现

对二叉树先序遍历、中序遍历和后序遍历递归算法进行了分析,给出了三种遍历方法的通用递归算法。该算法只需对二叉树遍历一次,对每个结点的值域（Data）访问三次即可求出三种遍历序列。     

Binary-space-partitioned images for resolving image-based visibility

We propose a novel 2D representation for 3D visibility sorting, the binary-space-partitioned image (BSPI), to accelerate real-time image-based rendering. BSPI is an efficient 2D realization of a 3D BSP tree, which is commonly used in computer graphics for time-critical visibility sorting. Since the overall structure of a BSP tree is encoded in a BSPI, traversing a BSPI is comparable to traversing the corresponding BSP tree. BSPI performs visibility sorting efficiently and accurately in the 2D image space by warping the reference image triangle-by-triangle instead of pixel-by-pixel. Multiple BSPIs can be combined to solve "disocclusion," when an occluded portion of the scene becomes visible at a novel viewpoint. Our method is highly automatic, including a tensor voting preprocessing step that generates candidate image partition lines for BSPIs, filters the noisy input data by rejecting outliers, and interpolates missing information. Our system has been applied to a variety of real data, including stereo, motion, and range images.     

Accelerating Ray Tracing using Constrained Tetrahedralizations

In this paper we introduce the constrained tetrahedralization as a new acceleration structure for ray tracing. A constrained tetrahedralization of a scene is a tetrahedralization that respects the faces of the scene geometry. The closest intersection of a ray with a scene is found by traversing this tetrahedralization along the ray, one tetrahedron at a time. We show that constrained tetrahedralizations are a viable alternative to current acceleration structures, and that they have a number of unique properties that set them apart from other acceleration structures: constrained tetrahedralizations are not hierarchical yet adaptive; the complexity of traversing them is a function of local geometric complexity rather than global geometric complexity; constrained tetrahedralizations support deforming geometry without any effort; and they have the potential to unify several data structures currently used in global illumination.     

关系型数据库中树形数据的组织与算法分析

介绍在关系型数据库中采用孩子表示法、双亲表示法以及双亲孩子表示法存储树形数据，讨论不同存储方法下插入删除结点、树的遍历、树的度和深度的计算算法，井分析这些算法的性能。     

Planar shape matching based on binary tree shape representation

In this paper we suggest a new way of representing planar two-dimensional shapes and a shape matching method which utilizes the new representation. Through merging of the neighboring boundary runs, a shape can be partitioned into a set of triangles. These triangles are inherently connected according to a binary tree structure. Here we use the binary tree with the triangles as its nodes to represent the shape. This representation is found to be insensitive to shape translation, rotation, scaling and skewing changes due to viewer's location changes (or the object's pose changes). Furthermore, the representation is of multiresolution.

In shape matching we compare the two trees representing two given shapes node by node according to the breadth-first tree traversing sequence. The comparison is done from top of the tree and moving downward, which means that we first compare the lower resolution approximations of the two shapes. If the two approximations are different, the comparison stops. Otherwise, it goes on and compares the finer details of the two shapes. Only when the two shapes are very similar, will the two corresponding trees be compared entirely. Thus, the matching algorithm utilizes the multiresolution characteristic of the tree representation and appears to be very efficient.     

Fast reroute from single link and single node failures for IP multicast

The rise in multicast implementations has seen with it an increased support for fast failure recovery from link and node failures. Most recovery mechanisms augment additional services to existing protocols causing excessive overhead, and these modifications are predominantly protocol-specific. In this paper, we develop a multicast failure recovery mechanism that constructs protocol independent fast reroute paths to recover from single link and single node failures. We observe that single link failure recovery in multicast networks is similar to recovering unicast traffic, and we use existing unicast recovery mechanisms for multicast traffic. We construct multicast protection trees that provide instantaneous failure recovery from single node failures. For a given node x, the multicast protection tree spans all its neighbors and does not include itself. Thus, when the node fails, the neighbors of the node are connected through the multicast protection tree instead of node x, and forward the traffic over the multicast protection tree for the duration of failure recovery. The multicast protection trees are constructed a priori, without the knowledge of the multicast traffic in the network. Based on simulations on three realistic network topologies, we observe that the multicast protection trees increase the routing table size only by 38% on average and the path length between any source–destination pair by 13% on average.     

应用于大数据的Trie树排序算法

针对在数据量动态增加的场景下现有的排序算法管理数据导致算法性能大大降低的问题,提出一种16-bit Trie树排序算法.借助邻居节点上存储的链节点指针完成排序,它不仅可以边构建边排序,且引入动态数组可以提高该算法的空间效率.仿真结果表明,传统Trie树支持数据动态更新,但通过遍历Trie树的方式完成排序耗时较多,快速排...     

Proximity clouds — an acceleration technique for 3D grid traversal

In this paper we present a new method for the acceleration of ray traversal through a regular 3D grid. A distance transformation is precomputed and mapped onto the empty grid space. A ray traversing the empty space is assisted by the distance values which permit it to perform long skips along the ray direction. We show that the City-Block metric simplifies the preprocessing with no penalty at the traversal phase. Different schemes are discussed and the trade-off between the preprocessing time and the speed-up is analyzed.     

Ray tracing: A quantitative analysis and a new practical algorithm

We present a new method to accelerate the process of finding nearest ray-object intersections in ray tracing. The algorithm consumes an amount of memory more or less linear in the number of objects. The basic ideas can be characterized with a modified BSP tree and plane traversal. Plane traversal is a fast linear time algorithm to find the closest intersection point in a list of bounding volumes hit by a ray. We use plane traversal at every node of the high outdegree BSP tree. Our implementation is competitive to fast ray-tracing programs. We present a benchmark suite that allows for an extensive comparison of ray-tracing algorithms.     

Solving the subset-sum problem with a light-based device

We propose an optical computational device which uses light rays for solving the subset-sum problem. The device has a graph-like representation and the light is traversing it by following the routes given by the connections between nodes. The nodes are connected by arcs in a special way which lets us to generate all possible subsets of the given set. To each arc we assign either a number from the given set or a predefined constant. When the light is passing through an arc it is delayed by the amount of time indicated by the number placed in that arc. At the destination node we will check if there is a ray whose total delay is equal to the target value of the subset sum problem (plus some constants). The proposed optical solution solves a NP-complete problem in time proportional with the target sum, but requires an exponential amount of energy.     

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

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

程序树的快速定位算法

程序树能够用一定规则的图元以树状结构在屏幕上表达程序,人们可以直接在屏幕上编辑和阅读程序树,并可利用一定的工具生成相应的源程序代码。对于程序树的周流问题,人们一直沿用从树根开始搜索的方法。本文提出了一种从当前节点开始搜索的“相对搜索”的快速定位方法。性能分析表明：该算法优于传统算法。     

二叉树遍历的非递归算法分析与实现

对二叉树的遍历过程进行了深入的分析,根据二叉树三种遍历的内在关系给出了求先序序列、中序序列和后序序列的非递归算法,该算法只需对二叉树遍历一次即可求出三种遍历序列。     

无线传感器网络RaSMaLai算法的改进

针对RaSMaLai算法有可能进入无效循环和无效等待状态的问题,对RaSMaLai进行了两点改进并提出了一种新的随机转换算法NRaSMaLai:改进一在算法初始化过程中遍历树中节点进行初始化检查,防止树进入无效等待状态;改进二在更新树操作过程中对树中最大负载节点及其所有子孙节点时进行状态检测,防止树进入无效循环状态。NRaSMaLai通过增大最小负载节点及其子孙节点的负载使树平衡。仿真实验表明,使用改进一、二的算法能使树达到平衡状态或更接近预设的平衡状态。当sink节点位于区域中心时,NRaSMaLai使树平衡时所需的迭代步数减小为原来的1/5并很少出现振荡,对使数据收集树快速收敛并延长网络寿命具有重要意义。     

Improving Memory Space Efficiency of Kd‐tree for Real‐time Ray Tracing

Compared with its competitors such as the bounding volume hierarchy, a drawback of the kd‐tree structure is that a large number of triangles are repeatedly duplicated during its construction, which often leads to inefficient, large and tall binary trees with high triangle redundancy. In this paper, we propose a space‐efficient kd‐tree representation where, unlike commonly used methods, an inner node is allowed to optionally store a reference to a triangle, so highly redundant triangles in a kd‐tree can be culled from the leaf nodes and moved to the inner nodes. To avoid the construction of ineffective kd‐trees entailing computational inefficiencies due to early, possibly unnecessary, ray‐triangle intersection calculations that now have to be performed in the inner nodes during the kd‐tree traversal, we present heuristic measures for determining when and how to choose triangles for inner nodes during kd‐tree construction. Based on these metrics, we describe how the new form of kd‐tree is constructed and stored compactly using a carefully designed data layout. Our experiments with several example scenes showed that our kd‐tree representation technique significantly reduced the memory requirements for storing the kd‐tree structure, while effectively suppressing the unavoidable frame‐rate degradation observed during ray tracing.     

Fast projection-based ray-casting algorithm for renderingcurvilinear volumes

We present an efficient and robust ray-casting algorithm for directly rendering a curvilinear volume of arbitrarily-shaped cells. By projecting cell-faces onto the image plane, we have effectively addressed three critical steps of the ray-casting process, namely finding the entry cell-faces for a ray, traversing along the ray from one cell to another, and reconstructing data values at the ray/cell-face intersections. Our algorithm significantly reduces rendering time, alleviates memory space consumption, and overcomes the conventional limitation requiring cells to be convex. Application of this algorithm to several commonly used curvilinear data sets has produced a favorable performance when compared with recently reported algorithms