10 Aug 2011 13:49

## 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
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list <at> lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

```
10 Aug 2011 14:26

### Re: Draw & fill regular polygon?

```Hi Joel,

> 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.

I think the easiest way to fill a convex polygon is to generate horizontal
spans, and fill them in.
Declare two arrays (e.g. "left" and "right"), which will be used to store the
horizontal spans of the polygon. Initialize them with max/min of your
datatype.
Rasterize each segment on the polygon boundary, by stepping along the y-axis.
and store the corresponding x coordinate. Something like:

// Caveat: hande horizontal segments, last segment, etc.
float dX = (float)(boundary[i+1].x - boundary[i].x)/(boundary[i+1].y -
boundary[i].y);
float X = boundary[i].x + 0.5;
for (int y = boundary[i].y; y < max_y; y++)
{
X+= dX;
left[y] = min(left[y], (int)X);
right[y] = max(right[y], (int)X);
}

Now, fill in the spans:

for (y = min_y; y < max_y; y++)
```

10 Aug 2011 14:49

### Re: Draw & fill regular polygon?

```Does it have to be online?  Foley, van Dam, Feiner and Hughes have
plenty of details on scan line rendering.

-----Original Message-----
From: Joel B [mailto:onephatcat <at> earthlink.net]
Sent: 10 August 2011 12:49
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
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list <at> lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
```

10 Aug 2011 15:21

### Re: Draw & fill regular polygon?

```On 10 August 2011 12:49, Joel B <onephatcat <at> earthlink.net> wrote:
> 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

if you already have a line drawing function, then use the code from
that to update a pair of arrays of min/max on the x axis:

int xmin[SCREEN_HEIGHT] = { SCREEN_WIDTH... }
int xmax[SCREEN_HEIGHT] = { -1... }

then for each step of your line drawing function update the min/max:

replace your: put_pixel(x,y,colour)
with: xmin[y] = min(x,xmin[y]); xmax[y] = max(x,xmax[y]);

Once you have the arrays, it's a simple case of iterating over them
and rendering all pixels between the min and max where the difference
is positive.

foreach y in SCREEN_HEIGHT:
if( xmax[y] > xmin[y] )
foreach( x in range( xmin[y], xmax[y] ):
put_pixel( x,y, colour )

```

10 Aug 2011 17:15

### Re: Draw & fill regular polygon?

Hi Joel,

it's from an old book of Andre LaMothe, in this chapter he described how to rasterize poligons with just a pointer to vram.

check it out.

hope it's usefull. ;)

"It's not that I'm insane, it just happens that I'm very creative with my own sanity"

On Wed, Aug 10, 2011 at 8:21 AM, Richard Fabian wrote:
On 10 August 2011 12:49, Joel B <onephatcat <at> earthlink.net> wrote:
> 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

if you already have a line drawing function, then use the code from
that to update a pair of arrays of min/max on the x axis:

int xmin[SCREEN_HEIGHT] = { SCREEN_WIDTH... }
int xmax[SCREEN_HEIGHT] = { -1... }

then for each step of your line drawing function update the min/max:

replace your: put_pixel(x,y,colour)
with: xmin[y] = min(x,xmin[y]); xmax[y] = max(x,xmax[y]);

Once you have the arrays, it's a simple case of iterating over them
and rendering all pixels between the min and max where the difference
is positive.

foreach y in SCREEN_HEIGHT:
if( xmax[y] > xmin[y] )
foreach( x in range( xmin[y], xmax[y] ):
put_pixel( x,y, colour )

and you have an untextured triangle.
if you want it textured, don't forget to store only UV values when the
max/min is updated.

--
fabs();
Just because the world is full of people that think just like you,
doesn't mean the other ones can't be right.

------------------------------------------------------------------------------
uberSVN's rich system and user administration capabilities and model
configuration take the hassle out of deploying and managing Subversion and
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list <at> lists.sourceforge.net
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
```
```_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list <at> lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list```
11 Aug 2011 18:32

### Re: Draw & fill regular polygon?

On Aug 10, 2011, at 8:15 AM, Jacobo Ríos wrote:

Hi Joel,

it's from an old book of Andre LaMothe, in this chapter he described how to rasterize poligons with just a pointer to vram.

check it out.

hope it's usefull. ;)

Very nice!
```------------------------------------------------------------------------------
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```
```_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list <at> lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list```
10 Aug 2011 17:29

### Re: Draw & fill regular polygon?

```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-polyscan.pdf
www.cs.virginia.edu/~asb/teaching/cs445-fall06/slides/09-rasterization.ppt

I even found this YouTube video:

Graham

-----Original Message-----
From: Joel B [mailto:onephatcat <at> earthlink.net]
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
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list <at> lists.sourceforge.net
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
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list <at> lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

```
11 Aug 2011 08:05

### Re: 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 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-polyscan.pdf
www.cs.virginia.edu/~asb/teaching/cs445-fall06/slides/09-rasterization.ppt

I even found this YouTube video:

Graham

-----Original Message-----
From: Joel B [mailto:onephatcat <at> earthlink.net]
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
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list <at> lists.sourceforge.net
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
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list <at> lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

```------------------------------------------------------------------------------
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```
```_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list <at> lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list```
11 Aug 2011 09:01

### Re: Draw & fill regular polygon?

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

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 <grhodes <at> ara.com> 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-polyscan.pdf
www.cs.virginia.edu/~asb/teaching/cs445-fall06/slides/09-rasterization.ppt

I even found this YouTube video:

Graham

-----Original Message-----
From: Joel B [mailto:onephatcat <at> earthlink.net]

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
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list <at> lists.sourceforge.net
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
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list <at> lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

```------------------------------------------------------------------------------
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```
```_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list <at> lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list```
11 Aug 2011 09:54

### Re: Draw & fill regular polygon?

```On 10.08.2011 23:05, Martin Gladnishki wrote:
> 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.

Even for general polygons, the auxiliary arrays aren't necessary; you
keep a linked list of active edges sorted by their current x coordinate
(in the last processed scanline). This is fairly simple to code (and
keep up to date).

From there, you just need to count the current winding based on the
orientation of active edges. That allows you to implement all popular
fill rules.

-Fabian

------------------------------------------------------------------------------
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
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list <at> lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

```
11 Aug 2011 18:17

### Re: Draw & fill regular polygon?

Hi Graham,

www.cs.virginia.edu/~asb/teaching/cs445-fall06/slides/09-rasterization.ppt

Thanks, this is a stunningly good PPT presentation.

- Joel
```------------------------------------------------------------------------------
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```
```_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list <at> lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list```

Gmane