Coordinates in distorted grid

Question

I have a grid in a 2D system like the one in the before image where all points A,B,C,D,A',B',C',D' are given (meaning I know the respective x- and y-coordinates).

I need to calculate the x- and y-coordinates of A(new), B(new), C(new) and D(new) when the grid is distorted (so that A' is moved to A'(new), B' is moved to B'(new), C' is moved to C'(new) and D' is moved to D'(new)).

The distortion happens in a way in which the lines of the grid are each divided into sub-lines of equal length (meaning for example that AB is divided into 5 parts of the equal length |AB|/5 and A(new)B(new) is divided into 5 parts of the equal length |A(new)B(new)|/5).

The distortion is done with the DistortImage class of the Sandy 3D Flash engine. (My practical task is to distort an image using this class where the handles are not positioned at the corners of the image like in this demo but somewhere within it).

Answer 1

Are you sure that you want to be getting into all of this for handles? in the examples the handles are there to act as reference points on the movieclip for drawing, they are not related in any way to the image or the distortion apon it. if you are wanting to just have the handlers inside the image then you would just need to offset the point calculation value (topRightCorner = new Point(pointb.x +10, point.y - 10) for example)

if you are really wanting to get into calculating exact points then you can try doing a call to localToGlobal(new Point(this.x, this.y)) from a handler to work out where it is (and therefore the translation that has been applied to it). otherwise you are going to have to deal with transformation matricies and work out exactly how the class calculates its triangles.

for a very good guide to transformation matricies, see here: senoular.com

good luck

Answer 2

Do you want help from algorithmic point of view (Transformations etc) or are you looking for help on how to achieve transformations specifically using Sandy 3D flash engine?

Answer 3

You could probably figure something out, but I doubt that you or your users are going to like the result.

To see why, select a point in the interior of the image. Say you want to move it upwards by a bit. You can do that by moving any one of the four corners (try it in the demo). That means if you wanted to put a handle there and move it upwards, the four corners would move in some combination. Most likely the corners would not do what you want. For example, all four of them could move up by the same amount, resulting in a pure translation and no warp. Or a single corner could move, but maybe not the one you expected. There are an infinity of solutions, and most likely the one you choose is not the one you (or somebody else) is expecting.

The distortion method being used in the demo, by the way, is "bilinear interpolation". Having the handles at the corners is probably the best way to control it.

Answer 4

This looks like a linear transformation to me. We know this because any line in the original graph is also a line in the transformed graph (this is not always true of the demo you gave, but will be true if you follow the directions you gave in your question and not allow concave vertices). I do believe that AS3 has built-in support for transformation matrix manipulations. If not, you can implement them yourself.

[ x' ]  =   [ a b ] x [ x ]
[ y' ]      [ c d ]   [ y ]

These are matrices. The first is a vector (your final point), and that equals a certain 2x2 matrix multiplied by a vector (your original point)

If you're not familiar with matrix multiplication, this can be simplified out to be:

x' = a*x + b*y
y' = c*x + b*y

Any linear transformation can be represented by that two-by-two matrix of a, b, c, and d. Pick numbers for each of them, and you get a linear transformation. So how do you find the values of a, b, c, and d that will give you yours?

For four unknowns, you need four equations. If you look at the equations above, you'll see that one point ("vector") and its transformation will give you two equations. So...we need two points. As you'll see later, it'll be useful to pick points in the un-transformed form (m,0) and (0,n) (ie, one along your x axis, and the other along your y axis).

In your example, these are easy to find! They are B and D (if A or C is your origin)!

I'll be using a bit different notation: "primes" for transformed versions of points.

B => B'
B_x => B'_x
B_y => B'_y

If you know the before and the after coordinates of B and D, you can find your transformation matrix a,b,c,d.

Setting up your equations:

B'_x = a * B_x + b * B_y
B'_y = c * B_x + d * B_y

D'_x = a * D_x + b * D_y
D'_y = c * D_x + d * D_y

Now, let's say that B is your x-axis point, in form (B_x,0). Say D is your y-axis point, in form (0,D_y). If this is opposite, switch them. Here, we assume that your origin is A = (0,0), like in most Flash apps.

Setting B_y = 0 and D_x = 0, we get:

B'_x = a * B_x + b * 0
B'_y = c * B_x + d * 0
D'_x = a * 0   + b * D_y
D'_y = c * 0   + d * D_y

Using the powers of algebra, we find:

a = B'_x / B_x
c = B'_y / B_x
b = D'_x / D_y
d = D'_y / D_y

So, in short:

If you know original points: (the vertices on the original x and y axis)

M = (M_x, 0)
N = (0  , N_x)

and their transformed/distorted points

M' = (M'_x, M'_y)
N' = (N'_x, N'_y)

(so that M => M' and N => N')

then calculate and store these four variables:

a = M'_x / M_x
b = N'_x / N_y
c = M'_y / M_x
d = N'_y / N_y

and finally:

(x, y)  =>  ( a*x + b*y , c*x + d*y )

---

edit: Okay, I ran through a few of your arbitrary-corner-handle transformation, and realized that I jumped to conclusions when I assumed that your transformation was linear. The equations above will only be linear under two conditions:

1. Your new grid is the shape of some rotated parallelogram (and you original is a square, 'normal' grid)
2. The position of your (0,0) origin point does not change.

Now, I'm not sure what degrees of freedom you are allowing your handles to be positioned by, but perhaps you can restrain them so that your gridspace always follows the form of a rotated parallelogram.

Answer 5

I can't give you the full answer, but I am pretty sure you will find it in "Fundamentals of Texture Mapping and Image Warping" by Paul S. Heckbert: http://www.cs.cmu.edu/~ph/texfund/texfund.pdf (in the appendix it contains source code for all kinds of mappings)

Answer 6

Let (u,v) represent "texture" coordinates. Your handles stay at the same texture coordinates regardless of grid distortions.

So, in texture space, A=(0,0) B=(1,0) C=(1,1) D=(0,1) A'=(au,av) B'=(bu,bv) ...

We can convert from texture space to pixel space.

P(u,v) = A*(1-u)*(1-v) + B*u*(1-v) + C*u*v + D*(1-u)*v

(u,v are texture coordinates, and A, B, C, D refer to pixel coordinates)

So, if your handle A' is defined to have texture coordinate (.35,.15), then the position of A' in pixel space is given by P(.35,.15).

Now, say the user drags handle A'. We need to solve for the new location of A. B,C,D remain fixed. It's just simple algebra.

A' = A*(1-au)*(1-av) + B*au*(1-av) + C*au*av + D*(1-au)*av
A' - B*au*(1-av) - C*au*av - D*(1-au)*av = A*(1-au)*(1-av)
A = (A' - B*au*(1-av) - C*au*av - D*(1-au)*av) / ((1-au)*(1-av))

Not too bad. The same process gets formulas for the other handles. Here is my C# code. It gets called when any of the 8 "Thumbs" get dragged:

     double au = .35, av = .15; // texture coordinates of A'
     double bu = .8, bv = .2;   // texture coordinates of B'
     double cu = .8, cv = .6;   // texture coordinates of C'
     double du = .2, dv = .9;   // texture coordinates of D'

     // if we're dragging A' (AA), then move A, etc.
     if (sender == ThumbAA) A = (AA - B*au*(1-av) - C*au*av - D*(1-au)*av) / ((1-au)*(1-av));
     if (sender == ThumbBB) B = (BB - A*(1-bu)*(1-bv) - C*bu*bv - D*(1-bu)*bv) / (bu*(1-bv));
     if (sender == ThumbCC) C = (CC - A*(1-cu)*(1-cv) - B*cu*(1-cv) - D*(1-cu)*cv) / (cu*cv);
     if (sender == ThumbDD) D = (DD - A*(1-du)*(1-dv) - B*du*(1-dv) - C*du*dv) / ((1-du)*dv);

     // update position of A', B', C', D'   
     AA = A*(1-au)*(1-av) + B*au*(1-av) + C*au*av + D*(1-au)*av;
     BB = A*(1-bu)*(1-bv) + B*bu*(1-bv) + C*bu*bv + D*(1-bu)*bv;
     CC = A*(1-cu)*(1-cv) + B*cu*(1-cv) + C*cu*cv + D*(1-cu)*cv;
     DD = A*(1-du)*(1-dv) + B*du*(1-dv) + C*du*dv + D*(1-du)*dv;

video of my demo app: http://screencast.com/t/NDU2ZWRj

This doesn't answer your exact question about repositioning 4 handles at the same time. Is that what you really want? Also, let me know if your handles' texture coordinates aren't predetermined. You can convert from pixel to texture coordinates, but it is more complicated.

Answer 7

You speak of a 2D system, yet the distortion you're applying is a 3D distortion (albeit projected back down into 2d, of course) - is that intentional?

In general, I'm not actually sure it's possibly to compute A'new's new location without more information about the perspective projection being using than just ABCD's new locations. After all, perspective projection exaggerates nearby distances and compresses distant ones - and the degree to which it does this depends on the distance from the focal point (equivalently, the FOV).

It'd be easiest, in any case, to reuse whatever needed to be computed for the projection in the first place - if you can get the original transformation matrix and perspective transform, you can straightforwardly apply those to A' B' and D' as well.