math & physics
misc at March 9th, 2010 07:50 — #1
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.
vrnunes at March 9th, 2010 08:46 — #2
you check against those leaf bsp planes, and if the object being tested is behind any of the convex planes... you got a collision.
misc at March 9th, 2010 10:15 — #3
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,
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).
reedbeta at March 9th, 2010 12:08 — #4
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.
vrnunes at March 9th, 2010 13:40 — #5
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.
misc at March 9th, 2010 16:39 — #6
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