Angle computation can give high error

[stgatilov]

Here is the code for computing angle:

    /// Return the angle between <self> and <other>
    T angle(const BasicVector3<T>& other) const
    {
        // Get dot product of normalised vectors, ensuring it lies between -1
        // and 1.
        T dot = std::clamp(
            getNormalised().dot(other.getNormalised()), -1.0, 1.0
        );

        // Angle is the arccos of the dot product
        return acos(dot);
    }

This approach gives high error for small angles (i.e. when cosine is close to 1.0 or -1.0).
If machine epsilon is eps, then error can be as high as O(sqrt(eps)).
For floats, it would be about 3e-4, and for doubles, it would be about 1e-8.

It can be good idea to use asin/acos to compute angle only if you prefer speed over precision.

In order to achieve O(eps) precision for all angles, use atan2:

return fabs(atan2(a.cross(b).length(), a.dot(b)));

This approach also works perfectly well for computing signed angle in plane --- just remove fabs and replace .length() with dot product over plane normal (direction matters).

[greebo]

I just checked, the angle method is used to detect whether vectors are parallel and to calculate rotation matrices from two given angles. I guess these are ok.

Do I get this right, that if the error is ~3e-4, the corresponding error is ~0.02 degrees - for floats. In DR all the structures are using doubles, so I'm having a hard time imagining where this could be a problem?

[stgatilov]

5 hours ago, greebo said:

I just checked, the angle method is used to detect whether vectors are parallel and to calculate rotation matrices from two given angles. I guess these are ok.

If tolerance for checking parallellity is much larger than error, then it should be OK.
On my daily job people use angular tolerance 1e-10 or 1e-9, in which case O(sqrt(eps)) error is unacceptable.

As for rotation matrix for two ?vectors?, again it depends on how much error you can cope with in the rotated data.

Quote

Do I get this right, that if the error is ~3e-4, the corresponding error is ~0.02 degrees - for floats.

Yes.

If the rotated coordinate is about 5000, then 3e-4 error in the angle gives 1.5 error in the result. Which is a lot.

Quote

In DR all the structures are using doubles, so I'm having a hard time imagining where this could be a problem?

I understand. However I can say the same about doubles: float gives 1e-7 relative precision, which is absolute error at most 0.01 doom units for levels of sane size. So single precision floats should be enough for you... but it is not enough for some reason, right?

Having O(sqrt(eps)) error with double-precision vectors is like using single-precision vectors. Of course, the problem only triggers when you have small angle, which can happen very rarely in some cases (but very often in other cases).

[OrbWeaver]

It sounds to me like the precision is acceptable. We're not using these rotations for motion tracking or precision engineering, it's mainly for rotating models (most likely in steps of 15 or even 45 degrees). I presume most mappers won't notice if their 15° rotation is actually 15.02°.

The reason we use doubles everywhere is because when we tried floats, we started seeing inaccuracies in brush coordinates. When brushes are a long way from the origin and have a bunch of cumulative operations done to them (splitting, edge dragging etc), the combined error in the face coordinates starts to add up, perhaps even to the point where it can generate map leaks.