mgcquadricsurface.cpp

《3D游戏引擎设计》的源码

            // Set as a flag for later use (avoids redundant copies of
            // edge triangle pointers).
            pkE0->m_apkTriangle[0] = 0;
            pkE1->m_apkTriangle[0] = 0;

            // For testing purposes, but not necessary for the algorithm.
            // This allows the display program to show the subdivision
            // structure.
            pkE1->m_uiStep = pkE0->m_uiStep;
        }

        // compute new centroid (for next step of iteration)
        ComputeCentroid(rkPoly,iVMax+iEMax);

        // Add new edges.  Vertex pointers are set to the new vertices, but
        // the triangle pointers are not calculated until later.
        //
        // Add new triangles.  The middle triangle will replace the old
        // triangle to save storage.  As a result, the adjacency values for
        // the middle triangle are calculated later since the current value
        // are needed globally for computing the other adjacencies.
        Triangle *pkT0, *pkT1, *pkT2, *pkT3;
        Vertex *pkM0, *pkM1, *pkM2;
        int iT, i0, i1, i2, i3, iOrient;
        int iTM1 = iTMax, iTM2 = 2*iTMax, iTM3 = 3*iTMax;
        iE = 2*iEMax;
        for (iT = 0; iT < iTMax; iT++, iTM1++, iTM2++, iTM3++)
        {
            // get triangle
            pkT0 = &rkPoly.m_apkTriangle[iT];

            // get vertices
            Vertex* pkV0 = pkT0->m_apkVertex[0];
            Vertex* pkV1 = pkT0->m_apkVertex[1];
            Vertex* pkV2 = pkT0->m_apkVertex[2];

            // get edges
            Edge* pkE0 = pkT0->m_apkEdge[0];
            Edge* pkE1 = pkT0->m_apkEdge[1];
            Edge* pkE2 = pkT0->m_apkEdge[2];

            // get adjacent triangles
            Triangle* pkA0 = pkT0->m_apkAdjacent[0];
            Triangle* pkA1 = pkT0->m_apkAdjacent[1];
            Triangle* pkA2 = pkT0->m_apkAdjacent[2];

            // get midpoints of triangle edges
            pkM0 = &rkPoly.m_apkVertex[iVMax+EdgeIndex(rkPoly,pkE0)];
            pkM1 = &rkPoly.m_apkVertex[iVMax+EdgeIndex(rkPoly,pkE1)];
            pkM2 = &rkPoly.m_apkVertex[iVMax+EdgeIndex(rkPoly,pkE2)];

            // get new edges and set vertex values
            Edge* pkE0New = &rkPoly.m_apkEdge[iE++];
            pkE0New->m_apkVertex[0] = pkM2;
            pkE0New->m_apkVertex[1] = pkM0;
            Edge* pkE1New = &rkPoly.m_apkEdge[iE++];
            pkE1New->m_apkVertex[0] = pkM0;
            pkE1New->m_apkVertex[1] = pkM1;
            Edge* pkE2New = &rkPoly.m_apkEdge[iE++];
            pkE2New->m_apkVertex[0] = pkM1;
            pkE2New->m_apkVertex[1] = pkM2;

            // For testing purposes, but not necessary for the algorithm.
            // This allows the display program to show the subdivision
            // structure.
            pkE0New->m_uiStep = uiS;
            pkE1New->m_uiStep = uiS;
            pkE2New->m_uiStep = uiS;

            // construct triangle T1
            pkT1 = &rkPoly.m_apkTriangle[iTM1];
            pkT1->m_apkVertex[0] = pkV0;
            pkT1->m_apkVertex[1] = pkM0;
            pkT1->m_apkVertex[2] = pkM2;
            pkT1->m_apkEdge[0] =
                ( pkE0->m_apkVertex[0] == pkV0 ? pkE0 : pkE0+iEMax );
            pkT1->m_apkEdge[1] = pkE0New;
            pkT1->m_apkEdge[2] =
                ( pkE2->m_apkVertex[0] == pkV0 ? pkE2 : pkE2+iEMax );
            pkT1->m_apkAdjacent[1] = pkT0;

            // construct triangle T2
            pkT2 = &rkPoly.m_apkTriangle[iTM2];
            pkT2->m_apkVertex[0] = pkM0;
            pkT2->m_apkVertex[1] = pkV1;
            pkT2->m_apkVertex[2] = pkM1;
            pkT2->m_apkEdge[0] =
                ( pkE0->m_apkVertex[0] == pkV1 ? pkE0 : pkE0+iEMax );
            pkT2->m_apkEdge[1] =
                ( pkE1->m_apkVertex[0] == pkV1 ? pkE1 : pkE1+iEMax );
            pkT2->m_apkEdge[2] = pkE1New;
            pkT2->m_apkAdjacent[2] = pkT0;

            // construct triangle T3
            pkT3 = &rkPoly.m_apkTriangle[iTM3];
            pkT3->m_apkVertex[0] = pkM2;
            pkT3->m_apkVertex[1] = pkM1;
            pkT3->m_apkVertex[2] = pkV2;
            pkT3->m_apkEdge[0] = pkE2New;
            pkT3->m_apkEdge[1] =
                ( pkE1->m_apkVertex[0] == pkV2 ? pkE1 : pkE1+iEMax );
            pkT3->m_apkEdge[2] =
                ( pkE2->m_apkVertex[0] == pkV2 ? pkE2 : pkE2+iEMax );
            pkT3->m_apkAdjacent[0] = pkT0;

            // set edge triangle pointers
            pkE0New->m_apkTriangle[0] = pkT0;
            pkE0New->m_apkTriangle[1] = pkT1;
            pkE1New->m_apkTriangle[0] = pkT0;
            pkE1New->m_apkTriangle[1] = pkT2;
            pkE2New->m_apkTriangle[0] = pkT0;
            pkE2New->m_apkTriangle[1] = pkT3;

            // get the indices for the subdivided triangles of A0
            i0 = TriangleIndex(rkPoly,pkA0);
            i1 = i0+iTMax;
            i2 = i1+iTMax;
            i3 = i2+iTMax;

            // Determine the orientation of A0 relative to T0 and set the
            // adjacency links.
            iOrient = AdjacentOrient(pkT0,pkA0);
            if ( iOrient == 0 )
            {
                pkT1->m_apkAdjacent[0] = &rkPoly.m_apkTriangle[i2];
                pkT2->m_apkAdjacent[0] = &rkPoly.m_apkTriangle[i1];
                rkPoly.m_apkTriangle[i2].m_apkAdjacent[0] = pkT1;
                rkPoly.m_apkTriangle[i1].m_apkAdjacent[0] = pkT2;
            }
            else if ( iOrient == 1 )
            {
                pkT1->m_apkAdjacent[0] = &rkPoly.m_apkTriangle[i3];
                pkT2->m_apkAdjacent[0] = &rkPoly.m_apkTriangle[i2];
                rkPoly.m_apkTriangle[i3].m_apkAdjacent[1] = pkT1;
                rkPoly.m_apkTriangle[i2].m_apkAdjacent[1] = pkT2;
            }
            else
            {
                pkT1->m_apkAdjacent[0] = &rkPoly.m_apkTriangle[i1];
                pkT2->m_apkAdjacent[0] = &rkPoly.m_apkTriangle[i3];
                rkPoly.m_apkTriangle[i1].m_apkAdjacent[2] = pkT1;
                rkPoly.m_apkTriangle[i3].m_apkAdjacent[2] = pkT2;
            }

            // get the indices for the subdivided triangles of A1
            i0 = TriangleIndex(rkPoly,pkA1);
            i1 = i0+iTMax;
            i2 = i1+iTMax;
            i3 = i2+iTMax;

            // Determine the orientation of A1 relative to T0 and set the
            // adjacency links.
            iOrient = AdjacentOrient(pkT0,pkA1);
            if ( iOrient == 0 )
            {
                pkT2->m_apkAdjacent[1] = &rkPoly.m_apkTriangle[i2];
                pkT3->m_apkAdjacent[1] = &rkPoly.m_apkTriangle[i1];
                rkPoly.m_apkTriangle[i2].m_apkAdjacent[0] = pkT2;
                rkPoly.m_apkTriangle[i1].m_apkAdjacent[0] = pkT3;
            }
            else if ( iOrient == 1 )
            {
                pkT2->m_apkAdjacent[1] = &rkPoly.m_apkTriangle[i3];
                pkT3->m_apkAdjacent[1] = &rkPoly.m_apkTriangle[i2];
                rkPoly.m_apkTriangle[i3].m_apkAdjacent[1] = pkT2;
                rkPoly.m_apkTriangle[i2].m_apkAdjacent[1] = pkT3;
            }
            else
            {
                pkT2->m_apkAdjacent[1] = &rkPoly.m_apkTriangle[i1];
                pkT3->m_apkAdjacent[1] = &rkPoly.m_apkTriangle[i3];
                rkPoly.m_apkTriangle[i1].m_apkAdjacent[2] = pkT2;
                rkPoly.m_apkTriangle[i3].m_apkAdjacent[2] = pkT3;
            }

            // get the indices for the subdivided triangles of A2
            i0 = TriangleIndex(rkPoly,pkA2);
            i1 = i0+iTMax;
            i2 = i1+iTMax;
            i3 = i2+iTMax;

            // Determine the orientation of A2 relative to T0 and set the
            // adjacency links.
            iOrient = AdjacentOrient(pkT0,pkA2);
            if ( iOrient == 0 )
            {
                pkT3->m_apkAdjacent[2] = &rkPoly.m_apkTriangle[i2];
                pkT1->m_apkAdjacent[2] = &rkPoly.m_apkTriangle[i1];
                rkPoly.m_apkTriangle[i2].m_apkAdjacent[0] = pkT3;
                rkPoly.m_apkTriangle[i1].m_apkAdjacent[0] = pkT1;
            }
            else if ( iOrient == 1 )
            {
                pkT3->m_apkAdjacent[2] = &rkPoly.m_apkTriangle[i3];
                pkT1->m_apkAdjacent[2] = &rkPoly.m_apkTriangle[i2];
                rkPoly.m_apkTriangle[i3].m_apkAdjacent[1] = pkT3;
                rkPoly.m_apkTriangle[i2].m_apkAdjacent[1] = pkT1;
            }
            else
            {
                pkT3->m_apkAdjacent[2] = &rkPoly.m_apkTriangle[i1];
                pkT1->m_apkAdjacent[2] = &rkPoly.m_apkTriangle[i3];
                rkPoly.m_apkTriangle[i1].m_apkAdjacent[2] = pkT3;
                rkPoly.m_apkTriangle[i3].m_apkAdjacent[2] = pkT1;
            }

            // add edge links to midpoint vertices
            if ( pkM0->m_iNumEdges == 0 )
            {
                // add four edges (first time edges are added for this vertex)
                pkM0->m_iNumEdges = 4;
                pkM0->m_apkEdge[0] = pkT1->m_apkEdge[0];
                pkM0->m_apkEdge[1] = pkT1->m_apkEdge[1];
                pkM0->m_apkEdge[2] = pkT2->m_apkEdge[2];
                pkM0->m_apkEdge[3] = pkT2->m_apkEdge[0];
            }
            else if ( pkM0->m_iNumEdges == 4 )
            {
                // add two edges (last time edges are added for this vertex)
                pkM0->m_iNumEdges = 6;
                pkM0->m_apkEdge[4] = pkT1->m_apkEdge[1];
                pkM0->m_apkEdge[5] = pkT2->m_apkEdge[2];
            }

            if ( pkM1->m_iNumEdges == 0 )
            {
                // add four edges (first time edges are added for this vertex)
                pkM1->m_iNumEdges = 4;
                pkM1->m_apkEdge[0] = pkT2->m_apkEdge[1];
                pkM1->m_apkEdge[1] = pkT2->m_apkEdge[2];
                pkM1->m_apkEdge[2] = pkT3->m_apkEdge[0];
                pkM1->m_apkEdge[3] = pkT3->m_apkEdge[1];
            }
            else if ( pkM1->m_iNumEdges == 4 )
            {
                // add two edges (last time edges are added for this vertex)
                pkM1->m_iNumEdges = 6;
                pkM1->m_apkEdge[4] = pkT2->m_apkEdge[2];
                pkM1->m_apkEdge[5] = pkT3->m_apkEdge[0];
            }

            if ( pkM2->m_iNumEdges == 0 )
            {
                // add four edges (first time edges are added for this vertex)
                pkM2->m_iNumEdges = 4;
                pkM2->m_apkEdge[0] = pkT1->m_apkEdge[2];
                pkM2->m_apkEdge[1] = pkT1->m_apkEdge[1];
                pkM2->m_apkEdge[2] = pkT3->m_apkEdge[0];
                pkM2->m_apkEdge[3] = pkT3->m_apkEdge[2];
            }
            else if ( pkM2->m_iNumEdges == 4 )
            {
                // add two edges (last time edges are added for this vertex)
                pkM2->m_iNumEdges = 6;
                pkM2->m_apkEdge[4] = pkT1->m_apkEdge[1];
                pkM2->m_apkEdge[5] = pkT3->m_apkEdge[0];
            }
        }

        // Set middle triangle vertex, edge, and triangle pointers.  Set
        // edge triangle pointers.
        iTM1 = iTMax;
        iTM2 = 2*iTMax;
        iTM3 = 3*iTMax;
        for (iT = 0; iT < iTMax; iT++, iTM1++, iTM2++, iTM3++)
        {
            // get subdivided triangles
            pkT0 = &rkPoly.m_apkTriangle[iT];
            pkT1 = &rkPoly.m_apkTriangle[iTM1];
            pkT2 = &rkPoly.m_apkTriangle[iTM2];
            pkT3 = &rkPoly.m_apkTriangle[iTM3];

            // get midpoints of original triangle edges
            pkM0 = &rkPoly.m_apkVertex[iVMax+EdgeIndex(rkPoly,
                pkT0->m_apkEdge[0])];
            pkM1 = &rkPoly.m_apkVertex[iVMax+EdgeIndex(rkPoly,
                pkT0->m_apkEdge[1])];
            pkM2 = &rkPoly.m_apkVertex[iVMax+EdgeIndex(rkPoly,
                pkT0->m_apkEdge[2])];

            // set vertices for middle triangle
            pkT0->m_apkVertex[0] = pkM2;
            pkT0->m_apkVertex[1] = pkM0;
            pkT0->m_apkVertex[2] = pkM1;

            // set edges for middle triangle
            pkT0->m_apkEdge[0] = pkT1->m_apkEdge[1];
            pkT0->m_apkEdge[1] = pkT2->m_apkEdge[2];
            pkT0->m_apkEdge[2] = pkT3->m_apkEdge[0];

            // set adjacencies for middle triangle
            pkT0->m_apkAdjacent[0] = pkT1;
            pkT0->m_apkAdjacent[1] = pkT2;
            pkT0->m_apkAdjacent[2] = pkT3;

            // set edge triangle pointers
            if ( pkT1->m_apkEdge[0]->m_apkTriangle[0] == 0 )
            {
                pkT1->m_apkEdge[0]->m_apkTriangle[0] = pkT1;
                pkT1->m_apkEdge[0]->m_apkTriangle[1] = pkT1->m_apkAdjacent[0];
            }
            if ( pkT1->m_apkEdge[2]->m_apkTriangle[0] == 0 )
            {
                pkT1->m_apkEdge[2]->m_apkTriangle[0] = pkT1;
                pkT1->m_apkEdge[2]->m_apkTriangle[1] = pkT1->m_apkAdjacent[2];
            }

            if ( pkT2->m_apkEdge[0]->m_apkTriangle[0] == 0 )
            {
                pkT2->m_apkEdge[0]->m_apkTriangle[0] = pkT2;
                pkT2->m_apkEdge[0]->m_apkTriangle[1] = pkT2->m_apkAdjacent[0];
            }
            if ( pkT2->m_apkEdge[1]->m_apkTriangle[0] == 0 )
            {
                pkT2->m_apkEdge[1]->m_apkTriangle[0] = pkT2;
                pkT2->m_apkEdge[1]->m_apkTriangle[1] = pkT2->m_apkAdjacent[1];
            }

            if ( pkT3->m_apkEdge[1]->m_apkTriangle[0] == 0 )
            {
                pkT3->m_apkEdge[1]->m_apkTriangle[0] = pkT3;
                pkT3->m_apkEdge[1]->m_apkTriangle[1] = pkT3->m_apkAdjacent[1];
            }
            if ( pkT3->m_apkEdge[2]->m_apkTriangle[0] == 0 )
            {
                pkT3->m_apkEdge[2]->m_apkTriangle[0] = pkT3;
                pkT3->m_apkEdge[2]->m_apkTriangle[1] = pkT3->m_apkAdjacent[2];
            }
        }

        // Adjust edge pointers of original vertices to account for the
        // edge splitting.
        for (int iV = 0; iV < iVMax; iV++)
        {
            Vertex* pkV = &rkPoly.m_apkVertex[iV];
            for (iE = 0; iE < pkV->m_iNumEdges; iE++)
            {
                Edge* pkE = pkV->m_apkEdge[iE];
                if ( pkE->m_apkVertex[0] != pkV
                &&   pkE->m_apkVertex[1] != pkV )
                {
                    pkV->m_apkEdge[iE] = &rkPoly.m_apkEdge[
                        iEMax+EdgeIndex(rkPoly,pkE)];
                }
            }
        }

        // update indices
        iVMax = iVMax + iEMax;
        iEMax = 2*iEMax + 3*iTMax;
        iTMax = 4*iTMax;
    }
}
//---------------------------------------------------------------------------
void MgcQuadricSurface::DeletePolyhedron (ConvexPolyhedron& rkPoly)
{
    // assumes that rkPoly.vertex[*].point was dynamically allocated
    for (int i = 0; i < rkPoly.m_iNumVertices; i++)
    {
        delete rkPoly.m_apkVertex[i].m_pkPoint;
        delete[] rkPoly.m_apkVertex[i].m_apkEdge;
    }

    delete[] rkPoly.m_apkVertex;
    delete[] rkPoly.m_apkEdge;
    delete[] rkPoly.m_apkTriangle;

    rkPoly.m_iNumVertices = 0;
    rkPoly.m_apkVertex = 0;
    rkPoly.m_iNumEdges = 0;
    rkPoly.m_apkEdge = 0;
    rkPoly.m_iNumTriangles = 0;
    rkPoly.m_apkTriangle = 0;
}
//---------------------------------------------------------------------------