Techniques for coding and decoding video may include predicting picture regions defined by a time-varying tessellation and/or by a tessellation that varies spatially within a picture. These techniques improve decoded video quality, for example, by reducing block-based visual artifacts. Tessellation patterns may be irregular spatially to prevent alignment of some prediction region boundaries within a picture. Tessellation patterns may vary over time based on a spatial offset value, and the spatial offset value may be determined via a modulo function. Tessellation patterns may include overlapped shapes, for example when used in conjunction with overlapped block motion compensation.