1. Polygon coordinates transformation
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.
Let's see if there are any math geniuses in the Euphoria-community!
--
Tommy Carlier
tommy online: http://users.pandora.be/tommycarlier
2. Re: Polygon coordinates transformation
----- Original Message -----
From: "Tommy Carlier" <tommy.carlier at pandora.be>
To: "Euphoria Mailing List" <EUforum at topica.com>
Subject: Polygon coordinates transformation
>
>
> 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
--
Derek
3. Re: Polygon coordinates transformation
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?
--
Tommy Carlier
tommy online: http://users.pandora.be/tommycarlier
4. Re: Polygon coordinates transformation
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.
I don't think that this is the case. I think in your 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
the variables u? (belonging to the source polygon) are known, but the
variables x? and y? (belonging to the destination polygon) are *not*
known. If you knew the values of the variables x? and y?, you were
already done, and it wouldn't be necessary to do any calculation ... 
And what about the variables a, b, and c? I'm not sure whether or not
you know them, because I don't know their meaning.
Maybe, because of my limited knowledge of the English language, I didn't
understand at all, what exactly the problem is.
Assumption:
You want to be able to change the *size* of any polygon with 4 corners,
without changing its shape, i.e. without altering any of its *angles*.
Is this true?
If so, then I think a different set of equations must be solved, in
order to get the appropriate formula. I don't want to make calculations
based on a guess, so please tell me, whether this assumption is correct.
> 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?
Regards,
Juergen
PS: Tomorrow I'll leave the town for some days, so there might be a
delay until I can write my next post.
5. Re: Polygon coordinates transformation
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
6. Re: Polygon coordinates transformation
Juergen wrote:
> I don't think that this is the case. I think in your 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
>
> the variables u? (belonging to the source polygon) are known, but the
> variables x? and y? (belonging to the destination polygon) are *not*
> known. If you knew the values of the variables x? and y?, you were
> already done, and it wouldn't be necessary to do any calculation ...
> And what about the variables a, b, and c? I'm not sure whether or not
> you know them, because I don't know their meaning.
(x?, y?) are the 4 coordinates of the corners of the polygon, so those are
known. I'm trying to find a, b and c.
> Assumption:
> You want to be able to change the *size* of any polygon with 4 corners,
> without changing its shape, i.e. without altering any of its *angles*.
> Is this true?
No, it's not. I have 2 polygons that don't need to be of the same shape.
Polygon 1 has coordinates {{x1, y1}, {x2, y2}, {x3, y3}, {x4, y4}} and
polygon 2 has coordinates {{u1, v1}, {u2, v2}, {u3, v3}, {u3, v3}}. If I
take a random point that is part of polygon 1, I need to find the
corresponding point in polygon 2.
--
Tommy Carlier
tommy online: http://users.pandora.be/tommycarlier
7. Re: Polygon coordinates transformation
Tommy wrote:
> Juergen wrote:
>> I don't think that this is the case. I think in your 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
>>
>> the variables u? (belonging to the source polygon) are known, but the
>> variables x? and y? (belonging to the destination polygon) are *not*
>> known. If you knew the values of the variables x? and y?, you were
>> already done, and it wouldn't be necessary to do any calculation ...
>> And what about the variables a, b, and c? I'm not sure whether or not
>> you know them, because I don't know their meaning.
>
> (x?, y?) are the 4 coordinates of the corners of the polygon, so those are
> known. I'm trying to find a, b and c.
>
>> Assumption:
>> You want to be able to change the *size* of any polygon with 4 corners,
>> without changing its shape, i.e. without altering any of its *angles*.
>> Is this true?
>
> No, it's not.
Oops. Then I misunderstood your original post, sorry.
> I have 2 polygons that don't need to be of the same shape.
> Polygon 1 has coordinates {{x1, y1}, {x2, y2}, {x3, y3}, {x4, y4}} and
> polygon 2 has coordinates {{u1, v1}, {u2, v2}, {u3, v3}, {u3, v3}}. If I
> take a random point that is part of polygon 1, I need to find the
> corresponding point in polygon 2.
It sounds to me, as if this problem can't be solved, because it's not
defined exactly. In your original post, you wrote:
| I need to find a formula that transforms a coordinate {x, y} inside
| polygon_destination to a coordinate {u, v} inside polygon_source.
But you didn't specify, what kind of transformation you want to do.
Also, if you have two quadrilaterals with different shapes,
say a trapezoid ( http://mathworld.wolfram.com/Trapezoid.html )
and a kite ( http://mathworld.wolfram.com/Kite.html ),
and then you take a random point of the trapezoid, what do you mean
by "corresponding point" in the kite?
Regards,
Juergen
8. Re: Polygon coordinates transformation
- Posted by kbochert at copper.net
Mar 18, 2004
--Alt-Boundary-26309.75454278
Content-description: Mail message body
On 18 Mar 2004 at 21:36, Juergen Luethje wrote:
>
>
> Tommy wrote:
>
> > Juergen wrote:
> >> I don't think that this is the case. I think in your 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
> >>
>
There are two equations, one for x and one for y.
Each has 4 constants.
See:
http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/OWENS/LECT5/node5.htm
l
under 'tie points'
Useful google terms: matrix transformations "tie points" distortion
Karl Bochert
--Alt-Boundary-26309.75454278
Content-type: text/html; charset=US-ASCII
Content-transfer-encoding: 7BIT
Content-description: Mail message body
<?xml version="1.0" ?><html>
<head>
<title></title>
</head>
<body>
<div align="left"><font face="Arial"><span style="font-size:10pt">On 18 Mar 2004
at 21:36, Juergen Luethje wrote:</span></font></div>
<div align="left"><br/>
</div>
<div align="left"><font face="Arial" color="#7f0000"><span
style="font-size:10pt">> ============ The Euphoria Mailing List ============
</span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span
style="font-size:10pt">> </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span
style="font-size:10pt">> </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span
style="font-size:10pt">> Tommy wrote:</span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span
style="font-size:10pt">> </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span
style="font-size:10pt">> > Juergen wrote:</span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span
style="font-size:10pt">> >> I don't think that this is the case. I think
in your equations:</span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span
style="font-size:10pt">> >> x1 * a + y1 * b + c =
u1</span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span
style="font-size:10pt">> >> x2 * a + y2 * b + c =
u2</span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span
style="font-size:10pt">> >> x3 * a + y3 * b + c =
u3</span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span
style="font-size:10pt">> >> x4 * a + y4 * b + c =
u4</span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span
style="font-size:10pt">> >></span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span
style="font-size:10pt">> </span></font></div>
<div align="left"><font face="Arial"><span style="font-size:10pt">There are two
equations, one for x and one for y.</span></font></div>
<div align="left"><font face="Arial"><span style="font-size:10pt">Each has 4
constants.</span></font></div>
<div align="left"><font face="Arial"><span
style="font-size:10pt">See:</span></font></div>
<div align="left"><font face="Arial"><span style="font-size:10pt">
</span></font></div>
<div align="left"><font face="Arial"><span
style="font-size:10pt">http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/OWENS/LECT5/node5.html</span></font></div>
<div align="left"><br/></div>
<div align="left"><font face="Arial"><span style="font-size:10pt">under 'tie
points'</span></font></div>
<div align="left"><br/></div>
<div align="left"><font face="Arial"><span style="font-size:10pt">Useful google
terms: matrix transformations "tie points"
distortion</span></font></div>
<div align="left"><br/>
</div>
<div align="left"><font face="Arial"><span style="font-size:10pt">Karl
Bochert</span></font></div>
<div align="left"></div>
--Alt-Boundary-26309.75454278--
9. Re: Polygon coordinates transformation
Tommy,
back in 1998 I proposed *fast* texture mapping routines that transform a
given polygon to another polygon. The target polygon has only two
restrictions: (1) it has to have the same number of vertices as the source
polygon, and (2) it has to be 'horizontally' convex (but, of course, both
these conditions can be circumvented with a tiny bit of effort...).
I realize my transform (essentially mapping every point on a horizontal line
in the target to a point in the source) is not exactly what you were asking
for, but it can be perhaps adapted for your purposes.
jiri
-- map.e : texture mapping
function space(integer n,integer y,integer y2)
sequence s
integer d,dy,e,f,m
if n=1 then return {y} end if
if y=y2 then return repeat(y,n) end if
s = repeat(y,n)
s[n] = y2
dy = 1
d = 2*(y2-y)
m = n-1
f = 2*m
e = -m
if y>y2 then
dy = -1
d = -d
end if
for i = 2 to m do
e += d
while e>=0 do
e -= f
y += dy
end while
s[i] = y
end for
return s
end function
global procedure map_image(
sequence tex, -- texture bitmap, 2-d sequence
sequence p, -- vertices in texture: {{u1,v1},..{un,vn}}
sequence s -- polygon to be shown: {{x1,y1},..{xn,yn}}
)
-- texture mapping, pixel mode:
-- map polygon p in image (texture) tex into polygon s
-- polygon s must be convex : any *horizontal* line has no
-- more than *two* intersections with sides of such polygon
sequence u,uu,v,vv,x,xx
integer i1,i2,k,len,n,rows,u1,u2,v1,v2,x1,x2,y,y1,y2,yi,ymax,ymin
s=floor(s) -- integers only
n=length(s) -- number of sides
-- get y extremes
ymin=s[1][2]
ymax=ymin
for i=2 to n do
if s[i][2]<ymin then ymin=s[i][2] end if
if s[i][2]>ymax then ymax=s[i][2] end if
end for
-- set up edge arrays
rows=ymax-ymin+1
xx=repeat({},rows) -- hold x-values
uu=xx -- texture horizontal index
vv=xx -- texture vertical index
-- init & loop
x2=s[n][1]
y2=s[n][2]-ymin+1
u2=p[n][1]
v2=p[n][2]
for i=1 to n do
x1=x2
x2=s[i][1]
y1=y2
y2=s[i][2]-ymin+1
u1=u2
u2=p[i][1]
v1=v2
v2=p[i][2]
if y1=y2 then -- horizontal side
xx[y1] &= x1
uu[y1] &= u1
vv[y1] &= v1
else -- non-horizontal side
if y1>y2 then
len=y1-y2+1
yi=-1
else
len=y2-y1+1
yi=1
end if
x=space(len,x1,x2)
u=space(len,u1,u2)
v=space(len,v1,v2)
k=1
for j=y1 to y2-yi by yi do
xx[j] &= x[k]
uu[j] &= u[k]
vv[j] &= v[k]
k+=1
end for
end if
end for
-- display
y=ymin
if length(xx[1])=1 then
pixel(tex[vv[1][1]][uu[1][1]],{xx[1][1],y})
y+=1
i1=2
else
i1=1
end if
if length(xx[rows])=1 then
i2=rows-1
pixel(tex[vv[rows][1]][uu[rows][1]],{xx[rows][1],ymax})
else
i2=rows
end if
for i=i1 to i2 do
x=xx[i]
x1=x[1]
x2=x[2]
if x1<x2 then
len=x2-x1+1
u=space(len,uu[i][1],uu[i][2])
v=space(len,vv[i][1],vv[i][2])
else
len=x1-x2+1
u=space(len,uu[i][2],uu[i][1])
v=space(len,vv[i][2],vv[i][1])
x1=x2
end if
x=repeat(0,len)
for j=1 to len do
x[j]=tex[v[j]][u[j]]
end for
pixel(x,{x1,y})
y+=1
end for
end procedure -- map_image
global procedure vmap_image(
atom a, -- screen address
integer w, -- screen width
sequence tex, -- texture bitmap, 2-d sequence
sequence p, -- vertices in texture: {{u1,v1},..{un,vn}}
sequence s -- polygon to be shown: {{x1,y1},..{xn,yn}}
)
-- texture mapping for virtual screens:
-- map polygon p in image (texture) tex into polygon s
-- polygon s must be convex : any *horizontal* line has no
-- more than *two* intersections with sides of such polygon
sequence u,uu,v,vv,x,xx
integer i1,i2,k,len,n,rows,u1,u2,v1,v2,x1,x2,y1,y2,yi,ymax,ymin
s=floor(s) -- integers only
n=length(s) -- number of sides
-- get y extremes
ymin=s[1][2]
ymax=ymin
for i=2 to n do
if s[i][2]<ymin then ymin=s[i][2] end if
if s[i][2]>ymax then ymax=s[i][2] end if
end for
-- set up edge arrays
rows=ymax-ymin+1
xx=repeat({},rows) -- hold x-values
uu=xx -- texture horizontal index
vv=xx -- texture vertical index
-- init & loop
x2=s[n][1]
y2=s[n][2]-ymin+1
u2=p[n][1]
v2=p[n][2]
for i=1 to n do
x1=x2
x2=s[i][1]
y1=y2
y2=s[i][2]-ymin+1
u1=u2
u2=p[i][1]
v1=v2
v2=p[i][2]
if y1=y2 then -- horizontal side
xx[y1] &= x1
uu[y1] &= u1
vv[y1] &= v1
else -- non-horizontal side
if y1>y2 then
len=y1-y2+1
yi=-1
else
len=y2-y1+1
yi=1
end if
x=space(len,x1,x2)
u=space(len,u1,u2)
v=space(len,v1,v2)
k=1
for j=y1 to y2-yi by yi do
xx[j] &= x[k]
uu[j] &= u[k]
vv[j] &= v[k]
k+=1
end for
end if
end for
-- display
a+=w*ymin
if length(xx[1])=1 then
poke(a+xx[1][1],tex[vv[1][1]][uu[1][1]])
a+=w
i1=2
else
i1=1
end if
if length(xx[rows])=1 then
i2=rows-1
else
i2=rows
end if
for i=i1 to i2 do
x=xx[i]
x1=x[1]
x2=x[2]
if x1<x2 then
len=x2-x1+1
u=space(len,uu[i][1],uu[i][2])
v=space(len,vv[i][1],vv[i][2])
else
len=x1-x2+1
u=space(len,uu[i][2],uu[i][1])
v=space(len,vv[i][2],vv[i][1])
x1=x2
end if
x=repeat(0,len)
for j=1 to len do
x[j]=tex[v[j]][u[j]]
end for
poke(a+x1,x)
a+=w
end for
if i2<rows then
poke(a+xx[rows][1],tex[vv[rows][1]][uu[rows][1]])
end if
end procedure -- vmap_image
10. Re: Polygon coordinates transformation
Jiri wrote:
> Tommy,
>
> back in 1998 I proposed *fast* texture mapping routines that transform a
> given polygon to another polygon. The target polygon has only two
> restrictions: (1) it has to have the same number of vertices as the
> source
> polygon, and (2) it has to be 'horizontally' convex (but, of course, both
> these conditions can be circumvented with a tiny bit of effort...).
>
> I realize my transform (essentially mapping every point on a horizontal
> line
> in the target to a point in the source) is not exactly what you were
> asking
> for, but it can be perhaps adapted for your purposes.
>
> jiri
Jiri, thanks a lot. That is exactly what I was trying to achieve. I had
already made it work for triangles, and I was now looking for a way to
transform quadrangles. Your method can take ANY convex polygon, which is
even better. I'll implement it in Win32Dib as soon as possible. I'll just
have to add clipping, because I'm copying memory and your method doesn't
check if the pixels are within their boundaries.
--
Tommy Carlier
tommy online: http://users.pandora.be/tommycarlier
