instructions

In the previous article, we had the vertical foot from point to line. The so-called distance is actually the vector length (modulus length) from the point to the foot. Why don’t we just subtract, take the sum of the squares of xyz, and then take the square root? More simply, the SIMD framework provides a function called distance() to calculate the distance between two coordinates, which can be called directly.

static func distanceBetween(point:simd_float3, line:Line) -> Float {
    let position = projectionOnLine(from: point, to: line) // The function of the projection point
    return distance(position, point)
}
Copy the code

But in computers, taking square roots is a time-consuming operation, especially on older cpus. In 3D and AR, you can process hundreds or even hundreds of thousands of points per frame, at 60 frames per second. If there are a lot of square root operations in the calculation, it will put a lot of pressure on the CPU/GPU. SQRT in the C math function library has ideal accuracy, but is too slow for 3D games. So in 3D game code, we often see algorithms that use vectors or matrices instead of taking square roots to find distances as much as possible.

The geometric

After finding the nearest point from the point to the line (vertical foot), we get the DA vector. At this time, as long as we project the BA vector once again, we can directly get the distance by using the dot product decomposition to the DA direction.

Notice that if D coincides with A, then the DA vector is the zero vector, and you can’t project onto it. So it’s a separate judgment.

code

In computers, when a vector is too small, you can’t normalize, or return the 0 vector. And when a vector is too large, the normalization will also lose accuracy. Two times normalization, two times dot product, will make this algorithm less accurate, so you should be careful when using it.

truct Line {
    var position = simd_float3.zero
    var direction = simd_float3.zero
}

static func distanceBetween2(point:simd_float3, line:Line) -> Float {
ProjectionOnLine (from point:simd_float3, to line: line) is not called directly because we need to use vector values
    let vector = point - line.position
    let normalizedDirection = normalize(line.direction)
    let dotValue = dot(vector, normalizedDirection)
    let tarPoint = line.position + dotValue * normalizedDirection

    // Determine if the point is already on the line
    let disVector = point - tarPoint
    if length_squared(disVector) < 0.001  {// Use square instead of length
        return 0
    }
    // Use the dot product to find the distance again
    return dot(vector, normalize(disVector))
}
Copy the code

Modern computer hardware and SIMD framework are optimized for dot product and vector normalization function. Compared with time-consuming square root, dot product and vector normalization are used here to solve the distance problem and save a lot.

Maybe you will be confused: vector normalization, also use the length of the module, that is, divide by the square root to get the normalized value, why should we use vector method instead of square root?

  • Legacy habit: early CPU square root inefficient, C mathematical function librarysqrtProvides ideal accuracy, but is too slow for 3D games, which leads to weird thinking and optimized code;
  • Acceleration of 3D frameworks: Accuracy is not very high in 3D, so use Float (single precision) and sometimes even half (half precision), then the algorithm can also lose some accuracy to speed up. For example, the normalized function doesn’t always get a vector of length 1, it just gets very close to 1. Therefore, there is a lot of room for optimization, such as the fast square root inverse algorithm, which can quickly get the inverse of the square root (with a slight error), and some cpus already support similar instructions; For example, table lookup + interpolation to get approximate value, and so on;

As a result, a lot of 3D/AR code tends to be normalized rather than square root code.

other

The square root method should also be avoided when calculating distances in 3D/AR. If you don’t want to think too hard about vector solutions, you can also use distance_squared(), the distance squared function, instead of distance() to minimize the operation of taking square roots. For example, when comparing distance sizes, the distance squared is larger, so is the distance.

So, a lot of times, when you have to square the distance to calculate the distance, it also provides a distance squared method, which can be used in some scenarios to replace the distance itself with the square.

static func distanceSquaredBetween(point:simd_float3, line:Line) -> Float {
    let position = projectionOnLine(from: point, to: line)
    return distance_squared(position, point)
}
Copy the code