A texture map for use in graphics processing is encoded by first subdividing the texture map into a plurality of texture element blocks. The texture data elements in each texel block to be encoded are then divided into different partitions (sub sets) within the block. The partitioned block is then encoded in a compressed form as an encoded texture data block. Each encoded block is partitioned using a partitioning pattern generation function to generate the partitioning patterns. The partitioning pattern generation function sorts the texture data elements of the block into respective partitions based on their respective positions within the block. To do this the partitioning pattern generation function generates a series of sawtooth waves at various angles, phases and frequencies across the block of texture data elements to be encoded.