Next goal: Oriented Bounding Boxes

I’m thinking of creating oriented bounding boxes, and from that OBB trees for a collision detection system.

Anyone got any suggestions on how to go? I’m thinking I should extend Box. When the OBB is transformed, just set the local translation/rotation of the OBB. When I have to tell what side of a plane the box is on, I would transform the 8 corners of the box and see if they are on the positive or negative side of the plane.

Most implimentations I see define OBB as 3 axis, an extent, and a center. But that’s already there in jME with translation/rotation/scale, so I figure the fastest way would be the above. Suggestions?

OBB are in CVS. Test class com.jme.renderer.TestOrientedBox Suggestions on improvments are welcome. It’s definantly not the best way to do plane testing, so improvments could be made there. OBB are a tiny bit slower to update than AABB (that’s a given) but they make a much tighter fit which allows for more exact intersection testing and greater probability of culling which can result in speedups if draw is your bottleneck. All of the utility functions for OBB like intersection are forthcoming. Input appriciated.

Sadly, I’m no match for the experience of David Eberly. I’ve implimented most his magic software code for OBB. There’s intersection of two OBB, intersection of ray and OBB, screen area of OBB, and much faster view culling of OBB in CVS. The only other thing is to add merge functions that combine AABB/Sphere to OBB and they’re complete.

and adding the ability to set Orientated bounds in the JmeBinaryLoader :wink:

PS. Very nice


OBB is complete and should play nice with what’s already here. If anyone has a jME program going, if you could just try it out for one run with OrientedBoundingBox and let me know how it goes, that would be great. In my test, it seems to be almost as fast as the other bounds, but much smaller.

a bit of a question/observation on OBB. If I turn on bounding in TestCollision, I see the AABB for each box and the combined AABB which grows and shrinks with the positions of the two boxes. That seems right and well… But if I replace the two AABBs for OBBs, the combined OBB never grows and shrinks and so doesn’t seem the tightest possible bounding box as one might think OBB to give.

Recomputing an OBB every frame is an expensive operation. What it does is calculates an approximation when updateModel is called, and then just rotates the bounds when the object rotates.

My initial bounds isn’t a tighest fit though. There’s a somewhat complex algorithm to do that, which I’ll try to figure out some time soon.

After Renanse mentioned this, I gave it a try and also replaced BoundingBox with OrientedBoundingBox in TestCollision. I did notice some oddities. For example, single boxes are no longer culled, culling only occurs when the large box is off the screen.

I’m curious, how do you calculate this parent bounding box if it doesn’t grow? In the test it’s large enough to contain the boxes at all times during their travels, but how did you do this? And how would you handle a box traveling randomly for awhile, if the boundings are not updated and merged properly, culling will break.

Mojo: Bug fix was commited. It should now work. I had POSITIVE when I should of had NO_SIDE

renase: The way I combine is some complex algorithm I found at magic software. It combines fast, but not exactly. To create an exact bounding volume, I would probably have to compute each corner, then create a bounding volume from those corners, which is what I do in the commented out code. I’m not sure which is faster. Usually, the combining algorithm does pretty good.

Just it looks pretty odd… the box never shrinks even though the two boxes come together at the same pointin space. Maybe you can try the test mentioned above and see that for yourself. It scares me a tiny bit… what will more complex tests result in…?

Yea I did try it. It doens’t look pretty at all. My money’s on the idea I’m just using the algorithm I got wrong. I’ll give it some more research.

Nod, let me know if you want a second pair of eyes on that. I’m pretty familiar with Eberly’s code by now.

That would def be helpful. The code I’m implimenting currently is off his website.

Ok, found one bug in the merge code. In one case (kMin and kMax) your temp vectors are accumulating results and spilling them over to the next merge call. calling .zero() on them before use took care of that. The results look great!

Also, the computeCorners() function you had in OrientedBox was pretty hard on the eyes and filled with divisions and dot products. I’ve replaced it with something simpler from eberly that is easy on the eyes and possibly faster (adds and subtracts, no divisions or dot products!) Your code is still there, commented out for reference.