BSP Collision

E29af0e3e1f084aaaaf3a42bb2481b48
0
misc 101 Mar 09, 2010 at 12:50

Im a little confused as to how collision is performed within a BSP tree, specifically the enviroment. From my understanding the tree is traversed, and any nodes that intersected that happen to be leaf nodes have their data collision checked.

That being, in the Quake 3 format, nodes have a left and right child. Where these nodes can be of 2 types, BSP tree nodes, or leaf nodes. BSP tree nodes mark that the child has further children to traverse. Where as the leaf node types marks the end of traversal of this route, and contains data for that node for rendering and collision detection.

Whilts I understand how this works for scene objects. In that the leaf node contains a list of collision brushes. Where each brush is the convex hull of a scene object. I dont understand how you are supposed to check for collisions agains the enviroment, that being the walls,floor and ceiling. Is this data stored in brushes as well? I dont see how that would woek as this enviroment data isnt convex.

5 Replies

Please log in or register to post a reply.

17ba6d8b7ba3b6d82970a7bbba71a6de
0
vrnunes 102 Mar 09, 2010 at 13:46

you check against those leaf bsp planes, and if the object being tested is behind any of the convex planes… you got a collision.

E29af0e3e1f084aaaaf3a42bb2481b48
0
misc 101 Mar 09, 2010 at 15:15

Hmmmm. Are you saying that each leaf should contain a list of planes that form a convex shape to be collision tested against? Im looking at the leaf node,

http://www.mralligator.com/q3/#Leafs

and it doesn’t mention anything about storing a list of planes. Only faces, which are used for rendering geometry (which dont have plane data, and I assume wont form a convex shape).

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Mar 09, 2010 at 17:08

The environment may not be convex as a whole but the BSP divides it into convex regions. Each leaf is such a region. While I’m not specifically familiar with Q3 I would guess each leaf contains brushes representing the portion of the environment in that leaf. A brush comes down to a set of planes and its interior is defined as all the points that are behind all of those planes.

17ba6d8b7ba3b6d82970a7bbba71a6de
0
vrnunes 102 Mar 09, 2010 at 18:40

yes, there is plane information there, at the brushes… it is even mentioned there in the link you provided as well. look there for leaf brushes again.

just correcting myself: if the object is behind *all* (not any) planes of the leaf, then you got a collision.

E29af0e3e1f084aaaaf3a42bb2481b48
0
misc 101 Mar 09, 2010 at 21:39

Sorry. When they refered to brushes, I thought that specifically meant the collision mesh for scene objects, bot for the enviroment as well. That was my confusion.

Thanks for your help