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.
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.
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:
All trademarks and registered trademarks are the property of their respective owners.
design by: Gippsland Web Design