Notes to myself (and anyone else who cares) regarding the process of extracting connectivity information (portals) from a Leafy BSPTree..

So - we've created a Leafy BSPTree, which contains convex clusters of Faces in its Leaves, and no Faces are in non-leaf nodes..

Step 1: for each non-leaf node, create a large, rectangular polygon which rests on the node's splitting plane.. we'll call it a SuperPlane. I'm going to use two Triangles for this, so I can take advantage of the existing and PROVEN triangle-splitting functionality we used to create the BSPTree..

Step 2: for each SuperPlane, cut the all the triangles it contains using "the Planes from all OTHER nodes in the BSPTree". Each node now contains a list of "potential portal faces". It's like a crazy rectangular pizza.

Step 3: Push the "potential faces" down the BSPTree until they land in a Leaf.
IMPORTANT: if we ever find the Face is coplanar with a Plane, send a reference of it down BOTH sides. Note that this will happen ALWAYS at the node of origin,  and in theory, should not happen ever again (unless we re-used an existing plane as a splittingplane, which would mean we made a mistake when we created our BSPTree)

Step 4: each Leaf now contains a bunch of "potential portal facereferences" sourced from various parent nodes.
For each of these FaceRefs, search all OTHER LEAVES for a duplicate of that faceref.. if we find none, destroy the faceref, because we WANT to find two of them.
If we find two of them, note which two Leaves they appear in, and then find the Parent nodes of each of those Leaves... now cut the FaceRef against all the geometric Faces owned by the Parent Node's two leaves ("against all faces in both leaves planes").. any fragments of the "potential portals" that lie BEHIND any of the leafpolygons are discarded.. coplanars are ignored.. any fragments that survive this process ARE PORTALS. Mark each set of surviving portal fragments with an Index or Pointer to the OTHER LEAF.. since we're really talking about two sides of a doorway leading between two Leafs.

Can anyone help to optimize this algorithm?
I had one idea early on.. note that this algorithm totally ignores coplanar faces.
When we first create our rectangular polygon, we know that any Faces in that node's leaves which are coplanar with the cutting plane are WALLS (not a hole).
If we can come up with an algo to cut coplanar polygons, we can use these coplanar geometric faces to eliminate some of the "potential portal faces" BEFORE we shove them down into the Leaves..

Wow, confused? Enlightened? Don't care?
Posted on 2006-03-06 02:24:40 by Homer
I started out by creating a new OA32 Object called (oddly enough) "Portal".
The Portal object is a container for a DwordCollection of Triangle faces, and supports a VertexBuffer (implemented as a DataCollection of Vec3's).
I'm keeping the Portal vertices separate from the main geometric vertexbuffer during the discovery of Portals, for two reasons.
#1 - I am expecting a LOT of vertices to be actually redundant (ie, to be created, and then later deleted again).
#2 - Portals are not textured, so the size (and thus the FVF) of these vertices differs from that of our geometric vertices.
After all the splitting I'll feed the surviving vertices into the main vertexbuffer and increase their size to match the FVF being used.

So, now I have three new Objects which are unique to this project:
BSPTree (contains code to import geometry from xfile etc)
BSPNode (contains most of the tree generator code, as its recursive)
Portal (contains bugger all code, which might soon change)

I've added code to BSPNode such that after we've finished sorting the input faces of a non-leaf BSPNode against its Plane, a Portal object is created and filled with two triangles comprising a large rectangle which lays on that Plane.
This occurs for every non-leaf Node during tree generation, ie, for all the BSPNodes that actually HAVE a splitting plane (leaves don't have one).
I stored each new Portal in a global Collection, and also locally in the BSPNode that shares its Plane.

So, we've got a bunch of "large portals" strewn throughout the BSPTree, and also kept in a linear list, and all that done DURING the tree generation.

The next stage requires that the BSPTree is completed, because it involves splitting each of our "large portals" using "every Plane except itself" as the Cutting Plane (therefore we need to have decided on all our Planes).

So, this is where I'm currently up to.
I've done everything above up to completing the tree generation : all the faces in convex clusters in the leaves of the tree, planes and large portals at all the other nodes.

I've been staring at the algorithm by Nathan Whitaker quite a lot, and something occurred to me, but I'm going to have to describe his procedure to explain what I have in mind..
Posted on 2006-03-07 01:21:24 by Homer

Nathan says basically that we should mark each large portal with the splitplane it lies on (a pointer to the BSPNode makes more sense to me) and pass the large portals down the BSPTree until they reach a LeafNode.
He actually suggests we mark each PortalPolygon, but I was thinking to keep the Polygons together as coplanar sets (Portals).
I guess Nathan's idea is better than the alternative, which involves multiple Lists and is messy..
This means I'll have to change the way I've designed my Portal object.

Anyway, Nathan goes on to say that as we filter the Portal fragments down the BSPTree to the Leaves, if we ever find a fragment to be Coplanar with a CuttingPlane (which they ALL are, when they start out) then we should send "a reference to that Polygon down BOTH sides of the tree", which is important, because after all the Portal fragments have been filtered down into the Leaves, we need to search for each Polygon's mate in all the other Leaves.
If we can find a PortalPoly reference in two different Leaves, then we've discovered a Potential Portal, and if we CANNOT find it in two different leaves, then its NOT A PORTAL so kill it.
If we find a Potential Portal, we clip its geometry against all the faces in both of the Leaves in which it appears, and whatever remains is an Actual Portal.
Each leaf now needs to contain a Pointer to the the Actual Portal, which in turn contains Pointers to both of the Leaves it was found in.
So, an Actual Portal is a Portal (as I originally described it) with two more Pointers ;)

Anyway, back to my brilliant idea.
It occurs to me that since we sent ALL the faces down into the Leaves when we originally made the Tree, that it is redundant to "split each large portal against all Other Planes", we can ignore that step. Here's why.
If we just send the "large portals" down the Tree, once they get to the Leaves, they're going to be cut against the Planes of any Faces in those Leaves, and the Planes in the BSPNodes are just a SUBSET of the Planes of All Faces ;)
It occurs to me that the only Faces that a Portal needs to be cut with are those which bound the Leaf it exists in and those of the Faces in that Leaf.
Perhaps thats nonsense, anyone care to comment?
Posted on 2006-03-07 02:04:15 by Homer
OK, let's describe the current problem.

I have a Tree containing N nonleaf nodes, and each nonleaf node contains a Portal object... these Portal objects each contain two triangles at this point.
I need to cut each Portal's triangles up using N planes.
Now each nonleaf node contains a Portal which is a crazy rectangular pizza of N triangles.
In order to reduce complexity of the program, I extend my Face structure to include a Tag identifying what BSPNode (and thus what Plane) it originated from.
I use these ExtendedFaces to describe PortalPolygons.
Back to the Pizza..
I send each rectangular Pizza down the Tree, piece by piece, and catch all the pieces in the LeafNodes in a DwordCollection.
Now for each Leaf, I can discover the Portals by looking for leafs which contain matching pieces of pizza .. ie, the same triangle from the same plane.. ie, two REFS to the SAME TRIANGLE.
When I send my Triangles down the Tree, I can use the same method I did when I created the Tree, that is, to use FaceRefs stored in DwordCollections, and destroying the DwordCollection behind me (without destroying the payload objects) and I'm PRETTY sure I'm making no sense to anyone but myself at this point... after all, DwordCollections are not a standard OA32 object.
They're a Collection which doesn't destroy the object instances it carries.
More specifically, they're a collection of arbitrary dword values.
I find them useful for sorting purposes.
If I keep objects temporarily in these while sorting them from list to list, I can destroy redundant lists safely (container is destroyed, the contents are not), I just have to make sure I clean up the objects myself if it's time to die.

Posted on 2006-03-07 06:22:27 by Homer

I've completed the next stage of "portal discovery"...
Recapping the rather cryptic postings I made previously, I have done the following:
1) Import triangle soup from XFile
2) Build Leafy BSPTree (convex clusters of faces in Leaves, SplittingPlanes in all other Nodes), and while doing so, calculate the Bounds of the input geometry for each Node.
3) Create a large flat rectangle at each non-leaf node which rests on the node's SplittingPlane and extends to the Bounds of the node we precalculated. (I used two Triangles to describe the rectangle, so I could recycle some existing code in the next step)
4) Cut each "large rectangle" using "all the other splitting planes". Mark each resulting "fragment" with the id of (or ptr to) the BSPNode it was constructed apon.

That last step can take extremely long time, much longer than the time taken to build the entire BSPTree.. I'm crying.. It makes the entire algorithm painfully slow to implement, and I can see that there is a way to speed this stage up, which I described at the end of the first posting I made in this thread.. we can eliminate a lot of Fragments early by performing some Clipping against any Faces which were found to be COPLANAR.

The next stage which I haven't done yet:
5) Send all the Fragments down the Tree, and collect them in the LeafNodes.. if a Fragment is coplanar with any splitting plane, send it down BOTH sides.

The last step is:
6) Search for instances of a Fragment which appear in two different Leaves. This is an ACTUAL PORTAL as opposed to a "potential portal".
Whatever is not an actual portal, kill it.. we only want the real ones.
Mark each pair of real portals with "a pointer to its mating leaf".

That's all !!
Posted on 2006-03-10 00:00:09 by Homer
I think I'm applying the algo incorrectly.
Here's how I think I should be doing it:

We've created the large flat rectangles (our 'initialized Potential Portals') at each CuttingPlane (each non-leaf Node) of the BSPTree.
We should now 'frogmarch' the Portal geometry down the Tree into the Leaves, cutting it against each cutting plane exactly as we did when we constructed the BSPTree.
Starting at the RootNode, we cut the largerectangle against the Plane, and we output the distributed triangles into the child nodes. Then we recurse each child, and thus the entire Tree.
Once this process is completed, all the PotentialPortal geometry is stored in the Leaves, ready to be clipped against the Faces in that Leaf.




Posted on 2006-03-10 17:25:13 by Homer
I've implemented the algorithm as described in the previous post, and it works, and it's a crapload faster.
I had to change the way I handle the destruction of "faces made redundant through splitting" in order to implement "the duplication of references to coplanar faces".. basically a face can't be destroyed until all Nodes have been processed, in case there's more than one Reference to it.

I'm ready for the final stage of Portal discovery - the search for Mating References in Other Leaves.
This will be very easy since in my implementation, a 'Mate' face is simply a duplicate Pointer, I just have to compare a bunch of Pointers.

To find the "true portals", we do the following..

For each LeafNode:
  For each pFace in the Node's Portal object:
    If the Face has NOT been marked as "a true portal",
      Search all Other Leaves for a copy of pFace
      If Found,
        Mark each Face with a ptr to "the other Leaf"
        Mark each Face as being "a true portal"
      Else
        Destroy pFace
      EndIf
    EndIf
Posted on 2006-03-10 19:51:03 by Homer
Well, today I implemented the function to "find mating portal faces" - and bugger me, it worked the first time - which is REALLY suprising because I FORGOT TO CLIP THE PORTALFACES TO THE FACES IN THE SAME LEAF.

I guess I'm not finding ALL the portals at the moment, but it is finding a whole bunch.

Anyways, here's the function I threw together, and the structure being used for PortalFaces.
Note that I made a linear list of the LeafNodes during the building of the Tree, and now I'm simply iterating each item in the list.
Remember, a real Portal face connects two Leaves.
Its geometry exists in both Leaves.
I decided to store a pair of ptrs in each PortalFace which indicate the two Leaves that the Portal is connecting...



PortalFace struct
pVertex1 dd ?
pVertex2 dd ?
pVertex3 dd ?
pOwnerNode dd ? ;ptr to the BSPNode whose Plane the PortalFace was created apon
pLeafA dd ? ;ptr to LeafNode
pLeafB dd ? ;ptr to LeafNode
PortalFace ends

Method BSPTree.FindActualPortals, uses esi
LOCAL numLeaves
LOCAL numFaces,numOtherFaces
LOCAL pLeafNode,pOtherLeafNode
LOCAL pFace,pFaces,pOtherFace,pOtherFaces

SetObject esi

;For each LeafNode:
mov eax,pLeafNodes
m2m numLeaves,.DwordCollection.dCount
xor ecx,ecx
.while ecx<numLeaves
push ecx
;(Obtain ptr to LeafNode)
mov pLeafNode,$OCall (pLeafNodes::DwordCollection.ItemAt,ecx)
;For each PortalFace in the Node's Portal Object:
mov eax,.BSPNode.pPortals
mov ebx,.Portal.pFaces
mov pFaces,ebx
m2m numFaces,.DwordCollection.dCount
xor ecx,ecx
.while ecx<numFaces
push ecx
;(Obtain ptr to PortalFace)
mov pFace,$OCall (pFaces::DwordCollection.ItemAt,ecx)
;If this PortalFace has NOT been marked as a "true portal"
;(we skip KNOWN portals)
.if .PortalFace.pLeafA==NULL
;Search "all OTHER Leaves" for this pointer..
xor ecx,ecx
.while ecx<numLeaves
push ecx
mov pOtherLeafNode,$OCall (pLeafNodes::DwordCollection.ItemAt,ecx)
.if eax!=pLeafNode ;Don't search the Same Leaf
mov eax,.BSPNode.pPortals
mov ebx,.Portal.pFaces
mov pOtherFaces,ebx
m2m numOtherFaces,.DwordCollection.dCount
xor ecx,ecx
.while ecx<numOtherFaces
push ecx
OCall pOtherFaces::DwordCollection.ItemAt,ecx
.if eax==pFace
;We have a MATCH !!!
DbgWarning "TRUE PORTAL FOUND"
;Mark the PortalFace with the ptrs
;to the TWO leaves it connects
m2m .PortalFace.pLeafA, pLeafNode
m2m .PortalFace.pLeafB, pOtherLeafNode
;Correct the Stack so we can exit early
pop eax
pop eax
jmp @F

.endif
pop ecx
inc ecx
.endw
.endif
;Search Other Leaves
pop ecx
inc ecx
.endw
;The search Failed, so pFace ain't a Portal
OCall pFacesToKill::DwordCollection.Insert, pFace
.endif
@@: ;Check next Face in current Leaf
pop ecx
inc ecx
.endw
;Check next Leaf
pop ecx
inc ecx
.endw

MethodEnd



Posted on 2006-03-11 09:30:02 by Homer
I have a suggestion that would speed up portal searching exponentially, err logarithmically.

Instead of using a List why not a red/black linked tree or a sorted list.
By doing this your search time for each ptr to ptr comparison would be log(n) because you would be using a binary search instead of a brute force iterative one.

Unless you have a red/black binary search tree implementation it would probably be easier to just run the list through a radix sort (4n) or a quicksort (n log(n)).
Posted on 2006-03-11 21:30:52 by r22
I dunno if theres ever enough leafnodes to warrant it, even when we're dealing with relatively large worlds.

The geometry files I've been using to test this baby are 'tiger.x' and 'brokentiny.x' which are roughly 600 and 8000 triangles respectively.
If anything needs to be optimized, its in the tree generator itself.
600 triangles are processed in about a minute on a 500mhz machine, and 8000 in about 5 minutes.. I'm yet to throw anything more substantial at it.

Still, I'm listening, and appreciate the input.

Let me complete the project by implementing the "clipping to leaf faces" which I omitted, and then I'll post the whole thing, and I will then invite you to tear it apart (philosophically speaking) in search of 'the most optimal implementation'.

Posted on 2006-03-11 23:55:16 by Homer
Here's a beta copy of the Binary.

Guys, please test this puppy and let me know your thoughts.
Rest assured that I intend to post the entire sourcecode, I just want to hear some feedback so I can make last-minute changes BEFORE I post it.
After that, I'll be looking at optimizing the existing codebase before implementing ANYTHING further (there's a lot of stuff I have in mind, such as a radiosity lightmap generator, and a CSG editor which performs boolean operations on objects encoded as BSPTrees).
Attachments:
Posted on 2006-03-14 03:20:14 by Homer
Hi Homer
I get sereral times the error message "Object ID = 23, Error Code = 201" when I import Tiger.x ...

Biterider
Posted on 2006-03-14 03:55:05 by Biterider
When you IMPORT? Can anyone verify this?

Here's what I get when I import Tiger.x..


XFile Loaded - Optimizing
XFile Optimized - Importing
Materials and textures Imported
Mesh Variables Noted
.dwFVF = 258t
.dwNumBytesPerVertex = 20t
.dwNumVertices = 303t
.dwNumFaces = 602t
eax = 1t, NumTexCoordSets in VertexFormat
eax = 1t, #TextureCoord Sets in each Vertex
Flexible Vertex Format Cracked
Calculated World Bounds
Vertices Imported
Faces Imported
yayyy


I've made a number of changes to the Import function, however I don't get any such problems (iirc, 23 is Collection and 201 is "index oob" - generally the result of a failed Insert due to a Collection being initialized with insufficient slack space)

I'm really interested since this does not occur here.. ever.
Posted on 2006-03-14 04:18:40 by Homer
That's the output of the 3DEDITOR window

XFile Loaded - Optimizing
XFile Optimized - Importing
Materials and textures Imported
Mesh Variables Noted
.dwFVF = 258t
.dwNumBytesPerVertex = 20t
.dwNumVertices = 303t
.dwNumFaces = 602t
eax = 1t, NumTexCoordSets in VertexFormat
eax = 1t, #TextureCoord Sets in each Vertex
Flexible Vertex Format Cracked
Calculated World Bounds
Vertices Imported
Faces Imported
yayyy


If it gives you a hint, the error 201 occurs more than 200 times.
Posted on 2006-03-14 04:37:53 by Biterider
I modified the zip posted earlier to include a MessageBox after impoting and before I populate a listview control. Please try this one.
The result will tell me where to look for this bug, which oddly, I can't seem to trigger on this machine.
Note that I've got a fair bit of error checking already, it's got me interested..
Posted on 2006-03-14 06:45:22 by Homer
AHAH !! Found the bug..

The bug was caused by some code which "walks the attributetable in parallel" while processing the Faces in a linear loop.. this is required for importing Meshes with multiple Materials (or multiple Textures), so that each Face can be marked with the Material it uses (so that I can lump all the Faces together for BSP processing instead of dealing with N subsets).

The bug caused the parallel walker to stray beyond the bounds of the attributetable into "uninitialized memoryville", and subsequently was returning random junk for the current AttributeID .. which was then used as an Index into the Materials collection, which specifically caused the 201 error.

Fixed :)


Attachments:
Posted on 2006-03-14 09:52:17 by Homer

This bug had eluded me because of the arbitrary content of the memory being illegally accessed.. and because since I have not yet implemented any code to render, I had been disregarding the imported Materials.

That being said, I'm looking forward to some feedback.
Provided I don't hear any more horror stories, I'll post the source.
Posted on 2006-03-15 01:19:47 by Homer
There were no errors when loading tiger.x

XFile Loaded - Optimizing
XFile Optimized - Importing
Mesh Variables Noted
.dwFVF = 258t
.dwNumBytesPerVertex = 20t
.dwNumVertices = 303t
.dwNumFaces = 602t
eax = 0t, Result of GetAttributeTable
.D3DXATTRIBUTERANGE.AttribId = 0t
.D3DXATTRIBUTERANGE.FaceStart = 0t
.D3DXATTRIBUTERANGE.FaceCount = 602t
.D3DXATTRIBUTERANGE.VertexStart = 0t
.D3DXATTRIBUTERANGE.VertexCount = 303t
Materials and textures Imported
eax = 1t, NumTexCoordSets in VertexFormat
eax = 1t, #TextureCoord Sets in each Vertex
Flexible Vertex Format Cracked
Calculated World Bounds
Vertices Imported
AttrID = 0t, Initial AttributeID
Faces Imported
yayyy


On Manual Edit, only the Vertices table is filled. I tested 3DEditor.exe with ~50 textured .x files and several .x files without textures  (files from an arbitrary 3D game). Half of the .x files were binary, the other - text.
Only one file failed to load, but it turned out its texture files were missing.
Posted on 2006-03-15 12:48:01 by Ultrano
Thanks for the feedback - yeah, I haven't finished the code for the component editor by a long shot, but I was interested to know if it shows the vertex format correctly for various FVFs (the number of columns should change depending on the FVF of the mesh).

Also, do the values make sense (are Normals always between 0.0 and 1.0, are the UVs ever negatively signed (flipped)) ?

Does the BSPGenerator appear to be working ok? Are "Actual Portals" being discovered at the end of the BSP processing? (the funky colours are just an indicator of what the program is doing)

Finally, do the vertices created during the BSPGen processing have sane values? (refresh the listview by changing the component type, it will be rebuilt - I might change this..)

One thing for sure, it leaks like a sieve if you load more than once per execution.. not all resources are deallocated correctly. I'll do that next.
I've been preoccupied with getting the BSP stuff finished because I intend to use it as the basis of a realtime CSG editor (solid modeller)..
The idea is to define a handful of "brushes" (convex primitives), build a BSPTree for each, and then allow the user to combine multiple brushes using boolean operators (add, subtract, intersect), creating more complex brushes, with their complete 3d model as the most complex brush.
Note this indirectly allows a careful user of such an editor the ability to define the cuttingplanes of their BSP solid-modelled complex object (heh) because they are really building a revised BSPTree with each operation they perform..
Posted on 2006-03-16 00:43:18 by Homer
3DEditor (the 2nd update) always exits when I press "Generate BSP" (that's why I thought it wasn't implemented). Before exiting, it displays "Generating BSPTree" in the main dbg window, and then "WEIRDNESS : NOTHING TO SORT" in BSPNode.Sort. The same stuff happens with tiger.x.
Most files don't have normals specified. Wherever they're present, they're ok: for instance (-1,0,0), (1,0,0),(-0.49,-0.74,-0.44),(0,-0.97,0.2)

UVs are regular - from 0.0 to 1.0 .
Posted on 2006-03-17 04:50:51 by Ultrano