BSP Tree

//-----------------------------------------------------------------------------
// Name : splitPolygon
// Desc : This function is used to do ALL the clipping and Splitting of 
//        polygons. It takes a polygon and a Plane and splits 
//        the polygon into to two seperate polygons. When used for clipping to 
//        a plane, call this function and then simply discard the front or
//        back depending on your needs.
// NOTE : FRONT and BACK MUST be valid pointers to empty Polygon structures as 
//        this function does NOT allocate the memory for them. The reason for
//        this is that this function is used in so many cases and some of them
//        required the Front and Back already be initialized. 
//-----------------------------------------------------------------------------
void CMyD3DApplication::splitPolygon( POLYGON *Poly, POLYGON *Plane, 
                   POLYGON *FrontSplit, POLYGON *BackSplit )
{
    // 50 is used here, as we should never really have more 
    // points on a portal than this.
    VERTEX FrontList[50];
    VERTEX BackList[50];
    int PointLocation[50];
    int CurrentVertex = 0;
    int FrontCounter  = 0;
    int BackCounter   = 0;
    int InFront       = 0;
    int Behind        = 0;
    int OnPlane       = 0;
    int Location      = 0;

    // Determine each points location relative to the plane.
    for( int i = 0; i < Poly->nNumberOfVertices; i++ )  
    {
        Location = classifyPoint((D3DXVECTOR3*)&Poly->VertexList, Plane);

        if (Location == POINTPOSITION_FRONT )
            ++InFront;
        else if (Location == POINTPOSITION_BACK )
            ++Behind;
        else
            ++OnPlane;

        PointLocation = Location;
    }
    
    // We set the VertexList[0] location again at the end
    // of the array so that we don't have to check and loop later
    //PointLocation[Poly->nNumberOfVertices] = PointLocation[0];

    if( !InFront ) 
    {
        memcpy(BackList, Poly->VertexList, Poly->nNumberOfVertices * sizeof(VERTEX));
        BackCounter = Poly->nNumberOfVertices;
    }

    if( !Behind ) 
    {
        memcpy(FrontList, Poly->VertexList, Poly->nNumberOfVertices * sizeof(VERTEX));
        FrontCounter = Poly->nNumberOfVertices;
    }

    if( InFront && Behind ) 
    {
        for( i = 0; i < Poly->nNumberOfVertices; ++i) 
        {
            // Store Current vertex remembering to MOD with number of vertices.
            CurrentVertex = (i+1) % Poly->nNumberOfVertices;

            if (PointLocation == POINTPOSITION_ONPLANE ) 
            {
                FrontList[FrontCounter] = Poly->VertexList;
                ++FrontCounter;
                BackList[BackCounter] = Poly->VertexList;
                ++BackCounter;
                continue; // Skip to next vertex
            }
            if (PointLocation == POINTPOSITION_FRONT ) 
            {
                FrontList[FrontCounter] = Poly->VertexList;
                ++FrontCounter;
            } 
            else 
            {
                BackList[BackCounter] = Poly->VertexList;
                ++BackCounter;
            }
            
            // If the next vertex is not causing us to span the plane then continue
            //if (PointLocation[i+1] == CP_ONPLANE || PointLocation[i+1] == PointLocation) continue;
            if( PointLocation[CurrentVertex] == POINTPOSITION_ONPLANE || 
                PointLocation[CurrentVertex] == PointLocation ) 
                continue;
            
            // Otherwise create the new vertex
            D3DXVECTOR3 IntersectPoint;
            float       percent;

            getIntersect( (D3DXVECTOR3*)&Poly->VertexList, 
                          (D3DXVECTOR3*)&Poly->VertexList[CurrentVertex], 
                          (D3DXVECTOR3*)&Plane->VertexList[0], 
                          &Plane->Normal, &IntersectPoint, &percent );

            // create new vertex  
            VERTEX copy;
           
            copy.x       = IntersectPoint.x;
            copy.y       = IntersectPoint.y;
            copy.z       = IntersectPoint.z;
           

            BackList[BackCounter++]   = copy;
            FrontList[FrontCounter++] = copy;
        }
    }

    //OK THEN LETS BUILD THESE TWO POLYGONAL 

    FrontSplit->nNumberOfVertices = 0;
    BackSplit->nNumberOfVertices  = 0;

    // Copy over the vertices into the new polys
    FrontSplit->nNumberOfVertices = FrontCounter;
    memcpy(FrontSplit->VertexList, FrontList, FrontCounter * sizeof(VERTEX));
    BackSplit->nNumberOfVertices  = BackCounter;
    memcpy(BackSplit->VertexList, BackList, BackCounter * sizeof(VERTEX));

   
    // Copy Extra Values
    FrontSplit->Normal = Poly->Normal;
    BackSplit->Normal  = Poly->Normal;
}