深度探索DxFramework 10-3

2007-10-25

请尊重原作者的工作，转载时请务必注明转载自：www.xionggf.com

第10章进入三维的世界 3

10.5 无规矩不成方圆，C_BoundingBox类

10.5.1.包围盒的种类

DXFrameWork的包围盒是一个凸六面体，由6个面，8个顶点，12条边组成的闭合体。因此，DXFrameWork也使用了相关的数据结构来描述包围盒。代码如下：

1class C_BoundingBox
2{
3    ...
4public:
5    D3DXVECTOR3 point[8]; //8个顶点
6    D3DXPLANE     plane[6]; //6个表面
7}

8个顶点和6个面和编号的示意图如下：

###10.5.2.包围盒的数据结构和初始化设置

  1//根据给定的图元计算出它的包围盒
  2void C_BoundingBox::FindBoundingBox(C_Primitive* p_Primitive) 
  3{
  4    unsigned i;
  5
  6    //获取
  7    DWORD numVertices = p_Primitive->numVertices;
  8
  9    // Lock the vertex buffer
 10    C_VertexManipulator vertexMemory;
 11    p_Primitive->LockVertexBuffer(&vertexMemory);
 12
 13    // Find the mins and maxs for each X Y and Z axis
 14    D3DXVECTOR3 position;
 15
 16    float minX;
 17    float minY;
 18    float minZ;
 19    float maxX;
 20    float maxY;
 21    float maxZ;
 22
 23    position = vertexMemory[0].position;
 24    minX = maxX = position.x;
 25    minY = maxY = position.y;
 26    minZ = maxZ = position.z;
 27
 28    //遍历每一个顶点，找出X,Y,Z值最大和最小值
 29    for (i = 1; i < numVertices; i++) {
 30        position = vertexMemory[i].position;
 31        if (position.x < minX) {
 32            minX = position.x;
 33        }
 34        if (position.y < minY) {
 35            minY = position.y;
 36        }
 37        if (position.z < minZ) {
 38            minZ = position.z;
 39        }
 40        if (position.x > maxX) {
 41            maxX = position.x;
 42        }
 43        if (position.y > maxY) {
 44            maxY = position.y;
 45        }
 46        if (position.z > maxZ) {
 47            maxZ = position.z;
 48        }
 49    }
 50
 51    // Unlock the vertex buffer
 52    p_Primitive->UnlockVertexBuffer();
 53
 54    //如果一些图元的包围盒是不是三维的话，比如，一个二维面片的包围盒。
 55    //那么，就要适当地调整一下，使得包围盒能变成三维的
 56    if (fabs(minX - maxX) < 0.01f) { 
 57        minX -= 0.1f;
 58        maxX += 0.1f; 
 59    }
 60
 61    if (fabs(minY - maxY) < 0.01f) { 
 62        minY -= 0.1f;
 63        maxY += 0.1f; 
 64    }
 65
 66    if (fabs(minZ - maxZ) < 0.01f) { 
 67        minZ -= 0.1f;
 68        maxZ += 0.1f; 
 69    }
 70
 71    //创建组成三角形的八个顶点，从0到7的顺序，X,Y,Z值分别是：
 72    //0 右，下，近
 73    //1 右，上，近
 74    //2 左，上，近
 75    //3 右，上，近
 76    //4 右，下，远
 77    //5 右，上，远
 78    //6 左，上，远
 79    //7 左，下，远
 80    // 意思是，前4个
 81    point[0] = D3DXVECTOR3(maxX, minY, minZ); // Right Bottom Near
 82    point[1] = D3DXVECTOR3(maxX, maxY, minZ); // Right Top Near
 83    point[2] = D3DXVECTOR3(minX, maxY, minZ); // Left Top Near
 84    point[3] = D3DXVECTOR3(minX, minY, minZ); // Right Top Near
 85    point[4] = D3DXVECTOR3(maxX, minY, maxZ); // Right Bottom Far
 86    point[5] = D3DXVECTOR3(maxX, maxY, maxZ); // Right Top Far
 87    point[6] = D3DXVECTOR3(minX, maxY, maxZ); // Left Top Far
 88    point[7] = D3DXVECTOR3(minX, minY, maxZ); // Left Bottom Far
 89
 90    // Obtain the 6 plane specifying the bounding box
 91    D3DXPlaneFromPoints(&plane[0], &point[2], &point[1], &point[0]); //Near
 92    D3DXPlaneFromPoints(&plane[1], &point[5], &point[6], &point[4]); //Far
 93    D3DXPlaneFromPoints(&plane[2], &point[7], &point[6], &point[2]); //Left
 94    D3DXPlaneFromPoints(&plane[3], &point[1], &point[5], &point[0]); //Right
 95    D3DXPlaneFromPoints(&plane[4], &point[4], &point[3], &point[0]); //Bottom
 96    D3DXPlaneFromPoints(&plane[5], &point[2], &point[5], &point[1]); //Top
 97
 98    // Validate the bounding box
 99    valid = true;
100}

 1//根据指定的包围盒的大小范围查找到对应的包围盒
 2void C_BoundingBox::FindBoundingBox(float minX, float minY, float minZ, float maxX, float maxY, float maxZ) {
 3
 4    /* 当有些包围盒不是3D的话，比如其中有一维的值为0，则调整它变成真正三维的盒子*/
 5    if (fabs(minX - maxX) < 0.01f) { 
 6        minX -= 0.1f;
 7        maxX += 0.1f; 
 8    }
 9
10    if (fabs(minY - maxY) < 0.01f) { 
11        minY -= 0.1f;
12        maxY += 0.1f; 
13    }
14
15    if (fabs(minZ - maxZ) < 0.01f) { 
16        minZ -= 0.1f;
17        maxZ += 0.1f; 
18    }
19
20    point[0] = D3DXVECTOR3(maxX, minY, minZ); // Right Bottom Near
21    point[1] = D3DXVECTOR3(maxX, maxY, minZ); // Right Top Near
22    point[2] = D3DXVECTOR3(minX, maxY, minZ); // Left Top Near
23    point[3] = D3DXVECTOR3(minX, minY, minZ); // Right Top Near
24    point[4] = D3DXVECTOR3(maxX, minY, maxZ); // Right Bottom Far
25    point[5] = D3DXVECTOR3(maxX, maxY, maxZ); // Right Top Far
26    point[6] = D3DXVECTOR3(minX, maxY, maxZ); // Left Top Far
27    point[7] = D3DXVECTOR3(minX, minY, maxZ); // Left Bottom Far
28
29    // Obtain the 6 plane specifying the bounding box
30    D3DXPlaneFromPoints(&plane[0], &point[2], &point[1], &point[0]); //Near
31    D3DXPlaneFromPoints(&plane[1], &point[5], &point[6], &point[4]); //Far
32    D3DXPlaneFromPoints(&plane[2], &point[7], &point[6], &point[2]); //Left
33    D3DXPlaneFromPoints(&plane[3], &point[1], &point[5], &point[0]); //Right
34    D3DXPlaneFromPoints(&plane[4], &point[4], &point[3], &point[0]); //Bottom
35    D3DXPlaneFromPoints(&plane[5], &point[2], &point[5], &point[1]); //Top
36
37    // Validate the bounding box
38    valid = true;
39}
40 
41void C_BoundingBox::SetBoundingBox(D3DXVECTOR3 point[8]) {     int i;
42
43    for (i = 0; i < 8; i++) {
44        this->point[i]=point[i];
45    }
46
47    // Obtain the 6 plane specifying the bounding box
48    D3DXPlaneFromPoints(&plane[0], &point[2], &point[1], &point[0]); //Near
49    D3DXPlaneFromPoints(&plane[1], &point[5], &point[6], &point[4]); //Far
50    D3DXPlaneFromPoints(&plane[2], &point[7], &point[6], &point[2]); //Left
51    D3DXPlaneFromPoints(&plane[3], &point[1], &point[5], &point[0]); //Right
52    D3DXPlaneFromPoints(&plane[4], &point[4], &point[3], &point[0]); //Bottom
53    D3DXPlaneFromPoints(&plane[5], &point[2], &point[5], &point[1]); //Top
54
55    // 确认包围盒有效
56    valid = true;
57}
58 
59void C_BoundingBox::SetBoundingBox(D3DXVECTOR3 point[8], D3DXPLANE plane[6])
60{
61    int i;
62
63    for (i = 0; i < 8; i++) {
64        this->point[i] = point[i];
65    }
66
67    for (i = 0; i < 6; i++) {
68        this->plane[i] = plane[i];
69    }
70
71    valid = true;
72}

10.5.3.包围盒的相交种类和相交判定

在dxframework中，包围盒的相交种类分为四种，分别是：相离，相交，覆盖，被包含四种。

相离的情况如下，所谓相离是指，A包围盒和B包围盒之间，A包围盒中任意一个顶点，都不在B包围盒内部。或者B包围盒中任意一个顶点，都不在A包围盒的内部。示意图如下：

相交是指：B包围盒的一部分的顶点在A包围盒的内部，这时候称为A包围盒与B包围盒相交。示意图如下：

覆盖和被包含是指：B包围盒的全部顶点完全在A包围盒内部。这时候称为A包围盒“覆盖”了B包围盒。或者称为：B包围盒“被包含”于A包围盒。示意图如下：

C_BoundingBox类提供了包围盒相交检测的函数，如下：

  1//核心函数，判断本包围盒是否和p_BoundingBox包围盒相交
  2INTERSECTION_TYPE C_BoundingBox::IsIntersecting( C_BoundingBox *p_BoundingBox) 
  3{
  4
  5    if ((p_BoundingBox == NULL) || (!p_BoundingBox->valid) || (!this->valid)) 
  6    {
  7        //两包围盒必须要有效，即各顶点信息和表明信息要计算好才能进行相交判断
  8        throw Error(_T("C_BoundingBox::IsIntersecting : Bounding box(es) do not exist or are not valid"));
  9    }
 10
 11    //注释约定：first box指本包围盒（this指针所指向的包围盒对象），
 12    //second box指传递进来的参数指针所指向的包围盒。
 13    int i,j;
 14
 15     //out[i]数据中的第k位表示是否第i个包围盒顶点是否在第k个平面的外测
 16    DWORD out[8]; 
 17
 18    //检查second box的顶点是否在first box里面
 19    for (i = 0; i < 8; i++)    {
 20        out[i] = 0;
 21    }
 22    
 23    bool aPointInside = false;
 24    int sumOut = 0;
 25
 26    for (i = 0; i < 8; i++) 
 27    {
 28        for (j = 0; j < 6; j++)
 29        {
 30            //调用工具函数，检查第i个second box是否在
 31            //first box的第j个表面正则。
 32            if (positiveSide(&p_BoundingBox->point[i], 
 33                             &plane[j]))
 34            {
 35                out[i] |=(1 << j);
 36            }
 37        }
 38
 39        //如果第i个second box的顶点都在所有的first box的的负侧
 40        //表明表示这个第i个second box的顶点在first box的内部。
 41        if (!out[i]) 
 42        {
 43            aPointInside = true;
 44        }
 45        sumOut += out[i];
 46    }
 47
 48    //如果second box至少有一个点在first box的内侧
 49    if (aPointInside) 
 50    {
 51        // sumOut等于0。表示所有的second box的顶点都在first box
 52        // 内部。所以first box覆盖second box
 53        if (sumOut == 0) 
 54        {
 55            return COMPLETELY_COVER;
 56        }
 57        return PARTIALY_INTERSECTING;
 58    }
 59
 60    D3DXVECTOR3 intersectionPoint;
 61    if ((((((((out[0] & out[1]) & out[2]) & out[3]) 
 62        & out[4]) & out[5]) & out[6]) & out[7]) != 0) 
 63    {
 64        // 所有的顶点都在某一个面的正测，表示这两个包围盒是相离的
 65        return NOT_INTERSECTING;
 66    }
 67
 68    //检查first box的某一边是否穿过second box
 69    {
 70        D3DXVECTOR3 edges[12][2] = {
 71        p_BoundingBox->point[0], p_BoundingBox->point[1],
 72        p_BoundingBox->point[1], p_BoundingBox->point[2],
 73        p_BoundingBox->point[2], p_BoundingBox->point[3],
 74        p_BoundingBox->point[3], p_BoundingBox->point[0],
 75        p_BoundingBox->point[0], p_BoundingBox->point[4],
 76        p_BoundingBox->point[1], p_BoundingBox->point[5],
 77        p_BoundingBox->point[2], p_BoundingBox->point[6],
 78        p_BoundingBox->point[3], p_BoundingBox->point[7],
 79        p_BoundingBox->point[4], p_BoundingBox->point[5],
 80        p_BoundingBox->point[5], p_BoundingBox->point[6],
 81        p_BoundingBox->point[6], p_BoundingBox->point[7],
 82        p_BoundingBox->point[7], p_BoundingBox->point[4]};
 83
 84        D3DXVECTOR3 faces[6][4] = {
 85        point[3], point[2], point[1], point[0],//近Z，XY面
 86        point[5], point[6], point[7], point[4],//远Z，XY面
 87        point[3], point[7], point[6], point[2],//左X，YZ面
 88        point[1], point[5], point[4], point[0],//右X，YZ面    
 89        point[4], point[7], point[3], point[0],//底Y，XZ面
 90        point[2], point[6], point[5], point[1]};//顶Y，XZ面
 91
 92        for (i = 0; i < 12; i++) 
 93        {
 94            for (j = 0; j < 6; j++)
 95            {
 96                //调用工具函数checkEdgeIntersects检查第i条first 
 97                //box的边是否穿过第j个second box的面
 98                if(checkEdgeIntersectsFace(edges[i],faces[j], 
 99                    4, &plane[j], &intersectionPoint)) 
100                    { 
101                        return PARTIALY_INTERSECTING;
102                    }
103                }
104            }
105    }
106
107    //检查second box的某一边是否穿过first box
108    {
109        D3DXVECTOR3 edges[12][2] = {
110                    point[0], point[1],
111                    point[1], point[2],
112                    point[2], point[3],
113                    point[3], point[0],
114                    point[0], point[4],
115                    point[1], point[5],
116                    point[2], point[6],
117                    point[3], point[7],
118                    point[4], point[5],
119                    point[5], point[6],
120                    point[6], point[7],
121                    point[7], point[4]};
122
123        D3DXVECTOR3 faces[6][4] = {
124        p_BoundingBox->point[3], p_BoundingBox->point[2], 
125        p_BoundingBox->point[1], p_BoundingBox->point[0],    
126        p_BoundingBox->point[5], p_BoundingBox->point[6], 
127        p_BoundingBox->point[7], p_BoundingBox->point[4],     
128        p_BoundingBox->point[3], p_BoundingBox->point[7], 
129        p_BoundingBox->point[6], p_BoundingBox->point[2],    
130        p_BoundingBox->point[1], p_BoundingBox->point[5], 
131        p_BoundingBox->point[4], p_BoundingBox->point[0],      
132        p_BoundingBox->point[4], p_BoundingBox->point[7], 
133        p_BoundingBox->point[3], p_BoundingBox->point[0],    
134        p_BoundingBox->point[2], p_BoundingBox->point[6], 
135        p_BoundingBox->point[5], p_BoundingBox->point[1]};   
136
137        for (i = 0; i < 12; i++) 
138        {
139            for (j = 0; j < 6; j++)
140            {
141                if(checkEdgeIntersectsFace(edges[i],faces[j],
142                                4, &p_BoundingBox->plane[j], 
143                                &intersectionPoint)) 
144                {
145                      return PARTIALY_INTERSECTING;
146                }
147            }
148        }
149    }
150
151    //检查一下是否first box的一点是否至少在second box的一个面的正侧，
152    //如果是的话，表示两盒子相离。如果否的话，在上述的各种情况都检查过的
153    //前提下，就表示，first box在second box的内部，即first box被
154    //包含于second box
155    for (i = 0; i < 6; i++)
156    {
157        if( positiveSide(&point[0], 
158            &p_BoundingBox->plane[i])) 
159        {
160            return NOT_INTERSECTING; 
161        }
162    }
163
164    return COMPLETELY_INSIDE;
165}

上面的函数检查两包围盒相交与否是非常精确的。但是也可以看到，检测的计算非常耗时。尤其是后面判断first box是否被包含于second box的部分。如果我们能够预先知道first box的体积肯定大于second box的话。那么后面的“被包含”判断就可以省略的。因此，DXFrameWork提供了一个比较快速的相交判断函数：INTERSECTION_TYPE C_BoundingBox:: LazyIsIntersecting (C_BoundingBox *p_BoundingBox)。和IsIntersectiong函数相比，LazyIsIntersecting函数省略了检查“被包含”的判断。因此使用此函数的时候，要保证first box的体积大于second box才能得到正确的判断。

除了判断包围盒之间的相交检测之外，C_BoundingBox类还提供了包围盒和线段之间的相交判断函数，如下：

 1bool C_BoundingBox::IsPenetrated(D3DXVECTOR3 p_Edge[2]) 
 2{
 3    int j;
 4    D3DXVECTOR3 intersectionPoint;
 5    D3DXVECTOR3 faces[6][4] = {
 6        point[3], point[2], point[1], point[0],       //Near
 7        point[5], point[6], point[7], point[4],       //Far
 8        point[3], point[7], point[6], point[2],       //Left
 9        point[1], point[5], point[4], point[0],       //Right    
10        point[4], point[7], point[3], point[0],       //Bottom
11        point[2], point[6], point[5], point[1]};      //Top
12
13    for (j = 0; j < 6; j++) 
14    {
15        if (checkEdgeIntersectsFace(p_Edge, faces[j], 4,&plane[j], &intersectionPoint)) 
16        {
17              return true;
18
19        }
20    }
21    return false;
22}

从上述代码看出，要检查某线段是否和某包围盒相交，就只是需要检查某线段是否和包围盒的任意一个表面相交即可。如果是则表示这线段和包围盒相交，否就表示不相交。

第10章 进入三维的世界 3

10.5 无规矩不成方圆，C_BoundingBox类

10.5.1.包围盒的种类

10.5.3.包围盒的相交种类和相交判定

第10章进入三维的世界 3