A virtually-addressed local texture memory stores selected regions (a sparse representation) of a texture for use by a graphics processor. The graphics processor requests a texel of the texture by referencing a virtual address of the texel. A memory interface references an address map to determine whether the requested texel is in one of the regions of the texture that is resident in the local texture memory. If so, the texel is retrieved from the local memory and used in the rendering operation; if not, an alternative texel that is resident in the local memory is retrieved and used in the rendering operation. Non-resident regions that include requested texels are retrieved from a primary texture data store at regular intervals (e.g., once per frame) and stored in local texture memory for use in a subsequent rendering operation.