I would still rather use a simple texture mapping - map the image to a rectangle and then just rotate the 4 corner points. Rest is done naturally by your texture mapper. You can implement a texture mapper easily by finding the top-most rotated corner, take the two edge lines coming out of that corner, linearly interpolate texture coordinates on these lines for each horizontal line they cross and then simply walk linearly between those two texture positions spread across the horizontal line range. Then replace the edge line whose endpoint you reached by the next line until you reach the bottom-most corner. You can add surrounding texels to the mix to get the bilinear or another filtering. Also, Bresenham's line algorithm can be used for each of the line interpolations (though my assembly language experience showed that fixed point ints were actually faster). This is also embarrassingly parallel.
