1. Polygon coordinates transformation
- Posted by Tommy Carlier <tommy.carlier at pandora.be> Mar 18, 2004
- 366 views
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
- Posted by "Derek Parnell" <ddparnell at bigpond.com> Mar 18, 2004
- 342 views
----- 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
- Posted by Tommy Carlier <tommy.carlier at pandora.be> Mar 18, 2004
- 347 views
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
- Posted by "Juergen Luethje" <j.lue at gmx.de> 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. 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
- Posted by Tommy Carlier <tommy.carlier at pandora.be> Mar 18, 2004
- 345 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
6. Re: Polygon coordinates transformation
- Posted by Tommy Carlier <tommy.carlier at pandora.be> Mar 18, 2004
- 346 views
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
- Posted by "Juergen Luethje" <j.lue at gmx.de> Mar 18, 2004
- 354 views
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
- 353 views
--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
- Posted by jiri babor <jbabor at paradise.net.nz> Mar 19, 2004
- 356 views
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
- Posted by Tommy Carlier <tommy.carlier at pandora.be> Mar 19, 2004
- 363 views
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