Polygons filled using scan line algorithm

Post your FreeBASIC tips and tricks here. Please don’t post your code without including an explanation.
Pitto
Posts: 119
Joined: Nov 19, 2012 19:58

Polygons filled using scan line algorithm

Postby Pitto » Sep 01, 2017 13:49

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.

Image

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 sub

randomize timer
'variables declarations_________________________________________________
dim as integer a(0 to POINTS, 0 to 1), x, c, p
dim as double timer_01, timer_02


'INITIALIZING GRAPHICS _________________________________________________
screenres SCR_W, SCR_H, 24      'initialize graphics
cls

c = &h0000FF
timer_01 = timer
for 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 p


timer_02 = timer
draw string (SCR_W\2 +1, SCR_H - 20 + 1), "scanline fill in " + str(int((timer_02 - timer_01)*10000)/10000) + " sec", &h000000
draw 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:", &h000000
draw string (21, 31), "code-heaven.blogspot.it/2009/10/simple-c-program-for-scan-line-polygon.html", &h000000
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

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

Re: Polygons filled using scan line algorithm

Postby MrSwiss » Sep 01, 2017 14:21

@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: 9994
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Polygons filled using scan line algorithm

Postby fxm » Sep 01, 2017 14:29

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: 3636
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: Polygons filled using scan line algorithm

Postby MrSwiss » Sep 01, 2017 14:35

> 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: 1363
Joined: Jun 04, 2005 9:51

Re: Polygons filled using scan line algorithm

Postby dafhi » Sep 01, 2017 15:02

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

Re: Polygons filled using scan line algorithm

Postby Pitto » Sep 01, 2017 15:04

@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: 3636
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: Polygons filled using scan line algorithm

Postby MrSwiss » Sep 01, 2017 15:06

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

Postby St_W » Sep 01, 2017 15:13

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: 3636
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: Polygons filled using scan line algorithm

Postby MrSwiss » Sep 01, 2017 15:20

> 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

Postby St_W » Sep 01, 2017 15:25

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: 9994
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Polygons filled using scan line algorithm

Postby fxm » Sep 01, 2017 16:39

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: 3636
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: Polygons filled using scan line algorithm

Postby MrSwiss » Sep 01, 2017 16:51

> 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: 9994
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Polygons filled using scan line algorithm

Postby fxm » Sep 01, 2017 16:57

Everyone has his fads!
MrSwiss
Posts: 3636
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: Polygons filled using scan line algorithm

Postby MrSwiss » Sep 01, 2017 21:38

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 here

Sub 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 y
End Sub


randomize Timer, 3
'variables declarations_________________________________________________
Dim As Long     a(0 to POINTS, 0 to 1), x, c, p
Dim As Double   timer_01, timer_02

'INITIALIZING GRAPHICS _________________________________________________
ScreenRes(SCR_W, SCR_H, 24)      'initialize graphics
Cls

c = &h0000FF
timer_01 = timer
For 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 p
timer_02 = Timer - timer_01

Draw 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

Postby Pitto » Sep 03, 2017 10:00

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

Return to “Tips and Tricks”

Who is online

Users browsing this forum: Bing [Bot] and 3 guests