Comment calculer un nombre 3D Morton (entrelacez les bits de 3 ints)
https://stackoverflow.com/questions/1024754
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je cherche un moyen rapide de calculer un nombre 3D Morton. Ce site possède un truc magique permettant de le faire pour Les numéros 2D de Morton, mais il ne semble pas évident de l'étendre à la 3D.
Donc, fondamentalement, j'ai 3 nombres de 10 bits que je veux entrelacer en un seul nombre de 30 bits avec un nombre minimal d'opérations.
La solution
Vous pouvez utiliser la même technique. Je suppose que les variables contiennent des entiers 32 bits avec les 22 bits les plus élevés réglés sur 0 (ce qui est un peu plus restrictif que nécessaire). Pour chaque variable x contenant l'un des trois nombres entiers de 10 bits, nous procédons comme suit:
x = (x | (x << 16)) & 0x030000FF;
x = (x | (x << 8)) & 0x0300F00F;
x = (x | (x << 4)) & 0x030C30C3;
x = (x | (x << 2)) & 0x09249249;
Ensuite, avec x , y et z , les trois entiers manipulés de 10 bits permettent d'obtenir le résultat en prenant:
x | (y << 1) | (z << 2)
Le fonctionnement de cette technique est le suivant. Chacune des lignes x = ... situées au-dessus de "fractionnent". groupes de bits en deux de manière à laisser suffisamment d'espace entre eux pour les bits des autres entiers. Par exemple, si nous considérons trois entiers de 4 bits, nous divisons l'un avec les bits 1234 en 000012000034 où les zéros sont réservés pour les autres entiers. Dans l'étape suivante, nous séparons 12 et 34 de la même manière pour obtenir 001002003004. Même si 10 bits ne permettent pas une belle division répétée en deux groupes, vous pouvez simplement le considérer en 16 bits lorsque vous perdez les plus élevés à la fin. .
Comme vous pouvez le voir sur la première ligne, vous n’avez en fait besoin que pour chaque entier saisi x , cela signifie que x & amp; 0x03000000 == 0 .
Autres conseils
Voici ma solution avec un script python:
J'ai repris l'allusion dans son commentaire: Fabian “ryg” Giesen
Lisez le long commentaire ci-dessous! Nous devons garder une trace des bits qui doivent aller jusqu'où!
Ensuite, à chaque étape, nous sélectionnons ces bits, les déplaçons et leur appliquons un masque de bits (voir commentaire dernières lignes) pour les masquer!
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
Donc, pour un nombre 10 bits et 2 bits d'entrelacement (pour 32 bits), vous devez procéder comme suit!:
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
Et pour un numéro 21 bits et 2 bits d'entrelacement (pour 64 bits), vous devez procéder comme suit!:
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
Et pour un numéro 42 bits et 2 bits d'entrelacement (pour 128 bits), vous devez procéder comme suit (au cas où vous en auriez besoin ;-)):
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
Un script Python pour produire et vérifier les modèles d'entrelacement !!!
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!!!!")
Je vais aussi ajouter le code de décodage dans un moment!
Le plus simple est probablement une table de recherche, si vous avez 4K d'espace 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 );
}
Le bit hack utilise des décalages et des masques pour répartir les bits. Ainsi, chaque fois qu'il décale et modifie la valeur, il copie certains des bits dans des espaces vides, puis masque les combinaisons de manière à ne conserver que les bits d'origine.
par exemple:
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
À chaque itération, chaque bloc est divisé en deux, le bit le plus à droite de la moitié la plus à gauche du bloc étant déplacé vers sa position finale, et un masque est appliqué afin que seuls les bits requis restent.
Une fois les entrées espacées, décalez-les pour que les valeurs de l'une tombent dans les zéros de l'autre.
Pour étendre cette technique de plus de deux bits entre les valeurs du résultat final, vous devez augmenter les décalages entre les positions des bits. Cela devient un peu plus délicat, car la taille du bloc de départ n’est pas une puissance de 2, vous pouvez donc le diviser au milieu ou sur une limite de puissance 2.
Une évolution comme celle-ci pourrait donc fonctionner:
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
Effectuez la même transformation sur les entrées, déplacez-les une par une et deux par deux, ou ensemble, et vous avez terminé.
Bon timing, je viens de faire cela le mois dernier!
La clé était de créer deux fonctions. On étale des bits sur un tiers. Ensuite, nous pouvons en combiner trois (avec un décalage pour les deux derniers) pour obtenir la valeur finale entrelacée de Morton.
Ce code s'entrelace en commençant par les bits HAUT (ce qui est plus logique pour les valeurs en points fixes). Si votre application ne comporte que 10 bits par composant, il suffit de décaler chaque valeur de 22 pour la faire démarrer aux bits hauts.
/* 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);
}
Le code suivant trouve le numéro de Morton des trois nombres d’entrée de 10 bits. Il utilise l’idée de votre lien et effectue la propagation des bits aux étapes 5-5, 3-2-3-2, 2-1-1-1-2-1-1-1 et 1-1-1. 1-1-1-1-1-1-1 car 10 n'est pas une puissance de deux.
......................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
Ci-dessus, vous pouvez voir l'emplacement de chaque bit avant le premier et après chacune des quatre étapes.
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;
}
J'ai pris ce qui précède et je l'ai modifié pour combiner 3 nombres de 16 bits en un nombre de 48 (vraiment 64) bits. Peut-être que cela épargnera à quelqu'un le peu de réflexion pour y arriver.
#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) );
}
Voici l'extrait de code qui génère la clé Morton de taille 64 bits pour le point 3D.
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);
}
J'ai eu un problème similaire aujourd'hui, mais au lieu de 3 nombres, je dois combiner un nombre arbitraire de nombres de longueur quelconque. J'ai utilisé mon propre algorithme d'étalement et de masquage de bits et je l'ai appliqué à C # BigIntegers. Voici le code que j'ai écrit. En tant qu'étape de compilation, il calcule les nombres magiques et le masque pour le nombre donné de dimensions et la profondeur de bits. Vous pouvez ensuite réutiliser l'objet pour plusieurs conversions.
/// <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) + ")";
}
}
Voici un générateur que j'ai créé en Ruby pour la production de méthodes de codage de longueur arbitraire:
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 sortie est générique et peut être adaptée en fonction des besoins. Exemple de sortie:
// 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
