I've been toying with one of my older projects..making improvements and adding further code to my BSPTree Generator.
-improved algorithms (faster, better numerical stability)
-threadbased execution (decoupled from MessagePump)

Step 1: take an input XFile and generates from it a BSPTree.
This has been completed, the implementation 'seems ok'..
But just building a BSP only solves the problem of z sorting.
It doesn't help us to cull non-visible faces..

Step 2 involves calculating the geometry of the Portals which separate pairs of leaf nodes.
Step 3 involves calculating the PVS of each leaf node with the assistance of the results from step 2.
Step 4 will just be code for Writing the output to a custom file, and code for Reading it back again.. nothing major.

I'm not going to talk about Generating a BSPTree here unless I'm asked to .. it deserves to be a separate topic of discussion.

For those not intimate with BSP:
1. The leafnodes of a BSPTree represent the empty spaces which exist in a 3D world which might be occupied by players or other objects.
2. There exists some Portals which connect pairs of LeafNodes and represent 'doorways' between leafnodes.
3. For each leafnode, we can calculate the total set of faces which are visible from any point within that leafnode (the pvs).
This is the faces of that leafnode, plus faces that are visible thru any Portals connected to it.
Now we can accelerate our rendering of the 3D world by ONLY drawing the pvs of the leafnode the camera is within.

While writing code for step 2, I noticed that I could re-use a lot of code from step 1, with a little modification.
I made the necessary modifications and improvements to the existing code, but didn't implement step 2 just yet..
Wanting to make sure that those changes, didn't interfere with existing code, I rebuilt the project and tested it.
I noticed a fairly dramatic speedup in the execution of Step 1 due to all the improvements, which kinda made my day since it wasn't an intentional result.

Next update will implement the new code for step 2.
Sourcecode available apon request.

Attachments:
Posted on 2006-12-26 03:09:02 by Homer
Hi Homer,

Sourcecode available apon request.


I'm interested in the source

I'm not going to talk about Generating a BSPTree here unless I'm asked to .. it deserves to be a separate topic of discussion.


I'ld like to learn more about Generating a BSPTree.

Friendly regards,
mdevries.
Posted on 2006-12-26 03:29:12 by mdevries
For the record, the recent improvements reduced the time for processing of my testfile (Tiny.x) on a 500Mhz machine from 42 minutes (old version) to 14 minutes (current version).
Note that the new version correctly preserves the Materials of faces, so that the World can contain multiple materials and even translucent ones.

OK, let's talk about how to create a BSPTree, and I'll provide my sourcecode.

BSPTrees are a binary tree structure where each non-leaf node describes a Plane used to binary-partition the World, and the leaf nodes contain (typically convex) sets of polygons which (along with the planes of all parent nodes) describe (typically convex) subspaces in WorldSpace.
Trees are typically described as a network of connected nodes.
We begin by defining the BSPNode structure (we can add stuff to this of course)..

BSPNode struct
pFront dd ?
pBack dd ?
pFaces dd ?
BSPNode ends

At the bare minimum, our node struct contains two dwords.
They can each be NULL, or they can each contain a pointer to a child node.

We begin with a 'polygon soup' made of triangles (we'll refer to these triangles as Faces).
I'm obtaining Faces from a .x file of your choosing.
The first thing we do is calculate the Plane of each Face (ie the plane which each face lays apon), and have each Face remember its Plane.

We create a root node for our tree.
Now we begin to build our tree.

We are given an input set of Faces (and their Planes).

The recursive problem is as follows:
From the Planes of all input Faces, find the Plane which both:
A) 'cuts' the fewest other faces
B) 'most evenly' divides the other faces

Use this to divide the other faces into three lists:
-those in front of the plane
-those behind the plane
-those which are coplanar
-those which are cut by the plane
If any faces are cut, create output faces and send them to front and back lists, then destroy the original.

Now mark the current node with the splitting plane, create child nodes, send the front list to the front child, the back list to the back child, overwrite the current node's input list with the coplanar list, and then solve the recursive problem (all of the above) for each child.

When this recursive process is complete, we have built a BSP tree whose non-leaf nodes represent splitting planes and any faces which live on that plane.. the leaf nodes are as described.

This is all we need to implement view-independant Z-sorting, but at this stage we're still forced to draw the entire world - we're not finished !!

The attached zip is bound to have files missing - let me know which and I'll add them.


Attachments:
Posted on 2006-12-26 05:00:56 by Homer
Hi Homer
Missing files:
- ..\..\..\..\ObjAsm32_13d\Projects\Homer\D3D9\PointsPlanesEtc.inc
- the whole res folder

Here is a link that describes the partitioning with a little graphical support http://en.wikipedia.org/wiki/Binary_space_partitioning

Regards,

Biterider
Posted on 2006-12-26 05:45:06 by Biterider
Biterider - thanks :)

;include c:\masm32\ObjAsm32_13d\Projects\Homer\d3d9\PointsPlanesEtc.inc
This file is redundant - where was it included?

Attached zip contains Res folder, and also the latest copy of Vec3Math.inc :)
Attachments:
Posted on 2006-12-26 06:45:21 by Homer
Hi Homer
This is the compilation status:
Missing file: C:\Masm32\ObjAsm32\Code\Objects\Vec4Collection.inc
I have an old copy, but it shoulde be included in your distro

I changed the following line:
;include c:\masm32\ObjAsm32_13d\Projects\Homer\d3d9\d3d9.inc ;Contains some global data (REQUIRED)
% include &COMPath&COM.inc
% include &DxPath&D3D9.inc
% include &DxPath&D3DX9Core.inc
% include &DxPath&D3DX9Math.inc
% include &DxPath&D3D9Types.inc
% include &DxPath&D3D9Caps.inc
% include &DxPath&D3DX9Mesh.inc
% include &DxPath&D3DX9Tex.inc

Still missing symbols:
pD3DDevice, szErr, szFailD3D, pD3D, d3dpp, fp1000
I guess that all of them are included in your modified d3d9.inc

Regards,

Biterider
Posted on 2006-12-26 08:47:37 by Biterider
Attachment has the missing files.
Attachments:
Posted on 2006-12-26 10:14:22 by Homer
Hi Homer,

Compiling the project I had some errors.
There was a symbol redefinition of the structs: vec2 and vec3

I commented them both out:
- vec2, in BSPGenerator.asm
- vec3, in vec3Math.inc

They are both defined in \masm32\ObjAsm32\code\DirectX\D3DXMath.inc.

I moved the line which includes vec3Math.inc a little further, directly after the line which includes d3d9.inc, because I still had errors.

After having done this the next compile error remains:

BSPGenerator.obj : error LNK2001: unresolved external symbol _DirectSoundFullDuplexCreate@40
BSPGenerator.exe : fatal error LNK1120: 1 unresolved externals


How can I solve this error? And have I done right sofar?

Friendly regards,
mdevries.
Posted on 2006-12-26 17:26:27 by mdevries
Heya - the teething problems don't sound too painful.

I had commented out those Vec structs in the dxmath file.. the structs are the same, so it really doesn't matter..

Here's what I did to my dxmath file:

D3DXVECTOR2 struct
  x FLOAT ?
  y FLOAT ?
D3DXVECTOR2 ends
LPD3DXVECTOR2 typedef ptr D3DXVECTOR2

D3DXVECTOR3 struct
  x FLOAT ?
  y FLOAT ?
  z FLOAT ?
D3DXVECTOR3 ends
LPD3DXVECTOR3 typedef ptr D3DXVECTOR3

D3DXVECTOR4 struct
  x FLOAT ?
  y FLOAT ?
  z FLOAT ?
  w FLOAT ?
D3DXVECTOR4 ends
LPD3DXVECTOR4 typedef ptr D3DXVECTOR4
Vec4 equ <D3DXVECTOR4>


The reason I removed the Vec2 and Vec3 references from there is that they are not DX terminology, they're MY terminology.. it just so happens that I am also the creator of that dxmath file, which is how they ended up being there in the first place.


I don't use any DirectSound stuff in this demo.
When I build this project, I only get a warning from the linker :
"LINK : warning LNK4089: all references to "DSOUND.dll" discarded by /OPT:REF

Maybe our linking options differ? (I use RadAsm, I can provide RAP file)
Anyway, you can safely comment out any references to DSound which are in the d3d9.inc file since we're not using it..

Also - I believe the more recent source I posted contains some extra code to begin generating Portals after the tree is generated - if so the app will likely crash at that point - I'll probably post an update at some stage today.

Posted on 2006-12-26 21:20:37 by Homer
Biterider will probably be most interested in the XFile importing code (main asm file).

mdevries will probably be most interested in the ChooseBestDividingPlane procedure, and the ClassifyFacePlane procedure which it relies apon.

ClassifyFacePlane compares a single triangular face and a plane.

If we say that input triangles are made of points ABC, the result from ClassifyFacePlane tells us which side of the plane each point lays.
For example, the result 'FRONTBACKCOPLANAR" means that Point A is on the Front side of the plane, Point B is on the Back side of the plane, and point C is smack on the plane.. in this example case, our plane passes through point C, and intersects edge AB, dividing the triangle into two output triangles.

ChooseBestDividingPlane takes an input set of triangles, and tries to use the Plane of each triangle to partition the rest of the triangles in order to determine which is the 'best'.. it doesn't actually partition the input list, it performs 'virtual partitioning' to evaluate the 'best partition result'.
Once it has determined the 'best splitter', it calls DivideFaces which reproduces the 'best result', but this time actually generating new output triangles and new vertices at intersections.

Child nodes are created on demand and are filled with the output triangle lists, and then we recurse the child nodes until we fail to find a suitable splitter.
This only happens when the input list contains 2 parallel faces, or contains a convex set of faces .. we call these leafnodes and return from recursion.

Posted on 2006-12-26 23:45:07 by Homer
Hi Homer,

I had commented out those Vec structs in the dxmath file.


The reason I removed the Vec2 and Vec3 references from there is that they are not DX terminology, they're MY terminology..


For that reason I will remove them from the D3DXMath.inc file too, instead of commenting them out in the project.

Maybe our linking options differ? (I use RadAsm, I can provide RAP file)


You already provided the rap file in the project source.
I am using RadAsm too. The linking options for the project are:

5,O,$B\LINK.EXE /SUBSYSTEM:WINDOWS /RELEASE /VERSION:4.0 /LIBPATH:"$L" /OUT:"$5",3,4


Anyway, you can safely comment out any references to DSound which are in the d3d9.inc file


The project compiles now succesfully.

I tested Tiny.x on my 1,8 GHz laptop:
- Saving of the output (DebugCenter): 667 KB
- Duration (Application Topmost, DebugCenter visible behind it): 5:15 minutes.
- Duration (DebugCenter Topmost): 4:12 minutes.
- Duration (Windows explorer Topmost, Application and DebugCenter not visible behind it: 3:11 minutes.
- Duration (Application Topmost, Debugging off): 2:51 minutes.
- Duration (Windows explorer Topmost, Application not visible behind it, Debugging off): 2:40 minutes.

Friendly regards,
mdevries.
Posted on 2006-12-27 01:38:24 by mdevries
Please refer to Portals.inc ...

The next step is to create a large rectangle (two big triangles) which lay on each of the splitting planes (non leaf nodes).
This is easily achieved via the bounding box corners (BoxMin, BoxMax).. we simply take the boundingbox values and feed them into each Plane Equation in order to generate the 'missing points'.
We call these large triangles 'potential portal faces', and we store each pair of them in a list , then store that list in the Node whose splittingplane we just used to generate it.

Why did we need to store them in lists? This is why:
Each time we create a list of potential portals on a given plane, we 'fragment' that list by cutting those faces with ALL OTHER SPLITTINGPLANES...
We simply use our existing triangle-splitting code.. output collections are channelled back into their respective input collections instead of being shoved into child nodes.
Now each List contains a healthy number of 'potential portal fragments'.

The next part is a little tricky.. we need to 'frogmarch' all those fragments down the tree.. Basically this is similar to generating a tree.. Note that since all fragments have been pre-split against all planes, no Splitting should occur during this stage.. if it does, you screwed up.
Each fragment is compared against the current node's plane.. front fragments are sent to the front child, back fragments to the back child, and (THIS IS IMPORTANT) coplanar fragments are sent down BOTH SIDES.
It is for THAT reason that we are using DwordCollections that contain REFERENCES to faces.. we can have multiple REFERENCES to one face without trouble.
Anyway, when that's completed, all the fragments have ended up filtering down into the leafnodes.

We're almost finished !!

For each PAIR of leafnodes, we look for any fragments that exist in BOTH leafnodes - if a fragment exists in two leafnodes, it's a 'TRUE PORTAL FRAGMENT', otherwise it's marked for death.

Once we've found all the TRUE PORTALS that join LEAFNODE PAIRS, we can DANCE A JIG because we just 'extracted connectivity information from a BSPTree' - we're only a heartbeat away from generating a PVS for each leafnode.

Portals make calculating PVS quite fast and simple, but theres at least one other thing we can use them for - if we recall that leafnodes describe 'the subspaces where players and other objects can exist', we can think of portals as 'the possible exits from the current room'.. if Elvis collides with a portal, he just left the building.. more importantly, we know exactly which leafnode Elvis just entered, no discovery process is required.

Posted on 2006-12-27 20:18:46 by Homer
I've finished writing code to save the tree (after generating it, and before we screw with Portals) , and to load it back again.

Note to Biterider: The problem when using Put and Get methods was due to a lack of checking of MemAlloc failures.. Having spent some days developing this code, HeapAlloc() was beginning to fail (either my ram failing in the heat, or the OS heap manager failing due to poor implementation).. once I replaced the Get and Put calls with handcrafted loops that contained MemAlloc checking, the problem vanished - and strangely, MemAlloc stopped failing me too !!
Maybe all I had to do was reboot :P

The Load and Save functions are recursive - the tree is saved and reloaded in exactly the same order it is typically Walked.
The planeptrs (stored in each node) are replaced with Indices during Saving, and are converted back into Pointers during Loading.
This could have been handled in a more linear fashion, but then we'd have to store a chunk of linear data describing the tree layout (like Quake's BSP files, which use a binary string) - I chose to record this information on a per-node basis, thus the nodes themselves guide the reconstruction of the tree.. The two dwords which trail each non-leaf node in the file could be replaced with bytes, which would reduce the filesize somewhat, and there's a number of further optimisations that COULD have been applied in order to further reduce filesize, but it's simply not a big issue to me right now.

The Load and Save functions both ATTEMPT to deal with Portals - which at this point don't exist .. it means that once I implement the portal generating code, we can reuse the existing Save and Load functions.

I'd like to make it clear that Tiny.x is a very UNSUITABLE mesh for BSPTree generation - which is exactly WHY I chose to use it.
Not ONE of its 6,841 planes was duplicated - nothing is truly coplanar (during loading of XFile, I eliminate duplicate Planes by returning duplicate Pointers/Indices)..
The planes of its faces intersect each other so much, causing MANY splits (despite our attempts to reduce this in ChooseDividingPlane).
Typical game worlds contain many more coplanar faces (more faces 'share the same planes', so we have less planes than faces at the start) - this is far more suitable - creating fewer splits (fewer new triangles and fewer new vertices), and yielding a more balanced, less deep tree.
I wanted to make SURE my generator would work for arbitrary scenes, not just nice orthogonal indoor scenes (eg DOOM)

Posted on 2006-12-27 22:38:10 by Homer
Hi Homer,

I've finished writing code to save the tree (after generating
it, and before we screw with Portals) , and to load it back again.

Note to Biterider: The problem when using Put and Get methods was
due to a lack of checking of MemAlloc failures.. Having spent some
days developing this code, HeapAlloc() was beginning to fail.


Does this mean you intended to attach the new source?
There is no attachment though, but I'm interested in it.

Friendly regards,
mdevries.
Posted on 2006-12-28 03:27:40 by mdevries
Attachment contains my sourcecode as of today.
The code in Portals.inc is unreliable and incomplete - it is only there for your personal amusement / interest.

mdevries:
I'm not in any hurry to complete this project - given that fact, and the implied time you have to familiarize yourself with this code, are you interested in helping to extend and complete it?
(I could shovel you smallish jobs to help complete the project)
No deadlines means no pressure, and since there's no pressure, I could care less if you completely bork the job, it's an educational/fun kinda project with a potentially commercial long term prognosis.
Please note that this is currently to the best of my knowledge the world's FASTEST BSPTree Generator, and I've posted it all for FREE.
A lot of people don't really understand BSP, and the 'other' ways it can be applied ... example.. a 'CSG Editor' where our paint 'brushes' are precompiled BSPTrees which are unioned at runtime.
Attachments:
Posted on 2006-12-28 05:03:54 by Homer
Hi Homer,

I'm not in any hurry to complete this project - given that
fact, and the implied time you have to familiarize yourself with this
code, are you interested in helping to extend and complete it?


I'm in the luxury of having holidays until the end of december.
That's why I have more time for asm programming at the moment.

But have to divide my programming time into three parts:

Gathering information
---------------------
I'm always looking for documentation on subjects I'm interested in,
which can be studied at a later moment. For instance:

Project Source:
- OOP
- RadAsm AddIns
- 3D Projects
- GameDev Tutorial (Especially the way it was evolving)
- BSP Generator (I guess this project will evolve too, I am interested
in this evolving process)
etc.

Books:
- Jim Adams: Advanced animation with DirectX
- Frank D.Luna: Introduction to 3D Game Programming with DirectX 9.0
etc.

Studying information
--------------------
Gathered information has to be studied. At the moment I am studying:
- RadAsm AddIn source code projects

Programming
------------
It is my wish to create a chess engine. I once did for DOS, and it was time consuming.
But for now my active programming time has to go to the tools I need for creating my engine. That's the reason why a few RadAsm AddIns have my specific attention at the moment. Maybe I want to create my own AddIn.
After my chess engine I want to give my active programming time
most likely to 3D programming.

Given these facts, and your proposal to getting involved in the
BSPGenerator project: I'ld rather be on the sideline for now,
if you don't mind. But I'm interested in it.

Friendly regards,
mdevries.
Posted on 2006-12-29 10:07:11 by mdevries
Not a problem :)

I've never coded a chess engine, but I can say without a moment of hesitation that it would be based on a neural network.
The reason is that chess (and most turn-based games for that matter) is an exercise in pattern recognition, and neural networks are nothing if not trainable pattern recognizers... training your own game to beat you sounds a lot more fun than the alternatives, and it will remain unpredictable and adjust itself to the enemy.

Anyway, I'm now at the stage where I'm creating a large flat rectangle  (actually 2 big triangles) apon the plane of each non leaf node and extending over the entire bounds of the model (ie based on the model's bounding box).
Each rectangle is a collection of triangles, and lives in node.pPortals
I'm meant to split each of these pairs of triangles using the planes of all the OTHER non-leaf nodes, so that we produce a crapload of tiny fragments of triangles.. then I'm meant to pass each resulting list of fragments to the rootnode and let them 'fall through the tree' by classifying them against each node's plane until they reach the leaves (no splitting should happen now).
The current problem I'm facing is that my triangle splitting code is refusing to correctly classify my giant triangle pairs against the other splitplanes and so no fragmenting is occuring.
I suspect I'm doing something silly, since I'm reusing a lot of the code from previous stages, and hadn't detected issues in there previously.
One thing I did do late last night is add a couple of debug lines to let me see when large portals are first created what plane they were meant to use, and what plane the new big triangles actually used.. I noticed a very small error, far smaller than my epsilon of .001 , but still..

The attached zip contains an update allowing you to save your tree to a 'TRF' custom file after generating it, and to allow you to load a TRF file for portal generating.
It includes several minor bugfixes, and several modifications of shared functions.


Attachments:
Posted on 2006-12-29 22:23:15 by Homer
Think I found the problem..
The boundingbox of the entire model is calculated when the xfile is first loaded.. I had neglected to store this in my custom file data.. so that one is my bad, since I insisted on saving the machinestate half way.

Also, I found the source of the instability in the loader, and fixed that small and silly bug also.
Probably be updating this again today :)
Posted on 2006-12-29 22:48:28 by Homer
Hi Homer,

Thanks for your thoughts:

I've never coded a chess engine, but I can say without a moment of
hesitation that it would be based on a neural network.
The reason is that chess (and most turn-based games for that matter) is an
exercise in pattern recognition, and neural networks are nothing if not trainable
pattern recognizers... training your own game to beat you sounds a lot more fun
than the alternatives, and it will remain unpredictable and adjust itself to the enemy.


I must admit that my chess engine wasn't a self teaching system.
What readings on neural networks would you recommend?
- Documentation
- Tutorials
- Project sources

Friendly regards,
mdevries.
Posted on 2006-12-30 04:47:12 by mdevries
I would recommend a thorough study of Thomas Bleeker's DigiBrain project, and suggest that my oopified translation of the core code be a good place to start. Here we have working code, and a proven demo, and that's always a bonus.
Posted on 2006-12-30 06:52:46 by Homer