23 2月

Grids加速算法

光线追踪的加速算法有很多,我们常见的有bounding volume hierarchies(BVHs),octrees,binary space partition(BSP) trees, kd-tree 和 grids。

我已经迫不及待的想讲加速算法了。因为光线追踪实在是非常的慢。因为光线追踪算法的数据量实在是非常的巨大。尤其是当渲染分辨率增加,意味着光线总数增大,物体数量的增加也同样会增加数据量。打个比方我们渲染一张800*800分辨率的图片,场景内有100个球。根据之前的算法:数据量是:800*800*100=64,000,000次碰撞检测。渲染时间: 2.636093s。

得到下图:

sp

我们发现,其实每个光线最多也就会穿过3,4个球,但是呢,我们现在每根光线都要和100个球进行碰撞测试,95%的碰撞测试是无用的。那么我们如何每次每根光线只和对应的几个球进行碰撞测试呢。

那能不能只和每根光线附近的球进行碰撞检测呢。当然可以,Grids加速算法就是将场景根据里面的物体分割成立体网格,然后每次查找我们先找光线穿过哪个网格,然后再判断相对应网格内的物体进行碰撞检测,这样就大大减少了数据量。

我们先来看一下2d情况。

grid

(a)将场景分成网格,(b)我们只需要和网格内的物体进行碰撞检测(蓝色物体),(c)当网格分割越精细,我们就能越精确取到相对应物体。

搭建Grid网格

首先,我们要确定,我要搭建多大的网格,前一章我们讲过用bounding box来确定物体的大小范围,所以我们也许要用bbox来表示这个grid网格。我们搭建的这个grid只要包括所有物体bbox范围就行了。如下图:

bbxgrid

我们确定了grid的大小之后,我们现在来确定一下要划分成几乘几的网格呢。影响网格的一个因素就是场景中物体的数量。子网格(cell)的数量是影响效率的关键,如果网格不划分,整个场景就一个子网格,一个子网格包含所有的物体,那么等于没有加速。

如果,子网格数量过多,那这又无形中增加了很多数据量,所以,选择一个合理的平衡点很关键。

我们定义nx,ny,nz为三个轴向子网格的数目。wx,wy,wz为三个轴向网格grid长度。

每个轴向划分网格数目为:

nx=trunc(m*wx/s)+1

ny=trunc(m*wx/s)+1

nz=trunc(m*wz/s)+1

trunc函数为取整函数。m是一个系数来影响子网格cells的数量。当m=1,那么cells数量约等于物体数量。cells越多,我们就可能检测到更多的空cells,cells越少,那么每个子网格就会含有更多的物体。经过先人的测试,貌似子网格cells的数量是物体8-10倍是个最佳的平衡点。也就是m=2。m³=8。大家可以自己尝试一下找到一个合理的值。

现在grids有了,cells也划分好了,现在我们如何将场景中的物体放入相对应的cells中呢?

虽然grid是三维立体的,但是每个cell在计算机存储是线性的。所以每个cells都有一个编号。cell(ix,iy,iz)的编号是:

index=ix+iy*nx+iz*nx*ny

cellobj boooo

以上两图,我们可以这么归纳,只要物体bbox和物体cells重叠,那么这个cell就包含这个物体。

上图(b)为了确定物体归属哪个cells,我们需要p0是物体bbox的最小值。p1是物体bbox的最大值。

我们先确定一个轴向cells,确定ix,我们通过p0求出ix最小值ixMin,然后求出p1求出ix最大值ixMax,那么ix的范围在[ixMin, ixMax]的cells都会包含这个物体。

gridcells

如上图,x轴向上面有4个cells,ix∈[0,3],p点坐标是在p0,和p1之间,所以我们可以映射到[0,1]。然后在乘以nx就能得到当前ix。

focell

当px>p1,f(p)=1 ;当px<p0,f(p)=0;

px

假设每个cells宽度是1,那么f(px)和ix的关系如上图。

 

 

One thought on “Grids加速算法

发表评论

电子邮件地址不会被公开。