Question about direction vector in support functions

[ppiastucki]

Hi,

This is a question rather than an issue.

I am trying to improve the performance of libccd support functions in ODE a bit by removing the unneeded transformations between world space and local space. While making these changes I noticed that in some cases the direction vector passed to support functions was normalized in ODE and in some cases it was not. I believe there is no need to normalize it as long as MPR is used at least it seems to be already normalized in portalDir(). Would you please confirm? Is it also the case for GJK? Should it be always expected to be a unit vector.

The full PR along with some discussions is available here - https://bitbucket.org/odedevs/ode/pull-requests/7/optimize-libccd-support-functions/diff#comment-13296486

Thanks, Piotr

[kroitor]

The direction vector should not be normalized in GJK. The algorithm does not care about the magnitude of direction-vector, it only uses the 'direction' of the direction-vector during geometric iteration. The direction of that direction-vector is used to find another support point along that direction, therefore you don't need to normalize it, and you don't care about the magnitude of that vector. Imagine an infinite ray-arrow 'pointing' in some direction. You don't care of its length (if it is normalized or not) at all. As Casey said in the GJK video ( http://mollyrocket.com/849 ), there's no divides in this algorithm, just pure cross and dot products ('easy' arithmetic with multiplication and addition).

The direction-vector is never expected to be a unit vector or to be normalized apriori - it does not have to be normalized at all. I also recommend reading the following article on GJK: http://www.dyn4j.org/2010/04/gjk-gilbert-johnson-keerthi/ .

I believe that everything regarding the magnitude and normalization of direction-vector behaves in the same way in EPA, MPR and other geometry-traversing algorithms – you just ignore the magnitude and don't normalize the direction-vector and don't expect that vector to be normalized.

[ppiastucki]

Thanks for the info. However, I was asking about the particular implementation in libccd rather than general algorithms and I am still not quite sure if it really applies to MPR implementation in libccd. As you can see in mpr.c, ccdVec3Normalize() is invoked quite often on the direction vector, basically before any call to __ccdSupport(). If the vector is already normalized by libccd for MPR (and it seems to be the case), normalizing it again in support functions will be just a waste of time.

[kroitor]

The magnitude of direction-vector can really be ignored algorithmically, I suppose this is true for libccd implementation. This is the actual testcase implementation of support function for various shapes: https://github.com/danfis/libccd/blob/master/src/testsuites/support.c.

That __ccdSupport function you mentioned calls two of the shape-specific support functions (one for each of two shapes in a colliding pair), which can actually be implemented ignoring the magnitude of direction-vector. After all there's only 4 calls to ccdVec3Normalize() in mpr.c. I would test that by commenting those 4 lines )

I think there's no cases when the magnitude of direction-vector really matters in libccd support functions (except for precision issues with 'touching' contacts). You can write your own support functions for any shape without using the magnitude of direction-vector if you want. Sorry didn't have time to play with code, that's just my 2 cents.

[danfis]

Hi Piotr, can I close this issue?

[ppiastucki]

Daniel,

To sum up: 1) MPR - the direction vector can be safely assumed to be a unit vector in support functions 2) GJK - no assumption can be made, the direction vector must be normalized in support functions if needed

If the above statements are correct feel free to close the issue :)