Jump to content
  • Advertisement
Sign in to follow this  

BSP Tree

This topic is 4438 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am building up a BSP tree for collision detection. my BuildBsptree() function uses // Split the poly into two fragments splitPolygon( polyTest, CurrentNode->Splitter, FrontSplit, BackSplit); whenever there is need 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. My problem is locking of vertex & index buffer for memcpy function. There are 3 calls to memcpy() function in splitPolygon(). can i use default options for all directx buffers. while calling memcpy() function should i lock both vertex as well as index buffer; and with what options?
// 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 )
        else if (Location == POINTPOSITION_BACK )

        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;
                BackList[BackCounter] = Poly->VertexList;
                continue; // Skip to next vertex
            if (PointLocation == POINTPOSITION_FRONT ) 
                FrontList[FrontCounter] = Poly->VertexList;
                BackList[BackCounter] = Poly->VertexList;
            // 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 ) 
            // Otherwise create the new vertex
            D3DXVECTOR3 IntersectPoint;
            float       percent;

            getIntersect( (D3DXVECTOR3*)&Poly->VertexList, 
                          &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;


    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;

Share this post

Link to post
Share on other sites
It's worth baring in mind that BSP trees were a really cool technology a while back, but they're not necessarily all that great these days. They were an amazing optimization when developers really had to get directly to the metal and shaving any and every polygon was A Good Thing™

With modern GPU's being the monsters that they are, you can often get better performance by throwing that extra data at it. That is, sending extra geometry to render is quicker than the overhead incurred by culling/clipping and processing a precise visible set. BSP's require CPU-based sorting and manipulation and also uploading the resulting data set to the GPU - neither of which is particularly good for performance.

A few thoughts..
  1. A minor nitpick, but I notice you're using memcpy() and not the preferred memcpy_s() [wink]
  2. buffer creation and locking flags will be crucial if you want good performance from resource manipulation. You should be making the buffers dynamic and write-only, ideally also locking with discard.
  3. minimal lock time. Try to make the lock time as short as possible. Ideally lock, write and unlock - don't do any CPU processing between those locks. As the name implies, having the resource locked stops any other rendering that is queued up and other nasty stalling type things. The best strategy would be to compose a system-memory array from your BSP algorithm and then upload the whole thing in a single call. Don't lock/write/unlock each time you make a single change.
  4. minimal number of locks. A simple one really: Locking is expensive - only do it when you absolutely have to.


Share this post

Link to post
Share on other sites
I agree with the previous post, but I'd say also that _do not_ mix your BSP with vertex buffer / index buffers. A good guide line is that VB and IBs are used only for rendering (ie. transferring data to GPU). Of course there are exceptions.

So, drop the VB and locks, and the sun will shine on you :) you should definetely not use them while doing collision detection. If I understood you correctly, you won't use BSP for rendering.

Best regards

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!