State quantization

Deep dive

How it works

In: a float and its (min, max, bits) · Out: an integer of bits bits, decoded back within step/2 · State: none (the ranges are shared constants) · Cost: O(1) per value, a multiply, add, round and clamp.

1. Bounded scalars: q = round((v − min) / (max − min) × (2^b − 1)), clamp to range; decode v = min + q × (max − min) / (2^b − 1).
2. Angles: yaw in [0, 2π) with wraparound, e.g. 16 bits = 0.0055°. Pitch in [−90°, 90°].
3. Quaternions (smallest three): find the component with the largest magnitude; if it's negative, negate the quaternion (q and −q are the same rotation); send its index (2 bits) and the other three quantized over [−1/√2, 1/√2]; the receiver reconstructs the fourth as √(1 − a² − b² − c²).
4. Velocities: clamp to the maximum physical speed; small values near zero can use fewer bits with a "nearly zero" flag.
5. Booleans and enums: 1 bit / ceil(log2(variants)) bits; pack into a bit stream.
6. Server-side: after each tick, round the authoritative state through quantize/dequantize so what was sent is exactly what is simulated.

float position  32+32+32 = 96 bits     ->  x,z in ±2048 m @ 1/256 m: 20+20, y in [-64, 192] @ 1/256 m: 16  = 56 bits
float quaternion 4 x 32 = 128 bits     ->  smallest three: 2 + 3 x 9 = 29 bits

Code

#[derive(Clone, Copy)]
pub struct Range { pub min: f32, pub max: f32, pub bits: u32 }

impl Range {
    /// Choose bits for a resolution: e.g. Range::with_step(-2048.0, 2048.0, 1.0 / 256.0).
    pub fn with_step(min: f32, max: f32, step: f32) -> Self {
        let intervals = ((max - min) / step).ceil() as u64; // 2^bits - 1 intervals ≈ this
        Range { min, max, bits: 64 - (intervals - 1).leading_zeros() }
    }
    fn levels(&self) -> f32 { ((1u64 << self.bits) - 1) as f32 }
    pub fn quantize(&self, v: f32) -> u32 {
        let t = ((v - self.min) / (self.max - self.min)).clamp(0.0, 1.0);
        (t * self.levels() + 0.5) as u32 // round to nearest
    }
    pub fn dequantize(&self, q: u32) -> f32 { self.min + q as f32 * (self.max - self.min) / self.levels() }
    pub fn max_error(&self) -> f32 { (self.max - self.min) / self.levels() / 2.0 }
}

const SQRT1_2: f32 = std::f32::consts::FRAC_1_SQRT_2;

/// Smallest-three quaternion encoding: 2 + 3 * bits (bits <= 10 to fit a u32).
pub fn quat_encode(q: [f32; 4], bits: u32) -> u32 {
    let mut largest = 0;
    for i in 1..4 { if q[i].abs() > q[largest].abs() { largest = i; } }
    let sign = if q[largest] < 0.0 { -1.0 } else { 1.0 }; // q == -q: make the dropped one positive
    let r = Range { min: -SQRT1_2, max: SQRT1_2, bits };
    let mut out = largest as u32;
    for i in (0..4).filter(|&i| i != largest) {
        out = (out << bits) | r.quantize(q[i] * sign);
    }
    out
}

pub fn quat_decode(v: u32, bits: u32) -> [f32; 4] {
    let r = Range { min: -SQRT1_2, max: SQRT1_2, bits };
    let mask = (1u32 << bits) - 1;
    let largest = (v >> (3 * bits)) as usize;
    let mut q = [0.0f32; 4];
    let mut shift = 3 * bits;
    let mut sum = 0.0;
    for i in (0..4).filter(|&i| i != largest) {
        shift -= bits;
        q[i] = r.dequantize((v >> shift) & mask);
        sum += q[i] * q[i];
    }
    q[largest] = (1.0 - sum).max(0.0).sqrt();
    let n = q.iter().map(|x| x * x).sum::<f32>().sqrt(); // renormalize after rounding
    q.map(|x| x / n)
}

/// Angle between two unit quaternions in degrees.
pub fn quat_angle_deg(a: [f32; 4], b: [f32; 4]) -> f32 {
    let d = (0..4).map(|i| a[i] * b[i]).sum::<f32>().abs().min(1.0);
    2.0 * d.acos().to_degrees()
}

#[test]
fn errors_are_bounded() {
    let pos = Range::with_step(-2048.0, 2048.0, 1.0 / 256.0);
    assert_eq!(pos.bits, 20);
    for v in [-2048.0, -0.3, 0.0, 17.123, 2047.99] {
        assert!((pos.dequantize(pos.quantize(v)) - v).abs() <= pos.max_error() + 1e-4);
    }
    let mut worst: f32 = 0.0;
    let mut s = 1u32;
    for _ in 0..100_000 {
        let mut q = [0.0f32; 4];
        for x in q.iter_mut() { s ^= s << 13; s ^= s >> 17; s ^= s << 5; *x = s as f32 / u32::MAX as f32 * 2.0 - 1.0; }
        let n = q.iter().map(|x| x * x).sum::<f32>().sqrt();
        let q = q.map(|x| x / n);
        worst = worst.max(quat_angle_deg(q, quat_decode(quat_encode(q, 9), 9)));
    }
    assert!(worst < 0.6, "worst {worst} deg"); // 29 bits per rotation; measured ≈ 0.49°
}

Complexity and constants

• O(1) per value: a multiply, add, round and clamp.
• Sizing examples: 4 km at 1/256 m (3.9 mm) → 20 bits; 256 m vertical at 1/256 m → 16 bits; yaw 16 bits → 0.0055°; health 0-255 → 8 bits.
• Smallest three, measured over 100k random rotations: 9 bits per component (29 total) ≈ 0.49° worst case, 10 bits (32 total) ≈ 0.23°. A 2 m object at 0.25° error moves its tip about 9 mm.
• Typical savings: a 7-float transform (28 bytes) becomes about 11 bytes before delta coding; with delta compression a moving entity often costs 3-6 bytes per update.

Efficiency

Cost: a multiply, add, round and clamp per value; memory is the packed bits. A 7-float transform (28 bytes) becomes about 11 bytes before delta coding, and a moving entity often costs 3-6 bytes per update after delta compression. Smallest three at 9 bits per component gives 0.49° worst case over 100k random rotations; 10 bits gives 0.23°. Bound: bandwidth or storage, not CPU.

Levers:

• Size bits from range ÷ step — 1 km at 1 mm is 20 bits instead of 32 — every bounded value.
• Smallest three for rotations — 128 bits to 29-32 — orientation of every entity.
• Grid-cell origin plus local offset — keeps bits low in large worlds — worlds beyond a few km.
• Diff the integers, not the floats — sub-resolution jitter costs no bandwidth — change detection.
• Half floats (f16) where no range setup is wanted — 16 bits, 11 bits of precision — values near the origin.

Naive → standard → state of the art:

• Raw f32 per component · 96 bits per position, 128 per rotation
• Bounded fixed-point plus smallest three · 56 bits position, 29 bits rotation in the example
• Quantize, then delta against an acked baseline (snapshot-delta-compression) · 3-6 bytes per moving entity per update

Implementation notes

• Pick resolution from what the eye and the game can tell apart: position errors below about 1 mm-1 cm and angle errors below about 0.1° are invisible at normal camera distances.
• Large worlds: quantize relative to a grid cell or floating origin (cell id + local offset) instead of one huge range.
• Quantize in the simulation (server end of tick) for anything the client predicts; otherwise the client's replay starts from slightly different values and corrections never fully disappear.
• Use quantized integers as keys for delta coding and change detection: "changed" means the quantized value changed, so sub-resolution jitter doesn't cost bandwidth.
• Rounding: round to nearest (+ 0.5 then truncate for non-negative values); truncation biases values downward and drifts objects over time.

Pitfalls

• Values outside the declared range wrap or saturate silently; clamp and log, and size ranges from real data.
• Quantizing velocity but not position (or vice versa) for extrapolation: mismatched precision causes visible wobble.
• Forgetting the sign flip in smallest three: the omitted component may be negative and the decoder reconstructs the wrong rotation.
• Quaternion components very close to 1/√2 for two axes: either can be "largest"; encoder and decoder must use the same tie-break, which the index field handles.
• Floats compared after dequantize on different platforms: dequantization is deterministic only if it uses the same operations; for lockstep, keep integers.

Variants and alternatives

In production

• Games: Gaffer On Games cube demos (smallest three, bounded positions), Unreal Engine (FVector_NetQuantize, NetQuantize10/100, compressed rotators), Source (SendProp bit counts and SPROP_COORD), Quake 3 (netField_t bit widths), Unity Netcode for Entities (quantization per ghost field).
• 3D graphics: KHR_mesh_quantization allows 8/16-bit integer attributes; the spec's example drops a typical PBR vertex from 48 to 20 bytes.
• Mapping: Mapbox Vector Tile geometry uses integer tile-local coordinates, with extent 4096 meaning 1/4096 of the tile.
• Robotics and UAVs: MAVLink GLOBAL_POSITION_INT carries lat/lon as int32 degE7, altitude as int32 mm and ground speed as int16 cm/s.

Implementations

Sources

• Fiedler, Snapshot Compression, gafferongames.com, 2015. post
• Epic Games, Unreal Engine documentation: FVector_NetQuantize and property replication.
• Valve Developer Community, Networking Entities (SendProp flags and bit counts). page
• Cigolle et al., A Survey of Efficient Representations for Independent Unit Vectors, JCGT, 2014. paper
• Khronos Group, KHR_mesh_quantization, glTF 2.0 extension. spec
• Mapbox, Vector Tile Specification 2.1. spec
• MAVLink, Common messages: GLOBAL_POSITION_INT. spec