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

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算法中的光线跟踪相比，速度上有了明显提高，但加速只对隐式曲面的绘制有效，对阴影计算没有明显的改善。