## Polygons filled using scan line algorithm

Pitto
Posts: 119
Joined: Nov 19, 2012 19:58

### Polygons filled using scan line algorithm

Here's a translation from a C implementation of the scan line algorithm to fill polygons.
In this snippet 10 random generated polygons of 10 vertices each are filled without using "paint" function. C original source: http://code-heaven.blogspot.it/2009/10/simple-c-program-for-scan-line-polygon.html

Code: Select all

`'Polygons filled using scan line algorithm#include "fbgfx.bi"Using FB'DEFINE_________________________________________________________________#define POINTS       10#define POLYGONS    10#define SCR_W       640#define SCR_H       480'SUBS declarations______________________________________________________declare sub fill_polygon(vertices() as integer, c as integer)sub fill_polygon(a() as integer, c as integer)   'translation of a c snippet by Angad   'source of c code: http://code-heaven.blogspot.it/2009/10/simple-c-program-for-scan-line-polygon.html   dim as integer i,j,k,dy,dx, x,y,temp   dim as integer xi (0 to Ubound(a))   dim as single slope(0 to Ubound(a))      'join first and last vertex   a(Ubound(a),0)=a(0,0)   a(Ubound(a),1)=a(0,1)   for i=0 to Ubound(a) - 1       dy=a(i+1,1)-a(i,1)      dx=a(i+1,0)-a(i,0)      if(dy=0) then slope(i)=1.0      if(dx=0) then slope(i)=0.0      if ((dy <> 0) and (dx <> 0)) then         'calculate inverse slope         slope(i) = dx / dy      end if   next i   for y=0 to SCR_H-1      k = 0      for i=0 to Ubound(a) - 1         if( ((a(i,1)<=y) and (a(i+1,1)>y)) or ((a(i,1)>y) _         and (a(i+1,1)<=y))) then            xi(k)= int(a(i,0)+slope(i)*(y-a(i,1)))            k +=1         end if      next i      for j = 0 to k-2         'Arrange x-intersections in order         for i = 0 to k-2            if (xi(i) > xi(i+1)) then               temp = xi(i)               xi(i) = xi(i+1)               xi(i+1) = temp            end if         next i      next j      'line filling      for i = 0 to k - 2 step 2         line (xi(i),y)-(xi(i+1)+1,y), c      next i   next y   end subrandomize timer'variables declarations_________________________________________________dim as integer a(0 to POINTS, 0 to 1), x, c, pdim as double timer_01, timer_02'INITIALIZING GRAPHICS _________________________________________________screenres SCR_W, SCR_H, 24      'initialize graphicsclsc = &h0000FFtimer_01 = timerfor p = 0 to POLYGONS-1   for x = 0 to POINTS      a(x, 0) = int (rnd*SCR_W)      a(x, 1) = int (rnd*SCR_H)   next x   fill_polygon(a(), rnd*&hFFFFFF)next ptimer_02 = timerdraw string (SCR_W\2 +1, SCR_H - 20 + 1), "scanline fill in " + str(int((timer_02 - timer_01)*10000)/10000) + " sec", &h000000draw string (SCR_W\2, SCR_H - 20), "scanline fill in " + str(int((timer_02 - timer_01)*10000)/10000) + " sec"draw string (21, 21), "scanline polygon - translated from:", &h000000draw string (21, 31), "code-heaven.blogspot.it/2009/10/simple-c-program-for-scan-line-polygon.html", &h000000draw string (20, 20), "scanline polygon - translated from:"draw string (20, 30), "code-heaven.blogspot.it/2009/10/simple-c-program-for-scan-line-polygon.html"sleep`
MrSwiss
Posts: 3635
Joined: Jun 02, 2013 9:27
Location: Switzerland

### Re: Polygons filled using scan line algorithm

@Pitto,

I've not tried your code, however, there is a massive problem, in the translation:

a INT (in C = 32bit) <> Integer (in FBC 64) = LongInt (64bit)
(it's only the same, with FBC 32!)

INT = Long (in FB, all versions 32/64), this is important, to stay compatible, with FBC 32/64.
fxm
Posts: 9993
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

### Re: Polygons filled using scan line algorithm

MrSwiss wrote:I've not tried your code, however, there is a massive problem, in the translation...
Still, it works in 64-bit too!
MrSwiss
Posts: 3635
Joined: Jun 02, 2013 9:27
Location: Switzerland

### Re: Polygons filled using scan line algorithm

> Still, it works in 64-bit too!

Sorry, I'm taking that as a joke, since:
a larger variable of the same type (e.g. both some sort of 'integer') always works ...
unless its 'blowing' a given size, of a defined 'header'.

Its still an incorrect conversion!
dafhi
Posts: 1361
Joined: Jun 04, 2005 9:51

### Re: Polygons filled using scan line algorithm

nice one pitto. thanks for posting
Pitto
Posts: 119
Joined: Nov 19, 2012 19:58

### Re: Polygons filled using scan line algorithm

@MrSwiss

thanks for the tip.

So, in order to avoid problems with 64bit fbc (or some headers), I've to replace `integer` with `Long`.
`Long` remains a 32-bit signed whole-number data type in both 32 and 64 bit platforms, right?

@dafhi
you welcome
MrSwiss
Posts: 3635
Joined: Jun 02, 2013 9:27
Location: Switzerland

### Re: Polygons filled using scan line algorithm

> `Long` remains a 32-bit signed whole-number data type in both 32 and 64 bit platforms, right?

correct (so called fixed data-type)
Last edited by MrSwiss on Sep 01, 2017 15:15, edited 1 time in total.
St_W
Posts: 1508
Joined: Feb 11, 2009 14:24
Location: Austria
Contact:

### Re: Polygons filled using scan line algorithm

Pitto wrote:`Long` remains a 32-bit signed whole-number data type in both 32 and 64 bit platforms, right?

Yes, or use "Integer<32>" which makes the size more clear. However, you only need to use Integer<32>/Long where you actually need a 32-bit variable. In your application Integer is probably fine in many (if not all) cases.
MrSwiss
Posts: 3635
Joined: Jun 02, 2013 9:27
Location: Switzerland

### Re: Polygons filled using scan line algorithm

> In your application Integer is probably fine in many (if not all) cases.

Its a translation from: C's int (for those, not really reading the whole thread!)
St_W
Posts: 1508
Joined: Feb 11, 2009 14:24
Location: Austria
Contact:

### Re: Polygons filled using scan line algorithm

MrSwiss wrote:> In your application Integer is probably fine in many (if not all) cases.

Its a translation from: C's int (for those, not really reading the whole thread!)

Yes, it wouldn't be a simple 1:1 translation anymore, but the algorithm would still work correctly. (and btw I did skim the whole thread including the part refering to the C code ;-) )

I just wanted to say that the use of Integer is not inherently wrong or a "massive problem". And it's just some code found somewhere on the web, it doesn't necessarily have to be 100% correct either. But I agree that from a strict translation point-of-view the translation of int to Integer is wrong.
fxm
Posts: 9993
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

### Re: Polygons filled using scan line algorithm

By the way, the execution speed (on any platform) is not improved by reducing the size of the variable used compared to the basic size "Integer" (32 bits or 64 bits depending on the platform). The only speed gain would be if one goes from a 64-bit variable to a 32-bit variable and on a 32-bit platform only.

The only gain is on the RAM memory space used.
MrSwiss
Posts: 3635
Joined: Jun 02, 2013 9:27
Location: Switzerland

### Re: Polygons filled using scan line algorithm

> The only gain is on the RAM memory space used.

No, the main gain is: writing code that's independent of, which compiler 32/64 is later used ...
(this applies mainly to code, containing UDT's, libraries etc.)
fxm
Posts: 9993
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

### Re: Polygons filled using scan line algorithm

MrSwiss
Posts: 3635
Joined: Jun 02, 2013 9:27
Location: Switzerland

### Re: Polygons filled using scan line algorithm

Here is the translated code:

Code: Select all

`'Polygons filled using scan line algorithm#Include "fbgfx.bi"Using FB'DEFINE_________________________________________________________________'#Define POINTS      10'#Define POLYGONS    10'#Define SCR_W       640'#Define SCR_H       480' replaces the defines above (single line Macro's in FB)Const As Long   POINTS = 10, POLYGONS = 10, SCR_W = 640, SCR_H = 480'SUBS declarations______________________________________________________'Declare Sub fill_polygon(a() As Long, ByVal c As ULong) not necessary hereSub fill_polygon(a() As Long, ByVal c As ULong)   'translation of a c snippet by Angad   'source of c code: http://code-heaven.blogspot.it/2009/10/simple-c-program-for-scan-line-polygon.html   Dim As Long      i, j, k, dy, dx, x, y, temp   Dim As Long      xi(0 to Ubound(a, 1))   Dim As Single    slope(0 to Ubound(a, 1))      'join first and last vertex   a(Ubound(a, 1), 0) = a(0, 0)   a(Ubound(a, 1), 1) = a(0, 1)   For i = 0 To Ubound(a, 1) - 1      dy = a(i+1, 1) - a(i, 1)      dx = a(i+1, 0) - a(i, 0)      If (dy = 0) Then slope(i) = 1.0      If (dx = 0) Then slope(i) = 0.0      If (dy <> 0) AndAlso (dx <> 0) Then slope(i) = dx / dy   Next i   For y = 0 to SCR_H - 1      k = 0      ' using FB's short-cut operators (which C doesn't have!)      For i = 0 to Ubound(a, 1) - 1         If (a(i, 1) <= y AndAlso a(i+1, 1) > y) OrElse _             (a(i, 1) > y AndAlso a(i+1, 1) <= y) Then            xi(k) = CLng(a(i, 0) + slope(i) * (y - a(i, 1)))            k += 1         End If      Next i      For j = 0 to k - 2         'Arrange x-intersections in order         For i = 0 To k - 2            If (xi(i) > xi(i + 1)) Then               temp = xi(i)               xi(i) = xi(i + 1)               xi(i + 1) = temp            End If         Next i      Next j      'line filling      For i = 0 To k - 2 Step 2         Line (xi(i), y)-(xi(i + 1) + 1, y), c      Next i   Next yEnd Subrandomize Timer, 3'variables declarations_________________________________________________Dim As Long     a(0 to POINTS, 0 to 1), x, c, pDim As Double   timer_01, timer_02'INITIALIZING GRAPHICS _________________________________________________ScreenRes(SCR_W, SCR_H, 24)      'initialize graphicsClsc = &h0000FFtimer_01 = timerFor p = 0 to POLYGONS-1   For x = 0 to POINTS      a(x, 0) = CLng(rnd*SCR_W)      a(x, 1) = CLng(rnd*SCR_H)   Next x   fill_polygon(a(), CULng(rnd*&hFFFFFF))Next ptimer_02 = Timer - timer_01Draw String (SCR_W\2, SCR_H - 20), "scanline fill in " + Str(CLng(timer_02 * 10000) / 10000) + " sec"Draw String (20, 20), "scanline polygon - translated from:"Draw String (20, 30), "code-heaven.blogspot.it/2009/10/simple-c-program-for-scan-line-polygon.html"Sleep' ----- EOF -----`
Pitto
Posts: 119
Joined: Nov 19, 2012 19:58

### Re: Polygons filled using scan line algorithm

@MrSwiss
Thanks for the correct translation.
I'll use it on a vector graphic low poly editor I'm currently working on.