Compression methods and systems that encode the bounding volume hierarchy (BVH) and the triangles of a scene in one compact data structure. Efficient on-the-fly decompression is performed and may be used in interactive ray tracing. Quantized vertices and triangle strips may be stored in BVH leaf nodes. The local vertex positions and vertex indices may use a small number of bits that are encoded in bit strings. During traversal, the geometry may be decoded by an optimized algorithm allowing for random access with minimal overhead.