A texture compression method is described. The method comprises splitting an original texture having a plurality of pixels into original blocks of pixels. Then, for each of the original blocks of pixels, a partition is identified that has one or more disjoint subsets of pixels whose union is the original block of pixels. The original block of pixels is further subdivided into one or more subsets according to the identified partition. Finally, each subset is independently compressed to form a compressed texture block.