Bullet's Voronoi Simplex Solver

[Etherton]

Wait, there is more then 2 people. I can confirm it is more intuitive

Maybe for you it is, do you know that before Gino and Ericson re-wrote JGK algorithm?
There are over a dozen packages (physics engines and stand alone collision systems) that are doing the same thing, some of them are extremetely efficient, no one claims a rediscovery of Girvert and Johnson algorithm.

I did performance and robustness comparisons, and they are not much different. Just run the latest bullet demo if you like. Earlier in this threat I posted the Solid 3.5 integration files to compare it yourself
Code size between bullet simplex solver and solid simplex solver is similar too, I think that bullet simplex solver code is actually smaller, but I have to verify.
So in the end, not much difference:

Aren?t does your own personal opinions as facts? has you tested with simplexes of 5 or 10000 edges or more? it should be equallt efficient.
BTW I run the demos, like you say bullet is not better.

(Bullet versus Solid 3.5 simplex solver)
0) the geometric version is more intuitive
1) robustness, code size and performance is similar
1) caching can hurt, keeping data in registers is better
2) between frames: its better to cache the separating vector, and avoid gjk all toghether, instead of caching the determinants
Erwin

Again these are just personal opinions, nothing there say Bullet has the edge over Solid or any other collision library for that matter, because it is using a better version of GJK. Like I say it requires a stronger proof than just a speculations.
About Cache on PS3 obviously you are talking on and area of expertise very few people has knowledge since it is not a released nor it is an open platform. Whoever it seems that from your point of view the specific detail of a particular platform are reason enough for overthrown good practices of software engineering. I am so convince yet.

[Christer Ericson]

Math is math, but on a machine A dot B - A dot C is not the same as A dot (B - C). A "geometric" view does not help a lot in improving accuracy. In the given code it would be incredibly hard to fix numerical issues. Something to keep in mind as well.

I'm not sure what you mean by the caveat "does not help a lot" (does it mean you agree it helps some?) but I'll disagree nevertheless. Johnson's recursive formulation serves one and one purpose only: to reduce the number of multiplies (and to some extent, additions) performed in searching for the feature containing the closest point. That is not an important consideration today. Understanding and intuition is, though, which is why I greatly prefer the "geometric" view. I see nothing in Johnson's formulation to indicate it has been designed to be particularly robust (but I would be interested to learn otherwise, if you have such indications).

In that the geometric view treats each feature individually, without necessarily linking the calculations like the recursive formulation does, you stand a better chance of tweaking individual expressions for improved robustness, just as you indicate with your "A dot B - A dot C is not the same as A dot (B - C)" comment. That is, in the recursive formulation you're effectively stuck using the one expression, you do not have the liberty to pick and choose. A case-by-case approach does have the liberty to solve each case in whichever way is most appropriate. To me, the room for more adjustments translates into more opportunity to adjust for robustness issues, that's all.

[Erwin Coumans]

Maybe for you it is, do you know that before Gino and Ericson re-wrote JGK algorithm?

I follow Gino's work since around 1995, when we met at Eindhoven University, so I know he rewote it in a very good way.

There are over a dozen packages (physics engines and stand alone collision systems) that are doing the same thing, some of them are extremetely efficient, no one claims a rediscovery of Girvert and Johnson algorithm.

True, and I don't claim any re-discovery either. I predicted some performance degradation for caching on next gen platforms due to the big cache hits or due to small local memories. In other words, the gap between speed of memory access and processor speed is growing. All the subdistance algorithm have a constant time complexity,so from a performance perspective, we are just talking about the value of this constant, isn't it ?

Aren?t does your own personal opinions as facts? has you tested with simplexes of 5 or 10000 edges or more? it should be equallt efficient.
BTW I run the demos, like you say bullet is not better.

All the test runs and experiences are just empirical data to support the discussion, they are no personal opinions, just testruns. But I agree, empirical and statistical can be chosen to support any claim, and highlight just the good or the bad cases. That is why I recommended to do the tests yourself.

(Bullet versus Solid 3.5 simplex solver)
0) the geometric version is more intuitive
1) robustness, code size and performance is similar
1) caching can hurt, keeping data in registers is better
2) between frames: its better to cache the separating vector, and avoid gjk all toghether, instead of caching the determinants
Erwin

Again these are just personal opinions, nothing there say Bullet has the edge over Solid or any other collision library for that matter, because it is using a better version of GJK. Like I say it requires a stronger proof than just a speculations.

There is no claim that bullet has the edge, it claims that they are similar, see point 1.

About Cache on PS3 obviously you are talking on and area of expertise very few people has knowledge since it is not a released nor it is an open platform. Whoever it seems that from your point of view the specific detail of a particular platform are reason enough for overthrown good practices of software engineering. I am so convince yet.

I think on next-gen platforms, I would recommend to take a c++ implementation and optimize core parts in native assembly. Keep a unit test (extreme programming) to verify that the assembly and c++ have the same behaviour.

I don't think that not choosing to cache a variable is overthowing practices of software engineering. To me good software engineering practices are about keeping the work modular, object oriented, multi platform, care taken in dependencies on all levels. Then there is implementation details like making the code re-entrant, choice of caching strategy etc.

Etherton, can you let me know if Bullet Voronoi Solver, or any other part is violating your good software engineering standards ? I will happily ammend things.

Erwin

[gino]

Math is math, but on a machine A dot B - A dot C is not the same as A dot (B - C). A "geometric" view does not help a lot in improving accuracy. In the given code it would be incredibly hard to fix numerical issues. Something to keep in mind as well.

I'm not sure what you mean by the caveat "does not help a lot" (does it mean you agree it helps some?) but I'll disagree nevertheless. Johnson's recursive formulation serves one and one purpose only: to reduce the number of multiplies (and to some extent, additions) performed in searching for the feature containing the closest point. That is not an important consideration today. Understanding and intuition is, though, which is why I greatly prefer the "geometric" view. I see nothing in Johnson's formulation to indicate it has been designed to be particularly robust (but I would be interested to learn otherwise, if you have such indications).

In that the geometric view treats each feature individually, without necessarily linking the calculations like the recursive formulation does, you stand a better chance of tweaking individual expressions for improved robustness, just as you indicate with your "A dot B - A dot C is not the same as A dot (B - C)" comment. That is, in the recursive formulation you're effectively stuck using the one expression, you do not have the liberty to pick and choose. A case-by-case approach does have the liberty to solve each case in whichever way is most appropriate. To me, the room for more adjustments translates into more opportunity to adjust for robustness issues, that's all.

Christer, earlier I agreed on having a geometric interpretation of the subsimplex selection being helpful. In your texts you interpret the determinant sign comparisons as tests against planes of Voronoi regions, which is a nice way of looking at it. For instance, the closest points lies on an edge if the origin lies inside the Voronoi planes orthogonal to the edge, but outside the Voronoi planes orthogonal to the adjacent triangles. This is exactly what Johnson's algorithm is doing in geometric terms, and this geomtric view is helpful.

When it comes to computing the determinants you have a number of options. Compare it to solving Rubik's cube: there is only one solution but there are many patterns to get there. One of these patterns is using the recursive formula. Now, I cannot look into your code, but the Johnson code you refer to *is* using this pattern. Apart from performance issues, choosing the right pattern matters also in reducing the rounding error. I claim that a geometric view is useless in choosing the right pattern. For example, "A dot B - A dot C" is noisier than "A dot (B - C)". I did not use any geometric intuition to find that out.

Note that the recursive formulation *does* allow for some variation. You are still free to choose the y_k pivot point. This freedom as well as factorizing "A dot B - A dot C" to "A dot (B - C)" helps a lot in improving accuracy. I would not have been able to discover these tricks if I didn not have a simple recursive formulation of the determinant computation to start from.

Now, suppose you do use a different pattern for computing the determinants, and you'd like to add case distinction in order to be able to use a different pattern per case (point, edge, triangle, tetrahedron). One reason I can think of you would want to do that is because then you can use vector instructions for computing scalar triple products, which obviously is going to beat any recursive pattern. However, with respect to accuracy I find it hard to believe you can beat the recursive pattern. Furthermore, adding case-distinction in the determinant computation gives you more lines of code to worry about, making the process of controling robustness more challenging to say the least. Finally, I would like to add that not the simplex subalgorithm, but GJK's termination condition is going to give you the biggest headache when it comes to controling accuracy.

[mav]

Hi,

I'll take the opportunity that you are discussing the "geometric" view and the recursive formulation of the Johnson's algorithm to ask for your help to understand the recursive formulation. ( I almost hear you cry :p )

Hope you have Gino's book next to you because i'm going to make some references to it.

The geometric view you can describe to someone and they'll understand it first try. The recursive formulation you can describe 10 times and people still don't get it.

I couldn't agree more. The "geometric" view described in Christer's book is extremely simple to understand. The recursive formulation described in Gino's book is a lot difficult to understand, at least for me. But i want to understand both methods, that's why i keep struggling to understand the recursive formulation.

I read pages 126, ..., 130 from Gino's book probably a dozen times or something, but i'm still not understanding the idea of the recursive definition he explains in page 128. Pages 126 and 127 are very simple to understand but page 128 is not, i can follow all that math perfectly but not the idea behind it and in the end i feel like those calculations are leading me to nowhere.

Until the end of page 127 it's simple because Gino assumes that all x that belongs to X are known and of course its simple to calculate the unknowns ( lambda values ) using a system of linear equations. I suppose that the recursive definition is a general solution for the problem of finding points y that belongs to X so then the unknowns can be determined, but as i'm not understanding the idea of the recursive definition i'm not quite sure about that.

I would like to have seen more explanations coming along with the derivation of the recursive definition instead of just the math but ok, it may be sufficient for some people, but not for me, that's why i'm asking for your help to help me understand the whole concept of the recursive formulation.

Comments and/or links to papers/tutorials are very welcome.

Thank you.

[gino]

Hi,

I'll take the opportunity that you are discussing the "geometric" view and the recursive formulation of the Johnson's algorithm to ask for your help to understand the recursive formulation. ( I almost hear you cry :p )

Hope you have Gino's book next to you because i'm going to make some references to it.

The geometric view you can describe to someone and they'll understand it first try. The recursive formulation you can describe 10 times and people still don't get it.

I couldn't agree more. The "geometric" view described in Christer's book is extremely simple to understand. The recursive formulation described in Gino's book is a lot difficult to understand, at least for me. But i want to understand both methods, that's why i keep struggling to understand the recursive formulation.

I read pages 126, ..., 130 from Gino's book probably a dozen times or something, but i'm still not understanding the idea of the recursive definition he explains in page 128. Pages 126 and 127 are very simple to understand but page 128 is not, i can follow all that math perfectly but not the idea behind it and in the end i feel like those calculations are leading me to nowhere.

Until the end of page 127 it's simple because Gino assumes that all x that belongs to X are known and of course its simple to calculate the unknowns ( lambda values ) using a system of linear equations. I suppose that the recursive definition is a general solution for the problem of finding points y that belongs to X so then the unknowns can be determined, but as i'm not understanding the idea of the recursive definition i'm not quite sure about that.

I would like to have seen more explanations coming along with the derivation of the recursive definition instead of just the math but ok, it may be sufficient for some people, but not for me, that's why i'm asking for your help to help me understand the whole concept of the recursive formulation.

Comments and/or links to papers/tutorials are very welcome.

Thank you.

Hi mav, after rereading these pages I can understand part of the confusion. The only reason I introduced the x_i points is to have a contiguous indexing of points in X. So for example given Y = { y_1,...,y_3}, a subset X = {y_1, y_3}, would be referred to as { x_1, x_2 }. The x-s are simply new names for points in X, thus x_1 = y_1 and x_2 = y3. The assignment is arbitrary, so we could just as well have taken x_1 = y_3 and x_2 = y_1. It does not matter for the outcome.

The general principle for computing determinants is cofactor expansion which is described on page 14. If you'd work out the determinant computation by hand for all subsimplices, you probably will find out that you are computing the same value over again. If you are not convinced then it might be helpful to first work your way through 3.4.6 on page 97. The recursive formulation captures this idea. It is a method for computing the determinants resulting from applying Cramer's rule. In most texts, the derivation of the recursive formulation is left out, but I felt I needed to include it in the book. It probably will not spark any beautiful new insights, but at least it should reassure you that we are not making things up.

Like I said, there are other ways to compute the determinants but this one is particularly general and compact. To come back to "geometric intuition", there is not a lot of geometry going on here (but then again, geometry is in the eye of the beholder), but as far as I am concernend the recursive formulation and the geometric view presented by Christer are orthogonal concepts. They do not bite each other.

[mav]

Hi,

Thanks Gino for your quick reply.

I'll take a close look to section 3.4.6 then. It might be a great help to understand the recursive formulation of Johnson's algorithm.

Thank you.

[Erin Catto]

I like the compactness of the simplex solver in Solid 3.5.6, but I noticed that there are no early returns. For a given simplex, all determinants are computed.

On the other hand Bullet and the gilbert.c solvers have many early returns, meaning that many computations can be skipped. Perhaps this is an advantage of the geometric approach. Or can the recursive barycentric formulas provide some early returns?

The Bullet solver kind of gives up on Voronoi regions for the tetrahedron case. It first checks if the origin is inside the tetrahedron and otherwise finds the closest triangle by repeatedly calling the triangle solver (leading to some extra divides). The gilbert.c solver pushes through the tetrahedron case using the Voronoi checks, but the code is quite thorny.

[Erin Catto]

I'm now wondering if the geometric approach can obtain better accuracy if the winding order is known on the tetrahedron.

For the tetrahedron we can compute the barycentric coordinates in two ways. Gino's version of Johnson's algorithm doesn't make use of the winding order and gives formulas like:

Code: Select all

lambda = dot(w1, w2 - w1) * dot(w2, w3 - w1) * dot(w3, w4 - w1) + (5 more similar terms)

If the winding order is known, then the barycentric coordinate can be computed from geometry with formulas like:

Code: Select all

lambda = dot(w1, cross(w2 - w1, w3 - w1))

The first formula has 95 adds and 66 multplies.
The second formula has 11 adds and 8 multiplies.

The first formula can make use of some recursion to reduce the cost, but my concern is that so many additions can lead to more round-off error. Recursion doesn't reduce the round-off error.

The second formula is easier to implement, but we must fix the winding order. This can be done by checking the sign of a dot product and then swapping two vertices if necessary.

At a minimum, we can also conclude that the math is _not_ the same for all approaches.

[Erwin Coumans]

The Bullet solver kind of gives up on Voronoi regions for the tetrahedron case. It first checks if the origin is inside the tetrahedron and otherwise finds the closest triangle by repeatedly calling the triangle solver (leading to some extra divides). The gilbert.c solver pushes through the tetrahedron case using the Voronoi checks, but the code is quite thorny.

Apart from performance, is there any issue with the Bullet approach of just iterating over the 4 triangles for the tetrahedron case? Surely, if the original is inside the tetrahedron we need to terminate GJK.

The simplex solver could be further optimized using Casey's ideas, in one of the forum topics here, have you looked into doing that?
Thanks,
Erwin

[Erin Catto]

Yeah, it would just be a potential performance increase to search all the Voronoi regions for the tetrahedron case. There is nothing wrong with the Bullet approach. I've been using a similar approach until recently.

I did try some of Casey's optimizations, but they can fall apart when computing the distance (rather than just looking for a separating axis). In particular, Casey's assumptions about the positioning of the origin do not apply to cached simplices (as discussed in another thread in this forum). You also can not mix Casey's optimizations with the Bullet approach of iterating over all the tetrahedron triangles. For a single face, the closest point may be in an excluded Voronoi region. It will turn out that the failed face is not the closest face. Nevertheless, the optimized code may hit a failure case.

We can gain the benefit of Casey's optimizations without having failures by placing the missing Voronoi test cases (the ones that Casey excludes) last in our function. Due to early returns, those cases will rarely be hit.

[Erwin Coumans]

A while back, actually a few years ago, we received a SIMD optimized simplex solver, as well as a SIMD 'getSupportingVertex' for convex polyhedra. This hasn't been integrated into Bullet yet.

Is that something you considered?
Thanks,
Erwin

[Dirk Gregorius]

If the winding order is known, then the barycentric coordinate can be computed from geometry with formulas like:

Actually you can easily build the simplex in a way such that the winding order is known. Casey explains this in his video as well.

[Erin Catto]

Actually you can easily build the simplex in a way such that the winding order is known. Casey explains this in his video as well.

Would you care to elaborate?

It is quite easy to fix the winding by computing the signed volume of the tetrahedron and swapping two vertices if the sign is wrong.

[Dirk Gregorius]

IIRC correctly you only need to test whether the new vertex is below or above the triangle simplex and order the new tetrahedron simple accordingly. Casey always assumes that the new vertex is the first vertex 'A'. I found this a very convenient convention.