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

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

1 3
circle collision

1 ответ:

Умножьте набыстрый обратный квадратный корень из квадрата величины для нормализации.

Нормализация вектора означает деление каждой его компоненты на величину этого вектора. Величина равна 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

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

8