Как эффективно рассчитать отражения и повороты, которые отображают единичный куб на себя? - PullRequest
Новая
       134

Как эффективно рассчитать отражения и повороты, которые отображают единичный куб на себя?

2 голосов
/ 06 февраля 2020

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

Без ограничения общности предположим, что куб является единичным кубом с одним углом в начале координат, т. Е. (0,0,0), и противоположным углом. в (1,1,1). Я закодировал углы куба как 3-битное целое число. Таким образом, 0 (= 0b000) представляет угол в начале координат, 1 (= 0b001) представляет угол в (0,0,1) и 7 (= 0b111) представляет угол в (1,1,1). Единственные разрешенные повороты и отражения находятся вокруг центра куба (½, ½, ½) и такие, что углы заканчиваются в целочисленных координатах. Это означает, что есть только 48 различных возможных преобразований. (Первый угол может быть отображен на 8 возможных позиций, следующий угол на 3, третий на 2, и это фиксирует положение остальных углов.)

Я еще не решил, как кодировать преобразование, хотя должна быть возможность закодировать его как одно 32-разрядное целое число (или даже 6-разрядное целое число, поскольку существует только 48 возможных преобразований). Затем преобразование можно применить как функцию, которая отображает каждый угол куба на его местоположение после преобразования. Т.е. 

int transform(int corner, int transformation) {
  // magic happens here
  return result;
}

Кроме того, у меня также должна быть функция combine, которая объединяет преобразования, так что transform(corner, combine(a,b)) равно transform(transform(corner, b), a).

Поскольку эти функции будут вызываться около миллиарда раз во-вторых, они должны быть быстрыми. Хотя transform будет вызываться примерно в 4 раза чаще, чем комбинат. Алгоритм является рекурсивным, поэтому, если кодировка преобразования использует более одного 32-разрядного целого числа, это потребует дополнительных затрат времени выполнения для помещения его в стек.

До сих пор я выяснил, что проблема может быть разложенным на переворачивание битов, которое может быть сделано с одной операцией xor, и перестановкой битов (которую я пока не знаю, как сделать эффективно). Тем не менее, операция, которая выполняет оба одновременно, может быть более эффективной.

Я намерен использовать это в коде C ++, который уже использует встроенные функции SSE4.1. Хотя решение, которое не использует встроенные функции или требует только SSE3, является предпочтительным. И, в конце концов, скорость важнее всего. Я попытаюсь использовать http://quick-bench.com/ для сравнения решений.

(Примечание. Я использовал тег affinetransform, поскольку тег orthogonaltransform отсутствует, и я не хотел его создавать).

1 Ответ

0 голосов
/ 04 мая 2020

Вы можете сохранить преобразование в виде массива из 8 байтов, который кодирует перестановку углов кубов. Метод transform будет таким же простым, как поиск в массиве. Объединить два из этих преобразований можно было бы в al oop, но это было бы довольно медленно. Однако оказывается, что SSSE3 имеет встроенный c, который делает это в одной инструкции: _mm_shuffle_pi8.

Таким образом, необходимые методы могут быть реализованы следующим образом: 

#include <tmmintrin.h>

int transform(int corner, __m64 transformation) {
    uint8_t array[8];
    memcpy(array, &transformation, 8); // This call is optimized away by the compiler.
    return array[corner];
}

__m64 combine(T a, T b) {
    return _mm_shuffle_pi8(b, a);
}

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

Я также реализовал несколько различных методов для сравнения:

  • Упакуйте перестановку как клев (4-разрядные целые числа) в int32 и используйте al oop для вычисления результата combine. При использовании вдвое меньше памяти, она примерно в 3-5 раз медленнее.
  • Работайте над 6-битной кодировкой, предложенной напрямую Мило Брандтом. Однако мне не удалось реализовать это правильно.
  • Ограничить разрешенные преобразования только комбинацией отражений, выровненных по оси. Их можно быстро вычислить, используя побитовый XOR. Это примерно на 30-50% быстрее.

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

...