PVS Tutorial
By Alan Baylis 14/02/2002
Download the Demo with Source
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);
}
}
Before calling the main function, the view frustum planes must be found. I used a function called ExtractFrustum() which is a slightly modified version of a function by
Mark Morely. The function updates a global array of six planes and can be found in general.cpp of the source code.
The following functions follow the method I described, except in one area, the clipped portal passed to the recursive function is not a true portal, it just contains the vertex data so I also pass the current node and portal number (along with the id of the current node) and use this information to find the true portal within the recursive function.
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;
}
The positive aspect to this method is that the least number of leaves are marked as being potentially visible rather than all leaves that could be seen from anywhere in the current leaf. The only drawback is that it takes more processing time to find the PVS compared to a pre-calculated set. Whether it outweighs the pre-calculated method, by not processing unseen geometry, is still unknown, but I feel it would.
Another feature that could be easily added would be to clip the actual geometry with the clip planes during the process, creating a zero overdraw method, but I wont add this feature for now.
I know the code is... how you say... inelegant, the memory management could be handled a lot better (I still prefer this compared to maximum sized arrays) and it is
not optimized, but it will do for now as a proof that the method works and I'll work on cleaning it up later. If you have any questions or error reports then send me an email.
References:
Mark Morely
Copyright © 1998 - 2010 Alan Baylis, All Rights Reserved
