24 6月

Lego Ninjago

支持一下自己加入海外大军做的第一个项目。当初其实第一次看的时候没什么感觉。感觉没啥搞笑的,但是感觉老外的笑点都蛮低的,感觉自己也被影响了,现在感觉几乎每个镜头都有笑点了。。。。

国内版的有些许不一样。连预告片都不放过,简直了。。。。
如果可以翻墙的同学可以看看youtube

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