归一化无平方根的空间向量 [英] Normalizing Spatial Vectors without Square Root

问题描述

因此，我了解到在编程中使用平方根总是不好的做法，尤其是在每个更新步骤中。我正在尝试在圆之间进行逼真的弹性碰撞，并且我一直在阅读以下内容： http：/ /www.vobarian.com/collisions/2dcollisions2.pdf 有没有一种方法可以在不使用平方根的情况下标准化向量？还是执行我正在做的事情的任何快速方法？

So I've learned that using square root in programming is always bad practice, especially in every update step. I'm trying to do realistic elastic collisions between circles, and I've been reading this: http://www.vobarian.com/collisions/2dcollisions2.pdf Is there a way to normalize the vector without using square root? Or any fast way to do what I'm doing?

推荐答案

乘以要进行标准化的幅度平方的快速反平方根。

Multiply by the Fast Inverse Square Root of the square of the magnitude to normalize.

归一化向量意味着将其每个分量除以该向量的大小。幅度等于 sqrt（x ** 2 + y ** 2），其中 x 和 y 是向量的组成部分。但是平方根很慢，我们宁愿避免。因此，我们选择乘以幅度的倒数平方根，即<$ c，而不是除以 sqrt（x ** 2 + y ** 2） $ c> 1 / sqrt（x ** 2 + y ** 2）。

Normalizing a vector means dividing each of its components by that vector's magnitude. The magnitude equals sqrt(x**2 + y**2), where x and y are the components of the vector. But square root is slow, we'd rather avoid it. So, instead of dividing by sqrt(x**2 + y**2), we choose to multiply by the inverse square root of the magnitude, which is 1 / sqrt(x**2 + y**2).

为什么有帮助？因为制作《雷神之锤III》的好伙计们想出了一种非常快速的方法来计算 1 / sqrt（x ** 2 + y ** 2），我们称之为 Fast Inverse Square Root 。

Why does that help? Because the good folks who made Quake III came up with a really fast way to calculate 1 / sqrt(x**2 + y**2), which we call the Fast Inverse Square Root.

换句话说， fisqrt（x）等于 1 / sqrt（x），但是计算 fisqrt（x）比计算 1 / sqrt（x）。

In other words, fisqrt(x) equals 1 / sqrt(x), but calculating fisqrt(x) is much faster than calculating 1 / sqrt(x).

下面是一些伪python来说明如何将它们放在一起。

Here's some pseudo-python to illustrate putting this all together.

def fisqrt(x):
    # See article for implementation details.

def normalize(vector):
    magnitude_squared = vector.x**2 + vector.y**2
    invsqrt = fisqrt(magnitude_squared)
    vector.v *= invsqrt
    vector.y *= invsqrt
    return vector

此外，您也可以剔除更昂贵的碰撞检查（以下为伪python）：

def magnitudeSquared(vector):
    return vector.x ** 2 + vector.y ** 2

def cull(circleA, circleB):
    # Save a square root by calling magnitudeSquared.
    # Assuming that circle.center is a vector with x and y components.

    minCollisionDistance = circleA.radius + circleB.radius
    if magnitudeSquared(circleA.center - circleB.center) <= minCollisionDistance ** 2:
        # Circles overlap, can't cull.
        return false

    # Circles do not overlap, can cull!
    return true

调用 cull 在进行其他碰撞检查之前。当 cull 返回true时，您不需要做任何进一步的检查，因为两个圆圈不可能互相接触。很好，因为 cull 几乎肯定会比您可能使用的其他冲突检测方法快。如果 cull 返回false，则圆的面积在某处重叠，因此您可以调用更昂贵的物理建模算法。

Call cull before you do other collision checks. When cull returns true, you don't need to do any further checks because the two circles cannot possibly be touching each other. This is nice, because cull will almost definitely be faster than other collision detection methods you may use. If cull returns false, the area of the circles overlap somewhere, so you call your more expensive, physics-modeling algorithm.

这篇关于归一化无平方根的空间向量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！