线性复杂度的网格优化划分

均匀网格划分是一种重要的场景空间组织结构,在光线跟踪绘制、碰撞检测、路径规划等方面有着广泛的应用.特别是由于其计算简单,很适合动态环境的处理.由于该结构的创建时间、空间需求和应用效率与网格分辨率密切相关,优化的网格划分一直是国际上探讨的重要问题.对此,提出一种新的优化划分方法,确保该结构的创建时间和空间需求都是O(N)复杂度的.这里,N是场景的面片数.同时,在相关的应用计算方面,比如光线跟踪,可与目前最好的加速计算结构相媲美.实验结果表明,该优化划分方法所产生的层次网格结构具有与当前主流的加速结构kd树相当的加速效率,且大幅降低了创建时间,优于已有的类似工作.     

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

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

基于空间网格细分的不规则场景的光线跟踪

针对不规则场景中光线跟踪算法绘制速度慢的问题,在深入学习和比较近些年的光线跟踪加速算法的基础上,提出了一种改进的网格细分的光线跟踪算法。首先,设置矩形场景包围盒,剔除对场景没有影响的外部光线,进而简化求交运算;其次,采用新方法创建空间网格,该方法可使空间单元数量和存储空间复杂度都限定在一定范围内;最后,对网格进行细分,这一步骤消除了传统空间网格算法忽略部分空白区域对加速效果产生的不良影响, 极大完善了传统空间网格算法。通过实验证明,该方法能有效提高光线在空白空间的穿行速度,不仅提高了时间效率,而且减少了空间开销。     

基于中介面加快光线跟踪计算

提出一种新的光线跟踪方法,以提高光线找到相交面片的效率.它在场景中生成一些面积较大的规整中介面片,然后为中介面上的每个点建立一个场,以记录到达该点的不同方向的光线将相交的面片.由此,光线跟踪时,一条光线可方便地找到相交的中介面,并通过查找中介面上所记录的内容,就能得到它所相交的面片.与已有方法相比,新方法不仅能很好加速主光线与阴影光线的计算,而且能很好地加速反射、折射等二次光线的计算.它能在GPU上方便地实现,并能有效地处理动态场景.     

并行光线跟踪中的数据划分策略

提出了一种新的场景数据分割方法,以待计算的象素点来决定场景数据的有效分割,克服了以往盲目分割数据所带来的光线在处理机间的频繁交换,从而减小了通信开销。     

基于光线跟踪方法的全局光照研究

光线跟踪方法是解决全局光照问题的一种重要方法。概括性地提出光线跟踪方法研究的基本任务是研究关于采样、加速求交的问题,并综述性地分析了光线跟踪相关算法。介绍了该领域近期研究热点即实时光线跟踪以及基于图形硬件的光线跟踪的相关研究工作,指出了光线跟踪方法在解决全局光照问题时的优缺点以及未来的研究重点。展望了基于光线跟踪方法的全局光照应用前景。     

基于OpenCL的实时KD-Tree与动态场景光线跟踪

目前,基于GPU或多核CPU加速的光线跟踪算法是与硬件相关的.研究具有跨平台性能的实时光线跟踪算法既具有挑战性,又具有很强的应用价值.为此,提出一种基于OpenCL并且跨平台的动态场景实时光线跟踪绘制算法.首先通过对通用GPU并行处理性能进行发掘,将光线跟踪中KD-Tree建立、场景遍历和绘制3个过程均设计在GPU上,而CPU只负责其中各过程的调度,从而充分利用了GPU的计算性能,并有效地降低了数据传输开销;通过设计并行分区、并行SAH、紧密的数据管理以及区间性叶结点存储等算法,在GPU中高效、高质量地建立动态场景的KD-Tree,同时高质量的KD-Tree也有效地加速了场景的遍历速度.该算法以广度优先和大规模并行模式建立K D-Tree,更具通用性,既可以运行于NVIDIA GPU(CUDA GPU),也可以运行于AMD GPU.实验结果表明,文中算法可以在NVIDIA GPU和AMD GPU上对中等规模的动态场景实现实时光线跟踪绘制.     

裁剪后二次曲面的光线跟踪

提出了一个对裁剪后二次曲面进行光线跟踪的新方法。在该方法中引进了一个易于由世界坐标求参数的辅助参数空间，通过预处理，事先将原参数域下的边界变换到新的参数空间。这样，光线与曲面的求交仍可按二次曲面的几何参数进行，求出交点后，再将交点变换到辅助参数空间，在新的参数域中判断交点是否在裁剪过的曲面上。     

一种用于光线与三角形网格求交运算的有效剔除算法

提出一种用于光线与三角形网格求交运算中的有效剔除算法.算法中,一根光线被定义为两个非平行平面的交线.针对由稠密三角形网格组成的复杂场景,算法通过三角形和测试平面的相交判断剔除与投射光线不相交的绝大多数三角面片.利用该算法,光线跟踪中主光线在图像空间的相关性可以方便、直观地被利用.为了利用物体在景物空间的相关性,算法可以结合层次包围盒、八叉树等常见的场景划分方法.而且,该算法可以方便地扩展应用于一般多边形网格.     

光线跟踪程序PBRT的并行化及性能优化

随着多核处理器的出现和迅速发展,将以前经典的串行程序并行化,更好地利用多核体系结构提高其性能,成为了当前多核处理器应用研究值得关注的-个问题.以并行化光线跟踪程序PBRT为例,深入研究了串行程序并行化中的并行模型的设计与实现、正确性验证,以及并行化后的性能优化等问题.优化后的并行PBRT取得了4个线程时近3.5倍的加速比,证明了所给出的并行化及性能优化有良好的效果.     

State of the Art in Ray Tracing Animated Scenes

Ray tracing has long been a method of choice for off-line rendering, but traditionally was too slow for interactive use. With faster hardware and algorithmic improvements this has recently changed, and real-time ray tracing is finally within reach. However, real-time capability also opens up new problems that do not exist in an off-line environment. In particular real-time ray tracing offers the opportunity to interactively ray trace moving/animated scene content.
This presents a challenge to the data structures that have been developed for ray tracing over the past few decades. Spatial data structures crucial for fast ray tracing must be rebuilt or updated as the scene changes, and this can become a bottleneck for the speed of ray tracing. This bottleneck has recently received much attention by researchers and that has resulted in a multitude of different algorithms, data structures and strategies for handling animated scenes. The effectiveness of techniques for ray tracing dynamic scenes vary dramatically depending on details such as scene complexity, model structure, type of motion and the coherency of the rays. Consequently, there is so far no approach that is best in all cases, and determining the best technique for a particular problem can be a challenge. In this State of the Art Report (STAR), we aim to survey the different approaches to ray tracing animated scenes, discussing their strengths and weaknesses, and their relationship to other approaches. The overall goal is to help the reader choose the best approach depending on the situation, and to expose promising areas where there is potential for algorithmic improvements.     

Priority-driven Ray Tracing

A typical ray tracing algorithm traces a ray through each screen-pixel and spawns secondary rays at ray–object intersection points. Unlike traditional ray tracers which follow these rays recursively, we assign a priority value to each newly spawned ray and insert it into a priority queue. The priority assigned to each ray can be based on a variety of criteria, some of which we explore here. The next ray we trace is always the one with the highest priority in the queue. Occasionally, we trigger display updates when a checkpoint or predefined threshold is reached, providing intermediate images for review and evaluation. Classical ray tracers, once given the rendering specifications, are not controllable by the user. The priority-driven ray tracing, on the other hand, provides the user with a mechanism to steer the rendering and deliver intermediate images amid processing. This paper describes the illumination model of the non-recursive priority-driven ray tracer and evaluates its memory and time requirements. We show that although worst-case memory requirements can be overwhelming, in practice, our method is both useful and feasible. © 1997 by John Wiley & Sons, Ltd.     

光线追踪的OpenCL加速实现研究

目前GPU计算能力让kD-Tree划分实时场景光线追踪并行算法的执行变得更具有可行性。图像处理器(GPU)高效应用于多边形的渲染,GPU内部单元的可编程性已经让其广泛应用于多边形渲染以外的领域。本文详细描述使用OpenCL的kD-Tree遍历算法,对运算占主要部分的相交测试作出改进,同时提高了GPU计算能力与存储器的利用率,从而提升了光线追踪算法效率。     

Ray Tracing with Extended Cameras

This paper discusses an extended camera model for ray tracing. As an alternative to standard camera modules an abstract camera machine is presented. It represents a framework of extended cameras which is based on standard mapping functions. They are integrated within the abstract camera machine to complete the camera function, which generates rays out of image locations (pixels). Modelling the camera function as an abstract camera machine in combination with standard mapping functions opens a wide field of applications and the specification of extended cameras is greatly simplified. By using extended cameras it is easily possible to produce special and artistic effects, e.g. a local non-linear zoom of especially interesting regions while still retaining an overview of the whole scene. Overviews of given scenes can be modelled and several views of the same object can be integrated into one picture. Several examples of extended cameras designed with the abstract camera machine are discussed and colour plates made with these cameras are presented.     

An Efficient Algorithm for Ray Tracing

This paper presents a new algorithm that performs more efficient ray tracing compared to existing algorithms. This algorithm is based on the divide-and-conquer technique well known from the area of lists sorting, and speeds up the intersections and light-visibility tests for the first hit. A new definition of transitive-between-relations (TBR) is introduced. A simple shooting ray guide is embedded into a conventional ray tracer to reduce the number of intersection tests and thus speed-up the first hit calculation and the associated light conditions tests. The algorithm was tested in environments made up of convex polygons (random triangles, linearly positioned pyramids) but it can be used in environments with other primitives.     

点模型的局部几何重建和光线跟踪

在每个点附近重建一个二次多项式函数曲面逼近原点模型,并根据逼近误差将每个重建曲面限制在称为ε置信邻域的范围内,从而形成一个ε面元.这些面元逼近原点模型表面,而且误差处处小于ε,可用于计算光线和点模型的交点.实验结果表明,文中算法速度快、逼近程度好、绘制质量高,能够自适应不同采样密度的模型.     

A 4D Ray Tracing

We are going to present a survey of techniques using temporal coherence in between frames to render animation sequences with ray tracing. A new method using temporal coherence in the ray space (lightpath of rays) is proposed. The goal of this technique is to factorize intersection and illumination calculations over the frames of the sequence. An optical event springing out many times in the sequence is computed once. The method is based upon 4D intersection calculations between temporal rays and moving objects. At the end of this paper, we present measurements showing the number of rays we need not calculate with our solution. These results come from simulating the algorithm behavior through a graphic and statistic ray analyser tool.     

非线性折射和反射平面场景的实时光线跟踪

该文利用光学映射虚对象的概念,提出了实时计算平面折射虚物体的新方法,给出了在不同情况下实时计算平面折射虚顶点的计算公式,实现了基于三维图形硬件（加速卡）加速的实时光线跟踪算法。该算法能够处理非线性平面折射和反射问题,极大地提高了真实感图形绘制和显示的速度。这对于建筑物实时漫游、实时动画和虚拟现实等领域具有非常广阔的应用前景。