I've started recoding my BSP generator.
This version imports directly from XFile.

The attached demo is an XFile-to-BSP converter tool.
You can't save the output yet, so don't bother trying.

So far it imports geometry from an XFile (collapsing the scene hierarchy if any), checks that all referenced textures are available (in the same folder as the xfile), calculates an array of unique Planes from the Face data, and marks each imported Face with the index of its Plane.
Then it will examine the set of imported faces to determine if the set is concave, convex, or neither.
A Concave set of triangles "all face toward each others plane", while a Convex set of triangles "all face away from each others plane".
In both of these cases, no plane exists which divides the set of faces, and therefore no (further) BSP sorting is possible.
During generation of the nodes of a BSP Tree, this test for 100% concavity/convexity is the first test we apply, and so it is the first test which I have coded.
The demo does not generate a BSP Tree, it simply performs the first test apon the entire set of imported faces.

If you are interested and want to see the source, ask and you shall receive.

Posted on 2006-01-14 21:53:56 by Homer
Moving right along, here's an updated version of the BSP tool.

This time, I have added the most important function of all.
Its name is ChooseBestDividingPlane.
Given a set of faces, the function performs an exhaustive (and thus slow) search for the Face whose Plane best matches the following two (mutually exclusive) criteria:
- the Face's Plane must cut (split) the fewest other Faces.
- the Face's Plane must divide the other Faces most equally on either of its sides.

The first thing that ChooseBestDividingPlane does is perform the concavity/convexity test outlined in the previous posting. If the set of faces is found to be concave or convex, it returns EAX=NULL.
Otherwise, every Face is compared to every other Face, while some heuristics are maintained in order to find the Face which is "best" according to the criteria outlined above, and it returns EAX=pointer to Best Face and EBX=index of Best Face.

In order to generate a BSP Tree, we select the best dividing face as outlined above, and then divide the remaining faces into two sublists, adding extra faces due to Splitting where necessary.
This process is then repeated for each sublist, until division becomes impossible.

Therefore, this ChooseBestDividingPlane function is really at the heart of the BSPGenerator, and is vital in order to generate a well-balanced tree with the fewest possible splits ("the best tree").

The attached version of the tool chooses the best splitter from the entire set of faces, that's all folks.

Posted on 2006-01-15 00:46:29 by Homer
Hi Homer,

If you are interested and want to see the source, ask and you shall receive.

Sure I am intersested to see the source. Could you attach it?

But I have a problem running the given executables.
Both of them produce the complaint that d3dx9_28.dll is not installed, and that I should install it first.

On my computer DirectX 9.0 SDK (Oktober 2005) is installed.
Isn't this enough?

Friendly regards,

Posted on 2006-01-15 02:29:26 by mdevries
I built this using the DECEMBER 2005 updated libs.
I suggest you update your DX9 runtimes, we don't want to live in the past, do we?

Attached are the main .asm file, the main .inc, and the ChooseBestDividingPlane code.
This is not ALL of the code required to build the project.

The missing files include the Vec4Collection class and my "PointsPlanesEtc" include which contains most of the math and primitive classification functions.
The Vec4Collection class implements an array of unique Vec4's used to store Planes.
It is guaranteed to ONLY store unique Planes.

Probably most interesting to you will be the main .asm file, which shows how to get D3D9 fired up for Windowed mode (it just uses the desktop's pixelformat and the appwindow's resolution).
No code for rendering is provided, we don't want to render anything here, just wanna use DX functionality to help us rip the XFile data. I only bothered firing up D3D at ALL because the XFile loading function requires it.

If you want ALL the files, ask again, noting that this is a work in progress and that these files are subject to change without notification ;)

Posted on 2006-01-15 03:47:41 by Homer
Hi Homer,

I built this using the DECEMBER 2005 updated libs.
I suggest you update your DX9 runtimes, we don't want to live in the past, do we?

I will update the DX9 runtimes.

If you want ALL the files, ask again, noting that this is a work in progress and that these files are subject to change without notification

I understand that the files are subject to change.
But at the moment, they represent the actual state of the project, and they help building the project, which is very useful.
So, I am interested in ALL the files.

Friendly regards,
Posted on 2006-01-15 07:50:41 by mdevries
I've added code to divide the faces into face subsets as directed by the AttributeTable.
ChooseBestDividingPlane was modified into ChooseBestDividingPlaneFromSubSet, and a new ChooseBestDividingPlaneFromSet was added.
A new class, SubSetManager was added.
Its job is to manage a Collection of Face SubSets, and ChooseBestDividingPlaneFromSet expects to be handed a SubSetManager instance.

Sorting the faces into subsets at load time is a good idea, even if it does make the processing of faces in the BSPTree generation slightly more difficult. If we keep the faces in separate subsets, texture thrashing will be reduced during the bsptree rendering process... not only can we draw all faces within a bsp leaf, we can draw them as subsets - and this gives us a mechanism to selectively disable entire subsets if we want to. By maintaining N subsets at the Node level, we have avoided being forced to mark each Face with a subset identifier, and we have eliminated any code which accesses that field, and we have eliminated sorting of faces  by subset at the end of the tree generation (to cope with new faces that were created from splitting of faces during tree generation).

ChooseBestDividingPlaneFromSet finds the best divider from N subsets, and stores the results in a temporary collection. If there's more than one result, ChooseBestDividingPlaneFromSet then finds the best divider from the results.
In other words, candidates are selected from each subset and then the candidates are whittled down to one winner.

Attached is the updated binary + full source.
If I missed any files, yell at me :)

Posted on 2006-01-15 10:52:07 by Homer
In my constant search for perfection, sometimes I overlook the obvious.
I believe I have been approaching this the wrong way.
Supporting face subsets during the bsptree sorting phase is undesirable... saving a few bytes of memory at the expense of higher complexity and slower execution is not desirable during the most computationally expensive phase.
Therefore, I have reverted to the original version of the source, with a few changes backported from the more recent source.
Faces are now marked with pPlane, rather than iPlane.
AttributeRanges are tracked during the extraction of Faces, and so Faces are marked with pMaterial as dictated by the AttributeID of the AttributeRange each Face belongs to.
Finally, Faces are now Stored in a DwordCollection rather than a DataCollection.
The reason is that this vastly simplifies the process of actually segregating the input list of faces into two sublists, although it means that we must provide our own code to clean up the collection where required.

A DwordCollection and a DataCollection are similar, but quite different.
DataCollection stores an array of Pointers to allocated structs ("memory objects").
It automatically releases the memory of objects removed from the collection.
DwordCollection stores an array of arbitrary dwords (which in our case happen to be Pointers).
It is totally naive as to the nature of the dwords it contains, and does not clean anything up when dwords are removed from the collection.
Since we want to be able to remove stuff from one collection and shove it into another one WITHOUT releasing anything, DwordCollection becomes the logical choice, noting that we must now take FULL responsibility for our data.

We can still sort the Faces in each BSPLeaf by Material at the end of the tree generation.
I'll live with that if it means that the processing speed is improved.
GENERATING A BSPTREE IS SLOW, and we should do everything within our power to speed it up.
I thought about creating a large lookup table of the results of comparing each face to the plane of each other face, but decided that is unrealistic for large meshes as the memory required is quite great.. and storing the LUT to disk for dynamic access is not an option, since disk access times are greater than the time required to perform a single comparison.
I'll be keeping my eye open for other potential optimisations.

Posted on 2006-01-17 01:42:54 by Homer
Attached is an update of the BSP tool.
This version actually generates a BSPTree, and has a crappy gui so you can watch it working without having DebugCenter installed (detailed information is spewed to debug output).
It handles both convex and concave meshes, and has been tested so far with 600 and 6000 triangle meshes.
What it currently does NOT do is split triangles which are cut by the dividing plane.
Also, I have yet to implement code to save the BSPTree to disk, I'll do that LAST.
I must solve the triangle splitting problem before even thinking about disk format, because right now faces which are to be split are simply disregarded, and thus are filtered from the tree, which is a Bad Thing.

Here is some pseudocode I threw together for performing the splitting of triangles.
It takes one input face and returns two or three output faces.
It does NOT calculate UV coordinates in regards to the new vertices created at the intersections of edges and the plane. So far, the entire project has been written to be "fvf-naive" - that is to say, it has no understanding of the vertex format, except for knowing how large vertices are in terms of #bytes per vertex.

If anyone wants to have a go at optimizing the pseudocode in any way, please post your work!!

;Name - SplitFace
;Purpose - Split a triangular Face into two or three triangular Faces
;pFace = pointer to Face to be split
;pPlane = pointer to splitting plane
;pFrontCollection = Collection to receive Front output faces
;pBackCollection = Collection to receive Back output faces
;dwSplitType = how to split the triangle
;(we determined SplitType in DivideFaces function)
SplitFace proc pFace, pplane, pFrontCollection, pBackCollection,dwSplitType
LOCAL RawTriangle:Triangle
LOCAL p1Classified
LOCAL p2Classified
LOCAL p3Classified
LOCAL fDist1
LOCAL fDist2
LOCAL fDist3

;First thing to do : obtain raw vertices (Points) of triangle face
invoke ConvertIndexedTriangleToRaw,addr RawTriangle,pFace,pVertices,dwNumBytesPerVertex
;Now classify each of the Points against the Plane (again)
;This time we are interested in exactly where each Point lays
;with respect to both the plane AND each other...
mov numOnPlane,0
invoke ClassifyPointPlane,addr RawTriangle.Point1,pPlane
fstp fDist1
mov p1Classified,eax
invoke ClassifyPointPlane,addr RawTriangle.Point2,pPlane
fstp fDist2
mov p2Classified,eax
invoke ClassifyPointPlane,addr RawTriangle.Point3,pPlane
fstp fDist3
mov p3Classified,eax

;Cases of OneFrontTwoBack
;One point is on the Front side of the Plane,
;and the other two points are on the Back side.
;So.. which point is on the Front side?
;p1 front, p2p3 back
.if p1Classified==INFRONT && p2Classified==BEHIND  && p3Classified==BEHIND
;p1=Point1, p2=Point2, p3=Point3

;p2 front, p1p3 back
.elseif p1Classified==BEHIND  && p2Classified==INFRONT && p3Classified==BEHIND
;p1=Point2,p2=Point3, p3=Point1

;p3 front, p1p2 back
.elseif p1Classified==BEHIND  &&  p2Classified==BEHIND && p3Classified==INFRONT

jmp UnhandledCase

.elseif dwSplitType==TWOFRONTONEBACK
;Cases of TwoFrontOneBack
;One point is on the Back side of the Plane,
;and the other two points are on the Front side.
;So.. which point is on the Back side?
;p1p2 front, p3 back
.elseif p1Classified==INFRONT && p2Classified==INFRONT && p3Classified==BEHIND
;p1=Point1, p2=Point2, p3=Point3

;p1p3 front, p2 back
.elseif p1Classified==INFRONT && p2Classified==BEHIND  && p3Classified==INFRONT
;p1=Point3, p2=Point1, p3=Point2
;Same algo as above

;p2p3 front, p1 back
.elseif p1Classified==BEHIND  && p2Classified==INFRONT && p3Classified==INFRONT
;p1=Point2, p2=Point3, p3=Point1
;Same algo as above

jmp UnhandledCase

.elseif dwSplitType==ONEEACHSIDE
;Cases of OneEachSide
;We have one point laying smack dab on the plane,
;and the other two points lay either side of the plane.
;p1 on plane, p2p3 on different sides
.if p1Classified==COINCIDING
.if (p2Classified==FRONT && p3Classified==BEHIND)
.elseif (p2Classified==BEHIND && p3Classified==FRONT)
;p2 on plane, p1p3 on different sides
.elseif p2Classified==COINCIDING

.if (p1Classified==FRONT && p3Classified==BEHIND)
.elseif (p1Classified==BEHIND && p3Classified==FRONT)
;p3 on plane, p1p2 on different sides
.elseif p3Classified==COINCIDING
.if (p1Classified==FRONT && p2Classified==BEHIND)
.elseif (p1Classified==BEHIND && p2Classified==FRONT)
return TRUE

DbgWarning "SplitFace : Unhandled Case"
DbgDec dwSplitType
DbgDec p1Classified
DbgDec p2Classified
DbgDec p3Classified
return FALSE
SplitFace endp

As usual, full updated source is available apon request.
I'm not going to post it if nobody gives a crap.

Posted on 2006-01-18 09:27:59 by Homer
I've revised my BSPGenerator code yet again.
This time, I've incorporated the "convexity test" within the "FindBestSplitter" function, which speeds up the generator immensely. I've also found two other major speedups which involve tagging any Faces that are coplanar with the splitting plane to prevent them from being considered as candidate Splitters in future iterations. Also, I'm now throwing splitter faces down the Tree in order to generate a "Leafy Tree" as used in Quake etc. I've improved the heuristics used to select splitter planes. I've streamlined the memory accesses to handle massive worlds, eliminating "illegal pointers" caused by memory reallocation.

The algorithms involved have been and will continue to be refined until I am absolutely satisifed that they are as fast as they possibly can be without sacrificing stability.

I am considering extending the existing functionality to include "CSG" , ie, realtime construction of geometry via boolean operations applied to convex primitives.

I would have attached a binary executable to show you, but the Board is still a little wiggy.."An Error Has Occurred!
Cannot access attachments upload path!"

If you are interested in the source, are interested in becoming involved in betatesting, or think you might be able to contribute in some other way, please let me know.
Posted on 2006-02-28 23:29:43 by Homer
Hi Homer
I値l be glad to take a look into the source code.
My interest focus lays in first place on the code construction and in second place the logic you have used.


Posted on 2006-03-01 00:42:07 by Biterider
Cool, I'll send you source directly when I see you online next.. I found another three optimizations at the algorithmic level today :D

A guy called Nathan Whitaker wrote a tutorial on BSPTree construction for Leafy Trees in which he said something along the lines of "so now that we're no longer storing Faces at the Nodes of the tree, what do we do with the Faces we used to form Splitting Planes? We throw them down the Tree like any other face, marking them so we don't use them again"..

It got me thinking : yeah, ok, but what about any OTHER faces that happen to be coplanar with the splitting plane? Is this not true of those faces also?

Now I've made the whole thing smarter, because I've realized that "all coplanar faces, including the splitterface, can be distributed any way we like" - that means in many cases the balance of faces can be improved or even perfected, and that a set of faces that is "totally coplanar" is in fact "convex", and can be treated as such.

You'll have to excuse the fact that I've disabled and/or removed code relating to the handling of "split faces" due to my preoccupation with improving the two main algorithms (choosing a splitting plane, and distributing the faces either side of it).

Posted on 2006-03-01 08:00:55 by Homer
back to terrainengines:
if you instead construct terrain more object oriented, outta hill1,hill2 ,valley1,valley2, etc, instead of heightmaps
and do that in combination of using BSP tree's if you can see Hill1, but Hill2 is hidden and so is valley2 etc

for example a small terrainarea is composed outta Hill1-4 and valley1-2 and leveled plain 1-4 and stonebridge  5
instead of load heightmap, you instead load the objects not yet in memory before entering this area
now why not use BSP tree twice? one time for visible surfaces to render, and one time for determine readahead objects on disk.
must be less diskload when you use Hill1 instanced several times and no diskload if it already been used in previous terrain
now maybe we even can use BSP a third time, to determine the stonebridge you left far behind you is time to release that object to free up space for other objects that need to be readahead

what I understood, you are climbing around in that BSP tree and current node is where you are, neighbouring nodes are what needs to be read, farthest away nodes is what need to be released
Posted on 2006-03-04 05:10:28 by daydreamer
I wrote a huge reply to this posting yesterday, but my videocard is crashing my machine intermittently (thermal fault), and I'm too lazy to type all of it again, so here's the short version.

BSPTrees split the world into ever-smaller pieces, where each piece is approximately half of the input.
The root node of a BSPTree cuts the world into halves, stored as two child nodes, and this process is repeated until a node contains a single face, a convex set of faces, or some other preset limit we imposed.

There's basically two kinds of BSPTree, they are called Nodey and Leafy.

Nodey trees have some geometry stored at the Nodes of the tree, whereas Leafy trees store ALL the geometry in the LEAFNODES of the tree.

I'm predominantly interested in Leafy Trees because of certain properties of the LeafNodes.. for example, each LeafNode represents a convex subspace defined by the planes of the Faces it contains and the planes of its Parent nodes.
Convex sets can be rendered in any order without causing error (no occlusions), which is cool, and LeafNodes represent "places we can go".
The major error of your assumption is that we can travel from one leafnode to another by following the BSPTree.
The BSPTree has nothing to do with linking leafnodes together.
We need to create links between leafnodes ourselves, which are known as PORTALS.
Portals are "the places where walls are not", ie "holes".
We can discover them automatically.
One of the clues we are handed is the knowledge that "portals can only exist on the planes of non-leaf bsp nodes".
Non-leaf nodes MAY contain Portals, but they may NOT.

If you want more information regarding BSPTrees, and how they relate to passive culling and collision detection acceleration, let me know.

The only other thing I really wanna say regarding your posting is that yeah, we can store an entire BSPTree on disk, and so long as we "write the nodes in the same order as we normally walk them", we can walk the tree directly from disk at runtime, its not necessary to have the entire bsptree in memory at once.
Posted on 2006-03-05 23:06:50 by Homer