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 Dave Eberly The triangle decomposes the parametric plane into seven regions, labeled say by a triple of signs of the barycentric coordinates. If inside the triangle, the distance is zero (triangle treated as a solid). If outside, three regions require you to test one edge for closeness. The other three regions require you test two edges for closeness. This last fact is why I believe you say "have to perform additional computations".

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).

Quote:

<!–QUOTE–></td></tr></table></blockquote><!–/QUOTE–><!–ENDQUOTE–>Yes, if you recall it was Gino who pointed this out to both of us &#111;n c.g.a. Points far from the triangle are likely to be in a vertex Voronoi region, which are the fastest to test (requiring &#111;nly two dot products and two comparisons each).<br><br>

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:

Until I actually compare implementations, I will remain skeptical that the Voronoi approach *greatly* outperforms the minimization approach.

Oh, for sure. That's why I said "slight" and "but don't quote me"; I doubt there's much difference in practice.

IMO, in terms of efficiency the clincher is going to be what is more effectively implemented in SIMD (since we'd want to do ~4 tests in parallel), how well you can implement the branches without actual branching (to avoid mispredication) and how short the code can be made (to minimize code cache penalties). These are all very platform-specific measurements, so there'll never be a conclusive answer.

Quote:

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.

You know I can't comment on my involvement in the PlayStation 17 project! ;)

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

Quote:

Original post by jovani 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. [Rest of odd rant deleted]

First, I'm responding against my better judgement, but I feel I need to point out that Brian Mirtich (not Mirty) has nothing to do with this discussion. His Voronoi-Clip algorithm is completely unrelated to the simple problem of computing the point on a triangle (or tetrahedron) closest to a query point. The same goes for the Lin-Canny algorithm to which you're alluding.

If anything, you could consider the approaches both myself and Dave are proposing as effectively testing the Karush-Kuhn-Tucker conditions of a (nonlinear) minimization problem in two different (but related) ways. As such, the methods date back to 1939, but even that is reasonably incorrect, because this is simple enough that Gibbs, Hamilton, Grassmann, Clifford and other pioneers of vector analysis undoubtedly could (and indeed might) have solved these problems in a heartbeat even as they were inventing what was to become the vector methods we use today.

Second, and I don't mean to be rude, but considering your somewhat weak grasp of English, you may want to consider if you have misinterpreted something before you jump to conclusions about something. In this case specifically, the "my approach" in my post refers to "the method which I present in my book" not "the method which I invented". Same thing when Dave refers to it as "your [i.e. mine, Christer's] Voronoi approach"; he isn't sugesting I invented anything, just that it is the algorithm I'm refering to in the discussion here.

In summary, the algorithms we are talking about here are generally considered so "trivial" that there is no acknowledged inventor for them -- anyone with good linear algebra and calculus skills can easily derive them from first principles. I have done so, Dave has done so, and so has hundreds if not thousands of others. When these people talk about their implementation they're likely to say "my algorithm", but not to imply they invented something "original".

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.

Quote:

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.

First, and for the second time, his last name is Mirtich. M-i-r-t-i-c-h. Second, your statement is blatantly false (as I will show in the following). What is novel in Brian Mirtich's V-Clip paper is the _way_ in which his algorithm determines how to walk from one feature to another (in the context of searching for closest points of two polytopes). The idea of walking from one feature to another did _not_ originate with Mirtich. Anyone who can read can easily verify that the well-known Lin-Canny paper from 1991 (A Fast Algorithm for Incremental Distance Calculation) describes Voronoi feature walking and predates the Mirtich V-Clip report from 1997 by six years. Thus _clearly_ the approach did not originate with Mirtich.

Furthermore, the novel thing with the Lin-Canny approach is _not_ the search of Voronoi feature regions as such, but the idea of walking between neighboring regions in a hill-climbing like fashion. As I already pointed out, the evaluation of Karush-Kuhn-Tucker feasibility conditions for (quadratic) optimization problems on polytopes effectively corresponds to a test for containment in a Voronoi feature region and thus one can make a strong case for Voronoi feature region search having been performed since as early as the 1940s, only under a different name.

Before making bold claims on a topic, you might want to familiarize yourself with the topic first.