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?

Phenol

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.

Uptake

Could you give an example? – Phenol

What would you like me to clarify? Hopefully I can come up with an example, just let me know what isn't clear. – Uptake

I have a function to find the Inverse Square root, but how do I normalize the vector from that point? – Phenol

@Phenol Well, multiply the vector by the result of Inverse Square root! – Copperhead

@Copperhead lol I was 14 when I posted this question and this was not obvious to me at the time... now I'm 24 and have a degree so makes sense – Phenol

@Phenol I know this feel! When I was 14 I didn't even know elementary algebra properly. Now I need to study all the way up from the very basics to grasp the linear algebra concepts that I need practically currently... – Copperhead