Quaternion.setFromUnitVectors lacks precision for close to opposite vectors

[iaxyz]

Describe the bug

A Quaternion calculated using setFromUnitVectors doesn't align the two unit vectors precisely if it get's applied.

To Reproduce

run the following code using node (I've tested with 14.7.0) or check the live example on JSFiddle.

Code

const three = require("three");

const zAxis = new three.Vector3(0, 0, 1);
// just 3 example Vectors that fail
const normals = [
  new three.Vector3(0.00001630279256671349, 0.00021101192465278993, -0.9999999776040931).normalize(),
  new three.Vector3(-0.00011854270500476976, 0.00027142141201982574, -0.9999999561390212).normalize(),
  new three.Vector3(0.000042675541323141565, -0.00040869364504498944, -0.9999999155741478).normalize(),
];

normals.forEach(normal => {
  const alignNormalsRotation = new three.Quaternion().setFromUnitVectors(normal, zAxis);
  console.log(normal.clone().applyQuaternion(alignNormalsRotation).angleTo(zAxis));
});

Live example

• jsfiddle-latest-release

Expected behavior
I would expect the calculations to have higher precision. I've only encounterd this amount of error with Vectors that are close to being opposite.

Result of the code:

0.00021164076687348634
0.000296178929600093
0.00041091569275236077

Expected result:

0
0
0

Platform:
Tested locally with:

• Device: Desktop
• OS: Windows 10
• NodeJS: v14.7.0
• Three.js version: three@0.110.0

and in the browser with:

• Device: Desktop
• OS: Windows 10
• Browser: Chromium, Firefox, Edge (via jsfiddle see link above)
• Three.js version: "https://threejs.org/build/three.module.js" (17.03.2021)

[WestLangley]

This is an edge-case.

In Quaternion.setFromUnitVectors() the constant EPS would have to be changed from

const EPS = 0.000001;

to

const EPS = 0.00000001;

I am not sure of the ramifications -- or advisability -- of doing that.

[Mugen87]

How about adding a third (optional) epsilon parameter with the existing 0.000001 as a default value?

[WestLangley]

I do not think users should be expected to set such parameters. That's our job.

This is a numerical-stability issue.

[Mugen87]

The problem is that a fixed epsilon is not always obvious to determine. I mean why was 0.000001 chosen and not something else?

The desired precision in context of floating point computations is in general use case specific. For some use cases the precision is "good enough". For others not. By making it part of the parametrization, a proper epsilon can be picked at app level if the default is insufficient.

I've seen configurable epsilons in other math libraries, too.

[WestLangley]

This is not about a desired precision, it is about avoiding a singularity.

Furthermore, we should not expect users to know how to properly set EPS. It is our job to do that.

If a smaller EPS is numerically stable, we should use it.

If a smaller EPS is is not numerically stable, we should not allow the user to set it.

//

Ideally, EPS should be the smallest value that results in numerically-stable results for the given platform.

[Mugen87]

Couldn't we implement the method just like so? https://www.html5gamedevs.com/topic/29839-rotation-between-two-unit-vectors/?tab=comments#comment-171556

Updated fiddle (@iaxyz This produces your expected result): https://jsfiddle.net/0ug5h1v7/

@WestLangley Do you know the original resource of setFromUnitVectors()'s implementation? I'm trying to understand the if clause.

[WestLangley]

@Mugen87 Thanks for working on it!

The links you are looking for are hidden in here: https://github.com/mrdoob/three.js/pull/4580/files.

You can also check out a glm implementation:
https://github.com/g-truc/glm/blob/ace16e47780dcef815294715237f51e9129b6eb3/glm/gtx/quaternion.inl#L121-L158

[Mugen87]

glm uses std::numeric_limits::epsilon. From the documentation:

Returns the machine epsilon, that is, the difference between 1.0 and the next value representable by the floating-point type T.

If we want to use an equivalent approach in JS, we have to use Number.EPSILON.

The Number.EPSILON property represents the difference between 1 and the smallest floating point number greater than 1.

[WestLangley]

EPS should be the smallest value that results in numerically-stable results for the given platform.

...meaning the cross-product calculation must be correct. That may be related to Number.EPSILON in some complex way...

//

Maybe just implement #21477 (comment) and move on...

const EPS = 1e-8;

[Mugen87]

I've tested the fiddle with Number.EPSILON and it works as expected. I vote for the glm approach since that is indeed a good reference.

[WestLangley]

If you feel your testing is exhaustive, give it a go. :-) I was just opting to be a bit more conservative.