gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

DS development > inversing affine matrix inaccurate?

#169995 - vuurrobin - Fri Aug 21, 2009 1:58 am

hello everybody,

because the ds hardware needs an inverse affine matrix instead of a normal affine matrix, I wanted to make an function that would inverse the matrix before storing it and some functions to get the normal matrix elements back. I used the inverse matrix formule on toncs affine matrix page.

it seems to work, but there seems to be some inaccuracy with the inverted matrix, and when inverting it back, the numbers are some points off. the axes also seems wrong. the y ax points down (which it should, according to tonc) but the x ax points to the left instead of the right.

here is the code to invert the matrix:

Code:
/**
    @brief Allows you to directly sets the affine transformation matrix.

    with this, you have more freedom to set the matrix, but it might be more difficult to use if
    you're not used to affine transformation matrix.
    this function will invert the matrix so it will work correctly with the hardware.

 * @param hdx   the 1st matrix value, in .8 fixed point format.
 * @param vdx   the 2nd matrix value, in .8 fixed point format.
 * @param hdy   the 3th matrix value, in .8 fixed point format.
 * @param vdy   the 4th matrix value, in .8 fixed point format.

    @return a reference to the object, so you can chain multiple commands.
 */
inline AffineMatrix& setAffineTransformation(const int hdx, const int vdx, const int hdy, const int vdy)
{
   register int temp = (((hdx*vdy) >> FIX_SHIFT) - ((vdx*hdy) >> FIX_SHIFT));
                temp = ((FIX_VALUE_1 * FIX_SCALE) / temp);

   this->hdx = (temp * vdy)  >> FIX_SHIFT;
   this->hdy = (temp * -vdx) >> FIX_SHIFT;
   this->vdx = (temp * -hdy) >> FIX_SHIFT;
   this->vdy = (temp * hdx)  >> FIX_SHIFT;

   return *this;
}


where FIX_VALUE_1 and FIX_SCALE is (1<<8) and FIX_SHIFT is 8.
and this is the code to invert one of the values back to its original:

Code:
/**
    @brief returns the 1st value of the affine matrix.

    @return the 1st value of the affine matrix, in .8 fixed point format.
*/
inline const int gettesthdx() const
{
    register int temp = (((hdx*vdy) >> FIX_SHIFT) - ((vdx*hdy) >> FIX_SHIFT));
                temp = ((FIX_VALUE_1 * FIX_SCALE) / temp);

    return (temp * vdy) >> FIX_SHIFT;
}


does anybody sees a mistake that could explain the wrong ax, or a way to increase the accuracy so the points are more acurate? (maybe using more bits for the fixed point)


I've also created a program to test this, if anybody is interesting:

http://vuurrobin.100webcustomers.com/stuff/changingAffineMatrix.zip
(copy-paste to the adress balk if clicking it doesn't work)

the first 4 values are the normal affine matrix, which you can change with the ABXY and directional keys.

the second 4 is the inverse matrix, which the hardware uses.

the last value is one of the matrix values inverted back. this should be equal to the first value, but sometimes it is off.

#170003 - TwentySeven - Fri Aug 21, 2009 9:04 am

If the matrixes you're feeding in are orthagonal the inverse is equal to the transpose.

#170004 - Cearn - Fri Aug 21, 2009 10:52 am

Don't shift down so soon. Do the calculations in as high a precision as you can. This will increase the accuracy. There's also no real need for const here because ints are passed by value, and on ARM systems the register keyword is more or less useless because there's no other place for operands to be.

Code:

inline AffineMatrix& setAffineTransformation(int hdx, int vdx, int hdy, int vdy)
{
   int det= hdx*vdy - vdx*hdy;   // Q16
   int invdet = 0x1000000 / det;  // Q8

   this->hdx = (invdet * vdy)  >> FIX_SHIFT;
   this->hdy = (invdet * -vdx) >> FIX_SHIFT;
   this->vdx = (invdet * -hdy) >> FIX_SHIFT;
   this->vdy = (invdet * hdx)  >> FIX_SHIFT;

   return *this;
}

This should be a little better, but you're always going to have a little offset. You're going to have to round off at some point, and that's where errors creep in. Where possible, use the direct matrices, rather than going through an inverse function.

As far as I can see, the axes are fine. With a 45· rotation to the left, h=(1,-1)/√2 and v=(1,1)√2. That is to say, h points to top-right and v to bottom-right. There is something odd about the numbers of the second matrix though. for a rotation, the minus sign should be in the other diagonal. The matrix in OAM is correct though.

#170017 - vuurrobin - Fri Aug 21, 2009 10:56 pm

I know that const and register isn't needed there, but I like to put there anyway. tells more about my code.

your code does work, with more precision, but I've tried a different, more basic way of inversing the matrix. I'm not sure if its correct, or works with all 2*2 matrices, but it seems to work correctly:

Code:
this->hdx = (-(hdx-FIX_VALUE_1)) + FIX_VALUE_1;
this->hdy = -vdx;
this->vdx = -hdy;
this->vdy = (-(vdy-FIX_VALUE_1)) + FIX_VALUE_1;


there are still some problems with it when trying to flip the image (it flips with 768, instead of -256), and I still think that one of the axes is wrong. when I increase vdx, the top part of the image go's to the left, instead of the right. which means that the ax points left...

the inverse of the identity matrix is exactly itself, right? does that also aply to this:
Code:

[[-1,  0]
 [ 0, -1]]


I've created another program with the second approach:
http://vuurrobin.100webcustomers.com/stuff/changingAffineMatrix2.zip
(again, copy-paste to the adress balk if clicking it doesn't work)

it seems to work correctly, and the last value is exactly like the first value, which means converting and converting back is accurate.

Quote:
There is something odd about the numbers of the second matrix though. ... The matrix in OAM is correct though.


that doesn't make much sense, seeing as the second matrix is the one that is directly set into OAM.

EDIT: there is another problem with this method, causing the image to scale 2 times when the value is 384 instead of 512. will try to fix it later.

#170018 - Cearn - Sat Aug 22, 2009 10:29 am

vuurrobin wrote:
I know that const and register isn't needed there, but I like to put there anyway. tells more about my code.

Fair enough. But remember that in general, less cruft makes code more readable.

vuurrobin wrote:
your code does work, with more precision, but I've tried a different, more basic way of inversing the matrix. I'm not sure if its correct, or works with all 2*2 matrices, but it seems to work correctly:

Code:
this->hdx = (-(hdx-FIX_VALUE_1)) + FIX_VALUE_1;
this->hdy = -vdx;
this->vdx = -hdy;
this->vdy = (-(vdy-FIX_VALUE_1)) + FIX_VALUE_1;


there are still some problems with it when trying to flip the image (it flips with 768, instead of -256)

This method doesn't work. Or, rather, it will work for some matrices, but not all. The definition of the inverse matrix A is the matrix that, when multiplied with A results in I : A[sup]-1[/sup]*A = I. For the general case, this will require division by the determinant.

vuurrobin wrote:

and I still think that one of the axes is wrong. when I increase vdx, the top part of the image go's to the left, instead of the right. which means that the ax points left...

That depends on which vdx you're referring to. It might be better not to use the same terms for different matrices. Say that the forward transformation is given by axes A=[a b], with a=(ax, ay) and b=(bx, by) and the inverse by P=[h v]. If bx (which I assume you're referring to here) increases, the point for b moves right. However, since b points downward, you really need to look at the bottom-left point, not the top-left.

Code:

    |                            \
    |                             \
    |                              \
-------------> a (1,0)          ----------> a (1,0) 
    |                                \
    |                     ---\        \
    |                     ---/         \
    |                                   \
    V  b (0,1)                          _\| b (1,1)


vuurrobin wrote:

the inverse of the identity matrix is exactly itself, right? does that also aply to this:
Code:

[[-1,  0]
 [ 0, -1]]

Yes in both cases. I*I = I and (-I)*(-I) = (-1*-1)*(I*I) = I.

vuurrobin wrote:

I've created another program with the second approach:
http://vuurrobin.100webcustomers.com/stuff/changingAffineMatrix2.zip
(again, copy-paste to the adress balk if clicking it doesn't work)

it seems to work correctly, and the last value is exactly like the first value, which means converting and converting back is accurate.
EDIT: there is another problem with this method, causing the image to scale 2 times when the value is 384 instead of 512. will try to fix it later.

The second demo does not seem to be following the equations you gave earlier. The demo handles shears fine (with vdx = - bx), but the equations have vdx = -ay, which isn't right.

vuurrobin wrote:

Quote:
There is something odd about the numbers of the second matrix though. ... The matrix in OAM is correct though.


that doesn't make much sense, seeing as the second matrix is the one that is directly set into OAM.

I think the error may be in printing the matrix. It seems hdy and vdx are switched.

#170021 - vuurrobin - Sun Aug 23, 2009 1:54 am

here is the fixed version of my method:

Code:
this->hdx = (FIX_VALUE_1<<8) / hdx;
this->vdy = (FIX_VALUE_1<<8) / vdy;
this->hdy = -vdx;
this->vdx = -hdy;


I'm still not sure if this is correct, but is seems correct to me. its at least better than my last attempt (which was just wrong), and the accuracy of inverting it back is also pretty good.

I've created another program (again) with this method:
http://vuurrobin.100webcustomers.com/stuff/changingAffineMatrix3.zip
this program prints the entire 3th matrix, which should be equal to the first (although there are some presicion errors). I've also implemented flipping the sprite horizontally and vertically using an affine matrix (cause hardware flipping can't be used when using an affine matrix). you can flip it with start and select. also, touching the screen will reset the matrix to the identity matrix.


Quote:
However, since b points downward, you really need to look at the bottom-left point, not the top-left.


ack, I mixed the axes up. that would explain it. sorry, my bad.


Quote:
I think the error may be in printing the matrix. It seems hdy and vdx are switched.


I double-checked it, and printing the matrix seems correct. I also checked the rest of the code, in case I was switching function parameters or something, but that also seem fine. as far as I can tell, the second matrix on screen is the matrix in OAM.

#170022 - Cearn - Sun Aug 23, 2009 11:16 am

vuurrobin wrote:
here is the fixed version of my method:

Code:
this->hdx = (FIX_VALUE_1<<8) / hdx;
this->vdy = (FIX_VALUE_1<<8) / vdy;
this->hdy = -vdx;
this->vdx = -hdy;


I'm still not sure if this is correct, but is seems correct to me. its at least better than my last attempt (which was just wrong), and the accuracy of inverting it back is also pretty good.

I'm sorry, but no. I think what you're trying to do is look at the elements individually -- to see if, when you plug-in the numbers, you get the old matrix back:
Code:

| a  b | ->  | (1/a)  -c   |  ->  | 1/(1/a)   -(-b)    |  = | a  b |
| c  d |     |   -b  (1/d) |      |  -(-c)    1/(1/d)  |    | c  d |

This isn't how matrix inverses work. Matrix inverses look at matrix multiplications, specifically, if you have matrices A and B for which A*B = I holds, then A and B are each other's inverses. If you multiply the matrices you have now, you get
Code:
| (1/a)  -c   |*| a  b |  = | ( a/a-cc) ( b/a-cd) |  = | (1-c²)  (b/a-cd) |
|   -b  (1/d) | | c  d |    | (-ab+c/d) (-bb+d/d) |    | (c/d-ab)  (1-b²) |

If b and c are 0 it'll work, but otherwise it won't.
You can also see it by trying out a scale + rotate, say R(45°)S(2,1). In Q8, that should be:
Code:
A = | 362  181 |    A^-1 = |  90   -90 |
    | -362 181 |           | 181   181 |

While the "test" matrix gives back the original matrix, the actual transformation is not what it should be.

The correct form of the inverse is:
Code:
A = | a  b |
    | c  d |

D = ad-bc

P = | hx  vx |  = A^-1 =  |  d  -b | * 1/D
    | hy  vy |            | -c   a |

This is pretty much what you had in the OP, except that there you had vx and hy swapped. I think the problem may be in the class definition itself.

vurrrobin wrote:
Quote:
I think the error may be in printing the matrix. It seems hdy and vdx are switched.

I double-checked it, and printing the matrix seems correct. I also checked the rest of the code, in case I was switching function parameters or something, but that also seem fine. as far as I can tell, the second matrix on screen is the matrix in OAM.

Run any of the programs in Desmume (0.9.4) and vary hy :
Code:

| 256   0 |
|  hy  256 |

Open the ARM9 memory viewer, goto 07000000 and set it to 16-bit. You should see the matrix in the 4th and 8th column. When you move hy, you'll see the 3th matrix element change. This is how it should be. However, in the 'raw' matrix on screen, it's the second element (rawvdx) that changes. This is what I meant when I said something's off in the debug prints.

#170026 - vuurrobin - Mon Aug 24, 2009 12:13 am

I think I've found the problem. from what I can see in gbatek and tonc, the parameters should come in this order in memory: hdx, vdx, hdy, vdy. but libnds has this in sprite.h:

Code:
/**
 * @struct SpriteRotation
 * @brief A sprite rotation entry
 */
typedef struct {
  uint16 filler1[3]; /**< Unused! Filler for the sprite entry attributes which overlap these */
  int16 hdx;       /**< The change in x per horizontal pixel */

  uint16 filler2[3];  /**< Unused! Filler for the sprite entry attributes which overlap these */
  int16 hdy;        /**< The change in y per horizontal pixel */

  uint16 filler3[3];  /**< Unused! Filler for the sprite entry attributes which overlap these */
  int16 vdx;        /**< The change in x per vertical pixel */

  uint16 filler4[3];  /**< Unused! Filler for the sprite entry attributes which overlap these */
  int16 vdy;         /**< The change in y per vertical pixel */
 
} SpriteRotation, * pSpriteRotation;


I think int16 hdy and int16 vdx should be switched here. this also means that I overcompensated to get the values in oam right so that the values on screen were wrong. if someone can confirm this, then I'll post it in the bug report section of the devkitPro forums so it can be fixed with the next libnds version.


as for what I am doing, I'm trying to create a function that takes an affine matrix as how an human would see it, and put it in OAM in such a way that the image on screen will look like how the human will think it looks. this is useally done by inversing the matrix (which is what I first did), but then I tried to do it without inversing the matrix (which seemed more complicated than nessisary) to get a better accuracy and to make it easier for the human. if ? decide that axes pointing up-right instead of bottom-right is easier, than I will change the function like that (and document it of course). if the matrix in OAM isn't the inverse of the matrix entered by the human, or the formula won't work on all matricen, then thats fine by me. I'm sorry if this wasn't clear (although it wasn't really clear to me to at first)