1

Summary: Is there a name for the technique I describe below?

In this question I described a situation where I have four non-axis-aligned 2D input points mapping to output vectors, and a desire to map an arbitrary input point to a new output vector.

(-19,-7) -> (-150,-100)
( 10,-8) -> ( 150,-100)
(-11, 4) -> (-150, 100)
(  9, 7) -> ( 150, 100)
(-4.2,1) -> (  ??,  ??)

                               

Based on one answer I came up with my own algorithm, illustrated above as the green and orange calculations. See the answer for details, but in short: find the X intercept on the top and bottom lines, lerp the output values to those "north"/"south" locations, and then lerp between those outputs based on where the input point is on the line.

Comments on my answer indicate that what I'm doing cannot be called "bilinear interpolation". I believe that this is because I'm calculating different percentages for the top and bottom edges, and the way that I am doing this may cause some input points within the quad to result in output values outside the min/max of the corner output points.

  • For example an input of (-19,0) in my scheme results in a point that is -40% along the bottom edge, and thus results in an output value of ~(-236,43), far less than the minX of -150.

If it's not "bilinear interpolation", what is this algorithm? And, if you'll permit a secondary question, how would you use bilinear interpolation on a non-parallelogram of inputs as I have here? Is that even possible?

Pretty visual test of my algorithm can be found on my website.

Community
  • 1
  • 1
Phrogz
  • 296,393
  • 112
  • 651
  • 745
  • 1
    If the goal is to map the trapezoid to a rectangle, then your algorithms distorts the image, due to using a perfectly vertical line during the intercept stage. This is clearly demonstrated if the arbitrary input is... (-15,-6) say. That's clearly inside the trapezoid, but I'm uncertain if your algorithm would put it inside of the rectangle. – Mooing Duck Jun 03 '14 at 16:29
  • I would probably take the distances from the point to each of the corners, and use those ratios, though it's significantly more math intensive. – Mooing Duck Jun 03 '14 at 16:30
  • Thank you @MooingDuck, that helped a lot. I realize now that given that I have both an input and an output quad, what I really want to do is perform [inverse bilinear interpolation](http://stackoverflow.com/questions/808441/inverse-bilinear-interpolation) on the input quad to find the UV coordinates for the input point, and then perform normal bilinear interpolation on the output quad (which in this case is a simple rectangle) using those UV coordinates. – Phrogz Jun 03 '14 at 16:36

2 Answers2

2

I dont know if there is a name for this kind of algorithm but what you seem to be trying is to reverse map, the coordinates of a 4 point polygon to a rectangle.. something like that is used on this code http://www.vcskicks.com/image-distortion.php and if you you want a better explanation of out is works you can find it here http://ryoushin.com/cmerighi/en-US/2006-09-30_21/Quadrilateral_Distortion_Algorithm. But bare in mind that these geometric algorithms are slow, and also dont work with concave shapes.. (you may have also noticed that on your test)..

that is why I developed a different tecnique http://www.codeproject.com/Articles/247214/Quadrilateral-Distortion that is faster and dosent break on concave polygons..

But if the effect you are trying to acheive is something like your sample.. creating a gradiente from given points.. probably there are more simple and efficiente ways of doing it.. than point maping.. maybe you can just enumerate all points in the canvas and chose its color depending on the distance of "anchor" points.. I will probably be faster.. and wont have those concave glitches..

CaldasGSM
  • 3,032
  • 16
  • 26
1

Welll. It would technically be reasonable to call this a variant of bilinear interpolation, one in which each top endpoint is first extrapolated along the top line to line up along the X axis with the corresponding bottom point. That is, first you're turning your arbitrary quadrilateral into a trapezoid, and then you're doing bilinear interpolation on that trapezoid.

It's not likely to produce useful results in the general case.

As for how you'd use bilinear interpolation, it basically comes down to solving a system of equations. There's some (u,v) pair such that if you perform bilinear interpolation with them, you get your input coordinates. You find what that pair is, and then you use it to produce your output value.

Sneftel
  • 40,271
  • 12
  • 71
  • 104