Очень быстрая проверка расстояния 3D?

Question

Есть ли способ сделать быструю и грязную 3D-проверку расстояния, если результаты грубые, но это очень-очень быстро?Мне нужно сделать сортировку по глубине.Я использую STL sort следующим образом:

bool sortfunc(CBox* a, CBox* b)
{
    return a->Get3dDistance(Player.center,a->center) <
      b->Get3dDistance(Player.center,b->center);
}

float CBox::Get3dDistance( Vec3 c1, Vec3 c2 )
{
    //(Dx*Dx+Dy*Dy+Dz*Dz)^.5 
    float dx = c2.x - c1.x;
    float dy = c2.y - c1.y;
    float dz = c2.z - c1.z;

return sqrt((float)(dx * dx + dy * dy + dz * dz));
}

Есть ли способ сделать это без квадратного корня или, возможно, без умножения?

Answer 1

Если бы вы могли центрировать свои координаты вокруг игрока, используйте сферические координаты?Тогда вы могли бы отсортировать по радиусу.

Это большой, если.

Answer 2

Вы можете рассмотреть возможность кэширования расстояния между игроком и объектом при его вычислении, а затем использовать это в своем sortfunc. Это будет зависеть от того, сколько раз ваша функция сортировки просматривает каждый объект, поэтому вам, возможно, придется профилировать, чтобы быть уверенным.

Я понял, что ваша функция сортировки может делать что-то вроде этого:

compare(a,b);
compare(a,c);
compare(a,d);

и вы будете каждый раз вычислять расстояние между игроком и 'a'.

Как уже упоминалось, в этом случае вы можете опустить sqrt.

Answer 3

Если это просто значение для сортировки , тогда вы можете поменять sqrt () на abs ().Если вам нужно сравнить расстояния с заданными значениями, получите квадрат этого значения.

Например, вместо проверки sqrt (...) по a, вы можете сравнить abs (...) по a * a.