I was correct in claiming that I wasn't kludging the stack.. no issues there.
The crash was caused by a lack of sanity checks being performed on output fragment lists during the nested recursion.
Having added a few lines of code to check the content of an input fragmentlist before processing it (or rather lack of content), the application is now stable, at least until the completion of the fragmenting and frogmarching phase.
At the end of this pass, we forget about the rest of the tree and just look at the leafnodes, which now each contain a list of potential portal fragments.
We must perform an exhaustive search for mating fragments that live in two leafnodes, as these are considered 'real portal fragments', and having done that, we can chuck out the rest.
I am yet to confirm the accuracy of that operation, my existing code just looks for duplicate facepointers, which might not be enough (if I screwed up the vertex order at ANY previous stage, I'm going to have to compare vertex index triples for rearranged triples, if that makes sense at all.

I've attached the most recent binary so we can time this operation, and see just how many fragments we're dealing with (its a LOT).

Compared to the creation of a bsptree, the discovery of the portal geometries is some exponential order more complex, and thus exponentially slower and exponentially more resource intensive, and for this reason, I've switched to testing on tiger.x, but remember I'm developing this on a lowly 500mhz box, and I'm not getting any younger!
Posted on 2007-01-03 18:36:09 by Homer
Heh, that version just exits when I choose file->load. Does it require tiger.x in same folder as the exe?
Posted on 2007-01-03 18:47:10 by f0dder
No it does not, but theres some kind of allocation problem when loading the planes data back from TRF file.. its intermittant, no idea what the deal is there, code is VERY straightforward :|

I've just been ignoring it for the time being, just execute the app a few times until the darn thing works, 2 or 3 failures and then it works :|

Note that the app will just exit if the TEXTURE mentioned in given xfile is not in same folder as xfile ;)
If you have debugcenter installed, this event will be the last thing you'll see in the debug spew, and filename will be mentioned - if u dont have a texture u can just rename any bmp u like and shove it in there ;)

Attached is an update, I've wrapped the portalizing code in its own thread just like I did with the treegen code, and it has a working timer too :P

Posted on 2007-01-03 19:24:23 by Homer
I'm running a full test on tiny now.
Treegen pass took 10 minutes, 15 seconds.
As for the Portalizing pass, the FIRST portalrect took 118 minutes to fragment and frogmarch.. ouch!
I've generated so far roughly 100kvertices / 60k faces (all-inclusive), but remember that most of those are 'fakes', and will have to be pruned out later.
That'll be an interesting chore to renumber the vertex indices of the 'actual portals' :)
If we assume an average time of around one hour per node, and we assume theres around 5000 non-leaf nodes, I estimate this operation to complete in about 208 days !  :shock:

I'm pretty sure I can improve on the algorithm itself, and I'm yet to introduce extra code for culling of 'bad triangles' (ie avoid splitting triangles where the result would produce a triangle of extremely small area). I believe that the extra time required for this extra processing would pale into insignificance compared to the overall time saved by NOT processing these so called bad triangles at all deeper recursion levels.

Posted on 2007-01-03 19:41:15 by Homer
Well, it exited when I selected "file->load xfile"... gives a "bla bla debugcenter" messages then exits. The one from "mobetterer" exits without showing the debugcenter box >_<.

Would be nice if you used OutputDebugString instead of the debugcenter, then I could just use sysinternals' dbgview :)
Posted on 2007-01-04 04:17:28 by f0dder
Not meaning to imply that I doubt your word, but theres a few debug lines that you should ALWAYS be seeing.
If the app is dying before a single line is output, then I am highly concerned, and feel that others should be made aware that DebugCenter has some as-to-now unknown shortcoming, which needs immediate addressing.

I agree, sometimes when you hit Load TRF file, it dies.
It never dies for me when merely loading an xfile, it DOES die occasionally when I load my custom file, I repeat this is weird and I am yet to put my finger on that one, but NO DEBUG LINES is a real worry.

Posted on 2007-01-04 04:40:15 by Homer
Well, I'm not running DebugCenter - so I'm not seeing any output :)

But the program dies (just terminates, no crash) when I select "load xfile".
Posted on 2007-01-04 05:56:23 by f0dder
I get yet another behavior: Selecting "load tree..." shows "registeration error. start debug center manually" and then grays-out the option. The 'load xfile' gets greyed out when i select "cancel" in the openfilename dialog (and sometimes shows the "registration error..." messagebox).

...But after some tries (the "registration error..." stuff seems to show up randomly) I managed to load "tiny.x", then it was "thinking" for about 10 minutes when I cancelled it ^^

BTW: I think that the process can be sped up a little bit by _NOT_ repainting the client area so often (1 repaint every 500ms is more than enough).
Posted on 2007-01-04 07:31:56 by ti_mo_n
From the description you write, I guess you are using an old version of DebugCenter (DC). DC needs to run once to register itself, so that the thebug process can popup the DC window as needed. If you install the OA32 package without problems, the registration is done automatically.
I suggest to download the latest DC version and run it once (and dont change it location).

Posted on 2007-01-04 07:57:30 by Biterider
I've discovered a much better algorithm for the portal generation - it looks like it requires far less recursion, it generates fewer fragments, and it can be adapted to suit my style of BSPTree (where leafnodes are not necessarily truly convex sets of faces, and where non-leaf nodes may contain N coplanar faces).
Credit for this algo goes to Andreas Brinck.

Recursive function A (For each non-leaf node in the tree):
- create a large rectangular polygon on the current node's plane
- pass this polygon to BOTH childs via recursive function B
- recurse childs

Recursive function B (for given Node and given Poly):
- if the given Node is a leaf node (OR if the node contains a 'list of coplanar faces' - thats my adaptation), we must clip our portal polygon against these faces *see below
- if the given Node is NOT a leafnode:
- try to split the Poly with the current node's plane
- if the resulting Poly is "all front", recurse the Front via B
- if the resulting Poly is "all back", recurse the Back via B
- if the resulting Poly is "coplanar", recurse BOTH childs via B
- if the resulting Poly is "SPLIT", send resulting fragments back to the top of the Tree and reprocess them via a call to Recursive function A

* we must clip any parts of our poly which are overlapped by these faces .. if the faces are coplanar with the poly, then this is fairly easy.. if not coplanar (ie leafnodes), we project those faces onto the poly's plane, and then we're back to 'this is fairly easy..' :P

As you can see, we still have a nested recursion, but this algorithm has the advantage of eliminating much UNNECESSARY recursion, and automatically identifies the 'real portals' via the clipping function - ie fake portal fragments are removed by that operation, and this can occur at ANY node in the tree, not just at the leaves .. which also means we're sending LESS fragments down the tree :)

I'll begin modifying my existing code to take advantage of this improved algorithm later today  8)
Posted on 2007-01-04 23:26:52 by Homer