Normalizing Spatial Vectors without Square Root

Question

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?

Answer 1

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

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).

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.

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

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

Also, you can 'cull' more expensive collision checks (pseudo-python below):

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

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.