The second step, the resampling, is just an interpolation operation. It is no more complex than applying normal moveout (NMO), for example. However, as with other resampling operators, the choice of interpolation (nearest-neighbour, linear, band-limited etc.) may affect the quality of results.
The more challenging problem is how do we determine the new coordinate system? Or equivalently, how do we determine the warp function itself?