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
48 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:

Introduction

Recently my friend and I have been working on our first 3D game engine. After evaluating several methods, we decided to implement portal-based scene graph management. There are many articles talking about portal-based rendering, but I've rarely see one that mentions how to generate portals automatically in a map editor. The exception is one article called "Binary Space Partioning Trees and Polygon Removal in Real Time 3D Rendering" by Samuel Ranta-Eskola at www.gamedev.net. However when my friend tried to implement the algorithm in the article for our map editor, we found fatal errors in the algorithm, such as unreasonable recursive calls. So we had to design a new algorithm by ourselves. At first we thought it would be very difficult, but after a week's effort, we finally made it, though the algorithm is not perfect. In some cases it will generate a few redundant portals, but it is easy to eliminate those by hand.

If you are trying to implement a portal-based engine,and you do not want to generate the portals by hand (and who would?) keep on reading.

Problem consideration

We export triangle data from 3dsmax to our engine's map editor, so we do not need to develop a CSG map editor like Quake. The task of our map editor is to first generate a BSP tree from the triangle soup we've exported from 3dsmax and then generate portals for each leaf in the BSP tree. There are several points you need to notice in our algorithm:

1. Portals only exist on the plane of the BSP node. This is obvious but very important, because without this assumption, we could not set up this algorithm. We generate a large enough rectangle (exceeding the boundary of the bounding box of the environment) at each non-leaf node, and clip it against other planes (plane of the node and triangles in the leaf) when we traverse down the tree. So finally we have a lot of polygons and portals, and the remaining process is to identify which are real portal and which are not. Actually, we analyse the validity of each portal each time we clip the portal. The rules are as follows (each portal has an attribute bCulled with an initial value of TRUE):

  1. If a portal is spanning the dividing plane at a node (not a leaf), we clip the portal into 2 portals and set their bCulled flag to be the same as the original one.
  2. If a portal is divided by a triangle in the leaf, we set the bCulled attribute of the portal on the positive side of the triangle's plane to FALSE, and the negative one to TRUE.
  3. Finally, after dividing against all triangles, portals with their bCulled attribute set to FALSE are the ones we really want. We can do this because the direction the triangle is facing tells us whether the space is solid or non-solid, and we don't want those portals in solid space.

2. We do not require that the triangles in a leaf form a convex region, which means the portals between regions (a region is a leaf in the bsp tree) can form a concave polygon - which is not suitable for portal rendering. So our algorithm will make sure that all portals generated form a convex polygon, which means that if a portal turns out to be concave, we will generate several convex ones from it. This may appear inefficient, but it comes up infrequently enough that it doesn't present a problem.

3. In order to generate correct portals, we need to assure that the triangle soup forms a closed space and that there is no self intersection (otherwise it will cause some redundant portals). The artists on our team found that making sure the space is closed is relatively easy, but eliminating self intersection isn't. So, we decided to not force artists to meet these requirements in their modelling. Instead, we use some rules to eliminate some obvious redundant portals automatically once the generation process is done. If unreasonable portals remain, it's easy to eliminate them by hand. Fortunately, while implementing the collision detection system, we invented an algorithm that indentifies situations where self-intersetion occurs, so if you use this algorithm to scan the triangle soup and do some subdivision you can eliminate these situations! I will cover this algorithm in a future article.

What's more, we will also generate several convex polygons which can be replaced by one convex polygon during the process, so at later stage we'll also add a process of portal merging.

4.Floating point precision is a problem that you have to handle carefully in the algorithm. At first we generated many obvious redundant portals due to floating point precision errors, but we were able to solve this problem by carefully controlling the tolerance in various situations.

Primary data structures

class CPortal
{
public:
   //If the portal's polygon seems like a line segament,it is not reasonable
   //this is some kind of tolerance control.
   BOOL      Reasonable();

   Cpolygon  m_Polygon;            
   BOOL      m_bCulled;                
   int       m_iLeftNode;            
   int       m_iRightNode;          
}


class CSurperPlane
{
public:
   void Remove(CPortal *pPortal);
   void Add(CPortal *pPortal);
 
   TList<CPortal*>    m_LisOfPortals;
}
 

class CBspNode
{
public:
   int                  m_iTag; //if m_iTag>=0 it is a node else it is a leaf
   CPlane               m_DividingPlane;
   CBspNode            *m_pParent;
   CBspNode            *m_pLeftNode;
   CBspNode            *m_pRightNode;
   Tlist<CTriangle>     m_ListOfTriangle;
}


class CBspTree
{
public:
   //This is the main algorithm function
   void GeneratePortal(CBspTreeNode *pBspNode_, CSuperPlane *pSuperPlane_);
 
   //Test if the triangle is intersecting with the polygon,
   //this function needs careful tolerance control
   BOOL TriangleIntersectPolygon(CTriangle& Tri_,CPolygon& Polygon_);
 
   //Check the relationship between the plane and the polygon
   //polygon on positive side of the plane
   //       on negative side
   //            spanning
   //            coincide
   //this function needs a little tolerance control
   int CalculateSide(CPlane plane_,CPolygon *pPolygon_);

   
   //use the plane to clip the portal and put the output the data into leftportal
   //and rightportal, left means on the positive side of the plane and right means
   //on the negative side
   void ClipPortal(CPlane plane_, CPortoal *pPortal_, 
   CPortoal& PortalLeft_, CPortoal& PortalRight_);

   CBspNode               *m_pRoot;
   TList<CSuperPlane*>     m_ListOfSuperPlanes;
}

Algorithm pseudocode

Because the algorithm is a bit long, I will give you a simple version first. Note that you must generate a bsp tree before using this algorithm.

void CBspTree::GeneratePortal(CBspTreeNode *pBspNode_, CSuperPlane *pSuperPlane_)
{
   if (pBspNode_->IsLeaf ())
   {
      Use each triangle in pBspNode_ to clip against each portal in pSuperPlane_;
      Update validation information of each portal;
      Delete those culled portals which connects pBspNode_ in pSuperPlane_;
   }
   else
   {
      if (pSuperPlane_)
      {
         Use dividing plane at pBspNode_ to clip against each portal in pSuperPlane_;
         Update connection information of each portal;
         GeneratePortal(pBspNode_->m_pLeftNode,pSuperPlane_);
         GeneratePortal(pBspNode_->m_pRightNode,pSuperPlane_);
      }

      if (we have not generated a Super plane at pBspNode_)
      {
         Create pNewSuperPlane on the dividing plane of pBspNode_ 
         Generate a large portal on pNewSuperPlane;
         Clip portal on pNewSuperPlane to make sure it is within the space of pBspNode_
         GeneratePortal(pBspNode_->m_pLeftNode,pNewSuperPlane);
         GeneratePortal(pBspNode_->m_pRightNode,pNewSuperPlane);
      }
   }
}




A Very Simple Example
Contents
  Introduction
  A Very Simple Example
  Tolerance Control

  Printable version
  Discuss this article