首页 > 代码库 > 【转】游戏程序员的数学食粮05——向量速查表

【转】游戏程序员的数学食粮05——向量速查表

原文:http://gad.qq.com/program/translateview/7172922

翻译:王成林(麦克斯韦的麦斯威尔)  审校:黄秀美(厚德载物)

 

这是本系列大家盼望已久的第五篇。如果你对向量了解不多,请先查看本系列的前四篇文章:介绍,向量基础,向量的几何表示,向量的运算。

这篇速查表会列举一些游戏中常见的几何问题,以及使用数学向量解决它们的方法。

 

基本向量运算的完整表单

首先,先复习一下。

 

首先我假设你有一个可用的向量类。它的功能大部分集中在2D上,但是3D的原理相同。差别只在于向量乘积,在2D中我假设向量相乘只会返回代表“z”轴的标量。我会特别指出任何只适用于2D或3D的情况。

 

严格来说,一个点不是一个向量——但是一个向量可以代表从原点(0,0)到点的距离,那么把向量当做点代表位置就很合理了。

 

我预期在该类中你拥有每个分量,以及下列各运算(使用C++风格的标记法,包括算子的重载——但根据你的需求应该很容易将它翻译到任何其它的语言)的使用权限。如果一个运算不可用,你仍可以通过拓展该类或者创建一个“VectorUtils”的类来实现它。以下的例子一般适用于2D向量——但对于3D通常只需简单地按照x、y的形式加入z坐标即可。

 

  • Vector2foperator+(Vector2f vec):返回两向量的和。(在没有重载的语言中,该函数可能叫做add()。下面几个例子类似。)

a+b=Vector2f(a.x+b.x,a.y+b.y);

  • Vector2foperator-(Vector2f vec):返回两向量的差

a-b=Vector2f(a.x-b.x,a.y-b.y);

  • Vector2foperator*(Vector2f vec):返回两向量的逐分量的乘积

a*b=Vector2f(a.x*b.x,a.y*b.y);

  • Vector2foperator/(Vector2f vec):返回两向量的逐分量的商

a/b=Vector2f(a.x/b.x,a.y/b.y);

  • Vector2foperator*(float scalar):返回向量所有分量分别乘以一标量参数的结果。

a*s=Vector2f(a.x*s,a.y*s);

s*a=Vector2f(a.x*s,a.y*s);

  • Vector2foperator/(float scalar):返回向量所有分量分别除以一标量参数的结果。

a/s=Vector2f(a.x/s,a.y/s);

  • floatdot(Vector2f vec):返回两向量的点乘

a.dot(b)=a.x*b.x+a.y*b.y;

  • floatcross(Vector2f vec):(2D情况)返回两向量叉乘(3D向量)的z分量

a.cross(b)=a.x*b.y-a.y*b.x;

  • Vector3fcross(Vector3f vec):(3D情况)返回两个向量的叉乘。

a.cross(b)=Vector3f(a.y*b.z-a.z*b.y, a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x);

  • floatlength():返回向量的长度。

a.length()=sqrt(a.x*a.x+a.y*a.y);

  • floatsquaredLength():返回向量长度的平方。适用于比较两向量的长度,避免了计算平方根。

a.squaredLength()=a.x*a.x+a.y*a.y;

  • floatunit():返回一个指向同一方向长度为1的向量。

a.unit()=a/a.length();

  • Vector2fturnLeft():返回向量向左旋转90度的结果。适用于计算法向量。(假设y轴指向上,否则就是向右转)

a.turnLeft=Vector2f(-a.y,a.x);

  • Vector2fturnRight():返回向量向右旋转90度的结果。适用于计算法向量。(假设y轴指向上,否则就是向左转)
  • a.turnRight=Vector2f(a.y,-a.x);
  • Vector2frotate(float angle):按照特定角度旋转向量。尽管很少能够在向量类中找到,但这是非常有用的运算。等效于乘以一个2x2旋转矩阵

a.rotate(angle)=Vector2f(a.x*cos(angle)-a.y*sin(angle),a.x*sin(angle)+a.y*cos(angle));

  • floatangle():返回向量指向的角度。

a.angle()=atan2(a.y,a.x);

 

简单的示例——热身

例1——两点间距离

也许你知道可以用毕达哥拉斯定理得出,但是向量方法更简单。给定向量a和向量b:

1

float distance = (a-b).length();

 

例2——矫直(alignment)

一些情况下你也许想要按照一张照片的中心矫直它。有时要按照它的左上角或者中上点。更广泛来说,为了最大限度地控制矫直线,你可以使用一个两分量从0到1(甚至超出也可以,如果你希望的话)的向量进行任意方向的矫直。

1

2

// imgPos, imgSize and align are all Vector2f

Vector2f drawPosition = imgPos + imgSize * align

 

例3——参数化直线方程

两点定义一条直线,但是该定义有很多玄机。一个处理直线不错的方法是使用参数化方程:一个点(“P0”)和一个方向(“dir”)。

1

2

Vector2f p0 = point1;

Vector2f dir = (point2 - point1).unit();

 

有了这个,你可以,例如,你可以得到一个距离p010单位远的点:

1

Vector2f p1 = p0 + dir * 10;

 

例4:——中点和两点间的内延(interpolation)

给定向量p0和p1。它们的中点是(p0+p1)/2。更广泛来讲,p0和p1定义的线段可以通过线性内延在0到1间改变t来得到

1

Vector2f p = (1-t) * p0 + t * p1;

 

 

在t=0时,你得到p0;在t=1时,你得到p1;在t=0.5时,你得到中点,等等。

 

例5:找到一线段的法向

你已经知道如何找到线段的方向了(例3)。将它旋转90度得到法向量,所以对它使用turnLeft()或turnRight()即可得到结果。

 

使用点乘的投影

点乘对于计算向量沿一个方向投影的长度具有很大帮助。我们需要向量(“a”)和一个代表投影方向(“dir”)的单位向量(所以确保你首先使用unit())。那么投影长度就是a.dot(dir)。例如,如果a=(3,4),dir=(1,0),那么a.dot(dir)=3。你可以判断这是正确的,因为(1,0)是x轴的方向。实际上a.x恒等于a.dot(Vector2f(1,0)),a.y恒等于a.dot(Vector2f(0,1))。

因为a和b的点乘还可以被定义为|a||b|cos(alpha)(alpha是两向量夹角),所以如果两者垂直结果为0,如果两者夹角小于90°结果为正,大于90°结果为负。我们可以使用这一点判断两向量是否指向同一大方向。

如果将点乘的结果乘以方向向量,你会得到沿着那方向的向量的投影——我们称之为“at”(t代表切向)。如果我们做a-at,我们会得到垂直于方向向量的向量——我们称之为“an”(n代表法向)。at+an=a。

 

例6——决定最靠近dir的方向

假设你有许多指向不同方向的单位向量,你想要找出哪一个方向最靠近dir。只需找到列表中向量和dir点乘的结果最大的那个。同样,最小的点乘意味着距离最远的那个。

 

例7——判断两向量的夹角是否小于alpha

使用上述方程,我们知道如果两向量a和b的单位向量的点乘小于cos(alpha),那么它们之间的夹角小于alpha。

1
2
3
bool isLessThanAlpha(Vector2f a, Vector2f b, float alpha) {
    return a.unit().dot(b.unit()) < cos(alpha);
}

 

例8——判断一点所在的半平面

假设平面中有任意一点p0,和一个方向(单位)向量,dir。假设一条穿过p0,垂直于dir的无线长的线将平面一分为二:dir指向的半平面和dir没有指向的半平面。那么如何判断一个点p是否在dir指向的那一边呢?记住当向量间夹角小于90°时它们的点乘为正,那么只需做投影然后检查:

1
2
3
bool isInsideHalfPlane(Vector2f p, Vector2f p0, Vector dir) {
    return (p - p0).dot(dir) >= 0;
}

 

例9——迫使一点在半平面内

和上面范例相似,但是不仅仅是检查,如果投影小于0的话,我们使用它将目标-投影移动到dir方向,这样目标点就在半平面的边缘了。

1
2
3
4
5
Vector2f makeInsideHalfPlane(Vector2f p, Vector2f p0, Vector dir) {
    float proj = (p - p0).dot(dir);
    if (proj >= 0) return p;
    else return p - proj * dir;
}

 

例10——检查/迫使一点在一凸多面体内。

一个凸多面体可以被定义为多个半平面相交所得结果,每个交线作为多面体的边。它们的p0是边上的顶点,它们的dir是边的内面法线向量(例如,如果你按顺时针方向走,那就是turnRight()法向)。一个点在多面体内部当且仅当它在所有的半平面内。同样地,你可以迫使它在多面体内(通过移动到最靠近的边)通过对所有半平面运用makeInsideHalfPlane 算法。[哎呀!其实只有当所有角度>=90°时才管用]

 

例11——按照给定法线反射一个向量

弹球类游戏,球撞向一个斜墙面。已知球的速度向量和墙的法向量(见例5)。现实情况下它会如何反弹?简单!只需反射球的法向速度,保持它的切向速度即可。

1
2
3
4
5
Vector2f vel = getVel();
Vector2f dir = getWallNormal(); // Make sure this is a unit vector
Vector2f velN = dir * vel.dot(dir); // Normal component
Vector2f velT = vel - velN; // Tangential component
Vector2f reflectedVel = velT - velN;

想要更贴近现实,你可以将velT和velN分别乘以一个代表摩擦力和恢复系数的常数。

 

例12——抵消沿轴的运动

有时我们需要将运动限制在一个给定坐标轴内。思路和上面相同:将速度分解到法向和切向上,然后仅保留切线速度。这有助于计算沿轨道运动的人的速度。

 

旋转

例13——点绕定点做旋转

假设我们有一点,rotate()会将点按原点进行旋转。这很有趣,但是也有限制。按任意一定点旋转简单而且实用——只需用点减去定点,也就是将定点平移到原点,然后旋转,然后再把定点加回去。

1
2
3
Vector2f rotateAroundPivot(Vector2f p, Vector2f pivot) {
    return (pos - pivot).rotate(angle) + pivot;
}

 

例14——判断向哪一方向旋转

假设我们有一个角色想要转身面向敌人。已知他的方向和面向敌人的方向。那么他应该向左转还是向右转?叉乘给出了简单的答案:curDir.cross(targetDir)返回正数如果你应该左转,负数如果你应该右转(返回0如果已经面对他了或者180°背对他)。

 

其他几何示例

有一些其它实用的例子,其中没有过多使用向量,但是很有用:

 

例15——等距空间到屏幕坐标

等距游戏中,你知道世界的(0,0)在屏幕的什么位置(让我们称之为原点,使用一个向量代表它),但是你如何知道(x,y)在屏幕的什么位置呢?首先,你需要两个代表坐标基的向量,新x轴和新y轴。对于一个典型的等距游戏来说,它们可以是bx=Vector2f(2,1)和by=Vector2f(-2,1)——它们不一定是单位向量。现在,一切都简单了。

1
2
Vector2f p = getWorldPoint();
Vector2f screenPos = bx * p.x + by * p.y + origin;

没错,的确很简单。

 

例16——等距屏幕到世界坐标

相同情况,但是这次你想要知道鼠标滑过哪块儿拼接图(tile)。这要更复杂一些。我们知道(x’,y’)=(x*bx.x+y*by.x,x*bx.y+y*by.y)+原点,所以可以先减去原点,然后对线性方程求解。使用克拉默法则,我们可以聪明地使用2D叉乘(查看文章开始的定义)进行简化:

1
2
3
4
5
Vector2f pos = getMousePos() - origin;
float demDet = bx.cross(by);
float xDet = pos.cross(by);
float yDet = bx.cross(pos);
Vector2f worldPos = Vector2f(xDet / demDet, yDet / demDet);

 

我看多许多人都在用“找到矩形然后查看位图”的方法,现在你不需要了。

【转】游戏程序员的数学食粮05——向量速查表