instructions
From the beginning, we encountered computational accuracy problems. In the previous code, when we encountered the need to determine whether points coincide, whether vectors are parallel/vertical, and whether vectors are zero (too short), Are in general use is less than 0.0001 or the Swift provides minimum Float Float type. The leastNormalMagnitude to simple judgment.
In fact, these are unreasonable, indiscriminate all lead to puzzling problems. In this paper, we will briefly discuss the types of these errors and try to make targeted treatment. It should be noted that we do not deliberately pursue perfection and accuracy in mathematical principles for the purpose of engineering reasonableness, bug-free project and relatively consistent effect.
Binary and floating point
According to IEEE 754, any binary floating point number can be expressed as: sign bit + exponent bit + mantissa bit. Take the Float type as an example. It is a 32-bit floating-point type. The first bit is the symbolic bit S, the next eight bits are the exponential bit E, and the last 23 bits are the significant digit M.
So where does the error occur? One is the conversion of base 10 and base 2, there will be an unequal problem; Second, the length of significant digit is limited, the length of index is limited, which brings the problem of precision discarding or overflow.
How to deal with
For these problems involving mathematical principles and computer principles, this series of articles do not deal with the unified!! Yeah, it’s for direct use, no processing.
There is a problem, floating point Numbers also points standardization and the normalization (Normal or Subnormal), unified by the normalization processing in this series, namely the minimum Float. LeastNormalMagnitude, rather than Float. LeastNonzeroMagnitude.
The operation process
There are two kinds of problems that arise from this process:
- Overflow of calculation results: for example, if square is used in the calculation process, it may be too large or too small to cause overflow;
- It doesn’t cancel out: multiply by 3 and divide by 3, cosine by acOS, theoretically return to the original value, but the result is inconsistent.
How to deal with
There is no perfect strategy for these problems, but in general we can tweak the code to either precompute or delay certain values, avoid overflows first, and worry about accuracy later.
For example, if we want to calculate the average of 100,000 points, we add them up and divide by the total number, which is fast and accurate. But you run the risk of spilling over in the sum, so you can divide each point by the total number, and then add up the tiny values to get the average. But this is obviously slower and less accurate.
The essence of delayed computation is to dump the problem onto the compiler, expecting the powerful optimization capabilities of modern compilers to help simplify computation and improve accuracy. Multiplying by 3 and then dividing by 3, for example, will be optimized by the compiler.
Approximate algorithm and performance optimization
In 3D and AR, in order to improve efficiency, there are many approximation algorithms and performance optimization algorithms, which also introduce errors. In general, we can assume that the functions and operations in the system and well-known third-party frameworks are reliable and do not need to be handled except in extremely small or extreme cases.
The other is our own approximation algorithm. For example, when calculating the length of A vector, we replace the length with the square of the length, and compare the Angle with cosA instead of A.
How to deal with
If it is a system framework or a well-known third party, generally do not handle, in most cases is enough.
And its own alternative algorithms need to take care of themselves. Such as using vector length square to compare size and better handling: the original is to calculate | | ab | | > 100, should now is | | ab | | * | | ab | | > 100 * 100.
If you simply compare the Angle (0 ~ 180) : A > b, you can change it to cos(a) < cos(b).
But when we judge whether we are close to vertical or parallel, there may be problems: for example, when x is close to 90 degrees, the absolute value of cosine (x) is less than 0.01 with high accuracy, while the absolute value of sine (x) is greater than 0.99 with poor accuracy. Why is that? To start with the graph of the function, strictly speaking, the slope of the graph (i.e., the derivative) :
That’s why, when we’re trying to figure out whether a vector is perpendicular, we use the cosine of x dot product; And if you’re parallel, you use the sine of x, the cross product;
The physical meaning of geometric data
In general, in 3D and AR, we don’t care too much about the existence of error, we just want it to be relatively stable and uniform.
Especially in AR, which is relevant to the real world, when the two points are 0.0001 apart, that is, 0.1 millimeter, the difference is almost indistinguishable unless you are very close or zoom in to see the details. So the distance and the length need to take into account the distance of the observer (the size of the final display).
As for the Angle, when the Angle between the two directions is less than 0.0001, it is also impossible to see the difference. Of course, the Angle is special, and if it is far enough, the deviation can be seen, and the difference is obvious ten kilometers away. So when we use the dot product to determine whether the vector is parallel, we should consider the effect of the length of the vector; Similarly, when using the cross product to judge whether a vector is perpendicular, the influence of vector length should also be considered.
Another thing to note is that in 3D and AR, physical quantities may also come from the user’s input (such as the user’s movement, click, select, etc.). When the user moves 0.1 mm, or rotates 0.0001 radian, it is almost meaningless and probably meaningless interference. Normalizing a very short vector, for example, probably amplifies the error and doesn’t make much sense.
How to deal with
I think the proper way to deal with it is:
- Distinguish different physical quantities, such as distance, length, Angle and so on, respectively. For example, the influence of vector length should be ignored when calculating Angle.
- Provide approximate equality options, allowing equality within the error range;
The following code, for example, uses the error range and eliminates the effect of vector length in calculating angles. To facilitate subsequent calculations, the Angle relation is returned along with the dot and cross product values.
extension simd_float3 {
func almostSamePoint(to point:simd_float3, tol:Float = 0.0001) -> (isSame:Bool, distanceSquared:Float) {
let distanceSquared = distance_squared(self, point)
return (isSame:distanceSquared < tol * tol, distanceSquared:distanceSquared)
}
func almostParallelRelative(to vector:simd_float3, tol:Float = 0.0001) -> (isParallel:Bool, crossValue:simd_float3) {
let lengthS1 = length_squared(self)
let lengthS2 = length_squared(vector)
let crossValue = cross(self, vector)
let isParallel = length_squared(crossValue)/lengthS1/lengthS2 < tol * tol
return (isParallel:isParallel, crossValue:crossValue)
}
func almostPerpendicular(to vector:simd_float3, tol:Float = 0.0001) -> (isPerpendicular:Bool, dotValue:Float) {
let lengthS1 = length_squared(self)
let lengthS2 = length_squared(vector)
let dotValue = dot(self, vector)
let isPerpendicular = dotValue * dotValue / lengthS1 / lengthS2 < tol * tol
return (isPerpendicular:isPerpendicular, dotValue:dotValue)
}
}
Copy the codeconclusion
Computational geometry is not mathematics, as long as the error is controlled within a certain range and stable, it can meet the needs of engineering. In fact, there are two ways to sum up:
- Regardless, do not deal with;
- According to the specific situation, their own ideas;
It sounds crazy, but it’s the truth.
Project code
This series code has been published in making: ComputationalGeometrySwift