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

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

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

中图分类号：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]是利用物体的空间相关性，用相邻光线来估算当前光线的起始跟踪长度，可以减少一些光线的求交测试次数，但并不能减少光线的条数，鲁棒性不强，而且所计算的光线长度需要保存下来，占用大量的内存空间。

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

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