Quote: Original post by Gorwooken
For my closest point on a Tetrahedron, I just calculate the distance to each facet and take the point with the smallest distance, Would it be beneficial for me to break the tetrahedron up into Voronoi regions?

As long as you include all features in your minimization (points, edges, triangles) you are fine. Using voronoi regions is a quick way to get to the right feature. See http://www.continuousphysics.com/Bullet/BulletFull/html/VoronoiSimplexSolver_8cpp-source.html

Quote: Original post by Gorwooken
Also, a quick question about GJK, say if I have two intersecting objects, the minkowski difference contains the origin. In order to find the penetration distance would I calculate the closest point on the minkowski difference to the origin?

That is correct. However the origin lies within the minkowski difference, so taking this minimum is a bit of work. Take a look at Gino van den Bergens book on GJK, the algorithm for the penetration depth is called EPA, expanding polytope algorithm. An approximation can be done by firing a number of rays in various directions from the origin to the minkowski difference and taking the minimum. I implemented this in the collision detection and physics library Bullet. It features GJK too, using some of Christer Ericsons work.

http://www.continuousphysics.com/Bullet
Erwin Coumans

Quote: Original post by Christer Ericson
Correct, that's why I made that comment. Specifically, when the signs of the barycentric coordinates indicate you're outside two edges and you have to test two edges, those tests effectively resolve into testing which Voronoi region you're in. Therefore you might as well test for Voronoi regions in the first place (or so my argument goes).

The tests I make involve one or two arithmetic operations and a sign test. I doubt if these are a bottleneck in the distance code. Until I actually compare implementations, I will remain skeptical that the Voronoi approach *greatly* outperforms the minimization approach.

Quote: Yes, if you recall it was Gino who pointed this out to both of us on c.g.a. Points far from the triangle are likely to be in a vertex Voronoi region, which are the fastest to test (requiring only two dot products and two comparisons each).

Yes, I quoted the newspost in my book. Gino and you argued that you should compare to vertices first and edges second, for the reason you mention here: Points *far away from* the triangle are likely to be in a vertex Voronoi region. In the book, my argument was that for points *close to* the triangle, the minimization approach performs better. Given that the performances vary with query point location, you would choose one or the other approach depending on your application. I would imagine in a collision detection system, you would be more likely to have the "close to" case than the "far away from" case :)

For what it is worth, I will implement the Voronoi approach just to see the results. I have also worked out the conjugate gradient algorithm for point-triangle distance computation and will implement that and make a comparison. No doubt you have already done this on exotic hardware ("Playstation 17" or some such), but I'll just stick to PC for this experiment.

Quote: Original post by Christer Ericson
I doubt there's much difference in practice.

Perhaps so, but if you have a very large number of such queries, a few cycles saved here or there can make a difference (say, for computational geometric applications in medical imaging :)

Quote:
IMO, in terms of efficiency the clincher is going to be...

I agree that this is what things boil down to. Over the years I have tried looking at mathematical variations on the problem, always reaching the point of seeing the same expressions to be evaluated and the same abundance of branches. The attraction to the conjugate gradient approach is that it appears to reduce number of branches. Even so, I don't know yet about how the branch penalties will wreak havoc. Still thinking about it...

...so there'll never be a conclusive answer.
[\quote]

But it always is fun to debate the various algorithms :)

There is absolutely so evidence that Brian Mirty Voronoi distance method is any more efficient that than the Quadratic minimization method.
Ericson has very peculiar ways to state things that are only real in his mind.
First hi keep calling his method and it is not it is, Brian Mirty method, which has its origins on Ming C ling and Mallosovich.
Second hi keep say that for some reason is more geometrical and that is not truth either.
Hi also say it is more accurate with not prove whatsoever more than for him somehow the expression Sum (a, Sum (b, c)) is better than Sum (Sum (a, b), c)
And finally there is not way to establish and argument with him because hi keep changing the subject,
If his claim of geometrical correctness is contested, he switched to numerical robustness, and if that is challenged then he bring the card of the new platform secretsy implementation detail, as if hi and only hi has the knowledge of assembly language programming.
Hi keep talking about caches, new platform an all kind of nonsense in order to get people to buy his book. The way I see it this new consoles is nothing but a still picture in a movie. Very soon we will all have access to them and then there will be even better hardware. just the same way is happens with the current generation.
Hi probably do not know this but caches and vector processors has been around for a while.
The truth is that both Voronoi descend method and GJK method are equally numerical unstable. In fact as Gino has once demonstrated to him his method is nothing more than the unrolling of Ginos or Cameron implementation

Jovani. I do not understand your objections. I know Christer personally, I know his experience, and I have read through his book. His posts are quite knowledgable. And he has real experience with real games on real console hardware. The issues about hardware (cache coherence, branch penalties, and so on) are very real. If he says that is where you need to focus, I trust his judgment. And, by the way, his book is *damn* good. And while you are criticizing folks, note that Gino made a significant contribution with GJK in showing how to *robustly* implement the method using 'float'. Computational geometry in the presence of floating-point arithmetic is difficult to make robust. Unless you have something useful to contribute to this topic, I suggest you avoid posting here.

So do I and thousand of other programmers, the difference is that it seems he thinks he known the consoles better than anybody else, never mind they are the developing tools. I saw the book at my company. The book is good but is not more than one of those problem solutions books you can buy at any college library. I could not find one single topic I did not know already or read on other original paper. So the book has very little value.

Christer:
My English may be very limited, however I do not go out of my way defending algorithms created by others as if they where mine as you do so eloquently and so frequently.
The Voronoi search is Brian Mirty publication and there is not amount of well written English that will change that. When you test the different convex sections of a convex piece you are using that idea.

If the algebraic methods are so trivial and you have such strong grasp of English, why don’t you used that knowledge to do what Lin, Mirty, Baraff, Cameron, Wiking and some other did in the 90’s. They used the basic and trivial knowledge to create new ideas that for some reason you decided you understnd better than anybody else, it is very easy to say something is trivial after some body figure it out.

For example here is an idea you may use to write a book on, “minimum distance calculation for arbitrary concave solid geometry”, or something along that line. Maybe you can use more maths and less English to write some irrefutable theorems and that way no one will claim your publications. You don’t even have to write source code, as any body could read the math even in Italian, French, Mandarin, you name the language it will be readable, even an illiterate like me could read it.

Instead you used that understanding of the English language of yours to write clear explanations in forums and the problem is that your explanation are clear but the idea are not and that is why every body who wrote something similar with a twist challenge yours claim, or it is not what Dave and Gino’s are doing.