Who is interested in writing a BSPTree Generator?
I propose an xfile-->bsptree converter, final file format similar to Quake files (IBSP)

It should be possible for the user to select the root plane manually, and the output bsptree should be self-optimizing, via a recursive approach to best-node-selections (keep runtime statistics on tree depth / branch factoring so the app can "discover" the most optimal order of planes).

BSP too redundant for you guys?
Posted on 2004-07-04 01:20:00 by Homer
The two major options to choose from are called Nodey BSP and Leafy BSP.
In Nodey BSP, the geometry is scattered throughout the nodes of the tree.
In Leafy BSP, geometry is stored only in the Leaf nodes.
I will describe the Leafy case.

In either case, the generator is supplied with a list of triangles, a "triangle soup", which is to be processed.
We create a Root BSP Node, and place the list (pointer) inside the Node, because at the moment the node owns All the geometry.
In our case, if the source was an xmesh, then we could use face indices during processing, and indexed vertices as well.
We would wish to create a "split-optimized tree", where we attempt to avoid splitting faces by selecting them in the optimal order of processing. We need to select a face to begin with.
Which one will we choose?
We need to choose one which produces few splits.
But there is secondary consideration, we want to have a relatively balanced tree. Having a balanced tree isn't as important as having few splits, but it does matter to us, so we'll need to attempt to select an initial face which produces few (or no) splits, and has relatively the same number of faces on either side of its plane. Therefore we should categorically compare each face against all other faces, recording the statistics as we go for the face which best suits our purpose.
Having selected the best face, we should create two Child BSP nodes and move all the triangles on each side of the bestface's plane into each of the Child BSP Nodes, such as they own all geometry on either side of the "current" plane.
Note that the geometry has now been moved down from the root node into the child nodes, the list has been split into two lists of approximately half the original.
We now recursively reprocess each of the Lists, sorting their lists again and again until we hit some minimum theshhold value for the #triangles in our leaf nodes. If we kept going, we'd end up with leafnodes that contained 0 unsorted triangles, which may not necessarily be bad.
Does this sound difficult to code?
I note that new Nodes are added linearly , never removed or moved, and as such, a simple linear array would serve, no need for linklists here...
Posted on 2004-07-05 03:39:48 by Homer
Well, I've posted some code in another thread for classifying a point against the plane of a triangle, and I've since written code to classify a triangle against the plane of another triangle.
Most importantly, I've written a function to select one triangle from a soup whose plane forms the most ideal split-plane, which produces the least splits while maintaining polygonal balance in the output tree.
It's meant to be called from within an iterative tree-building function which is pretty much also written.
So far I've only worked with sample triangles.
The time has come for me get some some REAL triangles imported into my application, and the easy way for me to do that is to simply load a mesh and read its geometry into my application then discard it.
That will be next.
Looks like I'll be posting some code sooner than I thought :)

Still not much interest in this thread :(
Ah well.
Posted on 2004-07-06 03:25:48 by Homer
I've added Windows code, implemented a basic Mesh loader and triangle extractor.
First I was extracting full vertex data per triangular face. Then I realized I was wasting the IndexBuffer. So now I extract only the Index values which represent vertices, and not looking them up.
Therefore a Triangle is stored as just 3 word-sized indices, and we must retain the VertexBuffer content from meshloading.
I open the VertexBuffer as Read-Only, which will need to change since we will for sure generate some SPLITS in polygons as we process the tree.
Happy Days :)
Posted on 2004-07-06 05:54:32 by Homer
Hi EvilHomer2k,

I'm following your thread, interested in your research and thoughts. I'm busy learning OpenGL, I think you do work in DirectX if I'm not mistaken. But your concepts should apply! What is the thread you posted your code to. Please continue, although this is not my current interest in OpenGL, I expect to be doing my own BSP tree research soon, so your experiments/knowledge/comments and some source would come in handy!

Regards
Posted on 2004-07-07 07:26:29 by SubEvil

Hi EvilHomer2k,

I'm following your thread, interested in your research and thoughts. I'm busy learning OpenGL, I think you do work in DirectX if I'm not mistaken. But your concepts should apply! What is the thread you posted your code to. Please continue, although this is not my current interest in OpenGL, I expect to be doing my own BSP tree research soon, so your experiments/knowledge/comments and some source would come in handy!

Regards


Here here. I also read your posts to learn more.
Posted on 2004-07-07 10:52:00 by mark_larson
Code for geometric classification was posted in the thread called "Triangles and the Plane Equation".
I'll post the whole lot pretty soon, I'm currently only being held up by the procedure which selects "the best triangle from a soup".
Posted on 2004-07-08 00:23:06 by Homer
I've not resolved the issue in the "best poly" function, so I'm going to post the code for that, maybe one of you can spot the issue (been staring at this too long).



;================================================================
;ChooseDividingPolygon
;---------------------------------------
;pPolygonSet - The set of polygons to search for the best dividing polygon.
;Returns: The best dividing polygon
;Effect: Searches through the set of polygons and returns the polygons that
; splits the set into the two best resulting sets. If the set is
; convex no polygon can be returned.
;================================================================

.data
MINIMUMRELATION FLOAT 0.8f
MINRELATIONSCALE FLOAT 2.0f
NOPOLYGON equ 0

.code
ChooseDividingPolygon proc pPolygonSet
local BestRelation
local BestPolygon
local LeastSplits
local NumPositive
local NumNegative
local NumSpanning
local fMinRelation
local fRelation
local P1
local NumEntries
local CurrentPolygonIndex
local pTestPoly
local ppolygonset
set ppolygonset as CVector

m2m ppolygonset,pPolygonSet
.if ($invoke (IsConvexSet, ppolygonset)) == TRUE
return NOPOLYGON
.endif

mov BestRelation,0
mov BestPolygon, NOPOLYGON
m2m fMinRelation , MINIMUMRELATION
mov LeastSplits , -1 ;=INFINITY

; // Loop to find the polygon that best divides the set.
.while BestPolygon == NOPOLYGON
Message "Searching..."

mov ebx,ppolygonset ;<---- Get the #Entries in the array
mov ebx,[ebx].CVector.dwNextPlace
shr ebx,2
mov NumEntries,ebx

xor ebx,ebx
mov CurrentPolygonIndex,ebx
.while ebx < NumEntries; for each polygon P1 in PolygonSet
startstack
$Message "CurrentPolygonIndex= %lu",CurrentPolygonIndex

mov P1,$pcall (ppolygonset.GetByIndex, CurrentPolygonIndex)
$Message "pPolygon1=%lx",P1
; .if (Polygon P1 has not been used as divider previously during the creation of the tree)

; // Count the number of polygons on the positive side, negative side
; // of and spanning the plane defined by the current polygon.
mov NumPositive , 0
mov NumNegative , 0
mov NumSpanning , 0
xor ebx,ebx
.while ebx < NumEntries ; for each polygon P2 in PolygonSet except P1
push ebx
mov pTestPoly, $pcall (ppolygonset.GetByIndex, ebx)
.if eax!=P1 ;<--We don't want to classify poly against itself !!
; $Message "%lX", pTestPoly
invoke CalculateSide,P1,pTestPoly
.if eax == INFRONT
inc NumPositive
.elseif eax == BEHIND
inc NumNegative
.elseif eax == SPANNING
inc NumSpanning
.endif
.endif
pop ebx
inc ebx
.endw

; // Compare the number of polygons in the two sets divided by the current polygon.
mov eax,NumPositive
.if eax < NumNegative
fild NumPositive
fidiv NumNegative
fstp fRelation ; = NumPositive / NumNegative
.else
fild NumNegative
fidiv NumPositive
fstp fRelation ; = NumNegative / NumPositive
.endif

; // Compare the results given by the current polygon to the best this
; // far. If the this polygon splits fewer polygons and the relationship
; // between the resulting sets is acceptable this is the new candidate
; // polygon. If the current polygon splits the same amount of polygons
; // as the best polygon this far and the relation between the two
; // resulting sets is better,then again this polygon is the new candidate
; // polygon.
fld fRelation
fcomp fMinRelation
__FJG @F
mov eax,NumSpanning
mov ebx,BestRelation
.if (eax < LeastSplits) || (eax == LeastSplits && fRelation > ebx)
m2m BestPolygon , P1
m2m LeastSplits , NumSpanning
m2m BestRelation , fRelation
.endif


; .endif

@@:
Message "Outer Loop"
inc CurrentPolygonIndex
mov ebx,CurrentPolygonIndex ; <--- update ebx for loop control
endstack
.endw

; // Decrease the number least acceptable relation by dividing it with a predefined constant.
fld fMinRelation
fdiv MINRELATIONSCALE
fstp fMinRelation
Message "Outermost Loop"
.endw
return BestPolygon
ChooseDividingPolygon endp


Any questions, or want to see dependant code?

The problem I'm having is that in the second iteration of the outer loop the pointers from the array are being returned with an 80 in the front byte, for example if the array returned 00A02BE0 the first time around, it becomes 80A02BE0 after the first iteration - and all I'm doing is fetching values from the array !!
Posted on 2004-07-08 20:15:16 by Homer
Probably you want to see this too:

CVector_GetByIndex proc dwIndex
mov eax,dwIndex
shl eax,2
add eax,.CVector.pBase
return dword ptr
CVector_GetByIndex endp

(Note: ecx=pThis, a pointer to the instance of CVector)
Posted on 2004-07-08 20:32:12 by Homer
There was nothing wrong with the code I posted.
The problem was in "CalculateSide", I was clobbering ebx.
Blunderful.

Happy Days :)
Posted on 2004-07-08 22:53:16 by Homer
Here's the codebase I said I would post soon.
This represents the current state of the project.
Posted on 2004-07-08 22:55:31 by Homer
I've just realized that CalculateSide still won't wok at the moment, because I changed the definition of a "triangle" to use indices into a vertexbuffer and not contain actual vertex data.
All I have to do is add a couple of lines to look up the vertex data.
I can't be stuffed at the moment :tongue:
Posted on 2004-07-08 22:58:49 by Homer

I've just realized that CalculateSide still won't wok at the moment, because I changed the definition of a "triangle" to use indices into a vertexbuffer and not contain actual vertex data.
All I have to do is add a couple of lines to look up the vertex data.
I can't be stuffed at the moment :tongue:


You can't be "stuffed" or you can't be "stopped"? ;)
Posted on 2004-07-09 17:47:57 by mark_larson
..for We are the Makers, and We are the Dreamers of Dreams.
Posted on 2004-07-09 23:32:54 by Homer
I've written the code which drives the polygon sorter (the actual Tree-building code), now just one thing remains to complete this project (less debugging), and that is a function to SPLIT a triangle (using a plane).

If two of the triangle vertices are on the plane, then no split is required after all - the triangle is abutting the plane.


/
/
/
/
/
/
/ =======
/

If one of the triangle vertices is on the plane, then we split the triangle into two triangles.


/ /
/ /
/ /
/ /
/ =======
/

If NONE of the triangle vertices are on the plane, then we split the triangle into THREE triangles (one triangle for the vertex on its lonesome, and two triangles for the other side of the plane)


/
_/__\__________
/
/
=======

Masterpiece of ascii art :tongue:
Posted on 2004-07-10 02:05:13 by Homer
I missed one case in that ascii, so here's my original scrap note.
This is genuine napkin material :)
Posted on 2004-07-10 06:07:53 by Homer
For anyone following this thread, I have attached the not-complete-nor-working triangle splitter function, so you can see where I'm going with it.
Posted on 2004-07-10 10:10:45 by Homer