Portals Tutorial
By Alan Baylis 30/01/2002
After constructing the BSP tree we then come to the task of removing areas of
the world that cannot be seen. The most common method of doing this is to construct
portals between the leaves of the BSP tree and check whether they are in view,
if they are we can say that the leaf behind the portal is in view and add it to
the potentially visible set (PVS) of leaves. There are easier ways of calculating
which leaves are in the view frustum but they aren't as accurate as using portals,
for example we could construct bounding boxes around each of the leaves and see
which boxes are within the view frustum, this would remove a lot of the non-visible
leaves, but if we have a case where there is a hallway with a lot of rooms leading
from it and we are looking directly down the hallway then all the rooms would
be included in the PVS even though most of them are not visible because of the
hallway.
I have yet to implement the actual calculation of the PVS using the portals but
this was such a major step that I thought it should be covered separately. The
process is based on an
article by Nathan
Whitaker called 'Extracting connectivity information from a BSP tree' which goes
through the steps of creating the portals, I found it very helpful and recommend
that you read it before continuing to read this tutorial. My source code relies
heavily on a linked list for handling the creation and destruction of the portals
rather that handling lists of portal ids as Nathan suggests. A few alterations
to the nodes were needed, in order to handle the nodes of the BSP tree in a list
I have wrapped them in a new class called a ListNode and I have added a list of
portals to each node.
Download the Demo with Source
Stage One
Stage one involves creating the large portals that lie on the partitioning planes.
This was done by creating a bounding box that encompassed the data set rather
than a bounding sphere and then using planar mapping with the dimensions of this
box to create the large portals. The code to create the bounding box is as follows,
it loops through each polygon in the data set and adjusts the minimum and maximum
variables.
// Global bounding box variables
GLfloat Min_X, Min_Y, Min_Z, Max_X, Max_Y, Max_Z;
// Find the bounding box of the data set
Min_X = polygon[0].Vertex[0].x;
Min_Y = polygon[0].Vertex[0].y;
Min_Z = polygon[0].Vertex[0].z;
Max_X = polygon[0].Vertex[0].x;
Max_Y = polygon[0].Vertex[0].y;
Max_Z = polygon[0].Vertex[0].z;
for (int loop = 0; loop < numPolygons; loop++)
{
for (int i = 0; i < 3; i++)
{
if (polygon[loop].Vertex[i].x < Min_X )
Min_X = polygon[loop].Vertex[i].x;
if (polygon[loop].Vertex[i].y < Min_Y )
Min_Y = polygon[loop].Vertex[i].y;
if (polygon[loop].Vertex[i].z < Min_Z )
Min_Z = polygon[loop].Vertex[i].z;
if (polygon[loop].Vertex[i].x > Max_X )
Max_X = polygon[loop].Vertex[i].x;
if (polygon[loop].Vertex[i].y > Max_Y )
Max_Y = polygon[loop].Vertex[i].y;
if (polygon[loop].Vertex[i].z > Max_Z )
Max_Z = polygon[loop].Vertex[i].z;
}
}
The next step is to take these values and create the large portals using planar
mapping, The function to do this is below. This is called for each partitioning
plane in the BSP tree and creates the vertices of the portal passed in as a pointer.
GLvoid CreateLargePortal(POLYGON splittingPolygon, PORTAL* largePortal)
{
// Make large portal using planar mapping
largePortal->numVertices = 4;
largePortal->Vertex = new VERTEX[4];
// find the primary axis plane
int flag = 0;
VECTOR poly_normal = splittingPolygon.GetNormal();
poly_normal.Normalize();
if (fabs(poly_normal.x) > fabs(poly_normal.y) && fabs(poly_normal.x)
> fabs(poly_normal.z))
{
flag = 1;
largePortal->Vertex[0].y = Min_Y;
largePortal->Vertex[0].z = Max_Z;
largePortal->Vertex[1].y = Min_Y;
largePortal->Vertex[1].z = Min_Z;
largePortal->Vertex[2].y = Max_Y;
largePortal->Vertex[2].z = Min_Z;
largePortal->Vertex[3].y = Max_Y;
largePortal->Vertex[3].z = Max_Z;
}
else if (fabs(poly_normal.y) > fabs(poly_normal.x) && fabs(poly_normal.y)
> fabs(poly_normal.z))
{
flag = 2;
largePortal->Vertex[0].x = Min_X;
largePortal->Vertex[0].z = Max_Z;
largePortal->Vertex[1].x = Max_X;
largePortal->Vertex[1].z = Max_Z;
largePortal->Vertex[2].x = Max_X;
largePortal->Vertex[2].z = Min_Z;
largePortal->Vertex[3].x = Min_X;
largePortal->Vertex[3].z = Min_Z;
}
else
{
flag = 3;
largePortal->Vertex[0].x = Min_X;
largePortal->Vertex[0].y = Min_Y;
largePortal->Vertex[1].x = Max_X;
largePortal->Vertex[1].y = Min_Y;
largePortal->Vertex[2].x = Max_X;
largePortal->Vertex[2].y = Max_Y;
largePortal->Vertex[3].x = Min_X;
largePortal->Vertex[3].y = Max_Y;
}
GLfloat X, Y, Z;
GLfloat Distance = - (poly_normal.x * splittingPolygon.Vertex[0].x +
poly_normal.y * splittingPolygon.Vertex[0].y +
poly_normal.z * splittingPolygon.Vertex[0].z);
switch (flag)
{
case 1: //YZ Plane
X = - ( poly_normal.y * Min_Y + poly_normal.z * Max_Z + Distance )
/ poly_normal.x;
largePortal->Vertex[0].x = X;
X = - ( poly_normal.y * Min_Y + poly_normal.z * Min_Z + Distance )
/ poly_normal.x;
largePortal->Vertex[1].x = X;
X = - ( poly_normal.y * Max_Y + poly_normal.z * Min_Z + Distance )
/ poly_normal.x;
largePortal->Vertex[2].x = X;
X = - ( poly_normal.y * Max_Y + poly_normal.z * Max_Z + Distance )
/ poly_normal.x;
largePortal->Vertex[3].x = X;
break;
case 2: //XZ Plane
Y = - ( poly_normal.x * Min_X + poly_normal.z * Max_Z + Distance )
/ poly_normal.y;
largePortal->Vertex[0].y = Y;
Y = - ( poly_normal.x * Max_X + poly_normal.z * Max_Z + Distance )
/ poly_normal.y;
largePortal->Vertex[1].y = Y;
Y = - ( poly_normal.x * Max_X + poly_normal.z * Min_Z + Distance )
/ poly_normal.y;
largePortal->Vertex[2].y = Y;
Y = - ( poly_normal.x * Min_X + poly_normal.z * Min_Z + Distance )
/ poly_normal.y;
largePortal->Vertex[3].y = Y;
break;
case 3: //XY Plane
Z = - ( poly_normal.x * Min_X + poly_normal.y * Min_Y + Distance )
/ poly_normal.z;
largePortal->Vertex[0].z = Z;
Z = - ( poly_normal.x * Max_X + poly_normal.y * Min_Y + Distance )
/ poly_normal.z;
largePortal->Vertex[1].z = Z;
Z = - ( poly_normal.x * Max_X + poly_normal.y * Max_Y + Distance )
/ poly_normal.z;
largePortal->Vertex[2].z = Z;
Z = - ( poly_normal.x * Min_X + poly_normal.y * Max_Y + Distance )
/ poly_normal.z;
largePortal->Vertex[3].z = Z;
break;
}
largePortal->SetNormal();
}
The screenshot above shows an example of a test partition polygon (in blue) and the
large portal created on the polygons plane (in yellow) as well as the bounding
box of the data set. Next we need to split the large portals by all the partitioning
planes. The following function is used to either classify or split the portal
passed in. This is called for every portal in the portal list and updates the
list based on the result.
int SplitPortal(PORTAL* portalToSplit, POLYGON planePolygon, PORTAL* front, PORTAL* back)
{
const MaxVerts = 100;
int numVerts = portalToSplit->numVertices;
int count = 0, out_c = 0, in_c = 0, sideA, sideB, loop;
VECTOR planeNormal, polysNormal, pointOnPlane, edge1, edge2, temp;
VERTEX ptA, ptB, intersection, outpts[MaxVerts], inpts[MaxVerts];
// get a point on the plane
pointOnPlane.x = planePolygon.Vertex[0].x;
pointOnPlane.y = planePolygon.Vertex[0].y;
pointOnPlane.z = planePolygon.Vertex[0].z;
// get the splitting planes normal
edge1.x = planePolygon.Vertex[1].x - planePolygon.Vertex[0].x;
edge1.y = planePolygon.Vertex[1].y - planePolygon.Vertex[0].y;
edge1.z = planePolygon.Vertex[1].z - planePolygon.Vertex[0].z;
edge2.x = planePolygon.Vertex[2].x - planePolygon.Vertex[0].x;
edge2.y = planePolygon.Vertex[2].y - planePolygon.Vertex[0].y;
edge2.z = planePolygon.Vertex[2].z - planePolygon.Vertex[0].z;
planeNormal = CrossVector(edge1, edge2);
// get the normal of the portal to split
edge1.x = portalToSplit->Vertex[1].x - portalToSplit->Vertex[0].x;
edge1.y = portalToSplit->Vertex[1].y - portalToSplit->Vertex[0].y;
edge1.z = portalToSplit->Vertex[1].z - portalToSplit->Vertex[0].z;
edge2.x = portalToSplit->Vertex[2].x - portalToSplit->Vertex[0].x;
edge2.y = portalToSplit->Vertex[2].y - portalToSplit->Vertex[0].y;
edge2.z = portalToSplit->Vertex[2].z - portalToSplit->Vertex[0].z;
polysNormal = CrossVector(edge1, edge2);
// check if the portal lies on the plane
for (int loop = 0; loop < numVerts; loop++)
{
temp.x = portalToSplit->Vertex[loop].x;
temp.y = portalToSplit->Vertex[loop].y;
temp.z = portalToSplit->Vertex[loop].z;
if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
count++;
else
break;
}
if (count == numVerts)
{
if (ClassifyPoint(polysNormal, pointOnPlane, planeNormal) == 1)
return Front;
if (ClassifyPoint(polysNormal, pointOnPlane, planeNormal) == -1)
return Back;
}
// find if all of the points are infront of or behind the plane
int frontcount = 0, backcount = 0;
for (int loop = 0; loop < numVerts; loop++)
{
temp.x = portalToSplit->Vertex[loop].x;
temp.y = portalToSplit->Vertex[loop].y;
temp.z = portalToSplit->Vertex[loop].z;
if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
{
frontcount++;
backcount++;
}
else if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 1)
frontcount++;
else if (ClassifyPoint(temp, pointOnPlane, planeNormal) == -1)
backcount++;
}
if (frontcount == numVerts)
return Front;
if (backcount == numVerts)
return Back;
// try to split the portal
ptA = portalToSplit->Vertex[numVerts - 1];
temp.x = ptA.x;
temp.y = ptA.y;
temp.z = ptA.z;
sideA = ClassifyPoint(temp, pointOnPlane, planeNormal);
for (int i = -1; ++i < numVerts;)
{
ptB = portalToSplit->Vertex[i];
temp.x = ptB.x;
temp.y = ptB.y;
temp.z = ptB.z;
sideB = ClassifyPoint(temp, pointOnPlane, planeNormal);
if (sideB > 0)
{
if (sideA < 0)
{
// find intersection
edge1.x = ptA.x;
edge1.y = ptA.y;
edge1.z = ptA.z;
edge2.x = ptB.x;
edge2.y = ptB.y;
edge2.z = ptB.z;
temp = GetEdgeIntersection(edge1, edge2, planePolygon);
intersection.x = temp.x;
intersection.y = temp.y;
intersection.z = temp.z;
outpts[out_c++] = inpts[in_c++] = intersection;
}
inpts[in_c++] = ptB;
}
else if (sideB < 0)
{
if (sideA > 0)
{
// find intersection
edge1.x = ptA.x;
edge1.y = ptA.y;
edge1.z = ptA.z;
edge2.x = ptB.x;
edge2.y = ptB.y;
edge2.z = ptB.z;
temp = GetEdgeIntersection(edge1, edge2, planePolygon);
intersection.x = temp.x;
intersection.y = temp.y;
intersection.z = temp.z;
outpts[out_c++] = inpts[in_c++] = intersection;
}
outpts[out_c++] = ptB;
}
else
outpts[out_c++] = inpts[in_c++] = ptB;
ptA = ptB;
sideA = sideB;
}
if (out_c == 0 || in_c == 0)
{
int side;
for (int loop = 0; loop < numVerts; loop++)
{
temp.x = portalToSplit->Vertex[loop].x;
temp.y = portalToSplit->Vertex[loop].y;
temp.z = portalToSplit->Vertex[loop].z;
side = ClassifyPoint(temp, pointOnPlane, planeNormal);
if (side == 1)
return Front;
else if (side == -1)
return Back;
}
}
else
{
front->Vertex = new VERTEX[in_c];
back->Vertex = new VERTEX[out_c];
front->numVertices = in_c;
back->numVertices = out_c;
for (loop = 0; loop < in_c; loop++)
front->Vertex[loop] = inpts[loop];
for (loop = 0; loop < out_c; loop++)
back->Vertex[loop] = outpts[loop];
return PortalWasSplit;
}
return NULL;
}
The following function uses the above code to create the large portal for each
partitioning plane and splits them by every other partitioning plane (the PartitionList
it refers to was created using a function called MakeNodeLists() which is in bsp.cpp)
leaving us with a large list of potential portals each with a unique id.
GLvoid MakePortalList()
{
// Create the large portals
for (int loop = 1; loop <= numpartitions; loop++)
{
listnode = PartitionList.Get(loop);
portal = new PORTAL;
portal->linkPosition = loop;
portal->PartitionNodeId = loop;
CreateLargePortal(listnode->node->partition, portal);
PortalList.Insert(portal);
}
// Split the large portals into potential portals
numportals = numpartitions;
int result, portalToSplit;
PORTAL* frontportal;
PORTAL* backportal;
for (int partition = 1; partition <= numpartitions; partition++)
{
listnode = PartitionList.Get(partition);
portalToSplit = numportals;
while (portalToSplit > 0)
{
frontportal = new PORTAL;
backportal = new PORTAL;
portal = PortalList.Get(portalToSplit);
result = SplitPortal(portal, listnode->node->partition,
frontportal, backportal);
if (result == PortalWasSplit)
{
frontportal->linkPosition = ++numportals;
frontportal->PartitionNodeId = portal->PartitionNodeId;
PortalList.Insert(frontportal);
backportal->linkPosition = ++numportals;
backportal->PartitionNodeId = portal->PartitionNodeId;
PortalList.Insert(backportal);
delete[] portal->Vertex;
PortalList.Delete(portalToSplit);
numportals--;
}
else
{
delete frontportal;
delete backportal;
}
portalToSplit--;
}
}
// Loop through the portals and assign a unique id
for (int loop = 1; loop <= numportals; loop++)
{
portal = PortalList.Get(loop);
portal->PortalId = loop;
}
}
Stage Two
The next stage involves running each of the portals through the BSP tree and adding
them to the leaves they come to. The functions used to do this are below, the
first function calls the recursive function AddPortal() for each portal in the
PortalList, if a portal is found to be on a partition then a copy is made and
passed down both sides of the tree, once all of the portals have been added to
the leaves we no longer use the portal list and work directly with the portal
lists in the leaf nodes. The source file portal.cpp contains the CopyPortal()
and ClassifyPortal() functions.
GLvoid AddPortalsToLeaves(BSP_node* root)
{
for (int loop = 1; loop <= numportals; loop++)
{
PORTAL* tempportal = CopyPortal(PortalList.Get(loop));
AddPortal(tempportal, root);
}
}
GLvoid AddPortal(PORTAL* thisportal, BSP_node* node)
{
if (node->leaf == true)
{
node->numportals++;
thisportal->linkPosition = node->numportals;
node->portallist.Insert(thisportal);
return;
}
int side = ClassifyPortal(thisportal, node->partition);
if (side == Front)
{
AddPortal(thisportal, node->frontnode);
}
if (side == Back)
{
AddPortal(thisportal, node->backnode);
}
if (side == OnPartition)
{
AddPortal(thisportal, node->frontnode);
PORTAL* tempportal = CopyPortal(thisportal);
AddPortal(tempportal, node->backnode);
}
return;
}
Stage Three
The final stage requires that we remove the excess portals. Nathan mentions that
we can walk the BSP tree and check for portals that exist in only one leaf and
remove them as they cannot be a true portal. This is achieved through the following
functions, FindTruePortals() recursively walks the BSP tree checking for single
portals, if one is found then it is removed from the nodes portal list, if it
is in two leaf nodes then it is clipped by the polygons of its front and back
nodes. After this I call a function called InvertPortals() which reorders the
vertices of the portal so that it faces into the node it is in, it also sets up
the portal's front and back leaf pointers. After the clipping stage there remained
some extra portals that existed in more than one leaf but weren't true portals,
they were coplanar with the walls that lay on the partitioning planes. To fix
this I go through each portal in a leaf node, reverse them temporarily and classify
them with only the polygons of its back node, if they are found to be in front
of all the polygons then keep them, otherwise delete them. If we don't reverse
the portal then some of the true portals will also be deleted.
GLvoid FindTruePortals(BSP_node* node)
{
int flag;
if (node->leaf == true)
{
for (int portalnumber = node->numportals; portalnumber > 0; portalnumber--)
{
flag = 0;
PORTAL* tempportal = node->portallist.Get(portalnumber);
CheckForSinglePortals(root, node, tempportal, &flag);
if (flag == 0)
{
delete[] tempportal->Vertex;
node->portallist.Delete(portalnumber);
node->numportals--;
}
else
{
ClipPortalToFrontLeaf(tempportal);
ClipPortalToBackLeaf(tempportal);
}
}
InvertPortals(node);// also inverts the front and back leaf pointers if necessary
for (int portalnumber = node->numportals; portalnumber > 0; portalnumber--)
{
PORTAL* tempportal = node->portallist.Get(portalnumber);
flag = RemoveExtraPortals(tempportal);
if (flag == true)
{
delete[] tempportal->Vertex;
node->portallist.Delete(portalnumber);
node->numportals--;
}
}
return;
}
else
{
FindTruePortals(node->frontnode);
FindTruePortals(node->backnode);
return;
}
}
GLvoid CheckForSinglePortals(BSP_node* node, BSP_node* originalnode,
PORTAL* portal, int* flag)
{
PORTAL* tempportal;
if (node->leaf == true)
{
if (node->nodeid != originalnode->nodeid)
{
for (int portalnum = node->numportals; portalnum > 0; portalnum--)
{
tempportal = node->portallist.Get(portalnum);
if (tempportal->PortalId == portal->PortalId)
{
portal->frontleaf = originalnode;
portal->backleaf = node;
*flag += 1;
}
}
}
return;
}
else
{
CheckForSinglePortals(node->frontnode, originalnode, portal, flag);
CheckForSinglePortals(node->backnode, originalnode, portal, flag);
return;
}
}
int RemoveExtraPortals(PORTAL* portal)
{
int result, count = 0;
POLYGON temppoly;
BSP_node* tempnode = portal->backleaf;
for (int loop = 0; loop < tempnode->numpolys; loop++)
{
temppoly = tempnode->nodepolylist[loop];
result = ClassifyInvertedPortal(portal, temppoly);
if (result == Front)
count++;
}
if (count != portal->backleaf->numpolys)
return true;
else
return false;
}
int ClipPortalToFrontLeaf(PORTAL* portal)
{
int result, returnvalue = 0;
for (int polygon = 0; polygon < portal->frontleaf->numpolys; polygon++)
{
PORTAL* front = new PORTAL;
PORTAL* back = new PORTAL;
result = SplitPortal(portal, portal->frontleaf->nodepolylist[polygon],
front, back);
if (result == PortalWasSplit)
{
returnvalue = PortalWasSplit;
delete[] back->Vertex;
delete back;
delete[] portal->Vertex;
portal->numVertices = front->numVertices;
portal->Vertex = front->Vertex;
delete front;
}
else
{
delete back;
delete front;
}
}
return returnvalue;
}
int ClipPortalToBackLeaf(PORTAL* portal)
{
int result, returnvalue = 0;
for (int polygon = 0; polygon < portal->backleaf->numpolys; polygon++)
{
PORTAL* front = new PORTAL;
PORTAL* back = new PORTAL;
result = SplitPortal(portal, portal->backleaf->nodepolylist[polygon],
front, back);
if (result == PortalWasSplit)
{
returnvalue = PortalWasSplit;
delete[] back->Vertex;
delete back;
delete[] portal->Vertex;
portal->numVertices = front->numVertices;
portal->Vertex = front->Vertex;
delete front;
}
else
{
delete back;
delete front;
}
}
return returnvalue;
}
There may be errors in there somewhere and it certainly hasn't been optimized
(it's all done before runtime so that isn't too much of an issue.) I hope this
helps when creating portals, if you have any problems or error reports then send
me an email, however, I don't check it often so be patient for a reply.
References:
Nathan Whitaker
