These tutorials focus mainly on OpenGL, Win32 programming and the ODE physics engine. OpenGL has moved on to great heights and I don't cover the newest features but cover all of the basic concepts you will need with working example programs.

 

Working with the Win32 API is a great way to get to the heart of Windows and is just as relevant today as ever before. Whereas ODE has been marginalized as hardware accelerated physics becomes more common.

 

Games and graphics utilities can be made quickly and easily using game engines like Unity so this and Linux development in general will be the focus of my next tutorials.    

  

 

This tutorial describes the method I have developed to calculate the Potentially Visible Set (PVS) of leaves of a BSP tree in real-time. Unlike other methods that pre-calculate the PVS as part of the world data, this method uses the view frustum and the current leaf node's portals to find which leaves are potentially in view.

 

The first step is to find which leaf node the camera is in and mark it as visible, then loop through all the portals in the node, clipping them to five of the six view frustum planes (all except the near plane.) If a portal fails to be in front of or clipped by all five planes then we know that the portal is outside the frustum and move on to the next portal. If a portal is found to be in front of all the planes after the clipping then it is within view and we pass the clipped portal to a recursive function that performs a very similar task.

The recursive function begins by marking the back leaf of the portal passed in as visible. It then takes the portal and creates a new n-sided frustum using the vertices of the portal and the camera position. With this new frustum, it loops through all the portals in the back leaf of the portal passed in, clipping them as it goes. If a portal in the back leaf is found to have survived all the clipping then it too is in view, so the function calls itself, passing in this new clipped portal. After all the recursion, the visible leaves of the BSP tree will have been marked as visible. As the tree is rendered, we only process the visible leaves and set them back to non-visible afterwards ready for the next frame.

 

This is the function to find the current leaf. The parameters are the camera's position and the root node of the BSP tree. It returns the id of the current leaf node.


int FindCurrentLeaf(VECTOR Position, BSP_node* node)

{

    if (node->leaf == true)

    {

        numcurrentportals = node->numportals;

        return node->nodeid;

    }



    VECTOR edge1, edge2, planeNormal, temp;

    // get the partitioning planes normal

    edge1.x = node->partition.Vertex[1].x - node->partition.Vertex[0].x;

    edge1.y = node->partition.Vertex[1].y - node->partition.Vertex[0].y;

    edge1.z = node->partition.Vertex[1].z - node->partition.Vertex[0].z;

    edge2.x = node->partition.Vertex[2].x - node->partition.Vertex[0].x;

    edge2.y = node->partition.Vertex[2].y - node->partition.Vertex[0].y;

    edge2.z = node->partition.Vertex[2].z - node->partition.Vertex[0].z;

    planeNormal = CrossVector(edge1, edge2);

    temp.x = node->partition.Vertex[0].x;

    temp.y = node->partition.Vertex[0].y;

    temp.z = node->partition.Vertex[0].z;



    int side = ClassifyPoint(Position, temp, planeNormal);



    if (side == 1 || side == 0)

    {

        return FindCurrentLeaf(Position, node->frontnode);

    }

    else

    {

        return FindCurrentLeaf(Position, node->backnode);

    }

}


GLvoid CalculatePVS(int currentleaf)

{

    int flag, result, counter, parentid, portalnumber, planenumber;

    VECTOR pointOnPlane;

    VECTOR ZUnit = camera[currentCamera].GetZUnit(); // camera's direction vector

    ListNode* CurrentNode;

    PORTAL* CurrentPortal;

    PORTAL* front = new PORTAL;

    PORTAL* back = new PORTAL;



    parentid = currentleaf;

    CurrentNode = LeafList.Get(currentleaf);

    CurrentNode->node->visible = true;

    // loop through the portals of the current leafnode

    for (portalnumber = 1; portalnumber <=

         CurrentNode->node->numportals; portalnumber++)

    {

        counter = 0;

        CurrentPortal = CurrentNode->node->portallist.Get(portalnumber);

        flag = 1;

        // loop through the frustum planes

        for (planenumber = 0; planenumber < 6; planenumber++)

        {

            // find a point on the far plane by projecting

            // the camera's direction vector

            if (planenumber == 4)

            {

                pointOnPlane.x = camera[currentCamera].Position.x;

                pointOnPlane.x -= ZUnit.x * 500.0;

                pointOnPlane.y = camera[currentCamera].Position.y;

                pointOnPlane.y -= ZUnit.y * 500.0;

                pointOnPlane.z = camera[currentCamera].Position.z;

                pointOnPlane.z -= ZUnit.z * 500.0;

            }

            else if (planenumber == 5) // skip the near frustum plane test

                continue;

            else

                // the camera position is a point on the frustum planes

                pointOnPlane = camera[currentCamera].Position;



            result = SplitPortal(CurrentPortal, frustum[planenumber], pointOnPlane

                     , front, back);

            if (result == PortalWasSplit)

            {

                delete[] back->Vertex;

                if (flag == 0)   // if there has been a previous split portal

                {

                    delete[] CurrentPortal->Vertex;

                    delete CurrentPortal;

                }

                flag = 0;

                CurrentPortal = front;

                front = new PORTAL;

            }

            if (result != Back)

                counter++;

        }

        // if the portal was split by or infront of the planes

        if (counter == 5)

        {

            FindVisibleLeaves(parentid, CurrentPortal, CurrentNode, portalnumber);

        }

        if (flag == 0)  // if there has been at least one split portal

        {

            delete[] CurrentPortal->Vertex;

            delete CurrentPortal;

        }

    }

    delete front;

    delete back;

}





GLvoid FindVisibleLeaves(int Parent, PORTAL* CurrentPortal, ListNode* ParentNode,

                         int portalnumber)

{

    int loop, numPlanes, leafnumber, Nminus1, counter, flag, result,

    parentid, planenumber;

    VECTOR edge1, edge2, pointOnPlane, planesNormal;

    ListNode* CurrentNode;

    PORTAL* front = new PORTAL;

    PORTAL* back = new PORTAL;

    PORTAL* inputPortal;



    inputPortal = ParentNode->node->portallist.Get(portalnumber);

    parentid = inputPortal->backleaf->nodeid;

    CurrentNode = LeafList.Get(parentid);

    CurrentNode->node->visible = true;



    // Create the planes from CurrentPortal

    pointOnPlane = camera[currentCamera].Position;



    numPlanes = CurrentPortal->numVertices;

    PLANE* Planes = new PLANE[numPlanes];

    for (loop = 0; loop < numPlanes; loop++)

    {

        if (loop == 0)

            Nminus1 = numPlanes - 1;

        else

            Nminus1 = loop - 1;

        // get the normal from edges

        edge1.x = CurrentPortal->Vertex[loop].x -

                  camera[currentCamera].Position.x;

        edge1.y = CurrentPortal->Vertex[loop].y -

                  camera[currentCamera].Position.y;

        edge1.z = CurrentPortal->Vertex[loop].z -

                  camera[currentCamera].Position.z;

        edge2.x = CurrentPortal->Vertex[Nminus1].x -

                  camera[currentCamera].Position.x;

        edge2.y = CurrentPortal->Vertex[Nminus1].y -

                  camera[currentCamera].Position.y;

        edge2.z = CurrentPortal->Vertex[Nminus1].z -

                  camera[currentCamera].Position.z;

        planesNormal = CrossVector(edge1, edge2);

        Planes[loop].nx = planesNormal.x;

        Planes[loop].ny = planesNormal.y;

        Planes[loop].nz = planesNormal.z;

    }



    // loop through the portals of this leafnode

    for (portalnumber = 1; portalnumber <=

         CurrentNode->node->numportals; portalnumber++)

    {

        counter = 0;

        CurrentPortal = CurrentNode->node->portallist.Get(portalnumber);

        flag = 1;

        // if the backleaf isn't the parent

        if (CurrentPortal->backleaf->nodeid != Parent)

        {

            // loop through the planes

            for (planenumber = 0; planenumber < numPlanes; planenumber++)

            {

                result = SplitPortal(CurrentPortal, Planes[planenumber],

                         pointOnPlane, front, back);

                if (result == PortalWasSplit)

                {

                    delete[] back->Vertex;

                    if (flag == 0)   // if there has been a previous split polygon

                    {

                        delete[] CurrentPortal->Vertex;

                        delete CurrentPortal;

                    }

                    flag = 0;

                    CurrentPortal = front;

                    front = new PORTAL;

                }

                if (result != Back)

                    counter++;

            }

            // if the portal was split by or infront of all the planes

            if (counter == numPlanes)

            {

                FindVisibleLeaves(parentid, CurrentPortal,

                                  CurrentNode, portalnumber);

            }

            if (flag == 0)   // if there has been at least one split polygon

            {

                delete[] CurrentPortal->Vertex;

                delete CurrentPortal;

            }

        }

    }

    delete[] Planes;

    delete front;

    delete back;

}