Оптимизация картирования Point to Voxel

Question

Я использовал профилировщик для просмотра некоторого кода, который еще недостаточно быстро работает Было обнаружено, что следующая функция занимала большую часть времени, а половина этой функции была потрачена на floor. Теперь есть две возможности: оптимизировать эту функцию или перейти на один уровень выше и уменьшить количество вызовов этой функции. Интересно, возможно ли первое?

int Sph::gridIndex (Vector3 position) const {
    int mx = ((int)floor(position.x / _gridIntervalSize) % _gridSize);
    int my = ((int)floor(position.y / _gridIntervalSize) % _gridSize);
    int mz = ((int)floor(position.z / _gridIntervalSize) % _gridSize);

    if (mx < 0) {
        mx += _gridSize;
    }
    if (my < 0) {
        my += _gridSize;
    }
    if (mz < 0) {
        mz += _gridSize;
    }

    int x = mx * _gridSize * _gridSize;
    int y = my * _gridSize;
    int z = mz * 1;
    return x + y + z;
}

Vector3 - это простой класс, который хранит три числа с плавающей точкой и предоставляет несколько перегруженных операторов. _gridSize имеет тип int, а _gridIntervalSize является float. Есть _gridSize ^ 3 сегмента.

Цель функции - обеспечить поддержку хеш-таблицы. Каждая 3d-точка сопоставляется с индексом, и точки, которые лежат в одном и том же вокселе размера _gridIntervalSize ^ 3, должны попадать в одно и то же ведро.

Answer 1

Первое правило оптимизации, когда речь идет о математике: устранение деления, квадратных корней и тригонометрических функций.

inverse_size = 1 / _gridIntervalSize; ....that should be done only once, not once per call.</p> <pre><code>int mx = ((int)floor(position.x * inverse_size) % _gridSize); int my = ((int)floor(position.y * inverse_size) % _gridSize); int mz = ((int)floor(position.z * inverse_size) % _gridSize);

Я бы также рекомендовал отказаться от операции мода, потому что это еще одно деление - если размер сетки равен степени 2, вы можете использовать & (gridsize-1), что также позволит вам удалить условный код внизу, что является еще одной большой экономией.

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

Answer 2

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

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

Использование fmod может гарантировать, что у вас есть безопасное наиболее отрицательное значение, и заменить целое число %, но это, вероятно, анти-оптимизация.Тем не менее, в качестве быстрого изменения, возможно, стоит проверить.

Кроме того, проверьте, поддерживает ли ваша платформа векторные инструкции и можно ли легко рекомендовать их использовать компилятору.Микросхемы x86, безусловно, имеют как целочисленные векторные инструкции, так и float (старые инструкции Pentium 1 MMX, для начала) и могут справиться с этим гораздо более эффективно, чем «обычный» набор команд ЦП.Это может даже быть причиной выкапывания списка встроенных инструкций вектора для вашего компилятора и некоторой ручной оптимизации.Просто проверьте, что компилятор может сделать для вас в первую очередь - я не уверен, что такого рода компиляторы оптимизации уже сделают для вас.

Одна, вероятно, тривиальная часть микрооптимизации ...

return (mx * _gridSize + my) * _gridSize + mz;

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

О - смотрите первые подчеркивания.Это зарезервированные идентификаторы.Вряд ли это может вызвать проблемы, но вы не можете жаловаться, если они это делают.

РЕДАКТИРОВАТЬ

Еще один способ избежать floor состоит в обработке положительных и отрицательныхпо отдельности.Если вы согласны с тем, что элементы, расположенные по краям ячейки сетки, могут находиться не в той ячейке (возможно, в любом случае, поскольку значения с плавающей точкой следует считать приблизительными)Просто примените смещение -1 в отрицательном случае, чтобы оттянуть его от нуля на почти точно правильную величину, чтобы компенсировать усечение.Вы могли бы рассмотреть немного изменяющуюся мантиссу впоследствии (чтобы получить уже целочисленные значения в ячейке, которую вы ожидаете), но это, вероятно, не нужно.

Если вы можете наложить ограничения степени два наваши размеры, может быть немного бесполезный способ эффективно извлечь положение сетки из числа с плавающей запятой, избегая некоторых или всех умножения, пола и % для каждого из x, y и z, предполагая стандартное представление с плавающей запятой (т.е. это непереносимо).Опять же, обрабатывайте положительное и отрицательное отдельно.Извлеките экспоненту, соответственно сдвиньте мантиссу, затем замаскируйте ненужные биты.

Answer 3

Я думаю, вам нужно посмотреть выше по иерархии, чтобы получить реальные улучшения скорости.То есть хранение точек в хэш-карте - действительно самое эффективное решение?Я предполагаю, что у вас есть массив массивов Vector3, то есть:

Vector3 * points [размер] [размер] [размер]

, где каждый элемент в массиве 3Dмассив Vector3.

Используемый вами алгоритм не гарантирует равномерного распределения точек в каждом массиве Vector3, что может быть проблемой.Кластер точек в пределах _gridIntervalSize будет отображаться в тот же массив.

Альтернативным методом будет использование окт-деревьев, которые похожи на двоичные деревья, но каждый узел имеет восемь дочерних узлов.Каждому узлу требуются значения min / max x / y / z для определения объема, охватываемого узлом.Чтобы добавить значения в дерево:

Рекурсивное дерево поиска для поиска наименьшего узла, который может содержать точку

Добавление точки к узлу

Если количество точек в узле>верхний предел количества точек в узле

Создание дочерних узлов и перемещение точек в дочерние узлы

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

Преобразование чисел с плавающей точкой в ​​целочисленные значения и размещение плоскостей деления на целочисленных значениях также ускорит процесс.

Поиск по приведенным выше терминам приведет вас к большемууглубленный анализ алгоритмов.

Наконец, использование поплавков (или двойников) для координат в бесконечной плоскости - плохая идея - чем дальше вы получаете от (0,0,0), тем меньше точностьиметь (промежутки между значениями с плавающей запятой увеличивается с увеличением значения).Вам нужно будет «сбросить» значения с плавающей запятой, чтобы сохранить точность.Одним из методов является «разбиение» на ячейки и изменение координат для использования целочисленных и с плавающей запятой частей.Целочисленная часть определяет «плитку», а часть с плавающей запятой определяет положение в плитке.Этот метод дает вам гораздо более простой метод хеширования - просто используйте целочисленные части, не требуется вызов floor и требуются только целочисленные вычисления.Другой подход заключается в использовании значений с фиксированной запятой, а не значений с плавающей запятой, но это ограничит вашу точность.Это значительно упростит вычисления по всем границам листов.

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