向量几何在游戏编程中的使用


<1>简单的 2-D 追踪 -Twinsen 编写 -本人水平有限,疏忽错误在所难免,还请各位数学高手、编程高手不吝赐教 -我的 Email-address: popyy@netease.com Andre Lamothe 说:“向量几何是游戏程序员最好的朋友”。一点不假,向量几何在游戏编程中的地位不容忽 视,因为在游戏程序员的眼中,显示屏幕就是一个坐标 系,运动物体的轨迹就是物体在这个坐标系曲线运动结 果,而描述这些曲线运动的,就是向量。使用向量可以很好的模拟物理现象以及基本的 AI。 现在,先来点轻松的,复习一下中学知识。 向量 v(用粗体字母表示向量)也叫矢量,是一个有大小有方向的量。长度为 1 的向量称为单位向量,也叫幺矢, 这里记为 E。长度为 0 的向量叫做零向量,记为 0,零向量没有确定方向,换句话说,它的方向是任意的。 一、向量的基本运算 1、向量加法:a+b 等于使 b 的始点与 a 的终点重合时,以 a 的始点为始点,以 b 的终点为终点的向量。 2、向量减法:a-b 等于使 b 的始点与 a 的始点重合时,以 b 的终点为始点,以 a 的终点为终点的向量。 3、 数量乘向量:k*a,k>0 时,等于 a 的长度扩大 k 倍;k=0 时,等于 0 向量;k<0 时,等于 a 的长度扩大|k| 倍然后反向。 4、向量的内积(数量积、点积): a.b=|a|*|b|*cosA 等于向量 a 的长度乘上 b 的长度再乘上 a 与 b 之间夹角 的余弦。 它的几何意义就是 a 的长度与 b 在 a 上的投影长度的乘积,或者是 b 的长度与 a 在 b 上投影长的乘积,它是 一个标量,而 且可正可负。因此互相垂直的向量的内积为 0。 5、向量的矢积(叉积): a x b = |a|*|b|*sinA*v = c, |a|是 a 的长度,|b|是 b 的长度,A 是 a 和 b 之间的 锐夹角,v 是与 a,b 所决定的平面垂直的幺矢,即 axb 与 a、b 都垂直。a,b,c 构成右手系,即右手拇指伸直,其 余四指按由 a 到 b 的锐角蜷曲,此时拇指所指方向就是 c 的方向。因此 axb!=bxa,bxa 是手指朝 b 到 a 的锐角蜷 曲时,拇指指向的方向,它和 c 相反,即-c。a x b 的行列式计算公式在左右手坐标系下是不同的,如上图所 示。两个向量的矢积是一个向量。 6、正交向量的内积:互相垂直的两个向量是正交的,正交向量的内积为零。a.b = |a|.|b|*cos(PI/2) = |a|.|b|*0 = 0。 二、向量的性质 没有下面的这些性质做基础,我们后面向量技巧的推导将无法进行。 1) a + b = b + a 2) (a + b) + c = a + (b + c) 3) a + 0 = 0 + a = a 4) a + (-a) = 0 5) k*(l*a) = (k*l)*a = a*(k*l) 6) k*(a + b) = k*a + k*b 7) (k + l)*a = k*a + l*a 8) 1*a = a 9) a.b = b.a 10)a.(b + c) = a.b + a.c 11)k*(a.b) = (k*a).b = a.(k*b) 12)0.a = 0 13)a.a = |a|^2 三、自由向量的代数(分量)表示 1、向量在直角坐标中的代数表示方法: a=(x,y) 其中 x,y 分别是向量在 x 轴和 y 轴上的分量。任何一个在直角坐标轴上的分量为(x,y)的向量都相等。比如上图 中的每个向量都表示为(-2,1)。 或者写成 a=x*i+y*j,即 i 和 j 的线性组合,这里 i 是 x 轴方向的单位向量(1,0),j 是 y 轴方向的单位向量(0,1), 因此 i 正交于 j。任意一个 2-D 向量都可以表成 i 与 j 的线性组合。 |i| = |j| = 1 2、向量的代数(分量)表示的运算: 向量加法分量表示:a+b=(xa,ya)+(xb,yb)=(xa+xb,ya+yb) 向量减法分量表示:a-b=(xa,ya)-(xb,yb)=(xa-xb,ya-yb) 向量的内积(数量积、点积)分量表示: a.b =(xa * i + ya * j).(xb * i + yb * j) = xa * i * xb * i + xa * i * yb * j + ya * j * xb * i + ya * j * yb * j =(xa * xb) * (i * i) + (xa * yb) * (i * j) + (xb * ya) * (i * j) + (ya * yb) * (j * j) = xa * xb + ya * yb 3、向量长度(模)的计算以及单位化(归一化): 设 a=(x,y),则 |a| = |(x,y)| = |x*i + y*j| = sqrt(x^2*i^2 + y^2*j^2) = sqrt(x^2 + y^2),这里 sqrt 是开平方符号。 a 的单位向量为 a/|a|,即(x,y)/sqrt(x^2 + y^2)。 四、简单的 2-D 追踪 现在,有了向量的基本知识,我们就可以分析一个常见的问题-屏幕上一点到另一点的追踪,其实这一问题也可 理解为画线 问题,画线的算法有很多:DDA 画线法、中点画线法以及高效的 Bresenham 算法。但这些算法一般 只是画一些两端固定的线段时所使用的方法,再做一些 动态的点与点之间的跟踪时显得不很灵活。使用向量的 方法可以很好的解决此类问题。 现在假设你正在编写一个飞行射击游戏,你的敌人需要一种 很厉害的武器-跟踪导弹,这种武器在行进的同时 不断的修正自己与目标之间的位置关系,使得指向的方向总是玩家,而不论玩家的位置在哪里,这对一个水平 不高 的玩家(我?)来说可能将是灭顶之灾,玩家可能很诧异敌人会拥有这么先进的秘密武器,但对于你来说 只需要再程序循环中加入几行代码 ,它们的原理是向量的单位化和基本向量运算。 首先我们要知道玩家的位置(x_player, y_player),然后,我们的导弹就可以通过计算得到一个有初始方向的 速度,速度的方向根据玩家的位置不断修正,它的实质是一个向量减法的计算过程。 速度的大小我们自己来设 置,它可快可慢,视游戏难易度而定,它的实质就是向量单位化和数乘向量的过程。具体算法是:导弹的更新 速度 (vx_missile, vy_missile) = 玩家的位置(x_player, y_player) - 导弹的位置(x_missile, y_missile), 然后再对(vx_missile, vy_missile)做缩小处理,导弹移动,判断是否追到玩家,重新更新速度,缩小... 看一下这个简单算法的代码: // 假设 x_player,y_player 是玩家位置分量 // x_missile,y_missile 是导弹位置分量 // xv_missile,yv_missile 是导弹的速度分量 // 让我们开始吧! float n_missile ; // 这是玩家位置与导弹位置之间向量的长度 float v_rate ; // 这是导弹的速率缩放比率 // 计算一下玩家与导弹之间的位置向量 xv_missile = x_player-x_missile ; // 向量减法,方向由导弹指向玩家,x 分量 yv_missile = y_player-y_missile ; // y 分量 // 计算一下它的长度 n_missile = sqrt( xv_missile*xv_missile + yv_missile*yv_missile ) ; // 归一化导弹的速度向量: xv_missile /= n_missile ; yv_missile /= n_missile ; // 此时导弹的速率为 1,注意这里用速率。 // 导弹的速度分量满足 xv_missile^2+yv_missile^2=1 // 好!现在导弹的速度方向已经被修正,它指向玩家。 // 由于现在的导弹速度太快,为了缓解一下紧张的气氛,我要给导弹减速 v_rate = 0.2f ; // 减速比率 xv_missile *= v_rate ; // 这里的速率缩放比率,你可以任意调整大小 yv_missile *= v_rate ; // 可以加速:v_rate 大于 1;减速 v_rate 大于 0 小于 1,这里就这么做! // 导弹行进!导弹勇敢的冲向玩家! x_missile += xv_missile ; y_missile += yv_missile ; // 然后判断是否攻击成功 现在,你编写的敌人可以用跟踪导弹攻击玩家了。你也可以稍加修改,变为直线攻击武器。这样比较普遍。 基本的跟踪效果用向量可以很好的模拟。 此时,我们只用到了所述向量知识的很少的一部分。其他的知识会慢慢用到游戏中。这次先介绍到这里。 下次我将说说利用向量模拟 2-D 物体任意角度返弹的技巧:)但是!别忘了复习一下向量的基础知识,我们要 用到它们。 <2>2-D 物体任意角度的反弹 -Twinsen 编写 -本人水平有限,疏忽错误在所难免,还请各位数学高手、编程高手不吝赐教 -我的 Email-address: popyy@netease.com 第一次我说了一下向量知识的基础内容和一点使用技巧,浅显的展示了它在游戏编程中的作用。这次深入一些, 充分利用向量的性质模仿一个物理现象。 首先,我要介绍一下将要使用的两个基本但非常重要的技巧。 一、求与某个向量a正交的向量b 根据向量内积的性质以及正交向量之间的关系,有: 设a=(xa,ya),b=(xb,yb) a.b = 0 => xa*xb + ya*yb = 0 => xa*xb = -ya*yb => xa/-ya = yb/xb => xb = -ya , yb = xa 或 xb = ya , yb = -xa 则向量(xa,ya)的正交向量为(xb,yb)=(-ya,xa) 比如上图中,向量(2,3)的逆时针旋转 90 度的正交向量是(-3,2),顺时针旋转 90 度的正交向量为(3,-2)。 这样,任给一个非零向量(x,y),则它相对坐标轴逆时针转 90 度的正交向量为(-y,x),顺时针转 90 度的正交向 量为(y,-x)。 二、计算一个向量b与另一向量a共线的两个相反的投影向量 我们看一下上面的图,很明显,cosA(A=X)关于y轴对称,是偶函数,因此cosA = cos(-A), 又因为cosA是周期函数,且周期是 2*PI,则有cos(A+2*PI) = cosA = cos(-A) = cos(-A+2*PI), 则根据cosA = cos(2*PI-A)以及a.b = |a|*|b|*cosA,有 a.b = |a|*|b|*cosA = |a|*|b|*cos(2*PI-A) 现在,根据上图,就有a.b = |a|*|b|*cosA = |a|*|b|*cos(2*PI-A) = ax*bx + ay*by 按照这个规则,当上面的b与c的模相等时,有|a|*|b| = |a|*|c|,进一步的,当它们与a的夹角A = B时,就有 a.b = |a|*|b|*cosA = |a|*|c|*cosB = a.c ,相应的有 a.b = |a|*|b|*cosA = |a|*|b|*cos(2*PI-A) = |a|*|c|*cosB = |a|*|c|*cos(2*PI-B) = a.c 也就是 ax*bx + ay*by = ax*cx + ay*cy 我们还注意到在一个周期内,比如在[0,2*PI]中,cosA有正负两种情况,分别是:在(0,PI/2)&(3*PI/2, 2*PI) 为正,在(PI/2,3/2*PI)为负。好,知道了这件事情之后,再看a.b = |a|*|b|*cosA,|a|和|b|都为正,所以a.b 的正负性就由cosA决定,换句话说,a.b与它们夹角A的余弦cos有相同的符号。所以,还看上面的图,我们就有: 1)当A在(0, PI/2)&(3*PI/2, 2*PI)中,此时 2*PI-A在(-PI/2,0)&(0, PI/2)中,a.b为正 2)当A在(PI/2, 3*PI/2)中,此时 2*PI-A也在(PI/2, 3*PI/2)中,a.b为负 现在我们再来看一下同模相反(夹角为PI)向量b和b'与同一个向量a的两个内积之间有什么关系。 首先B + B'= 2*PI - PI = PI,所以有b = -b', b' = -b,即 (bx, by) = (-b'x, -b'y) = -(b'x, b'y) (b'x, b'y) = (-bx, -by) = -(bx, by) 所以 a.b =(ax, ay) . (bx, by) = (ax, ay) . -(b'x, b'y) = a.-b'= -(a.b') a.b'= (ax, ay) . (b'x, b'y) = (ax, ay) . -(bx, by) = a.-b = -(a.b) 我们看到,一个向量b的同模相反向量b'与向量a的内积a.b',等于b与a的内积的相反数-(a.b)。 好,有了上面的基础,我们就可以求一个向量b与另一向量a共线的两个相反的投影向量c和c'了。 要求b在a上的投影向量c,我们可以用一个数乘上一个单位向量,这个单位向量要和a方向一至,我们记为a1。而 这个数就是b在a上的投影长。 先来求单位向量a1,我们知道它就是向量a乘上它自身长度的倒数(数乘向量),它的长度我们 可以求出,就是m = sqrt(ax^2 + ay^2),所以a1就是(ax/m, ay/m),记为(a1x, a1y)。 再求投影长/c/(注意//与||的区别,前者是投影长,可正可负也可为零,后者是实际的长度,衡为非负)。 根 据内积的几何意义:一个向量b点乘另一个向量a1,等 于 b在a1上投影长与a1的长的乘积。那我们要求b在a上的投 影长,就用它点乘a的单位向量a1就可以了,因为单位向量的长度为 1,b的投影长/c/乘上 1 还等于投影长自身, 即: /c/ = b.a1 = (bx, by) . (a1x, a1y) = bx * a1x + by * a1y 好,我们得到了c的投影长,现在就可以求出c: c = /c/*a1 = ( (bx * a1x + by * a1y)*a1x, (bx * a1x + by * a1y)*a1y ) 总结一下,就是c = (b.a1)*a1。 我们看到,b与a1的夹角在(0, PI/2)之间,因此它们的点积/c/是个正值。因此当它乘a1之后,得到向量的方向 就是a1的方向。 现在来看b',它是b的同模相反向量,它和a1的夹角在(PI/2, 3*PI/2)之间,因此b'点乘a1之后得到/c'/是个负 值,它再乘a1,得到向量的方向和a1相反。我们知道,一个向量b的同模相反向量b'与向量a的内积a.b',等于b 与a的内积的相反数-(a.b)。因此,/c'/ = -/c/,也就是说,它们的绝对值相等,符号相反。因此它们同乘一 个a1,得到的的两个模相等向量c与c'共线。 让我们把它完成: (b'.a1) = -(b.a1) => -(b'.a1) = (b.a1), 好,代入c = (b.a1)*a1,得到 c = -(b'.a1)*a1 => (b'.a1)*a1 = -c = c' c = ( b . a1 ) * a1 = (-b'. a1) * a1 c'= ( b'. a1 ) * a1 = (-b . a1) * a1 至此为止,我们得出结论:当一个向量b与另一个向量a的夹角在(0, PI/2)&(3*PI/2, 2*PI)之间,它在a方向上 的投影向量c就是c = ( b . a1 ) * a1,其中a1是a的单位向量;它在a相反方向的投影向量c'是c'= ( b'. a1 ) * a1,其中向量b'是b的同模相反向量。 相反的,也可以这样说:当一个向量b'与另一个向量a的夹角在(PI/2, 3*PI/2)之间,它在a相反方向上的投影向 量c'是 c'= ( b'. a1 ) * a1,其中 a1是a的单位向量;它在a方向上的投影向量c是c = ( b . a1 ) * a1。其中向量b 是b'的同模相反向量。 特别的,点乘两个单位向量,得到它们夹角的余弦值: E.E = |E|*|E|*cosA = 1*1*cosA = cosA 好了,可完了。 现在就可以看一下 三、使用向量模拟任意角度反弹的原理 根据初等物理,相互接触的物体在受到外力具有接触面相对方向相对运动趋势的时候,接触面会发生形变从而 产生相互作用的弹力。 弹力使物体形变或形变同时运动形式发生改变。在知道了这件事情之后,我们开始具体讨论下面这种情况: 矩形框和小球碰撞,碰撞时间极短,墙面无限光滑从而碰撞过程没有摩擦,碰撞时间极短,没有能量损失... 总之是一个理想的物理环境。我们在这种理想环境下讨论,小球与墙面发生了完全弹性碰撞,且入射角和反射 角相等:A=A',B=B',C=C',...。虚线是法线,它和墙面垂直。小球将在矩形框中永无休止的碰撞下去,且每次 碰撞过程中入射角和反射角都相等。 我 们再具体点,现在假设上面那个矩形墙壁的上下面平行于x轴,左右面平行于y轴。这样太好了,我们在编写 程序的时候只要判断当球碰到上下表面的时候将y方向 速度值取返,碰到左右表面时将x方向速度值取返就行 了,这种方法常常用在简单物理模型和规则边界框的游戏编程上,这样可以简化很多编程步骤,编写简单游戏 时 可以这样处理。可事实不总是像想向中的那么好。如果情况像下面这样: 虽然在碰撞过程中入射角仍然等于反射角,但是边界的角度可没那么“纯”了,它们的角度是任意的,这样就 不能简单的将x方向或者y方向的速度取返了,我们要另找解决办法。 我们现在的任务是:已知物体的速度向量S和边界向量b,求它的反射向量F。我们先来看一下在碰撞过程中都有 哪些向量关系: 设b是障碍向量,S是入射速度向量,F是反射速度向量,也就是我们要计算的向量。A是入射角度,A'是反射角 度,A=A'。N是b的法向量,即N垂直于b。n是与N共线的向量,n'是N方向的单位向量。T是垂直于N的向量。根据 向量加法,现在有关系: (1) S + n = T (2) n + T = F 合并,得 F = 2*T - S 我们已经找到了计算F的公式了。这里S是已知的,我们要计算一下T,看(1)式: T = S + n 要计算T,S是已知的,就要计算一下n。我们知道,n是S在N方向上投影得到的,S已知所以要得到n就要再计算 一下N,而N又是和b垂直的。还记得刚才我们导出的使用向量的两个技巧吧,这里我们都要用到: 1、任给一个非零向量(x,y),则它相对坐标轴逆时针转 90 度的垂直向量为(-y,x),顺时针转 90 度垂直向量为 (y,-x)。 2、当一个向量b与另一个向量a的夹角在(0, PI/2)&(3*PI/2, 2*PI)之间,它在a方向上的投影向量c就是c = ( b . a1 ) * a1,其中a1是a的单位向量;它在a相反方向的投影向量c'是c'= ( b'. a1 ) * a1,其中向量b'是b的同 模相反向量。 我们知道了b,用技巧1 可以计算出N。然后归一化N计算出n',再用技巧 2,这里S和n'之间的夹角在(PI/2, 3*PI/2) 中,因此要想用c = ( b. a1 ) * a1,必须要使b = -S,a1=n'。这样就计算出了n。然后根据上面的(1)式计算 出T,好了,有了T和F = 2*T - S ,你就拥有了一切! 计算出的F就是物体碰撞后的速度向量,在 2-D中它有两个分量x和y,3-D中有x,y,z三个分量。这里也证明了使 用向量的一个好处就是在一些类似这样关系推导过程中不用去考虑坐标问题,而直接的用简单的向量就可以进 行。 这里注意我们的障碍向量b在实际的编程中是用障碍的两个端点坐标相减计算出的,计算的时候不需要考虑相减 的顺序问题。因为虽然用不同的相减顺序得到b的方向相反,且计算得到的单位法向量n'方向也相反(看上图的 虚线部分),但是当用-S去点乘单位法向量n'之后得到的值也是相反的,它有一个自动的调节功能:现在假设 以b为界,S一侧为正方向。则如果单位法向量n'是正方向,与-S点积值也是正,正的n'再乘正点积得正的n;如 果单位法向量为负方向,与-S点积值也为负值,负的n'再乘负的点积得到的n为正方向。总之n的方向是不变的, 算出的F当然也是不变的。 四、编码实现它 现 在我想编码实现它,但之前有一点我想说一下,可能读者已经想到了,在反弹之前我们要先判断什么时候开 始反弹,也就是什么时候碰撞,这是一个碰撞检测问题, 本来这是我们应该先要解决的问题,但我想把它放到 下一次在具体说,所以这里的编码省略碰撞检测的一步,直接计算反弹速度向量!目的是把上述理论迅速用到 算 法中去。 // 在游戏循环中 // 移动的物体简化为质点,位置是x=0.0f,y=0.0f // 质点速度向量的分量是Svx=4.0f,Svy=2.0f // 障碍向量是bx=14.0f-6.0f=8.0f,by=4.0f-12.0f=-8.0f // 则障碍向量的垂直向量是Nx=-8.0f,Ny=-8.0f // 这里可以加入碰撞检测 // 现在假设已经碰撞完毕,开始反弹计算! // 计算N的长度 float lengthN = sqrt( Nx*Nx + Ny*Ny ) ; // 归一化N为n' float n0x = Nx / lengthN ; // n0x就是n'的x分量 float n0y = Ny / lengthN ; // n0y就是n'的y分量 // 计算n,就是S在N方向上的投影向量 // 根据b'= (-b.a1').a1',有n = (-S.n').n' float nx = -(Svx*n0x+Svy*n0y)*n0x ; // n的x分量 float ny = -(Svx*n0x+Svy*n0y)*n0y ; // n的y分量 // 计算T // T = S + n float Tx = Svx + nx ; // T的x分量 float Ty = Svy + ny ; // T的y分量 // 有了T,有了F = 2*T - S,好了,你现在拥有一切了 // 计算F float Fx = 2*Tx - Svx ; // F的x分量 float Fy = 2*Ty - Svy ; // F的y分量 // 现在已经计算出了反弹后的速度向量了 // 更新速度向量 Svx = Fx ; Svy = Fy ; // 质点移动 x+=Svx ; y+=Svy ; // 现在你就可以看到质点被无情的反弹回去了 // 而且是按照物理法则在理想环境下模拟 就是这么简单,一个物理现象就可以模拟出来,但是还不完善,只是针对直线障碍,且没有碰撞检测,下次分 析一下后者,还是用向量的知识。这次先到这,See u next time! <3>2-D 边界碰撞检测 -Twinsen 编写 -本人水平有限,疏忽错误在所难免,还请各位数学高手、编程高手不吝赐教 -我的 Email-address: popyy@netease.com 一、使用向量进行障碍检测的原理 上次说了使用向量模拟任意角度的反弹,这次谈谈它的前提---障碍碰撞。 在游戏中进行障碍碰撞检 测,基本思路是这样的:给定一个障碍范围,判断物体在这次移动后会不会进入这个 范围,如果会,就发生碰撞,否则不发生碰撞。在实际操作中,是用物体的边界 来判断还是其他部位判断完全 取决于编程者。这时候,就可以从这个部位沿着速度的方向引出一条速度向量线,判断一下这条线段(从检测 部位到速度向量终点)和 障碍边界线有没有交点,如果有,这个交点就是碰撞点。 上面物体 A,在通过速度向量移动之后将到达 B 位置。但是,这次移动将不会顺利进行,因为我们发现,碰撞 发生了。碰撞点就在那个红色区域中,也就是速度向量和边界线的交点。 我们接下来的工作就是要计算这个交 点,这是一个解线性方程组的过程,那么我们将要用到一样工具... 二、一个解线性方程组的有力工具---克兰姆(Cramer)法则 首先要说明一下的是,这个法则是有局限性的,它必须在一个线性方程组的系数行列式非零的时候才能够使用。 别紧张,我会好好谈谈它们的。首先让我来叙述一下这个法则(我会试着让你感觉到这不是一堂数学课): 如果线性方程组: A11*X1 + A12*X2 + ... + A1n*Xn = b1 A21*X1 + A22*X2 + ... + A2n*Xn = b2 ................................... An1*X1 + An2*X2 + ... + Ann*Xn = bn 的系数矩阵 A = __ __ | A11 A12 ... A1n | | A21 A22 ... A2n | | ............... | | An1 An2 ... Ann | -- -- 的行列式 |A| != 0 线性方程组有解,且解是唯一的,并且解可以表示为: X1 = d1/d , X2 = d2/d , ... , Xn = dn/d (这就是/A/=d为什么不能为零的原因) 这里d就是行列式/A/的值,dn(n=1,2,3...)是用线性方程组的常数项b1,b2,...,bn替换系数矩阵中的第n列的值 得到的矩阵的行列式的值,即: | b1 A12 ... A1n | d1 = | b2 A22 ... A2n | | .............. | | bn An2 ... Ann | | A11 b1 ... A1n | d2 = | A21 b2 ... A2n | | .............. | | An1 bn ... Ann | ... | A11 A12 ... b1 | dn = | A21 A22 ... b2 | | .............. | | An1 An2 ... bn | 别去点击关闭窗口按钮!我现在就举个例子,由于我们现在暂时只讨论 2-D 游戏(3-D 以后会循序渐进的谈到), 就来个 2-D 线性方程组: (1) 4.0*X1 + 2.0*X2 = 5.0 (2) 3.0*X1 + 3.0*X2 = 6.0 这里有两个方程,两个未知量,则根据上面的 Cramer 法则: | 4.0 2.0 | d = | 3.0 3.0 | = 4.0*3.0 - 2.0*3.0 = 6.0 (2 阶行列式的解法,'\'对角线相乘减去'/'对角线相乘) | 5.0 2.0 | d1 = | 6.0 3.0 | = 5.0*3.0 - 2.0*6.0 = 3.0 | 4.0 5.0 | d2 = | 3.0 6.0 | = 4.0*6.0 - 5.0*3.0 = 9.0 则 X1 = d1/d = 3.0/6.0 = 0.5 X2 = d2/d = 9.0/6.0 = 1.5 好了,现在就得到了方程组的唯一一组解。 是不是已经掌握了用 Cramer 法则解 2-D 线性方程组了?如果是的话,我们继续。 三、深入研究 这里的 2-D 障碍碰撞检测的实质就是判断两条线段是否有交点,注意不是直线,是线段,两直线有交点不一定 直线上的线段也有交点。现在我们从向量的角度,写出两条线段的方程。 现在有v1和v2两条线段,则根据向量加法: v1e = v1b + s*v1 v2e = v2b + t*v2 v1b和v2b分别是两线段的一端。s,t是两个参数,它们的范围是[0.0,1.0],当s,t=0.0 时,v1e=v1b,v2e=v2b; 当s,t=1.0 时,v1e和v2e分别是两线段的另一端。s,t取遍[0.0,1.0]则v1e和v2e取遍两线段的每一点。 那么我们要判断v1和v2有没有交点,就让v1e=v2e,看解出的s,t是不是在范围内就可以了: v1e = v2e => v1b + s*v1 = v2b + t*v2 => s*v1 - t*v2 = v2b - v1b 写成分量形式: s*x_v1 - t*x_v2 = x_v2b - x_v1b s*y_v1 - t*y_v2 = y_v2b - y_v1b 现在是两个方程式,两个未知数,则根据Cramer法则: | x_v1 -x_v2 | | 4.0 -2.0 | d = | y_v1 -y_v2 | = | 1.0 -3.0 | = -10.0 | x_v2b-x_v1b -x_v2 | | 5.0 -2.0 | d1 = | y_v2b-y_v1b -y_v2 | = | 2.0 -3.0 | = -11.0 s = d1/d = -11.0/-10.0 = 1.1 > 1.0 现在s已经计算出来,没有在[0.0,1.0]内,所以两线段没有交点,从图上看很直观。t没有必要再计算了。所以 是物体与障碍没有发生碰撞。如果计算出的s,t都在[0.0,1.0]内,则把它们带入原方程组,计算出v1e或者v2e, 它的分量就是碰撞点的分量。 四、理论上的东西已经够多的了,开始写程序 我现在要写一个用于处理障碍碰撞检测的函数,为了测试它,我还准备安排一些障碍: 这是一个凸多边形,我让一个质点在初始位置(10,8),然后给它一个随机速度,这个随机速度的两个分速度在区 间[1.0,4.0]内,同时检测是否与边界发生碰撞。当碰撞发生时,就让它回到初始位置,重新给一个随机速度。 // 首先我要记下凸多边形的边界坐标 float poly[2][8] = { { 6.0f , 2.0f , 4.0f , 8.0f , 14.0f , 18.0f , 14.0f , 6.0f } , // 所有点的 x 分量,最后一个点和第一 个点重合 { 2.0f , 6.0f , 10.0f , 14.0f , 12.0f , 8.0f , 4.0f , 2.0f } // 所有点的 y 分量 } ; // 定义一些变量 float x,y ; // 这是质点的位置变量 float vx , vy ; // 质点的速度向量分量 // 好,开始编写碰撞检测函数 bool CollisionTest() { // 当发生碰撞时返回 true,否则返回 false float s , t ; // 线段方程的两个参数 // 各个参量 float x_v1 , x_v2 , y_v1 , y_v2 ; float x_v2b , x_v1b , y_v2b , y_v1b ; for( int i = 0 ; i < 8-1 ; ++i ) { // 循环到倒数第二个点 // 障碍线段 x_v1 = poly[0][i+1]-poly[0][i] ; y_v1 = poly[1][i+1]-poly[1][i] ; // 物体速度向量 x_v2 = vx ; y_v2 = vy ; // 障碍向量初始点 x_v1b = poly[0][i] ; y_v1b = poly[1][i] ; // 物体位置 x_v2b = x ; y_v2b = y ; // 计算 d,d1 和 d2 // | x_v1 -x_v2 | //d = | y_v1 -y_v2 | // | x_v2b-x_v1b -x_v2 | //d1 = | y_v2b-y_v1b -y_v2 | // | x_v1 x_v2b-x_v1b | //d2 = | y_v1 y_v2b-y_v1b | d = (x_v1*(-y_v2))-((-x_v2)*y_v1) ; d1 = ((x_v2b-x_v1b)*(-y_v2))-((-x_v2)*(y_v2b-y_v1b)) ; d2 = (x_v1*(y_v2b-y_v1b))-((x_v2b-x_v1b)*y_v1) ; // 判断 d 是否为零 if( abs(d) < 0.001f ) // 如果等于零做近似处理,abs()用于求绝对值 d = 0.001f ; // 计算参量 s,t s = d1/d ; t = d2/d ; // 判断是否发生碰撞 // 如果发生了就返回 true if( 0.0f <= s && 1.0f >= s && 0.0f <= t && 1.0f >= t ) return true ; } // for( int i = 0 ; i < 8-1 ; ++i ) // 没有发生碰撞,返回 false return false ; } // end of function // 现在对函数做测试 // 初始化质点 x = 10.0f , y = 8.0f ; vx = vy = (float)(rand()%4+1) ; // 进入主循环中 // 假设现在已经在主循环中 if( CollisionTest() ) { // 如果物体与质点发生碰撞 x = 10.0f , y = 8.0f ; vx = vy = (float)(rand()%4+1) ; } // 质点移动 x+=vx ; y+=vy ; 现在你就可以结合上次的讨论模拟一个完整的理想物理情景:一个物体在不规则障碍中移动、反弹,永不停息... 除非... 至此为止我们讨论了 2-D 游戏的障碍碰撞检测以及它的编程实现,在此过程中涉及到了线性代数学的知识,以 后随着深入还会不断的加入更多的数学、物理知识。下次我们继续讨论,BYE! <4>2-D 物体间的碰撞响应 -Twinsen 编写 -本人水平有限,疏忽错误在所难免,还请各位数学高手、编程高手不吝赐教 -我的 Email-address: popyy@netease.com 这次我要分析两个球体之间的碰撞响应,这样我们就可以结合以前的知识来编写一款最基本的 2-D 台球游戏了, 虽然粗糙了点,但却是个很好的开始,对吗? 一、初步分析 中学时候上物理课能够认真听讲的人(我?哦,不包括我)应该很熟悉的记得:当两个球体在一个理想环境下 相撞之后,它们的总动量保持不变,它们的总机械能也守恒。但这个理想环境是什么样的呢?理想环境会不会 影响游戏的真实性?对于前者我们做出在碰撞过程中理想环境的假设: 1)首先我们要排除两个碰撞球相互作用之外的力,也就是假设没有外力作用于碰撞系统。 2)假设碰撞系统与外界没有能量交换。 3)两个球体相互作用的时间极短,且相互作用的内力很大。 有了这样的假设,我们就可以使用动量守恒和动能守恒定律来处理它们之间的速度关系了,因为 1)确保没有 外力参与,碰 撞系统内部动量守恒,我们就可以使用动量守恒定律。2)保证了我们的碰撞系统的总能量不会 改变,我们就可以使用动能守恒定律。3)两球发生完全弹性碰撞, 不会粘在一起,没有动量、能量损失。 而对于刚才的第二个问题,我的回答是不会,经验告诉我们,理想环境的模拟看起来也是很真实的。除非你是 在进行科学研究,否则完全可以这样理想的去模拟。 现在,我们可以通过方程来观察碰撞前后两球的速度关系。当两球球心移动方向共线(1-D 处理)时的速度,或 不共线(2-D 处理)时共线方向的速度分量满足: (1)m1 * v1 + m2 * v2 = m1 * v1' + m2 * v2' (动量守恒定律) (2)1/2 * m1 * v1^2 + 1/2 * m2 * v2^2 = 1/2 * m1 * v1'^2 + 1/2 * m2 * v2'^2 (动能 守恒定律) 这里 m1 和 m2 是两球的质量,是给定的,v1 和 v2 是两球的初速度也是我们已知的,v1'和 v2'是两球的末速度, 是我们要求的。好,现在我们要推导出 v1'和 v2'的表达式: 由(1),得到 v1' = (m1 * v1 + m2 * v2 - m2 * v2') / m1,代入(2),得 1/2 * m1 * v1^2 + 1/2 * m2 * v2^2 = 1/2 * m1 * (m1 * v1 + m2 * v2 - m2 * v2')^2 + 1/2 * m2 * v2'^2 => v2' = (2 * m2 * v1 + v2 * (m1 - m2)) / (m1 + m2),则 => v1' = (2 * m1 * v2 + v1 * (m1 - m2)) / (m1 + m2) 我们现在得到的公式可以用于处理当两球球心移动方向共线(1-D 处理)时的速度关系,或者不共线(2-D 处理) 时共线方向的速度分量的关系。不管是前者还是后者,我们都需要把它们的速度分解到同一个轴上才能应用上 述公式进行处理。 二、深入分析 首先我要说明一件事情:当两球碰撞时,它们的速度可以分解为球心连线方向的分速度和碰撞点切线方向的分 速度。而由于 它们之间相互作用的力只是在切点上,也就是球心连线方向上,因此我们只用处理这个方向上的 力。而在切线方向上,它们不存在相互作用的力,而且在理想环境下 也没有外力,因此这个方向上的力在碰撞 前后都不变,因此不处理。好,知道了这件事情之后,我们就知道该如何把两球的速度分解到同一个轴上进行 处理。 现在看上面的分析图,s和t是我们根据两个相碰球m1 和m2 的位置建立的辅助轴,我们一会就将把速度投影到它 们上面。v1和v2分别是m1 和m2 的初速度,v1'和v2'是它们碰撞后的末速度,也就是我们要求的。s'是两球球心 的位置向量,t'是它的逆时针正交向量。s1是s'的单位向量,t1是t'的单位向量。 我们的思路是这样的:首先我们假设两球已经相碰(在程序中可以通过计算两球球心之间的距离来判断)。接 下来我们计算一下s'和t',注意s'和t'的方向正反无所谓(一会将解释),现在设m1 球心为(m1x, m1y),m2 球 心为(m2x, m2y),则s'为(m1x-m2x, m1y-m2y),t'为(m2y-m1y, m1x-m2x)(第一篇的知识)。 则设 sM = sqrt((m1x-m2x)^2+(m1y-m2y)^2), tM = sqrt((m2y-m1y)^2+(m1x-m2x)^2),有 s1 = ((m1x-m2x)/sM, (m1y-m2y)/sM) = (s1x, s1y) t1 = ((m2y-m1y)/tM, (m1x-m2x)/tM) = (t1x, t1y) 现在s和t轴的单位向量已经求出了,我们根据向量点乘的几何意义,计算v1和v2在s1和t1方向上的投影值,然 后将s轴上投影值代 入公式来计算s方向碰撞后的速度。注意,根据刚才的说明,t方向的速度不计算,因为没有相互作用的力,因 此,t方向的分速度不变。所以我们要做的就是:把v1投影到s和t方向上,再把v2投影到s和t方向上,用公式分 别计算v1和v2在s方向上的投影的末速度,然后把得到的末速度在和原来v1和v2在t方向上的投影速度再合成, 从而算出v1'和v2'。好,我们接着这个思路做下去: 先算v1(v1x, v1y)在s和t轴的投影值,分别设为v1s和v1t: v1s = v1.s1 => v1s = v1x * s1x + v1y * s1y v1t = v1.t1 => v1t = v1x * t1x + v1y * t1y 再算v2(v2x, v2y)在s和t轴的投影值,分别设为v2s和v2t: v2s = v2.s1 => v2s = v2x * s1x + v2y * s1y v2t = v2.t1 => v2t = v2x * t1x + v2y * t1y 接下来用公式 v1' = (2 * m1 * v2 + v1 * (m1 - m2)) / (m1 + m2) v2' = (2 * m2 * v1 + v2 * (m1 - m2)) / (m1 + m2) 计算v1s和v2s的末值v1s'和v2s',重申v1t和v2t不改变: 假设m1 = m2 = 1 v1s' = (2 * 1 * v2s + v1s * (1 - 1)) / (1 + 1) v2s' = (2 * 1 * v1s + v2s * (1 - 1)) / (1 + 1) => v1s' = v2s => v2s' = v1s 好,下一步,将v1s'和v1t再合成得到v1',将v2s'和v2t再合成得到v2',我们用向量和来做: 首先求出v1t和v2t在t轴的向量v1t'和v2t'(将数值变为向量) v1t' = v1t * t1 = (v1t * t1x, v1t * t1y) v2t' = v2t * t1 = (v2t * t1x, v2t * t1y) 再求出v1s'和v2s'在s轴的向量v1s'和v2s'(将数值变为向量) v1s'= v1s' * s1 = (v1s' * s1x, v1s' * s1y) v2s'= v2s' * s1 = (v2s' * s2x, v2s' * s2y) 最后,合成,得 v1' = v1t' + v1s' = (v1t * t1x + v1s' * s1x, v1t * t1y + v1s' * s1y) v2' = v2t' + v2s' = (v2t * t1x + v2s' * s2x, v2t * t1y + v2s' * s2y) 从而就求出了v1'和v2'。下面解释为什么说s'和t'的方向正反无所谓:不论我们在计算s'时使用m1 的球心坐标 减去m2 的球心坐标还是相反的相减顺序,由于两球的初速度的向量必有一个和s1是夹角大于 90 度小于 270 度 的,而另外一个与s1的夹角在 0 度和 90 度之间或者说在 270 度到 360 度之间,则根据向量点积的定义 |a|*|b|*cosA,计算的到的两个投影值一个为负另一个为正,也就是说,速度方向相反,这样就可以用上面的 公式区求得末速度了。同时,求出的末速度也是方向相反的,从而在转换为v1s'和v2s'时也是正确的方向。同 样的,求t'既可以是用s'逆时针 90 度得到也可以是顺时针 90 度得到。 三、编写代码 按照惯例,该编写代码了,其实编写的代码和上面的推导过程极为相似。但为了完整,我还是打算写出来。 // 用于球体碰撞响应的函数,其中 v1a 和 v2a 为两球的初速度向量, // v1f 和 v2f 是两球的末速度向量。 // m1 和 m2 是两球的位置向量 // s'的分量为(sx, sy),t'的分量为(tx, ty) // s1 是 s 的单位向量,分量为(s1x, s1y) // t1 是 t 的单位向量,分量为(t1x, t1y) void Ball_Collision(v1a, v2a, &v1f, &v2f, m1, m2){ // 求出 s' double sx = m1.x - m2.x ; double sy = m1.y - m2.y ; // 求出 s1 double s1x = sx / sqrt(sx*sx + sy*sy) ; double s1y = sy / sqrt(sx*sx + sy*sy) ; // 求出 t' double tx = -sy ; double ty = sx ; // 求出 t1 double t1x = tx / sqrt(tx*tx + ty*ty) ; double t1y = ty / sqrt(tx*tx + ty*ty) ; // 求 v1a 在 s1 上的投影 v1s double v1s = v1a.x * s1x + v1a.y * s1y ; // 求 v1a 在 t1 上的投影 v1t double v1t = v1a.x * t1x + v1a.y * t1y ; // 求 v2a 在 s1 上的投影 v2s double v2s = v2a.x * s1x + v2a.y * s1y ; // 求 v2a 在 t1 上的投影 v2t double v2t = v2a.x * t1x + v2a.y * t1y ; // 用公式求出 v1sf 和 v2sf double v1sf = v2s ; double v2sf = v1s ; // 最后一步,注意这里我们简化一下,直接将 v1sf,v1t 和 v2sf,v2t 投影到 x,y 轴上,也就是 v1'和 v2'在 x,y 轴上的分量 // 先将 v1sf 和 v1t 转化为向量 double nsx = v1sf * s1x ; double nsy = v1sf * s1y ; double ntx = v1t * t1x ; double nty = v1t * t1y ; // 投影到 x 轴和 y 轴 // x 轴单位向量为(1,0),y 轴为(0,1) // v1f.x = 1.0 * (nsx * 1.0 + nsy * 0.0) ; // v1f.y = 1.0 * (nsx * 0.0 + nsy * 1.0) ; // v1f.x+= 1.0 * (ntx * 1.0 + nty * 0.0) ; // v1f.y+= 1.0 * (ntx * 0.0 + nty * 1.0) ; v1f.x = nsx + ntx ; v1f.y = nsy + nty ; // 然后将 v2sf 和 v2t 转化为向量 nsx = v2sf * s1x ; nsy = v2sf * s1y ; ntx = v2t * t1x ; nty = v2t * t1y ; // 投影到 x 轴和 y 轴 // x 轴单位向量为(1,0),y 轴为(0,1) // v2f.x = 1.0 * (nsx * 1.0 + nsy * 0.0) ; // v2f.y = 1.0 * (nsx * 0.0 + nsy * 1.0) ; // v2f.x+= 1.0 * (ntx * 1.0 + nty * 0.0) ; // v2f.y+= 1.0 * (ntx * 0.0 + nty * 1.0) ; v2f.x = nsx + ntx ; v2f.y = nsy + nty ; }// end of function 呼~~是不是感觉有点乱阿?不管怎么样,我有这种感觉。但我们确实完成了它。希望你能够理解这个计算的过 程,你完全可以依照这个过程自己编写更高效的代码,让它看上去更清楚:)至此位置,我们已经掌握了编写 一个台球游戏的基本知识了,Let's make it! 事实上,一切才刚刚起步,我们还有很多没有解决的问题,比如旋转问题,击球的角度问题等等,你还会深入 的研究一下,对吗?一旦你有了目标,坚持下去,保持激情,总会有成功的一天:)这次就到这里,下次我们 接着研究,Bye for now~~ <5>物体的旋转 -Twinsen编写 -本人水平有限,疏忽错误在所难免,还请各位数学高手、编程高手不吝赐教 -我的Email-address: popyy@netease.com 欢 迎回来这里!此次我们要讨论向量的旋转问题,包括平面绕点旋转和空间绕轴旋转两部分。 对于游戏程序员来说,有了向量的旋转,就代表有了操纵游戏中物体旋转 的钥匙,而不论它 是一个平面精灵还是一组空间的网格体亦或是我们放在 3-D世界某一点的相机。我们仍需借 助向量来完成我们此次的旅程,但这还不够,我们还 需要一个朋友,就是矩阵,一个我们用 来对向量进行线性变换的GooL GuY。就像我们刚刚提及向量时所做的一样,我们来复习一下 即将用到的数学知识。(这部分知识我只会一带而过,因为我将把重点放在后面对旋转问题 的分析 上) 一、矩阵的基本运算及其性质 对于 3x3 矩阵(也叫 3x3 方阵,行列数相等的矩阵也叫方阵)m 和 M,有 1、矩阵加减法 m +(-) M = [a b c] [A B C] [a+(-)A b+(-)B c+(-)C] [d e f] +(-) [D E F] = [d+(-)D e+(-)E f+(-)F] [g h i] [G H I] [g+(-)G h+(-)H i+(-)I] 性质: 1)结合律 m + (M + N) = (m + M) + N 2) 交换律 m + M = M + m 2、数量乘矩阵 k x M = [A B C] [kxA kxB kxC] k x [D E F] = [kxD kxE kxF] [G H I] [kxG kxH kxI] 性质: k 和 l 为常数 1) (k + l) x M = k x M + l x M 2) k x (m + M) = k x m + k x M 3) k x (l x M) = (k x l) x M 4) 1 x M = M 5) k x (m x M) = (k x m) x M = m x (k x M) 3、矩阵乘法 m x M = [a b c] [A B C} [axA+bxD+cxG axB+bxE+cxH axC+bxF+cxI] [d e f] x [D E F] = [dxA+exD+fxG dxB+exE+fxH dxC+exF+fxI] [g h i] [G H I] [gxA+hxD+ixG gxB+hxE+ixH gxC+hxF+ixI] 可以看出,矩阵相乘可以进行的条件是第一个矩阵的列数等于第二个矩阵的行数。 由矩阵乘法的定义看出,矩阵乘法不满足交换率,即在一般情况下,m x M != M x m。 性质: 1) 结合律 (m x M) x N = m x (M x N) 2) 乘法加法分配律 m x (M + N) = m x M + m x N ; (m + M) x N = m x N + M x N 4、矩阵的转置 m' = [a b c]' [a d g] [d e f] = [b e h] [g h i] [c f i] 性质: 1)(m x M)' = M' x m' 2)(m')' = m 3)(m + M)' = m' + M' 4)(k x M)' = k x M' 5、单位矩阵 [1 0 0] E = [0 1 0] 称为 3 级单位阵 [0 0 1] 性质:对于任意 3 级矩阵 M,有 E x M = M ; M x E = M 6、矩阵的逆 如果3x3级方阵m,有m x M = M x m = E,这里E是3级单位阵,则可以说 m 是可逆的,它 的逆矩阵为 M,也记为 m^-1。相反的,也可以说 M 是可逆的,逆矩阵为 m,也记为 M^-1。 性质: 1) (m^-1)^-1 = m 2) (k x m)^-1 = 1/k x m^-1 3)(m')^-1 = (m^-1)' 4) (m x M)^-1 = M^-1 x n^-1 矩阵求逆有几种算法,这里不深入研究,当我们用到的时候在讨论。 在我们建立了矩阵的概念之后,就可以用它来做坐标的线性变换。好,现在我们开始来使用 它。 二、基础的 2-D 绕原点旋转 首先是简单的 2-D 向量的旋转,以它为基础,我们会深入到复杂的 3-D 旋转,最后使我们可以 在 3-D 中无所不能的任意旋转。 在 2-D的迪卡尔坐标系中,一个位置向量的旋转公式可以由三角函数的几何意义推出。比如 上图所示是位置向量R逆时针旋转角度B前后的情况。在左图中,我们有关系: x0 = |R| * cosA y0 = |R| * sinA => cosA = x0 / |R| sinA = y0 / |R| 在右图中,我们有关系: x1 = |R| * cos(A+B) y1 = |R| * sin(A+B) 其中(x1, y1)就是(x0, y0)旋转角B后得到的点,也就是位置向量R最后指向的点。我们展开 cos(A+B)和sin(A+B),得到 x1 = |R| * (cosAcosB - sinAsinB) y1 = |R| * (sinAcosB + cosAsinB) 现在把 cosA = x0 / |R| sinA = y0 / |R| 代入上面的式子,得到 x1 = |R| * (x0 * cosB / |R| - y0 * sinB / |R|) y1 = |R| * (y0 * cosB / |R| + x0 * sinB / |R|) => x1 = x0 * cosB - y0 * sinB y1 = x0 * sinB + y0 * cosB 这样我们就得到了 2-D迪卡尔坐标下向量围绕圆点的逆时针旋转公式。顺时针旋转就把角度 变为负: x1 = x0 * cos(-B) - y0 * sin(-B) y1 = x0 * sin(-B) + y0 * cos(-B) => x1 = x0 * cosB + y0 * sinB y1 = -x0 * sinB + y0 * cosB 现在我要把这个旋转公式写成矩阵的形式,有一个概念我简单提一下,平面或空间里的每个 线性变换(这里就是旋转变换)都对应一个矩阵,叫做变换矩阵。对一个点实施线性变换就 是通过乘上该线性变换的矩阵完成的。好了,打住,不然就跑题了。 所以 2-D 旋转变换矩阵就是: [cosA sinA] [cosA -sinA] [-sinA cosA] 或者 [sinA cosA] 我们对点进行旋转变换可以通过矩阵完成,比如我要点(x, y)绕原点逆时针旋转: [cosA sinA] [x, y] x [-sinA cosA] = [x*cosA-y*sinA x*sinA+y*cosA] 为了编程方便,我们把它写成两个方阵 [x, y] [cosA sinA] [x*cosA-y*sinA x*sinA+y*cosA] [0, 0] x [-sinA cosA] = [0 0 ] 也可以写成 [cosA -sinA] [x 0] [x*cosA-y*sinA 0] [sinA cosA] x [y 0] = [x*sinA+y*cosA 0] 三、2-D 的绕任一点旋转 下面我们深入一些,思考另一种情况:求一个点围绕任一个非原点的中心点旋转。 我 们刚刚导出的公式是围绕原点旋转的公式,所以我们要想继续使用它,就要把想要围绕的 那个非原点的中心点移动到原点上来。按照这个思路,我们先将该中心点通 过一个位移向量 移动到原点,而围绕点要保持与中心点相对位置不变,也相应的按照这个位移向量位移,此 时由于中心点已经移动到了圆点,就可以让同样位移后的 围绕点使用上面的公式来计算旋转 后的位置了,计算完后,再让计算出的点按刚才的位移向量 逆 位移,就得到围绕点绕中心 点旋转一定角度后的新位置了。看下面的图 现在求左下方的蓝色点围绕红色点旋转一定角度后的新位置。由于红色点 不在原点,所以可 以通过红色向量把它移动到原点,此时蓝色的点也按照这个向量移动,可见,红色和蓝色点 的相对位置没有变。现在红色点在原点,蓝色点可以用 上面旋转变换矩阵进行旋转,旋转后 的点在通过红色向量的的逆向量回到它实际围绕下方红色点旋转后的位置。 在这个过程中,我们对围绕点进行了三次线性变换:位移变换-旋转变换-位移变换,我们把 它写成矩阵形式: 设红色向量为(rtx, rty) [x y 1] [1 0 0] [cosA sinA 0] [1 0 0] [x' y' -] [0 1 0] x [0 1 0] x [-sinA cosA 0] x [0 1 0] = [- - -] [0 0 1] [rtx rty 1] [0 0 1] [-rtx -rty 1] [- - -] 最后得到的矩阵的 x'和 y'就是我们旋转后的点坐标。 注意到矩阵乘法满足结合律:(m x M) x N = m x (M x N),我们可以先将所有的变换矩阵乘 在一起,即 [1 0 0] [cosA sinA 0] [1 0 0] M = [0 1 0] x [-sinA cosA 0] x [0 1 0] [rtx rty 1] [0 0 1] [-rtx -rty 1] 然后再让 [x y 1] [0 1 0] x M [0 0 1] 像这样归并变换矩阵是矩阵运算一个常用的方法,因为当把诸多变换矩阵归并为一个矩阵之 后,对某点或向量的重复变换只需要乘一个矩阵就可以完成,减少了计算的开销。 本 小节讨论的这种“其他变换-绕点旋转变换-其他变换”的思想很重要,因为有时候复杂一 些的旋转变换不可能一步完成,必须使用这种旁敲侧击、化繁为简的方 法,尤其是在 3-D 空 间中,可能需要在真正做规定度数的旋转前还要做一些其他必要旋转变换,也就是要做很多 次的旋转,但总体的思想还是为了把复杂的问题分 成若干简单的问题去解决,而每一个简单 问题都需要一个变换矩阵来完成,所以希望读者深入思考一下这种方法。 好,2-D 的旋转探讨完毕。接下来,我们进入 3-D 空间,讨论更为复杂一些的旋转。Here We Go! 四、基础的 3-D 绕坐标轴方向旋转 就像 2-D 绕原点旋转一样,3-D 的绕坐标轴旋转是 3-D 旋转的基础,因为其他复杂的 3-D 旋 转最后都会化简为绕坐 标轴旋转。其实,刚才我们推导出的在 xoy 坐标面绕 o 旋转的公式可 以很容易的推广到 3-D 空间中,因为在 3-D 直角坐标系中,三个坐标轴两两正交,所以 z 轴 垂直于 xoy 面,这样,在 xoy 面绕 o 点旋转实际上在 3-D 空间中就是围绕 z 轴旋转,如下图 左所示: 这张图描述了左手系中某点在 xoy、yoz、xoz 面上围绕原点旋转的情况,同时也是分别围绕 z、x、y 坐标轴旋转。可见在 3-D 空间中绕坐标轴旋转相当于在相应的 2-D 平面中围绕原点 旋转。我们用矩阵来说明: 设p(x, y, z)是 3-D空间中的一点,也可以说是一个位置向量,当以上图中的坐标为准,p点 所围绕的中心轴指向你的屏幕之外时,有 p绕z轴逆时针和顺时针旋转角度A分别写成: [x y z 1] [cosA -sinA 0 0] [x y z 1] [cosA sinA 0 0] [0 1 0 0] x [sinA cosA 0 0] 和 [0 1 0 0] x [-sinA cosA 0 0] [0 0 1 0] [0 0 1 0] [0 0 1 0] [0 0 1 0] [0 0 0 1] [0 0 0 1] [0 0 0 1] [0 0 0 1] p绕x轴逆时针和顺时针旋转角度A分别写成: [x y z 1] [1 0 0 0] [x y z 1] [1 0 0 0] [0 1 0 0] x [0 cos -sinA 0] 和 [0 1 0 0] x [0 cosA sinA 0] [0 0 1 0] [0 sin cosA 0] [0 0 1 0] [0 -sinA cosA 0] [0 0 0 1] [0 0 0 1] [0 0 0 1] [0 0 0 1] p绕y轴逆时针和顺时针旋转角度A分别写成: [x y z 1] [cosA 0 sinA 0] [x y z 1] [cosA 0 -sinA 0] [0 1 0 0] x [0 1 0 0] 和 [0 1 0 0] x [0 1 0 0] [0 0 1 0] [-sinA 0 cosA 0] [0 0 1 0] [sinA 0 cosA 0] [0 0 0 1] [0 0 0 1] [0 0 0 1] [0 0 0 1] 以后我们会把它们写成这样的标准 4x4 方阵形式,Why?为了便于做平移变换,还记得上小节 做平移时我们把 2x2 方阵写为 3x3 方阵吗? 让我们继续研究。我们再把结论推广一点,让它适用于所有和坐标轴平行的轴,具体一点, 让它适用于所有和y轴平行的轴。 这个我们很快可以想到,可以按照 2-D的方法“平移变换-旋转变换-平移变换”来做到,看 下图 要实现 point 绕 axis 旋转,我们把 axis 按照一个位移向量移动到和 y 轴重合的位置,也就 是变换为 axis',为了保持 point 和 axis 的相对位置不变,point 也通过相同的位移向量做 相应的位移。好,现在移动后的 point 就可以用上面的旋转 矩阵围绕 axis'也就是 y 轴旋转 了,旋转后用相反的位移向量位移到实际围绕axis 相应度数的位置。我们还是用矩阵来说明: 假设 axis 为 x = s, z = t,要 point(x, y, z)围绕它逆时针旋转度数 A,按照“平移变换- 旋转变换-位移变换”,我们有 [x y z 1] [1 0 0 0] [cosA 0 sinA 0] [1 0 0 0] [x' y z' -] [0 1 0 0] [0 1 0 0] [0 1 0 0] [0 1 0 0] [- - - -] [0 0 1 0] x [0 0 1 0] x [-sinA 0 cosA 0] x [0 0 1 0] = [- - - -] [0 0 0 1] [-s 0 -t 1] [0 0 0 1] [s 0 t 1] [- - - -] 则得到的(x', y, z')就是 point 围绕 axis 旋转角 A 后的位置。 同理,平行于 x 轴且围绕轴 y=s,z=t 逆时针旋转角 A 的变换为 [x y z 1] [1 0 0 0] [1 0 0 0] [1 0 0 0] [x y' z' -] [0 1 0 0] [0 1 0 0] [0 cosA -sinA 0] [0 1 0 0] [- - - -] [0 0 1 0] x [0 0 1 0] x [0 sinA cosA 0] x [0 0 1 0] = [- - - -] [0 0 0 1] [0 -s -t 1] [0 0 0 1] [0 s t 1] [- - - -] 平行于 z 轴且围绕轴 x=s,y=t 逆时针旋转角 A 的变换为 [x y z 1] [1 0 0 0] [cosA -sinA 0 0] [1 0 0 0] [x' y' z -] [0 1 0 0] [0 1 0 0] [sinA cosA 0 0] [0 1 0 0] [- - - -] [0 0 1 0] x [0 0 1 0] x [0 0 1 0] x [0 0 1 0] = [- - - -] [0 0 0 1] [-s -t 0 1] [0 0 0 1] [s t 0 1] [- - - -] 逆时针旋转就把上面推出的相应逆时针旋转变换矩阵带入即可。至此我们已经讨论了 3-D 空 间基本旋转的全部,接下来的一小节是我们 3-D 旋转部分的重头戏,也是 3-D 中功能最强大 的旋转变换。 五、3-D 绕任意轴的旋转 Wow!终于来到了最后一部分,这一节我们将综合运用上面涉及到的所有旋转知识,完成空间 一点或着说位置向 量围绕空间任意方向旋转轴的旋转变换(我在下面介绍的一种方法是一个 稍微繁琐一点的方法,大体上看是利用几个基本旋转的综合。我将在下一篇中介绍一个高档 一些的方法)。 何谓任意方向的旋转轴呢?其实就是空间一条直线。在空间解析几何中,决定空间直线位置 的两个值是直线上一点以及直线的方向向量。在旋转中,我们把这个直线称为一个旋转轴, 因此,直线的这个方向向量我们叫它轴向量,它类似于 3-D动画中四元数的轴向量。我们在 实际旋转之前的变换矩阵需要通过把这个轴向量移动到原点来获得。 我 们先讨论旋转轴通过原点的情况。目前为止对于 3-D空间中的旋转,我们可以做的只是绕 坐标轴方向的旋转。因此,当我们考虑非坐标轴方向旋转的时候,很自然 的想到,可以将这 个旋转轴通过变换与某一个坐标轴重合,同时,为了保持旋转点和这个旋转轴相对位置不变, 旋转点也做相应的变换,然后,让旋转点围绕相应旋 转轴重合的坐标轴旋转,最后将旋转后 的点以及旋转轴逆变换回原来的位置,此时就完成了一点围绕这个非坐标轴方向旋转轴的旋 转。我们再来看图分析。 图中有一个红色的分量为(x0, y0, z0)的轴向量,此外有一个蓝色位置向量围绕它旋转,由 于这个轴向量没有与任何一个坐标轴平行,我们没有办法使用上面推导出的旋转变换矩阵, 因此必须将该 轴变换到一个坐标轴上,这里我们选择了 z 轴。在变换红色轴的同时,为了保 持蓝色位置向量同该轴的相对位置不变,也做相应的变换,然后就出现中图描述的情 况。接 着我们就用可以用变换矩阵来围绕 z 轴旋转蓝色向量相应的度数。旋转完毕后,再用刚才变 换的逆变换把两个向量相对位置不变地还原到初始位置,此时就完 成了一个点围绕任意过原 点的轴的旋转,对于不过原点的轴我们仍然用“位移变换-旋转变换-位移变换”的方法,一 会讨论。 在理解了基本思路之后,我们来研究一下变换吧!我们就按上图将红色轴变到 z 轴上,开始 吧! 首先我们假设红轴向量是一个单位向量,因为这样在一会求 sin 和 cos 时可以简化计算,在 实际编程时可以先将轴向量标准化。然后我准备分两步把红色轴变换到 z 轴上去: 1)将红色轴变换到 yoz 平面上 2) 将 yoz 平面上的红色轴变到 z 轴上 至于这两个变换的方法...我实在没有别的办法了,只能够旋转了,你觉得呢?先把它旋转到 yoz 平面上。 我们设轴向量旋转到 yoz 面的变换为(绕 z 轴旋转): [cosA sinA 0 0] [-sinA cosA 0 0] [0 0 1 0] [0 0 0 1] 接着我们要求出 cosA 和 sinA,由上图,沿着 z 轴方向看去,我们看到旋转轴向量到 yoz 面 在 xoy 面就是将轴的投影向量旋转角度A到y轴上,现在我不知道角度 A,但是我们可以利 用它直接求出 cosA 和 sinA,因为我们知道关系: cosA = y0 / 轴向量在 xoy 面的投影长 sinA = x0 / 轴向量在 xoy 面的投影长 我们设轴向量的投影长为 lr = sqrt(x0^2 + y0^2),呵呵,现在,我们第一步的变换矩阵就 出来了: [y0/lr x0/lr 0 0] [-x0/lr y0/lr 0 0] [0 0 1 0] [0 0 0 1] 同时我们得到逆变换矩阵: [y0/lr -x0/lr 0 0] [x0/lr y0/lr 0 0] [0 0 1 0] [0 0 0 1] 然后我们进行第二步:将yoz 平面上的红色轴变到 z 轴上。我们的变换矩阵是(绕x 轴旋转): [1 0 0 0] [0 cosB sinB 0] [0 -sinB cosB 0] [0 0 0 1] 由图,这是经第一次旋转后的轴向量在 yoz 面中的情形,此次我们要求出上面变换中的 cosB 和 sinB,我们仍不知 道角度 B,但我们还是可以利用它求 cosB 和 sinB。由于第一次旋转是 围绕 z 轴,所以轴向量的 z 分量没有变,还是 z0。此外,轴向量现在的 y 分量和原来 不同 了,我们再看一下第一次变换那张图,可以发现轴向量在旋转到 yoz 面后,y 分量变成了刚 才轴向量在 xoy 面上的投影长 lr 了。Yes!我想是时候写出 cosB 和 sinB 了: cosB = z0 / 轴向量的长 sinB = lr / 轴向量的长 还记得我们刚才假设轴向量是一个单位向量吗?所以 cosB = z0 sinB = lr 至此我们的第二个变换就出来了: [1 0 0 0] [0 z0 lr 0] [0 -lr z0 0] [0 0 0 1] 相应逆变换矩阵: [1 0 0 0] [0 z0 -lr 0] [0 lr z0 0] [0 0 0 1] 现在总结一下,我们对于空间任意点围绕某个任意方向且过原点的轴旋转的变换矩阵就是: [y0/lr x0/lr 0 0] [1 0 0 0] [cosA sinA 0 0] [1 0 0 0] [y0/lr -x0/lr 0 0] [-x0/lr y0/lr 0 0] [0 z0 lr 0] [-sinA cosA 0 0] [0 z0 -lr 0] [x0/lr y0/lr 0 0] M = [0 0 1 0] x [0 -lr z0 0] x [0 0 1 0] x [0 lr z0 0] x [0 0 1 0] [0 0 0 1] [0 0 0 1] [0 0 0 1] [0 0 0 1] [0 0 0 1] 上面的变换是“旋转变换-旋转变换-旋转变换-旋转变换-旋转变换”的变换组。当我们需要 让空间中的某个位置向量围绕一个轴旋转角度 A 的时候,就可以用这个向量相应的矩阵乘上 这个 M,比如 [x y 0 0] [x' y' z' -] [0 1 0 0] [- - - -] [0 0 1 0] x M = [- - - -] [0 0 0 1] [- - - -] 当然,M 中矩阵相应的元素是根据轴向量得到的。 以 上的变换矩阵是通过把轴向量变到 z 轴上得到的,而且是先旋转到 yoz 面上,然后再旋转 到 z 轴上。我们也可以不这样做,而是先把轴向量旋转到 xoz 面上,然 后再旋转到 z 轴上。 此外,我们还可以把轴向量变到x或y轴上,这一点我们可以自己决定。虽然变换不同,但 推导的道理是相同的,都是这种“其他变换-实际旋 转变换-其他变换”的渗透形式。 刚才分析的是旋转轴过原点的情况,对于一般的旋转轴,虽然我们也都是把它的轴向量放到 原点来考虑,但我们不能只是让 旋转点围绕过原点的轴向量旋转完就算完事,我们仍需要采 用“平移变换-旋转变换-平移变换”方法。即先将旋转轴平移到过原点方向,旋转点也做相 应平移,接 着按上面推出的变换阵旋转,最后将旋转轴和点逆平移回去。这里,我们只需在 M 的左右两边各加上一个平移变换即可。这个平移变换的元素是根据轴向量与原点之 间的距 离向量得到的,比如旋转轴与原点的距离向量是(lx, ly, lz),则我们的变换就变成 [1 0 0 0] [1 0 0 0] [0 1 0 0] [0 1 0 0] m = [0 0 1 0] x M x [0 0 1 0] [-lx -ly -lz 1] [lx ly lz 1] 变换矩阵 m 就是全部 7 个变换矩阵的归并,适用于各种旋转情况。 我们现在已经讨论完了一般的 2-D、3-D 旋转了。可以看出其基本的思想还是能够化繁为简的 变换、归并。而实际的旋转也仍是用我们最最基本的 2-D 绕原点旋转公式。其实还有很多的旋转效果 可以用我们上面的变换、公式稍加修改获得。比如螺旋形旋转、旋转加前进、随机旋转等等。下一篇将介绍 一个用的最多的高档一些的方法,下次见。
还剩34页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

tjp24

贡献于2017-08-16

下载需要 10 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf