Подтвердить что ты не робот

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

Есть ли способ сделать быструю и грязную трехмерную проверку расстояния, где результаты грубые, но очень быстро? Мне нужно выполнить сортировку глубины. Я использую 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));
}

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

4b9b3361

ОТВЕТЫ

Ответ 1

Вы можете оставить квадратный корень, потому что для всех положительных (или действительно, неотрицательных) чисел x и y, если sqrt(x) < sqrt(y), тогда x < y. Поскольку вы суммируете квадраты действительных чисел, квадрат каждого действительного числа неотрицателен, а сумма любых положительных чисел положительна, условие квадратного корня имеет место.

Однако вы не можете устранить умножение без изменения алгоритма. Здесь контрпример: если x равно (3, 1, 1) и y равно (4, 0, 0), |x| < |y|, потому что sqrt(1*1+1*1+3*3) < sqrt(4*4+0*0+0*0) и 1*1+1*1+3*3 < 4*4+0*0+0*0, но 1+1+3 > 4+0+0.

Поскольку современные процессоры могут вычислять точечный продукт быстрее, чем они могут фактически загружать операнды из памяти, маловероятно, что у вас будет что-то, что можно получить, устраняя размножение в любом случае (я думаю, что у новейших процессоров есть специальная инструкция, которая может вычислять точечный продукт каждые 3 цикла!).

Я бы не стал рассматривать алгоритм без предварительного профилирования. Ваш выбор алгоритма будет в значительной степени зависеть от размера вашего набора данных (подходит ли он в кеше?), Как часто вам приходится запускать его, и что вы делаете с результатами (обнаружение столкновения? Близость? Окклюзия?).

Ответ 2

Я обычно делаю первый фильтр Манхэттенское расстояние

float CBox::Within3DManhattanDistance( Vec3 c1, Vec3 c2, float distance )
{
    float dx = abs(c2.x - c1.x);
    float dy = abs(c2.y - c1.y);
    float dz = abs(c2.z - c1.z);

    if (dx > distance) return 0; // too far in x direction
    if (dy > distance) return 0; // too far in y direction
    if (dz > distance) return 0; // too far in z direction

    return 1; // we're within the cube
}

На самом деле вы можете оптимизировать это дальше, если знаете больше о своей среде. Например, в среде, где есть земля, такая как симулятор полета или шутер от первого лица, горизонтальная ось намного больше, чем вертикальная ось. В такой среде, если два объекта находятся далеко друг от друга, они, скорее всего, больше разделены осью x и y, а не осью z (в шутере от первого лица большинство объектов имеют одинаковую ось z). Поэтому, если вы сначала сравниваете x и y, вы можете вернуться раньше от функции и избегать дополнительных вычислений:

float CBox::Within3DManhattanDistance( Vec3 c1, Vec3 c2, float distance )
{
    float dx = abs(c2.x - c1.x);
    if (dx > distance) return 0; // too far in x direction

    float dy = abs(c2.y - c1.y);
    if (dy > distance) return 0; // too far in y direction

    // since x and y distance are likely to be larger than
    // z distance most of the time we don't need to execute
    // the code below:

    float dz = abs(c2.z - c1.z);
    if (dz > distance) return 0; // too far in z direction

    return 1; // we're within the cube
}

Извините, я не понимал, что функция используется для сортировки. Вы можете использовать расстояние в Манхэттене, чтобы получить очень грубую первую сортировку:

float CBox::ManhattanDistance( Vec3 c1, Vec3 c2 )
{
    float dx = abs(c2.x - c1.x);
    float dy = abs(c2.y - c1.y);
    float dz = abs(c2.z - c1.z);

    return dx+dy+dz;
}

После грубого первого сортировки вы можете взять самые верхние результаты, сказать 10 самых близких игроков и повторно сортировать, используя правильные расчеты расстояния.

Ответ 3

Здесь уравнение, которое может помочь вам избавиться от обоих sqrt и размножаться:

max(|dx|, |dy|, |dz|) <= distance(dx,dy,dz) <= |dx| + |dy| + |dz|

Это дает вам оценку диапазона для расстояния, которое выталкивает его с точностью до 3 (верхняя и нижняя границы могут отличаться не более чем на 3 раза). Затем вы можете отсортировать, скажем, меньшее число. Затем вам нужно обработать массив до тех пор, пока вы не достигнете объекта, который находится в 3 раза дальше, чем первый затеняющий объект. Затем вам гарантировано не найти объект, который ближе к концу в массиве.

Кстати, сортировка здесь излишняя. Более эффективным способом было бы сделать серию ведер с разными оценками расстояния, например [1-3], [3-9], [9-27],.... Затем поместите каждый элемент в ведро. Обработайте ведра от наименьшего до самого большого, пока не достигнете скрытого объекта. Для того, чтобы убедиться в этом, сделайте 1 дополнительное ведро.

Кстати, умножение с плавающей запятой в наши дни довольно быстро. Я не уверен, что вы многого выиграете, превратив его в абсолютную ценность.

Ответ 4

Я разочарован тем, что большие старые математические трюки, кажется, теряются. Вот ответ, который вы просите. Источником является Пол Се, отличный веб-сайт: http://www.azillionmonkeys.com/qed/sqroot.html. Обратите внимание, что вас не интересует расстояние; вы сделаете все возможное для своего вида с квадратом расстояния, который будет намного быстрее.

В 2D мы можем получить грубое приближение метрики расстояния без квадратного корня с формулой:

distanceapprox (x, y) = (1 + 1/(4-2 * √2))/2 * min ((1/√2 ) * (| x | + | y ​​|), max (| x |, | y |)) http://i52.tinypic.com/280tbnc.gif

который отклонится от истинного ответа максимум на 8%. Аналогичный вывод для трех измерений приводит к:

distanceapprox (x, y, z) = (1 + 1/4√3)/2 * min ((1/√3) * ( | x | + | y ​​| + | z |), max (| x |, | y |, | z |)) http://i53.tinypic.com/2vlphz8.gif

с максимальной погрешностью около 16%.

Однако, что-то, на что следует обратить внимание, заключается в том, что часто расстояние требуется только для целей сравнения. Например, в классическом вычислении набора (z ← z2 + c) величина комплексного числа обычно сравнивается с длиной граничного радиуса 2. В этих случаях можно просто отказаться от квадратного корня, стороны сравнения (поскольку расстояния всегда неотрицательны). То есть:

    √(Δx2+Δy2) < d is equivalent to Δx2+Δy2 < d2, if d ≥ 0

Следует также упомянуть, что в главе 13.2 Ричарда Г. Лиона "Понимание обработки цифровых сигналов" имеется невероятная коллекция 2D-алгоритмов расстояния (a.k.a). В качестве одного из примеров:

Max = x > y? x: y;

Min = x < y? x: y;

if (Min < 0,04142135Max)

|V| = 0.99 * Max + 0.197 * Min;

еще

|V| = 0.84 * Max + 0.561 * Min;

которая имеет максимальную погрешность 1,0% от фактического расстояния. Конечно, наказание состоит в том, что вы делаете пару ветвей; но даже "самый приемлемый" ответ на этот вопрос имеет по крайней мере три ветки.

Если вы серьезно относитесь к оценке сверхбыстрого расстояния до определенной точности, вы можете сделать это, написав собственную упрощенную оценку fsqrt(), используя тот же базовый метод, что и производители компиляторов, но с меньшей точностью, делая фиксированное число итераций. Например, вы можете исключить обработку особых случаев для крайне малых или больших чисел и/или уменьшить количество итераций Newton-Rapheson. Это была ключевая стратегия, лежащая в основе реализации так называемого "Quake 3" быстрого обратного квадратного корня - это классический алгоритм Ньютона с ровно одной итерацией.

Не предполагайте, что ваша реализация fsqrt() медленна, не сравнивая ее и/или читая источники. Большинство современных реализаций библиотек fsqrt() являются бесветренными и действительно прокляты быстро. Вот, например, старая реализация fsqrt с плавающей запятой IBM. Преждевременная оптимизация является и всегда будет корнем всего зла.

Ответ 5

Заметим, что для 2 (неотрицательных) расстояний A и B, если sqrt(A) < sqrt(B), то A < B. Создайте специализированную версию Get3DDistance() (GetSqrOf3DDistance()), которая не вызывает sqrt(), которая будет использоваться только для sortfunc().

Ответ 6

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

float Get3dDistance( Vec3 c1, Vec3 c2 );

подразумевается две копии структуры Vec3. Вместо этого используйте ссылки:

float Get3dDistance( Vec3 const & c1, Vec3 const & c2 );

Ответ 7

Вы можете сравнить квадраты расстояний вместо фактических расстояний, так как d 2 = (x 1 -x 2) 2 + (у <суб > 1суб > -y <суб > 2суб > ) 2 + (г <суб > 1суб > -z <суб > 2суб > ) 2. Он не избавляется от умножения, но устраняет операцию с квадратным корнем.

Ответ 8

Как часто обновляются входные векторы и как часто они сортируются? В зависимости от вашего дизайна может быть довольно эффективно расширить класс "Vec3" с заранее рассчитанным расстоянием и отсортировать его. Особенно актуально, если ваша реализация позволяет использовать векторизованные операции.

Кроме этого, см. статью flipcode.com о приближении функций расстояния для обсуждения еще одного подхода.

Ответ 9

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

1) Перепишите массив в один список расстояний на Манхэттене с помощью out [i] = abs (posn [i].x - player.x) + abs (posn [i].y - player.y) + abs (posn [i].z - player.z);

2) Теперь вы можете использовать сортировку radix для чисел с плавающей запятой, чтобы упорядочить их.

Обратите внимание, что на практике это будет намного быстрее, чем сортировка списка трехмерных позиций, поскольку это значительно снижает требования к пропускной способности памяти в операции сортировки, которые все время будут потрачены, и в которых непредсказуемые обращения и записи будут происходить. Это будет работать во время O (N).

Если многие точки неподвижны в каждом направлении, есть гораздо более быстрые алгоритмы, такие как использование KD-Trees, хотя реализация довольно сложна, и получить более хорошие шаблоны доступа к файлам намного сложнее.

Ответ 10

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

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

Ответ 11

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

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

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

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

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

Ответ 12

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

Это большой, хотя, хотя.

Ответ 13

Если ваша операция происходит много, возможно, стоит добавить ее в некоторую трехмерную структуру данных. Вероятно, вам нужна сортировка по расстоянию, чтобы решить, какой объект виден, или какая-то аналогичная задача. В порядке сложности вы можете использовать:

  • Единое (кубическое) подразделение

    Разделите использованное пространство на ячейки и назначьте объекты ячейкам. Быстрый доступ к элементу, соседи тривиальны, но пустые ячейки занимают много места.

  • квадрадерево

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

  • Octree

    То же, что и Quadtree, но делит на 8, оптимально, даже если объекты находятся друг над другом.

  • Дерево Kd

    Учитывая некоторую эвристическую функцию стоимости и порог, разделите пространство на две половины с плоскостью, где функция стоимости минимальна. (Например: одинаковое количество объектов на каждой стороне.) Повторите рекурсивно до достижения порога. Всегда логарифмический, соседи труднее получить, пространство эффективно (и работает во всех измерениях).

Используя любую из вышеперечисленных структур данных, вы можете начать с позиции и перейти от соседа к соседству, чтобы перечислить объекты на расстоянии. Вы можете остановиться на желаемом расстоянии. Вы также можете пропускать ячейки, которые нельзя увидеть с камеры.

Для проверки расстояния вы можете выполнить одну из вышеупомянутых процедур, но в конечном итоге они не будут хорошо масштабироваться с увеличением количества объектов. Они могут использоваться для отображения данных, которые занимают сотни гигабайт пространства на жестком диске.