wie 27 vector3 in einen 0-256 Wert zu kodieren?

Question

I habe 27 Kombinationen von 3 Werten von -1 bis 1 vom Typ:

Vector3(0,0,0); 
Vector3(-1,0,0); 
Vector3(0,-1,0); 
Vector3(0,0,-1); 
Vector3(-1,-1,0); 
... up to 
Vector3(0,1,1); 
Vector3(1,1,1); 

Ich brauche sie zu und von einer 8-Bit-sbyte/Byte-Array zu konvertieren.

Eine Lösung ist die erste Ziffer zu sagen, von der 256 = X die zweite Ziffer ist Y und die dritte ist Z ...

so

Vector3(-1,1,1) becomes 022, 
    Vector3(1,-1,-1) becomes 200, 
    Vector3(1,0,1) becomes 212... 

Ich würde es vorziehen, es zu codieren in einer kompakteren Weise, vielleicht mit Bytes (worüber ich keine Ahnung habe), weil die obige Lösung viele Multiplikationen und runde Funktionen zum Decodieren verwendet, haben Sie bitte einige Vorschläge? Die andere Möglichkeit ist 27 zu schreiben, wenn die Bedingungen zum Schreiben der Vector3-Kombination in ein Array ineffizient erscheinen.

Dank Böse Tak für die Führung, änderte ich den Code ein bisschen 0-1 Werte auf das erste Bit hinzuzufügen, und es für unity3d anzupassen:

function Pack4(x:int,y:int,z:int,w:int):sbyte { 
var b: sbyte = 0; 

b |= (x + 1) << 6; 
b |= (y + 1) << 4; 
b |= (z + 1) << 2; 
b |= (w + 1); 
return b; 
} 

function unPack4(b:sbyte):Vector4 { 
var v : Vector4; 
v.x = ((b & 0xC0) >> 6) - 1;  //0xC0 == 1100 0000 
v.y = ((b & 0x30) >> 4) - 1; // 0x30 == 0011 0000 
v.z = ((b & 0xC) >> 2) - 1;  // 0xC == 0000 1100 
v.w = (b & 0x3) - 1;   // 0x3 == 0000 0011 
return v; 
} 

Answer 1

Eine Möglichkeit ist, um die Komponente zu speichern, jedes Vektors in je 2 Bits eines Bytes.

Das Konvertieren eines Vektorkomponentenwerts in und aus der gespeicherten 2-Bit-Form ist so einfach wie das Addieren und Subtrahieren von eins.

-1 (1111 1111 as a signed byte) <-> 00 (in binary) 
0 (0000 0000 in binary)  <-> 01 (in binary) 
1 (0000 0001 in binary)  <-> 10 (in binary) 

Die gepackten 2-Bit-Werte können in einem Byte in beliebiger Reihenfolge Ihrer Präferenz gespeichert werden. Ich werde das folgende Format verwenden: 00XXYYZZ Dabei ist XX der konvertierte (gepackte) Wert der X-Komponente und so weiter. Die 0 am Start werden nicht verwendet.

ein Vektor dann in einem Byte gepackt werden, wie folgt: Form wie folgt wird

byte Pack(Vector3<int> vector) { 
    byte b = 0; 
    b |= (vector.x + 1) << 4; 
    b |= (vector.y + 1) << 2; 
    b |= (vector.z + 1); 
    return b; 
} 

Auspacken einen Vektors von seinem Byte:

Vector3<int> Unpack(byte b) { 
    Vector3<int> v = new Vector<int>(); 
    v.x = ((b & 0x30) >> 4) - 1; // 0x30 == 0011 0000 
    v.y = ((b & 0xC) >> 2) - 1;  // 0xC == 0000 1100 
    v.z = (b & 0x3) - 1;  // 0x3 == 0000 0011 
    return v; 
} 

Sowohl die obigen Verfahren setzen voraus, dass der Eingang ist gültig, dh Alle Komponenten von vector in Pack sind entweder -1, 0 oder 1 und alle 2-Bit-Abschnitte von b in Unpack haben eine (binärer Wert von entweder 00, 01 oder 10.

Da diese Methode bitweise Operatoren verwendet, ist sie schnell und effizient. Wenn Sie die Daten weiter komprimieren möchten, können Sie auch versuchen, die 2 unbenutzten Bits zu verwenden und alle 3 zu einem Vektor verarbeiteten 2-Bit-Elemente zu konvertieren.

Answer 2

Die kompakteste Weg ist durch eine 27 Ziffern Zahl zur Basis Schreiben 3 (unter Verwendung eines Schiebe -1 -> 0, 0 -> 1, 1 -> 2).

Der Wert dieser Zahl wird aus 0 bis 3^27-1 = 7625597484987, Bereich, die 43 Bits codiert zu werden braucht, d.h. 6 Bytes (und 5 Ersatz Bits).

Dies ist ein wenig Ersparnis im Vergleich zu einer gepackten Darstellung mit 4 Zwei-Bit-Zahlen in einem Byte gepackt (daher 7 Bytes/56 Bits insgesamt).

Eine interessante Variante besteht darin, die Basis 3 Ziffern fünf mal fünf in Bytes zu gruppieren (daher Zahlen 0 bis 242). Sie benötigen immer noch 6 Bytes (und keine Ersatzbits), aber die Decodierung der Bytes kann leicht als eine Tabelle von 243 Einträgen hart-codiert werden.

Answer 3

1. Ich nehme an, Ihre Werte sind float integer nicht

   so Operationen Bit werden auf ganzzahlige Typ nicht Geschwindigkeit zu viel im Vergleich zur Umkehr verbessern. Also wird meine Wette mit voller Reichweite besser sein. Ich würde dies für 3D-Fall:

   8 bit -> 256 values 
   3D -> pow(256,1/3) = ~ 6.349 values per dimension 
   6^3 = 216 < 256 
   

   So von (x,y,z) Verpackung wie folgt aussieht:

   BYTE p; 
   p =floor((x+1.0)*3.0); 
   p+=floor((y+1.0)*3.0*6.0); 
   p+=floor((y+1.0)*3.0*6.0*6.0); 
   

   Die Idee <-1,+1> ist konvertieren <0,1> daher die +1.0 und *3.0 statt *6.0 zu reichen und dann multiplizieren Sie einfach an der richtigen Stelle im endgültigen BYTE.

   und p Auspacken sieht wie folgt aus:

   x=p%6; x=(x/3.0)-1.0; p/=6; 
   y=p%6; y=(y/3.0)-1.0; p/=6; 
   z=p%6; z=(z/3.0)-1.0; 
   

   Auf diese Weise können 216 von 256 Werte verwendet werden, die dann nur 2 Bits viel besser ist (4 Werte). Ihr 4D Fall würde ähnlich aussehen, verwenden Sie einfach 3.0,6.0 andere Konstante floor(pow(256,1/4))=4 so verwenden Sie 2.0,4.0 aber Vorsicht Fall, wenn p=256 oder verwenden Sie 2 Bits pro Dimension und Bit-Ansatz wie die angenommene Antwort tut.

   Wenn Sie echte Geschwindigkeit benötigen, können Sie diese optimieren, um Schwimmer Darstellung Halte Ergebnis BYTE Paket zu erzwingen bestimmten Exponenten und extrahieren Mantissenbits als gepackte BYTE direkt. Als Ergebnis wird <0,216> Sie können eine größere Zahl hinzufügen. siehe IEEE 754-1985 für Details, aber Sie wollen die Mantisse mit Ihrem BYTE so ausrichten, wenn Sie Nummer wie 2^23 hinzufügen, dann sollte die niedrigste 8 Bit float Ihr gepackter Wert direkt sein (wie MSB 1 ist nicht in Mantisse vorhanden) so keine teure Konvertierung wird gebraucht.

2. Im Fall bekam man nur {-1,0,+1} statt <-1,+1>

   dann von groben ganzzahligen Ansatz wie Bit mit 2 Bits pro Dimension Verpackung oder verwenden LUT Tabelle aller 3^3 = 27 Möglichkeiten und ganze Vektor-Pack verwenden sollten in 5 Bits.

   Die Codierung würde wie folgt aussehen:

   int enc[3][3][3] = { 0,1,2, ... 24,25,26 }; 
   p=enc[x+1][y+1][z+1]; 
   

   und Decodierung:

   int dec[27][3] = { {-1,-1,-1},.....,{+1,+1,+1} }; 
   x=dec[p][0]; 
   y=dec[p][1]; 
   z=dec[p][2]; 
   

   die schnell genug sein sollte, und wenn man viele Vektoren bekam können Sie die p in jeder Packung 5 Bits ... um noch mehr Speicherplatz zu sparen