Нормализация пространственных векторов без квадратного корня

Question

Итак, я узнал, что использование квадратного корня в программировании - это всегда плохая практика, особенно на каждом этапе обновления. Я пытаюсь сделать реалистичные упругие столкновения между кругами, и я читал это: http://www.vobarian.com/collisions/2dcollisions2.pdf Есть ли способ нормализовать вектор без использования квадратного корня? Или любой быстрый способ сделать то, что я делаю?

Answer 1

Умножьте на Fast Inverse Square Root квадрата величины, чтобы нормализовать.

Нормализация вектора означает деление каждого из его компонентов на величину этого вектора. Величина равна sqrt(x**2 + y**2), где x а также y являются составляющими вектора. Но квадратный корень медленный, мы бы лучше его избегали. Таким образом, вместо деления на sqrt(x**2 + y**2), мы решили умножить на обратный квадратный корень из величины, которая 1 / sqrt(x**2 + y**2),

Почему это помогает? Потому что хорошие люди, которые сделали Quake III, придумали очень быстрый способ расчета 1 / sqrt(x**2 + y**2), который мы называем быстрый обратный квадратный корень.

Другими словами, fisqrt(x) равняется 1 / sqrt(x), но расчет fisqrt(x) гораздо быстрее, чем расчет 1 / sqrt(x),

Вот некоторый псевдопифон, чтобы проиллюстрировать это все вместе.

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

Кроме того, вы можете 'отбирать' более дорогие проверки коллизий (псевдопайтон ниже):

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, площадь кругов где-то перекрывается, поэтому вы называете свой более дорогой алгоритм физического моделирования.