BSP Tree (WMO)

[abdalrahman9]

Hello there, now i am trying to create a bsp tree from a 3ds max scene with using maxscript but lately i have been having some trouble with it. I am not a programmer so i don't have the fundamentals that are found in other people. So from what i know, to generate the BSP tree you have to separate the scene into multiple sections which are nodes. Through those nodes, you are suppose to find the the first face that appears. I had looked at the wiki where there is a (c++?) script to generate the bsp tree but i am coding in maxscript and not to mention i would to actually learn how to do it. So i have several questions:

1: How is the first face determined? like what is the point that you take as your reference. Would it be the (0,0,0)??

2: Now the planeType, there are four types and i am guessing this refers to the cut of the node and it can be xy, xz, and yz. But what is the leaf? From what i looked up, the leaf is the node that has no children so what does that have to do with the type of cut?

3:How would i type the code anyways? Like what should i start off with? Should i create dummy planes in the scene to represent the plane cuts which isn't really intelligent as i am sure there is a better way but right now i got no idea how i am suppose to generate the code in 3ds max. Any tips would help!

4:Also, how many cuts or nodes should i do for each object? Like if it is only a box i know i shouldn't be doing many cuts but does the amount of cuts depends on the number of faces/vertices? Like if i had 25 faces there should be only 5 cuts?

Lastly, thank you for reading.

[schlumpf]

Note that the code seems to be for testing, not creating the tree.

• as far as I know there is no requirement on the quality of the tree, as long as it is correct. one could probably just always start with the xy plane at 0,0,0. An actually good point to start would be the middle/average of all vertices though. I'm not sure if there is some kind of face limit per leaf so one possibly even has to. The limit of faces in a node might be limited to 8192.
• the leaf node does not have any more children but just marks that there are no more cuts. it will have no values for children and distance, but will list the faces it contains.
• I have no idea how you would do it with your maxscript requirement. Unless you're writing into the output who file, it seems to be the wrong place to do it.
• as with 1), I think there aren't strict quality requirements. Try to stay with reasonable numbers.

As indicated with 1) and 4), I wouldn't even start with properly cutting but rather just do a one-node "tree" that has just a leaf node with all faces. It might work quite well.

[abdalrahman9]

First of all thanks for the reply.
1: Wow never knew that the code was for testing, thanks for the heads up!
2: Now i am outputting the tree to a file outside of maxscript and i have tried to just output one node leaf which contains all the faces. Now wouldn't this cause problems when the object has a large number of polygons?
3:About where my reference point would be, where in the wmo does the position of the starting point get placed in the wmo file? Or does it not get placed because how would you know if one wmo has a different starting point than another wmo? or does it even matter at all?
4: Also you said that the best starting point would be the middle average of the vertices. However, wouldn't that mean that the starting point would eventually lye in at least one node/leaf? Would that be okay?

[schlumpf]

[list type=2][li]yes[/li]
[li]the first plane is relative to (0,0,0)[/li]
[li]I guess it would be okay. you can also just take some random plane and put the first plane (-1,0,0) from it and begin there. except for resulting in pretty shit trees, everything should work just fine.[/li][/list]

[abdalrahman9]

Okay thanks for the reply. I will try to start and hopefully i can do it. Just one more quesiton:
1: What do i do if one of the planes intersect one of the faces? So i consider that face in both the nodes or only one or is there a way to avoid something like that?

[schlumpf]

I would add it to both.

[Gamh]

As indicated with 1) and 4), I wouldn't even start with properly cutting but rather just do a one-node "tree" that has just a leaf node with all faces. It might work quite well.

I second that, especially if your model is small enough (a small house, a rock, etc). For bigger models, you will have problems at some point, I don't remember what the threshold is exactly, but collisions will start to misbehave.

If you really want to generate your own, here are BSP tree generators I coded a while ago with Tharo, if you can shift through the awful style : C++ and Python. They aren't perfect because they do not check if a triangle goes through a node without having vertices in it; it then has no collision. This can happen when there are "stretched triangles", with one vertex being far from the two others.

[abdalrahman9]

Thank you Gamh, hopefully this will help me in writing my own bsp tree. I appreciate it!!

[abdalrahman9]

I have another question, now we know that the first plane's distance is based on the origin (0,0,0). However, what of the second cut/plane? Is it's reference on the position of the new plane or still the origin (0,0,0)? The wiki states that the reference changes with the plane but i am not sure if that is the case. I am using the WestFallLightHouse.wmo as my test wmo because it has only one group. When i tried creating the bsp planes in 3ds max it seemed that the plane's distances were based on (0,0,0) though i only did the first couple. Yet, there are those that have the same distance with the same plane type which is very weird. An example is nodes 7 and 8 which are both plane types 0 and distance of 6. The only difference between them is the children. Why would they create two planes/cuts in the same place but then have different children? Does this mean the distance is based on the parent plane or am i just not understanding something?

[Gamh]

Does this mean the distance is based on the parent plane or am i just not understanding something?

No I think you're right, the fDist value is relative to the parent node, or maybe from (0, 0, 0). The wiki explains that better than me:

fDist is where split plane locates based on planetype, ex, you have a planetype 0 (YZ-plane) and fDist 15, so the split plane is located at offset ( 15, 0, 0 ) with Normal as ( 1, 0, 0 ), I think the offset is relative to current node's bounding box center. The BSP root ( ie. node 0 )'s bounding box is the WMO's boundingbox, then you subdivide it with plane and fdist, then you got two children with two bounding box, and so on. you got the whole BSP tree.

Also fun fact, despite being a float fDist is always an integer value.

[abdalrahman9]

Ya i did read the wiki before but just wanted to make sure, I am guessing it is based on the parent node. So after the first node which has a reference of (0,0,0) the rest of the planes will be referenced from the new location of their parent planes.

Also fun fact, despite being a float fDist is always an integer value.

Ya i realized that, it is so weird to why would they make it a float and not an integer!!