Sign in to follow this  

Weighing pixels for affine transformation (2D)

Recommended Posts

Hi, I've been trying for days to figure out how to weigh pixels for 2D affine transformations, but in vain. [depressed] If it is pure scaling and translation, it's ok. (Thanks to TheAdmiral) But when rotation comes into the picture, things get very complicated. For example, for a transformation [ 0.3cos30 sin30 0 ] [ -sin30 0.3cos30 0 ] [ 0 0 1 ] How to calculate the weight for pixels 2, 3, 11, etc? [Edited by - snooty on October 2, 2006 6:15:14 AM]

Share this post

Link to post
Share on other sites
Hi again, snooty. I'll warn you - this is where things start to get messy [wink]. Two paths exist: one rather unpleasant and the other slightly less so.

If this rasterisation algorithm is aiming for accuracy, you'll need to calculate the intersection areas accurately. Hold on to your drawers...

Your first goal is to quickly eliminate (almost) all fully covered/uncovered pixels. This is best done by considering the destination pixel as the intersection of four non-axis-aligned half-planes. You can visualise this by extrapolating each side of the blue square to infinity in both directions: each will then be the dividing line between two half-planes; only one side of which contains the square. You can test which pixels are potentially split by testing for 'shortest distance' to each of these lines (the cross-product magnitude of the point's position and normalised ray will give you this, after translating to the origin). You may want to further make sure that the point is not much more than dest_pixel_width/sqrt(2) away from the centre, as the line segments stretch out forever and will give false positives otherwise.

From here, the problem is fairly trivially reduced to an 'intersection area of two arbitrary coplanar squares' problem, on each remaining pixel. Using the half-plane-intersection abstraction described above, this reduces further to a case-analysis on four square/half-plane area intersection tests. I'm not sure how well-documented this is, but it's worth a Google if you want to keep along this route. Speak up if you'd like more information.

The alternative is to use a sampling method like the ones your graphics card uses. This sacrifices a little accuracy for a lot of speed. When pixel-pixel mapping is roughly 1-1, the difference isn't all that obvious on a first-generation rotation, but after several successive resamples, or using large or small scaling factors, the difference becomes rather noticeable.
The idea is to take several (usually equally-spaced) samples, rounded to the nearest pixel, and weight them equally. As the number of samples increases, this becomes a better and better approximation to the true value.

The most basic of such filters will sample the four corner points of the destination pixel, rounding them to the nearest point in the source image, and weight the results equally. As you can imagine, this will completely miss out any detail in the centre of the destination pixel when scaling down significantly, so it doesn't make for a great min-filter.
The technique is rather naturally developed by including another sample in the centre of the pixel. This is quincunx sampling, if you're familiar with that term.

I'm sure you can guess the idea for further improvement: Increase the number of samples and keep them as uniformly spaced as possible. If you stick to square numbers, this usually involves sampling a regular grid, which is straightforward enough.

A nice idea to take this further is to employ a 'smart scale', which bases the number of sample points on the square of the scaling factor, to keep as close as possible to the optimal situation whereby each source pixel is sampled once and only once.

This should be enough to get you going again. Let me know if anything wasn't clear.


Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this