A method for motion estimation of video data, the method comprising, when performing motion estimation of non-natural video data: selecting a candidate block of a first frame of the non-natural video data for matching with a current block of a second frame of the non-natural video data, the candidate block being selected from a first diamond pattern surrounding a predictor, the predictor being a previous candidate block of the first frame that is predicted to be a match having a lowest matching cost with the current block; obtaining a previous lowest matching cost for matching the predictor of the first frame with the current block, a matching cost being indicative of a matching error between two blocks of the non-natural video data; calculating a first partial matching cost for matching a first subset of samples of the candidate block to the current block; approximating a total matching cost for matching the candidate block to the current block based on the first partial matching cost; comparing the approximated total matching cost of the candidate block to the previous lowest matching cost of the predictor; determining whether the candidate block does not have a lowest matching cost with the current block based on the comparison of the approximated total matching cost of the candidate block and the previous lowest matching cost of the predictor; and selecting, in response to determining that the candidate block does not have a lowest matching cost with the current block, a subsequent candidate block for matching with the current block from a second diamond pattern that is horizontally and/or vertically displaced from the first diamond pattern and is the same size as the first diamond pattern, wherein the motion estimation is performed by traversing a fixed-size diamond-shaped search pattern horizontally and/or vertically across a first portion of the first frame, and wherein the method further comprises, after the fixed-size diamond shape search pattern has been traversed horizontally and/or vertically across the first portion of the first frame: i) determining a first distance between the candidate having the lowest matching cost and the current block; ii) determining a second distance between the predictor and the current block; and iii) determining, based on the difference between the first and second distances, whether to perform a refinement search or a full search with error approximation, wherein non-natural video data is computer-generated video data. selecting a candidate block of a first frame of the non-natural video data for matching with a current block of a second frame of the non-natural video data, the candidate block being selected from a first diamond pattern surrounding a predictor, the predictor being a previous candidate block of the first frame that is predicted to be a match having a lowest matching cost with the current block; obtaining a previous lowest matching cost for matching the predictor of the first frame with the current block, a matching cost being indicative of a matching error between two blocks of the non-natural video data; calculating a first partial matching cost for matching a first subset of samples of the candidate block to the current block; approximating a total matching cost for matching the candidate block to the current block based on the first partial matching cost; comparing the approximated total matching cost of the candidate block to the previous lowest matching cost of the predictor; determining whether the candidate block does not have a lowest matching cost with the current block based on the comparison of the approximated total matching cost of the candidate block and the previous lowest matching cost of the predictor; and selecting, in response to determining that the candidate block does not have a lowest matching cost with the current block, a subsequent candidate block for matching with the current block from a second diamond pattern that is horizontally and/or vertically displaced from the first diamond pattern and is the same size as the first diamond pattern, wherein the motion estimation is performed by traversing a fixed-size diamond-shaped search pattern horizontally and/or vertically across a first portion of the first frame, and wherein the method further comprises, after the fixed-size diamond shape search pattern has been traversed horizontally and/or vertically across the first portion of the first frame: i) determining a first distance between the candidate having the lowest matching cost and the current block; ii) determining a second distance between the predictor and the current block; and iii) determining, based on the difference between the first and second distances, whether to perform a refinement search or a full search with error approximation, ii) determining a second distance between the predictor and the current block; and iii) determining, based on the difference between the first and second distances, whether to perform a refinement search or a full search with error approximation, wherein non-natural video data is computer-generated video data.