Constrained Convex Space Partition for Ray Tracing in Architectural Environments

This paper explores constrained convex space partition (CCSP) as a new acceleration structure for ray tracing. A CCSP is a graph, representing a space partition made up of empty convex volumes. The scene geometry is located on the boundary of the convex volumes. Therefore, each empty volume is bounded with two kinds of faces: occlusive ones (belonging to the scene geometry), and non‐occlusive ones. Given a ray, ray casting is performed by traversing the CCSP one volume at a time, until it hits the scene geometry. In this paper, this idea is applied to architectural scenes. We show that CCSP allows to cast several hundreds of millions of rays per second, even if they are not spatially coherent. Experiments are performed for large furnished buildings made up of hundreds of millions of polygons and containing thousands of light sources.     

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.     

Fast ray-tracing of rectilinear volume data using distancetransforms

The paper discusses and experimentally compares distance based acceleration algorithms for ray tracing of volumetric data with an emphasis on the Chessboard Distance (CD) voxel traversal. The acceleration of this class of algorithms is achieved by skipping empty macro regions, which are defined for each background voxel of the volume. Background voxels are labeled in a preprocessing phase by a value, defining the macro region size, which is equal to the voxel distance to the nearest foreground voxel. The CD algorithm exploits the chessboard distance and defines the ray as a nonuniform sequence of samples positioned at voxel faces. This feature assures that no foreground voxels are missed during the scene traversal. Further, due to parallelepipedal shape of the macro region, it supports accelerated visualization of cubic, regular, and rectilinear grids. The CD algorithm is suitable for all modifications of the ray tracing/ray casting techniques being used in volume visualization and volume graphics. However, when used for rendering based on local surface interpolation, it also enables fast search of intersections between rays and the interpolated surface, further improving speed of the process     

Multi‐layer Depth Peeling by Single‐Pass Rasterisation for Faster Isosurface Raytracing on GPUs

Empty‐space skipping is an essential acceleration technique for volume rendering. Image‐order empty‐space skipping is not well suited to GPU implementation, since it must perform checks on, essentially, a per‐sample basis, as in kd‐tree traversal, which can lead to a great deal of divergent branching at runtime, which is very expensive in a modern GPU pipeline. In contrast, object‐order empty‐space skipping is extremely fast on a GPU and has negligible overheads compared with approaches without empty‐space skipping, since it employs the hardware unit for rasterisation. However, previous object‐order algorithms have been able to skip only exterior empty space and not the interior empty space that lies inside or between volume objects. In this paper, we address these issues by proposing a multi‐layer depth‐peeling approach that can obtain all of the depth layers of the tight‐fitting bounding geometry of the isosurface by a single rasterising pass. The maximum count of layers peeled by our approach can be up to thousands, while maintaining 32‐bit float‐point accuracy, which was not possible previously. By raytracing only the valid ray segments between each consecutive pair of depth layers, we can skip both the interior and exterior empty space efficiently. In comparisons with 3 state‐of‐the‐art GPU isosurface rendering algorithms, this technique achieved much faster rendering across a variety of data sets.     

基于打包索引纹理的大规模数据体绘制算法

针对大规模数据体绘制效率低下的问题,提出一种算法：对体数据进行纹理分块打包,移除空数据块,并创建数据块的索引数据,绘制时通过索引访问打包后的纹理实现大规模数据完全载入显存,同时在索引中标记空数据及高密度数据块的位置,绘制前生成其有效的立方体数据表达,结合早期光线终止与空域跳过等加速技术,有效地实现了大规模的体数据的实时绘制,同时保证了结果图像的质量。     

The same origin ray set query for realistic illumination: Algorithm and analysis

The same origin ray set (SORS) is a computational primitive which can be used by ray tracing, radiosity and multiple pass illumination simulation algorithms for realistic image synthesis. A SORS consists of a set of rays emanating from the same point in space. The SORS query computes the first object intersected by each ray and the intersection point. In this paper we present an efficient projection algorithm for computing a SORS query for polygonal scenes. The algorithm achieves its efficiency by separating ray-polygon intersection detection from the computation of the intersection point between the ray and the polygon's plane. The algorithm can be integrated with all current illumination acceleration schemes. We analyse the projection algorithm and compare it to the alternative of computing the SORS query one ray at a time. The analysis' results are expressed in terms of a few intuitive parameters, measuring the success of the acceleration scheme in culling irrelevant objects and the concentration of the ray set. The projection algorithm can be up to five times more efficient, depending on these parameters and the quality of the image. The relative advantage of the projection increases with image quality.     

A distance template for octree traversal in CPU-based volume ray casting

Several optimization techniques have been proposed to improve the speed of direct volume rendering. A hierarchical representation formed by an octree is a data structure to skip over transparent regions while requiring little preprocessing and data storage. However, in order to skip over an octant estimated to be transparent (a transparent octant), the distance from a boundary to another boundary of the octant should be calculated. Because the distance computation is expensive, we propose a precomputed data structure, the distance template, which stores direction and distance values from one boundary voxel on a face to all the boundary voxels on the remaining five faces. In the rendering step, if a ray reaches a transparent octant, it leaps over the octant by referring to the stored distance value.     

空间跳跃加速的GPU光线投射算法

光线投射算法是一种应用广泛的体绘制基本算法,能产生高质量的图像,但是时间复杂度较高。实现了一种基于图形处理器的单步光线投射算法,并在此基础上提出了一种基于空间跳跃技术的光线投射算法,以实现加速。采用八叉树组织体数据,利用空间跳跃有效地剔除体数据中对重建图像无贡献的部分,降低了硬件的负载。一个片段程序即可完成光线方向的生成、光线投射、空体素跳跃和光线终止等。实验结果表明,该算法对于内部包含大量空体素的体数据重建能起到明显的加速作用。     

Acceleration of direct volume rendering with programmable graphics hardware

We propose a method to accelerate direct volume rendering using programmable graphics hardware (GPU). In the method, texture slices are grouped together to form a texture slab. Rendering non-empty slabs from front to back viewing order generates the resultant image. Considering each pixel of the image as a ray, slab silhouette maps (SSMs) are used to skip empty spaces along the ray direction per pixel basis. Additionally, SSMs contain terminated ray information. The method relies on hardware z-occlusion culling and hardware occlusion queries to accelerate ray traversals. The advantage of this method is that SSMs are created on the fly by the GPU without any pre-processing. The cost of generating the acceleration structure is very small with respect to the total rendering time.     

基于像素模型的CT仿真投影快速计算

提高仿真投影的计算速度一直是CT仿真技术的重要研究内容。针对像素模型的投影计算,提出了一种快速仿真投影生成算法。首先确定射线与像素模型边界相交的起始像素索引及纵向距离,然后通过该纵向距离依次计算射线穿过的像素索引及相交长度,同时累加出投影数据。实验结果表明,该算法大大提高了投影计算速度,与Siddon算法相比取得了约7倍的加速比;图像重建结果也证明了该算法的正确性。     

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

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

基于空盒自适应生成的动态场景光线跟踪计算

提出了一项光线跟踪新技术,能有效提高光线在空白区域的行进速度.该技术首先用一种新方法创建均匀空间网格,然后用较少的空盒自适应聚集空的空间网格,以加快光线跟踪的计算.新加速结构的创建时间复杂度和空间复杂度均是O(n),而相应的光线跟踪计算的时间复杂度为O(logn),与kd树结构相当.当该结构与已有的一些加速结构结合后,能很好地处理大规模动态场景.比如,光线逐根跟踪且计算二次衍生光线时,新技术可在普通PC机上高真实感地交互绘制包含6G三角面片的多Buddha动态场景.     

Spacetime ray tracing for animation

Techniques for the efficient ray tracing of animated scenes are presented. They are based on two central concepts: spacetime ray tracing, and a hybrid adaptive space subdivision/boundary volume technique for generating efficient, nonoverlapping hierarchies of bounding volumes. In spacetime ray tracing, static objects are rendered in 4-D space-time using 4-D analogs to 3-D techniques. The bounding volume hierarchy combines elements of adaptive space subdivision and bounding volume techniques. The quality of hierarchy and its nonoverlapping character make it an improvement over previous algorithms, because both attributes reduce the number of ray/object intersections that must be computed. These savings are amplified in animation because of the much higher cost of computing ray/object intersections for motion-blurred animation. It is shown that it is possible to ray trace large animations more quickly with space-time ray tracing using this hierarchy than with straightforward frame-by-frame rendering     

GPU Ray Tracing using Irregular Grids

We present a spatial index structure to accelerate ray tracing on GPUs. It is a flat, non‐hierarchical spatial subdivision of the scene into axis aligned cells of varying size. In order to construct it, we first nest an octree into each cell of a uniform grid. We then apply two optimization passes to increase ray traversal performance: First, we reduce the expected cost for ray traversal by merging cells together. This adapts the structure to complex primitive distributions, solving the “teapot in a stadium” problem. Second, we decouple the cell boundaries used during traversal for rays entering and exiting a given cell. This allows us to extend the exiting boundaries over adjacent cells that are either empty or do not contain additional primitives. Now, exiting rays can skip empty space and avoid repeating intersection tests. Finally, we demonstrate that in addition to the fast ray traversal performance, the structure can be rebuilt efficiently in parallel, allowing for ray tracing dynamic scenes.     

流形距离与压缩感知核稀疏投影的局部线性嵌入算法

流形学习算法的目的是发现嵌入在高维数据空间中的低维表示,现有的流形学习算法对邻域参数k和噪声比较敏感。针对此问题,文中提出一种流形距离与压缩感知核稀疏投影的局部线性嵌入算法,其核心思想是集成局部线性嵌入算法对高维流形结构数据的降维有效性与压缩感知核稀疏投影的强鉴别性,以实现高效有降噪流形学习。首先,在选择各样本点的近邻域时,采用流形距离代替欧氏距离度量数据间相似度的方法,创建能够正确反映流形内部结构的邻域图,解决以欧氏距离作为相似性度量时对邻域参数的敏感。其次,利用压缩感知核稀疏投影作为从高维观测空间到低维嵌入空间的映射,增强算法的鉴别性。最后,利用Matlab工具对实验数据集进行仿真,进一步验证所提算法的有效性。     

ART算法快速图像重建研究

讨论了影响ART(Algebraic Reconstruction Technique)算法重建速度和重建质量的主要因素,包括投影数据访问方式、松弛因子和投影系数等。针对投影系数的计算占绝大部分重建时间,成为制约ART算法的瓶颈,提出了一种快速、实时的投影系数计算方法。该方法通过一个距离参数来确定与射线相交的网格编号并计算出相交长度,距离参数采用增量计算,极大地节省了时间。实验结果表明该文提出的方法非常有效,与Siddon算法相比,在保证图像质量不受损失的前提下取得了6倍以上的重建加速比。     

Galerkin-Runge-Kutta methods and hyperbolic initial boundary value problems

Inhomogeneous but time-homogeneous linear hyperbolic initial boundary value problems are solved using Galerkin procedures for the space discretization and Runge-Kutta methods for the time discretization. The space discretized system is not transformed a-priori in a linear system of first order. For the difference of the Ritz projection of the exact solution and the numerical approximation error estimates are derived under the assumption that the applied Runge-Kutta methods have a non-empty interval of absolute stability. It is shown that this class of schemes is not empty in the present case of second order systems, too.     

一个新的体绘制加速算法

针对目前加速方式与传递函数交互设定需求的矛盾,提出了一个新的基于边缘切除原理的体绘制加速算法。算法针对两个关键难点:如何消除传递函数调整依赖性,如何识别空体素,提出了有效的绝对空体素识别准则,设计了高效的边缘空体素分离机制,构成了不依赖传递函数调整的加速模式。在保持高的图像质量的前提下,边缘切除算法具有显著的绘制速度提升。边缘切除过程在预处理阶段进行,算法参数易于选取和推广,具有广泛的适应性,非常适合需要交互设定传递函数的普及型医学图像分析系统应用。算法采用了规则的边缘切除方式,收缩后的体数据非常方便后续光线投射或溅射算法应用,可以方便地与其他各种加速方式组合使用,使不同角度的加速效果实现叠加,是当前各种主流加速技术的一个很好的互补技术。不同背景的运算实例,测试和验证了算法的有效性。