algorithm - Cómo calcular un número 3D Morton(intercalar los bits de 3 ints)

bit-manipulation z-order-curve

Question

Estoy buscando una forma rápida de calcular un número 3D Morton. Este sitio tiene un truco basado en el número mágico para hacerlo para los números 2D de Morton, pero no parece obvio cómo extenderlo a 3D: http://www-graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN

Así que, básicamente, tengo 3 números de 10 bits que quiero intercalar en un solo número de 30 bits con un número mínimo de operaciones.

Answer 1

A continuación se muestra el fragmento de código para generar la clave Morton de tamaño 64 bits para el punto 3-D.

using namespace std;

unsigned long long spreadBits(unsigned long long x)
{
    x=(x|(x<<20))&0x000001FFC00003FF;
    x=(x|(x<<10))&0x0007E007C00F801F;
    x=(x|(x<<4))&0x00786070C0E181C3;
    x=(x|(x<<2))&0x0199219243248649;
    x=(x|(x<<2))&0x0649249249249249;
    x=(x|(x<<2))&0x1249249249249249;
    return x;
}

int main()
{
    unsigned long long x,y,z,con=1;
    con=con<<63;
    printf("%#llx/n",(spreadBits(x)|(spreadBits(y)<<1)|(spreadBits(z)<<2))|con);    
}

Answer 2

Aquí hay un generador que hice en Ruby para producir métodos de codificación de longitud arbitraria:

def morton_code_for(bits)
  method = ''''

  limit_mask = (1 << (bits * 3)) - 1
  split = (2 ** ((Math.log(bits) / Math.log(2)).to_i + 1)).to_i
  level = 1

  puts "// Coding for 3 #{bits}-bit values"

  loop do
    shift = split
    split /= 2
    level *= 2

    mask = ([ ''1'' * split ] * level).join(''0'' * split * 2).to_i(2) & limit_mask

    expression = "v = (v | (v << %2d)) & 0x%016x;" % [ shift, mask ]

    method << expression

    puts "%s // 0b%064b" % [ expression, mask ]

    break if (split <= 1)
  end

  puts
  print "// Test of method results: "
  v = (1 << bits) - 1
  puts eval(method).to_s(2)
end

morton_code_for(21)

La salida es adecuadamente genérica y puede adaptarse según sea necesario. Muestra de salida:

// Coding for 3 21-bit values
v = (v | (v << 32)) & 0x7fff00000000ffff; // 0b0111111111111111000000000000000000000000000000001111111111111111
v = (v | (v << 16)) & 0x00ff0000ff0000ff; // 0b0000000011111111000000000000000011111111000000000000000011111111
v = (v | (v <<  8)) & 0x700f00f00f00f00f; // 0b0111000000001111000000001111000000001111000000001111000000001111
v = (v | (v <<  4)) & 0x30c30c30c30c30c3; // 0b0011000011000011000011000011000011000011000011000011000011000011
v = (v | (v <<  2)) & 0x1249249249249249; // 0b0001001001001001001001001001001001001001001001001001001001001001

// Test of method results: 1001001001001001001001001001001001001001001001001001001001001

Answer 3

Buen momento, ¡acabo de hacer esto el mes pasado!

La clave fue hacer dos funciones. Uno distribuye bits a cada tercer bit. Entonces podemos combinar tres de ellos juntos (con un cambio para los dos últimos) para obtener el valor final entrelazado de Morton.

Este código se entrelaza comenzando en los bits ALTOS (lo cual es más lógico para los valores de punto fijo). Si su aplicación es de solo 10 bits por componente, simplemente cambie cada valor dejado por 22 para que comience en los bits altos.

/* Takes a value and "spreads" the HIGH bits to lower slots to seperate them.
   ie, bit 31 stays at bit 31, bit 30 goes to bit 28, bit 29 goes to bit 25, etc.
   Anything below bit 21 just disappears. Useful for interleaving values
   for Morton codes. */
inline unsigned long spread3(unsigned long x)
{
  x=(0xF0000000&x) | ((0x0F000000&x)>>8) | (x>>16); // spread top 3 nibbles
  x=(0xC00C00C0&x) | ((0x30030030&x)>>4);
  x=(0x82082082&x) | ((0x41041041&x)>>2);
  return x;
}

inline unsigned long morton(unsigned long x, unsigned long y, unsigned long z)
{
  return spread3(x) | (spread3(y)>>1) | (spread3(z)>>2);
}

Answer 4

El siguiente código encuentra el número de Morton de los tres números de entrada de 10 bits. Utiliza la idee de su enlace y realiza la distribución del bit en los pasos 5-5, 3-2-3-2, 2-1-1-1-2-1-1-1 y 1-1-1- 1-1-1-1-1-1-1 porque 10 no es una potencia de dos.

......................9876543210
............98765..........43210
........987....56......432....10
......98..7..5..6....43..2..1..0
....9..8..7..5..6..4..3..2..1..0

Arriba puedes ver la ubicación de cada bit antes del primero y después de cada uno de los cuatro pasos.

public static Int32 GetMortonNumber(Int32 x, Int32 y, Int32 z)
{
    return SpreadBits(x, 0) | SpreadBits(y, 1) | SpreadBits(z, 2);
}

public static Int32 SpreadBits(Int32 x, Int32 offset)
{
    if ((x < 0) || (x > 1023))
    {
        throw new ArgumentOutOfRangeException();
    }

    if ((offset < 0) || (offset > 2))
    {
        throw new ArgumentOutOfRangeException();
    }

    x = (x | (x << 10)) & 0x000F801F;
    x = (x | (x <<  4)) & 0x00E181C3;
    x = (x | (x <<  2)) & 0x03248649;
    x = (x | (x <<  2)) & 0x09249249;

    return x << offset;
}

Answer 5

La más simple es probablemente una tabla de búsqueda, si tiene 4K de espacio libre:

static uint32_t t [ 1024 ] = { 0, 0x1, 0x8, ... };

uint32_t m ( int a, int b, int c )
{
    return t[a] | ( t[b] << 1 ) | ( t[c] << 2 );
}

El truco de bits utiliza desplazamientos y máscaras para separar los bits, de modo que cada vez que cambia el valor y lo ordena, copia algunos de los bits en espacios vacíos, y enmascara las combinaciones para que solo queden los bits originales.

por ejemplo:

x = 0xabcd;
  = 0000_0000_0000_0000_1010_1011_1100_1101    

x = (x | (x << S[3])) & B[3]; 

  = ( 0x00abcd00 | 0x0000abcd ) & 0xff00ff 
  = 0x00ab__cd & 0xff00ff 
  = 0x00ab00cd
  = 0000_0000_1010_1011_0000_0000_1100_1101
x = (x | (x << S[2])) & B[2]; 
  = ( 0x0ab00cd0 | 0x00ab00cd) & 0x0f0f0f0f 
  =   0x0a_b_c_d & 0x0f0f0f0f 
  = 0x0a0b0c0d 
  = 0000_1010_0000_1011_0000_1100_0000_1101
x = (x | (x << S[1])) & B[1]; 
  = ( 0000_1010_0000_1011_0000_1100_0000_1101 | 
      0010_1000_0010_1100_0011_0000_0011_0100 ) &
      0011_0011_0011_0011_0011_0011_0011_0011
  =   0010_0010_0010_0011_0011_0000_0011_0001
x = (x | (x << S[0])) & B[0]; 
  = ( 0010_0010_0010_0011_0011_0000_0011_0001 | 
      0100_0100_0100_0110_0110_0000_0110_0010 ) &
      0101_0101_0101_0101_0101_0101_0101_0101
  =   0100_0010_0100_0101_0101_0000_0101_0001

En cada iteración, cada bloque se divide en dos, el bit del extremo derecho de la mitad izquierda del bloque se mueve a su posición final y se aplica una máscara, de modo que solo quedan los bits necesarios.

Una vez que haya espaciado las entradas, cambiarlas para que los valores de uno caigan en los ceros de la otra es fácil.

Para extender esa técnica por más de dos bits entre los valores en el resultado final, debe aumentar los cambios entre donde terminan los bits. Se vuelve un poco más complicado, ya que el tamaño del bloque de inicio no es una potencia de 2, por lo que podría dividirlo en el medio o en una potencia de 2 límites.

Entonces una evolución como esta podría funcionar:

0000_0000_0000_0000_0000_0011_1111_1111    
0000_0011_0000_0000_0000_0000_1111_1111    
0000_0011_0000_0000_1111_0000_0000_1111    
0000_0011_0000_1100_0011_0000_1100_0011    
0000_1001_0010_0100_1001_0010_0100_1001    

// 0000_0000_0000_0000_0000_0011_1111_1111    
x = ( x | ( x << 16 ) ) & 0x030000ff;
// 0000_0011_0000_0000_0000_0000_1111_1111    
x = ( x | ( x << 8 ) ) & 0x0300f00f;
// 0000_0011_0000_0000_1111_0000_0000_1111    
x = ( x | ( x << 4 ) ) & 0x030c30c3;
// 0000_0011_0000_1100_0011_0000_1100_0011    
x = ( x | ( x << 2 ) ) & 0x09249249;
// 0000_1001_0010_0100_1001_0010_0100_1001    

Realice la misma transformación en las entradas, cambie una por una y otra por dos, o ambas juntas, y listo.

Answer 6

Tomé el anterior y lo modifiqué para combinar 3 números de 16 bits en un número de 48 (realmente 64) bits. Tal vez le ahorrará a alguien el poco de pensamiento para llegar allí.

#include <inttypes.h>
#include <assert.h>
uint64_t zorder3d(uint64_t x, uint64_t y, uint64_t z){
     static const uint64_t B[] = {0x00000000FF0000FF, 0x000000F00F00F00F,
                                    0x00000C30C30C30C3, 0X0000249249249249};           
     static const int S[] =  {16, 8, 4, 2}; 
     static const uint64_t MAXINPUT = 65536;

     assert( ( (x < MAXINPUT) ) && 
      ( (y < MAXINPUT) ) && 
      ( (z < MAXINPUT) )
     );

     x = (x | (x << S[0])) & B[0];
     x = (x | (x << S[1])) & B[1];
     x = (x | (x << S[2])) & B[2];
     x = (x | (x << S[3])) & B[3];

     y = (y | (y << S[0])) & B[0];
     y = (y | (y << S[1])) & B[1];
     y = (y | (y << S[2])) & B[2];
     y = (y | (y << S[3])) & B[3];

     z = (z | (z <<  S[0])) & B[0];
     z = (z | (z <<  S[1])) & B[1];
     z = (z | (z <<  S[2])) & B[2];
     z = (z | (z <<  S[3])) & B[3];

     return ( x | (y << 1) | (z << 2) );
    }

Answer 7

Tuve un problema similar hoy, pero en lugar de 3 números, tengo que combinar una cantidad arbitraria de números de cualquier longitud de bit. Utilicé mi propio tipo de algoritmo de dispersión y enmascaramiento de bit y lo apliqué a C # BigIntegers. Aquí está el código que escribí. Como paso de compilación, calcula los números mágicos y la máscara para la cantidad de dimensiones y profundidad de bits dadas. Luego puede reutilizar el objeto para múltiples conversiones.

/// <summary>
/// Convert an array of integers into a Morton code by interleaving the bits.
/// Create one Morton object for a given pair of Dimension and BitDepth and reuse if when encoding multiple 
/// Morton numbers.
/// </summary>  
public class Morton
{
    /// <summary>
    /// Number of bits to use to represent each number being interleaved.
    /// </summary>
    public int BitDepth { get; private set; }

    /// <summary>
    /// Count of separate numbers to interleave into a Morton number.
    /// </summary>
    public int Dimensions { get; private set; }

    /// <summary>
    /// The MagicNumbers spread the bits out to the right position.
    /// Each must must be applied and masked, because the bits would overlap if we only used one magic number.
    /// </summary>
    public BigInteger LargeMagicNumber { get; private set; }
    public BigInteger SmallMagicNumber { get; private set; }

    /// <summary>
    /// The mask removes extraneous bits that were spread into positions needed by the other dimensions.
    /// </summary>
    public BigInteger Mask { get; private set; }

    public Morton(int dimensions, int bitDepth)
    {
        BitDepth = bitDepth;
        Dimensions = dimensions;
        BigInteger magicNumberUnit = new BigInteger(1UL << (int)(Dimensions - 1));
        LargeMagicNumber = magicNumberUnit;
        BigInteger maskUnit = new BigInteger(1UL << (int)(Dimensions - 1));
        Mask = maskUnit;
        for (var i = 0; i < bitDepth - 1; i++)
        {
            LargeMagicNumber = (LargeMagicNumber << (Dimensions - 1)) | (i % 2 == 1 ? magicNumberUnit : BigInteger.Zero);
            Mask = (Mask << Dimensions) | maskUnit;       
        }
        SmallMagicNumber = (LargeMagicNumber >> BitDepth) << 1; // Need to trim off pesky ones place bit.
    }

    /// <summary>
    /// Interleave the bits from several integers into a single BigInteger.
    /// The high-order bit from the first number becomes the high-order bit of the Morton number.
    /// The high-order bit of the second number becomes the second highest-ordered bit in the Morton number.
    /// 
    /// How it works.
    /// 
    /// When you multupliy by the magic numbers you make multiple copies of the the number they are multplying, 
    /// each shifted by a different amount.
    /// As it turns out, the high order bit of the highest order copy of a number is N bits to the left of the 
    /// second bit of the second copy, and so forth. 
    /// This is because each copy is shifted one bit less than N times the copy number.
    /// After that, you apply the AND-mask to unset all bits that are not in position.
    /// 
    /// Two magic numbers are needed because since each copy is shifted one less than the bitDepth, consecutive
    /// copies would overlap and ruin the algorithm. Thus one magic number (LargeMagicNumber) handles copies 1, 3, 5, etc, while the 
    /// second (SmallMagicNumber) handles copies 2, 4, 6, etc.
    /// </summary>
    /// <param name="vector">Integers to combine.</param>
    /// <returns>A Morton number composed of Dimensions * BitDepth bits.</returns>
    public BigInteger Interleave(int[] vector)
    {
        if (vector == null || vector.Length != Dimensions)
            throw new ArgumentException("Interleave expects an array of length " + Dimensions, "vector");
        var morton = BigInteger.Zero;
        for (var i = 0; i < Dimensions; i++)
        {
            morton |= (((LargeMagicNumber * vector[i]) & Mask) | ((SmallMagicNumber * vector[i]) & Mask)) >> i;
        }
        return morton;
    }


    public override string ToString()
    {
        return "Morton(Dimension: " + Dimensions + ", BitDepth: " + BitDepth 
            + ", MagicNumbers: " + Convert.ToString((long)LargeMagicNumber, 2) + ", " + Convert.ToString((long)SmallMagicNumber, 2)
            + ", Mask: " + Convert.ToString((long)Mask, 2) + ")";
    }
}

Answer 8

Aquí está mi solución con un script de Python:

Tomé la indirecta de su comentario: Fabian "ryg" Giesen
Lee el comentario largo a continuación! Necesitamos hacer un seguimiento de qué bits deben ir hasta qué punto.
Luego, en cada paso, seleccionamos estos bits y los movemos y aplicamos una máscara de bits (ver las últimas líneas del comentario) para enmascararlos.

Bit Distances: [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
Bit Distances (binary): [''0'', ''10'', ''100'', ''110'', ''1000'', ''1010'', ''1100'', ''1110'', ''10000'', ''10010'']
Shifting bits by 1   for bits idx: []
Shifting bits by 2   for bits idx: [1, 3, 5, 7, 9]
Shifting bits by 4   for bits idx: [2, 3, 6, 7]
Shifting bits by 8   for bits idx: [4, 5, 6, 7]
Shifting bits by 16  for bits idx: [8, 9]
BitPositions: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Shifted bef.:   0000 0000 0000 0000 0000 0011 0000 0000 hex: 0x300
Shifted:        0000 0011 0000 0000 0000 0000 0000 0000 hex: 0x3000000
NonShifted:     0000 0000 0000 0000 0000 0000 1111 1111 hex: 0xff
Bitmask is now: 0000 0011 0000 0000 0000 0000 1111 1111 hex: 0x30000ff

Shifted bef.:   0000 0000 0000 0000 0000 0000 1111 0000 hex: 0xf0
Shifted:        0000 0000 0000 0000 1111 0000 0000 0000 hex: 0xf000
NonShifted:     0000 0011 0000 0000 0000 0000 0000 1111 hex: 0x300000f
Bitmask is now: 0000 0011 0000 0000 1111 0000 0000 1111 hex: 0x300f00f

Shifted bef.:   0000 0000 0000 0000 1100 0000 0000 1100 hex: 0xc00c
Shifted:        0000 0000 0000 1100 0000 0000 1100 0000 hex: 0xc00c0
NonShifted:     0000 0011 0000 0000 0011 0000 0000 0011 hex: 0x3003003
Bitmask is now: 0000 0011 0000 1100 0011 0000 1100 0011 hex: 0x30c30c3

Shifted bef.:   0000 0010 0000 1000 0010 0000 1000 0010 hex: 0x2082082
Shifted:        0000 1000 0010 0000 1000 0010 0000 1000 hex: 0x8208208
NonShifted:     0000 0001 0000 0100 0001 0000 0100 0001 hex: 0x1041041
Bitmask is now: 0000 1001 0010 0100 1001 0010 0100 1001 hex: 0x9249249

x &= 0x3ff
x = (x | x << 16) & 0x30000ff   <<< THIS IS THE MASK for shifting 16 (for bit 8 and 9)
x = (x | x << 8) & 0x300f00f
x = (x | x << 4) & 0x30c30c3
x = (x | x << 2) & 0x9249249

Por lo tanto, para un número de 10 bits y 2 bits de entrelazado (para 32 bits), debe hacer lo siguiente:

x &= 0x3ff
x = (x | x << 16) & 0x30000ff   #<<< THIS IS THE MASK for shifting 16 (for bit 8 and 9)
x = (x | x << 8) & 0x300f00f
x = (x | x << 4) & 0x30c30c3
x = (x | x << 2) & 0x9249249

Y para un número de 21 bits y 2 bits de entrelazado (para 64 bits), debe hacer lo siguiente:

x &= 0x1fffff
x = (x | x << 32) & 0x1f00000000ffff
x = (x | x << 16) & 0x1f0000ff0000ff
x = (x | x << 8) & 0x100f00f00f00f00f
x = (x | x << 4) & 0x10c30c30c30c30c3
x = (x | x << 2) & 0x1249249249249249

Y para un número de 42 bits y 2 bits de entrelazado (para 128 bits), debe hacer lo siguiente (en caso de que lo necesite ;-)):

x &= 0x3ffffffffff
x = (x | x << 64) & 0x3ff0000000000000000ffffffffL
x = (x | x << 32) & 0x3ff00000000ffff00000000ffffL
x = (x | x << 16) & 0x30000ff0000ff0000ff0000ff0000ffL
x = (x | x << 8) & 0x300f00f00f00f00f00f00f00f00f00fL
x = (x | x << 4) & 0x30c30c30c30c30c30c30c30c30c30c3L
x = (x | x << 2) & 0x9249249249249249249249249249249L

Python Script para producir y verificar los patrones de entrelazado.

def prettyBinString(x,d=32,steps=4,sep=".",emptyChar="0"):
    b = bin(x)[2:]
    zeros = d - len(b)


    if zeros <= 0: 
        zeros = 0
        k = steps - (len(b) % steps)
    else:
        k = steps - (d % steps)

    s = ""
    #print("zeros" , zeros)
    #print("k" , k)
    for i in range(zeros): 
        #print("k:",k)
        if(k%steps==0 and i!= 0):
            s+=sep
        s += emptyChar
        k+=1

    for i in range(len(b)):
        if( (k%steps==0 and i!=0 and zeros == 0) or  (k%steps==0 and zeros != 0) ):
            s+=sep
        s += b[i]
        k+=1
    return s    

def binStr(x): return prettyBinString(x,32,4," ","0")


def computeBitMaskPatternAndCode(numberOfBits, numberOfEmptyBits):
    bitDistances=[ i*numberOfEmptyBits for i in range(numberOfBits) ]
    print("Bit Distances: " + str(bitDistances))
    bitDistancesB = [bin(dist)[2:] for dist in  bitDistances]
    print("Bit Distances (binary): " + str(bitDistancesB))
    moveBits=[] #Liste mit allen Bits welche aufsteigend um 2, 4,8,16,32,64,128 stellen geschoben werden müssen

    maxLength = len(max(bitDistancesB, key=len))
    abort = False
    for i in range(maxLength):
        moveBits.append([])
        for idx,bits in enumerate(bitDistancesB):
            if not len(bits) - 1 < i:
                if(bits[len(bits)-i-1] == "1"):
                    moveBits[i].append(idx)

    for i in range(len(moveBits)):
        print("Shifting bits by " + str(2**i) + "/t for bits idx: " + str(moveBits[i]))

    bitPositions = range(numberOfBits);
    print("BitPositions: " + str(bitPositions))
    maskOld = (1 << numberOfBits) -1

    codeString = "x &= " + hex(maskOld) + "/n"
    for idx in xrange(len(moveBits)-1, -1, -1):
        if len(moveBits[idx]):


           shifted = 0
           for bitIdxToMove in moveBits[idx]:
                shifted |= 1<<bitPositions[bitIdxToMove];
                bitPositions[bitIdxToMove] += 2**idx; # keep track where the actual bit stands! might get moved several times

           # Get the non shifted part!     
           nonshifted = ~shifted & maskOld

           print("Shifted bef.:/t" + binStr(shifted) + " hex: " + hex(shifted))
           shifted = shifted << 2**idx
           print("Shifted:/t" + binStr(shifted)+ " hex: " + hex(shifted))

           print("NonShifted:/t" + binStr(nonshifted) + " hex: " + hex(nonshifted))
           maskNew =  shifted | nonshifted
           print("Bitmask is now:/t" + binStr(maskNew) + " hex: " + hex(maskNew) +"/n")
           #print("Code: " + "x = x | x << " +str(2**idx)+ " & " +hex(maskNew))

           codeString += "x = (x | x << " +str(2**idx)+ ") & " +hex(maskNew) + "/n"
           maskOld = maskNew
    return codeString


numberOfBits = 10;
numberOfEmptyBits = 2;
codeString = computeBitMaskPatternAndCode(numberOfBits,numberOfEmptyBits);
print(codeString)

def partitionBy2(x):
    exec(codeString)
    return x

def checkPartition(x):
    print("Check partition for: /t" + binStr(x))
    part = partitionBy2(x);
    print("Partition is : /t/t" + binStr(part))
    #make the pattern manualy
    partC = long(0);
    for bitIdx in range(numberOfBits):
        partC  = partC | (x & (1<<bitIdx)) << numberOfEmptyBits*bitIdx
    print("Partition check is :/t" + binStr(partC))
    if(partC == part):
        return True
    else:
        return False

checkError = False        
for i in range(20):
    x = random.getrandbits(numberOfBits);
    if(checkPartition(x) == False):
        checkError = True
        break
if not checkError:
    print("CHECK PARTITION SUCCESSFUL!!!!!!!!!!!!!!!!...")
else:
    print("checkPartition has ERROR!!!!")

¡Añadiré el código de descodificación también en un rato!

Answer 9

Puedes usar la misma técnica. Supongo que las variables contienen enteros de 32 bits con los 22 bits más altos establecidos en 0 (lo cual es un poco más restrictivo de lo necesario). Para cada variable x contenga uno de los tres enteros de 10 bits, hacemos lo siguiente:

x = (x | (x << 16)) & 0x030000FF;
x = (x | (x <<  8)) & 0x0300F00F;
x = (x | (x <<  4)) & 0x030C30C3;
x = (x | (x <<  2)) & 0x09249249;

Luego, con x , y y z los tres enteros manipulados de 10 bits obtenemos el resultado al tomar:

x | (y << 1) | (z << 2)

La forma en que funciona esta técnica es la siguiente. Cada una de las líneas x = ... arriba "divide" grupos de bits por la mitad de modo que haya espacio suficiente entre los bits de los otros enteros. Por ejemplo, si consideramos tres enteros de 4 bits, dividimos uno con los bits 1234 en 000012000034 donde los ceros están reservados para los otros enteros. En el siguiente paso dividimos 12 y 34 de la misma forma para obtener 001002003004. Aunque 10 bits no constituyen una buena división repetida en dos grupos, puedes considerar 16 bits donde pierdes los más altos al final .

Como puede ver en la primera línea, en realidad solo necesita eso para cada entero de entrada x que contenga x & 0x03000000 == 0 .