The video motion estimation (VME) unit of a graphics processor performs fast preprocessing prior to frame encoding to distribute macroblocks among slices based on weights of the macroblocks. The result of the preprocessing stage is iteratively improved based on the encoding stage. This allows real-time slice size limited encoding with minimum video quality reduction in some embodiments. Hardware preprocessing can be replaced with a software or hardware encoding step that gives macroblock weights (for example macroblock sizes after real encoding).