Очень быстрая проверка расстояния 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

Вы можете опустить квадратный корень, потому что для всех положительных (или действительно, неотрицательных) чисел 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.

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

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

Answer 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 лучших ближайших игроков, иПересортируйте, используя правильные расчеты расстояния.

Answer 3

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

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

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

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

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

Answer 4

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

---

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

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

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

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 «Понимания цифровой обработки сигналов» Ричарда Г. Лайонса имеется невероятная коллекция двухмерных алгоритмов расстояния (например, аппроксимации величин комплексных чисел). В качестве одного примера:

Макс = х> у? х: у;

Мин = х <у? х: у; </p>

if (Мин. <0,04142135Макс.) </p>

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

еще

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

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

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

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

Answer 5

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

Answer 6

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

float Get3dDistance( Vec3 c1, Vec3 c2 );

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

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

Answer 7

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

Answer 8

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

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

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

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

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

Answer 9

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

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

Answer 10

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

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

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

2. Quadtree

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

3. Octree

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

4. Дерево Kd

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

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

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