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

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

基于CUDA的光线追踪优化算法研究与实现

在三维场景仿真过程中,为了实现真实的光影效果,通常采用光线追踪法对场景进行渲染。光线追踪算法的核心过程是光线与场景中的片元进行相交测试,而对于一个复杂的场景,该过程计算量非常大。为了改善光线追踪算法的计算速度问题,实现一种基于CUDA(Compute Unified Device Architecture)的光线追踪算法。该算法利用GPU的并行处理能力同时结合KD-Tree加速相交测试过程,最终提高仿真场景的渲染速度。通过实验表明,该算法的KD-Tree创建性能相比传统方法提升约20%,光线追踪性能提升约6倍。     

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

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

一种基于八叉树空间剖分技术的光线跟踪算法

光线跟踪算法是生成真实感图形的主要算法之一。为了提高光线追踪速度,在研究和比较各种光线跟踪算法的基础上,提出了一种基于八叉树数据结构的光线追踪算法。并结合基于重心坐标系的快速求交算法来提高光线跟踪的求交效率,使用重心坐标来表示包含三角形面片的参数平面,不用像三角形顶点一样需要长期存储,能够快速判定光线与三角形是否相交并计算出交点。实验结果表明,该算法能够在保证图像质量的同时提高绘制速度。     

基于高光线模型消除三角形网格局部不规则区域

高光线是检测自由曲面质量的有效工具.它提供一种直观且便利的手段,在交互设计中提高自由曲面质量.文中提出了在任意三角形网格曲面上生成高光线模型的一种方法.基于该高光线模型,文中给出了一种消除三角形网格上的局部不规则区域的方法.该方法通过求解一个目标函数,并迭代地移动网格顶点位置,来获得修改后的新网格.利用该方法能够同时优化三角形网格表面形状以及网格上的高光线形状.该方法直观易用,适合于三角形网格的局部形状优化.     

基于逆向光线跟踪与图像绘制的运动水面反射场景绘制

提出了一种结合图像绘制和逆向光线跟踪的绘制算法来生成水面反射场景。首先,采用逆向光线跟踪方法获得视点所见水面反射场景点;然后在反射光线与场景相交点求解时,采用场景图像平面搜索,并将搜索到的图像平面象素点反向投影到观察坐标系求取光线与场景物体相交点以获取反射物颜色;最后按照Fresnel公式计算获得视点所见的水面上某点的颜色,通过对整个图像平面进行遍历,获得水面反射场景。使用该方法绘制的水面反射场景能够物理真实地模拟水面反射效果。对于波动水面附近或漂浮于水面上物体的反射场景,该方法较其它方法能够更好地获得物理真实的绘制结果。     

基于点索引的网格模型的层次结构

针对稠密采样的网格模型．提出一种基于面片中心点索引的新的场景BSP树结构．与常规RSP树构造方式不同,文中RSP树以面片中心点位置作为场景中各面片二叉分类的依据,避免了常规BSP树构造方法中因分割与削分平面相交的面片引起的场景复杂度的增加,大大简化了BSP树的构造过程．实验结果表明：对稠密网格场景,文中的BSP树比常规方式构造的BSP树任加速光线跟踪算法中的求交测试具有明显的优势．     

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

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

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

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

一种新的层次包围盒方法

在计算机图形学中，经常碰到这样的问题：给定平面或空间上的一系列景物，判断一条直线是否与这些景物的其中一个相交，或者更进一步地，如果相交的话，它与哪 些景物相交。这个问题在隐茂线消除、隐茂面消除、光线跟踪算法等图形学基本算法中具有普遍意义。     

一种光线与三角形求交算法的硬件架构设计

为了实现实时性的光线追踪平台,提出了一种光线与三角形求交算法的硬件架构设计。首先介绍了一种光线与三角形求交的简洁算法。该算法与其它算法相比使用存储空间最少,却具有相似的性能,便于硬件实现。根据此算法,提出了相应的硬件架构,在架构设计过程中,通过折叠、资源共享、以及多线程等硬件架构设计方法来提高硬件使用率,使有限的硬件资源达到最高的性能。实验结果表明,与现有方案相比,本文硬件架构平台在速度和芯片面积两个方面都存在着较大的提高。为实时光线追踪的实现提供了依据。     

真实感雨线绘制

雨线的真实感绘制极具挑战性.雨滴在下落过程中会发生快速的震荡,由于光线在其中的反射和折射而具有复杂的光学效果,在人眼和摄像机观察时会产生运动模糊形成雨线.提出一种基于Monte Carlo光线跟踪的方法用于绘制真实感雨线.通过预先对雨滴震荡周期内每个离散时间点的雨滴三角形网格建立加速结构,并利用雨滴运动包围盒与采样光线的相交计算,大大加速了光线与雨滴的相交测试;使用自适应采样技术避免了对图像中每个像素点都使用大的采样数,提高了采样效率,加速了图像的绘制.将本文方法集成于离线绘制器(PBRT)中,生成了具有真实感的雨线图像和雨景动画.实验结果表明,本文方法能真实地模拟雨滴的震荡和光线在雨滴中的多次反射和折射,并能在包含任意类型光源的场景中有效地绘制真实感雨线.     

Progressive Hulls for Intersection Applications

Progressive meshes are an established tool for triangle mesh simplification. By suitably adapting the simplification process, progressive hulls can be generated which enclose the original mesh in gradually simpler, nested meshes. We couple progressive hulls with a selective refinement framework and use them in applications involving intersection queries on the mesh. We demonstrate that selectively refinable progressive hulls considerably speed up intersection queries by efficiently locating intersection points on the mesh. Concerning the progressive hull construction, we propose a new formula for assigning edge collapse priorities that significantly accelerates the simplification process, and enhance the existing algorithm with several conditions aimed at producing higher quality hulls. Using progressive hulls has the added advantage that they can be used instead of the enclosed object when a lower resolution of display can be tolerated, thus speeding up the rendering process. ACM CSS: I.3.3 Computer Graphics—Picture/Image Generation, I.3.5 Computer Graphics—Computational Geometry and Object Modeling, I.3.7 Computer Graphics—Three‐Dimensional Graphics and Realism     

Fast Ray Tracing NURBS Surfaces

In this paper,a new algorithm wit extrapolation process for computing the ray/surface intersection is presented.Also,a ray is defined to be the intersection of two planes,which are non-orthogonal in general,in such a way that the number of multiplication operations is reduced.In the preprocessing step,NURBS surfaces are subdivded adaptively into rational Bezier patches.Parallelepipeds are used to enclose the respective patches as tightly as possible Therefore,for each ray that hits the enclosure(i.e.,parallelepiped)of a patch the intersection points with the parallelepiped‘s faces can be used to yield a good starting point for the following iteration.The improved Newton iteration with extrapolation process saves CPU time by reducing the number of iteration steps.The intersection scheme is facter than previous methods for which published performance data allow reliable comparison.The method may also be used to speed up tracing the intersection of two parametric surfaces and oter operations that need Newton iteration.     

Volume element model mesh generation strategy and its application in ship thermal analysis

This paper introduces a mesh generation strategy devised and implemented for the volume element model (VEM), and elaborates key contributions of the strategy in enhancing the VEM as a prominent tool in ship thermal modeling and simulation. The VEM mesh generation strategy employs ray crossings and ray– triangle intersection algorithms developed in previous studies, and constructs sufficiently accurate geometric representations of the whole ship within permissible time frame using hexahedral meshes. In addition, this work demonstrates the strategy’s practicality in thermal analysis of a notional all-electric ship, which is characterized by intricate structures and multiple internal components, i.e., thermal loads. Ship thermal solutions obtained in this assessment verify the proposed mesh generation strategy’s ability to improve the overall computational efficiency of the VEM, by allowing it to obtain plausible thermal solutions with respect to time and space using a coarse independent mesh.     

Valence-Driven Connectivity Encoding for 3D Meshes

In this paper, we propose a valence-driven, single-resolution encoding technique for lossless compression of triangle mesh connectivity. Building upon a valence-based approach pioneered by Touma and Gotsman²² , we design a new valence-driven conquest for arbitrary meshes that always guarantees smaller compression rates than the original method. Furthermore, we provide a novel theoretical entropy study of our technique, hinting the optimality of the valence-driven approach. Finally, we demonstrate the practical efficiency of this approach (in agreement with the theoretical prediction) on a series of test meshes, resulting in the lowest compression ratios published so far, for both irregular and regular meshes, small or large.     

Spectral mesh deformation

In this paper, we present a novel spectral method for mesh deformation based on manifold harmonics transform. The eigenfunctions of the Laplace–Beltrami operator give orthogonal bases for parameterizing the space of functions defined on the surfaces. The geometry and motion of the original irregular meshes can be compactly encoded using the low-frequency spectrum of the manifold harmonics. Using the spectral method, the size of the linear deformation system can be significantly reduced to achieve interactive computational speed for manipulating large triangle meshes. Our experimental results demonstrate that only a small spectrum is needed to achieve undistinguishable deformations for large triangle meshes. The spectral mesh deformation approach shows great performance improvement on computational speed over its spatial counterparts.     

Time‐Continuous Quasi‐Monte Carlo Ray Tracing

Domain‐continuous visibility determination algorithms have proved to be very efficient at reducing noise otherwise prevalent in stochastic sampling. Even though they come with an increased overhead in terms of geometrical tests and visibility information management, their analytical nature provides such a rich integral that the pay‐off is often worth it. This paper presents a time‐continuous, primary visibility algorithm for motion blur aimed at ray tracing. Two novel intersection tests are derived and implemented. The first is for ray versus moving triangle and the second for ray versus moving AABB intersection. A novel take on shading is presented as well, where the time continuum of visible geometry is adaptively point‐sampled. Static geometry is handled using supplemental stochastic rays in order to reduce spatial aliasing. Finally, a prototype ray tracer with a full time‐continuous traversal kernel is presented in detail. The results are based on a variety of test scenarios and show that even though our time‐continuous algorithm has limitations, it outperforms multi‐jittered quasi‐Monte Carlo ray tracing in terms of image quality at equal rendering time, within wide sampling rate ranges.     

A reliable triangular mesh intersection algorithm and its application in geological modelling

We introduce a reliable intersection algorithm for manifold surface meshes. The proposed algorithm builds conforming surface meshes from a set of intersecting triangulated surfaces. This algorithm effectively handles all degenerate triangle–triangle intersection cases. The key idea of the algorithm is based on an extensive set of triangle–edge intersection cases, combined with an intersection curve tracking method. The intersection operations do not rely on global spatial search operations and no remeshing steps are needed. The intersection curves are introduced into each surface mesh using a unique curve imprinting algorithm. The imprinting algorithm naturally handles degenerate intersection cases of many surfaces at an edge or at a point. The algorithm produces a consistent mesh data structure for subsequent mesh optimization operations. The mesh intersection algorithm is used within a general framework for modelling and meshing of geological formations, which are essential for reliable mathematical modelling of oil reservoirs.