[转]3D开端 RayCasting

[转]3D开端 RayCasting

3D开端 RayCasting
 
 
 
 
       很佩服卡马克,他所独立研究出的图形学算法,几乎涉及图形学这门最令我头大的学科的各个领域。是他将Wolfenstein 3D搬上了286这样老古董的机型,是他将FPS带入了我们的生活。从1992年Wolfenstein 3D发售至今10多年时间,仅凭一个人的力量就推动了图形学及计算机硬件的发展,他是美国创业梦及个人英雄主义的完美体现。
 
 
RayCasting 射线追踪
      从Wolfenstein 3D到DOOM3,我又重玩了一遍,技术进步的轨迹清晰可见。卡马克是个天才,但他技术的高楼并不是凭空建立,他的聪明才智加上他的专注造就了今天的卡马克及DOOM3。追随他的足迹,我想探究天才造就的秘密,那就先从RayCasting说起吧!
      在当时286 386时代,CPU速度的低下是不可能在实时的状态下运行真正的3D引擎的,RayCasting算法的出现是第一个解决之道。由于它只需要对每条垂线进行必要的计算,所以它能够运行的很快。
 
      Wolfenstein 3D的射线追踪引擎非常的有限,所有的墙必须是相同的高度,而且在2D平面他们必须是正方形的格子。就像在Wolfenstein 3D的地图编辑器里看到的那样。
 
      像梯子,跳跃和高度差这样的东东在这个引擎里是不被实现的。在DOOM里虽然也使用了射线追踪引擎,但是更高级一些,可以实现例如斜的墙,不同的高度,地板及天花板以及透明的墙等。游戏里人物及物品等都使用了2D的贴图,就像公告牌一样。
      这里说明一下RayCasting并不是RayTracing!RayCasting是一种伪3D技术,是使得3D场景可以在比较低速的CPU上运行的一种解决办法;而RayTracing是一种真实3D场景的实时渲染技术,在真实的3D场景里他被用作映像及阴影的计算,它需要很高速的CPU才能完成计算。
主要思想:
      RayCasting的主要思想是:地图是2D的正方形格子,每个正方形格子用0代表没有墙,用1 2 3等代表特定的墙,用来做纹理映射。
int worldMap[mapWidth][mapHeight]= {
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,0,0,0,0,0,2,2,2,2,2,0,0,0,0,3,0,3,0,3,0,0,0,1,
1,0,0,0,0,0,2,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,0,0,0,0,0,2,0,0,0,2,0,0,0,0,3,0,0,0,3,0,0,0,1,
1,0,0,0,0,0,2,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,0,0,0,0,0,2,2,0,2,2,0,0,0,0,3,0,3,0,3,0,0,0,1,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,4,4,4,4,4,4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,4,0,4,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,4,0,0,0,0,5,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,4,0,4,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,4,0,4,4,4,4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,4,4,4,4,4,4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
};
      从Player的位置发出一条射线,沿着Player视角的方向向前与地图Tile进行碰撞检测,当这条射线碰到了墙,记录下碰撞点跟Player的距离,使用这个距离来计算这堵墙在屏幕上应该是多高。大家都知道Player离墙越远,肯定墙就越低,反之则越高。这些只需要2D计算就可以了,下图显示了这个原理。
 
 
碰撞点的判定:
     因为这条射线上有无数个点,但我们不可能取无数个点来判定是否碰到了墙,所以如何取点就变得很重要。这时候就该我们的图形学出马啦!因为碰撞点只可能在水平线上或垂直线上,所以我们可以利用DDA来做。什么,你不知道什么是DDA,还不赶快拿出图形学来狂补一下。
     DDA(Digital Differential Analysis 数字微分分析法)通俗来讲就是增量计算。如下图检测点为红点:
 
     这里就不再讲述DDA的算法啦,有兴趣的朋友可以参看图形学。
     检测这些点是否碰到了墙应该是件容易的事,当发现了碰撞点,距离也就很好计算出来了吧!
定义视域?
     接下来我们要定义Player的视域,也就是视野范围。首先需要定义一个Player的位置向量pos,Player的位置可以表示为(x, y),同时也可以把它看成一个2维向量,这样更方便考虑问题和计算。我们还需要定义一个Player的朝向向量dir,该向量从Player的位置出发,沿着Player所看去的方向,其长度并不重要,只要我们把该向量数乘一个标量就可以很方便的改变其长度,而方向却不变。另外我们还需要定义一个摄像机向量plane,用来代表计算机的屏幕,所以dir总是与plane相垂直并且指向屏幕的里面,如下图:
 
     绿点代表Player的位置;黑线代表dir向量;黑点代表dir与plane的交点,所以其位置应该是dir+pos;蓝线代表全部的摄像机向量,所以plane应当从黑点开始向右到蓝点结束。所以右面的蓝点位置应该为黑点向量加上plane既pos+dir+plane,左面蓝点的位置应当为pos+dir-plane;红线代表一些射线,其向量很容易被计算:dir+部分plane。例如从左面数第三条红线,其与plane的交点在plane的1/3处,所以其向量应为dir+1/3*plane。
     左右边界的红线定义了一个可视范围,所以可视范围的定义跟两个向量有关:plane和dir。如果dir的长度等于plane的长度,可视范围的角度将会是90度,如果dir的长度大于plane的长度,可视范围的角度将小于90度,这时候物体将远离我们,我们看到的物体将会变小;如果dir的长度小于plane的长度,可是范围的角度将大于90度,这时候物体将被拉进,我们看到的物体将被放大。
     如果Player需要旋转的话,其摄像机向量plane及方向向量都进行了旋转,我们可以乘上下面的矩阵来做到这一点:
[ cos(a) -sin(a) ]
[ sin(a) cos(a) ]
 
 
 
 
     到现在为止,我们所探讨的都是在一个2维的平面上,包括位置向量,朝向向量,摄像机向量。他们都是2维向量,我们可以像上图那样在一个平面上就将其画出来。这是一个伪3维空间,但他已经具备了一些基本的要素。在后来的发展中,2维向量加入了Z分量而变成了3维向量,朝向向量变成了Z轴,摄像机向量不再是一条线,而演化成了一个平面,需要U和V两个向量来确定。从这里我们可以看出任何的技术都不是空中楼阁,卡马克也并非生来都通晓图形学,他们都需要时间和智慧的积淀来发展。
 
 

Leave a Reply

Your email address will not be published. Required fields are marked *