From da06ac178d2c083249f8cb2b2c0bef799c079cfd Mon Sep 17 00:00:00 2001
From: Daniel Karbach <daniel.karbach@localhorst.tv>
Date: Thu, 5 Nov 2015 11:27:28 +0100
Subject: [PATCH] higher precision for quats over the net

---
 doc/protocol           |  3 +-
 src/net/net.cpp        | 67 ++++++++++++++++++++++++++++++++++++------
 tst/net/PacketTest.cpp |  4 +--
 3 files changed, 62 insertions(+), 12 deletions(-)

diff --git a/doc/protocol b/doc/protocol
index 025a13d..8e26949 100644
--- a/doc/protocol
+++ b/doc/protocol
@@ -30,7 +30,8 @@ packu          2    16bit unsigned  int representing a float value normalized to
                     	it can be unpacked by dividing by 65535
 vec3n          6    3x packn
 vec3u          6    3x packu
-quat           8    4x packn float
+quat           8    2bit index of largest component, a 2bit padding, then 3x 20bit small components in xyzw
+                    	order mapped from [-0.7072,0.7072] to [0,1048574] (with largest omitted)
 entity state  42    [ 0] vec3i chunk pos (there's a variation where this is a vec3b)
                     [12] vec3u block pos by 16,
                     [18] vec3 velocity,
diff --git a/src/net/net.cpp b/src/net/net.cpp
index 5d06234..2e202e0 100644
--- a/src/net/net.cpp
+++ b/src/net/net.cpp
@@ -431,18 +431,67 @@ void Packet::Payload::ReadString(string &dst, size_t off, size_t maxlen) const n
 }
 
 void Packet::Payload::Write(const glm::quat &val, size_t off) noexcept {
-	WritePackN(val.w, off);
-	WritePackN(val.x, off + 2);
-	WritePackN(val.y, off + 4);
-	WritePackN(val.z, off + 6);
+	// find the largest component
+	float largest = 0.0f;
+	int largest_index = -1;
+	for (int i = 0; i < 4; ++i) {
+		float iabs = abs(val[i]);
+		if (iabs > largest) {
+			largest = iabs;
+			largest_index = i;
+		}
+	}
+	// make sure it's positive
+	const glm::quat q(val[largest_index] < 0.0f ? -val : val);
+	// move index to the two most significant bits
+	uint64_t packed = uint64_t(largest_index) << 62;
+	// we have to map from [-0.7072,0.7072] to [-524287,524287] and move into positive range
+	constexpr float conv = 524287.0f / 0.7072f;
+	// if largest is 1, the other three are 0
+	// precision of comparison is the interval of our mapping
+	if (abs(1.0 - largest) < (1.0f / conv)) {
+		packed |= 0x7FFFF7FFFF7FFFF;
+	} else {
+		// pack the three smaller components into 20bit ints each
+		int shift = 40;
+		for (int i = 0; i < 4; ++i) {
+			if (i != largest_index) {
+				packed |= uint64_t(int(q[i] * conv) + 524287) << shift;
+				shift -= 20;
+			}
+		}
+	}
+	// and write it out
+	Write(packed, off);
 }
 
 void Packet::Payload::Read(glm::quat &val, size_t off) const noexcept {
-	ReadPackN(val.w, off);
-	ReadPackN(val.x, off + 2);
-	ReadPackN(val.y, off + 4);
-	ReadPackN(val.z, off + 6);
-	val = normalize(val);
+	// extract the 8 byte packed value
+	uint64_t packed = 0;
+	Read(packed, off);
+	// two most significant bits are the index of the largest (omitted) component
+	int largest_index = packed >> 62;
+	// if all other three are 0, largest is 1 and we can omit the conversion
+	if ((packed & 0xFFFFFFFFFFFFFFF) == 0x7FFFF7FFFF7FFFF) {
+		val = { 0.0f, 0.0f, 0.0f, 0.0f };
+		val[largest_index] = 1.0f;
+		return;
+	}
+	// we have to map from [-524287,524287] to [-0.7072,0.7072]
+	constexpr float conv = 0.7072f / 524287.0f;
+	int shift = 40;
+	for (int i = 0; i < 4; ++i) {
+		if (i != largest_index) {
+			val[i] = float(int((packed >> shift) & 0xFFFFF) - 524287) * conv;
+			shift -= 20;
+		} else {
+			// set to zero so the length of the other three can be determined
+			val[i] = 0.0f;
+		}
+	}
+	// omitted component squared is 1 - length squared of others
+	val[largest_index] = sqrt(1.0f - dot(val, val));
+	// and already normalized
 }
 
 void Packet::Payload::Write(const EntityState &state, size_t off) noexcept {
diff --git a/tst/net/PacketTest.cpp b/tst/net/PacketTest.cpp
index 86517ca..880d6a5 100644
--- a/tst/net/PacketTest.cpp
+++ b/tst/net/PacketTest.cpp
@@ -116,7 +116,7 @@ void PacketTest::testJoin() {
 	EntityState write_state;
 	write_state.pos = { { 7, 2, -3 }, { 1.5f, 0.9f, 12.0f } };
 	write_state.velocity = { 0.025f, 0.001f, 0.0f };
-	write_state.orient = { 1.0f, 0.0f, 0.0f, 0.0f };
+	write_state.orient = normalize(glm::quat(0.863f, 0.0f, 0.505f, 0.0f));
 	write_state.pitch = 0.3f;
 	write_state.yaw = -2.3f;
 	write_entity.SetState(write_state);
@@ -165,7 +165,7 @@ void PacketTest::testPlayerUpdate() {
 	EntityState write_state;
 	write_state.pos = { { 7, 2, -3 }, { 1.5f, 0.9f, 12.0f } };
 	write_state.velocity = { 0.025f, 0.001f, 0.0f };
-	write_state.orient = { 1.0f, 0.0f, 0.0f, 0.0f };
+	write_state.orient = { 0.0f, 0.0f, 1.0f, 0.0f };
 	glm::vec3 write_movement(0.5f, -1.0f, 1.0f);
 	uint8_t write_actions = 0x05;
 	uint8_t write_slot = 3;
-- 
2.39.2