| |
Trap
Registered: Jul 2010
Posts: 222 |
2D Bitmap rotation with interpolation
Hi,
I need subject function. I've been doing some goosearching on the subject but so far I only found algorithms that do not use interpolation. So, can some kind soul please point me in the right direction?
So far I only found rotation by shearing to make interpolation but the algorithm i found is too sketchy for me to be able to convert it to something executable.
thanks
Trap |
|
| |
Mixer
Registered: Apr 2008
Posts: 422 |
heh, I wrote a long answer, but time outed. Happens often.
Anyway, shear rotation is about first shearing rows by x depending on the angle and distance to origin. Once that is done, the resulting image columns are shifted same way depending on the angle and distance from origin. Pixels can only be shifted one full pixel at a time, so the pixel movement is quantized. Shear rotation actually works just because of this and the assumption that the pixel is square.
Adding interpolation to above is about subpixels, i.e. the x or y shift by angle is actually some fraction, for instance by 2.4 pixels. In that case, one would shift a row full 2 pixels and then interpolate the color between the adjacent pixels by that 0.4 fraction. Once row shearing is done for the whole image, one would interpolate row colors by fraction and once column shearing is done, one would interpolate y color.
How to do this on c-64? I know how to do shear rotation, but have never tried interpolation. How to shift a bit by a fraction? I guess that in multicolor one can use 00 01 10 11 bit pairs with a gradient color to portray subpixel interpolated fractions and then one could use some lookuptables to do that quickly.
There are demos that have subpixel scrollers and images and there are rotozoomers that use "hidden pixels" to give the impression of interpolation.
Is this on the right track? |
| |
Trap
Registered: Jul 2010
Posts: 222 |
Well yes and no. I do understand the theory behind shearing and interpolation but I am not sure if this is the 'best' algorithmic approach (given that I prioritize quality over speed). |
| |
Oswald
Registered: Apr 2002
Posts: 5018 |
from the topy of my head:
work with subpixels, that is each pixel's midle is at #.5 so middle of pixel 3,5 is 3.5 and 5.5
now apply rotation keep it all nice floating point, work with pixel's middle point's!!
now after a pixel is rotated you will see how far it is off from the middle point of the pixel it fell into.
now you can use any of the usual texture filter methods to calculate the pixel's color. bilinear, anisotropic, bicubic, etc. all these methods work basically by checking how far you are off from the pixel middle point iirc. |
| |
Oswald
Registered: Apr 2002
Posts: 5018 |
ok I see the problem, I guess its a good idea to rotate neighbour pixels and interpolate those according how much each falls off from the middle point of the DST pixel. |
| |
JackAsser
Registered: Jun 2002
Posts: 1989 |
Simple z-rotation? Quality before speed? if yes & yes:
From the top of my head:
a = angle;
// UV-vector
ux = cos(a);
uy = sin(a);
vx = -sin(a);
vy = cos(a);
// Center
cx = width/2;
cy = height/2;
for (y=0; y<height; y++) {
for (x=0; x<width; x++) {
texel = bitmap[(x-cx)*ux + (y-cy)*uy][(x-cx)*vx + (y-cy)*vy];
plot(x,y,texel);
}
}
|
| |
Mixer
Registered: Apr 2008
Posts: 422 |
If one has 2 squares, one rotated by some angle and puts them on top of each other, they overlap depending on their orientation. Assume one is source and the other is destination.
If these were grids, one destination grid square could overlap with many source grid regions depending on their orientation.
If destination pixel overlaps with many "rotated" grid pixels, what should the destination pixel color be set to? |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1378 |
Well, it's basically a resampling problem.
99% of texture mapping hardware just does bilinear interpolation of the original texture (at least for the instance where there is no scaling, only rotation in the 2d plane), so all you're doing is computing for each destination pixel a fractional position in the source texture, then interpolating the colours from the four corners of the square you land in.
Photoshop defaults to using bicubic interpolation for resampling images instead, which works well for photographs but can overshoot for anything with hard edges..
Here, have some code for reading from sub-pixel locations using bilinear:
http://www.scratchapixel.com/old/lessons/3d-advanced-lessons/in..
http://rosettacode.org/wiki/Bilinear_interpolation
Replace the texel = bitmap... line from JackAsser's post above with one of the routines just linked, and there you go. |
| |
Trap
Registered: Jul 2010
Posts: 222 |
this is excellent. Thank you guys.
I will take a look at all the great info tomorrow.
/Trap |
| |
Axis/Oxyron
Registered: Apr 2007
Posts: 91 |
Basically what JackAsser said.
If you do the interpolation with floating point or fixed point with atleast 16 fraction bits, your rendering should be subpixel and subtexel correct.
In simple words: When zooming into the image, your texels build correct rotated quads without any artifacts at the texel-borders. And If you move or rotate slowly the texel-borders move smoothly and do not jump full pixel-wise.
If you are there, you need to solve the resampling problem.
There are 2 possible ways: antialias or trilinear filtering.
Antialias is very CPU-intensive, because it just means to calculate the effect in a virtual higher resolution and accumulate all the calculated sub-pixels.
The triliniear filtering approach (or gfx-card-approach) is a combination of bilinear filtering and mip-mapping.
In bilinear filtering a 2x2 array of texels around the UV texel coordinate is fetched from the texture. These 4 texel colors are then linear interpolated based on the fraction of U and V. E.g. first interpolate the 2 left and the 2 right texels based with the V-fraction and then interpolate the 2 results based on the U-fraction.
Linear interpolation just means: result=value1+(value2-value1)*fraction.
In Mip-mapping a pyramid of textures is calculated. Every next mip-map has half the resolution on both axes (E.g. 16x16, 8x8, 4x4, 2x2, 1x1). The correct mip-map is choosen from the zoom-scale. This avoids the usual flickering on zooming out.
In trilinear filtering you just do the bilinear filtering for 2 succeeding mip-maps and again linear interpolate the results based on the fraction of your mip-map choose parameter (zoom-scale). This last interpolation removes the popping that appears when switching between mip-maps.
Major drawback of this algorithm is that the resulting image gets a little bit blurry.
If you use the tools from Microsoft or NVidia to generate your mip-maps, they do some extra magic (something like a sharpening filter) to overcome that problem. |
| |
HCL
Registered: Feb 2003
Posts: 716 |
Excuse me sir, this is far off-topic from anything c-64 related. Impossible to code in 8 bits and far too many multiplications to be calculated in more than a 4x4 pixel screen.
What i'm trying to say is.. i wish i knew stuff like this, and it is very interesting reading!! Why didn't i do some 10 years in the Amiga or PC-sceen!? Then perhaps i would have known something about common computer graphics :P. Give me my life back!! ;) |
| |
Oswald
Registered: Apr 2002
Posts: 5018 |
even a 060 amiga is not powerfull enough :) well, maybe a cube :) |
| |
Axis/Oxyron
Registered: Apr 2007
Posts: 91 |
I guess, if quality is the most important goal, the intention was more about making PC-tools to generate animations or tables than realtime rendering. |
| |
Oswald
Registered: Apr 2002
Posts: 5018 |
scripting a paint editor to rotate a picture can do that |
| |
Axis/Oxyron
Registered: Apr 2007
Posts: 91 |
Hehe, but scripting a paint editor is half the fun. ;o)
And true, 060 is not fast enough for this. Tried it back in the 90´s. The muls are not the problem. But 060 is slow on memory. So accessing 8 texels per pixel is not a good idea at all. When zooming out or your poly rotates 90° everything breaks down, due to bad cache coherence. |
| |
Shine
Registered: Jul 2012
Posts: 328 |
Maybe offtopic:
FU-Script / GIMP is most powerful! ;) |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1378 |
Quote: Hehe, but scripting a paint editor is half the fun. ;o)
And true, 060 is not fast enough for this. Tried it back in the 90´s. The muls are not the problem. But 060 is slow on memory. So accessing 8 texels per pixel is not a good idea at all. When zooming out or your poly rotates 90° everything breaks down, due to bad cache coherence.
Heh, improved cache coherence is half the reason the memory layout the PS2 uses for texture ram is such a bastard; they interleave the address bits to ensure that neighbouring texels are usually in the same set of cache lines regardless of orientation.
(of course, then they lightly scattered things a little to try and avoid multiple TMUs from trying to read the same word at the same time, but I digress.. Google ps2 texture swizzling if you want to melt your brain) |
| |
Trap
Registered: Jul 2010
Posts: 222 |
Sorry to take this back on to the original subject :)
I am not sure how I should read this. Mind you, I'm not particularly good at math and university was lightyears ago.
So, how exactly do I read this line:
texel = bitmap[(x-cx)*ux + (y-cy)*uy][(x-cx)*vx + (y-cy)*vy];
I believe [] means 'absolute', so unsigned right?
however, I'm not seeing an operator between the two sets of []. I'm guessing this implies something - just not sure what? My guess would be x and y coordinates respectively (of the source bitmap). On track? |
| |
Shine
Registered: Jul 2012
Posts: 328 |
Quoting Trap
So, how exactly do I read this line:
texel = bitmap[(x-cx)*ux + (y-cy)*uy][(x-cx)*vx + (y-cy)*vy];
I believe [] means 'absolute', so unsigned right?
I am unsure right now ... but [][] seems to me like the dimensions of an array (possibly list). |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1378 |
In this instance, [] means array access.
so texel[y][x] is like
peek(texture_address+y*texture_width+x)
(assuming one byte per pixel..)
I suspect it was also intended to be
[cy+(x-cx)*ux + (y-cy)*uy][cx+(x-cx)*vx + (y-cy)*vy]
to get a rotation around the centre of the texture. |
| |
Axis/Oxyron
Registered: Apr 2007
Posts: 91 |
@ChristopherJam: Yes, swizzling or tiling of the texture would have helped on the 060. I think all modern AGA demo-engines do that. I even heard of some S3-style texture compression mappers. |
| |
Trap
Registered: Jul 2010
Posts: 222 |
Thank you all for your help. I believe I have enough to keep me up for the next couple of evenings :)
/Trap |
