Re: Draw & fill regular polygon?
"Derek Burnheim" <[email protected]> Thu, 11 Aug 2011 17:01:16 +1000
| Newsgroups | gmane.games.devel.algorithms |
|---|---|
| Message-ID | <[email protected]> |
This is a multipart message in MIME format. --===============0160816532929508665== Content-Type: multipart/alternative; boundary="----=_NextPart_000_0010_01CC5848.4A145D80" Content-Language: en-au This is a multipart message in MIME format. ------=_NextPart_000_0010_01CC5848.4A145D80 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Michael Abrash's Mode-X articles in DDJ and Chris Hecker's Game Developer articles on perspective correct texture mapping should be required reading for anybody interested in this kind of thing. My Google-fu failed to turn up Abrash's articles but it sounds like they were reprinted in his Graphics Programming Black Book special edition. Chris Hecker's series of articles on perspective texture mapping can be found on his website: http://chrishecker.com/Miscellaneous_Technical_Articles#Perspective_Texture_ Mapping Cheers Derek From: Martin Gladnishki [mailto:[email protected]] Sent: Thursday, 11 August 2011 4:05 PM To: Game Development Algorithms Subject: Re: [Algorithms] Draw & fill regular polygon? There are also a number of line rasterizing algorithms that do 2, even 3 pixels per iteration, i.e. with them you will be able to fill the arrays faster. Lookup for double-step rasterizing algorithms. Also, in my experience the extrema arrays are not needed: for convex polygons there are only two active edges at a time, therefore you just need to traverse the poly in clockwise and anti-clockwise order to switch the active edges until they meet at the maximum Y coordinate. Hope that helps further. Cheers, Martin On Wed, Aug 10, 2011 at 6:29 PM, Graham Rhodes ARA/SED <[email protected]> wrote: Some helpful Google search terms are "polygon rasterization" and "polygon scan conversion." Someone else mentioned the Foley/van Dam book/et al. book, which is a good reference that describes the classic algorithm. The book Graphics Gems I also has a discussion, though it is brief. You can also find this stuff online, for free. For example, two sets of lecture slides from University of Virginia that look good: http://www.cs.virginia.edu/~gfx/courses/2004/Intro.Fall.04/handouts/11-polys can.pdf <http://www.cs.virginia.edu/%7Egfx/courses/2004/Intro.Fall.04/handouts/11-po lyscan.pdf> www.cs.virginia.edu/~asb/teaching/cs445-fall06/slides/09-rasterization.ppt <http://www.cs.virginia.edu/%7Easb/teaching/cs445-fall06/slides/09-rasteriza tion.ppt> I even found this YouTube video: http://www.youtube.com/watch?v=TNbkX5bYrtE Graham -----Original Message----- From: Joel B [mailto:[email protected]] Sent: Wednesday, August 10, 2011 7:49 AM To: Game Development Algorithms Subject: [Algorithms] Draw & fill regular polygon? I should know how to do this, but i don't. I only have the ability in my system to draw lines (x1,y1,x2,y2)' to a bitmap, or write to the bitmap as a byte array. Can someone tell me the stepwise procedure to draw a polygon of n sides and then fill it? Having trouble finding anything online that doesn't use pre-existing primitives or libraries. Thanks, Joel Sent from my iPhone ---------------------------------------------------------------------------- -- uberSVN's rich system and user administration capabilities and model configuration take the hassle out of deploying and managing Subversion and the tools developers use with it. Learn more about uberSVN and get a free download at: http://p.sf.net/sfu/wandisco-dev2dev _______________________________________________ GDAlgorithms-list mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list ---------------------------------------------------------------------------- -- uberSVN's rich system and user administration capabilities and model configuration take the hassle out of deploying and managing Subversion and the tools developers use with it. Learn more about uberSVN and get a free download at: http://p.sf.net/sfu/wandisco-dev2dev _______________________________________________ GDAlgorithms-list mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list ------=_NextPart_000_0010_01CC5848.4A145D80 Content-Type: text/html; charset="us-ascii" Content-Transfer-Encoding: quoted-printable <html xmlns:v=3D"urn:schemas-microsoft-com:vml" = xmlns:o=3D"urn:schemas-microsoft-com:office:office" = xmlns:w=3D"urn:schemas-microsoft-com:office:word" = xmlns:m=3D"http://schemas.microsoft.com/office/2004/12/omml" = xmlns=3D"http://www.w3.org/TR/REC-html40"><head><META = HTTP-EQUIV=3D"Content-Type" CONTENT=3D"text/html; = charset=3Dus-ascii"><meta name=3DGenerator content=3D"Microsoft Word 14 = (filtered medium)"><style><!-- /* Font Definitions */ @font-face {font-family:Calibri; panose-1:2 15 5 2 2 2 4 3 2 4;} @font-face {font-family:Tahoma; panose-1:2 11 6 4 3 5 4 4 2 4;} /* Style Definitions */ p.MsoNormal, li.MsoNormal, div.MsoNormal {margin:0cm; margin-bottom:.0001pt; font-size:12.0pt; font-family:"Times New Roman","serif";} a:link, span.MsoHyperlink {mso-style-priority:99; color:blue; text-decoration:underline;} a:visited, span.MsoHyperlinkFollowed {mso-style-priority:99; color:purple; text-decoration:underline;} p.MsoAcetate, li.MsoAcetate, div.MsoAcetate {mso-style-priority:99; mso-style-link:"Balloon Text Char"; margin:0cm; margin-bottom:.0001pt; font-size:8.0pt; font-family:"Tahoma","sans-serif";} span.EmailStyle17 {mso-style-type:personal-reply; font-family:"Calibri","sans-serif"; color:#1F497D;} span.BalloonTextChar {mso-style-name:"Balloon Text Char"; mso-style-priority:99; mso-style-link:"Balloon Text"; font-family:"Tahoma","sans-serif"; mso-fareast-language:EN-AU;} .MsoChpDefault {mso-style-type:export-only; font-family:"Calibri","sans-serif"; mso-fareast-language:EN-US;} @page WordSection1 {size:612.0pt 792.0pt; margin:72.0pt 72.0pt 72.0pt 72.0pt;} div.WordSection1 {page:WordSection1;} --></style><!--[if gte mso 9]><xml> <o:shapedefaults v:ext=3D"edit" spidmax=3D"1026" /> </xml><![endif]--><!--[if gte mso 9]><xml> <o:shapelayout v:ext=3D"edit"> <o:idmap v:ext=3D"edit" data=3D"1" /> </o:shapelayout></xml><![endif]--></head><body lang=3DEN-AU link=3Dblue = vlink=3Dpurple><div class=3DWordSection1><p class=3DMsoNormal><span = style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497= D'>Michael Abrash’s Mode-X articles in DDJ and Chris = Hecker’s Game Developer articles on perspective correct texture = mapping should be required reading for anybody interested in this kind = of thing.<o:p></o:p></span></p><p class=3DMsoNormal><span = style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497= D'><o:p> </o:p></span></p><p class=3DMsoNormal><span = style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497= D'>My Google-fu failed to turn up Abrash’s articles but it sounds = like they were reprinted in his Graphics Programming Black Book special = edition.<o:p></o:p></span></p><p class=3DMsoNormal><span = style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497= D'><o:p> </o:p></span></p><p class=3DMsoNormal><span = style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497= D'>Chris Hecker’s series of articles on perspective texture = mapping can be found on his website: <a = href=3D"http://chrishecker.com/Miscellaneous_Technical_Articles#Perspecti= ve_Texture_Mapping">http://chrishecker.com/Miscellaneous_Technical_Articl= es#Perspective_Texture_Mapping</a><o:p></o:p></span></p><p = class=3DMsoNormal><span = style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497= D'><o:p> </o:p></span></p><p class=3DMsoNormal><span = style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497= D'>Cheers<o:p></o:p></span></p><p class=3DMsoNormal><span = style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497= D'>Derek<o:p></o:p></span></p><p class=3DMsoNormal><span = style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497= D'><o:p> </o:p></span></p><p class=3DMsoNormal><span = style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497= D'><o:p> </o:p></span></p><p class=3DMsoNormal><b><span = lang=3DEN-US = style=3D'font-size:10.0pt;font-family:"Tahoma","sans-serif"'>From:</span>= </b><span lang=3DEN-US = style=3D'font-size:10.0pt;font-family:"Tahoma","sans-serif"'> Martin = Gladnishki [mailto:[email protected]] <br><b>Sent:</b> Thursday, 11 = August 2011 4:05 PM<br><b>To:</b> Game Development = Algorithms<br><b>Subject:</b> Re: [Algorithms] Draw & fill regular = polygon?<o:p></o:p></span></p><p = class=3DMsoNormal><o:p> </o:p></p><p class=3DMsoNormal = style=3D'margin-bottom:12.0pt'>There are also a number of line = rasterizing algorithms that do 2, even 3 pixels per iteration, i.e. with = them you will be able to fill the arrays faster. Lookup for double-step = rasterizing algorithms.<br><br>Also, in my experience the extrema arrays = are not needed: for convex polygons there are only two active edges at a = time, therefore you just need to traverse the poly in clockwise and = anti-clockwise order to switch the active edges until they meet at the = maximum Y coordinate.<br><br>Hope that helps = further.<br><br>Cheers,<br>Martin<o:p></o:p></p><div><p = class=3DMsoNormal>On Wed, Aug 10, 2011 at 6:29 PM, Graham Rhodes ARA/SED = <<a href=3D"mailto:[email protected]">[email protected]</a>> = wrote:<o:p></o:p></p><p class=3DMsoNormal>Some helpful Google search = terms are "polygon rasterization" and "polygon scan = conversion." Someone else mentioned the Foley/van Dam book/et al. = book, which is a good reference that describes the classic algorithm. = The book Graphics Gems I also has a discussion, though it is brief. You = can also find this stuff online, for free. For example, two sets of = lecture slides from University of Virginia that look good:<br><br><a = href=3D"http://www.cs.virginia.edu/%7Egfx/courses/2004/Intro.Fall.04/hand= outs/11-polyscan.pdf" = target=3D"_blank">http://www.cs.virginia.edu/~gfx/courses/2004/Intro.Fall= .04/handouts/11-polyscan.pdf</a><br><a = href=3D"http://www.cs.virginia.edu/%7Easb/teaching/cs445-fall06/slides/09= -rasterization.ppt" = target=3D"_blank">www.cs.virginia.edu/~asb/teaching/cs445-fall06/slides/0= 9-rasterization.ppt</a><br><br>I even found this YouTube = video:<br><br><a href=3D"http://www.youtube.com/watch?v=3DTNbkX5bYrtE" = target=3D"_blank">http://www.youtube.com/watch?v=3DTNbkX5bYrtE</a><br><sp= an style=3D'color:#888888'><br>Graham</span><o:p></o:p></p><div><p = class=3DMsoNormal><br>-----Original Message-----<br>From: Joel B = [mailto:<a = href=3D"mailto:[email protected]">[email protected]</a>]<o:= p></o:p></p></div><div><p class=3DMsoNormal = style=3D'margin-bottom:12.0pt'>Sent: Wednesday, August 10, 2011 7:49 = AM<br>To: Game Development Algorithms<br>Subject: [Algorithms] Draw = & fill regular polygon?<o:p></o:p></p></div><div><div><p = class=3DMsoNormal>I should know how to do this, but i don't. I only have = the ability in my system to draw lines (x1,y1,x2,y2)' to a bitmap, or = write to the bitmap as a byte array. Can someone tell me the stepwise = procedure to draw a polygon of n sides and then fill it? Having trouble = finding anything online that doesn't use pre-existing primitives or = libraries.<br><br>Thanks,<br><br>Joel<br>Sent from my = iPhone<br>---------------------------------------------------------------= ---------------<br>uberSVN's rich system and user administration = capabilities and model<br>configuration take the hassle out of deploying = and managing Subversion and<br>the tools developers use with it. Learn = more about uberSVN and get a free<br>download at: <a = href=3D"http://p.sf.net/sfu/wandisco-dev2dev" = target=3D"_blank">http://p.sf.net/sfu/wandisco-dev2dev</a><br>___________= ____________________________________<br>GDAlgorithms-list mailing = list<br><a = href=3D"mailto:[email protected]">GDAlgorithms-list= @lists.sourceforge.net</a><br><a = href=3D"https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list" = target=3D"_blank">https://lists.sourceforge.net/lists/listinfo/gdalgorith= ms-list</a><br>Archives:<br><a = href=3D"http://sourceforge.net/mailarchive/forum.php?forum_name=3Dgdalgor= ithms-list" = target=3D"_blank">http://sourceforge.net/mailarchive/forum.php?forum_name= =3Dgdalgorithms-list</a><br><br>-----------------------------------------= -------------------------------------<br>uberSVN's rich system and user = administration capabilities and model<br>configuration take the hassle = out of deploying and managing Subversion and<br>the tools developers use = with it. Learn more about uberSVN and get a free<br>download at: = <a href=3D"http://p.sf.net/sfu/wandisco-dev2dev" = target=3D"_blank">http://p.sf.net/sfu/wandisco-dev2dev</a><br>___________= ____________________________________<br>GDAlgorithms-list mailing = list<br><a = href=3D"mailto:[email protected]">GDAlgorithms-list= @lists.sourceforge.net</a><br><a = href=3D"https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list" = target=3D"_blank">https://lists.sourceforge.net/lists/listinfo/gdalgorith= ms-list</a><br>Archives:<br><a = href=3D"http://sourceforge.net/mailarchive/forum.php?forum_name=3Dgdalgor= ithms-list" = target=3D"_blank">http://sourceforge.net/mailarchive/forum.php?forum_name= =3Dgdalgorithms-list</a><o:p></o:p></p></div></div></div><p = class=3DMsoNormal><o:p> </o:p></p></div></body></html> ------=_NextPart_000_0010_01CC5848.4A145D80-- --===============0160816532929508665== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline ------------------------------------------------------------------------------ Get a FREE DOWNLOAD! and learn more about uberSVN rich system, user administration capabilities and model configuration. Take the hassle out of deploying and managing Subversion and the tools developers use with it. http://p.sf.net/sfu/wandisco-dev2dev --===============0160816532929508665== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline _______________________________________________ GDAlgorithms-list mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list --===============0160816532929508665==--