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 …