1. A method of encoding a downsampled video in a video encoder, wherein the downsampled video is a spatially downsampled version of a full-resolution video, the downsampled video including a frame having a macroblock partitioned into at least one partition, wherein one partition of the at least one partition corresponds to at least two full-resolution partitions in a corresponding frame of the full-resolution video, each of the at least two full-resolution partitions having an associated full-resolution motion vector relative to a reference frame, the method comprising: downscaling the associated full-resolution motion vectors; identifying, for each of the downscaled motion vectors, a search area within a downscaled reference frame, wherein that search area is centered at a pixel indicated by that downscaled motion vector; searching within each of the search areas for candidate motion vectors for said one partition, including determining for each candidate motion vector a rate-distortion cost; selecting as a desired motion vector for said one partition that candidate motion vector having a minimum rate-distortion cost; and encoding the downsampled video to generate an encoded downsampled video, including the desired motion vector for said one partition.