基于图像空间剖分的隐式曲面光线跟踪算法

根据光线的空间相关性,本文提出了一种基于图像空间剖分的隐式曲面快速光线跟踪算法。首先对图像空间进行剖分,然后对剖分后的区域进行采样,根据采样结果估计未采样部分的像素值。这种方法避免了大量与曲面不相交的光线测试,而且估计的光线初始长度也减少了光线与曲面求交测

基于图像空间剖分的隐式曲面光线跟踪算法

武继银 潘荣江

山东大学计算机科学与技术学院 济南(250101)

E-mail:wujiyin@

摘 要： 根据光线的空间相关性，本文提出了一种基于图像空间剖分的隐式曲面快速光线跟踪算法。首先对图像空间进行剖分，然后对剖分后的区域进行采样，根据采样结果估计未采样部分的像素值。这种方法避免了大量与曲面不相交的光线测试，而且估计的光线初始长度也减少了光线与曲面求交测试的次数。实验表明该方法在保证隐式曲面绘制质量的同时，提高了用光线跟踪方法绘制隐式曲面的效率。

关键词：隐式曲面，光线跟踪，空间剖分，局部采样

中图分类号：TP391

1. 引 言

隐式曲面是几何造型中一类重要的曲面表示形式，主要有blobby model[1]，soft objects[2]，RBF (Radial-Basis Functions)[3,4] 、MPU(Multi-level Partition of Unity)[5]和SLIM (Sparse Low-degree IMplicit)[6] 等表示方法。本文中以MPU隐式曲面为例。MPU隐式曲面采用层次树状结构，把3D数据点集分割成若干较小的数据点集，每个叶子节点对应一个用低次多项式表示的局部曲面，整体隐式曲面由局部曲面加权平均得到。

目前隐式曲面的绘制主要有多边形化和光线跟踪方法。多边形化方法[7]是用离散的多边

形来逼近隐式曲面，对于某一曲面，要生成多边形网格只需要计算一次；通过采样精度可以控制生成的多边形数量；生成的多边形网格与视点的位置无关。但是多边形化方法要计算等值面多边形和对三维空间进行剖分，需要额外的内存，显示质量不高[8]。光线跟踪算法[9]是生成真实感图形的主要算法之一，原理简单、实现方便，能生成各种逼真的视觉效果。但光线跟踪算法需跟踪每一条从视点发出的光线，进行大量光线与曲面的求交测试，计算量大、速度慢。

Ohtake等人在文献[5]中分别用多边形化和光线跟踪方法来绘制MPU隐式曲面，其提供

的光线跟踪方法效率很低。为了提高用光线跟踪算法绘制隐式曲面的效率，主要有加速光线与曲面的求交速度、减少求交次数、采用并行算法等措施。空间剖分算法[10,11,12]是利用数据空间的相关性，对数据空间进行剖分，建立空体元的包围盒，当光线在数据空间通过时，只需与包围盒进行简单的求交计算，就可以略过空的包围盒，减少求交的次数。与基本的光线跟踪算法相比，基于空间剖分的加速技术需要进行树搜索和包围盒求交计算，当非空体元在数据空间的分布比较复杂时，空间剖分所产生的包围盒数量将迅速增加，导致预处理时间增加、大量的树搜索，降低了算法的效率。另外，随着图形处理器(GPU)性能的大幅度提高及可编程特性的扩展，图形处理流水线的某些阶段以及图形算法可以用GPU来处理。利用GPU的并行处理特性，把光线跟踪中求交计算、函数求值以及法向计算用GPU处理，提高光线跟踪算法的效率[13,14]。Rayskip算法[15]是利用物体的空间相关性，用相邻光线来估算当前光线的起始跟踪长度，可以减少一些光线的求交测试次数，但并不能减少光线的条数，鲁棒性不强，而且所计算的光线长度需要保存下来，占用大量的内存空间。

本文中，我们根据光线的空间相关性，把图像空间剖分成若干区域，对剖分后的子区域

进行采样，然后估计可能存在隐式曲面投影的区域，避免了与曲面不相交光线的求交测试，

根据光线的空间相关性,本文提出了一种基于图像空间剖分的隐式曲面快速光线跟踪算法。首先对图像空间进行剖分,然后对剖分后的区域进行采样,根据采样结果估计未采样部分的像素值。这种方法避免了大量与曲面不相交的光线测试,而且估计的光线初始长度也减少了光线与曲面求交测

对可能相交的光线估计其初始长度，减少了光线与曲面求交测试的次数。

2. 基于图像空间剖分的光线跟踪算法

2.1图像空间的剖分

把整个图像空间剖分成若干区域，每个区域的分辨率越高，剖分成的区域越少，图像的

采样总时间越短，所需绘制的面积越大，反之，剖分成的区域越多，采样时间越长，所需绘制的面积越小，如图1所示，每个区域都需要采样，存在点的区域都需要绘制，(a)中每个区域的分辨率为40×40，(b)为10×10，(c)为5×5，可见(a)剖分成的区域最少，采样时间最少，需要绘制的面积最大，(c)剖分成的区域最多，采样时间最多，需要绘制的面积最小，(b)为本文选择的分辨率，实验表明，该分辨率能够兼顾采样时间和绘制面积。

(a) (b)

图 1 区域分辨率的选取

(c) 图2 图像剖分与采样

图4

错误更正 图3估计光线与曲面关系

2.2 对图像空间的局部采样

根据光线的空间相关性，对剖分后的图像空间进行局部均匀采样，选择每个区域的9

个像素进行采样，如图2所示●所在方格为对应的采样像素。用光线跟踪算法计算光线与隐式曲面的交点，如果9条光线中没有与曲面相交的光线，则认为该区域中没有曲面投影，否则，记录从视点到光线与曲面交点的距离，称为采样长度，并把9条光线中采样长度最小的光线作为该区域中每条光线的起始长度。估计的光线起始长度可能会出现三种情况，如图3所示，①起始长度小于实际长度；②起始长度大于实际长度，但没有穿过曲面；③光线穿过曲面。对于①直接进行光线跟踪，②进行反向光线跟踪，③是一种错误的情况，Rayskip算法[14]使用填充算法来纠正这种错误。 没有取得采样长度的区域也有可能存在曲面投影，特别是在曲面的边缘部分，在算法中需要对这种错误进行更正。

根据光线的空间相关性,本文提出了一种基于图像空间剖分的隐式曲面快速光线跟踪算法。首先对图像空间进行剖分,然后对剖分后的区域进行采样,根据采样结果估计未采样部分的像素值。这种方法避免了大量与曲面不相交的光线测试,而且估计的光线初始长度也减少了光线与曲面求交测

2.3 错误更正

对没有取得采样长度的区域，检查其所有相邻的区域，如果其相邻的8个区域至少有一

个取得了采样长度，则认为该区域也可能存在曲面投影，把其所有相邻区域的最小采样长度作为该区域光线跟踪的起始长度，如图4所示，其中◇所在方格为取得采样长度的区域，★所在的方格为可能存在曲面投影的区域，可以看出★所在区域把◇所在区域紧紧包围，只需计算◇和★所在区域的像素亮度，这样可以排除不与曲面相交的光线测试。

2.4 求交策略

直线与隐式曲面求交的方法主要有区间算术[16]和Lipschitz[17]方法。区间算术方法是先

找到一个包含方程f(p(t)) = 0的一个根的区间[t1,t2]，其中p(t)为空间中的一点，然后在该区

Lipschitz方法是假设曲面是Lipschitz连续间上利用Newton法或regula falsi方法[18]计算根。

p2，存在一正常数L满足不等式。满足该式的最小L为函数f 的Lipschitz的，即对任意点p1，

常数，Lipschitz常数已经应用在计算机图形学中的碰撞检测[19]和隐式曲面的绘制[17]。

由于根据MPU隐式曲面可以计算有向距离，本文中采用球体跟踪[8]的方法进行求交测

试，该方法是Lipschitz方法的一种应用，其主要思想是光线每次以不穿过曲面的步长前进，如果光线与曲面相交，则返回光线与曲面的第一个交点，如图5所示。

图 5 球体跟踪

3. 实验结果与分析

我们用C++实现了本算法，实验环境是2.33GHz Intel Dual Core CPU、2G内存，在绘

制种使用了环境光、一个点光源和一个平行光源。

图6为bunny模型使用本算法绘制的结果，分辨率为400×400像素，(a)为没有添加阴

影的绘制效果，绘制时间为8.25秒，(b)为添加阴影计算后的绘制效果，绘制时间为20.36秒，可见阴影计算需要大量的时间，(c)为本算法进行图像空间剖分、局部采样和错误更正的描述，其中方格表示把图像空间剖分成的区域，内部点为采样长度最小的光线所对应的像素，外围点所在区域为可能存在曲面投影，但没有取得采样长度的区域，可见外围点所在区域把曲面投影的区域紧紧包围，既避免了对整个图像空间内的每个像素都发射一条光线，又不会遗漏与曲面相交的光线，在保证图像质量的前提下提高了绘制效率。 由表1可以看出本算法与MPU算法中的光线跟踪相比，速度上有了明显提高，但加速只对隐式曲面的绘制有效，对阴影计算没有明显的改善。

根据光线的空间相关性,本文提出了一种基于图像空间剖分的隐式曲面快速光线跟踪算法。首先对图像空间进行剖分,然后对剖分后的区域进行采样,根据采样结果估计未采样部分的像素值。这种方法避免了大量与曲面不相交的光线测试,而且估计的光线初始长度也减少了光线与曲面求交测

(a) (c) (b)

图6 bunny

模型的绘制效果

表1 各种模型的绘制时间对比 绘制时间(s)

模型 点数量 MPU中的光线跟踪

无阴影

33.89

Chinese

dragon

图7中(a)和(b)为本算法绘制的Stanford dragon模型，其中(a)为没有添加阴影的绘制效果，(b)为添加阴影的绘制效果，(c)和(d)为MPU算法中光线跟踪的绘制效果，其中(c)为没有使添加阴影的绘制效果，(d)为添加阴影的绘制效果，可见(a)和(c)，(b)和(d)并有明显差别，本算法没有降低图像的绘制质量。 图8绘出了各种模型在不同分辨率下所需时间的曲线，其中横坐标表示图像的分辨率为X×X。对图8分析可知：①随着分辨率的增大，每个模型的绘制时间近似以二次函数增长，这是因为绘制的像素个数随分辨率的增长以二次函数增长；②随着分辨率的增大，大模型绘制时间的增长速度比小模型的增长速度要快，这是由于MPU隐式曲面的重建速度随模型的增大而减慢，从而使函数求值变得复杂；③bunny模型比hand模型的点数量要少，但是bunny模型的绘制速度要慢，这是因为bunny模型绘制的像素个数要多，它与曲面相交的光线要多，其中bunny模型绘制了139320个像素，而hand模型只绘制了42962个像素 有阴影 图像空间剖分光线跟踪无阴影 8.25 7.28 9.82 有阴影时间比 无阴影 有阴影 2.05 4. 结论 本文描述了一种基于图像空间剖分的MPU隐式曲面光线跟踪算法，利用图像空间剖分和局部采样，在不降低图像质量的前提下，减少了投射光线的数目；利用光线的空间相关性，减少了光线求交测试的次数，提高了光线跟踪算法MPU隐式曲面的速度。 该方法对其他隐式曲面表示方法的推广，需要进一步的研究和改进。

根据光线的空间相关性,本文提出了一种基于图像空间剖分的隐式曲面快速光线跟踪算法。首先对图像空间进行剖分,然后对剖分后的区域进行采样,根据采样结果估计未采样部分的像素值。这种方法避免了大量与曲面不相交的光线测试,而且估计的光线初始长度也减少了光线与曲面求交测

(a) (b)

(c) (d) 图7 本算法与MPU中光线跟踪算法绘制效果的比较

图 8 各模型绘制不同分辨率图像时间对比

根据光线的空间相关性,本文提出了一种基于图像空间剖分的隐式曲面快速光线跟踪算法。首先对图像空间进行剖分,然后对剖分后的区域进行采样,根据采样结果估计未采样部分的像素值。这种方法避免了大量与曲面不相交的光线测试,而且估计的光线初始长度也减少了光线与曲面求交测

参考文献（五号，黑体）

[1] S. Muraki. Volumetric shape description of range data using blobby model [J]. Computer Graphics

SIGGRAPH’91 Proceedings. 1991, 25(4):227-235.

[2] G. Wyvill, C. Mcpheeters, and B. Wyvill. Data structure for soft objects [J]. The Visual Computer. 1986,

2(4):227-234.

[3] V. V. Savchenko, A. A. Pasko, and O. G. Okunev, et al. Function representation of solids reconstructed from

scattered surface points and contours [J]. Computer Graphics Forum. 1995,14(4):181-188.

[4] J. C. Carr, R. K. Beatson, and J. B. Cherrie, et al. Reconstruction and representation of 3D objects with radial

basis functions [A]. Proceedings of the 28th annual conference on Computer graphics and interactive techniques[C]. New York: ACM Press. 2001, 67-76.

[5] Y. Ohtake, A. Belyaev, and M. Alexa, et al. Multi-level partition of unity implicits [J]. Computer Graphics

SIGGRAPH. 2003, 463-470

[6] Y. Ohtake, A. Belyaev, and M. Alexa. Sparse Low-degree Implicit Surfaces with Applications to High Quality

Rendering, Feature Extraction, and Smoothing[A]. Processing of the third Eurographics symposium on Geometry[C]. Vienna Austria: Eurographics Association. 2005, 149-158.

[7] J. Bloomenthal. Polygonization of Implicit Surfaces [J]. Computer Aided Geometric Design. 1988, 5(4)

341-355.

[8] J. C. Hart. Sphere tracing: a geometric method for the antialiased ray tracing of implicit surfaces[A]. The

Visual Computer[C],New York: Springer Verlag,1996:527-545.

[9] 彭群生,鲍虎军,金小刚. 计算机真实感图形的算法基础[M]. 北京:科学出版社,1999,122-220.

[10] T. Duff. Interval arithmetic and recursive subdivision for implicit functions and constructive solid geometry[J].

Computer Graphics. 1992, 26 (2):131-138.

[11] L. Szirmay-Kalos , V. Havran , and B.Balazs. On the efficiency of ray-shooting acceleration schemes[A].

Proceedings of the Spring Conference on Computer Graphics[C]. Budmerice Slovakia :ACM Press.2002, 97 -106.

[12] J. Cleary, G. Wyvill, Analysis of an algorithm for fast ray tracing using uniform space subdivision [J]. Visual

Computer. 1988, 4(2), 65-83.

[13] O. Fryazinov, A. Pasko. GPU-based real time FRep ray casting [A]. GraphiCon'2007 [C]. 2007, 23-27.

[14] T. Kanai, Y. Ohtake, and H. Kawata, et al. GPU-based Rendering of Sparse Low-degree Implicit Surfaces[A].

In 4th International Conference on Computer Graphics and Interactive Techniques in Australasia and the Southeast Asia (GRAPHITE 2006)[C] . NY: ACM Press. 2006, 165-171.

[15] E. de Groot, B. Wyvill. Rayskip: Faster Ray Tracing of Implicit Surface Animations[A]. International

Conference on Computer Graphics and Interactive Techniques in Australasia and Southeast Asia[C]. Graphite: ACM Press . 2005,31-37.

[16] D. P. Mitchell. Robust ray intersection with interval arithmetic[A]. Proceedings of Graphics Interface ’90[C].

Halifax, Nova Scotia: Canadian Information Processing Society .1990, 68-74.

[17] D. Kalra, A. H. Barr. Guaranteed ray intersections with implicit surfaces [J].Computer Graphics.1989,23(3):

297-306.

[18] J. F. Blinn. A generalization of algebraic surface drawing[J]. ACM Transactions on Graphics. 1982,

1(3):235-256,.

[19] B. V. Herzen, A. H. Barr. Accurate triangulations of deformed, intersecting surfaces[J]. Computer Graphics.

1987,21(4):103-110.

Fast Ray Tracing of Implicit Surfaces Based on Image Space

Subdivision

Wu Ji-yin Pan Rong-jiang

School of Computer Science and Technology, Shandong University, Jinan 250100

Abstract

According to the spatial coherence, a fast algorithm for ray tracing is proposed for rendering implicit surfaces. The image space is subdivided into several small regions which are sampled for rendering. According to results of sampling, it avoids the computation of rays in regions without implicit surfaces and the estimated ray length reduces the computation for finding the first points of intersection between rays and implicit surfaces. Experiments show that the proposed algorithm improves the rendering speed of ray tracing for implicit surfaces without loss of quality.

Keywords: implicit Surface, ray tracing, space subdivision, local sampling

本文来源：https://www.bwwdw.com/article/zk14.html