News for hackers. Stuff that matters.
Re:Rotating Images by pwg on Saturday August 17, 2013 @10:53AM (#6229230)
The unmentioned publication behind this method is: "A Fast Algorithm for General Raster Rotation" by Alan W. Paeth. A copy of which can be obtained here:

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.

Re:Rotating Images by DanielRibeiro on Saturday August 17, 2013 @06:22PM (#6230573)
Another very good overview of rendering algorithms was given by Steven Wittens on his Making Webgl Dance[1, 2]

[1] slides: http://acko.net/files/fullfrontal/fullfrontal/webglmath/onli...

[2] video: http://www.youtube.com/watch?v=GNO_CYUjMK8

Re:Rotating Images by e98cuenc on Sunday August 18, 2013 @11:37AM (#6232941)
This is a fantastic speech and slides. Thanks for the link!
Re:Rotating Images by jwmerrill on Sunday August 18, 2013 @12:35PM (#6233153)
Can you expand on the one pass algorithm, or provide a link? There was a two pass variant at the end of the paper, but I didn't see any explicit one pass variant.
Re:Rotating Images by pwg on Monday August 19, 2013 @12:33AM (#6235635)
The solution to making a one pass algorithm from the paper is to realize that each pixel moves a fixed amount. First it moves horizontally, then vertically, then horizontally, to arrive at its final location.

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.
Re:Rotating Images by deletes on Sunday August 18, 2013 @01:38PM (#6233419)
The single pass is the first algorithm mentioned in the article that produces "holes". You have to split the operations to avoid them and thus make more passes.
Re:Rotating Images by pwg on Monday August 19, 2013 @12:43AM (#6235662)
The first algorithm mentioned in the article is not a one-pass Paeth algorithm. The first algorithm in the article is a pure trigonometry algorithm.

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.