Modified line algorithm for bitmap rotation
Author
Hi, I''m currently working on upgrading my existing 2D engine to
handle stuff like rotated sprites, scaling etc...
My rotation function works like this:
1. Clear destination surface, size of the source diagonal in
each direction to rotate the bitmap into.
2. Calculate coordinates of source rectangle aroud the origin
3. Build a combined 2D rotation/translation matrix to rotate the
points about the origin the translate then to the centre of
the surface.
4. Multiply 3 corners by the matrix, do subtractions for the 4th
5. Calculate endpoints of each row using Bresenhams line
algorithm
6. Draw each source row between endpoints, again using Bresenhams
The problem is that since Bresenhams plots one pixel for each
step along the major axis, in the worst case it will plot half
the number of pixels needed to display a row of the image,
leading to a funky but unwanted roto-zooming effect.
So what I was wondering is... does anyone know of a fast (but
still fairly pretty) way of drawing the rotated image rows?
Thanks
Jim
I was going to do something similar, but never got round to implementing it. Forgive me if the following makes no snse, I''m a newbie:
To solve the problem of one row in the rotated rectangle having a differnet number of pixels than one row in the source rectangle, I was thinking of using an adapted version of Bresenham''s algorithm to englarge each line. Rather than using it to increase y every few times x is increased, use it to calculate when you should advance along the source row and when you should advance along the destination row. You''d then need another copy of the algorithm within this to actually draw the rotated row.
Would that work?
To solve the problem of one row in the rotated rectangle having a differnet number of pixels than one row in the source rectangle, I was thinking of using an adapted version of Bresenham''s algorithm to englarge each line. Rather than using it to increase y every few times x is increased, use it to calculate when you should advance along the source row and when you should advance along the destination row. You''d then need another copy of the algorithm within this to actually draw the rotated row.
Would that work?
Author
Well I got something that works, using linear interpolation
with fixed point numbers so its all still integer.
Like texture coordinates, kind of.
I also have to draw an pixel every time the minor axis is changed otherwise there''ll be gaps.
Thanks anyway.
with fixed point numbers so its all still integer.
Like texture coordinates, kind of.
I also have to draw an pixel every time the minor axis is changed otherwise there''ll be gaps.
Thanks anyway.
Just rotate all the pixels. The angle is constant for the entire rotation so the sin() and cos() is constant. As you process a row you are just adding one to x and y is remaining constant. So you can replace the multiplications with addition. Integers will create an unacceptable rounding error, but fixed point should do fine. Basically just shift the sin(), cos() and x/y values to the left 16 places. Since you are adding the implied decimal place has to be in the same place. You can round to the nearest interger by adding 2^15 and shifting the value right 16 places. It is just like adding 1.1 to 1.1 by shifting the decimal right one place, adding 11 to 11 to get 22 and shifting the decimal left one place to get 2.2 except it is a binary decimal point. You will get a 30% overplot, i.e. mapping two pixels to the same destination, in the worst case, but eliminating it will most likely cost you everything you might save.
If the image doesn''t look good then you can first try averaging the overplots. If it still doesn''t look good then you are going to have to reverse direction and interpolate the color. A pixel in the destination actually maps to a location between two columns and two rows in the source in most cases. You have to do a weighted average of the four pixels at the upper left, upper right, lower left and lower right of where it actually mapped to. You can assign each of the rows and columns a weight based upon how far between them the actual point is. Then you take the four pixels, multiply each by their row and column weight and then sum them. Needless to say this adds a great deal more work though perhaps not as much as you might think once optimized. So unless there is really a serious problem with the rotated sprite then I doubt it is worth it.
If the image doesn''t look good then you can first try averaging the overplots. If it still doesn''t look good then you are going to have to reverse direction and interpolate the color. A pixel in the destination actually maps to a location between two columns and two rows in the source in most cases. You have to do a weighted average of the four pixels at the upper left, upper right, lower left and lower right of where it actually mapped to. You can assign each of the rows and columns a weight based upon how far between them the actual point is. Then you take the four pixels, multiply each by their row and column weight and then sum them. Needless to say this adds a great deal more work though perhaps not as much as you might think once optimized. So unless there is really a serious problem with the rotated sprite then I doubt it is worth it.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
