Sign in to follow this  

OBB Collision

This topic is 4092 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have found some algorithms for detecting collision between the boxes but for calculating a reasonably tight box I havent really been able to find many examples. Any suggestions?

Share this post


Link to post
Share on other sites
One way I can think of is a brute-forceish way that checks per rotation degree how large the resulting OBB is. When you consider this only needs to be done once, it might suffice. Might get tricky for 3D objects though.

An alternate method could be to search for the top, bottom, most-left and most-right vertex and trace lines between them, then check if there are any vertices outside the resulting rectangle. If so, add those vertices to the list and repeat the process, so to create a convex hull for the object. Then, project the hull on 2 (or 3) axis, once for each edge. Then it's a simple search for the smallest projection dimensions.

Then again, that's just what I can think up on right now. I don't know how how efficient it is, nor how easy it is to implement. Hope it helps. :)

Share this post


Link to post
Share on other sites
The standard algorithm for determining a suitable OBB for a point set involves computing the covariance matrix for the set and then extracting the eigenvectors. Building an OBB tree using this method is covered in a paper by Gottschalk, et al. It's a fairly old paper, but you might still be able to find it online. The algorithm is not perfect though, and sometimes returns non-optimal results (IIRC).

I would recommend bypassing this process if it's at all an option for you. For example, an object's local space AABB transformed by the matrix that transforms the object is often a perfectly suitable OBB for the object.

Share this post


Link to post
Share on other sites
To find the tight box you can use a covariant matrix and eigenvector and eigenvalues... the complet process can be found in the paper os OBB, that the link is below! And this method is quite fast

ftp://ftp.cs.unc.edu/pub/users/manocha/PAPERS/COLLISION/obb.ps.gz

Tree: A Hierarchical Structure for Rapid Interference Detection , S. Gottschalk, M. C. Lin and D. Manocha (27 pages PostScript, ) 493K, Technical report TR96-013, Department of Computer Science, University of N. Carolina, Chapel Hill. Proc. of ACM Siggraph'96.

hope that i helped!

PS: brutal force is inviable - 360 x 360 x 360 x nVertices x MultByMatrixRotation x computeOfBoundaryBox x testToSeeIfIsTheTightBox

Share this post


Link to post
Share on other sites

This topic is 4092 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this