OpenEuphoria

Re: Polygon coordinates transformation

• Posted by Tommy Carlier <tommy.carlier at pandora.be> Mar 18, 2004
• 346 views

Tommy wrote:
> Derek wrote:
>> Tommy wrote:
>>> I want to add a routine to Win32Dib, that can draw a part of a bitmap 
>>> on
>>> another bitmap, but stretched to a polygon. To do this, I need to find 
>>> an
>>> algorithm that transforms coordinates from 1 polygon to another one.
>>>
>>> I have 2 polygons with each 4 points:
>>> polygon_source = {{u1, v1}, {u2, v2}, {u3, v3}, {u4, v4}}
>>> polygon_destination = {{x1, y1}, {x2, y2}, {x3, y3}, {x4, y4}}
>>>
>>> I need to find a formula that transforms a coordinate {x, y} inside
>>> polygon_destination to a coordinate {u, v} inside polygon_source.
>>>
>>> I've looked for tutorials on texture mapping, but didn't find any 
>>> non-3D
>>> transformation formula. I've looked for methods to solve linear 
>>> equations, but didn't find the right method.
>>>
>>> Can anyone solve the following set of equations?
>>>
>>> x1 * a + y1 * b + c = u1
>>> x2 * a + y2 * b + c = u2
>>> x3 * a + y3 * b + c = u3
>>> x4 * a + y4 * b + c = u4
>>>
>>> a, b and c are the unknown variables. u?, x? and y? are known values. 
>>> If these equations can be solved, I can transform coordinates with the 
>>> 2
>>> simple functions:
>>>
>>> u = x * a + y * b + c
>>> v = x * d + y * e + f   -- d, e and f can be found with the same set of
>>> equations, but with v? instead of u?
>>>
>>> This finds the coordinate {u, v} in polygon_source that represent the
>>> coordinate {x, y} in polygon_destination.
>>
>> I'm very tired so this is probably wrong...
>>
>> b = (x1u2 - x1u3 + x2u3 - x2u1 + x3u1 - x3u2) / (x1y2 - x1y3 + x3y3 - 
>> x2y1 + x3y1 - x3y2)
>> a = (u1 - u2 - b(y1 -y2)) / (x1 - x2)
>> c = u1 - ax1 - by1
>
> Thanks for the effort, Derek. I've also tried it manually, and your 
> solution is one of the many solutions I came up with. The problem is: 
> there are 3 unknowns, but 4 equations. Your solution doesn't match the 
> 4th equation (no x4, y4 or u4 are present). I tried to solve this by 
> making 4 unknowns to match the 4 equations like this: 'x * a + y * b + c 
> + d = u' (extra unknown 'd'), but it didn't work.
>
> I just came up with something: couldn't I split the 4-cornered polygon 
> into 2 triangles...
> Triangle 1: {{x1, y1}, {x2, y2}, {x3, y3}}
> Triangle 2: {{x1, y1}, {x3, y3}, {x4, y4}}
> ...and find a, b and c for each triangle with Derek's solution?

I tried splitting the quadrangle into triangles, and rendering those, and 
that didn't work like it should: each triangle renders like it should, but 
when rendering a quadrangle, the image is a bit distorted: the 
transformation parameters only look at 3 coordinates, and should depend on 
all 4 coordinates.

Derek, your formula is partially right, but doesn't work when x1 equals 
x2: a = ... / (x1 - x2). I solved it with matrix maths and found the 
following formulas:

det = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)
if det = 0 then return end if

a = (u1 * (y2 - y3) + u2 * (y3 - y1) + u3 * (y1 - y2)) / det
b = (x1 * (u2 - u3) + x2 * (u3 - u1) + x3 * (u1 - u2)) / det
c = (x1 * (y2 * u3 - y3 * u2) + x2 * (y3 * u1 - y1 * u3) + x3 * (y1 * u2 - 
y2 * u1)) / det

-- 

Tommy Carlier
tommy online: http://users.pandora.be/tommycarlier