[QUESTION] BSP Tree usage in .WMO

[relaxok]

[note: this refers to 3.3.5 client data]

I am working on a client and server from scratch and have recently gotten to the point where I'm interested in WMO collision (e.g. for the purposes of walking on bridges and such).

I have included the BSP tree data in my conversion to my model, so I'm sure I have all of the LEAF nodes drawing properly.  In this SS of my client I've disabled normal mesh rendering and am drawing only BSP LEAFs - you can see all leaf nodes drawing, each leaf with a random color:

http://24.media.tumblr.com/tumblr_m9wz5ndTrp1rsifdno1_r1_1280.png

The next issue of course is traversing the tree for collision purposes.  Because this is tricky due to coordinate system issues (I'm pretty sure my planes will be different axes than WMO uses), I'm taking my Model Viewer app (separate from client) and have some debug code to draw at the supposed location of each plane.   I use Y-up so I will refer to Y that way.   Several places in WoW data do not, so let's take that into consideration.  I have attempted all sorts of axis swaps in case the BSP tree is different coordinate-wise, but still end up with problems.

For test purposes i'm using the following .WMO that I've converted - in case anyone wants to refer to it:

WMO/Lorderon/Buildings/Ghostlands/Footbridge/Ghostlands_Footbridge.wmo

The start of the tree according to some info on the wiki, is the start of the bounding box.  I call this 'ROOT' with debug text.  Node 0 i would think would refer to the start of the bounding box as well, but actually does not?  The first node is an XZ plane with a distance of -3.0f.  I would expect 0.0f.  Anyway,  because this bridge is basically a 'mirror' image', it wouldn't really make sense to me for the location of the first split plane to have anything other than a height offset from the middle of the bounding box, but I don't know..

I then draw a text indicator with the distance offset being a new plane location in one sepecific axis direction, and so on from there.  You would expect that even by the final leaf nodes, you are still drawing within leaf mini-bounding boxes that are all within the context of the model's geometry itself.  In this video however using this current method of offsets (and any other axis swaps I try) you end up far away from the model coordinates.

http://bh.polpo.org/bsptreefail.wmv

So my question is, is the distance float in each bsp node in the same unit scale as the model?  Is it supposed to be an accumulation of offsets as you traverse the tree?  I assumed so, so the basics of my code do this:

Code: [Select]

void CModelBspTree::drawNode( CModelBspTreeNode* node, XMFLOAT4 position )
{
std::string planeStr = "";
if( node->planeType == EModelBspNodePlaneType_XY )
{
planeStr = "XY ";
position.x += node->fDistance;
}
else if( node->planeType == EModelBspNodePlaneType_XZ )
{
planeStr = "XZ ";
position.y += node->fDistance;
}
else if( node->planeType == EModelBspNodePlaneType_YZ )
{
planeStr = "YZ ";
position.z += node->fDistance;
}
else if( node->planeType == EModelBspNodePlaneType_Leaf )
{
planeStr = "LEAF ";
assert( node->fDistance == 0.0f );
}

// draw node string and depth @ position

if( node->children[0] < 0 && node->children[1] < 0 ) return;

if( node->children[0] >= 0 )
{
drawNode( nodes[ node->children[0] ], position );
}

if( node->children[1] >= 0 )
{
drawNode( nodes[ node->children[1] ], position );
}
}

Ignoring the axis for a second (the above is just in the middle of trying various combinations, i've obviously tried them all), has anyone attempted to do something similar to debug the positions of bsp locations?

Would be interesting to hear thoughts.

[schlumpf]

The positions are not relative to the parent node, but always in relation to (0, 0, 0).

At least as far as I know.

[Cromon]

Steff sent me the thread this morning so i made a quick visualizer from scratch this evening. I guess it should be sorta like this, right:


/Code follows a bit later, just found a little bug.

[relaxok]

Steff sent me the thread this morning so i made a quick visualizer from scratch this evening. I guess it should be sorta like this, right:


/Code follows a bit later, just found a little bug.

Cromon - Great,  that should really help - and yes that's exactly the sort of tool I was making to visualize it while working on collision!

Schlumpf - hmm yes I tried that before but thought it can't be possible because then all plane split points are along the same axes as the center of the original bounding box, you couldn't ever subdivide in other areas.  (i will attach an SS of trying that later) - but it does make sure the leaf points are within the geometry for sure.

When Cromon posts code for the above that will clear things up for me.. I'll also probably update Wiki based on it if necessary.  It looks correct to me.

[Cromon]

Video:


Code:
http://fbe.am/bZx

[relaxok]

Video:


Code:
http://fbe.am/bZx

Great - the slicing method there is what I was concerned with.  I think that is different to how I understood the info on the WMO wiki page, so I'll try to clarify the text there.

Thanks Cromon!

[tharo]

Gamh and my humble self also tryed a bit around and thought this might looks more usefull:


[attachment=0:15wjh3yb]house.gif[/attachment:15wjh3yb]

[MR. Farrare]

very helpfull keep the good work  

[tharo]

Okay after debugging some files with this new. amazing but never gonna to be released bsp viewer of ours, i came to some conclusions that might help everyone doing a correct bsp rendering:

- calculate a global bounding box by taking the minimums and maximums of xyz your model donates. maybe add 0.001 to it .. just to make sure
- Do a 'one point of the surface is in a bounding box' checkup
- Split your boxes until you have not more than remaining 45 faces in it.
- dont hesistate to have the same surface in many boxes. its better than leaving unhandled spaces! if your surface is quite big an bend over many boxes each of them need to handle this surface!
- take care to handle each surface as least once
- dont care about f-dist too much. of course you can use it to adjust the proportions of your bsp-boxes but if you leave it buy 0 nobody will die