View Question
Q: Backwards 2D transform algorithm using geometry, trigonometry, pseudocode ( No Answer,   0 Comments )
 Question
 Subject: Backwards 2D transform algorithm using geometry, trigonometry, pseudocode Category: Computers > Algorithms Asked by: purpleprogrammer-ga List Price: \$100.00 Posted: 09 Sep 2006 05:25 PDT Expires: 16 Sep 2006 19:04 PDT Question ID: 763631
 ```I have two points, [+1,0] and [0,+1]. These points will (both together) have two to-be-determined transforms applied to them, with no change of position: t1xscale, t1yscale, t1rotation, t2xscale, t2yscale, t2rotation. Both transforms are applied to both coordinates. All scale and rotation is about the origin of [0,0]. Create an algorithm, when given post-transform coordinates [x1, y1] and [x2, y2], determines the two transforms: t1xscale, t1yscale, t1rotation, t2xscale, t2yscale, t2rotation. If the two input coordinates were to be swapped, the two output coordinates should swap. I believe this can be solved with t1rotation fixed at any non-0 degree -- 45 degrees being most convenient, and one of the scales (such as t2xscale) fixed at 1. -------- Here it all is backwards -- using the given transforms (t1xscale, t1yscale, t1rotation, t2xscale, t2yscale, t2rotation) to convert points ([+1,0] or [0,+1]) to a transformed point ([x1, y1] and [x2, y2]). This is probably the best place to start solving the problem by reversing this algorithm. This is verbose for uniformity and understandibility; transform 1 could be significantly reduced. // Transform 1, point [0, +1] x1a = 0 * t1xscale // Scale y1a = +1 * t1yscale rtemp1a = atan2(y1a, x1a) + t1rotation // Get ang/distance, add rotation dtemp1a = sqrt(x1a^2 + y1a^2) x1b = cos(rtemp1a) * dtemp1a // Turn ang/distance back to coordinates. y1b = sin(rtemp1a) * dtemp1a // Transform 2 x1c = x1b * t2xscale y1c = y1b * t2yscale rtemp1b = atan2(y1c, x1c) + t2rotation dtemp1b = sqrt(x1c^2 + y1c^2) x1 = cos(rtemp1b) * dtemp1b y1 = sin(rtemp1b) * dtemp1b // Transform 1, point [+1, 0] x2a = +1 * t1xscale y2a = 0 * t1yscale rtemp2a = atan2(y2a, x2a) + t1rotation dtemp2a = sqrt(x2a^2 + y2a^2) x2b = cos(rtemp2a) * dtemp2a y2b = sin(rtemp2a) * dtemp2a // Transform 2 x2c = x2b * t2xscale y2c = y2b * t2yscale rtemp2b = atan2(y2c, x2c) + t2rotation dtemp2b = sqrt(x2c^2 + y2c^2) x2 = cos(rtemp2b) * dtemp2b y2 = sin(rtemp2b) * dtemp2b --------- Your function will be given x1, y1, x2, y2, and return answers for t1xscale, t1yscale, t1rotation, t2xscale, t2yscale, t2rotation. The answer is proven 'correct' if and only if the above algorithm, given your function's answers, returns your function's inputs. The algorithm should avoid extremes; if the input points are "close to" the output points, the scale values should be near 100% -- (rather than, for example, 10% or 1000%!) For speed, I would prefer an optimized algorithm; minimal calls to exponent, sqrt(), atan2(), cos() and sin(). I do not need to understand the reasoning behind the math, but the format of the answer should be similar to the pseudocode I've provided -- with if/loop statements if necessary. This has no bearing on request, but if you're curious, this is to take a textured 2D right triangle (points [0,0], [+1, 0], [0, +1]) and transform it into an arbitrary triangle. --------- Here is where I am in the puzzle so far... The following half-done algorithm requres that y1 and y2 are equal (paralell with the y axis), but I can "fix that" by rotating the input coordinates about [0,0] until y1=y2 (that would be atan2(y2-y1, x2-x1)), and then subtracting that rotation from the resulting t2rotation. A great deal of this was magical brain power and trial-and-error, so I don't think I can explain it well. The function labeled "f???" is the one component that I have not yet determined; I have "guessed" at a polynomial for it, and it works well, but it is not accurate enough. ** In this implementation, I do know that t2yscale is some ** function of the angle from [0,0] to the half-way point ** between the two input points. ** The /2 here is to get the half-way point; ** -- it's for understandability only, since it doesn't ** affect the output of atan2. t2yscale = f???(atan2((y1+y2)/2, (x1+x2)/2)) ** These two are fixed at 100% and 45 degrees t2xscale = 1 t1rotation = PI/4 ** hypotenuse length hyplen = ((x1-x2)^2 + (y1-y2)^2)^0.5 ** ("scale length"?) scalelen = sqrt(t2xscale^2 + t2yscale^2); t1xscale = hyplen/scalelen; ** ("aspect angle"?) t2rotation = atan2(t2yscale, t2xscale); t1yscale = y1 * scalelen / t2yscale;``` Clarification of Question by purpleprogrammer-ga on 09 Sep 2006 08:48 PDT ```I've just discovered that the half-done code I provided -- my "work in progress" for this algorithm isn't perfect. It is probably off by 45 deges, and maybe flipped on the x or y axis. It's a good rough idea, but will require some tweaking. Regardless, I've rearranged and reduced the formula a bit, and come up with this: (Basic formulas for the algorithm to come) t = sqrt(2)/2 rotatex(x,y,r) = cos(atan(y/x) + r) * sqrt(y^2+x^2) rotatey(x,y,r) = sin(atan(y/x) + r) * sqrt(y^2+x^2) Here is the forward transform again -- Identitcal to the original as far as results, but optimized. x1c = -t * t1yscale y1c = t * t1yscale * t2yscale x1 = rotatex(x1c, y1c, t2rotation) y1 = rotatey(x1c, y1c, t2rotation) x2c = t * t1xscale y2c = t * t1xscale * t2yscale x2 = rotatex(x2c, y2c, t2rotation) y2 = rotatey(x2c, y2c, t2rotation) Rather than reversing the formula by resorting to asin, acos, tan, etc, you can reverse a rotation by using a negative rotation; so here is the un-transform, half solved: t * t1xscale * t2yscale = rotatey(x2, y2, -t2rotation) t * t1xscale = rotatex(x2, y2, -t2rotation) t * t1yscale * t2yscale = rotatey(x1, y1, -t2rotation) -t * t1yscale = rotatex(x1, y1, -t2rotation) I don't know where to take it from here -- to solve for the remaining unsolved variables: t1xscale, t1yscale, t2yscale, t2rotation. (t2xscale = 1, t2rotation = 45 degrees) Good luck!``` Clarification of Question by purpleprogrammer-ga on 16 Sep 2006 19:03 PDT ```Ha! Solved it! SOLUTION: t2xscale = 1 t1rotation = PI/4 t = sqrt(2)/2 a1 = atan2(y1,x1) a2 = atan2(y2,x2) t2rotation = (a1 + a2) / 2 d1 = sqrt(y1*y1 + x1*x1) rx1 = cos(a1 - t2rotation) * d1 t1yscale = -rx1/t t2yscale = -(sin(a1 - t2rotation) * d1)/rx1 t1xscale = cos(a2 - t2rotation) * sqrt(y2*y2 + x2*x2)/t```