Arrangements are provided for real-time variable compression and decompression schemes. In one arrangement, compressed images are stored as collections of tiled line textures representing breadth-first trees. In another arrangement, an image is decompressed directly on a GPU employing a microcode pixel shader. The arrangements allow for variable compression that can take into account complex local variations in light and shadowing. In this way, areas of high contrast may have significant detail preserved. The arrangement may be employed in a number of applications, including real-time shader image decompression, lighting and relighting, static shadow maps, dynamic texture packing, geometric representations, displacement maps, and so on.