An Exact Algorithm for Finding Minimum Oriented Bounding Boxes [pdf] | Hacker News Reader

An Exact Algorithm for Finding Minimum Oriented Bounding Boxes [pdf]

clb.demon.fi

67 pointsvmorgulis19 comments

That's neat. But the comparison time for oriented bounding boxes is no better than that for convex polyhedra, if you use incremental GJK.[1] It does, however, take less code, and the termination condition for GJK in the presence of roundoff error is quite difficult. If you do implement GJK, be aware that testing it with random polyhedra is not a good test. The hard cases appear when two objects are coming into contact and their face planes are becoming parallel. Since this is what usually happens whenever an object comes to rest in a simulation, that edge case comes up in practice.

Axis-oriented bounding boxes are cheap to test, but bounding boxes oriented to the object are really just convex polyhedra with 6 faces.

Lots of collision detection articles today.

[1] http://www.cs.ox.ac.uk/stephen.cameron/distances/

I don't understand your comment. You say OBB isn't any better than GJK on arbitary convex polyhedra. Followed by saying GJK has issues with roundoff. And that testing it with random polyhedra is a bad test.

So, uh, what's your point? Because I don't know.

And none of these really has anything to do with the root post. OBBs are always going to be used. Always. Different methods for finding OBBs is useful. Fast ways to find "good" OBBs and slower ways to find "perfect" OBBs both have value.

The point with GJK is that it's a good algorithm, but hard to implement right. I struggled with this years ago, Steven Cameron at Oxford worked on it, and it's a solved problem now. I'm tempted to open-source the collision code from my old Falling Bodies product, but it's pre-STL C++ from the 1990s and I don't want to overhaul it now.

On collision detection generally, the performance advantage of OBBs over convex polyhedra is small and may be negative. If you use convex hulls, you get better looking collisions and it doesn't cost you much, if anything.

If you use convex hulls, you get better looking collisions and it doesn't cost you much, if anything.

Very interesting.

Can you go into more detail here on what you mean by better looking?

The convex hull will represent the geometry more accurately than an OBB because it can have >8 points and doesn't have to be cuboid. So the collisions will be more representative.

Right. In particular, OBBs roll like square wheels.

I'm tempted to open-source the collision code from my old Falling Bodies product, but it's pre-STL C++ from the 1990s and I don't want to overhaul it now.

You should release it and put that in the description.

The lack of STL means it's more likely to be thoughtfully designed. It's a merit, not a demerit. Or to put it a bit bluntly: Don't worry about that! I'd love to see the code.

I try not to do this, but you might be interested to know that four people upvoted me. So there are a bunch of people who want to see your code. I assure you, no one minds whether it's STL or not. The solution is the interesting bit.

"you get better looking collisions and it doesn't cost you much, if anything."

Yeah I dunno about this. Generating good convex polyhedra isn't free. Their cache missing extra memory isn't free. Nor is the test free.

I suppose it all really depends on the use case. The right balance of early out vs precision depends on your data set. Run too many early outs and it can be a net loss. Run too many precise tests and it's a net loss.

I'm tempted to open-source the collision code from my old Falling Bodies product, but it's pre-STL C++ from the 1990s and I don't want to overhaul it now.

If you open source it, someone will port it, add tests and make it into a nice library... So don't hesitate.

While I agree that GJK is more useful for typical collision detection scenarios, I was of the impression that the OBB/OBB collider function in ODE/Bullet can generate multiple contacts, while GJK is limited to one. Is that correct?

GJK only generates one contact, but it can be vertex/vertex, vertex/edge, edge/edge, edge/face, or face/face. In a physical simulation, reaching stability in a face/face contact is common.

In Falling Bodies, by version 2, we went further. GJK gave us the two closest features. From those, we took the two most parallel faces. Those faces were then projected on the plane perpendicular to the closest point vector and through its midpoint. The intersection of those polygons was computed and treated as a contact patch. The goal was to eliminate all discontinuities in changes of the contact force vector as the objects moved, so that we never integrated across a discontinuity.

This was for spring/damper contact simulation, which is more realistic than impulse/constraint contact simulation, but more CPU-intensive. In the era of 100MHz CPUs, it was too slow for games, but good for movie-quality animation.

You did what ?

"The performance tests were run on a MacBook Pro laptop with a 2.7GHz Intel Core i7 processor and 16GB of RAM running Windows 8.1."

Honestly I don't know why, but that got me laughing more than I expected.

Oh also, https://support.apple.com/en-us/HT201468 (How to install Windows using Boot Camp)

At all the .Net/Windows dev events I've been to at least a third of the laptops there have been MacBooks running Windows. It's surprisingly common.

A question - statistically how much better is it than producing OBBs via applying KLT/PCA on the (x,y,z) coordinates, obtaining major/minor covariance axis? I used that one for my SW 3D engine and was quite happy about it - very fast eigenvector computation and only orthogonal projections needed.

I don't have any numbers, but I think they mentioned this in the article: It depends on how well distributed your points are. There are a lot of cases where a point cloud will yield an inefficient obbox using the PCA method, while (if what you want is the minimum volume) their method guarantees optimality. As always, it depends on your use case.

Sure, that issue was prevalent with low-poly models but I doubt it's an issue with current model complexity. I basically wanted to understand how much of an improvement can I reasonably expect shall I decide to implement their algorithm.

nice PDF article!

Reply on news.ycombinator.com