[1] slides: http://acko.net/files/fullfrontal/fullfrontal/webglmath/onli...
[2] video: http://www.youtube.com/watch?v=GNO_CYUjMK8
The way the algorithm works, for each pixel, the amount of shear horizontally and vertically can be calculated up front, before "moving" the pixel.
So to make a one pass algorithm, allocate a second image of sufficient size to hold the rotated original (the size of this second image can also be calculated before any pixel "movement"). Then, for each pixel, calculate its horizontal shift, followed by its vertical shift, followed by its final horizontal shift. You now have its destination coordinates, so store it into the second image buffer at the destination coordinates.
The algorithm becomes essentially:
foreach pixel source_coord do
dest_coord = transform(source_coord)
dest_image(dest_coord) = source_image(source_coord)
done
where transform()
performs the Horiz/Vert/Horz transformation of the input coordinate.A one pass Paeth algorithm produces identical results to the typical three pass implementation, because there is only one round of trigonometry up front, so there is only one round of round-off. Once the shear amounts are calculated, the rest is just integer pixel shears.
http://www.cipprs.org/papers/VI/VI1986/pp077-081-Paeth-1986....
While most explanations of the algorithm follow this blog post and imply that it is a three pass algorithm, if one carefully reads Paeth's paper, one realizes that the algorithm can be implemented as a one pass algorithm.