### About this blog

BSP and Beyond - Generating a Portal/Cell Graph from a Triangle Soup

## Entries in this blog

I went from -2 to -33 from a single post.

Well on track for my -666 !!!

In the meanwhile I've been quite busy, working on commercial projects.

I bet the people who voted me down have not even got a job in the industry !!

Vote me down more!! I need to reach my goal!

Now my current score on this crap forum is minus 2 - after they agreed minus scored would not happen.

Can i reach - 666?

Yours Truly, for saying nothing more than the truth.

I was invited to gcap - and stood around outside, hawking my wares like a whore, and it felt so right.

Thanks to all the people who stopped to play it!

Announcing the upcoming IGF student division finalists, http://studentgame.caswal.com/Jousting/index.html

Today I got my fledgling newchool opengl engine launched.

It flapped around, at no stage did it fly, but it did not fall over, and it did not disgrace itself on the way out!

It's a small blog mention @ http://www.asmcommunity.net/board/index.php?blog=751;sa=topic;id=51

Here I describe a way to breach regular hardware limits for the total number of lights, without sacrificing the minimum framerate, and while considering shadowcasting in the same step.

So on another topic, I'm currently working on a game involving medieval jousting (yes, horsies, mounted by metal-clad men..) and we've glued some kinematic rigid bodies to various joints of our warriors (shields, lances, so forth).

I was happy to set up physics under Bullet to drive the kinematic bodies around via a custom MotionState,

But when it came to finding collisions between two kinematic bodies, I was deeply depressed.

You see, Bullet does not apply physics response forces to kinematic bodies.. only dynamic ones (the third type, static, are not even worth mentioning). Since it doesn't need a response, it won't bother to generate any contacts for those collisions. So you can't use a 'OnContactSomething' callback to receive notification of a collision.. you are left with having to poll for it, or you will never know it happened. I guess that Erwin expected that there will only ever be one kinematic body and it's your guy smashing stuff out of the way? Not good enough.

So why were we using kinematic bodies in the first place, if dynamic bodies generate contacts like we wanted? Because you can't directly control dynamic bodies as such - you have to use forces to push them around, and this doesn't give you a reliable control mechanism when you just wanted to specify where something is at a particular time.

Our workaround was rather novel so I thought I would blog it here.

For each animation-driven kinematic body, glued to some bone (joint) by a MotionState, we would create a dynamic body, which shared the same CollisionShape, had the same world translation and orientation, and had the same local origin/pivot - and we would then create a constraint to glue the dynamic child to the kinematic parent.

We used a "Generic 6DOF" constraint, with "all degrees of freedom locked" to basically transfer motion from the kinematic body to the dynamic one.

This made the collision pipeline go absolutely crazy (debug build) since there was some bodies that are always 'perfectly intersecting' - the GJK separation solver runs about 1000 iterations per frame and keels over, ugh this is not good...

Then we used the most coarse level of collision filtering offered ('Collision Groups' basically) to eliminate the kinematic bodies from the collision pipeline, leaving only the dynamic ones to collide.

Now we were able to 'directly' drive dynamic bodies from outside the simulator, as well as rely on the contact callback notification of the collision event(s).

Re-enabling the culling of portal polygons during their Clipping phase paid off - I am now detecting five portal quads are being eliminated during the search for 'true portals', and their geometry matches that of the inner box faces - I have eliminated my 'fake portals' correctly.

The sixth and final leaf now contains 4 portal references, none of which lead into the interior of the inner box

I can see one remaining problem: two of my portals contain 5 polygons, where there should be 4.

Furthermore, there appears to be a pair of quads with the same geometry (actually they differ by 0.00000002).

I need to look into that.

I found a very fast way to get the results I was looking for in terms of dealing with the 'closed, unreachable space' in the test model (ie, the space inside the inner box).

I modified the ChoosePartitioningPlane function so that it will always return a plane from the input geometry, as long as there is one that has not already been used before. It will prefer to divide the geometry evenly, however if it can't find a plane that partitions the geometry, it will just return a plane that hasn't been used yet.

The results are similar to before, but important differences exist... and the results are actually NOT what I expected.

We still get six convex leaf nodes, however they are now all closed convex hulls - they are correct !!

The tree contains geometry in all leaf nodes, INCLUDING the last leaf node - there are NO empty leaf nodes representing places we can't go - the empty space is not part of our bsp tree at all !!!

We now get 10 planes examined, instead of 5.

They are marked as being Used, but in fact only the 6 planes of the inner box are used to construct the tree, and of those, only 5 represent Portals.

The BSP Tree is not made unnecessarily complex.

GREAT STUFF !!! WOOHOO !!!

Now on to the Portalizer again

We are still only getting 5 Portals - this is correct.

The extra planes are generating a lot of extra portal polygons due to more 'shattering', however I have implemented code to Weld them together later, where I detect that they were split unnecessarily.. the current result is a grand total of 14 portal polygons connecting our 6 subspaces.

There are definitely some redundant portal polygons being generated, which are not being appropriately Clipped.

They are coincident with some of the visible faces in the leaves they connect... that is to say, they not only share the same plane as one or more triangles, they are likely to be overlapping with them on said plane - conceptually, we wish to use the triangles to 'mask out' parts of the polygons that are within their bounds.

My portal-poly clipping function ignores polygons which are behind or coplanar with the clipping plane, so they slipped through the net.

I was hoping to avoid clipping of coplanar polygons as this is non trivial and prone to error... and I've had enough trouble with polygonal splitting and merging operations as it stands.

However, maybe I can still avoid it.

I have a theory that, if all previous operations were correct, the redundant portal polygons coincide EXACTLY with some coplanar triangles in the leaf. I should be able to use a process of elimination to decimate each polygon against coplanar triangles, and do it from my existing clipping function. I know it will work for this example model, I THINK it will work generally... this is revisiting the concept that a convex subspace is completely closed by the planes of its faces and portals.

Wrapping my Line/Plane intersection tests in a simple Macro helped to make the case handlers for the triangle splitter more consistant and helped knock out the bugs.

I have been studying the logged output of my tree generator, and using that information to step through the same process in the 3D modelling tool originally used to construct the current test model ('Box In A Box').

Attached are some screen shots.

My implementation chooses to make the first cut through +Z side of the inner box.

This results in 16 triangles on the 'front' side of the plane, and 24 on the 'back' side, when I perform this step in my modeller, the result is the same.

My impl. next chooses to cut through the -X side of the inner box.

The results this time are 13 to the front, and 20 to the back, again this agrees with my modeller.

My impl. then chooses to cut through the +Y side of the inner box.

The results now are 13 to the front, and 16 to the back.. My modeller disagrees, it does a better job than me of triangulating the polygons - My triangle code does not attempt to optimize/simplify the tesselation.

Its results are 11 to the front, and 16 to the back. Not bad though.

This goes on, until 5 of the 6 planes of the inner box have been used as splitting planes.

Anyway, the problem I currently have is related to the very last subspace we discover, and is due to the fact that my model contains a CLOSED SUBSPACE which is SOLID, ie UNREACHABLE (we think!)

Consider this last face of the inner box, surrounded by four of the five used splitting planes.

As we used each splitting plane to carve away at our model, we 'stole' a face of the inner box.

These faces are now in the other leaf nodes.. leaving only this one unused face, plus a bit of the outer box, in the last leaf node, parallel faces pointing at each other. This is actually a convex set, we can't choose either of these two planes to split the set. The problem is that our node thinks that it includes all the space INSIDE the inner box, as well as the remaining space outside of it.

It is worth noting that this problem subspace is a BACK LEAF, and in this example, happens to be the last and only back leaf.

One possible solution I am considering is to impose a constraint that states all back-facing leaf nodes must be EMPTY of polygons - if a leaf node is discovered which is found to be the back leaf of its parent, we will shove the faces down one node further, forcing selection of a splitting plane from those available. This means that only FRONT leaf nodes represent OPEN subspaces where the player can go, and BACK leaf nodes represent illegal void subspaces.

This solution seems perfectly viable until we reconsider our example, and note that we don't actually have any way to determine which plane from a convex set is actually valuable to us !! We know that it can't have been already used as a splitting plane, but otherwise, our plane selection algorithm doesn't know how to choose among these convex faces which plane to use in this final step.

Of course we know that a face which is part of the world's outer boundary is a VERY POOR CHOICE - this will always be true.

But there are bound to be cases where simply choosing the face closest to the world bounds will be the wrong choice.

Actually, it might be more appropriate to make my constraint even more forceful.... I might stipulate that every face in a subset must exist on a used splitting plane. This will absolutely guarantee that all potentially problematic closed subspaces are indeed fully closed in the bsp sense (unreachable subspaces will not be reachable by the point-in-open-leaf test), at the cost of unnecessary (but minor) tree depth due to the mindless inclusion of planes on the world's outer bounds - however I can think of lots of reasons FOR including these planes, so I am happy to go along with this as the final solution unless anyone has a better idea.

I would love to hear your thoughts, people!

Major bug located in my triangle-splitting implementation.

My algorithm for finding the intersection of a line segment (ie 'edge') and a plane expects the two endpoints of the line segments to be handed in a particular order, which I was not observing in all cases.

The result was that some child triangles were being created with incorrectly interpolated vertices, directly leading to them being incorrectly classified in subsequent iterations of the tree generating algorithm.

I hope I fixed all the cases, I will check them over today. I don't want to continue to examining the portal generator output until I am absolutely convinced that the tree is correct.

This brings me to a small point of contention.

The surface normals for some of my planes are being returned as 0.99999994 rather than 1.0 , and although this inaccuracy might seem acceptable given my planar tolerance of +/- 0.005, rounding errors such as this quickly add up over several recursive iterations - and especially so when we are bisecting space !!!

Should I be clamping normals to 0 and 1 when they are very close to being so? This assumes that there is much orthogonality in the 3D world, which I guess is a common scenario, even today. But given that I expect to handle organic shapes too, is clamping a good idea?

The fact that my Normal is not always exactly unit length for a plane aligned to a Major Axis is a bit of a concern.

What would you do?

More bugfixes and improvements.

The ChooseSplittingPlane method no longer returns planes which don't partition the input set, and its heuristic has been changed to take note of the number of triangles split by a candidate plane.

A bunch of small code changes and bug fixes were made, some enumerations were modified, the ClassifyTrianglePlane method has been changed to return more information, etc.

I am now getting 6 subspaces, separated by 5 planes... the subspaces contain different numbers of portal references, and the portal geometry contains references to the two leaves connected by each portal polygon.

Things are a lot better, however I'm not convinced yet that they are perfect.

Regardless, it's probably time for me to add some DebugRender stuff so I can digest the results of each iteration more quickly without having to study all the output data too much.

I'll probably post an update from Uni tomorrow.

[subheading]Shave and a Haircut?[/subheading]

When a problem comes along, you must Clip it ;)

At this point, most of the BSP tree will no longer be of any use to us - our leaf nodes, which represent our convex subspaces, each contains a list of 'portal fragments', some of which are actually 'duds', which must die, and others need some cosmetic attention.

For each leaf node, we will clip its portal fragments to the planes of the visible geometry in that leaf.

We will discard any resulting fragments that are found to be 'back' ie 'behind the plane' since they are not inside this subspace. This may involve discarding entire polygons..if its point away from us, or its totally behind any plane of our hull, then its not part of this subspace.

The front parts and the coplanar parts we will keep. These are the parts that are within the bounds of the current subspace. Actually I expect not to get any front parts, but we'll see.

What we are doing is constraining the portal geometry to the exact shape of the voids in our otherwise closed convex subspace, without violating their geometric constraints, such as existing apon one of the planes that bounds the subspace's closed hull.

To be clear, our subspace is an open convex hull, which is closed by planes of its portals. So our subspace has visible, solid surfaces, and it has some 'holes' that lead to other places. We have just discovered the exact shape of these holes. All that remains is to determine where they lead to, and do something useful with that information.

OK Wait - there is one final tricky special case to handle, but it can wait for my next post.

[subheading]Planar Polygonal Mating Rituals[/subheading]

So, we have reduced our set of fragments per leaf to a relatively small number. As a matter of fact, the only remaining portal polygon fragments are those which fit inside the shape of the holes, on the planar surfaces of our subspaces, ie, collectively, they represent the shapes of all the holes that connect any two subspaces in our world.

Note that each fragment is tagged with the ID of the Portal that originally owned it.

Now we reach the moment of truth - Connectivity.

For each leaf, and for each unique portal ID in that leaf, find another leaf which contains a portal fragment with the same ID.

These two leaf nodes are connected by this portal! Only two leaf nodes can contain pieces of the same portal, due to the fact that our partitioning scheme is bi-fold.

Move all the portal fragments which bear that Portal ID back into the owner portal, discarding the fragments in the 'other' of the two leaves (since they're 'clones'), and add to each Leaf a reference to said owner portal, and tag the Portal with a reference to each Leaf it leads to.

End Loop.

Now, each leaf contains no portal fragments - just visible triangles once more.

Each leaf contains a list of Portals that lead to adjacent subspaces, and each Portal knows which two subspaces it connects, and the shape of the connecting hole as projected apon a unique 3d plane on the surface of both subspaces, with respect to the first of the two (order of discovery).

We now have everything we need to construct a cell and portal graph - in fact, we have already created it

The problems in the tree generator and portal generator seem to be fixed.

I am now able to discover all the convex subspaces, construct the portals as BFQ's and then 'shatter' them against one another.

However before I post the updated sourcecode, I need to eliminate a bunch of runtime tracing/debugging stuff that helped me track down the bugs, and I'd like to have a go at improving the heuristic for selection of splitting planes (in the bsp tree gen).

I will note here that this endeavor is pretty much redundant, since I do not intend to use the BSP tree structure at runtime (as such).

However I will for the sake of completion go on to explain what its about.

[subheading]Can we do better?[/subheading]

The current heuristic treats the input set of triangles as a 'point cloud', choosing the plane which most equally bisects the vertices for 'best balance', without considering the geometry - the shapes involved. It does not care how many triangles the plane passes through, and makes no attempt to avoid doing so. This generates an inordinately high number of fragment triangles during bsp tree generation, and for me it's going to mean more duplicate triangle references to either filter or pay for in terms of pixel overdraw.

.

Our heuristic for selecting splitting planes should attempt to fulfill two goals simultaneously: good balance (don't favor one side of the tree too much), and fewest possible splits (avoid generating too many extra triangles, leading to extra tree depth). These goals both seem to make the tree not be too deep.

Although not immediately obvious, these two goals are in fact mutually exclusive. That, however, does not prevent us from designing and implementing a heuristic which tries its best to meet both objectives.

What we can do is attribute a 'fitness score' to each potential splitting plane, based apon the number of vertices falling on either side of the plane being similar (good), and the number of triangles that are cut by the plane (bad). Then we'll just return the candidate whose score is 'best' (which is a subjective term, depends on how we calculate our fitness score, but will typically be 'highest' or 'lowest').

[subheading]What's Next?[/subheading]

Now we have our Portals (one per non-leaf node), which were constructed as big fat quad, each apon one of the unique 3D planes we used to construct our tree. Each Portal object is a container for a bunch of convex fragment polygons resulting from the shattering of the convex BFQ polygons. We will now 'march' all the fragment polygons down the tree starting right from the very top (root node) until they each have landed in a leaf node.

Important note about this process:

Since the fragments are, collectively, the result of splitting every BFQ against every possible splitting plane, we can never have a case of a fragment being split by a plane during its 'walk' down the tree. If we do, we did not shatter the BFQs correctly.

We can take advantage of this fact... it implies that ANY point in a polygon will return a point/plane result that is true for the WHOLE polygon.

There are two small exceptions - the first is when our test point returns a Coplanar result - we'll need to try another point (or points) until we get a definitive result. But the odds of us picking a valid point on the first try are very good.

The second exception occurs when all the points of the fragment turn out to be coplanar (with the current node's plane). The implication is that all OTHER fragments of this current portal will also be coplanar with this current plane. This case needs special handling.

If we detect a fragment is coplanar with the current plane:

For every fragment in the current portal, duplicate (clone) the fragment, send the original down to the front child, flip the cloned fragment's surface normal (ie, the x,y,z components of its plane), and send the clone down to the back child.

The reasoning behind this will become clear in the final step, where we seek to mate the matching 'sides' of each Portal (since a Portal has two sides, each facing into an adjacent subspace). We have just ensured that there are indeed two sides, and that they indeed face into the correct subspaces - the last part ensures that they survive our next step: Culling and Clipping our Portal Fragments.

So, for each fragment, get a polygon/plane result (whether the 'long way' or the shortcut I've suggested), and (excepting those special coplanars) send the fragment intact to the corresponding child node, and repeat, until we can't anymore.

We should end up with our portal fragments in a jumbled mess, neatly contained in a single list in each and every leaf node.

We expect that all leaf nodes will receive portal fragments. If they don't, it indicates a 'solid subspace' which is somewhere the player should never be. Anyway, so each leaf now has a list of portal fragments, each tagged with the identity of its 'owner' portal. And we have our list of portals, now completely empty of any portal fragments.

We will now clip and cull the fragments - many will not survive this process. Those that do are our 'true portals', and their shape represents the exact silhouette of the portal, the shape of the 'hole'. I'll talk about that more in my next post

I've decided to spend a few hours hardening the current codebase through a series of exhaustive tests apon the triangle splitting code in the tree generator - I seem to be getting unreliable results for some reason (occasionally the output is not the same) and I need to understand why this is so.

I've been thinking about changing my Triangle class in the bsp tree gen too - and you haven't even seen it yet.

Looks like this:

// Defines a renderable triangle during tree generation

class Triangle

{

public:

Triangle(int iOrig, int iA, int iB, int iC):iOriginalIndex(iOrig), ivA(iA),ivB(iB),ivC(iC) { }

~Triangle() {};

// Vertex Indices

int ivA, ivB, ivC;

// Index of original triangle (since this triangle may have been 'fragmented' during tree generation)

int iOriginalIndex;

D3DXVECTOR4 Plane;

};

As you can see, each Triangle records its own Plane, this eliminates looking up the plane at runtime, a trivial optimization of a frequently performed lookup operation, which adds up quickly to provide a nice overall speedup.

Now, even though I am providing the plane for each triangle explicitly, the code for selecting a partitioning plane seems unreasonably slow (maybe its just my ASM background)... I am considering either replacing the vertex indices with pointers directly to the vertices, or just keeping the vertices in the triangles themselves. Either would effectively eliminate vertex lookups during the extremely cpu intensive task of selecting a partitioning plane. It also means I never have to record any geometric data that was generated solely due to splitting visible triangles (except within the triangles themselves) - I can leave my VBs and IBs alone.

Things seem to be going well.

The BSP Tree generator now successfully processes the 'box in a box' model into a bunch of convex subspaces and creates the Portals, intializing their geometry with Big Fat Quads.

I have implemented a full triangle-splitting BSP Tree generator, however I intend to remain true to my original plan.. when the BSP Tree has been generated, I will convert my Triangle structs back into simple references (indices) to original triangles. This will allow me to avoid interpolating vertex components other than position (currently I do bother to interpolate for position, normal, uv) when creating new vertices whenever a visible triangle is split during tree creation, it will also allow me to discard all junk vertices, indices, etc that were produced as a byproduct of full triangle splitting, and go back to the original input geometry only - which is lucky because my mesh class already uploaded that to hardware before I got hold of it, lol.

[subheading]In case of emergency, break glass...[/subheading]

The next step is to Shatter the portals.

As outlined, this involves splitting our Big Fat Quads against all the splitting planes that we used in our tree, and keeping all the output polygons irrespective of what side of a splitting plane they fall on, and even what shape they are.

Since we began with a convex portal geometry, and only bisected it, we know that all the fragments will be convex too.

We also know that they are 'flat' since the portals were originally constructed apon planes.... all the fragments in a given portal will remain coplanar.

The geometric requirements for portals are different for those of the visible triangles we processed thus far.

For this reason, two new classes (Polygon and Portal) have been introduced.

Unless something else blows up, I will post an update of the sourcecode today

Here is a picture of the Box in a Box model for anyone who struggles with visualizing something like that.

I found a bunch more small bugs and fixed them, but I haven't posted the changes yet...

I've created a test geometry involving two boxes, one inside the other, with the outer box's normals pointing inwards.

The BSP generator can't handle it. That's not good.

The BSP generator has two big problems.

The first is with this concept of just duplicating partitioned triangle indices that I've been trying out.

We end up passing entire geometries down the tree where they are duplicated endlessly.

The second problem is that I have not implemented some way of marking a splitting plane as having been previously used, and so not a suitable candidate in subsequent selections.

There may be no alternative but to implement a full partitioning of the input geometry.

I was hoping to avoid this because the result is that we generate a LOT more triangles and new vertices.

However I see no way to avoid it.

If anyone wants to comment, now is a good time

EDIT:

Having gone most of the way to fully implementing a complete triangle splitting bsp tree generator, I found more fundamental bugs in the implementation - subsequently I discovered that the Triangle Index based scheme probably would have been ok had these bugs not been causing hell.

Oh well, I'll forge ahead.

I have repurposed the global list of planes in the tree container class to record the planes I've actually used as a splitting plane, and implemented a Triangle class which contains indices and the triangle's plane.

Various methods have been adjusted to take a Triangle*

[subheading]Portal Geometry[/subheading]

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 {

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 {

// 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 {

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.

[subheading]Tracking Multiple Materials during BSP Tree Generation[/subheading]

My mesh loader sorts the model's triangles (ie vertex indices) into attribute groups by material, that's why you'll see references to "Sorted Indices" in my sourcecode.

I'm happy to completely forget about tracking materials at this stage because I know that I can easily determine what material any triangle uses via my 'attribute lists'.

These are simply the starting index and number of indices for each group of triangles.... very similar to what we'd find in a mesh that was sourced from a ".X-File" ...

So given any triangle index, I can determine what attribute range it falls into, and that tells me what indexed material from the mesh is being applied.

And it gets even better.

The triangle indices began life as a sorted list, and are processed in order during tree generation.

They remain sorted by material at all times, hah.

[subheading]Gathering the Renderables[/subheading]

Now about Rendering.

The 'render' function won't actually draw anything - not immediately anyway... it will recurse the visible portals with an ever-shrinking frustum, gathering up the visible triangle indices into an output indexbuffer, and then drawing them, hopefully with as few as one batch involved.

[subheading]What now?[/subheading]

Of course, that's a way off yet - we need to find the Portals now, and to do that, we need to start by creating 'big fat quads' that are aligned with each splitting plane (we recorded those at each non-leaf node). The vertices of these quads lay at the intersections of the plane and the node's boundingbox. For each non leaf node, we must find four vertices which are simultaneously coplanar with (ie 'on') the splitting plane, and on the surface of the bounding box.. sounds tricky, but it's not too bad.

[subheading]Keep them doggies movin'[/subheading]

Here's the goodies

Please forgive the organic nature of the code and do check periodically for an update!

The Leaf class currently consists only of a class def.. this is a work in progress. I may in fact decide to eliminate it after all.

I'm not very proficient at writing code in C++ so please feel free to educate me, I will certainly not be offended !!

#pragma once

#include "stdafx.h"

#include

#include

#include

#include

#include "dxBSPTree.h"

// This method calculates the Surface Normal and Plane-Distance of the given Triangle.

// Inputs:

// TriangleIndex iTriangle = index of unique triangle in the mesh's IndexBuffer

// (which contains a TriangleList of vertex indices).

// Outputs:

// D3DXVECTOR4 vPlane = triangle's plane (as surfacenormal and planeD)

D3DXVECTOR4 dxBSPTree::Calculate_Plane(Triangle* pTriangle)

{

D3DXVECTOR4 out;

D3DXVECTOR3* pout = (D3DXVECTOR3*) &out; // trick compiler into using the Vec4 as a Vec3 (ugh)

// Look up the Vertices corresponding to those indices,

// and calculate two Edge vectors originating at Point A

D3DXVECTOR3 vA = (m_pMesh->m_Vertices.at(pTriangle->ivA).Position);

D3DXVECTOR3 vAB = (m_pMesh->m_Vertices.at(pTriangle->ivB).Position) - vA;

D3DXVECTOR3 vAC = (m_pMesh->m_Vertices.at(pTriangle->ivC).Position) - vA;

// Calculate the Cross Product of the two vectors

D3DXVec3Cross(pout, &vAB, &vAC);

// Ensure the resulting Vector is of unit length

D3DXVec3Normalize(pout,pout);

// Calculate PlaneD : Ax + By + Cz + D = 0

out.w = - (D3DXVec3Dot(&vA, pout));

// Return the Plane

return out;

}

// This method generates the BSP Tree from the input list of triangle indices

void dxBSPTree::Generate_Tree()

{

dxPortal* pPortal;

if(m_pRootNode) delete m_pRootNode;

MessageBoxA(0,"Phase One: Generating BSP Tree","OK",MB_OK);

// Prepare the data we'll need during tree construction

std::vector *triangles = new std::vector();

int numtriangles = m_pMesh->GetIndexCount()/3;

for(int i=0; i {

// Grab the three indices for the current input triangle

int ivA = m_pMesh->m_SortedIndices.at(i*3);

int ivB = m_pMesh->m_SortedIndices.at(i*3+1);

int ivC = m_pMesh->m_SortedIndices.at(i*3+2);

// Create a container and fill its indices

Triangle* t = new Triangle(i,ivA,ivB,ivC); // #OriginalTriangle, #PointA, #PointB, #PointC

// Calculate the triangle's plane (as normal + planeD)

t->Plane = Calculate_Plane(t);

// Collect the new triangle object

triangles->push_back(t);

}

// Create Root Node, passing in the list of triangle indices

m_pRootNode = new dxBSPNode(this,NULL,triangles);

// Recurse Root Node - when we return, the entire tree has been created.

m_pRootNode->Generate_Tree();

MessageBoxA(0,"Phase One Complete: BSPTree generated and Portal List populated","Success",MB_OK);

MessageBoxA(0,"Phase Two: Shattering Portals","Here we go again",MB_OK);

vector* OutputList = new vector();

// We now have a list of Portals.

// For each Portal, we need to Split the Portal against every Splitting Plane (other than its own construction plane).

for(vector::iterator i=m_Portals.begin(); i!=m_Portals.end(); i++)

{

pPortal = (*i);

MessageBoxA(0,"NEXT PORTAL BEING SHATTERED",0,0);

// Rather than recurse the tree to access the splitting planes..

// Every Other Splitting Plane is available as 'the planes of all the other portals'

for(vector::iterator j=m_Portals.begin(); j!=m_Portals.end(); j++)

{

if(i==j) continue;

MessageBoxA(0,"NEXT PLANE BEING CONSIDERED",0,0);

// Let pPortal = the current Portal being Shattered

D3DXVECTOR4* pPlane = (*j)->GetPlane();

// We have to split every Polygon in this Portal

// Output polygons from splitting operations will be appended to the same list they were sourced from !!!

// We will make sure we process only the original number of polygons.

while(!pPortal->m_Polygons.empty())

{

dxPolygon* polygon = pPortal->m_Polygons.back();

pPortal->m_Polygons.pop_back();

PointPlaneResult res = pPortal->Split( polygon, pPlane, OutputList );

if(res!=-1)

{

// Polygon was not split - it was either totally in front, behind, or coplanar.

//OutputList->push_back(polygon);

MessageBoxA(0,"failed to split polygon",0,0);

}

else

{

// Polygon was Split... two childs were appended to the list.

MessageBoxA(0,"polygon was split",0,0);

}

}

//LOG("**************** RESULTS OF PORTAL POLYSPLIT **********************")

// Copy output polygons back into portal

while(!OutputList->empty())

{

//LOG("Polygon #"m_Polygons.size());

dxPolygon* poly = OutputList->back();

//for(int i=0; im_Points.size();i++)

//{

// LOG("Point #" m_Points.x m_Points.y m_Points.z);

//}

pPortal->m_Polygons.push_back(poly);

OutputList->pop_back();

}

}

}

delete OutputList;

MessageBoxA(0,"Phase Two Complete: All Portals have been Shattered and resulting fragments are ready to be sent down the tree","ok",MB_OK);

}

// Check if the given plane has already been used as a splitting plane before

bool dxBSPTree::IsPlaneUsed(D3DXVECTOR4* pPlane)

{

for(vector::iterator i = m_Planes.begin(); i!=m_Planes.end(); i++)

{

if((*i)==*pPlane) return true;

}

return false;

}

// Determine which Leaf node contains a given Point

// Returns leafnode, or NULL (point is not in any legal subspace).

// If the point is 'not legal', its inside a solid volume in our world,

// or outside the world itself, ie, somewhere a player should never be.

// This method is an example of 'walking a tree' without recursion.

dxBSPLeafNode* dxBSPTree::Find_Containing_Leaf(D3DXVECTOR3* pvPoint)

{

dxBSPNode* node = m_pRootNode;

while(node && !node->Is_Leaf())

{

switch(dxBSPNode::ClassifyPointPlane(pvPoint,node->Get_Plane()))

{

case COPLANAR:

case FRONT:

node = node->Get_Front_Child();

break;

case BACK:

node = node->Get_Back_Child();

break;

}

}

// We replaced all terminal dxBSPNodes with a dxBSPLeafNode

return (dxBSPLeafNode*) node;

}

void dxBSPTree::FrogMarch_Portal_Polygons(dxBSPNode* pStartNode, dxPortal* portal)

{

while(!portal->m_Polygons.empty())

{

dxPolygon* poly = portal->m_Polygons.back();

portal->m_Polygons.pop_back();

m_pRootNode->Quick_March(poly);

}

}

// Credit to Alan Baylis apon whose code some of this was based

#include "stdafx.h"

#include "dxBSPNode.h"

#include "dxBSPLeafNode.h"

#include "dxPortal.h"

// Classify a Point and a Plane, returning an enumerated result value

PointPlaneResult dxBSPNode::ClassifyPointPlane(D3DXVECTOR3* pPt, D3DXVECTOR4* pPlane)

{

//LOG("ClassifyPoint ("xyz float result = D3DXVec3Dot(pPt, (D3DXVECTOR3*) pPlane) + pPlane->w;

if(result else if(result > PLANAR_HALF_EPSILON) {return FRONT;}

return COPLANAR;

}

// RECURSIVE BEHAVIOR:

// This method attempts to split an input set of triangles (m_pvTriangles) into two subsets via a 'splitting plane'

// which is itself selected from the planes of the input triangles.

// Then it shoves the two output lists into two child nodes, and recurses them.

// TERMINAL CASE:

// If we fail to split an input set of triangles, the input set is considered to be Convex,

// and the node is considered to be a Leaf node - we will return from Recursion in this case.

void dxBSPNode::Generate_Tree()

{

LOG("============= GENERATING NODE =================== "

for(int i=0;isize();i++)

{

Triangle* tri = m_pvTriangles->at(i);

D3DXVECTOR3* pV = &m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position;

LOG("INPUT #"xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position;

LOG("INPUT #"xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position;

LOG("INPUT #"xyz);

}

// Determine the bounds of the input set of triangles

Calculate_Bounds();

// Find the best partitioning plane for the input set of Triangles

// Set this plane as the current node's partitioning plane

int bestfront=-1, bestback=-1;

int bestplane = Choose_Partitioning_Plane(&bestfront,&bestback);

// If we failed to find a partitioning plane, the input triangles are considered to be a convex set,

// and therefore the current node is considered to be a terminal (ie leaf) node.

// In this case we will replace 'this' node with a more specialized Leaf node, and return from recursion.

if(bestplane == -1)

{

// Replace THIS node with a special 'leaf' node

// MessageBoxA(0,"FOUND CONVEX SET","LEAF",0);

dxBSPLeafNode* temp = new dxBSPLeafNode(m_pTree,m_pParent->m_pParent,m_pvTriangles);

temp->m_Plane = m_Plane;

if(m_pParent->m_pFrontChild == this)

{

m_pParent->Attach_Front_Child(temp);

} else {

m_pParent->Attach_Back_Child(temp);

}

m_pvTriangles = 0; // preserve

delete this; // trash myself

return; // get outta here

}

// Set this node's partitioning plane

m_Plane = m_pvTriangles->at(bestplane)->Plane;

LOG("SELECTED PLANE: ("

// Attempt to Partition input triangles into two child sets:

// Even though we found a 'best' splitting plane,

// this method can still return all the triangles in just one of the output lists !!

// This is because the heuristic we used only considers the triangle vertices as a point cloud,

// whereas the actual splitting method detects and handles special cases like splits and coplanars.

// We DO need to check what we have been returned and take it like a man.

vector* pFrontTris = new vector();

vector* pBackTris = new vector();

Split_Triangles(pFrontTris, pBackTris);

// If all the triangles landed in only one child list,

// replace this node with a Leaf containing the triangle list

if( pFrontTris->empty() && !pBackTris->empty() )

{

// All the triangles landed in the Back output list.

// Convert into convex subspace, retaining the 'used plane' data

delete pFrontTris;

if(m_pParent)

{

// Replace THIS node with a special 'leaf' node

dxBSPLeafNode* temp = new dxBSPLeafNode(m_pTree,m_pParent->m_pParent,pBackTris);

temp->m_Plane = m_Plane;

if(m_pParent->m_pFrontChild == this)

{

m_pParent->Attach_Front_Child(temp);

} else {

m_pParent->Attach_Back_Child(temp);

}

delete this; // trash myself

//MessageBoxA(0,"RETURN FROM BACK OUTPUT","LEAF",0);

}

else

{

// Failed to split the root node??

MessageBoxA(0,"Error: Root Node triangles could not be Split A",0,0);

exit(1);

}

} else if ( !pFrontTris->empty() && pBackTris->empty() )

{

// All the triangles landed in the Front output list

// The back of the plane is solid space.

// We'll make a convex subspace out of this situation,

// and retain the 'used portal' data.

delete pBackTris;

if(m_pParent)

{

//MessageBoxA(0,"DISCOVERED FRONT LEAF","LEAF",0);

// Pop the last element back off the used planes list

// Replace THIS node with a special 'leaf' node,

// since the selected plane wasn't actually used.

dxBSPLeafNode* temp = new dxBSPLeafNode(m_pTree,m_pParent->m_pParent,pFrontTris);

temp->m_Plane = m_Plane;

if(m_pParent->m_pFrontChild == this)

{

//MessageBoxA(0,"attached to front","LEAF",0);

m_pParent->Attach_Front_Child(temp);

} else {

//MessageBoxA(0,"attached to back","LEAF",0);

m_pParent->Attach_Back_Child(temp);

}

delete this; // trash myself

//MessageBoxA(0,"RETURN FROM FRONT OUTPUT","LEAF",0);

}

else

{

// Failed to split the root node??

MessageBoxA(0,"Error: Root Node triangles could not be Split B",0,0);

exit(1);

}

} else if( !pFrontTris->empty() && !pBackTris->empty() )

{

LOG("*************** NODE WAS SPLIT ******************");

LOG("PLANE was " LOG("front received "size()size());

for(int i=0;isize();i++)

{

Triangle* tri = pFrontTris->at(i);

D3DXVECTOR3* pV = &m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position;

LOG("Front #"xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position;

LOG("Front #"xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position;

LOG("Front #"xyz);

}

for(int i=0;isize();i++)

{

Triangle* tri = pBackTris->at(i);

D3DXVECTOR3* pV = &m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position;

LOG("Back #"xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position;

LOG("Back #"xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position;

LOG("Back #"xyz);

}

//MessageBoxA(0,"TYPICAL OUTPUT","NON LEAF",0);

// Both output lists contain triangles - this is the usual case.

// Attach and Recurse the list of triangles found to be in front of the plane

Attach_Front_Child(new dxBSPNode(m_pTree,this,pFrontTris));

Attach_Back_Child(new dxBSPNode(m_pTree,this,pBackTris));

delete m_pvTriangles; // trash input list

m_pvTriangles = 0;

m_pFrontChild->Generate_Tree();

m_pBackChild->Generate_Tree();

// Create a new Portal at this node

CreatePortal();

//MessageBoxA(0,"CREATED PORTAL : RETURN FROM NON LEAF NODE","NON LEAF",0);

} else

{

// We should never get here - it means both output lists were returned empty(!)

MessageBoxA(0,"Error: bsp node partitioning returned no triangles !!",0,0);

exit(1);

}

}

// Partition the node's triangles into two output lists

void dxBSPNode::Split_Triangles(vector* pFrontOutput, vector* pBackOutput)

{

int results[3];

dxMeshResource::Vertex Intersections[2];

Triangle* tri;

// We're going to consume this node's input triangles, at the end there should be none remaining

while(!m_pvTriangles->empty())

{

// Number of triangle vertices found behind, before, and on the plane

int front = 0;

int back = 0;

int coplanar = 0;

// Get a pointer to the current Triangle and remove it from the input list

tri = m_pvTriangles->back();

m_pvTriangles->pop_back();

D3DXVECTOR3* pV = &m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position;

LOG("SPLITTING TRIANGLE: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position;

LOG("SPLITTING TRIANGLE: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position;

LOG("SPLITTING TRIANGLE: "xyz);

// classify the triangle against the plane

int result = ClassifyTrianglePlane( tri, &m_Plane);

// tally the results: there are three PointPlaneResult values compressed into 6 bits

for(int i=0; i {

int r = result & 3;

results=r;

if(r == FRONT)

{

front++;

}

else if(r == BACK)

{

back++;

}

else // COPLANAR

{

coplanar++;

}

// check the next point/plane result

result = result >> 2;

}

// Analyze the results: determine whether this triangle is intersected by the splitting plane.

// If the triangle is fully coplanar with the splitting plane,

// we will decide which half-space it is facing into, and send it to that child list.

if(coplanar==3)

{

// We want the Normals of the splitting plane and the triangle

D3DXVECTOR3* pNorm1 = (D3DXVECTOR3*) &m_Plane; // trick compiler into using the Vec4 as a Vec3 (ugh)

D3DXVECTOR3* pNorm2 = (D3DXVECTOR3*) &tri->Plane;

// Get the dot product of the two Normals (ie those of the triangle and the splitting plane)

float result = D3DXVec3Dot(pNorm1, pNorm2);

// Push the triangle reference down whichever child it faces into ;)

if(result > (1.0f - PLANAR_HALF_EPSILON*2 ))

{

LOG("(Coplanar->FRONT)");

pFrontOutput->push_back( tri );

}

else

{

LOG("(Coplanar->BACK)");

pBackOutput->push_back( tri );

}

}

// Else if the triangle is on the front side (abutting is included)

else if(back == 0 || front!=0 && front+coplanar==3)

{

LOG("(FRONT)");

pFrontOutput->push_back( tri );

}

// Else if the triangle is behind the plane (abutting is included)

else if(front == 0 || back!=0 && back+coplanar==3)

{

LOG("(BACK)");

pBackOutput->push_back( tri );

}

////////////////////////////////////////////////////////////////////////////////////

// Otherwise we must have a 'split' result - the plane cuts through this triangle

// We have a hack of a lot of work to do here

else

{

Triangle* baby;

LOG("SPLITTING: " if(front==1 && back==2)

{

// One of the three points is on the front side of the plane.

// Our split results will depend on which one that is.

/*

A B C

=I1===I2== ========= =========

\

\

B C C A A B

*/

if(results[0]==FRONT)

{

float fLerpFactorAB = this->IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position,&m_Plane);

if(fLerpFactorAB>0.0f && fLerpFactorAB {

float fLerpFactorCA = this->IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position,&m_Plane);

if(fLerpFactorCA>0.0f && fLerpFactorCA {

LOG("Style = OneFrontTwoBack (1)");

Intersections[0].Position = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position;

Intersections[0].Normal = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal;

Intersections[0].UV = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV;

Intersections[1].Position = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position;

Intersections[1].Normal = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal;

Intersections[1].UV = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV;

// front = A I1 I2

// back1 = I1 B C

// back2 = I1 C I2

int iIntersection1 = m_pTree->m_pMesh->m_Vertices.size();

int iIntersection2 = iIntersection1+1;

m_pTree->m_pMesh->m_Vertices.push_back(Intersections[0]);

m_pTree->m_pMesh->m_Vertices.push_back(Intersections[1]);

baby = new Triangle(tri->iOriginalIndex, tri->ivA,iIntersection1, iIntersection2);

baby->Plane = tri->Plane;

pFrontOutput->push_back(baby);

D3DXVECTOR3* pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;

LOG("FRONT FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;

LOG("FRONT FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;

LOG("FRONT FRAGMENT: "xyz);

baby = new Triangle(tri->iOriginalIndex, iIntersection1, tri->ivB, tri->ivC);

baby->Plane = tri->Plane;

pBackOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;

LOG("BACK FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;

LOG("BACK FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;

LOG("BACK FRAGMENT: "xyz);

baby = new Triangle(tri->iOriginalIndex, iIntersection1, tri->ivC, iIntersection2);

baby->Plane = tri->Plane;

pBackOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;

LOG("BACK FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;

LOG("BACK FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;

LOG("BACK FRAGMENT: "xyz);

delete tri;

}

else

{

MessageBoxA(0,"Expected CA intersection not found",0,0);

exit(1);

}

}

else

{

MessageBoxA(0,"Expected AB intersection not found",0,0);

exit(1);

}

}

else if(results[1]==FRONT)

{

float fLerpFactorBC = IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position,&m_Plane);

if(fLerpFactorBC>0.0f && fLerpFactorBC {

float fLerpFactorAB = IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position,&m_Plane);

if(fLerpFactorAB>0.0f && fLerpFactorAB {

LOG("Style = OneFrontTwoBack (2)");

Intersections[0].Position = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position;

Intersections[0].Normal = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal;

Intersections[0].UV = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV;

Intersections[1].Position = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position;

Intersections[1].Normal = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal;

Intersections[1].UV = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV;

// front = B I1 I2

// back1 = I1 C A

// back2 = I1 A I2

int iIntersection1 = m_pTree->m_pMesh->m_Vertices.size();

int iIntersection2 = iIntersection1+1;

m_pTree->m_pMesh->m_Vertices.push_back(Intersections[0]);

m_pTree->m_pMesh->m_Vertices.push_back(Intersections[1]);

baby = new Triangle(tri->iOriginalIndex, tri->ivB, iIntersection1, iIntersection2);

baby->Plane = tri->Plane;

pFrontOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;

LOG("FRONT FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;

LOG("FRONT FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;

LOG("FRONT FRAGMENT: "xyz);

baby = new Triangle(tri->iOriginalIndex, iIntersection1, tri->ivC, tri->ivA);

baby->Plane = tri->Plane;

pBackOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;

LOG("BACK FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;

LOG("BACK FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;

LOG("BACK FRAGMENT: "xyz);

baby = new Triangle(tri->iOriginalIndex, iIntersection1, tri->ivA, iIntersection2);

baby->Plane = tri->Plane;

pBackOutput->push_back( baby);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;

LOG("BACK FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;

LOG("BACK FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;

LOG("BACK FRAGMENT: "xyz);

delete tri;

}

else

{

MessageBoxA(0,"Expected AB intersection not found",0,0);

LOG("fLerpFactorAB =" exit(1);

}

}

else

{

LOG("fLerpFactorBC =" MessageBoxA(0,"Expected BC intersection not found",0,0);

exit(1);

}

}

else

{

float fLerpFactorCA = IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position,&m_Plane);

if(fLerpFactorCA>0.0f && fLerpFactorCA {

float fLerpFactorBC = IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position,&m_Plane);

if(fLerpFactorBC>0.0f && fLerpFactorBC {

LOG("Style = OneFrontTwoBack (3)");

Intersections[0].Position = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position;

Intersections[0].Normal = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal;

Intersections[0].UV = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV;

Intersections[1].Position = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position;

Intersections[1].Normal = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal;

Intersections[1].UV = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV;

// front = C I1 I2

// back1 = I1 A B

// back2 = I1 B I2

int iIntersection1 = m_pTree->m_pMesh->m_Vertices.size();

int iIntersection2 = iIntersection1+1;

m_pTree->m_pMesh->m_Vertices.push_back(Intersections[0]);

m_pTree->m_pMesh->m_Vertices.push_back(Intersections[1]);

baby = new Triangle(tri->iOriginalIndex, tri->ivC, iIntersection1, iIntersection2);

baby->Plane = tri->Plane;

pFrontOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;

LOG("FRONT FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;

LOG("FRONT FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;

LOG("FRONT FRAGMENT: "xyz);

baby = new Triangle(tri->iOriginalIndex, iIntersection1, tri->ivA, tri->ivB);

baby->Plane = tri->Plane;

pBackOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;

LOG("BACK FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;

LOG("BACK FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;

LOG("BACK FRAGMENT: "xyz);

baby = new Triangle(tri->iOriginalIndex, iIntersection1, tri->ivB, iIntersection2);

baby->Plane = tri->Plane;

pBackOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;

LOG("BACK FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;

LOG("BACK FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;

LOG("BACK FRAGMENT: "xyz);

delete tri;

}

else

{

MessageBoxA(0,"Expected BC intersection not found",0,0);

LOG("fLerpFactorBC =" exit(1);

}

}

else

{

LOG("fLerpFactorCA =" MessageBoxA(0,"Expected CA intersection not found",0,0);

exit(1);

}

}

}

else if(front==2 && back==1)

{

// One of the three points is at the Back.

// Our split results will depend on which one.

/*

C B A C B A

=I2====I1== ========= =========

A B C

*/

if(results[0]==BACK)

{

float fLerpFactorAB = this->IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position,&m_Plane);

if(fLerpFactorAB>0.0f && fLerpFactorAB {

float fLerpFactorCA = this->IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position,&m_Plane);

if(fLerpFactorCA>0.0f && fLerpFactorCA {

LOG("Style = TwoFrontOneBack (1)");

Intersections[0].Position = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position;

Intersections[0].Normal = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal;

Intersections[0].UV = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV;

Intersections[1].Position = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position;

Intersections[1].Normal = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal;

Intersections[1].UV = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV;

// back = A I1 I2

// front1 = I1 B C

// front2 = I1 C I2

int iIntersection1 = m_pTree->m_pMesh->m_Vertices.size();

int iIntersection2 = iIntersection1+1;

m_pTree->m_pMesh->m_Vertices.push_back(Intersections[0]);

m_pTree->m_pMesh->m_Vertices.push_back(Intersections[1]);

baby = new Triangle(tri->iOriginalIndex, tri->ivA, iIntersection1, iIntersection2);

baby->Plane = tri->Plane;

pBackOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;

LOG("BACK FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;

LOG("BACK FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;

LOG("BACK FRAGMENT: "xyz);

baby = new Triangle(tri->iOriginalIndex, iIntersection1, tri->ivB, tri->ivC);

baby->Plane = tri->Plane;

pFrontOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;

LOG("FRONT FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;

LOG("FRONT FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;

LOG("FRONT FRAGMENT: "xyz);

baby = new Triangle(tri->iOriginalIndex, iIntersection1, tri->ivC, iIntersection2) ;

baby->Plane = tri->Plane;

pFrontOutput->push_back( baby);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;

LOG("FRONT FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;

LOG("FRONT FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;

LOG("FRONT FRAGMENT: "xyz);

delete tri;

}

else

{

MessageBoxA(0,"Expected CA intersection not found",0,0);

exit(1);

}

}

else

{

MessageBoxA(0,"Expected AB intersection not found",0,0);

exit(1);

}

}

else if(results[1]==BACK)

{

float fLerpFactorBC = this->IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position,&m_Plane);

if(fLerpFactorBC>0.0f && fLerpFactorBC {

float fLerpFactorAB = this->IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position,&m_Plane);

if(fLerpFactorAB>0.0f && fLerpFactorAB {

LOG("Style = TwoFrontOneBack (2)");

Intersections[0].Position = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position;

Intersections[0].Normal = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal;

Intersections[0].UV = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV;

Intersections[1].Position = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position;

Intersections[1].Normal = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal;

Intersections[1].UV = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV;

// back = B I1 I2

// front1 = I1 C A

// front2 = I1 A I2

int iIntersection1 = m_pTree->m_pMesh->m_Vertices.size();

int iIntersection2 = iIntersection1+1;

m_pTree->m_pMesh->m_Vertices.push_back(Intersections[0]);

m_pTree->m_pMesh->m_Vertices.push_back(Intersections[1]);

baby = new Triangle(tri->iOriginalIndex, tri->ivB, iIntersection1, iIntersection2);

baby->Plane = tri->Plane;

pBackOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;

LOG("BACK FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;

LOG("BACK FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;

LOG("BACK FRAGMENT: "xyz);

baby = new Triangle(tri->iOriginalIndex, iIntersection1, tri->ivC, tri->ivA);

baby->Plane = tri->Plane;

pFrontOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;

LOG("FRONT FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;

LOG("FRONT FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;

LOG("FRONT FRAGMENT: "xyz);

baby = new Triangle(tri->iOriginalIndex, iIntersection1, tri->ivA, iIntersection2);

baby->Plane = tri->Plane;

pFrontOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;

LOG("FRONT FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;

LOG("FRONT FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;

LOG("FRONT FRAGMENT: "xyz);

delete tri;

}

else

{

MessageBoxA(0,"Expected AB intersection not found",0,0);

exit(1);

}

}

else

{

MessageBoxA(0,"Expected BC intersection not found",0,0);

exit(1);

}

}

else

{

float fLerpFactorCA = this->IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position,&m_Plane);

if(fLerpFactorCA>0.0f && fLerpFactorCA {

float fLerpFactorBC = this->IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position,&m_Plane);

if(fLerpFactorBC>0.0f && fLerpFactorBC {

LOG("Style = TwoFrontOneBack (3)");

Intersections[0].Position = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position;

Intersections[0].Normal = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal;

Intersections[0].UV = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV;

Intersections[1].Position = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position;

Intersections[1].Normal = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal;

Intersections[1].UV = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV;

// back = C I1 I2

// front1 = I1 A B

// front2 = I1 B I2

int iIntersection1 = m_pTree->m_pMesh->m_Vertices.size();

int iIntersection2 = iIntersection1+1;

m_pTree->m_pMesh->m_Vertices.push_back(Intersections[0]);

m_pTree->m_pMesh->m_Vertices.push_back(Intersections[1]);

baby = new Triangle(tri->iOriginalIndex, tri->ivC, iIntersection1, iIntersection2);

baby->Plane = tri->Plane;

pBackOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;

LOG("BACK FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;

LOG("BACK FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;

LOG("BACK FRAGMENT: "xyz);

baby = new Triangle(tri->iOriginalIndex, iIntersection1, tri->ivA, tri->ivB);

baby->Plane = tri->Plane;

pFrontOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;

LOG("FRONT FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;

LOG("FRONT FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;

LOG("FRONT FRAGMENT: "xyz);

baby = new Triangle(tri->iOriginalIndex, iIntersection1, tri->ivB, iIntersection2) ;

baby->Plane = tri->Plane;

pFrontOutput->push_back( baby);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;

LOG("FRONT FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;

LOG("FRONT FRAGMENT: "xyz);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;

LOG("FRONT FRAGMENT: "xyz);

delete tri;

}

else

{

MessageBoxA(0,"Expected BC intersection not found",0,0);

exit(1);

}

}

else

{

MessageBoxA(0,"Expected CA intersection not found",0,0);

exit(1);

}

}

}

else if(front==1 && back==1)

{

MessageBoxA(0,"SplitTheGuts",0,0);

// We have points that are coplanar, front and back.

// Our split result will depend on the configuration.

/*

A B C

| | |

| | |

| | |

B I C C I A A I B

*/

if(results[0]==COPLANAR)

{

// Calculate the Parametric Solution for the intersection point "u" (thanks Paul Bourke)

float fLerpFactorBC = this->IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position,&m_Plane);

// If "u" is between 0 and 1 then the intersection is legal (occurs between the endpoints of the line segment, our edge BC)

if(fLerpFactorBC>0.0f && fLerpFactorBC {

MessageBoxA(0,"SplitTheGuts 1",0,0);

// Calculate the point where the plane intersects with edge BC (just interpolate using "u")

Intersections[0].Position = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position;

// I'm going to go ahead and interpolate for all components of my vertex format

Intersections[0].Normal = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal;

Intersections[0].UV = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV;

// Note the index of the new vertex at intersection point

int iIntersection1=m_pTree->m_pMesh->m_Vertices.size();

// Add the new vertex

m_pTree->m_pMesh->m_Vertices.push_back(Intersections[0]);

// Construct two output triangles according to the following template:

// FRONT = ABI

// BACK = AIC

baby = new Triangle(tri->iOriginalIndex, tri->ivA, tri->ivB, iIntersection1);

baby->Plane = tri->Plane;

pFrontOutput->push_back( baby );

baby = new Triangle(tri->iOriginalIndex, tri->ivA, iIntersection1, tri->ivC);

baby->Plane = tri->Plane;

pBackOutput->push_back( baby );

}

else

{

MessageBoxA(0,"Expected BC intersection not found",0,0);

exit(1);

}

}

else if(results[1]==COPLANAR)

{

float fLerpFactorCA = this->IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position,&m_Plane);

if(fLerpFactorCA>0.0f && fLerpFactorCA {

MessageBoxA(0,"SplitTheGuts 2",0,0);

Intersections[0].Position = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position;

Intersections[0].Normal = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal;

Intersections[0].UV = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV;

int iIntersection1=m_pTree->m_pMesh->m_Vertices.size();

m_pTree->m_pMesh->m_Vertices.push_back(Intersections[0]);

// FRONT = BCI

// BACK = BIA

baby = new Triangle(tri->iOriginalIndex, tri->ivB, tri->ivC, iIntersection1);

baby->Plane = tri->Plane;

pFrontOutput->push_back( baby );

baby = new Triangle(tri->iOriginalIndex, tri->ivB, iIntersection1, tri->ivA);

baby->Plane = tri->Plane;

pBackOutput->push_back( baby );

}

else

{

MessageBoxA(0,"Expected CA intersection not found",0,0);

exit(1);

}

}

else if(results[2]==COPLANAR)

{

MessageBoxA(0,"SplitTheGuts 3",0,0);

float fLerpFactorAB = this->IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position,&m_Plane);

if(fLerpFactorAB>0.0f && fLerpFactorAB {

Intersections[0].Position = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position;

Intersections[0].Normal = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal;

Intersections[0].UV = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV;

int iIntersection1=m_pTree->m_pMesh->m_Vertices.size();

m_pTree->m_pMesh->m_Vertices.push_back(Intersections[0]);

baby = new Triangle(tri->iOriginalIndex, tri->ivC, tri->ivA, iIntersection1);

baby->Plane = tri->Plane;

pFrontOutput->push_back( baby );

baby = new Triangle(tri->iOriginalIndex, tri->ivC, iIntersection1, tri->ivB);

baby->Plane = tri->Plane;

pBackOutput->push_back( baby );

}

else

{

MessageBoxA(0,"Expected AB intersection not found",0,0);

exit(1);

}

}

else

{

MessageBoxA(0,"ouch",0,0);

exit(1);

}

}

}

}

// }

LOG("RETURNING FROM SPLITTER");

}

// Select a partitioning plane from the planes of all the input triangles

int dxBSPNode::Choose_Partitioning_Plane(int* bestfront, int* bestback)

{

int count = 0, absdifference = 1000000000, bestplane = -1, front, back, potentialplane, polytoclassify;

D3DXVECTOR3 temp;

int result;

int tricount = (int)m_pvTriangles->size();

LOG("CHOOSING PARTITIONING PLANE from "

// For splitting plane triangle = every Triangle in the input set

for(potentialplane = 0; potentialplane {

Triangle* PLANETRI = m_pvTriangles->at(potentialplane);

// Look up the Plane of that triangle

D3DXVECTOR4* pPlane = &PLANETRI->Plane;

// Don't use planes that were already used

if(m_pTree->IsPlaneUsed(&PLANETRI->Plane)) continue;

// LOG("Test Plane #"xyzw

// Clear evaluation counters for the current triangle

front = back = 0;

// For subject triangle = every (other) triangle in the input set

for (polytoclassify = 0; polytoclassify {

// Get the true, original index of the subject triangle

Triangle* TESTTRI = m_pvTriangles->at(polytoclassify);

//Don't compare against same plane

if(polytoclassify!=potentialplane)

{

// classify the triangle against the plane

// This returns three enumerated results, squished into 6 bits of an integer

result = ClassifyTrianglePlane( TESTTRI, pPlane);

// tally the results

for(int i=0; i {

int r = result & 3;

if(r == FRONT)

{

front++;

}

else if(r == BACK)

{

back++;

}

else if(r==COPLANAR) // COPLANAR

{

front++;

back++;

} else {

MessageBoxA(0,"UNEXPECTED RESULT from ClassifyTrianglePlane",0,0);

exit(1);

}

// check the next point/plane result

result = result >> 2;

}

}

}

// track the lowest absolute difference

if (abs(front - back) {

absdifference = abs(front - back);

bestplane = potentialplane;

*bestfront = front;

*bestback = back;

}

// track the number of times we found a triangle totally on one side

if (front == 0 || back == 0) count++;

}

// If we failed to find any plane which partitions the triangles

if (count == tricount)

return -1;

// Otherwise, return the (index of the) best one we found

else

{

// If we chose a plane, collect it so we dont use it in future

if(bestplane!=-1) m_pTree->m_Planes.push_back(m_pvTriangles->at(bestplane)->Plane);

return bestplane;

}

}

// Classify a triangle and plane: return three enumerated results, packed into 6 bits

int dxBSPNode::ClassifyTrianglePlane(Triangle* pTriangle, D3DXVECTOR4* pPlane)

{

// Classify each of the three triangle vertices against the plane

PointPlaneResult resA = ClassifyPointPlane(&m_pTree->m_pMesh->m_Vertices.at(pTriangle->ivA).Position, pPlane);

PointPlaneResult resB = ClassifyPointPlane(&m_pTree->m_pMesh->m_Vertices.at(pTriangle->ivB).Position, pPlane);

PointPlaneResult resC = ClassifyPointPlane(&m_pTree->m_pMesh->m_Vertices.at(pTriangle->ivC).Position, pPlane);

// Return a compound result

// Each point result returns 0,1 or 2.. so takes a maximum of two bits.

// Therefore we can jam all three results into just six bits.

return ((int) resC }

// Calculate the axially aligned bounding box of the input set of triangles for this node.

void dxBSPNode::Calculate_Bounds()

{

D3DXVECTOR3* pVec;

// Initialize the bounds to the origin

m_Bounds.vMax = m_Bounds.vMin = D3DXVECTOR3(0,0,0);

// Find the axial maxima and minima of all the input triangle vertices

for(int i=0; isize(); i++)

{

Triangle* tri = m_pvTriangles->at(i);

// Examine the axial components of the vertex's position,

// and expand our box bounds to enclose the vertex.

pVec = &m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position;

if (pVec->x x;

else if (pVec->x > m_Bounds.vMax.x) m_Bounds.vMax.x = pVec->x;

if (pVec->y y;

else if (pVec->y > m_Bounds.vMax.y) m_Bounds.vMax.y = pVec->y;

if (pVec->z z;

else if (pVec->z > m_Bounds.vMax.z) m_Bounds.vMax.z = pVec->z;

pVec = &m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position;

if (pVec->x x;

else if (pVec->x > m_Bounds.vMax.x) m_Bounds.vMax.x = pVec->x;

if (pVec->y y;

else if (pVec->y > m_Bounds.vMax.y) m_Bounds.vMax.y = pVec->y;

if (pVec->z z;

else if (pVec->z > m_Bounds.vMax.z) m_Bounds.vMax.z = pVec->z;

pVec = &m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position;

if (pVec->x x;

else if (pVec->x > m_Bounds.vMax.x) m_Bounds.vMax.x = pVec->x;

if (pVec->y y;

else if (pVec->y > m_Bounds.vMax.y) m_Bounds.vMax.y = pVec->y;

if (pVec->z z;

else if (pVec->z > m_Bounds.vMax.z) m_Bounds.vMax.z = pVec->z;

}

}

// 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()

{

//LOG("CREATING NEW PORTAL plane = " // 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))

{

// LOG("Chose Major X");

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))

{

// LOG("Chose Major Y");

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

{

// LOG("Chose Major Z");

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(pOut);

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);

// for(int i=0; im_Points.size();i++)

// {

// LOG("Point #" m_Points.x m_Points.y m_Points.z);

// }

}

// 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 dxBSPNode::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.

}

// Accessor methods

D3DXVECTOR4* dxBSPNode::Get_Plane()

{

return &m_Plane;

}

dxBSPNode* dxBSPNode::Get_Front_Child()

{

return m_pFrontChild;

}

dxBSPNode* dxBSPNode::Get_Back_Child()

{

return m_pBackChild;

}

// This method will shove the given polygon down the tree and into a leaf node.

// If we find it is coplanar with any splitting plane along the way,

// we will Clone the polygon, flipping its normal, and shove the two polygons

// into their respective child subtrees.

// Remarks:

// This method is handling POLYGONS - pieces of portals - NOT TRIANGLES !!!

void dxBSPNode::Quick_March(dxPolygon* poly)

{

if (Is_Leaf())

{

// I know, I know, downcasting from a baseclass to a derived class is a bad idea.

// However this won't be a problem for the implementation at hand.

dxBSPLeafNode* pthis = static_cast(this);

// The leaf node will collect this polgon

pthis->m_PortalFragments.push_back(poly);

}

else

{

dxBSPNode* front = Get_Front_Child();

dxBSPNode* back = Get_Back_Child();

// Classify points until we get a definitive result

for(int i=0; im_Points.size(); i++)

{

D3DXVECTOR3* pPoint = &poly->m_Points;

switch(ClassifyPointPlane(pPoint,&m_Plane))

{

case COPLANAR:

// Result not definitive - try next point

break;

case FRONT:

front->Quick_March(poly);

return;

case BACK:

back->Quick_March(poly);

return;

}

}

// Special case - all points were coplanar:

// Clone all Fragments of this Portal

dxPolygon* clone = new dxPolygon(poly->m_pPortal);

*clone = *poly; // copy all data

// Flip surface normal of clone's plane

clone->m_Plane.x = -clone->m_Plane.x;

clone->m_Plane.y = -clone->m_Plane.y;

clone->m_Plane.z = -clone->m_Plane.z;

// Send clone polygon to the back child

back->Quick_March(clone);

// Send this portal fragments to front child

front->Quick_March(poly);

}

}

#include "stdafx.h"

#include "dxBSPNode.h"

// Constructor for polygons will set 'construction portal' and 'construction plane' data.

dxPolygon::dxPolygon(dxPortal* pOwner):m_pPortal(pOwner), m_Plane(*m_pPortal->GetPlane()) { }

// This method will attempt to partition a portal's geometry with a splitting plane from a non-leaf bsp tree node.

// We do not attempt to preserve the WINDING ORDER of portal polygons, since they are not renderable geometry.

// This may be a problem, depending on your implementation.

// 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

// -1 = The polygon was split

PointPlaneResult dxPortal::Split(dxPolygon* SplitMe, D3DXVECTOR4* pPlane, vector* Outputs)//, PORTAL* front, PORTAL* back)

{

int numVerts = SplitMe->m_Points.size();

int count = 0;

PointPlaneResult sideA, sideB, side;

D3DXVECTOR3 polysNormal, edge1, edge2, temp;

//VERTEX ptA, ptB, intersection, outpts[MaxVerts], inpts[MaxVerts];

D3DXVECTOR3 intersection;

/*

LOG("*** ATTEMPT TO SPLIT PORTAL POLYGON:");

for(int i=0; im_Points.size();i++)

{

LOG("Point #" m_Points.x m_Points.y m_Points.z);

}

LOG("Plane = " x y z w);

*/

////////////////////////////////////////////////////////////////////////////////

// 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;

// Classify the polgyon against the splitting plane

int frontcount = 0, backcount = 0, coplanarcount=0;

for (int loop = 0; loop {

D3DXVECTOR3* pPoint = &SplitMe->m_Points[loop];

if (dxBSPNode::ClassifyPointPlane(pPoint, pPlane) == COPLANAR)

coplanarcount++;

else if (dxBSPNode::ClassifyPointPlane(pPoint, pPlane) == FRONT)

frontcount++;

else if (dxBSPNode::ClassifyPointPlane(pPoint, pPlane) == BACK)

backcount++;

}

// Determine if the polygon is intersected by the plane

if (coplanarcount == numVerts)

{

// Polygon is totally coplanar - no intersection (caller can deal with it)

Outputs->push_back(SplitMe);

return COPLANAR;

}

if (frontcount+coplanarcount == numVerts)

{

// Polygon is on the front side of the plane - no intersection

Outputs->push_back(SplitMe);

return FRONT;

}

else if (backcount+coplanarcount == numVerts)

{

// Polygon is on the back side of the plane - no intersection

Outputs->push_back(SplitMe);

return BACK;

}

//LOG("frontcount="

////////////////////////////////////////////////////////////////////////////////

// try to bisect the input polygon

////////////////////////////////////////////////////////////////////////////////

dxPolygon* frontside = new dxPolygon(this);

dxPolygon* backside = new dxPolygon(this);

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);

//LOG("FIRST RESULT = "

// Track the last side we were working on

side = sideA;

// For each Point on the Polygon (except the last one)

for (int i = 0; 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);

float uIntersect;

switch(sideA)

{

case FRONT:

switch(sideB)

{

case FRONT:

//LOG("next front");

frontside->m_Points.push_back(SplitMe->m_Points);

break;

case BACK:

//LOG("front to back");

// find intersection

uIntersect = IntersectLinePlane(pPtA,pPtB,pPlane);

if(uIntersect=1.0f)

{

MessageBoxA(0,0,0,0);

exit(1);

}

intersection = ((*pPtA-*pPtB) * uIntersect)+(*pPtB);

//LOG("Intersection = " frontside->m_Points.push_back(intersection);

backside->m_Points.push_back(intersection);

backside->m_Points.push_back(SplitMe->m_Points);

side=BACK;

break;

case COPLANAR:

//LOG("front to coplanar");

frontside->m_Points.push_back(SplitMe->m_Points);

break;

}

break;

case BACK:

switch(sideB)

{

case FRONT:

//LOG("back to front");

// find intersection

uIntersect = IntersectLinePlane(pPtA,pPtB,pPlane);

if(uIntersect=1.0f)

{

MessageBoxA(0,0,0,0);

exit(1);

}

intersection = ((*pPtA-*pPtB) * uIntersect)+(*pPtB);

//LOG("Intersection = "

backside->m_Points.push_back(intersection);

frontside->m_Points.push_back(intersection);

frontside->m_Points.push_back(SplitMe->m_Points);

side=FRONT;

break;

case BACK:

//LOG("next back");

backside->m_Points.push_back(SplitMe->m_Points);

break;

case COPLANAR:

//LOG("back to coplanar");

backside->m_Points.push_back(SplitMe->m_Points);

break;

}

break;

case COPLANAR:

switch(sideB)

{

case FRONT:

//LOG("coplanar to front");

frontside->m_Points.push_back(SplitMe->m_Points);

side=FRONT;

break;

case BACK:

//LOG("coplanar to back");

backside->m_Points.push_back(SplitMe->m_Points);

side=BACK;

break;

case COPLANAR:

//LOG("next coplanar");

frontside->m_Points.push_back(SplitMe->m_Points);

backside->m_Points.push_back(SplitMe->m_Points);

break;

}

break;

}

// Let sideA (Current Point) = the Previous Point

pPtA = pPtB;

sideA = sideB;

}

// This shouldnt happen ??? It may be redundant

if ( frontside->m_Points.size()m_Points.size() {

// All the points fell into one side or the other - due to being coplanar?

for (int loop = 0; loop {

side = dxBSPNode::ClassifyPointPlane(&SplitMe->m_Points[loop], pPlane);

if(side!=COPLANAR)

{

delete frontside;

delete backside;

Outputs->push_back(SplitMe);

return side;

}

}

}

else

{

// Yay, we cracked a polygon.

//LOG("*********** POLYGON SPLIT *************");

//LOG("front = "m_Points.size()m_Points.size());

// Add the two polygons resulting from the splitting operation

Outputs->push_back(frontside);

Outputs->push_back(backside);

// return special result: "POLYGON WAS SPLIT"

return (PointPlaneResult) -1;

}

// If we get here, we have apparently got a coplanar input polygon that escaped the early test for it :|

MessageBoxA(0,"COPLANAR POLYGON WAS UNEXPECTED",0,0);

exit(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)

{

LOG("Intersecting Line and Plane");

LOG("Point1 = "xyz);

LOG("Point2 = "xyz);

LOG("Plane = "xyzw);

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.

}

Code has been added to tag each node with the bounds of its input set of triangles, in preparation for the 'portalizing' phase. These can be simple AABB's, ie, just find the maxima and minima of the vertices involved. For the root node, this box will be the world bounds And for leaf nodes, it means the bounds of the set of renderable faces in that subspace. The header has also been adjusted.

Note that this bounding volume does not take account of portals, and it is highly noteworthy that a subspace can consist MAINLY of portal surfaces !!

It's just the bounds of the actual renderable triangles in each subspace. We will probably have to expand some of these once we've found our portals.

[subheading]Organic Code Warning[/subheading]

The following sourcecode is subject to change without notice.

Expect that I will adjust and extend this code as I see fit.

Here you can find the Class Definitions for the BSPTree container class, and my two BSPNode classes.

There is a BSPNode class for internal nodes, and a specialized BSPLeaf node for the terminal nodes, since I will be extending this work well beyond the mere generating of a BSP Tree as outlined in previous posts.

I will not be posting a handful of classes mentioned within the sourcecode, for example, my Mesh class (dxMeshResource) - I'm sure you're clever enough to find or write some code to load mesh geometry.

This code will be omitted mainly because it is outside the scope of this project, W.R.T. mesh loading, all you need to know is that the vertices should be loaded into one vertex buffer, and the vertex indices into one index buffer in the TriangleList style - ie, as a flat array of three indices per triangle.

I will blab inanely about various aspects of the code as I roll it out, these headers will provide a common point of reference.

So without further ado, we can finally get our hands dirty

// The dxBSPTree class implements a BSP Tree, generated from an input 3D model.

#pragma once

// Result of classifying a point and a plane

enum PointPlaneResult

{

FRONT,

BACK,

COPLANAR

};

#include "dxBSPNode.h" // Structural Node class for BSP Trees

#include "dxPortal.h"

#include "dxMeshResource.h" // This is my mesh class, use your own

class dxBSPNode;

class dxPortal;

class Triangle;

class dxBSPTree

{

public:

// Constructor expects an initialized Mesh to be handed in

dxBSPTree(dxMeshResource* LoadedMesh): m_pRootNode(NULL), m_pMesh(LoadedMesh) {}

// Generate BSP Tree from Triangle Soup

void Generate_Tree();

// This list will contain the global list of planes (one per input triangle)

// from which we will select our Splitting Planes during tree construction

vector m_Planes;

// This list will contain the global list of portals which were constructed apon

// the non leaf nodes of the BSP Tree during its construction phase.

vector m_Portals;

// Object representing loaded mesh resource, managed outside this class

dxMeshResource* m_pMesh;

// Check if a plane has been previously selected as splitting plane

bool dxBSPTree::IsPlaneUsed(D3DXVECTOR4* pPlane);

// Determine which subspace encloses a given point

dxBSPLeafNode* Find_Containing_Leaf(D3DXVECTOR3* pvPoint);

private:

// Calculate surface normal and PlaneD for the given triangle

D3DXVECTOR4 Calculate_Plane(Triangle* t);

// Send the shattered portal fragment polygons down the tree

void FrogMarch_Portal_Polygons(dxBSPNode* pStartNode, dxPortal* portal);

// Root Node of BSP Tree

dxBSPNode* m_pRootNode;

};

int typedef TriangleIndex;

#ifndef __dxBSPNode_H_

#define __dxBSPNode_H_

// The dxBSPNode class represents the structural node for a BSP Tree (see dxBSPTree.h)

// Each node can have up to two Children.

//////////////////////////////////////////////////////////////////////////

#include

#include

#include

#include

#include "dxBSPTree.h"

#include "dxMeshResource.h"

#define PLANAR_HALF_EPSILON 0.0005f

//fwd refs

class dxBSPLeafNode;

class dxBSPTree;

class dxPortal;

class dxPolygon;

// Defines a renderable triangle during tree generation

class Triangle

{

public:

Triangle(int iOrig, int iA, int iB, int iC):iOriginalIndex(iOrig), ivA(iA),ivB(iB),ivC(iC) { }

~Triangle() {};

// Vertex Indices

int ivA, ivB, ivC;

// Index of original triangle (since this triangle may have been 'fragmented' during tree generation)

int iOriginalIndex;

D3DXVECTOR4 Plane;

};

using namespace std;

class dxBSPNode

{

public:

// This constructor is mainly used to create new nodes during tree generation.

// It can also be used to construct the root node, if we hand in pParent=NULL.

dxBSPNode(dxBSPTree* pTree, dxBSPNode* pParent, vector* pTriangles): m_pTree(pTree),m_pParent(pParent),m_pvTriangles(pTriangles),m_pFrontChild(0),m_pBackChild(0) { }

// recursive destructor

~dxBSPNode()

{

if(m_pFrontChild) delete m_pFrontChild;

if(m_pBackChild) delete m_pBackChild;

}

// Check if the node is a leaf (ie terminal node)

bool Is_Leaf()

{

if(m_pFrontChild || m_pBackChild) return true;

return false;

}

// Compare a point and a plane

static PointPlaneResult ClassifyPointPlane(D3DXVECTOR3* pPt, D3DXVECTOR4* pPlane);

// Classify a Triangle against a Plane

// This returns three enumerated values, packed into 6 bits

int ClassifyTrianglePlane(Triangle* pTriangle, D3DXVECTOR4* iPlane);

// Test for intersection of a Line and a Plane

// On success, returns the interpolation factor for the intersection (ie, 0.0 to 1.0 means intersection)

// On failure, returns a negative value

float IntersectLinePlane(D3DXVECTOR3* pPoint1, D3DXVECTOR3* pPoint2, D3DXVECTOR4* pPlane);

// recursive polygon partitioner

void Generate_Tree();

// Find the best partitioning plane from the planes of the node's input triangles

int Choose_Partitioning_Plane(int*, int*);

// Partition the triangles

void Split_Triangles(vector* FrontOutput, vector* BackOutput);

// After 'shattering' our large planar quads, we send resulting fragments thru the tree:

// We push a polygon to the top of the hill, and let it fall where it may.

void dxBSPNode::Quick_March(dxPolygon* poly);

// Accessors

D3DXVECTOR4* Get_Plane();

dxBSPNode* Get_Front_Child();

dxBSPNode* Get_Back_Child();

private:

// Calculate bounds of input triangles

void Calculate_Bounds();

// Create big fat quad on this node

void dxBSPNode::CreatePortal();

// Set the Parent of this node

void inline SetParent(dxBSPNode* pParent) { m_pParent = pParent; }

// Attach FRONT child

void inline Attach_Front_Child(dxBSPNode* pChild)

{

m_pFrontChild = pChild;

m_pFrontChild->SetParent(this);

}

// Attach BACK child

void inline Attach_Back_Child(dxBSPNode* pChild)

{

m_pBackChild = pChild;

m_pBackChild->SetParent(this);

}

protected:

dxBSPNode* m_pFrontChild;

dxBSPNode* m_pBackChild;

dxBSPNode* m_pParent;

private:

// this list will contain the input list of triangles when a node is created during tree construction,

// and will contain the final list of triangles for leaf nodes (non-leaf nodes should have an empty list, yes?)

vector* m_pvTriangles;

D3DXVECTOR4 m_Plane; // Plane selected to split children

dxBSPTree* m_pTree; // pointer to container of the root node

// AABB of node's input triangle list

struct BoxBounds

{

D3DXVECTOR3 vMin;

D3DXVECTOR3 vMax;

} m_Bounds;

};

#endif

class dxBSPLeafNode: public dxBSPNode

{

public:

dxBSPLeafNode(dxBSPTree* pTree, dxBSPNode* pParent, vector* pTriangles): dxBSPNode(pTree,pParent,pTriangles)

{

}

// Collects fragments from portals

vector m_PortalFragments;

private:

vector m_Portals;

};

#pragma once

using namespace std;

#include "dxBSPNode.h"

#include "dxPortal.h"

#include "dxBSPTree.h"

// Some fwd refs

class dxBSPLeafNode;

class dxPortal;

// The dxPolygon class represents a fragment of portal geometry.

// This is a circular list of 3D points which share a common plane,

// forming a closed, convex, planar polygon in 3-space.

class dxPolygon

{

public:

// Constructor expects ptr to construction portal,

// and will tag the new polygon with that portal's Plane data.

dxPolygon(dxPortal* pOwner);

~dxPolygon(){};

// Polygons can be constructed from 3 or more points

vector m_Points;

// Polygons are tagged with pointer to (or identity of) their 'construction portal'

dxPortal* m_pPortal;

// Polygons are tagged with a Plane, which is typically the same as that of their construction portal

// We flip the plane normal for 'cloned fragments' during 'fragment frogmarch phase',

// therefore each polygon carries its own plane data.

D3DXVECTOR4 m_Plane;

};

// The dxPortal class represents a portal which connects exactly two convex subspaces.

// Subspaces may contain multiple portals however, thus a connectivity graph may be formed.

// Portal geometry can be quite complex, depending on the world geometry involved.

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();

}

};

// Accessors

D3DXVECTOR4* GetPlane() { return &m_Plane;}

void SetPlane(D3DXVECTOR4& plane) { m_Plane = plane; }

// Attempt to bisect a (convex) polygon with a given splitting plane.

// Any resulting polygons are also convex.

// Inputs:

// dxPolygon* SplitMe = the polygon to be split

// pPlane = the splitting plane

// Outputs = output list of polygons (receives all resulting polygonal fragments)

// Returns: -1 (polygon was split) or enumerated point/plane result (reason polygon was not split)

// Remarks: Coplanar polygons are simply returned intact.

PointPlaneResult Split(dxPolygon* SplitMe, D3DXVECTOR4* pPlane, vector* Outputs);

// A portal has some unique Geometry:

vector m_Polygons;

private:

// Parametize the intersection of a Line Segment and a Plane.

// Returns -1.0f for failure, or returns a float value.

// Only a return value between 0.0f and 1.0f indicates a true intersection, in which case

// we can then interpolate with this value and the EndPoints to find the intersection point itself.

float IntersectLinePlane(D3DXVECTOR3* pPoint1, D3DXVECTOR3* pPoint2, D3DXVECTOR4* pPlane);

// A portal connects two subspaces:

dxBSPLeafNode* m_pFrontLeaf;

dxBSPLeafNode* m_pBackLeaf;

// A portal has a unique plane:

D3DXVECTOR4 m_Plane;

};

Take some time to look over the headers, as I will begin to spew forth sourcecode for these classes in chunks (any Peter Jackson fans?)

Please feel free to ask any questions, even at this early stage.

Just curious - why are files with a dot H extension not a permitted filetype for uploading here? What is the reasoning behind that?

I have regretfully omitted to mention something quite important, although I did allude to it.

How do we track which subspace an entity is in at any given moment - and what happens if an entity is poking partly through a portal?

We can handle this two ways, but personally, I think it's helpful to make the following declaration:

AN ENTITY'S CURRENT CELL IS DEFINED BY THE LOCATION OF ITS ORIGIN.

The origin of anything is an infinitely small point in space, occupying zero volume.

We can, as mentioned, utilize the BSP tree structure to quickly determine which subspace or cell contains a given point.

So we can say for certain which cell contains a given entity (say, the camera).

But what if the entity is partly sticking through one or more portals? Is the entity actually in more than one cell?

For the purposes of collision detection, visibility and etc, the answer is YES, we are going to have to take this entity into account when processing the neighboring cell.

But for the purpose of answering the query 'what cell am i in', the answer is NO, an entity is 'owned' by the cell that contains its origin.

The physical simulation of the game world can be partitioned by Cell, but NOT CLEANLY - we must support the notion of a 'dirty list' of entities that belong to other cells, and yet are partially invading the given cell, and so could potentially be involved in collisions. We need something that is not exactly 'simulation islands' but more something like 'simulation peninsulas' or maybe 'simulation islands with floating walkways' ( )

Even with this extra cost of maintaining the 'dirty lists', we're still several orders faster than if we only had one big simulation.

[subheading]Regular Joe says:[/subheading]

[font="Arial"]Now we've done all our pre-processing, it's time to talk about the runtime stuff - actually rendering with this cell and portal graph.

We know that the cells in our world graph are convex, so we can safely assume that all surface geometry in the same cell as the camera is 'potentially visible'.

It's hardly even worth testing them against the view frustum - we can just go ahead and draw these polygons. More technically challenging are the portals.

The cell our camera is in contains one or more portals to other cells - if none of them are currently visible, then our job is done.

However, if a portal is visible, then some of the surfaces of the cell it leads to are visible as well...

The portal rendering algorithm involves recursively visiting the cells which are connected to visible portals.

Basically, the idea is to refine our view frustum, traditionally done by clipping it to the shape of visible portals, essentially 'shattering' the view frustum into 'frustlets'.

We recurse each connected cell, with the clipped 'frustlet' as input frustum.

I have included some 'programmer art' conveying this concept, sorry if it's crap.

[subheading]Let's redefine the problem[/subheading]

Unless your portals are all regular rectangles, it can be expensive to clip the 3D geometry repeatedly against portal silhouettes.. However we can go some way to reduce the pain by avoiding all the clipping operations entirely.

Let's look at what we are really trying to do.

We are trying to find the extruded intersection of each portal with the current cell's 'input frustlet'.

This is the same as the projection of the portal's geometry from its current location, onto the view frustum's near and far planes.

This tapered extrusion is the 'frustlet' we are looking for - all we need is a cheap way of projecting the portal from its current position onto the near/far planes, and then find the planes of the tapered surfaces (cost of one crossproduct per portal edge).

So the only remaining problem seems to be how to project an arbitrary point inside the view frustum onto its near/far planes.

We already have a matrix that can transform a WorldSpace point into ScreenSpace, which effectively projects world points onto the Near frustum plane.

That's ALMOST what we want! We could probably find a way to use it. Instead, we'll directly use the stuff it contains.

Wouldn't it be nice if we could find some way of Scaling the portal vertices up and down for a given frustum 'depth' ?

We can borrow some stuff normally used for 'screen ray picking'.

First, we will calculate the 2D coefficients of the input point with respect to the camera view:

[/font][font="Arial"]
dx=tanf(FOV*0.5f)*(x/WIDTH_DIV_2-1.0f)/ASPECT;

dy=tanf(FOV*0.5f)*(1.0f-y/HEIGHT_DIV_2);

Note that the tangents here can be pre-calculated if your projection matrix is not changing (which would be the normal case).

Now we can easily find the projection of the input point on the near and far planes as:

nearPoint=D3DVECTOR(dx*NEAR,dy*NEAR,NEAR);

farPoint =D3DVECTOR(dx*FAR,dy*FAR,FAR);

Hmm, wait, that will give us the Point relative to a camera with identity transform - we still need to transform the point into camera view space, unless we're happy to do our calculations relative to the camera view

We can construct a geometric primitive from the portal vertices' near and far plane projections, and from them, we can find the 'unknown planes' formed between the near and far projections of the portal vertices... we now have created one 'frustlet', which extends from the near plane to the far plane, and is the shape of the portal.

I know, it still sounds like a lot of work! However I believe it will end up being much cheaper than the traditional 'subtractive solid geometry' method of slicing up the original frustum, and discarding the occluded portions.

[subheading]Rendering Algorithm:[/subheading]

So, given the current cell (which contains the camera) and the current view frustum as input 'frustlet A', for each visible portal, construct a 'frustlet B' from the input 'frustlet A' and the portal, then recurse the cell which is behind that portal, passing in 'frustlet B'.

Since all our 'frustlets' share the same near and far planes (ie, those of the camera view frustum), this recursion is automatically bounded by the view depth - it will stop when we get far enough away from the camera.

Now, in order to ensure correct drawing order for our polygons, we simply defer the rendering of the polygons until the recursion is 'returning' as follows:

-For each Portal in this cell

--If Portal is Visible, Calculate Frustlet and recurse adjacent cell

-EndFor

-Draw polygons in this cell

-Return from recursion

This ensures that polygons are drawn on the 'way back', ie deepest recursed cells are drawn first, and the current cell is drawn last.

As mentioned, there will be some MINOR overdraw, which could be virtually eliminated if we add the step of testing polygons against the frustlets before drawing them, however I see this as prohibitively expensive (we shouldn't be culling at the polygon level on the cpu), and find the amount of expected overdraw acceptable.

[/font]

[subheading]AVOID ILLEGAL POLYGONS[/subheading]

Just some quick notes regarding the 'splitting' of geometry during BSP tree generation...

Traditionally, BSP Tree Generator algorithms will actually physically split polygons into two new polygons, placing one in each child subspace.

The problem with this is that it creates a large number of extra polygons and their associated costs, and the real danger of creating 'aberrations' - deformed, illegal polygons whose geometry might not be a problem for rendering but might certainly be problematic for things like collision responses.

We can easily avoid this: instead of directly passing polygons down the BSP tree during its construction, we will instead pass references to the original input set of polygons.

Now when we need to 'split' a polygon, we just duplicate the polygon's reference and send one down each side of the tree.

We'll end up with sets of polygon references in the leaf nodes instead of actual polygons.

There will be some duplication of references to polygons that are 'shared' by multiple subspaces, however these can easily be eradicated by collecting only unique references during the rendering step... or we can ignore them, and have some minor overdraw when those polygons are visible through onscreen portals.

Either way, the benefits of avoiding splitting polygons during BSP tree construction outweigh the costs and problems associated with 'perfect partitioning'.

We don't care if polygons overlap subspaces, only that we can identify those subspaces accurately.

[subheading]PORTALIZE ME[/subheading]

Now, the next exciting episode.

How do we automatically discover the portals which connect our subspaces?

[subheading]BIG FAT QUADS[/subheading]

We begin by observing the boundingbox of the original input set of polygons for the entire 'world'.

In fact, it would serve us well to calculate the boundingbox of the input set of polygons at each Node during tree construction.

Every non-leaf Node in the tree has recorded a splitting plane during the tree construction.

Our goal is to construct apon the splitting plane a rectangular polygon (eg a Quad, or two triangles) whose extents are those of the node's boundingbox.

So for the root node, we want to make a giant rectangle whose Surface Normal matches the splitting plane normal, and whose Vertices all exist apon the surface of the boundingbox (ie, the intersection of the plane and the box).

We will tag each of these special 'Portal polygons' with the ID of the node whose plane they were constructed apon.

This ID will be retained by any 'child fragments' resulting from the next step, where we 'smash' these 'giant windows', we will later use it to discover mating sides of each Portal.

[subheading]SHARDS OF PORTAL[/subheading]

Our next step is to 'Shatter' each of our Portal polygons: we attempt to Split each portal polygon with every splitting plane in the tree, with the exception of its own construction plane, keeping ALL the resulting fragments (both 'front' and 'back' of the splitting plane), tagging such fragments with the inherited ID of the input portal polygon fragment. We then pass each resulting fragment to the Root Node of the BSP tree, allowing it to 'fall' through the tree, classifying it against the splitting plane of each non leaf node, until it lands in a leaf node.

When a fragment reaches its own construction node, we should clone the ENTIRE fragment of the portal and send it down BOTH sides of the tree.

The reason is that a Portal has two sides - it lives in both of the subspaces that it connects, as we shall see momentarily.

Once we've finished doing that, we should have a whole bunch of portal polygon fragments in each of our leaf nodes, as well as the regular polygons from earlier.

NOTE: When passing Fragments down the tree, we should never need to Split them..

The reason is that these fragments have already been split against every single splitting plane in the BSP tree !!!

If we find that we need to Split them while passing them down the tree to the leaf nodes, we must have screwed up the Shattering step.

[subheading]CLIP ME AROUND THE EDGES[/subheading]

The next step is to Clip the Portal fragments against the planes of the regular polygons in the leaf nodes.

For each leaf node, clip the portal fragments in that leaf against the planes of the regular polygons in that same leaf.... literally we will split the portal fragment polygon against each clipping plane.

We want to keep the fragments that are 'inside the subspace' and throw away any parts that are behind any of the clipping planes.

We have now cut our portals into their exact shapes, any fragments which survived the clipping process are parts of our portals.

[subheading]MIRROR MIRROR - DISCOVERING CONNECTIVITY[/subheading]

Each fragment was tagged with the ID of its construction node, which contains its construction plane.

And each fragment has a mate in some other Leaf which bears the same ID.

Our goal is to match them - for each leaf, find all the portal fragments with the same ID and group them. Then for each group, find the Leaf containing a group with the same matching ID. We have now discovered the shape of each Portal and which two subspaces it connects. Note that it is perfectly legal for multiple coplanar Portals to connect the same two subspaces: for example, imagine a wall separating two rooms, with several windows and a doorway connecting them

Final steps could include welding the portal fragments into a single polygon (although its convexity cannot be guaranteed), and eliminating the second copy of the geometry for each portal. This step will involve finding and eliminating shared Edges in the portal fragment groups of each Leaf, and will lead to the discovery the individual shapes of multiple coplanar portals (ie unconnected portal fragment groups of the same construction id, as mentioned earlier).

Anyway, now we have found all the subspaces, and the portals that connect them, and the shapes of those portals.

We can now construct a Graph of connections between the subspaces, ie, a Cell and Portal Graph.

We're ready to write our structures to disk.

We no longer require the BSP Tree - just its Leaf nodes, or rather, the data they contain, since we can now track entities movements between subspaces via portals.

However its arguably useful to retain the BSP Tree for one simple reason: we can find out what subspace a given 3D point is in by simply passing it down the tree until it lands in a leaf node.... and finding out what subspace something began life in could be handy.

This wraps up the theory of Portalizing in a Polygon Soup, however there is much remaining discussion regarding correct utilization of the new cell and portal graph structure in terms of efficient rendering (to portal render or not to portal render), physical simulation (collision detection) and how to handle entities that are intersected by portals.

Relax.

We are not going to use BSP in the traditional way (ie, for implementing painters algorithm during rendering).

Rather we will use BSP as an intermediate tool for generating our cell and portal graph.

We are interested in discovering a set of convex subspaces and the 'holes' that connect them - BSP is going to get us more than half way to our goal.

[subheading]Discovering Convex Subspaces[/subheading]

The first stage then is to generate a BSP tree from an input set of triangles.

And to be quite specific, it will be a 'leafy' tree, with all the polygons located in leaf nodes, and all other nodes recording a splitting plane (this will make more sense as we progress).

While building our BSP tree, it is desirable to attempt to create a well-balanced tree of minimal depth... this brings us to our first algorithm: given an input set of triangles, discover a triangle whose 3D Plane 'best' partitions the input triangles.

By 'best', we mean that Plane which produces the most even number of triangles in each of the resulting subsets, while simultaneously 'splitting' the least other triangles.

These two goals are mutually exclusive, this algorithm implements a simple heuristic which attempts to achieve our mutual goals.

The process of building the BSP tree is recursive - given the original input set of triangles, partition it into two subsets, and repeat.

When should we stop?

For our purposes, we should not stop until a triangle subset contains NO candidate splitting planes.

When this happens, we have discovered a CONVEX SUBSPACE whose CLOSED HULL is defined by the set of planes of the triangles in this subset (and the planes of its ancestor nodes). Furthermore, we know that the holes or portals which connect this subspace to other subspaces must exist on existing splitting planes, defined at non-leaf nodes in our tree.

At this stage, we have a complete leafy BSP tree describing our world... its leaf nodes represent convex subspaces or 'rooms' in our world, our next step is to discover the portals or 'holes' which connect the subspaces together.