Pages: 1
  Print  
Author Topic: Simple Transformations  (Read 1934 times)
Offline (Unknown gender) TheExDeus
Posted on: June 28, 2012, 08:49:17 AM

Developer
Joined: Apr 2008
Posts: 1872

View Profile
Hi. Not really connected to ENIGMA, but still thought I might ask here. In one of my projects I need to transform from a convex quadrilateral to a rectangle. I though of just using bilinear interpolation, but got stuck at some basic ideas - mainly that the points for the convex quadrilateral with the point P has the origin still at the top left and so x0,y0 isn't 0,0 as it is in rectangle case. Here is a picture:

(note x0,y0, x1,y1... and so on are of course different for both the quadrilateral and the rectangle, I just named them the same)
As the transformation would be linear then the math isn't that hard, but I am tired now and if someone can figure it out in the next few hours while I am away, then that person gets a cookie (a virtual one).
Logged
Offline (Male) Josh @ Dreamland
Reply #1 Posted on: June 28, 2012, 11:44:19 AM

Prince of all Goldfish
Developer
Location: Pittsburgh, PA, USA
Joined: Feb 2008
Posts: 2949

View Profile Email
Kind of a neat problem. My first thought would be to represent the point in terms of four distances.
A*sqrt(sqr(x-x1) + sqr(y-y1)) = B*sqrt(sqr(x-x2) + sqr(y-y2)) = C*sqrt(sqr(x-x3) + sqr(y-y3)) = D*sqrt(sqr(x-x4) + sqr(y-y4)).

So to get the transformation, you'd use A=1 to solve for B, C, and D, then swap out the x1..x4,y1..y4 pairs and solve back for x,y. That part's a real pain in the ass.
Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire
Offline (Unknown gender) TheExDeus
Reply #2 Posted on: June 28, 2012, 01:02:42 PM

Developer
Joined: Apr 2008
Posts: 1872

View Profile
Quote
My first thought would be to represent the point in terms of four distances.
Ok, so the distances from the four corners of the quadrilateral. But wouldn't that mean that I have to recalculate A,B,C,D all the time? I will try something along those lines.

What's stupid is that I can't find the answer on the net, because I don't know how you would describe it. Its some kind of projection or interpolation problem...
Logged
Offline (Male) Josh @ Dreamland
Reply #3 Posted on: June 29, 2012, 01:55:58 PM

Prince of all Goldfish
Developer
Location: Pittsburgh, PA, USA
Joined: Feb 2008
Posts: 2949

View Profile Email
I was thinking the math would simplify. In my formula,
A*sqrt(sqr(x-x1) + sqr(y-y1)) = B*sqrt(sqr(x-x2) + sqr(y-y2)) = C*sqrt(sqr(x-x3) + sqr(y-y3)) = D*sqrt(sqr(x-x4) + sqr(y-y4))

x1=x4, x2=x3, y1=y2, y3 = y4. So we can rewrite it as this:
sqrt(sqr(x-x1) + sqr(y-y1)) = B*sqrt(sqr(x-x2) + sqr(y-y1)) = C*sqrt(sqr(x-x2) + sqr(y-y3)) = D*sqrt(sqr(x-x1) + sqr(y-y3))

But that's not really making the math any easier; we still have a thousand variables. So, use x1 = y1 = 0, and shift x2 and y3 appropriately (we'll shift the result back later):
sqrt(sqr(x) + sqr(y)) = B*sqrt(sqr(x-W) + sqr(y)) = C*sqrt(sqr(x-W) + sqr(y-H)) = D*sqrt(sqr(x) + sqr(y-H))

Square all terms:
sqr(x) + sqr(y) = B*B*(sqr(x-W) + sqr(y)) = C*C*(sqr(x-W) + sqr(y-H)) = D*D*(sqr(x) + sqr(y-H))

Looking kinder. Now, we treat W as 1 and H as 1. We can transform that later, too.
sqr(x) + sqr(y) = B*B*(sqr(x-1) + sqr(y)) = C*C*(sqr(x-1) + sqr(y-1)) = D*D*(sqr(x) + sqr(y-1))

Multiply everything out:
x*x + y*y = B*B*((x*x - 2*x - 1) + y*y) = C*C*((x*x - 2*x + 1) + (y*y - 2*y + 1)) = D*D*(x*x + (y*y - 2*y + 1))

More:
x*x + y*y = B*B*x*x + B*B*y*y - 2*B*B*x - B*B = C*C*x*x + C*C*y*y - 2*C*C*x - 2*C*C*y + 2*C*C = D*D*x*x + D*D*y*y - 2*D*D*y + D*D

Now subtract x*x and y*y from everything:
0 = (B*B-1)*x*x + (B*B-1)*y*y - 2*B*B*x - B*B
0 = (C*C-1)*x*x + (C*C-1)*y*y - 2*C*C*x - 2*C*C*y + 2*C*C
0 = (D*D-1)*x*x + (D*D-1)*y*y - 2*D*D*y + D*D

I'll revisit those later to figure out how to solve them.
Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire
Offline (Unknown gender) TheExDeus
Reply #4 Posted on: June 29, 2012, 03:20:04 PM

Developer
Joined: Apr 2008
Posts: 1872

View Profile
Here is how I did it:

Basically I need to get the distance from the sides to the point (which is computationally quite expensive), but it works. Now I am thinking if there is any better or faster way. Now I basically do this 4 times. The 640x480 could be anything, I just needed it for that size.

You can download an example exe here. When run, press 4 to get the final working version. If you can't run the executable, then I guess I can give the gmk.
Logged
Offline (Male) Josh @ Dreamland
Reply #5 Posted on: June 29, 2012, 10:21:59 PM

Prince of all Goldfish
Developer
Location: Pittsburgh, PA, USA
Joined: Feb 2008
Posts: 2949

View Profile Email
If I'm not mistaken, that measure's a little imprecise. It wouldn't really matter unless you had something like this:



Taking a distance from corners instead will fix that. You don't need to use the sqrt function, since all you are interested in is proportions.

Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire
Offline (Unknown gender) TheExDeus
Reply #6 Posted on: June 30, 2012, 06:12:35 AM

Developer
Joined: Apr 2008
Posts: 1872

View Profile
Quote
If I'm not mistaken, that measure's a little imprecise. It wouldn't really matter unless you had something like this
No, it still works then as well. Of course its "jittery" because then its so stretched out, that a few pixels in the quadrilateral moves the point in the rectangle a lot more. But its still how it should be. Of course in my case it wouldn't be in a shape like that, as I would have parallelograms and such.

Quote
Taking a distance from corners
I tried that, but not sure what you mean. Basically the exact same thing I do here, but the distances are from corners?

Quote
You don't need to use the sqrt function, since all you are interested in is proportions.
True. I will try to remake the whole thing in a script and optimize it on the way.

edit: Still don't get it. What ratio should I take? I can't take one distance from the corner and the distance from the opposite corner and just get ratio from them. But taking corner distance would be a lot faster, so if it is possible then I would love to figure this out. As I would not need to calculate intersection point of two lines four times.
« Last Edit: June 30, 2012, 06:27:48 AM by HaRRiKiRi » Logged
Pages: 1
  Print