Triangle bounding boxes in a single byte

Just thought of a way to store the bounding box for a single triangle in only one byte. It's not really practical or something you'd ever really want to use, but what the hell.

Assume we have some kind of indexed mesh structure with a list of vertex positions and a list of triangle indices:

  struct Mesh {
    std::vector<vec3> verts;
    std::vector<uvec3> triangles;
  };

We can find the bounding box of a triangle by taking the min and max of all three vertices:

  vec3 Mesh::lowerBound(uint32_t tri) const {
    vec3 v0 = verts[triangles[tri].x];
    vec3 v1 = verts[triangles[tri].y];
    vec3 v2 = verts[triangles[tri].z];
    return min(min(v0, v1), v2);
  }

  vec3 Mesh::upperBound(uint32_t tri) const {
    vec3 v0 = verts[triangles[tri].x];
    vec3 v1 = verts[triangles[tri].y];
    vec3 v2 = verts[triangles[tri].z];
    return max(max(v0, v1), v2);
  }

This is nice and simple and probably way better than what I'm about to suggest.

We can store a byte that tells us which of the three vertices defines the lower and upper bounds along each axis. In other words, for each of the x, y and z axes it tells us to get the lower bound value from vertex i and the upper bound value from vertex j. This avoids the need for the min() and max() calls, but replaces it with some division and modulus operations, so it's probably not a performance optimisation.

For component k of each vertex there are 4 possibilities:

1. v[k] is the lower bound value for axis k.
2. v[k] is the upper bound value for axis k.
3. v[k] is neither the upper or lower bound value for axis k.
4. v[k] is both the upper and lower bound value for axis k.

If v[k] is both the upper and lower bound, it means that the triangle is exactly perpendicular to axis k. In this case all three vertices will have the same value for axis k, which means we can choose any of them for the upper bound and any of them for the lower bound. As long as we make sure we choose a different vertex for each, we can avoid having to represent condition #4.

So that means along any given axis k, we have 6 possible permutations of conditions 1-3 above:

• LHN
• LNH
• HLN
• HNL
• NLH
• NHL

Where the first letter is the condition that holds for vertex v0, the second is the condition for v1 and the third is the condition for v3. The letter 'L' means this vertex is where the lower bound comes from, 'H' means it's the upper bound and 'N' means it's neither.

6 possibilities for each axis and 3 axes means we have 6x6x6 = 216 total possibilities. That's less than 256 so we can fit it all into a byte.

We can encode the per-axis possibilities into a pair of 6-element lookup tables:

  static const uint8_t kLow[6] = { 0, 0, 1, 2, 1, 2 };

  static const uint8_t kHigh[6] = { 1, 2, 0, 0, 2, 1 };

And we can store the bounding box as a single byte per triangle, so our mesh structure becomes:

  struct Mesh {

    std::vector<vec3> verts;
    std::vector<uvec3> triangles;
    std::vector<uint8_t> bboxes;
  };

Given all that, we can decode the bounding box like this:

  vec3 Mesh::lowerBound(uint32_t tri) const {

    uint8_t bbox = bboxes[tri];

    uint8_t ix = kLow[bbox % 6];

    uint8_t iy = kLow[(bbox / 6) % 6];

    uint8_t iy = kLow[bbox / 36];

    return vec3(verts[triangles[tri][ix]].x, 

                verts[triangles[tri][iy]].y, 

                verts[triangles[tri][iz]].z);

  }

  vec3 Mesh::upperBound(uint32_t tri) const {

    uint8_t bbox = bboxes[tri];

    uint8_t ix = kHigh[bbox % 6];

    uint8_t iy = kHigh[(bbox / 6) % 6];

    uint8_t iy = kHigh[bbox / 36];

    return vec3(verts[triangles[tri][ix]].x, 

                verts[triangles[tri][iy]].y, 

                verts[triangles[tri][iz]].z);

  }

Encoding the bounding box is left as an exercise for the reader. :-)

So when would you use this? Well, probably never. If the min and max operations were extremely slow compared to the arithmetic operations and memory lookups but I think you'd be very hard pressed to find a platform where this is actually the case. It's an interesting thought exercise though.