Upcoming Events
Unite 2010
11/10 - 11/12 @ Montréal, Canada

GDC China
12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010
12/24 - 12/27  

GDC 2011
2/28 - 3/4 @ San Francisco, CA

More events...
Quick Stats
49 people currently visiting GDNet.
2406 articles in the reference section.

Help us fight cancer!
Join SETI Team GDNet!
Link to us Events 4 Gamers
Intel sponsors gamedev.net search:

A very simple example

This is a 2 room scene. The BSP Tree has 3 nodes (2 of them are leaves).

Red triangles are those we are using to clip against portals.
Blue polygons indicatate portals that have beel culled (m_bCulled = TRUE)
Yellow polygons indicate portals that have not been culled (m_bCulled = FALSE)

Step 1

GeneratePortal(BspNode0,NULL)

We generate a SuperPlane at the dividing plane of the root node of the bsp tree, and we also create a large portal (portal 1) on the SuperPlane(the blue rectangle).

Assume the portal's plane normal points to BspNode0(the left space), and

portal1.m_iLeftNode = -1;
portal1.m_iRightNode = -2;

Step 2

GeneratePortal(BspNode1,SuperPlane)

This is a leaf node, so we have to use all the triangles in BspNode1 to clip against all the portals in SuperPlane. We find the first suitable triangle (the red one), and divide portal 1 into portal 1 and portal2. Portal 1 is on the positive side of the triangle, so its m_bCulled member is set to FALSE (and it is shown in yellow). Portal 2 is on the negative side of the triangle, so its m_bCulled member is set to TRUE (and it is shown in blue).

Step3

We find the second suitable triangle, and divide portal 1 into portal 1 and portal 3. Portal 3 is the yellow one and portal 1 is the blue one at the top.

Step 4

Next we find the third suitable triangle, and divide portal 3 into portal 3 and portal 4.

Step5

Next we find the last suitable triangle in BspNode1, and clip portal 4 into portal 4 and portal 5.

Note that these pictures are from an old version, where we're doing all portal filter processing in the final step, but actually you can do some filter processing as we describe in the algorithm)

Step 6

GeneratePortal(BspNode2,SuperPlane)

BspNode2 is also a leaf node, so we have to use all triangles in the leaf to clip against all the portals in SuperPlane

We find the first suitable trianle in BspNode2, and divide portal 6 into portal 5 and portal 6.

Step 7

We find the second suitable triangle, and clip portal 6 into portal 6 and portal 7.

Step 8

We find the last suitable triangle in BspNode2, and clip portal 7 into portal 7 and portal 8.

Step 9

After deleting all the blue portals we get what we want, the yellow portal that connects BspNode1 and BspNode2.

Here is the detailed version:

void CBspTree::GeneratePortal(CBspTreeNode *pBspNode_, CSuperPlane *pSuperPlane_)
{
   CPortal *pTemp1,*pTemp2;
   int iCount;
 
   if (pBspNode_->IsLeaf ())
   {
      if (!pSuperPlane_) return; //You should give us a bsp tree with more than 1 node!
 
      for (each triangle T in pBspNode_)
      {
         iCount = pSuperPlane_->m_ListOfPortals.GetCount();
         for (each portal  P  in pSuperPlane_->m_ListOfPortals)
         {
            iCount--;
            if (iCount<0) break;
            //please keep in mind,this process is
            //to trace the validation of each portal
            int *pInt;
            if (P->m_iLeftNode == pBspNode->m_iTag)
               pInt = &P->m_iLeftNode;
            else if (P->m_iRightNode == pBspNode->m_iTag)
               pInt = &P->m_iRightNode;
            else continue; // P has no relationship with this pBspNode_,so just ignore P
 
            if (TriangleIntersectPolygon(T,P->m_polygon))
            {
               pTemp1 = new CPortal;
               pTemp2 = new CPortal;
               pTemp1.m_bCulled = FALSE;
               pTemp2.m_bCulled = TRUE;
               ClipPortal(T->m_Plane, P,*pTemp1,*pTemp2);
               if (!pTemp1->Reasonable()|| !pTemp2->Reasonable())
               {
                  //Abort this operation
                  delete pTemp1;
                  delete pTemp2;
                  continue;
               }
               pSuperPlane_->m_ListOfPortals.Add(pTemp1);
               pSuperPlane_->m_ListOfPortals.Add(pTemp2);
               pSuperPlane_->m_ListOfPortals.Remove(P);
            }
         }
      }
      
      //OK,now we can delete those Culled portals in this leaf!
      for (each portal  P  in pSuperPlane_->m_ListOfPortals)
      {
         if ((P->m_iLeftNode!=pBspNode_->m_iTag)&&
             (P->m_iRightNode!=pBspNode_->m_iTag))
            continue;
         if (P->m_bCulled)
            pSuperPlane_->Remove(P);
      }
   }
   else
   {
      if (pSuperPlane)
      {
         iCount = pSuperPlane_->m_ListOfPortals.GetCount();
         for (each portal  P  in pSuperPlane_->m_ListOfPortals)
         {
            iCount--;
            if (iCount<0) break;
            //please keep in mind,this process is
            //to trace connection information of each portal
 
            int *pInt;
            if (P->m_iLeftNode == pBspNode->m_iTag)
               pInt = &P->m_iLeftNode;
            else if (P->m_iRightNode == pBspNode->m_iTag)
               pInt = &P->m_iRightNode;
            else continue;// P has no relationship with this pBspNode_,so just ignore P
 
            switch (CalculateSide(pBspNode_->m_DividingPlane,&P->m_Polygon))
            {
            case Polygon is on positive side of the dividing plane:
               *pInt = pBspNode_->m_pLeftNode->m_iTag;
               break;
            case Polygon is on negative side of the dividing plane:
               *pInt = pBspNode_->m_pRightNode->m_iTag;
               break;
            case Polygon is spanning the dividing plane:
               pTemp1 = new CPortal;
               pTemp2 = new CPortal;
               pTemp1->m_bCulled = P->m_bCulled;
               pTemp2->m_bCulled = P->m_bCulled;
               if (*pInt == pPortal->m_iLeftNode)
               {
                  This means we only need to update the left connection information:
                  pTemp1->m_iLeftNode = pBspNode_->m_pLeftNode->m_iTag;
                  pTemp2->m_iLeftNode = pBspNode_->m_pRightNode->m_iTag;
 
                  pTemp1->m_iRightNode = pBspNode_->m_pRightNode->m_iTag;
                  pTemp2->m_iRightNode = pBspNode_->m_pRightNode->m_iTag;
               }
               else
               {
                  This means we only need to update the right connection information:
                  pTemp1->m_iRightNode = pBspNode_->m_pLeftNode->m_iTag;
                  pTemp2->m_iRightNode = pBspNode_->m_pRightNode->m_iTag;
                  
                  pTemp1->m_iLeftNode = pBspNode_->m_pLeftNode->m_iTag;
                  pTemp2->m_iLeftNode = pBspNode_->m_pLeftNode->m_iTag;
               }
               
               ClipPortal(pBspNode_->m_DividingPlane,P,*pTemp1,*pTemp2);
               pSuperPlane_->m_ListOfPortals.Add(pTemp1);
               pSuperPlane_->m_ListOfPortals.Add(pTemp2);
               pSuperPlane_->m_ListOfPortals.Remove(P);
               break;
            case Polygon is coincide with the dividing plane:
               
               This situation should not happen, but it could. If this happens, that
               means your bsp tree is not organized well, for you have used a dividing
               plane which almost coincide with another dividing plane on the parent
               node. You should make sure your bsp tree is reasonable, or just do
               nothing here.
               break;
            }
         }
         GeneratePortal(pBspNode_->m_pLeftNode,pSuperPlane_);
         GeneratePortal(pBspNode_->m_pRightNode,pSuperPlane_);
      }
 
      if (!pBspNode_->m_bPushed) //we haven't generated a SuperPlane at pBspNode_
      {
         pBspNode_->m_bPushed = TRUE;
         CPortal* pPortal = new CPortal;
         CSuperPlane* pNewSuperPlane = new CSuperPlane;
         m_ListOfSuperPlanes.Add(pNewSuperPlane);
 
         On this superplane, generate a large enough polygon for the portal which exceeds the
         boundary of the bounding box of the environment. In our method we use a rectangle,
         but you can use other shapes as long as you meet the requirement. Then add those
         points to pPortal->m_Polygon
 
         In our assumption, the portals on the SuperPlane of pBspNode_ should only connect
         the regions in the subtree of pBspNode_, so we should confine the polygon of portal
         on the Superplane to the convex space of pBspNode_, this will optimize the
         performance. We achieve this by cliping the polygon against all the planes that on
         parent nodes of pBspNode_ as below:
         CbspNode* pTempNode,pPrevNode
         PPrevNode = pBspNode_;
 
         for (pTempNode = pBspNode_->m_pParent;pTempNode!= NULL;
                pTempNode = pTempNode->m_pParent)
         {
            if (pTempPortal is spanning the dividing plane of pTempNode)
            {
               ClipPortal(pTempNode->m_DividingPlane,pPortal,*pTemp1,*pTemp2);
               if (pPrevNode == pTempNode->m_pLeftNode)
                  *pPortal = *pTemp1;
               else
                  *pPortal = *pTemp2;
               delete pTemp1;
               delete pTemp2;
            }
            pPrevNode = pTempNode;
         }
         pNewSuperPlane->m_ListOfPortals.Add(pPortal);
 
         Now get the connection information of the Portal we have just generated,
         C3DPoint v1,v2,v3;
         v1=pPortal->m_Polygon.m_pPoints[0]-pPortal->m_Polygon.m_pPoints[1];
         v2=pPortal->m_Polygon.m_pPoints[2]-pPortal->m_Polygon.m_pPoints[1];
         v1.Normalize();
         v2.Normalize();
         v3=CrossProduct(v2,v1);
         if (DotProduct(v3, pBspNode->m_DividingPlane.Normal)>0)
         {
            The normal of the portal plane is the same as the normal of the dividing
            plane of the pBspNode_
            pPortal->m_iLeftNode = pBspNode_->m_pLeftNode->m_iTag;
            pPortal->m_iRightNode = pBspNode_->m_pRightNode->m_iTag;
         }
         else
         {
            The normal of the portal plane is the opposite against the normal of the
            dividing plane of the pBspNode_
            pPortal->m_iLeftNode = pBspNode_->m_pRightNode->m_iTag;
            pPortal->m_iRightNode = pBspNode_->m_pLeftNode->m_iTag;
         }
 
         Now the left thing is to push this superplane down to the subtree:
         GeneratePortal(pBspNode_->m_pLeftNode,pNewSuperPlane);
         GeneratePortal(pBspNode_->m_pRightNode,pNewSuperPlane);
      }
   }
}




Tolerance Control
Contents
  Introduction
  A Very Simple Example
  Tolerance Control

  Printable version
  Discuss this article