Embodiments of the invention are directed to a system and method for sub-pixel motion estimation for video encoding. The method includes providing a best match between a source frame and a reference frame by generating a plurality of non linear building surfaces, generating, in real time, an estimated matching criteria surface representing a matching criteria between the source frame and the reference frame based on the building surfaces and a plurality of sample points of an actual matching criteria surface and selecting, in real time, a position on the estimated matching criteria surface.