Rotation and signal processing?

[h3ro]

Hallo,

I am working on rotating a sprite in software.
What I am doing now is multiplying every pixel with a rotation matrix, which is slow.

I dont remember where I have this from, but I have been told/read that in order to speed up the rotation I can use some form of signal processing algorithm. It was something like rotating the first pixel, and the use the signal algorithm to find the rest.

Does anyone know anything about this? A link would be great. I tried google, but im not sure what to search for.

Regards,

[mike_g]

Its not something I have done yet. But the quickest way (If you have the ram) would probably be to pre-generate an image strip with your sprite rotated at each angle. Theres a RAM - Accuracy issue with it, but rotations would only mean flipping between frames then.

[abachler]

Rotation matrix's are faster on hardware that abstracts the math such as a GPU, if you are doing them manually then you are better off doing the trig itself, which involves far fewer multiplicatiosn and ends up with the exact same result. there are also optimizations that let you do fewer calculations. Check out 'Tricks of the game programmign Guru's'. Its an older book, before GPU's, so it deals with optimizing manually coded rotations.

[VirtualAce]

Before everything 2D was based on quads this technique was rarely used but is extremely fast. You can rotate just as the 3D APIs rotate. Do your matrix math for the rotation or do the 2D math required. Draw a quad in this orientation and then scan-convert the quad and texels as you poly-fill the quad.

1. Arrange the 'points' of the quad in clockwise fashion and set the u,v's of the points.
2. Start at the top of the primitive
3. If the next point has a lower Y value (IE: greater in 2D since 2D is always in the 4th quadrant), put it in the right array.
4. If the next point is higher (IE: lesser Y value) put it in the left array.
5. Draw lines from left to right using scan conversion and interpolation to determine u,v coords.

Use Bresehnam's algo to scan convert the lines and simply add in the u,v interpolation to and use those to 'fetch' the right colors from the bitmap.

You are scan converting on Y first to find what Y value you are starting at on the left and what Y value you are ending at on the right Once you have these endpoints you then draw a line from left.x,left.y to right.x,right.y using the same algo. If you also interpolate the u,v's starting at the points then you have a starting u,v and an ending u,v. So when drawing the lines from left to right you also interpolate from left u,v to right u,v. Simple linear texture mapping but it's fast, uses all integers with this algo, and will allow you to rotate the quad any way you want to. Note with this algo when the quad is rotated on the X axis, the linear texture mapping will start to warp since this is not perspective correct texture mapping. Older DOS games suffered from this heavily.

Using this very algorithm I was able to create a 3D poly-filled editor in QBasic on a Pentium 120. I also created a gouraud shaded texture mapped sphere in Qbasic using this. Then I moved to DJGPP and did the same using the linear frame buffer in SVGA mode. This algo is fast enough for what you want to do and the only sin and cos you will use is in the transform. The rasterizer is just linear operations.

Do not try to do the old-school bitmap rotation which involves adding pixels here and there as you rotate. This is a pain in the arse and it's slower.

Let's see if I can remember the line algo I used - without the u,v interpolation.

void DrawLine(int x,int y,int x2,int y2,DWORD color)
{
  unsigned int offset = y * screen_width + x;
  int eterm = 0;
  int stepx = 1;
  int stepy = screen_width;     //buffer pitch
  
  int diffx = x2 - x;
  int diffy = y2 - y;

  if (diffx < 0)
  {
     stepx = -stepx;
  }

  if (diffy < 0)
  {
     stepy = -stepy;
  }

  if (diffx > diffy)
  {
     int length = diffx + 1;

     for (int i = 0;i < length; ++i)
     {
         Screen[offset] = color;
         offset += stepx;
         eterm += diffy;
 
         if (eterm > diffx)
         {
            eterm -= diffx;
            offset += stepy;
         }
    }
  }
  else
  {
     int length = diffy + 1;

     for (int i = 0;i < length; ++i)
    {
       Screen[offset] = color;
       offset += stepy;
       eterm += diffx;
 
       if (eterm > 0)
       {
          eterm -= diffy;
          offset += stepx;
       }
    }
  }
}

Please don't take this verbatim. It's very close but I always confuse the eterm, what you compare it to, and what you decrement it by. That part is probably not correct. This also may draw 1 more pixel at the end of each line since length is set to diffy + 1 and diffx + 1. This can be changed if need be.