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的关系如上图。

 

 

19 2月

光线(直线)和三角形碰撞检测

今天我们来讲光线追踪之三角形碰撞的检测,三角形是所有不规则物体的基础,为什么这么说呢。因为不规则物体都可以用三角面来表示,是一堆三角面的集合,所以和一个不规则物体进行的光线碰撞检测其实就是和一堆三角形进行碰撞检测。那学过三维软件的同学都知道,我们建模更多的用的是四边面,也可能是多边面,其实这些多边面都能最终转换成三边面,所以今天来介绍怎么进行三角形的碰撞检测。

三角形定义:

triangle

是由三个点确认的一个平面。要确定垂直于面的发现n,有以下公式:

tfo

为了判断一条光线是否和一个三角形相交,首先我们先找到三角形所在的平面,然后再判断,线和平面的交点是否在三角形里面。这个算法牵扯到质心坐标系统Barycentric coordinate (α,β,γ),在平面上的任意点p可表示为:p

满足:α+β+γ=1

如果平面上的点p在三角形内,那么需要满足一下条件:

constaint

那么如果光线和三角形所在的平面的交点p满足上述条件,那么点就在三角形内,即直线和三角形相交。

实际上一个平面空间上我们可以转换成2维平面,我们可以去掉一个轴α。α=1-β-γ

p

可以转化成:

p(β,γ)=a+β(b-a)+γ(c-a)

需要满足条件:

ooo

当β=0:p=a+γ(c-a), 0<γ<1,(c-a)表示一条三角形边

当γ=0:p=a+γ(b-a),0<γ<1,(b-a)表示的三角形的另一条边.

我们替代β+γ=1,β=1-γ。p=b+γ(c-b), 0<γ<1(c-b)表示的是第三条边。

直线方程: p=o+td

我们可以得到方程:finaleq

gratrai

(β,γ)表示轴,α表示原点

Code

03 2月

axis-aligned bounding boxes碰撞检测

作者:will 网址:http://ymuhua.com/2016/02/03/aabb/

再讲加速算法之前,我要来介绍bounding box的概念,中文翻译成边界盒子,一般简称bbx。为什么要引入bbx呢。因为bbx可以代表一个物体体积范围,在模型很复杂的时候,如果每根光线都要和复杂模型进行碰撞运算会非常的慢,所以,一个快速简单的方法就是先和这个代表物体体积范围的bbx先进行快速碰撞检测,如果没碰到就不需要进行复杂模型的碰撞检测,这要大大减少了碰撞检测的运算量。加快了速度。

bbx

axis-aligned bounding box必须满足它是和轴向对齐,也就是每个面都满足垂直末个轴向。

如何求一根射线和一个box相交呢?我们先考虑2d情况。

我们还记得光线方程: p=o+td;

bbx2

图(a)x0,x1,y0,y1这四根是从box表面无线延伸的直线,图(b)一根光线射出,和x0,x1,y0,y1四根线分别产生四个交点,t0,t1,t2,t3。t0,t1表示一个线段x,t2,t3表示一个线段y,我们发现当x和y重叠的时候,光线就和box相交了。我们看下图。

bbx3

所以我们算法就是找这两断线段有没有重叠。

除了以上的规律外,我们还要考虑特殊情况,如下图。

bbx4

黑点表示的光线的起点。这是4种特殊情况,图(a)虽然他满足重叠规律,但是光线并没有穿过box,这时候所有的t满足,t<0。图(b)光线从物体表面和内部出发。

代码:

碰撞检测

转载请注明作者和出处,谢谢。http://ymuhua.com/2016/02/03/aabb/

 

 

02 2月

摄像机,透视,镜头畸变

作者:will 网址:http://ymuhua.com/2016/02/02/camera/

我们之前的渲染都是基于正交视图,是没有透视关系,何为透视,透视更符合我们平时眼睛观察,近大远小就是我们观察这个世界事物最常见的。所以我们需要在三维场景中也要实现这个效果。

在计算机图形学,我们知道所有的三维模型场景从显示器中显示出来都需要进行3d到2d的投射转换。所以我们需要一个观察屏幕view plane,也称为画布,而摄像机是一个观察点,通过这个摄像机观察点射出光线,然后打到模型,然后在这些光线的路径上我们放上一个画布view plane如果光线遇到模型,那么我们就会在屏幕上留下一个印记,然后,屏幕上就能显示出一个模型了。

persperct

那么透视是怎么产生的呢?我们用张图来解释。

perspect2

a图是透视的结果,b图是我们从一个顶视图俯瞰,小黄点是摄像机,虚线是光线,然后虚线和黑实线(view plane)相交的点就是在屏幕上所成图像的由来了。

这个也同样。

perspect3

 

知道了透视关系后,我们的摄像机作为透视的重要工具需要哪些属性呢。

观察屏幕:长,宽,分辨率,在《渲染第一张图片》已讲。

焦距:摄像机距离画布的距离(view plane)。如下图的d来表示

focallengthfocal

如上图,我们发现在保持摄像机相对物体位置不变,和画布大小不变的情况下,摄像机的焦距(d)越大,可视范围就越小。这个玩过摄影的人都知道,焦距越小,它的捕捉场景的范围反而越大,这个和相机的原理是相似的。因为你的感光器就是你的画布,而你的感光器的大小对于一台相机来说是定死。

摄像机的位置,方向:方便入门,我们将摄像机放在原点位置,方向是朝着z轴方向。那么画布也垂直于z轴。

这是摄像机类定义:

camera

这个是houdini中摄像机的关系图

spherecam

那么我们如何来确定从摄像机射出的光线方向呢,对比上面两张图,左图是正交试图的光线,右图是透视射出的光线,发现区别了吧。

左图的光线的方向永远是ray.dir=(0,0,1)。

但是右图的光绪需要将每个画布上的像素中心点减去摄像机的坐标,就能确定一个方向(向量位置相减)。viewplane

还记得这张图吗,我们是用来求每个像素中心点是用到的,假定现在的摄像机在坐标原点(0,0,0)。光线的方向公式:camdir

s:每个像素的size大小,pixel_size=Aperture/Hres(前一章介绍)

c,r: 当前长,宽,第几个宽像素。

d: 摄像机的方向,是指向z轴。

那么,很简单,我们的代码只需要改两句话。

下面是三张不同焦距的渲染一堆球。

f10

焦距:10

f50

焦距:50

f200

焦距:200

这个结果和之前分析的是一样的。焦距越大可视范围反而越小。同时我们发现在焦距等于10的情况下。圆球变成了椭圆形,尤其是图片边缘的球越发明显,我们称之为镜头畸变。

镜头畸变

镜头畸变是怎么产生的呢?请看下图。

distortion

引起透视变形的原因就是我们的画布(view plane)是平的。那为什么我们人眼没有透视畸变呢,就是因为人的眼球是个圆球。从上图可以发现,当焦距非常小的时候,可视范围是非常大。只有在z轴上的物体保持的是圆形,离开z轴越远,球失圆就越严重。所以照相机的鱼眼镜头镜片非常的凸就是为了避免镜头畸变的原因了。

转载请注明作者和出处,谢谢。http://ymuhua.com/2016/02/02/camera/