深度探索DxFramework 10-1
请尊重原作者的工作，转载时请务必注明转载自：www.xionggf.com
第10章 进入三维的世界 1
10.1.3D预备数学知识和相关代码的分析
10.2 向量，矩阵，四元数
10.3 三维几何工具集
10.3.1 与三维空间的平面相关算法
对于给定的3D点P0和法向量N，过点P0并且和N垂直的平面就可以定义为满足方程N.(P-P0) = 0的集合。（不明白这个定义怎么来的读者，可以回忆一下两向量点积的几何意义）。如下图，平面中任意点与P0的连线都与法线N是垂直的。
如果令法向量N为（A,B,C），点P0为（P0x,P0y,P0z）。则平面的方程为：
$ Ax + By + Cz + D = 0 $ ( 此时 $ Ax + By +Cz + D = \overset{\rightharpoonup}{N}\cdot P $ ，$ D = -\overset{\rightharpoonup}{N}\cdot P $ )
根据平面法线的指向，平面把它所处的空间划分成两个半空间，法线所指向的半空间称为正半空间，也可以称为正侧空间。另一半则称为负半空间，也称为负侧空间。判断某点和某平面的位置关系可以依照上面三个判断式，如下：
| 判断式 | 位置关系 | |
|---|---|---|
| Ax+By+Cz+D=0 | 点（x,y,z）在平面上 | |
| Ax+By+Cz+D>0 | 点（x,y,z）在正半空间 | |
| Ax+By+Cz+D<0 | 点（x,y,z）在负半空间 |
在此可以举一个例子来说明。如下图：
在图中，平面A由法线N(0,1,0)和点P0(0,5,0)定义。那么，定义式Ax+By+Cz+D=0的D为： D=－N.P0 = -(00+15+0*0) = -5
P3的坐标为(6,5,2)，代入方程式Ax+By+Cz+D中，为： 60+51+0*2-5=0
所以P3在平面上。P1的坐标为(0,10,0)，代入方程式Ax+By+Cz+D中，为： 00+101+0*0-5=5>0
所以P1在平面的正半空间。P2的坐标为(0,2,0)，代入方程式Ax+By+Cz+D中，为： 00+21+0*0-5=-3<0
所以P1在平面的负半空间。tool3d.cpp文件中定义了点和平面的位置关系判断的两个函数，如下：
1//检查某点p_Point是否在某平面p_Plane的正侧：
2bool positiveSide(D3DXVECTOR3* p_Point, D3DXPLANE* p_Plane)
3{
4 return p_Plane->a * p_Point->x + p_Plane->b * p_Point->y +
5 p_Plane->c * p_Point->z + p_Plane->d > 0;
6}
7
8//检查某点p_Point和某平面p_Plane的位置关系，1为正侧，
9//－1为负侧，0为点在平面上
10int whichSide(D3DXVECTOR3* p_Point, D3DXPLANE* p_Plane)
11{
12 float temp = p_Plane->a * p_Point->x +
13 p_Plane->b * p_Point->y +
14 p_Plane->c * p_Point->z + p_Plane->d;
15
16 if (temp > epsilon)
17 {
18 return 1;
19 }
20 else if (temp < (-epsilon))
21 {
22 return -1;
23 }
24 else
25 {
26 return 0;
27 }
28}
10.3.2 计算三角形面积和凸多边形面积
计算三角形的面积的方法有多种，最常用的就是把两个全等的三角形，组合成一个平行四边形，然后求出平行四边形的面积再除以2就可以了。当给定一个三角形的三个顶点坐标的时候，利用向量叉积的几何性质，就可以按照上述方法来求出三角形的面积。我们知道，两向量P×Q，有|P×Q| = |P|.|Q|.sinA,A是两向量的夹角。从几何意义上来说，两向量的叉积的模，就等于以这两向量的模的长度为不等边，组成的平行四边形的面积，如下图：
DXFrameWork提供了计算三角形面积的函数，如下：
1XFLOAT triangleArea(D3DXVECTOR3* p0, D3DXVECTOR3* p1,
2 D3DXVECTOR3* p2)
3{
4 D3DXVECTOR3 v1 = (*p1) - (*p0);
5 D3DXVECTOR3 v2 = (*p2) - (*p0);
6 return 0.5 * D3DXVec3Length(D3DXVec3Cross(&v1, &v1, &v2));
7}
知道了三角形的面积如何计算，接下来凸多边形的面积也好计算了。无非就是把凸多边形分解为若干个三角形，计算每个三角形的面积后累加即可。
1//第一个参数是凸多边形的顶点列表，第二个参数numPoints是凸多边形的顶点数
2XFLOAT convexPolygonArea(D3DXVECTOR3* points, int numPoints)
3{
4 int i;
5 XFLOAT sum = 0.0;
6 //注意points[0]是该凸多边形分解而成的三角形的共用顶点
7 for (i = 2; i < numPoints; i++)
8 {
9 sum += triangleArea(&points[0],&points[i - 1],&points[i]);
10 }
11 return sum;
12}
计算凸多边形的面积的示意图如下：
10.3.3 线段和面（face）相交检测
检查某线段是否和某面（face，注意不是平面）相交的代码如下：
1bool checkEdgeIntersectsFace( D3DXVECTOR3 p_Edge[2], D3DXVECTOR3* p_Face, int numVertices, D3DXPLANE* p_Plane, D3DXVECTOR3* p_PointOnPlane) {
2 //要进行相交判断的face，只能是三角形或者是四边形。
3 if(numVertices > MAX_VERTICES_FOR_EDGE_INTERSECT_CHECKING)
4 {
5 throw Error(_T("checkEdgeIntersectsFace : Number of
6 vertices used in checking an edge
7 intersects with a face is too many"));
8 return false;
9 }
10
11 // 通过计算面积，判断要检查的face是不是一个一维的线段。如果是就返回false
12 XFLOAT area = convexPolygonArea(p_Face, numVertices);
13 if ((area < 0.001) && (area > -0.001))
14 return false;
15
16 //如果线段的两个端点都在face所处平面的同一侧，则显然这个线段是不会和该face相交的
17 bool temp1, temp2;
18 temp1 = positiveSide(&p_Edge[0], p_Plane);
19 temp2 = positiveSide(&p_Edge[1], p_Plane);
20
21 if (temp1 == temp2)
22 {
23 return false;
24 }
25
26 //再检查线段和face所在的平面是否相交，如果不相交，则线段肯定不和face相交
27 if (D3DXPlaneIntersectLine(p_PointOnPlane, p_Plane, &p_Edge[0], &p_Edge[1]) == NULL)
28 {
29 return false;
30 }
如果计算到线段和face所在的平面相交，那么接下来就是要判断相交点是落在face的内侧还是外测了。在计算机图形学中，往往把三维对象通过降维处理，可以降低问题的复杂度。降维的方法是：通过去掉face的法线N的绝对值最大的分量所对应的坐标，就可以把问题降到二维空间来考虑。如下图所示，降维过程相当于把face投影到xy，xz或者是yz平面上。在此先假设被去掉的是z坐标，即投影到xy平面上。如下图投影多边形到XZ，YZ，XY平面上
判断某点在不在多边形内，可以把问题转化为判断点在不在某三角形内。如上图，把多边形划分为若干个三角形。然后判断点是否在这些三角形内，只要判断到点在某一三角形内，就肯定这点在此多边形内。先考虑如何判断点是否在三角形内。上面已经把三角形投影到一个二维平面来进行考虑。假定投影在了xz平面上。对三角形的每条边进行下面的二维差运算，有：
1E = P1-P0
2F=P2-P0
3G=P-P0
从本质上说，这样做的意义上移动坐标系，使得顶点P0位于原点位置。或者可以认为是以P0为原点。如下图所示。
在上面的式子中，向量E所代表的边有内侧和外测之分，将边向量旋转90°（顺时针或者逆时针旋转都可以），便可以构造出该边的法向量，而又因为点F一定是在边的正侧，所以点积Ne.F的符号就是边OE的任一内侧点的符号。因此，如果P点位于该边的内侧的话，那么就必须要满足：
1(Ne.F)(Ne.G)=(Ne.(P2-P0))(Ne.(P-P0))≥0
对于任何的点，如果它都位于三角形的三条边的内侧，那么它就在三角形内。从上面的图可以看出，线段P2-P0和法线Ne的点积是大于0（观察其夹角便可知道，其夹角绝对值小于90°），那么线段P-P0和法线Ne的点积也应大于0，即Ne.(P-P0)>0。假定是投影到XY平面上，而Ne又等于P1-P0乘以一个绕Z轴90°的旋转矩阵。令Ne为（NeX,NeY），P0为（x0,y0），P1为（x1,y1），P2为（x2,y2）,P为（x,y）则有：
1NeX = (x1-x0)*cos90°+(y1-y0)*sin90°
2NeY = -(x1-x0)*sin90°+(y1-y0)*cos90°
所以NeX=(y1-y0)，NeY=-(x1-x0),求P2在P0P1的那一侧，就求P0P2与法线的夹角值就可以了：当：
1Ne.(P2-P0)=NeX*(x2-x1)+NeY*(y2-y1)=(y1-y0)*(x2-x1)+(-(x1-x0)*(y2-y1))>0
就表示p2是在边e的正侧。 而Ne.(P2-P0)=NeX*(x2-x1)+NeY*(y2-y1)经过整理后，实质上就是下面行列式的值，如下：
1|x0 y0 1|
2|x1 y1 1|
3|x2 y2 1|
所以判断点P是否在边e的内侧，就是把上面行列式中点P2的分量代替为点P的分量，只需要计算行列式的值是否大于0便可。大于0，在e的正侧，小于0在e的负侧。下面接着的代码就是根据这个原理实现。
1 //接上段代码， checkEdgeIntersectsFace函数，tools3d.cpp
2 float absa = (float)fabs(p_Plane->a);
3 float absb = (float)fabs(p_Plane->b);
4 float absc = (float)fabs(p_Plane->c);
5
6 static D3DXVECTOR2
7 face2D[MAX_VERTICES_FOR_EDGE_INTERSECT_CHECKING];
8
9 D3DXVECTOR2 point2D;
10 int i;
11
12 //下面的几个if-else判断式，就是根据法线的分量大小，把三角形投影到适当的平面上去。
13 if ((absa >= absb) && (absa >= absc))
14 {
15 for (i = 0; i < numVertices; i++)
16 {
17 face2D[i].x = p_Face[i].y;
18 face2D[i].y = p_Face[i].z;
19 }
20 point2D.x = p_PointOnPlane->y;
21 point2D.y = p_PointOnPlane->z;
22 }
23 else if ((absb >= absa) && (absb >= absc))
24 {
25 for (i = 0; i < numVertices; i++)
26 {
27 face2D[i].x = p_Face[i].x;
28 face2D[i].y = p_Face[i].z;
29 }
30 point2D.x = p_PointOnPlane->x;
31 point2D.y = p_PointOnPlane->z;
32 }
33 else
34 {
35 for (i = 0; i < numVertices; i++)
36 {
37 face2D[i].x = p_Face[i].x;
38 face2D[i].y = p_Face[i].y;
39 }
40 point2D.x = p_PointOnPlane->x;
41 point2D.y = p_PointOnPlane->y;
42 }
43
44 //p0,p1是多边形的线段的两端点，p2是想要检查的点。
45
46 float val;
47 //这里就是检查(Ne.F)(Ne.G)的结果值
48 val=(face2D[0].x * face2D[1].y + face2D[0].y * point2D.x
49 + face2D[1].x * point2D.y ) -(point2D.x *
50 face2D[1].y + point2D.y * face2D[0].x +
51 face2D[1].x * face2D[0].y);
52 bool cc = val > 0;
53 bool cctemp;
54 if (fabs(val) < 0.0001f)
55 return true; //在边上
56
57 //逐个边检查。
58 for (i = 1; i < numVertices; i++)
59 {
60 val = (face2D[i].x * face2D[(i + 1) % numVertices].y
61 + face2D[i].y * point2D.x + face2D[(i + 1) %
62 numVertices].x * point2D.y) -
63 (point2D.x * face2D[(i + 1) % numVertices].y +
64 point2D.y * face2D[i].x + face2D[(i + 1) %
65 numVertices].x * face2D[i].y);
66
67 if (fabs(val) < 0.0001f) return true; //在边上
68 cctemp = val > 0;
69 if ((cctemp != cc))
70 {
71 return false;
72 }
73 }
74 return true; }
10.3.4 分割三角形
1void splitTriangle(D3DXPLANE* p_Plane, D3DXVECTOR3* p0,
2 D3DXVECTOR3* p1, D3DXVECTOR3* p2,
3 unsigned short* positiveIndices,
4 DWORD* p_NumPositiveIndices,
5 unsigned short* negativeIndices,
6 DWORD* p_NumNegativeIndices)
7{
8 //检查三角形的三个角顶点在分割平面的哪一则？正？负？面上？
9 int sides[3]; //存储顶点与分割平面的位置信息
10 int numzero = 0, i;//三角形角顶点在分割平面上的个数
11 sides[0] = whichSide(p0, p_Plane);
12 sides[1] = whichSide(p1, p_Plane);
13 sides[2] = whichSide(p2, p_Plane);
14
15 if (sides[0] == 0) numzero++;
16 if (sides[1] == 0) numzero++;
17 if (sides[2] == 0) numzero++;
18
19 //如果没有角顶点在分割平面上
20 if (numzero == 0)
21 {
22 //检查有多少个角顶点在分割平面的正侧
23 int numPositive = 0;
24 for (i = 0; i < 3; i++) {
25 if (sides[i] == 1) {
26 numPositive++;
27 }
28 }
29
30 //根据角顶点在分割平面的正侧的个数，分四种情况考虑。
31 //情况1：没有一个角顶点在分割平面上，
32 if (numPositive == 0)
33 {
34 //没有一个角顶点在分割平面的正侧，那么所有的角顶点都在
35 //分割平面的负侧
36 //在分割平面的正侧的角顶点数为0
37 *p_NumPositiveIndices = 0;
38 //在分割平面的负侧的角顶点数为3
39 *p_NumNegativeIndices = 3;
40
41 //记录下在分割平面负侧的角顶点编号
42 negativeIndices[0] = 0;
43 negativeIndices[1] = 1;
44 negativeIndices[2] = 2;
45 }
1 //有一个顶点在分割平面的正侧
2else if (numPositive == 1)
3{
4 // 找到哪个角顶点在分割平面的正侧
5 int index;
6 for (i = 0; i < 3; i++) {
7 if (sides[i] == 1) {
8 index = i;
9 break;
10 }
11 }
12
13 //原三角形在正侧部分被分割成1一个三角形，所以顶点数为3
14 //在负侧部分被分割成2个三角形，所以顶点数为6
15 *p_NumPositiveIndices = 3;
16 *p_NumNegativeIndices = 6;
17
18 positiveIndices[0] = 3 + (index + 2) % 3;
19 positiveIndices[1] = index;
20 positiveIndices[2] = 3 + index;
21
22 negativeIndices[0] = 3 + index;
23 negativeIndices[1] = (index + 1) % 3;
24 negativeIndices[2] = 3 + (index + 2) % 3;
25
26 negativeIndices[3] = (index + 1) % 3;
27 negativeIndices[4] = (index + 2) % 3;
28 negativeIndices[5] = 3 + (index + 2) % 3;
29
30 }
1 else if (numPositive == 2) {
2 // 1 point is on negative side
3 // Find which one is it
4 int index;
5 for (i = 0; i < 3; i++) {
6 if (sides[i] == -1) {
7 index = i;
8 break;
9 }
10 }
11 // Two triangles on positive side
12 // One triangles on negative side
13 *p_NumPositiveIndices = 6;
14 *p_NumNegativeIndices = 3;
15
16 positiveIndices[0] = 3 + index;
17 positiveIndices[1] = (index + 1) % 3;
18 positiveIndices[2] = 3 + (index + 2) % 3;
19
20 positiveIndices[3] = (index + 1) % 3;
21 positiveIndices[4] = (index + 2) % 3;
22 positiveIndices[5] = 3 + (index + 2) % 3;
23
24 negativeIndices[0] = 3 + (index + 2) % 3;
25 negativeIndices[1] = index;
26 negativeIndices[2] = 3 + index;
27
28 } else if (numPositive == 3) {
29 // Alll points are on positive side
30 *p_NumPositiveIndices = 3;
31 *p_NumNegativeIndices = 0;
32
33 positiveIndices[0] = 0;
34 positiveIndices[1] = 1;
35 positiveIndices[2] = 2;
36 }
37 }
1 //如果有一个角顶点在分割平面上
2else if (numzero == 1) {
3 //One point is on the plane
4 //Can either be 1. On one side of the plane
5 // 2. On two side of the plane
6 int sum = sides[0] + sides[1] + sides[2];
7 //-1+1+0=0，一个顶点在分割面正侧，另一个在负侧，一个在面上
8 if (sum == 0) {
9 //On two side of the plane
10 int index;
11
12 // Find which one is on the plane
13 for (i = 0; i < 3; i++) {
14 if (sides[i] == 0) {
15 index = i;
16 break;
17 }
18 }
19
20 //分别找到在正侧和在负测的顶点的索引
21 if (sides[(index + 1) % 3] == 1) {
22 // Positive
23 *p_NumPositiveIndices = 3;
24 *p_NumNegativeIndices = 3;
25
26 positiveIndices[0] = index;
27 positiveIndices[1] = (index + 1) % 3;
28 positiveIndices[2] = 3 + (index + 1) % 3;
29
30 negativeIndices[0] = 3 + (index + 1) % 3;
31 negativeIndices[1] = (index + 2) % 3;
32 negativeIndices[2] = index;
33 } else {
34 // Negative
35 *p_NumPositiveIndices = 3;
36 *p_NumNegativeIndices = 3;
37
38 positiveIndices[0] = 3 + (index + 1) % 3;
39 positiveIndices[1] = (index + 2) % 3;
40 positiveIndices[2] = index;
41
42 negativeIndices[0] = index;
43 negativeIndices[1] = (index + 1) % 3;
44 negativeIndices[2] = 3 + (index + 1) % 3;
45 }
46 }
1else {
2 //On one side of the plane
3 for (i = 0; i < 3; i++) {
4 if (sides[i] != 0) {
5 break;
6 }
7 }
8 if (sides[i] == 1) {
9 //The triangle is on positive sides
10 *p_NumPositiveIndices = 3;
11 *p_NumNegativeIndices = 0;
12
13 positiveIndices[0] = 0;
14 positiveIndices[1] = 1;
15 positiveIndices[2] = 2;
16 } else {
17 //The triangle is on negative side
18 *p_NumPositiveIndices = 0;
19 *p_NumNegativeIndices = 3;
20
21 negativeIndices[0] = 0;
22 negativeIndices[1] = 1;
23 negativeIndices[2] = 2;
24 }
25 }
26 }
1else if (numzero == 2) {
2 //Two points are on the plane
3 // See which one is not
4 for (i = 0; i < 3; i++) {
5 if (sides[i] != 0) {
6 break;
7 }
8 }
9
10 if (sides[i] == 1) {
11 //The triangle is on positive side
12 *p_NumPositiveIndices = 3;
13 *p_NumNegativeIndices = 0;
14
15 positiveIndices[0] = 0;
16 positiveIndices[1] = 1;
17 positiveIndices[2] = 2;
18
19 } else {
20 //The triangle is on negative side
21 *p_NumPositiveIndices = 0;
22 *p_NumNegativeIndices = 3;
23
24 negativeIndices[0] = 0;
25 negativeIndices[1] = 1;
26 negativeIndices[2] = 2;
27 }
28 }
最后一种情况，当被分割的三角形的三个角顶点都在分割平面上，就要检查三角形的法线和分割平面的法线是否同向。同向则表示三角形被分割成一个，在分割平面的正侧；反向则表示三角形也被分割成一个，在分割平面的负侧。
1else
2{
3 D3DXVECTOR3 v01, v02, normal;
4
5 //利用向量叉积的几何性质，根据三角形的两条边求此三角形的法线。要注意方向
6 v01 = (*p1) - (*p0);
7 v02 = (*p2) - (*p0);
8 D3DXVec3Cross(&normal, &v01, &v02);
9 D3DXVec3Normalize(&normal, &normal);
10
11 //用D3DX库函数计算到平面的的法线。
12 D3DXPLANE plane = *p_Plane;
13 D3DXPlaneNormalize(&plane, &plane);
14 D3DXVECTOR3 planeNormal = D3DXVECTOR3(plane.a, plane.b, plane.c);
15
16 //观察两法线的差
17 D3DXVECTOR3 temp = planeNormal - normal;
18
19 //如果两法线的差的模很小很小，接近于0，就可以认为这三角形的
20 //法线和分割平面的法线是同向。三角形被分在分割平面的正侧，否则
21 //就分在的负测
22 if (D3DXVec3Length(&temp) < 0.01f) {
23 // 在正侧
24 *p_NumPositiveIndices = 3;
25 *p_NumNegativeIndices = 0;
26
27 positiveIndices[0] = 0;
28 positiveIndices[1] = 1;
29 positiveIndices[2] = 2;
30
31 } else {
32 // 在负测
33 *p_NumPositiveIndices = 0;
34 *p_NumNegativeIndices = 3;
35
36 negativeIndices[0] = 0;
37 negativeIndices[1] = 1;
38 negativeIndices[2] = 2;
39 }
40 }
41}
