深度探索DxFramework


请尊重原作者的工作,转载时请务必注明转载自: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 = N.P,D=-N.P0。)

根据平面法线的指向,平面把它所处的空间划分成两个半空间,法线所指向的半空间称为正半空间,也可以称为正侧空间。另一半则称为负半空间,也称为负侧空间。判断某点和某平面的位置关系可以依照上面三个判断式,如下:

判断式|位置关系|
------|------|------
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文件中定义了点和平面的位置关系判断的两个函数,如下:

//检查某点p_Point是否在某平面p_Plane的正侧:
bool positiveSide(D3DXVECTOR3* p_Point, D3DXPLANE* p_Plane)
{
    return p_Plane->a * p_Point->x +  p_Plane->b * p_Point->y + 
             p_Plane->c * p_Point->z + p_Plane->d > 0;
}

//检查某点p_Point和某平面p_Plane的位置关系,1为正侧, 
//-1为负侧,0为点在平面上
int whichSide(D3DXVECTOR3* p_Point, D3DXPLANE* p_Plane) 
{
    float temp = p_Plane->a * p_Point->x + 
                 p_Plane->b * p_Point->y + 
                 p_Plane->c * p_Point->z + p_Plane->d;

    if (temp > epsilon) 
    {
        return 1;
    }
    else if (temp < (-epsilon))
    {
        return -1;
    } 
    else
    {
        return 0;
    }
}

10.3.2 计算三角形面积和凸多边形面积

计算三角形的面积的方法有多种,最常用的就是把两个全等的三角形,组合成一个平行四边形,然后求出平行四边形的面积再除以2就可以了。当给定一个三角形的三个顶点坐标的时候,利用向量叉积的几何性质,就可以按照上述方法来求出三角形的面积。我们知道,两向量P×Q,有|P×Q| = |P|.|Q|.sinA,A是两向量的夹角。从几何意义上来说,两向量的叉积的模,就等于以这两向量的模的长度为不等边,组成的平行四边形的面积,如下图:

DXFrameWork提供了计算三角形面积的函数,如下:

XFLOAT triangleArea(D3DXVECTOR3* p0, D3DXVECTOR3* p1, 
                    D3DXVECTOR3* p2)
{
    D3DXVECTOR3 v1 = (*p1) - (*p0);
    D3DXVECTOR3 v2 = (*p2) - (*p0);
    return 0.5 * D3DXVec3Length(D3DXVec3Cross(&v1, &v1, &v2));
}

知道了三角形的面积如何计算,接下来凸多边形的面积也好计算了。无非就是把凸多边形分解为若干个三角形,计算每个三角形的面积后累加即可。

//第一个参数是凸多边形的顶点列表,第二个参数numPoints是凸多边形的顶点数
XFLOAT convexPolygonArea(D3DXVECTOR3* points, int numPoints) 
{
    int i;
    XFLOAT sum = 0.0;
    //注意points[0]是该凸多边形分解而成的三角形的共用顶点
    for (i = 2; i < numPoints; i++)
    {
        sum += triangleArea(&points[0],&points[i - 1],&points[i]);
    }
    return sum;
}

计算凸多边形的面积的示意图如下:

10.3.3 线段和面(face)相交检测

检查某线段是否和某面(face,注意不是平面)相交的代码如下:

bool checkEdgeIntersectsFace( D3DXVECTOR3 p_Edge[2], D3DXVECTOR3* p_Face, int numVertices,  D3DXPLANE* p_Plane, D3DXVECTOR3* p_PointOnPlane)  {
    //要进行相交判断的face,只能是三角形或者是四边形。
    if(numVertices > MAX_VERTICES_FOR_EDGE_INTERSECT_CHECKING) 
    {
        throw Error(_T("checkEdgeIntersectsFace : Number of
                        vertices used in checking an edge 
                      intersects with a face is too many"));
        return false;
    }

    // 通过计算面积,判断要检查的face是不是一个一维的线段。如果是就返回false
    XFLOAT area = convexPolygonArea(p_Face, numVertices);
    if ((area < 0.001) && (area > -0.001))
        return false; 

    //如果线段的两个端点都在face所处平面的同一侧,则显然这个线段是不会和该face相交的
    bool temp1, temp2;
    temp1 = positiveSide(&p_Edge[0], p_Plane);
    temp2 = positiveSide(&p_Edge[1], p_Plane);

    if (temp1 == temp2)
    {
        return false;
    }

    //再检查线段和face所在的平面是否相交,如果不相交,则线段肯定不和face相交
    if (D3DXPlaneIntersectLine(p_PointOnPlane, p_Plane, &p_Edge[0], &p_Edge[1]) == NULL) 
    {
        return false;
    }

如果计算到线段和face所在的平面相交,那么接下来就是要判断相交点是落在face的内侧还是外测了。在计算机图形学中,往往把三维对象通过降维处理,可以降低问题的复杂度。降维的方法是:通过去掉face的法线N的绝对值最大的分量所对应的坐标,就可以把问题降到二维空间来考虑。如下图所示,降维过程相当于把face投影到xy,xz或者是yz平面上。在此先假设被去掉的是z坐标,即投影到xy平面上。如下图投影多边形到XZ,YZ,XY平面上

判断某点在不在多边形内,可以把问题转化为判断点在不在某三角形内。如上图,把多边形划分为若干个三角形。然后判断点是否在这些三角形内,只要判断到点在某一三角形内,就肯定这点在此多边形内。先考虑如何判断点是否在三角形内。上面已经把三角形投影到一个二维平面来进行考虑。假定投影在了xz平面上。对三角形的每条边进行下面的二维差运算,有:

E = P1-P0
F=P2-P0
G=P-P0

从本质上说,这样做的意义上移动坐标系,使得顶点P0位于原点位置。或者可以认为是以P0为原点。如下图所示。

在上面的式子中,向量E所代表的边有内侧和外测之分,将边向量旋转90°(顺时针或者逆时针旋转都可以),便可以构造出该边的法向量,而又因为点F一定是在边的正侧,所以点积Ne.F的符号就是边OE的任一内侧点的符号。因此,如果P点位于该边的内侧的话,那么就必须要满足:

(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)则有:

NeX = (x1-x0)*cos90°+(y1-y0)*sin90°
NeY = -(x1-x0)*sin90°+(y1-y0)*cos90°

所以NeX=(y1-y0),NeY=-(x1-x0),求P2在P0P1的那一侧,就求P0P2与法线的夹角值就可以了:当:

Ne.(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)经过整理后,实质上就是下面行列式的值,如下:

|x0 y0 1|
|x1 y1 1|
|x2 y2 1|

所以判断点P是否在边e的内侧,就是把上面行列式中点P2的分量代替为点P的分量,只需要计算行列式的值是否大于0便可。大于0,在e的正侧,小于0在e的负侧。下面接着的代码就是根据这个原理实现。

    //接上段代码,    checkEdgeIntersectsFace函数,tools3d.cpp
    float absa = (float)fabs(p_Plane->a); 
    float absb = (float)fabs(p_Plane->b); 
    float absc = (float)fabs(p_Plane->c);

    static D3DXVECTOR2 
        face2D[MAX_VERTICES_FOR_EDGE_INTERSECT_CHECKING];

    D3DXVECTOR2 point2D;
    int i;

    //下面的几个if-else判断式,就是根据法线的分量大小,把三角形投影到适当的平面上去。
    if ((absa >= absb) && (absa >= absc)) 
    {
        for (i = 0; i < numVertices; i++)
        {
            face2D[i].x = p_Face[i].y;
            face2D[i].y = p_Face[i].z;
        }
        point2D.x = p_PointOnPlane->y;
        point2D.y = p_PointOnPlane->z;
    }
    else if ((absb >= absa) && (absb >= absc)) 
    {
        for (i = 0; i < numVertices; i++)
        {
            face2D[i].x = p_Face[i].x;
            face2D[i].y = p_Face[i].z;
        }
        point2D.x = p_PointOnPlane->x;
        point2D.y = p_PointOnPlane->z;
    } 
    else 
    {
        for (i = 0; i < numVertices; i++)
        {
            face2D[i].x = p_Face[i].x;
            face2D[i].y = p_Face[i].y;
        }
        point2D.x = p_PointOnPlane->x;
        point2D.y = p_PointOnPlane->y;
    }

    //p0,p1是多边形的线段的两端点,p2是想要检查的点。

    float val;
    //这里就是检查(Ne.F)(Ne.G)的结果值    
    val=(face2D[0].x * face2D[1].y + face2D[0].y * point2D.x 
         + face2D[1].x * point2D.y  ) -(point2D.x * 
         face2D[1].y + point2D.y * face2D[0].x + 
         face2D[1].x * face2D[0].y);
    bool cc = val > 0;
    bool cctemp;
    if (fabs(val) < 0.0001f)
     return true; //在边上

    //逐个边检查。
    for (i = 1; i < numVertices; i++)
    {
         val = (face2D[i].x * face2D[(i + 1) % numVertices].y 
                + face2D[i].y * point2D.x + face2D[(i + 1) % 
                numVertices].x * point2D.y) -
              (point2D.x * face2D[(i + 1) % numVertices].y + 
              point2D.y * face2D[i].x + face2D[(i + 1) %
              numVertices].x * face2D[i].y);

           if (fabs(val) < 0.0001f) return true; //在边上
         cctemp = val > 0;
         if ((cctemp != cc))
         {
             return false;
         }
    }
    return true; }

10.3.4 分割三角形

void splitTriangle(D3DXPLANE* p_Plane, D3DXVECTOR3* p0, 
                           D3DXVECTOR3* p1, D3DXVECTOR3* p2, 
                           unsigned short* positiveIndices, 
                           DWORD* p_NumPositiveIndices, 
                           unsigned short* negativeIndices, 
                          DWORD* p_NumNegativeIndices)
{
    //检查三角形的三个角顶点在分割平面的哪一则?正?负?面上?
    int sides[3];  //存储顶点与分割平面的位置信息
    int numzero = 0, i;//三角形角顶点在分割平面上的个数
    sides[0] = whichSide(p0, p_Plane);
    sides[1] = whichSide(p1, p_Plane);
    sides[2] = whichSide(p2, p_Plane);

    if (sides[0] == 0) numzero++;
    if (sides[1] == 0) numzero++;
    if (sides[2] == 0) numzero++;

    //如果没有角顶点在分割平面上
    if (numzero == 0) 
    {
        //检查有多少个角顶点在分割平面的正侧
        int numPositive = 0;
        for (i = 0; i < 3; i++) {
            if (sides[i] == 1) {
                numPositive++;
            }
        }

        //根据角顶点在分割平面的正侧的个数,分四种情况考虑。
        //情况1:没有一个角顶点在分割平面上,
        if (numPositive == 0) 
        {
              //没有一个角顶点在分割平面的正侧,那么所有的角顶点都在
              //分割平面的负侧
              //在分割平面的正侧的角顶点数为0
            *p_NumPositiveIndices = 0;
             //在分割平面的负侧的角顶点数为3
            *p_NumNegativeIndices = 3;

            //记录下在分割平面负侧的角顶点编号
            negativeIndices[0] = 0;
            negativeIndices[1] = 1;
            negativeIndices[2] = 2;
        }

        //有一个顶点在分割平面的正侧 
else if (numPositive == 1)
{
            // 找到哪个角顶点在分割平面的正侧
            int index;
            for (i = 0; i < 3; i++) {
                if (sides[i] == 1) {
                    index = i;
                    break;
                }
            }

            //原三角形在正侧部分被分割成1一个三角形,所以顶点数为3
            //在负侧部分被分割成2个三角形,所以顶点数为6
            *p_NumPositiveIndices = 3;
            *p_NumNegativeIndices = 6;

            positiveIndices[0] = 3 + (index + 2) % 3;
            positiveIndices[1] = index;
            positiveIndices[2] = 3 + index;

            negativeIndices[0] = 3 + index;
            negativeIndices[1] = (index + 1) % 3;
            negativeIndices[2] = 3 + (index + 2) % 3;

            negativeIndices[3] = (index + 1) % 3;
            negativeIndices[4] = (index + 2) % 3;
            negativeIndices[5] = 3 + (index + 2) % 3;

        }

  else if (numPositive == 2) {
            // 1 point is on negative side
            // Find which one is it
            int index;
            for (i = 0; i < 3; i++) {
                if (sides[i] == -1) {
                    index = i;
                    break;
                }
            }
            // Two triangles on positive side
            // One triangles on negative side
            *p_NumPositiveIndices = 6;
            *p_NumNegativeIndices = 3;

            positiveIndices[0] = 3 + index;
            positiveIndices[1] = (index + 1) % 3;
            positiveIndices[2] = 3 + (index + 2) % 3;

            positiveIndices[3] = (index + 1) % 3;
            positiveIndices[4] = (index + 2) % 3;
            positiveIndices[5] = 3 + (index + 2) % 3;

            negativeIndices[0] = 3 + (index + 2) % 3;
            negativeIndices[1] = index;
            negativeIndices[2] = 3 + index;

        } else if (numPositive == 3) {
            // Alll points are on positive side
            *p_NumPositiveIndices = 3;
            *p_NumNegativeIndices = 0;

            positiveIndices[0] = 0;
            positiveIndices[1] = 1;
            positiveIndices[2] = 2;
        } 
    }

     //如果有一个角顶点在分割平面上
else if (numzero == 1) {
        //One point is on the plane
        //Can either be 1. On one side of the plane 
        //                2. On two side of the plane
        int sum = sides[0] + sides[1] + sides[2];
        //-1+1+0=0,一个顶点在分割面正侧,另一个在负侧,一个在面上
        if (sum == 0) {
            //On two side of the plane
            int index;

            // Find which one is on the plane
            for (i = 0; i < 3; i++) {
                if (sides[i] == 0) {
                    index = i;
                    break;
                }
            }

            //分别找到在正侧和在负测的顶点的索引
            if (sides[(index + 1) % 3] == 1) {
                // Positive
                *p_NumPositiveIndices = 3;
                *p_NumNegativeIndices = 3;

                positiveIndices[0] = index;
                positiveIndices[1] = (index + 1) % 3;
                positiveIndices[2] = 3 + (index + 1) % 3;

                negativeIndices[0] = 3 + (index + 1) % 3;
                negativeIndices[1] = (index + 2) % 3;
                negativeIndices[2] = index;
            } else {
                // Negative
                *p_NumPositiveIndices = 3;
                *p_NumNegativeIndices = 3;

                positiveIndices[0] = 3 + (index + 1) % 3;
                positiveIndices[1] = (index + 2) % 3;
                positiveIndices[2] = index;

                negativeIndices[0] = index;
                negativeIndices[1] = (index + 1) % 3;
                negativeIndices[2] = 3 + (index + 1) % 3;
            }
        }

else {
            //On one side of the plane
            for (i = 0; i < 3; i++)    {
                if (sides[i] != 0) {
                    break;
                }
            }
            if (sides[i] == 1) {
                //The triangle is on positive sides
                *p_NumPositiveIndices = 3;
                *p_NumNegativeIndices = 0;

                positiveIndices[0] = 0;
                positiveIndices[1] = 1;
                positiveIndices[2] = 2;
            } else {
                //The triangle is on negative side
                *p_NumPositiveIndices = 0;
                *p_NumNegativeIndices = 3;

                negativeIndices[0] = 0;
                negativeIndices[1] = 1;
                negativeIndices[2] = 2;
            }
        }
    }

else if (numzero == 2) {
        //Two points are on the plane
        // See which one is not 
        for (i = 0; i < 3; i++)    {
            if (sides[i] != 0) {
                break;
            }
        }

        if (sides[i] == 1) {
            //The triangle is on positive side
            *p_NumPositiveIndices = 3;
            *p_NumNegativeIndices = 0;

            positiveIndices[0] = 0;
            positiveIndices[1] = 1;
            positiveIndices[2] = 2;

        } else {
            //The triangle is on negative side
            *p_NumPositiveIndices = 0;
            *p_NumNegativeIndices = 3;

            negativeIndices[0] = 0;
            negativeIndices[1] = 1;
            negativeIndices[2] = 2;
        }
    }

最后一种情况,当被分割的三角形的三个角顶点都在分割平面上,就要检查三角形的法线和分割平面的法线是否同向。同向则表示三角形被分割成一个,在分割平面的正侧;反向则表示三角形也被分割成一个,在分割平面的负侧。

else     
{
        D3DXVECTOR3 v01, v02, normal;

        //利用向量叉积的几何性质,根据三角形的两条边求此三角形的法线。要注意方向
        v01 = (*p1) - (*p0);
        v02 = (*p2) - (*p0);
        D3DXVec3Cross(&normal, &v01, &v02);
        D3DXVec3Normalize(&normal, &normal);

        //用D3DX库函数计算到平面的的法线。
        D3DXPLANE plane = *p_Plane;
        D3DXPlaneNormalize(&plane, &plane);
        D3DXVECTOR3 planeNormal =  D3DXVECTOR3(plane.a, plane.b, plane.c);

        //观察两法线的差
        D3DXVECTOR3 temp = planeNormal - normal;

        //如果两法线的差的模很小很小,接近于0,就可以认为这三角形的
        //法线和分割平面的法线是同向。三角形被分在分割平面的正侧,否则
        //就分在的负测
        if (D3DXVec3Length(&temp) < 0.01f) {
            // 在正侧
            *p_NumPositiveIndices = 3;
            *p_NumNegativeIndices = 0;

            positiveIndices[0] = 0;
            positiveIndices[1] = 1;
            positiveIndices[2] = 2;

        } else {
            // 在负测
            *p_NumPositiveIndices = 0;
            *p_NumNegativeIndices = 3;

            negativeIndices[0] = 0;
            negativeIndices[1] = 1;
            negativeIndices[2] = 2;
        }
    }
}

返回首页
上一章
下一章