Thread: Rotation and signal processing?

  1. #1
    Registered User
    Join Date
    Oct 2006
    Location
    UK/Norway
    Posts
    485

    Rotation and signal processing?

    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,

  2. #2
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    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.

  3. #3
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    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.
    Last edited by abachler; 07-09-2008 at 06:45 PM.

  4. #4
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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.

    Code:
    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.
    Last edited by VirtualAce; 07-09-2008 at 08:59 PM.

Popular pages Recent additions subscribe to a feed