Portals begin life as a big fat planar quad, we already know this, we just don't know how to go about making them yet.
However, I am going to provide the sourcecode for the solution here and now. If you have questions, ask them.
And we don't know how to represent the geometry, since although they START as a quad, we're going to Shatter, Clip and Cull them so there will likely be all kinds of complex shapes involved - we're going to have to define our portal geometry better than we had to for the renderable triangles we dealt with earlier... we'll have to perform actual geometric clipping (splitting) operations, which generate entirely new vertices at the intersections of polygon edges and splitting planes. We will do this without meddling with our vertex buffer.
Of course, since we never actually want to DRAW the portal geometries (or do we?) things like Winding Order won't matter to us.
So let's begin by defining a Portal as a collection of special 'invisible' Polygons which all share the same plane.
And let's define a Polygon as being a circular list of coplanar points.
We won't place any further restrictions on our portal geometry other than that they meet those basic requirements.
So we'll need a Portal class, and a Polygon class:
#pragma once
using namespace std;
#include "dxBSPNode.h"
//#include "dxBSPLeafNode.h"
#include "dxBSPTree.h"
class dxBSPLeafNode;
class dxPolygon
{
public:
dxPolygon() {};
~dxPolygon(){};
vector m_Points;
};
class dxPortal
{
public:
dxPortal():m_pFrontLeaf(0), m_pBackLeaf(0) {};
~dxPortal()
{
// clean polygons
while(!m_Polygons.empty())
{
dxPolygon* p = m_Polygons.back();
delete p;
m_Polygons.pop_back();
}
};
bool Delete_Polygon(dxPolygon* pPolygon);
D3DXVECTOR4* GetPlane() { return &m_Plane;}
void SetPlane(D3DXVECTOR4& plane) { m_Plane = plane; }
PointPlaneResult Split(dxPolygon* SplitMe, D3DXVECTOR4* pPlane);
// A portal has some unique Geometry:
vector m_Polygons;
private:
float IntersectLinePlane(D3DXVECTOR3* pPoint1, D3DXVECTOR3* pPoint2, D3DXVECTOR4* pPlane);
// A portal connects two subspaces:
dxBSPLeafNode* m_pFrontLeaf;
dxBSPLeafNode* m_pBackLeaf;
D3DXVECTOR4 m_Plane;
};
and the code for that is here:
#include "stdafx.h"
#include "dxBSPNode.h"
#include "dxBSPTree.h"
#include "dxPortal.h"
// This method will attempt to partition a portal's geometry with a splitting plane from a non-leaf bsp tree node.
// It is a known property of all convex polygons that bisecting them produces two convex childs.
// Since a portal begins life as a convex polygon, bisection will always result in convex polygons.
// Inputs:
// dxPolygon* SplitMe = polygon (member of this portal) being considered for splitting
// D3DXVECTOR4* pPlane = Splitting Plane
// Outputs:
// FRONT / BACK = The polygon could not be Split
// COPLANAR = The polygon was duplicated
PointPlaneResult dxPortal::Split(dxPolygon* SplitMe, D3DXVECTOR4* pPlane)//, PORTAL* front, PORTAL* back)
{
int numVerts = SplitMe->m_Points.size();
int count = 0, out_c = 0, in_c = 0;
PointPlaneResult sideA, sideB, side;
D3DXVECTOR3 polysNormal, edge1, edge2, temp;
//VERTEX ptA, ptB, intersection, outpts[MaxVerts], inpts[MaxVerts];
D3DXVECTOR3 intersection;
////////////////////////////////////////////////////////////////////////////////
// Check whether the plane actually cuts through the portal geometry
////////////////////////////////////////////////////////////////////////////////
// Set up some quicky Vec3 pointers for dx api calls
D3DXVECTOR3* pSplitPlaneNormal = (D3DXVECTOR3*) pPlane;
D3DXVECTOR3* pThisPortalNormal = (D3DXVECTOR3*) &m_Plane;
// If the Splitting Plane and the Portal are (damn close to) coplanar, we can't split the portal geometry.
if(abs(D3DXVec3Dot(pSplitPlaneNormal,pThisPortalNormal )) > (1.0f - 2*PLANAR_HALF_EPSILON))
{
return COPLANAR;
}
// 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++)
{
D3DXVECTOR3* pPoint = &SplitMe->m_Points[loop];
if (dxBSPNode::ClassifyPointPlane(pPoint, pPlane) == 0)
{
frontcount++;
backcount++;
}
else if (dxBSPNode::ClassifyPointPlane(pPoint, pPlane) == 1)
frontcount++;
else if (dxBSPNode::ClassifyPointPlane(pPoint, pPlane) == -1)
backcount++;
}
if (frontcount == numVerts)
return FRONT;
if (backcount == numVerts)
return BACK;
////////////////////////////////////////////////////////////////////////////////
// try to split the input polygon
////////////////////////////////////////////////////////////////////////////////
dxPolygon* frontside = new dxPolygon();
dxPolygon* backside = new dxPolygon();
D3DXVECTOR3* pPtA;
D3DXVECTOR3* pPtB;
// Let PointA = the last point in the polygon
// Let sideA = the side that contains PointA
pPtA = &SplitMe->m_Points[numVerts - 1];
sideA = dxBSPNode::ClassifyPointPlane(pPtA, pPlane);
// For each Point on the Polygon (except the last one)
for (int i = 0; i < numVerts-1; i++)
{
// Let PointB = the Current point in the polygon
// Let sideB = the side that contains PointB
pPtB = &SplitMe->m_Points;
sideB = dxBSPNode::ClassifyPointPlane(pPtB, pPlane);
// If they are on different sides, find the intersection
if (sideB == FRONT)
{
if (sideA == BACK)
{
// find intersection
float uIntersect = IntersectLinePlane(pPtA,pPtB,pPlane);
intersection = ((*pPtA-*pPtB) * uIntersect)+(*pPtB);
frontside->m_Points[out_c++] = backside->m_Points[in_c++] = intersection;
}
frontside->m_Points[in_c++] = SplitMe->m_Points;
}
else if (sideB == BACK )
{
if (sideA == FRONT )
{
// find intersection
float uIntersect = IntersectLinePlane(pPtA,pPtB,pPlane);
frontside->m_Points[out_c++] = backside->m_Points[in_c++] = intersection;
}
backside->m_Points[out_c++] = SplitMe->m_Points;
}
else
{
frontside->m_Points[out_c++] = backside->m_Points[in_c++] = SplitMe->m_Points;
}
// Let sideA (Current Point) = the Previous Point
pPtA = pPtB;
sideA = sideB;
}
if (out_c == 0 || in_c == 0)
{
// I'm not sure how this case can happen, but anyway
for (int loop = 0; loop < numVerts; loop++)
{
side = dxBSPNode::ClassifyPointPlane(&SplitMe->m_Points[loop], pPlane);
if(side!=COPLANAR)
{
delete frontside;
delete backside;
return side;
}
}
}
else
{
// Add the two polygons resulting from the splitting operation
m_Polygons.push_back(frontside);
m_Polygons.push_back(backside);
// return special result: "POLYGON WAS SPLIT"
return (PointPlaneResult) -1;
}
MessageBoxA(0,"Something weird happened, we discovered a Coplanar result after the fact",0,0);
exit(1);
}
// This method attempts to find the intersection of a Line Segment and a Plane.
// Return value is interpolation factor, or 'normalized distance to plane' (0 to 1 if there is intersection).
// Formula courtesy of Paul Bourke, Canberra
// numerator = A x1 + B y1 + C z1 + D
// denominator= A (x1-x2) + B(y1-y2) + C(z1-z2)
float dxPortal::IntersectLinePlane(D3DXVECTOR3* pPoint1, D3DXVECTOR3* pPoint2,D3DXVECTOR4* pPlane)
{
D3DXVECTOR3* pPlaneNormal = (D3DXVECTOR3*) pPlane;
float numerator = D3DXVec3Dot(pPoint1,(D3DXVECTOR3*) pPlaneNormal) + pPlane->w;
float denominator = pPlane->x*(pPoint1->x-pPoint2->x)+pPlane->y*(pPoint1->y-pPoint2->y)+pPlane->z*(pPoint1->z-pPoint2->z);
// Ifthe denominator is 0 then the normal to the plane is perpendicular to the line.
// Thus the line is either parallel to the plane and there are no solutions or the line is on the plane in which case are infinite solutions.
if(denominator!=0) return numerator / denominator;
// Return value is meant to be a scalar, ie, always positive.
// Any negative value would indicate failure 
return -1.0f;
// if it is necessary to determine the intersection of the line segment between P1 and P2 then just check that u is between 0 and 1.
}
// Try to delete a Polygon from the Portal.
// Returns true/false to indicate success/failed
bool dxPortal::Delete_Polygon(dxPolygon* pPolygon)
{
for(vector::iterator i=m_Polygons.begin(); i!=m_Polygons.end(); i++)
{
if( (*i)==pPolygon)
{
m_Polygons.erase(i);
delete pPolygon;
return true;
}
}
return false;
}
And last but not least, code to make our BFQ's
// Construct a big fat Quad apon this node's splitting plane
// This is the initial shape of each Portal geometry.
// We don't take too much care about whether the winding order is right since we'll never draw it.
void dxBSPNode::CreatePortal()
{
// create a new portal object
dxPortal* pOut = new dxPortal();
// find the primary axis plane
D3DXVECTOR3 vA, vB, vC, vD;
if (fabs(m_Plane.x) > fabs(m_Plane.y) && fabs(m_Plane.x) > fabs(m_Plane.z))
{
vA.y = m_Bounds.vMin.y;
vA.z = m_Bounds.vMax.z;
vB.y = m_Bounds.vMin.y;
vB.z = m_Bounds.vMin.z;
vC.y = m_Bounds.vMax.y;
vC.z = m_Bounds.vMin.z;
vD.y = m_Bounds.vMax.y;
vD.z = m_Bounds.vMax.z;
vA.x = - ( m_Plane.y * m_Bounds.vMin.y + m_Plane.z * m_Bounds.vMax.z + m_Plane.w ) / m_Plane.x;
vB.x = - ( m_Plane.y * m_Bounds.vMin.y + m_Plane.z * m_Bounds.vMin.z + m_Plane.w ) / m_Plane.x;
vC.x = - ( m_Plane.y * m_Bounds.vMax.y + m_Plane.z * m_Bounds.vMin.z + m_Plane.w ) / m_Plane.x;
vD.x = - ( m_Plane.y * m_Bounds.vMax.y + m_Plane.z * m_Bounds.vMax.z + m_Plane.w ) / m_Plane.x;
}
else if (fabs(m_Plane.y) > fabs(m_Plane.x) && fabs(m_Plane.y) > fabs(m_Plane.z))
{
vA.x = m_Bounds.vMin.x;
vA.z = m_Bounds.vMax.z;
vB.x = m_Bounds.vMax.x;
vB.z = m_Bounds.vMax.z;
vC.x = m_Bounds.vMax.x;
vC.z = m_Bounds.vMin.z;
vD.x = m_Bounds.vMin.x;
vD.z = m_Bounds.vMin.z;
vA.y = - ( m_Plane.x * m_Bounds.vMin.x + m_Plane.z * m_Bounds.vMax.z + m_Plane.w ) / m_Plane.y;
vB.y = - ( m_Plane.x * m_Bounds.vMax.x + m_Plane.z * m_Bounds.vMax.z + m_Plane.w ) / m_Plane.y;
vC.y = - ( m_Plane.x * m_Bounds.vMax.x + m_Plane.z * m_Bounds.vMin.z + m_Plane.w ) / m_Plane.y;
vD.y = - ( m_Plane.x * m_Bounds.vMin.x + m_Plane.z * m_Bounds.vMin.z + m_Plane.w ) / m_Plane.y;
}
else
{
vA.x = m_Bounds.vMin.x;
vA.y = m_Bounds.vMin.y;
vB.x = m_Bounds.vMax.x;
vB.y = m_Bounds.vMin.y;
vC.x = m_Bounds.vMax.x;
vC.y = m_Bounds.vMax.y;
vD.x = m_Bounds.vMin.x;
vD.y = m_Bounds.vMax.y;
vA.z = - ( m_Plane.x * m_Bounds.vMin.x + m_Plane.y * m_Bounds.vMin.y + m_Plane.w ) / m_Plane.z;
vB.z = - ( m_Plane.x * m_Bounds.vMax.x + m_Plane.y * m_Bounds.vMin.y + m_Plane.w ) / m_Plane.z;
vC.z = - ( m_Plane.x * m_Bounds.vMax.x + m_Plane.y * m_Bounds.vMax.y + m_Plane.w ) / m_Plane.z;
vD.z = - ( m_Plane.x * m_Bounds.vMin.x + m_Plane.y * m_Bounds.vMax.y + m_Plane.w ) / m_Plane.z;
}
// Construct our big fat quad
dxPolygon* pPolygon = new dxPolygon();
pPolygon->m_Points.push_back(vA);
pPolygon->m_Points.push_back(vB);
pPolygon->m_Points.push_back(vC);
pPolygon->m_Points.push_back(vD);
// Add the new polygon to the portal
pOut->m_Polygons.push_back(pPolygon);
// Set Plane for the portal and its geometry
pOut->SetPlane(m_Plane);
// Add the portal to the tree container
m_pTree->m_Portals.push_back(pOut);
}
During tree construction, we created a big fat quad at each non-leaf node.
As soon as we've finished generating the BSP Tree, we are ready to Shatter our Portals.
