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?

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?

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...

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...

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.

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.

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 :)

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 :)

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

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

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.

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".

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".

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).

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 !!

```
```

;================================================================

;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 !!

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)

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)

There was nothing wrong with the code I posted.

The problem was in "CalculateSide", I was clobbering ebx.

Blunderful.

Happy Days :)

The problem was in "CalculateSide", I was clobbering ebx.

Blunderful.

Happy Days :)

Here's the codebase I said I would post soon.

This represents the current state of the project.

This represents the current state of the project.

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:

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:

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"? ;)

..for We are the Makers, and We are the Dreamers of Dreams.

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:

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:

I missed one case in that ascii, so here's my original scrap note.

This is genuine napkin material :)

This is genuine napkin material :)

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.