OBB Collision
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?
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. :)
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. :)
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.
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.
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
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement