When I was building this website I wanted to display a 3d scene on the welcome page. One of the problems is to minimize the amount of bytes needed to be transferred. You could just only gzip the data to reduce data transfer, but I wanted to go the extra mile. Of course -but far too often overlooked- the gains should be greater than the cost. The additional code should be less than the transferred bytes saved. And the complexity gain should be minimized (I do not have a method yet of determining code complexity in hard numbers, but it is more of an experienced feeling). The file that is being transferred is a json file. It contains images and meshes (3d models) in base64 encoding. I am focussing on the compression of the meshes.
A mesh consists of vertices and indices. A vertex contains data; in my case it contains a position, normal, tangent, color and uv-coordinate. An index is a number referencing a vertex. Three consecutively indices form a triangle, which makes it possible to render on to the screen.
The first thing I did is to look at what is compressable. Like the internet, the color is represented as a 32-bit hex value. The color represented as 4 32-bit floats could be compressed to 1 32-bit unsigned integer. A normal is a normalized vector with 3 axis. You only need to know two axis to know the length of the 3rd one using Pythagoras. Only one bit is needed to mark if it is signed or unsigned. I converted the x-axis to a 15-bit fixed point number. The z-axis to a 16-bit fixed point number. And the y-axis got one bit to mark if it is signed. [xxxxxxxxxxxxxxxyzzzzzzzzzzzzzzzz] The tangent is the same as the normal, except it has one additional element. This 4th element is either -1 or 1, and thus can be stored using 1 bit. instead of using 16 bits to notate the z axis, 15 bits are used to make room for the additional bit needed to determine the 4th element in the vector. To reduce the uv-coordinate, I reduced the two 32-bit floating point values to two 16-bit fixed point values, as my values are between 0 and 1. Although, this is a bit more risky than the other encodings. I knew the values would be between these limits.
/// <summary> /// position: 32bit x, y, z /// normal: 15 bit for x, 1 bit for y, 16 bit for z /// tangent: 15 bit for x, 1 bit for y, 15 bit for z, 1 bit for w /// uv: 16 bit for x, 16 bit for y /// color: 8 bit for r, g, b, a /// /// original size: 64 (if color is float32) /// compressed size: 28 /// </summary> public struct Vertex { public const int Size = 28; public const bool SwapEndian = false; public float px; public float py; public float pz; public uint normal; public uint tangent; public uint uv; public uint color; public void Encode(byte[] dst, int offset) { EncodeFloat(dst, offset + 0, px); EncodeFloat(dst, offset + 4, py); EncodeFloat(dst, offset + 8, pz); EncodeUint (dst, offset + 12, normal); EncodeUint (dst, offset + 16, tangent); EncodeUint (dst, offset + 20, uv); EncodeUint (dst, offset + 24, color); } public void EncodePosition(Vector3 position) { px = position.x; py = position.y; pz = position.z; } public Vector3 DecodePosition() => new Vector3(px, py, pz); public void EncodeNormal(Vector3 normal) { var normal_x = (double)normal.x; var normal_x_negative = normal_x < 0; if (normal_x_negative) normal_x = -normal_x; normal_x *= 0b00111111_11111111; var n_xy = ((uint)normal_x & 0b00111111_11111111) << 1; if (normal_x_negative) n_xy |= 0b10000000_00000000; if (normal.y < 0) n_xy |= 1; var normal_z = (double)normal.z; var normal_z_negative = normal_z < 0; if (normal_z_negative) normal_z = -normal_z; normal_z *= 0b01111111_11111111; var n_z = (uint)normal_z; if (normal_z_negative) n_z |= 0b10000000_00000000; this.normal = n_xy << 16 | n_z; } // 0b00111111_11111111 = 16383 // 0b01111111_11111111 = 32767 // 0b10000000_00000000 = 32768 public Vector3 DecodeNormal() { var nxy = normal >> 16; var double_nx = (double)(nxy >> 1 & 0b00111111_11111111) / 0b00111111_11111111; if ((nxy & 0b10000000_00000000) != 0) double_nx = -double_nx; var nz = normal & 0b01111111_11111111; var double_nz = (double)nz / 0b01111111_11111111; if ((nz & 0b10000000_00000000) == 0) double_nz = -double_nz; var double_ny = Math.Sqrt(1 - (double_nx * double_nx + double_nz * double_nz)); if ((nxy & 1) != 0) double_ny = -double_ny; return new Vector3((float)double_nx, (float)double_ny, (float)double_nz); } public void EncodeTangent(Vector4 tangent) { var tangent_x = (double)tangent.x; var tangent_x_negative = tangent_x < 0; if (tangent_x_negative) tangent_x = -tangent_x; tangent_x *= 0b00111111_11111111; var t_xy = ((uint)tangent_x & 0b00111111_11111111) << 1; if (tangent_x_negative) t_xy |= 0b10000000_00000000; if (tangent.y < 0) t_xy |= 1; var tangent_z = (double)tangent.z; var tangent_z_negative = tangent_z < 0; if (tangent_z_negative) tangent_z = -tangent_z; tangent_z *= 0b00111111_11111111; var t_zw = ((uint)tangent_z & 0b00111111_11111111) << 1; if (tangent_z_negative) t_zw |= 0b10000000_00000000; if (tangent.w < 0) t_zw |= 1; this.tangent = t_xy << 16 | t_zw; } public Vector4 DecodeTangent() { var txy = tangent >> 16; var double_tx = (double)(txy >> 1 & 0b00111111_11111111) / 0b00111111_11111111; if ((txy & 0b10000000_00000000) != 0) double_tx = -double_tx; var tzw = tangent; var double_tz = (double) (tzw >> 1 & 0b00111111_11111111) / 0b00111111_11111111; if ((tzw & 0b10000000_00000000) != 0) double_tz = -double_tz; var double_ty = Math.Sqrt(1 - (double_tx * double_tx + double_tz * double_tz)); if ((txy & 1) != 0) double_ty = -double_ty; var double_tw = (tzw & 1) == 0 ? 1 : -1; return new Vector4((float)double_tx, (float)double_ty, (float)double_tz, (float)double_tw); } public void EncodeUV(Vector2 uv) { var double_u = (double)uv.x; var is_u_negative = double_u < 0; if (is_u_negative) double_u = -double_u; double_u *= 0b01111111_11111111; var u = (uint)double_u; if (is_u_negative) u |= 0b10000000_00000000; var double_v = (double)uv.y; var is_v_negative = double_v < 0; if (is_v_negative) double_v = -double_v; double_v *= 0b01111111_11111111; var v = (uint)double_v; if (is_v_negative) v |= 0b10000000_00000000; this.uv = u << 16 | v; } public Vector2 DecodeUV() { var u = uv >> 16; var double_u = (double) (u & 0b01111111_11111111u) / 0b01111111_11111111; if ((u & 0b10000000_00000000) != 0) double_u = -double_u; var v = uv & 0b11111111_11111111; var double_v = (double)(v & 0b01111111_11111111) / 0b01111111_11111111; if ((v & 0b10000000_00000000) != 0) double_v = -double_v; return new Vector2((float)double_u, (float)double_v); } public void EncodeColor(Color32 color) { this.color = (uint)color.r << 24 | (uint)color.g << 16 | (uint)color.b << 8 | (uint)color.a; } public Color32 DecodeColor() { var r = (color >> 24) & 255; var g = (color >> 16) & 255; var b = (color >> 8) & 255; var a = color & 255; return new Color32((byte)r, (byte)g, (byte)b, (byte)a); } public static void EncodeFloat(byte[] dst, int offset, float value) { var bytes = BitConverter.GetBytes(value); if (SwapEndian) { dst[offset + 0] = bytes[3]; dst[offset + 1] = bytes[2]; dst[offset + 2] = bytes[1]; dst[offset + 3] = bytes[0]; } else { dst[offset + 0] = bytes[0]; dst[offset + 1] = bytes[1]; dst[offset + 2] = bytes[2]; dst[offset + 3] = bytes[3]; } } public static void EncodeUint(byte[] dst, int offset, uint value) { var bytes = BitConverter.GetBytes(value); if (SwapEndian) { dst[offset + 0] = bytes[3]; dst[offset + 1] = bytes[2]; dst[offset + 2] = bytes[1]; dst[offset + 3] = bytes[0]; } else { dst[offset + 0] = bytes[0]; dst[offset + 1] = bytes[1]; dst[offset + 2] = bytes[2]; dst[offset + 3] = bytes[3]; } } }
Thanks for reading my first ever blog