Archived

This topic is now archived and is closed to further replies.

Arkion

Collision detection between Solid BSP tree and OBB?

Recommended Posts

I'm using a Solid BSP tree and dynamic plane shifting technique (described in "Dynamic Plane Shifting BSP Traversal", S. Melax) for efficient and reliable collision detection. Leaves of the tree are either flagged as solid (impassable) or empty. The paper describes how to test sphere and cylinder against the tree for collisions. Does anyone know if it's possible to test Oriented Bounding Boxes (OBB) using this technique? I'd be very grateful for pointers to detailed information on how to do that. TIA. [edited by - Arkion on August 13, 2003 5:30:04 PM]

Share this post


Link to post
Share on other sites
as far as I remember, the fat-BSP requires only a function that outputs the support vertex of an object along a plane normal. So in that case, the beveled plane equation for a given box is

d = (N * Box.Centre) + fabs(N * Box.DirX) * Box.HalfSize.x + fabs(N * Box.DirY) * Box.HalfSize.y + fabs(N * Box.DirZ) * Box.HalfSize.Z;

(N.x * x) + (N.y * y) + (N.z * z) + (-d) = 0

Centre is the centre of the OBBox. DirX, DirY, DirZ is the orientation of the OBBox, HalfSize if the extent of the box along DirX, DirY and DirZ. N is the normal of the plane.

Share this post


Link to post
Share on other sites
actually, I was a bit too quick on that. The way I understand the algorithm, you have a plane equation in the BSP stored as

(N.x * x) + (N.y * y) + (N.z * z) + d = 0

and you simplify the BSP/OBB collision by reducing the test to a single ray with beveled planes. Then the beveled plane becomes

r = fabs(N * Box.DirX) * Box.HalfSize.x + fabs(N * Box.DirY) * Box.HalfSize.y + fabs(N * Box.DirZ) * Box.HalfSize.Z

(N.x * x) + (N.y * y) + (N.z * z) + (d+r) = 0

and you cast a ray from the box centre along the box displacement.

I am not sure if it is (d+r) or (d-r) in the plane equation, but it should be pretty clear once you try both if aren''t sure yourself.

Share this post


Link to post
Share on other sites