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/
28 1月

Vex 案例

作者:will 网址:http://ymuhua.com/2016/01/28/vex-104/

用volume做mask选点。(volumesample)

现在我们有一个河床,和一个用box塞满点。我想做个一条小溪流。

comb

但是,我想把在河床外面的点去掉,只留下河床里面的点来作为水。

bedvolume

那么,首先我们需要将河床转换成有体积的模型后再转换成volume。

然后,我通过volumesample来选择我需要的点。

v1node

结果:

wkresult

用volume来选模型的好处就是,速度非常的快,比用一个封闭的几何体去选择快很多,这个在生产中是非常实用的。

 

vex选出稀疏(落单)的点(point cloud)

我们做水或者水花的时候,可能会发现某些点飞得非常的远,为了处理这些落单的点,可能通常会用到速度来判断删除,但是用速度有个问题,当它速度减小的时候这些点又会重新出现。

所以,我们需要用点云pointcloud来判断,当某个点周围没有点,或者点很少的时候,我们可以删除这个点。

pointxxx density

 

 

更具一个轴来旋转方向向量

现在如图有一个法线N,它 的初始方向是{1,0,0}, 现在我需要让法线N绕y轴{0,1,0}来旋转。rot

rot2

转载请注明作者和出处,谢谢。http://ymuhua.com/2016/01/28/vex-104/
27 1月

Vex 语法

作者:will 网址:http://ymuhua.com/2016/01/27/vex-102/

这部分我们会简单介绍一下,判断和循环。为什么简单介绍一下呢,因为几乎和c是一样的。

{}

和C一样,大括号在逻辑语句中表示开始和结束的标记

If

结果:

cd

while loop

For

结果:增加10个点

foreach

这个循环旨在帮助你循环数组中的元素。
语法

举例

return

函数返回值

跳出当前循环,进行下次循环

Break

结束循环

 

调用使用用户自定义函数

转载请注明作者和出处,谢谢。http://ymuhua.com/2016/01/27/vex-102/
27 1月

Vex Expression 用法

作者:will 网址:http://ymuhua.com/2016/01/27/vex-103/

自从有了wrangle这些节点让我能够写vex表达式之后,houdini原有哪些很常用的节点都被我抛弃了。下面来介绍一下它可以代替哪些节点。

Point

point

如果用过houdini15之前的版本的同学,我们发现houdini15之后这个节点里面填写的内容发生改变了。说明sidefx也更倾向于用vex表达式了。

point2

以上的这些参数,我们用vex可以这么写:

Attribute Create

pscale

vex可以这么写:

很简洁~

将属性映射为local varible.

group

可以替代group节点

创建组:用group_name的前缀就能很方便创建一个组

判断组是否存在

根据条件进组

组合并

group2

其实我们在Spreadsheet中查看,其实就相当于添加了一个组的属性。

group

除了以上这些我比较常用的操作,它还能完成以下

Creating geometry修改创建模型

常用到一下函数:

addpoint

addprim

addvertex

removepoint

removeprim

setprimintrinsic

setattrib   用@name=val这种方式直接赋值属性会比较快,效率会更高,但是当你需要创 建不同类型的属性的时候可以用这个。

还有一点我们需要知道就是上面这些函数都是并发的,也就是说支持cpu多核并发处理。所以vex还是非常强大的。

创建primitive需要注意的是,要为每个point再创建一个相对应的vertex,否则houdini会崩溃。

转载请注明作者和出处,谢谢。http://ymuhua.com/2016/01/25/vex-103/
25 1月

VEX Expression 基础

作者:will  网址:http://ymuhua.com/2016/01/25/vex-101/

Houdini中的Vex语言是什么?

VEX在houdini中是一种执行效率很高的语言。简而言之它执行速度非常的快,速度接近C/C++的执行速度,而且编译houdini会帮你完成。这是他的优势所在了。它的目的是方便提供给用户自定义节点,自定义材质的一种语言。
当然了,日常中我用vex语言很容易搞混,它语法和C挺相似但是有不完全像C,所以我自己有时用的时候也经常犯一些愚蠢的语法问题。如下图。

cclose

这里是sidefx官网关于Vex的解释:

http://www.sidefx.com/docs/houdini15.0/vex/_index

Vex Expression是什么?

俗称vex的表达式,它是基于vex语法,大概是houdini12可以写在以下节点里面的语言,比如 Point Wrangle, Attrib Wrangle ; Geometry Wrangle, Gas Field Wrangleparticle dynamics nodes.我们可以直接将vex写在这些节点里面。

vex表达式运行是基于物体的((point, particle, edge, primitive, voxel),通过vex表达式可以很方便访问物体最底层的属性,并直接修改赋值。它们的出现大大方便了我们写vex表达式,同时也可以替代一些节点,如point节点,自从wrangle出现之后,我基本就不用这个节点了。
wrange

数据类型

数据类型的定义和c语言有点像又有点不像,相似的地方是声明一个变量需要定义他的类型。

数据类型
Type Definition Example
int Integer values 21, -3, 0x31, 0b1001, 0212, 1_000_000
float Floating point scalar values 21.3, -3.2, 1.0, 0.000_000_1
vector2 '二维向量',float类型 {0,0}, {0.3,0.5}
vector '三维变量' positions, directions, normals or colors (RGB or HSV) {0,0,0}, {0.3,0.5,-0.5}
array '数组' { 1, 2, 3, 4, 5, 6, 7, 8 }
struct '结构' c
matrix3 '矩阵' { {1,0,0}, {0,1,0}, {0,0,1} }
matrix '矩阵' { {1,0,0,0}, {0,1,0,0}, {0,0,1,0}, {0,0,0,1} }
string '字符' hello world
bsdf PBR shaders for information on BSDFs.

更多关于数组用法:http://www.sidefx.com/docs/houdini15.0/vex/arrays

定义属性

和c的变量定义很相似,那么下面是不同的地方。它不单可以定义变量,它还能定义属性attributes。这是vex表达式特有的。
何为属性,大家应该看着个教程之前都有一定houdini的基础了。就是基于模型元素的一些属性来表示元素性质,如质量,速度。
属性名前面必须要加@符号。

属性类型
type Syntax Example
float f@name 21.3,-3.2
vector2 (2 floats) u@name {0,0}{0.3,0.5}
vector (3 floats) v@name {0.3,0.5,-0.5}
vector4 (4 floats) p@name {0,0,0,1}
int i@name 21,-3,0x31
matrix2 (2×2 floats) 2@name
matrix3 (3×3 floats) 3@name { {1,0,0},{0,1,0},{0,0,1}}
matrix (4×4 floats) 4@name
string s@name hello world

注意:在声明属性的时候,等号的右边不能函数,变量、运算符(个人认为很不解的地方)

attributes

访问和修改属性属性:

注意:在赋值vector的时候如果右边有运算符或者调用函数,不能用{}。要用set()

houdini本身会自定义一些预设属性,所以我们在定义自己的属性的时候最好避开这些命名,如果你想更改预设属性也可以,名字要匹配(区分大小写),类型也一定要对上才能完成修改。

houdini预设属性
VEX type Attribute names
vector (3 floats) @P,@accel,@center,@dPdx,@dPdy,@dPdz
@Cd,@N,@scale,@force,@rest,@torque,@up,@uv,@v
vector4 (4 floats) @backtrack,@orient,@rot
int @id,@ix,@iy,@iz,@nextid,@pstate,@resx,@resy,@resz
@ptnum,@vtxnum,@primnum,@numpt,@numvtx,@numprim,@group_*
string @name,@instance,@OpInput1,@OpInput2,@OpInput3,@OpInput4

注意,这里某些预设的属性他们作用域不是全局的,是局部的,只针对当前节点,如果这个节点支持这个属性那么,我们才可以调用。

全局变量

和HScript的表达式不同, 你不能在vex中使用$F(我经常搞混这里).

要改成这些命名了。这些是全局的,你可以在所有类型的wrangle都能用。

@Time Float time ($T)
@Frame Float frame ($FF)
@SimTime Float simulation time ($ST), only present in DOP contexts.
@SimFrame Float simulation frame ($SF), only present in DOP contexts.
@TimeInc Float time step (1/$FPS)

操作符

Vex操作符和c相似,下面主要是区别一些和c不同的地方。

vector相乘的结果是vector每个元素之间的相乘

当两个不同类型的变量相加时,结果数据类型和第二个数据类型相匹配 for example

点符号Dot operator

可以用来表示一个向量每个元素。

  • .x or .u 表示vector2的第一个元素

  • .x or .r 表示vector and vector4的第一个元素

  • .y or .v 表示vector2的第二个元素

  • .y or .g 表示vector and vector4的第二个元素

  • .z or .b 表示vector and vector4的第三个元素

  • .w or .a 表示vector4的第四个元素

对于 matrices, 你可以使用以下:

  • .xx 表示 [0][0]元素

  • .zz 表示 [2][2]元素

  • .ax 表示 [3][0] 元素

保留关键字

break, bsdf, char, color, const, continue, do, else, export, false, float, for, forpoints, foreach, gather, hpoint, if, illuminance, import, int, integer, matrix, matrix2, matrix3, normal, point, return, string, struct, true, typedef, union, vector, vector2, vector4, void, while

 

转载请注明作者和出处,谢谢。http://ymuhua.com/2016/01/25/vex-101/
19 1月

Jetter Sampling Antialiasing 随机采样抗锯齿(二)

在抗锯齿第一章我们讲了均匀采样。如,将一个像素点分成5*5的子格子分别进行光线采样。

organiti

他的缺点就是太平均了,可能会出现一些奇怪的波纹。大自然都是无规律的形状,所以我们也要随机话。

jettersample

a图,在一个像素点随机取25个点进行光线采样,缺点是点很不平均。

b图,更均匀的分布,原理如c图将一个像素分割成5*5的格子,然后在每个子格子中采样点进行光线采样。即随机,又均匀。

代码修改很简单。只要将前一章的

q+0.5   p+0.5 替换成 q+rand_float()  p+rand_float(),rand_float()范围是0到1

 

15 1月

抗锯齿 Antialiasing(一)

抗锯齿,也译为抗锯齿或边缘柔化、消除混叠、抗图像折叠有损等。它是一种消除显示器输出的画面中图物边缘出现凹凸锯齿的技术。

这个技术是为了在保证低分辨的情况下,把图形的边缘变得更平滑,过渡更自然。

其实我最先遇到这个技术还是在小时候玩游戏的时候遇到的。尤其是那些大型三维游戏。那时候家里穷,买不起牛逼的显卡,但是又想玩,所以只能把游戏的分辨率调到最低,然后在显示选项里面把抗锯齿给关了,然后忍受的满屏的狗牙还玩的乐此不疲。最佩服自己的还是在一台只有两兆显存的电脑上,把生化危机3给通关了,全程帧速率不足10帧,就像在玩幻灯片一样,有个好处是你有足够的反映时间,里面那个追击者很难追上你,很怀念小时候的时光啊。

言归正转,以下三张图,最左边是没有抗锯齿,右边两张图是经过抗锯齿的,我们可以看到右边两张图是经过虚化处理。看起来边缘的过渡更平滑。

antitri

我先来介绍实现抗锯齿最简单的一个方法。

我们知道光线追踪是根据点采样产生的,我们每采样一个点,就在那个点上射出一根光线,之前我们介绍的是我们从每个像素的中心点作为一个光线的起点射出,虽然点在空间中是可以无限小的点,但是他在空间中也必须代表一块有限大小的面积。我们上一章一个中心点就代表这整个像素的结果,如果它射出去遇到红色的球,那么一整块像素就是红色的,但是这么做是很不精确的,尤其是在你像素点很大的情况下。

aniti1 anti2

上面两张图左图是理想状态下,右图是根据实际像素所采样的结果,图a的A像素,我们看到他2/3的面积是被黑色的背景覆盖,而1/3的面积是被黄色所覆盖,但是图b的A像素的中心点是在背景中,所以沿着中心点射出,我们必定遇不到黄色的模型。所以是黑色。

现在我们想,如果让这个A像素显示一个1/3的黄色的话不是更能够代表这个像素的真实情况吗。就像下图。

anti

那我们就需要将一个像素在分割成更小的像素。

aniti1G

如上图,像素A又被分割成9个小像素,然后我们再从这9个像素射出9个光线,然后,我们将这9个像素射出返回的值求他们的一个平均值给到像素A。我们就能得到一个光滑的边缘了。

anti

然后,我们来改一下代码。
假设我们采样3*3,也就是将每个像素点再划分成9小格,横向3个,纵向3个,定义n=3,n*n=9,也就是说我们在每次循环再增加9次光线碰撞计算,

Done

resultanit

当然了,这是最最基础抗锯齿的算法,速度也是最慢的,但是不关怎么着,我们有了第一步的图像优化!

接下俩又是思考题,如果多个物体的抗锯齿,尤其是叠加在一起的物体怎么算?

multanit

留给大家思考,有问题欢迎联系我