基于动态任务调度的层次包围盒构建算法

交点计算是光线跟踪算法中开销最大的部分,层次包围盒(BVH)则是主流加速结构.为了提高BVH的构建速度,提出一种基于动态任务调度和warp线程优化的BVH构建算法,并针对目前主流GPU架构特点进行优化.该算法根据表面积启发式(SAH)值对BVH进行自底向上多轮优化;在每次循环的开始阶段判断当前线程是否空闲,若空闲,则根据记录任务进度的全局变量进行任务分配,否则,继续遍历BVH;当遍历到符合条件的节点时以该节点为幼树根节点进行幼树重构,这一阶段使用同一warp中的32个线程协同进行幼树重构,并且可以依据幼树叶子节点数调整同时处理的幼树个数.对经典的三维场景进行实验的结果表明,在BVH构建质量相同的情况下,当场景中三角元片数超过10万时,BVH构建速度会得到提升;当三角元片数大于100万时,该算法比聚类幼树重构层次包围盒(Atr BVH)算法在BVH优化阶段速度提升47%,从而使整个构建速度提高25%.     

TDTMS:一种面向XML数据的结果子树构建算法

构建结果子树是XML关键字查询得以完成的关键步骤之一.针对已有方法求解子树效率低的问题,文中提出一种自顶向下的子树构建算法——TDTMS.TDTMS以自顶向下、深度优先的方式求解满足条件的子树根结点,避免了已有方法求解SLCA结点时存在的公共祖先重复处理问题.对于给定的子树根结点,TDTMS以自顶向下、广度优先的方式构建子树,可以在建树过程中快速裁剪无用结点,从而获得了最小的时间和空间复杂度.最后通过实验验证了TDTMS在时间和空间两方面的性能优势.     

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

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

采用Intel集成众核架构的并行光线追踪加速方法

针对真实感渲染光线追踪流程中光线和场景求交计算量大、渲染速度慢的问题,提出一种基于Intel集成众核架构的并行光线追踪加速方法.在场景预处理阶段,首先构建四分支场景加速结构,以适应于MIC的硬件架构.在光线追踪阶段,首先通过CPU主核控制光线追踪整体流程,该主核采用多线程调度优化策略,调度MIC从核进行光线和场景树的求交操作,实现CPU和MIC的异步数据传输,充分利用主从核的计算能力;在MIC从核的光线和场景树求交过程中提出一种并行求交算法,充分利用MIC宽SIMD处理单元,实现光线和场景树4个结点并行求交的向量化操作,以加速求交过程.实验结果表明,与CPU原生模式相比,文中方法在光线求交阶段可达到2~4倍的加速效果,整体光线追踪流程渲染速度亦得到显著提升.     

基于指针网络的汉语宏观篇章结构双向解析方法

宏观篇章结构解析旨在通过分析篇章的整体结构,为理解篇章的内容和主旨奠定基础。现有的研究大都采用了单一的自顶向下或自底向上的构建策略逐级地构建结构树,而单向构建策略无法根据不同待解析序列选择合适的解析动作,在解析流程中容易陷入决策局限性并将错误向后传播。该文提出一种集成自顶向下和自底向上两种构建策略的指针网络模型,该模型能同时利用两种构建策略的语义信息,从而选择合适的构建方式。在汉语宏观篇章树库(MCDTB 2.0)上的实验表明,通过集成两种构建方式,该文模型能有效提升篇章单元间的局部语义交互能力并减少构建过程中的错误传播,从而取得性能最优值。     

实时光线追踪相关研究综述

光线追踪因其渲染效果的真实性,长期以来被视为下一代主流图像渲染技术,是计算机图形学领域的热点研究方向。近年来,学术界和商业界对实时光线追踪开展了广泛研究。为促进实时光线追踪的研究,对相关文献进行归纳、分析和总结。首先阐述了光线追踪的概念、算法、加速数据结构等理论知识;介绍了三款支持光线追踪商用图形处理器（GPU）,并对比了之间的差异;从光线束遍历、无栈遍历、光线重排序、多分支BVH、降噪技术、与神经网络结合的实时光线追踪这六个方法综述了光线追踪的算法优化工作,并阐明了相关具体方法的优缺点;在算法加速的基础上,对使用GPU优化加速和采用定制化设计的硬件加速进行了归纳分析;最后对文章的内容进行了总结,指出了实时光线追踪仍面临的困难,并对未来的发展方向进行了展望。可以帮助研究人员系统地了解实时光线追踪的研究现状,为后续开展相关研究提供思路。     

基于混合数据结构的实时GPU光线跟踪算法

研究真实感图像的问题,光线跟踪算法是生成真实感图形的主要算法之一.为了解决光线跟踪算法计算量大、效率低下、对动态场景处理能力不足的问题,采用图形处理器(graphics processing unit,GPU)统一编程架构,提出了一种新的基于计算统一设备架构(Compute Unified Device Architecture,CUDA)编程模型的结合层次包围体(Bounding Volume Hierarchies,BVH)和kd-tree的光线跟踪方法,首先对场景进行启发式的层次包围体分割,随后在每一个层次包围体上做启发式的k维二叉树(k-dimensional tree,kd-tree)剖分,这样就形成了一种新的空间划分,有利于建立高效的空间数据结构,提高光线与场景物体的求交速度.新设计的算法易于扩展到动态场景的光线跟踪,而且具有更快的渲染速度,有利于在应用系统中集成和扩展.实验结果验证了算法的有效性.     

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

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

基于OpenGL的三维人体运动模型实现

虚拟人物造型及人体骨骼动画是虚拟现实技术中一大难点.OpenGL是目前广泛流行的一种三雏图形编程接口,在传统方法中,利用OpenGL对人体动画进行模拟时,由于OpenGL是基于顶点坐标和面片的操作,需要保存动画中每一个关键帧的顶点及面片信息,所以通常要进行大量的计算.而BVH格式的文件提供了关于人体关节的运动信息,这将大大减少动画的计算量.提出了一种基于BVH文件格式的模型实现人体动画的技术,并给出了实验结果.     

运动捕捉数据在Jack平台上的重定向技术研究

提出了一种BVH格式运动捕捉数据驱动Jack三维骨架模型产生人体运动效果的方法。将Peabody结构的Jack虚拟人模型简化成能够映射BVH数据的树状骨骼结构,使用欧拉角旋转方程建立运动捕捉数据与Jack角色模型的关节数据映射公式,最后在Jack平台上用Python等脚语言进行了编程实现。为在Jack平台中大规模重用运动捕捉数据提供了条件。     

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.     

Efficient BVH‐based Collision Detection Scheme with Ordering and Restructuring

Bounding volume hierarchy (BVH) has been widely adopted as the acceleration structure in broad‐phase collision detection. Previous state‐of‐the‐art BVH‐based collision detection approaches exploited the spatio‐temporal coherence of simulations by maintaining a bounding volume test tree (BVTT) front. A major drawback of these algorithms is that large deformations in the scenes decrease culling efficiency and slow down collision queries. Moreover, for front‐based methods, the inefficient caching on GPU caused by the arbitrary layout of BVH and BVTT front nodes becomes a critical performance issue. We present a fast and robust BVH‐based collision detection scheme on GPU that addresses the above problems by ordering and restructuring BVHs and BVTT fronts. Our techniques are based on the use of histogram sort and an auxiliary structure BVTT front log, through which we analyze the dynamic status of BVTT front and BVH quality. Our approach efficiently handles inter‐ and intra‐object collisions and performs especially well in simulations where there is considerable spatio‐temporal coherence. The benchmark results demonstrate that our approach is significantly faster than the previous BVH‐based method, and also outperforms other state‐of‐the‐art spatial subdivision schemes in terms of speed.     

The Use of Precomputed Triangle Clusters for Accelerated Ray Tracing in Dynamic Scenes

In this paper we present a hybrid algorithm for building the bounding volume hierarchy (BVH) that is used in accelerating ray tracing of animated models. This algorithm precomputes densely packed clusters of triangles on surfaces. Folowing that, a set of clusters is used to rebuild the BVH in every frame. Our approach utilizes the assumption that groups of connected triangles remain connected throughout the course of the animation. We introduce a novel heuristic to create triangle clusters that are designed for high performance ray tracing. This heuristic combines the density of connectivity, geometric size and the shape of the cluster.
Our approach accelerates the BVH builder by an order of magnitude rebuilding only the set of clusters that is much smaller than the original set of triangles. The speed-up is achieved against a 'brute-force' BVH builder that repartitions all triangles in every frame of animation without using any pre-clustering. The rendering performance is not affected when a cluster contains a few dozen triangles. We demonstrate the real-time/interactive ray tracing performance for highly-dynamic complex models.     

Grid-based SAH BVH construction on a GPU

We present an efficient algorithm for building an adaptive bounding volume hierarchy (BVH) in linear time on commodity graphics hardware using CUDA. BVHs are widely used as an acceleration data structure to quickly ray trace animated polygonal scenes. We accelerate the construction process with auxiliary grids that help us build high quality BVHs with SAH in O(k?n). We partition scene triangles and build a temporary grid structure only once. We also handle non-uniformly tessellated and long/thin triangles that we split into several triangle references with tight bounding box approximations. We make no assumptions on the type of geometry or animation motion. However, our algorithm takes advantage of coherent geometry layout and coherent frame-by-frame motion. We demonstrate the performance and quality of resulting BVHs that are built quickly with good spatial partitioning.     

Real‐time cutting simulation of meshless deformable object using dynamic bounding volume hierarchy

This paper proposes a novel method for a real‐time cutting simulation of deformable objects using meshless method. The method utilizes a rapid refinement of topological relations among the simulation nodes of meshless deformable objects. Topological relations are defined as an undirected graph based on a visibility criterion. The graph connects the adjacent nodes that lie within a support of each node. The topological relations are refined by removing the edges of the graph that is intersected by the cut surface during the cutting simulation. Our approach utilizes a bounding volume hierarchy (BVH) to accelerate the computation of the intersection test. The BVH reconstruction algorithm is proposed to account for the cases where pieces of the object are completely cut out from the object. Algorithms to examine the connectivity among simulation nodes and accordingly reconstructing the BVH using two‐level BVH are presented. The proposed approach achieves real‐time cutting simulation of deformable objects through the rapid refinement of the topological relation. In addition, the computational performance of the cutting procedure is preserved during the entire simulation, thanks to the real‐time reconstruction of the BVH. Copyright © 2012 John Wiley & Sons, Ltd.     

Parallel BVH Construction using Progressive Hierarchical Refinement

We propose a novel algorithm for construction of bounding volume hierarchies (BVHs) for multi‐core CPU architectures. The algorithm constructs the BVH by a divisive top‐down approach using a progressively refined cut of an existing auxiliary BVH. We propose a new strategy for refining the cut that significantly reduces the workload of individual steps of BVH construction. Additionally, we propose a new method for integrating spatial splits into the BVH construction algorithm. The auxiliary BVH is constructed using a very fast method such as LBVH based on Morton codes. We show that the method provides a very good trade‐off between the build time and ray tracing performance. We evaluated the method within the Embree ray tracing framework and show that it compares favorably with the Embree BVH builders regarding build time while maintaining comparable ray tracing speed.     

Dual graph partitioning for Bottom-Up BVH construction

Bounding Volume Hierarchies (BVHs) are essential tools in performing collision detection on three-dimensional information. They reduce the number of expensive calculations required to determine whether or not two geometrical entities collide by using inexpensive calculations to rule out parts of the objects that could not possibly intersect. Quickly producing a high quality BVH is an important aspect of three-dimensional multimedia analysis. As such a powerful optimization, efficient and high quality BVHs are still an active area of research. Herein, the authors present a novel BVH representation that reduces the redundancy in the tree structure by allowing a node to contain an arbitrary number of children, as well as compressing non-unique nodes and combining their children. A new partitioning scheme using a graphical representation of the object is also presented to improve the quality of the generated BVH.     

Compact,Fast and Robust Grids for Ray Tracing

The focus of research in acceleration structures for ray tracing recently shifted from render time to time to image, the sum of build time and render time, and also the memory footprint of acceleration structures now receives more attention. In this paper we revisit the grid acceleration structure in this setting. We present two efficient methods for representing and building a grid. The compact grid method consists of a static data structure for representing a grid with minimal memory requirements, more specifically exactly one index per grid cell and exactly one index per object reference, and an algorithm for building that data structure in linear time. The hashed grid method reduces memory requirements even further, by using perfect hashing based on row displacement compression. We show that these methods are more efficient in both time and space than traditional methods based on linked lists and dynamic arrays. We also present a more robust grid traversal algorithm. We show that, for applications where time to image or memory usage is important, such as interactive ray tracing and rendering large models, the grid acceleration structure is an attractive alternative.     

Fitted BVH for Fast Raytracing of Metaballs

Raytracing metaballs is a problem that has numerous applications in the rendering of dynamic soft objects such as fluids. However, current techniques are either limited in the visual effects that they can render or their performance drops as the number of metaballs and their density increase. We present a new acceleration structure based on BVH and kd‐tree for efficient raytracing of a large number of metaballs. This structure is built from an adapted SAH using a fast greedy algorithm and allows the visualization of several hundreds of thousands metaballs at interactive‐to‐real‐time framerates. Our method can handle arbitrary rays to simulate any complex secondary effects such as reflections or soft shadows, and is robust with respect to the density of metaballs. We achieve this performance thanks to a balanced CPU‐GPU (using CUDA) implementation of the animation, structure creation, and rendering.     

An Analysis of Region Clustered BVH Volume Rendering on GPU

We present a Direct Volume Rendering method that makes use of newly available Nvidia graphics hardware for Bounding Volume Hierarchies. Using BVHs for DVR has been overlooked in recent research due to build times potentially impeding interactive rates. We indicate that this is not necessarily the case, especially when a clustering algorithm is applied before the BVH build to reduce leaf‐node complexity. Our results show substantial render time improvements for full‐resolution DVR on GPU in comparison to a recent state‐of‐the‐art approach for empty‐space‐skipping. Furthermore, the use of a BVH for DVR allows seamless integration into popular surface‐based path‐tracing technologies like Nvidia's OptiX.