Found a major bug in the "triangle splitter" part of the BSP Tree generator code.. fixed that.
Modified the "triangle partitioner" part of the BSP Tree generator code so that it can operate apon "portal fragments" as well as regular "geometric" triangles (aka Faces).

I make very little distinction between these two kinds of triangles, with the HUGE exception that their Vertices are stored in completely different ways .. Geometric triangles have their vertices stored in a D3D_VertexBuffer, and these vertices can be shared by several triangles. Fragment triangles have their vertices stored as Vec3 structs in a DataCollection (they dont need anything more than Position at the moment), and every triangle uses its own vertices, they are not shared across triangles, they are duplicated in the collection if necessary. The reason for this is that many triangles and vertices generated during Portal Discovery will be later found to be redundant... we need to be able to safely unload triangles and their vertices without affecting other triangles.

Posted on 2009-05-07 22:07:44 by Homer
Added code to calculate a Vertex Normal and up to eight sets of Texture Coords for the new vertices created during the BSP Tree generation. The vertices in my test model also contain other junk such as Binormal and Tangent components - they're for bumpmapping, which I won't be supporting (immediately), so I'm gonna ignore them (for now)... just need to check the settings in my .X file exporter script (maya).

Tonight I'll be implementing code to perform the final stages of Portal Discovery:
-clip fragments against the geometric triangles in the two leaves that they touch.
-regroup fragments according to the destination leaf to which they lead.

The final Portal structure will contain a list of fragments which all lead to the same leaf (ie the fragments are all pieces of the same 'doorway').
The final Cell structure will contain a list of Portals and a list of geometric faces.
The final Cell and Portal Network is implied by our Cell and Portal data - constructing it is trivial.

I modified the Triangle Partitioner further to support Front-Clipping operations (where we wish to keep geometry in front, and discard geometry behind, of a set of test planes).
This is the next operation that is required to be performed apon the Portal Fragments.

Posted on 2009-05-08 00:27:54 by Homer
Implemented code to generate a set of output Portals, where:
A - Each portal contains a list of coplanar fragments
B - Each portal connects exactly two Leaf nodes

Also implemented code to Clip each resulting Portal against the Faces in the two Leaf nodes connected by that Portal.
This final operation is intended to coerce the shape of the portals to conform to that of the 'holes between leaves' - ie, to trim them down to their exact final shape.

Also implemented code to create, for each Leaf, a list of reference pointers to the Portals which connect that Leaf to other leaves. Thus, if we know what Leaf we are in, we have a short list of possible exits.

Next is to implement some quick code to render the Portal surfaces over the original mesh for a visual sanity check, then to start thinking about the final Cell structure and Custom File Format to save/load all the data.
One of the biggest decisions will be whether we wish to retain the BSP Tree data, or just the data in the Leaf nodes. We can use the BSP Tree for at least one useful thing - to determine which Leaf contains a given 3D point.
When we introduce 3D entities into our World, we need to determine which Leaf they are in.
After that, we can TRACK which Leaf they are in, so if we can find an alternative and reasonably efficient way to determine the initial leaf our entity is in, then we can discard the BSP Tree.

Posted on 2009-05-09 00:47:45 by Homer
Extended the Portal Vertices from a simple Vec3 to a Vec4.
I'm storing Position in the XYZ fields, and Color in the W field.
This is equivalent to the "D3DFVF_XYZ or D3DFVF_DIFFUSE" vertex format.
It will allow me to implement some very temporary and very cheap and nasty code to draw the Portal triangles using DrawPrimitiveUP calls.
Of course normally, we don't render these triangles, they are meant to be invisible :D
I only wish to draw them so that I can SEE them and verify that the results match my expectations, to prove that the implementation is flawless (yeah right, I'll believe it when I see it).

Uh oh, the Portal vertices have crazy values, I have a bug to eradicate.
Posted on 2009-05-10 23:49:19 by Homer
Spent some time adding debug statements here and there to isolate the problems.
Turned out to be a bug in method which generates the large planar rectangles that represent a "new" portal.
Implemented cheesy Render code to draw all portal fragments.
Still not getting the results I expected, but at least I am getting results on the screen now.
The current version of the code finds two Leaf nodes in my small test mesh, and one Portal linking them, constructed from Six Fragments.
However I'm not 100% sure that these triangles are correct, they look a bit weird to me.
Hey, at least I can see them :)
Posted on 2009-05-13 07:53:28 by Homer
Just did a little sanity checking of the triangles that I said didnt look right.
They are right.
There's just more of them than we really need.
We have one portal, made from six triangles.
But we can express the same portal geometry with less fragments (four in this case)
It is certainly worth thinking about retesselating the fragments in each portal at the very end, if not supporting the splitting of 2D (coplanar 3D) polygons of arbitrary complexity rather than only lists of triangles.

Anyway, I did find another "bug" - the portals should be pre-split against all the possible planes (except coplane) ... not just against the planes we used to construct the tree... Not sure if this was a misinterpretation on my part or whether Alan Baylis and Nathan Whitaker both got this wrong in their written descriptions, I'll check later.

Suddenly I'm generating five leaf nodes worth of correct-looking triangles, and I'm still detecting one unreachable leaf, but I'm starting to think this may be correct - this leaf may represent the "outside" subspace.
Posted on 2009-05-13 09:47:15 by Homer
There's a small problem with the portal discovery, in regards to the 'clipping' of portal fragments to coplanar Leaf faces..
When a portal fragment is found to be coplanar with a face in a leaf, we should be spliting the fragment against the three "Edge-Planes" of the face, and discarding any RESULTING fragments found to be 'behind' the face.
Noting that these triangles are coplanar, the meaning of 'behind' is not clear.
What we mean is "inside" - we wish to detect and discard fragments that are inside the area of the occluding face.

What do I mean by "Edge-Planes" ?

Well, we know how to find the Surface Normal of a triangle by crossing its Edges, right?
vPlaneNormal = vAB x vAC

I believe we can construct planes which pass through the edges of the triangle, and are orthogonal to its surface normal, by crossing the surface normal back over each of the ordered edges of the triangle:

vPlaneNormalAB = vAB x vAC x vAB
vPlaneNormalBC = vAB x vAC x vBC
vPlaneNormalCA = vAB x vAC x vCA

Is this correct?

Sure, we need to calculate PlaneD for each Edge-Plane, which is easy given a Normal and a Point (just evaluate the plane equation).

I'm thinking that I might calculate all the Edge-Planes for the input triangle soup, and add them to the 'potential splitter planes' before I even begin BSP tree generation. Not only will this solve my current problem with clipping of coplanar fragment/face pairs, but it will allow the BSP generator to produce trees with potentially far fewer splits (generating less new trianges), better balance, and less depth, simply because it has access to potentially better splitting planes.
Posted on 2009-05-13 10:54:44 by Homer

I did a quick check and it appears that my formulae for calculating the Normals of the Edges of a triangle are ok, although we still need to Normalize the three resulting normals, and we still need to find the PlaneD values.
We can calculate the PlaneD values quite cheaply using this formula:

Tonight I will implement the code to deal with the special case of clipping portal fragments against COPLANAR faces (requiring that we use the edges of the face as cutting planes).
Posted on 2009-05-15 02:16:31 by Homer
I'm still having trouble clipping one 3D coplanar triangle to another using the EdgePlanes technique to carve away at the geometry...I suspect that my EdgePlanes are not correct.
My situation is that I have some "permanent" triangles which intersect with some COPLANAR "portal fragment" triangles, and I wanna clip the portal fragment triangles to the permanent ones, discarding all the overlapping regions. It is worth noting that this is essentially a 2D problem, since the problem triangles ARE coplanar, however I'm not using Projection solutions, I'm trying to solve it in 3D.

The current solution involves calculating these three plane normals via crossproducts of the surfacenormal and the three edge vectors.

These three plane normals can be expressed another way.
We are looking for the three vectors that extend from the centroid of the permanent triangle to the midpoint of each of its edges.... normalize these three vectors.
Then for each, we can find PlaneD by assuming a known point on each plane, which is just any endpoint of the respective edge, and doing a crossproduct of that point with the respective normal.

Its actually a very poor alternative solution as it involves divides and other yucky stuff, I really wanna figure out whats wrong with my current code, are my edge planes correct, or are they not?

Posted on 2009-05-15 22:24:35 by Homer
I've been tackling this same bug for days now, almost a week in fact.
Disturbingly, when I disable Debug support, the application executes without a hitch, despite the numerous int3 traps which are otherwise encountered.

It appears that there's a bug in the debug :P
Biterider needs to see this.
Posted on 2009-05-16 22:47:25 by Homer
Finally, the waters have receded.... a bug is revealed!

The cause of all my problems was D3D_VertexBuffer's mechanism for growth.
It can (and usually does) relocate the internal (software) vertexbuffer, causing all existing pointers into that buffer to become invalid without any warnings being generated.
I was relying on these pointers remaining valid at all times!

I've added a couple of new methods to D3D_VertexBuffer.
Please use them in preference to the GetPtr / IndexOf methods.

GetHandle will convert a given Vertex Index into a 'handle'... this is in fact a zerobased offset into the buffer.
Handles remain valid for the lifetime of the D3D_VB object, Pointers do not.

PtrFromHandle will convert a given Vertex Handle into a pointer... note that this pointer will NOT remain valid, so use it to access the vertex data, then throw it away.

I'm currently implementing these new methods throughout the BSP code, I'm certain that I have nailed the culprit this time :)

Temporarily removed all code relating to Portals. Implemented changes in BSP generator. It's working perfectly, great! Now its time for Portals 2.0 - supporting true polygons (3 or more coplanar points).
Posted on 2009-05-19 04:16:07 by Homer
I've decided that the Portals implementation requires not "true polygons", but merely "coplanar quads" in addition to triangles.

Please feel free to examine the two attached images.

The first image shows how I figured out all the possible cases of a triangle being 'cut' by a plane, which is a requirement of the BSP tree generator.
In this image, the plane always faces UP, and the orientation of the triangle varies.
It is proof that cutting a triangle with a plane will either produce two triangles, or three triangles.

The second image shows what I have in mind for the Portal geometry.
In this image, the plane orientation varies (is indicated by the arrow), and the quad is drawn in place.
It is proof that cutting a quad with a plane will either produce two quads, or it will produce two triangles and a quad. Therefore, we do not require any more complex geometry than this.
Posted on 2009-05-19 09:13:27 by Homer
Implemented the new Quad-Splitting function.
Portals are created as quads, and during splitting, will prefer to generate quads, only generating triangles when necessary.

My test model processes perfectly with all the code implemented so far, it generates portals, then 'shatters' them by cutting them with all the splitting planes, and the result is a bunch of quad portal fragments, and ZERO triangle portal fragments.

This is correct, since in my test model, all the walls are orthogonal to each other, so they cut each other into neat sub-quads , ie my 'doorways' are all regular rectangular shapes. Zero portal triangles is the right answer in this case.

Re-implemented code to identify false portal geometry, and to trim the surviving geometry into its final shape, just need to reimplement code to render the portals for visual debug.

Just to keep this thread interesting, I'm attaching a current copy of the BSP code.
I was going to just post the source for the quad splitting function, but its too long to post (exceeds board limit) and thats while heavily using macros to reduce its line length!!!

Posted on 2009-05-23 07:31:57 by Homer
Made a few changes to the Portal slicing functions in order to implement 'clipping portals to leaf faces', required due to the way I chose to handle the special case of clipping coplanar geometries via their Edges.
Since our Portals contain both triangles and quads, its important that we always process the quads before we do the triangles.
The reason is that quad-slicing can produce triangles as well as quads, and we need to ensure that all geometry generated in nested calls is correctly handled at higher nesting levels.

My clipping code is almost complete, there remains a bug which I suspect is due to incorrect calculation of "edge planes", or possibly incorrect vertex ordering of the initial portals (I checked/corrected the Y axis construction, but not the other two).

I can't say I'm completely happy with my existing implementation of clipping, I think I'll ask a few people for their thoughts on this.

Posted on 2009-05-23 22:40:08 by Homer
My implementation of Portal discovery (using the 'Quads-n-Triangles with EdgePlane Clipping' approach) has turned out to be an unwieldy and overly complex beast with functions that have huge numbers of case handlers and nested solvers. Furthermore, it still can't produce the most optimal output geometry.

So back to the drawing board, my demand for excellence dictates that I implement 'real polygon portals'.
The attached image shows what I really want to do - given an input polygon constructed from an arbitrary number of COPLANAR points, and given a Cutting Plane, generate output Polygons for the Front and Back sides of the Plane.

The algorithm will be something like this...

1. Walk the points of the polygon which are on the same side of the plane, until we find the first instance of a point that is on the opposite side of the plane.

2. Calculate the first point of intersection.

3. Beginning at the intersection point, construct an output polygon by continuing to walk points until we once more cross the Plane.

4. Calculate the next point of intersection.

5. Close the current Polygon by creating a closing edge between the intersection points.

6. If the next Point is the first point of intersection we ever found, terminate the algorithm.

7. GOTO Step 3.

What are your thoughts?
Posted on 2009-05-24 02:19:38 by Homer
The algorithm needs to be 'contextual' and be able to 'switch' construction when we cross the plane.
In order to correctly split the polygon in the example image attached to the previous post, I think the algo needs to look something like this:

While we dont have an intersection point, and we still have Points

  Get the Side of the first Point
  Get the side of the Next Point
  If Different, remember first intersection point, and break loop

If we dont have an intersection point, Polygon was not SPLIT.. and we know which side.
Create New Polygon on the noted Side of the plane.

Beginning at the intersection point.
While the next Point is NOT the first ever intersection point
    Get the side of the Next Point.
    While the Next Point is on the Same Side
        Add to Current poly
    Calculate the New intersection point.
    If I was going Clockwise,
        Close the current Polygon
        If theres a current poly on the Other side
            Switch to it
            Add the New intersection point to it
            start a New one on the Other side of plane.
        Start a New one on the Other side WITHOUT killing the Current one.

Some feedback?
Posted on 2009-05-24 03:03:13 by Homer
I trashed that too, and decided that I could greatly simplify things by accepting the limitation that polygons must remain always Convex. With that in mind, I went about writing Portal and Polygon classes, and ripped out all the PortalQuad/PortalTri stuff.

The attached Polygon class implements a "N-Gon" constructed apon a 3D plane.
It's a list of 3D points, which we assume is a circular list, and between which we assume an ordered list of Edges.

Portal inherits from Collection, and implements a list of Polygons. The constructor method (Init) takes a Plane apon which the portal geometry will be constructed.
Polygon inherits from DataCollection, and implements a list of Vec3 points representing the (closed and convex) polygon. The constructor method (Init) takes a Plane apon which the polygon geometry will be constructed. The Insert method verifies, as we add each new point to the polygon, that the polygon remains convex. This is done by calculating the direction of the surfacenormal of the triangle formed by the last two points in the polygon plus the new point that the user is attempting to insert, and comparing that direction to the normal of the construction plane.

So far I'm constructing the initial portals using this new code, no problems.

Posted on 2009-05-25 07:29:17 by Homer
Everythings put back together except render code, took some work !!
Code is much smaller, much more stable, and produces better output.
Will reimplement rendercode and proof my work before moving on.
Posted on 2009-05-27 09:04:04 by Homer
Here's an update of the important files containing all the bugfixes.
This represents the current state of my implementation, which is undoubtedly incomplete.
However the code presented is robust, and gives nice results.
I'll certainly post a demo by the end of this weekend, although I doubt I'll consider the project mature.
Posted on 2009-05-28 02:18:40 by Homer
I made an important change to further improve stability.

The POLYGON.Insert method will now verify whether adding a given new Point would cause the polygon to become concave (non convex), and if so, will attempt to insert the new Point just before the last current Point ("twist" the polygon) in order to maintain convexity at all times.

I've asked Biterider to review the existing code, which is missing just the "clip portals to leaf faces" function, and a render-portals function for visual debug.
There appears to be a lingering intermittent bug to track down, I'm hoping it appears more often on his slowest development box.
Posted on 2009-05-30 03:09:23 by Homer