Polygons filled using scan line algorithm

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

Polygons filled using scan line algorithm

Post by Pitto »

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/ ... lygon.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: 3910
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: Polygons filled using scan line algorithm

Post by MrSwiss »

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

Re: Polygons filled using scan line algorithm

Post by fxm »

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

Re: Polygons filled using scan line algorithm

Post by MrSwiss »

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

Re: Polygons filled using scan line algorithm

Post by dafhi »

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

Re: Polygons filled using scan line algorithm

Post by Pitto »

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

Re: Polygons filled using scan line algorithm

Post by MrSwiss »

> `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: 1619
Joined: Feb 11, 2009 14:24
Location: Austria
Contact:

Re: Polygons filled using scan line algorithm

Post by St_W »

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

Re: Polygons filled using scan line algorithm

Post by MrSwiss »

> 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: 1619
Joined: Feb 11, 2009 14:24
Location: Austria
Contact:

Re: Polygons filled using scan line algorithm

Post by St_W »

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

Re: Polygons filled using scan line algorithm

Post by fxm »

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

Re: Polygons filled using scan line algorithm

Post by MrSwiss »

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

Re: Polygons filled using scan line algorithm

Post by fxm »

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

Re: Polygons filled using scan line algorithm

Post by MrSwiss »

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: 122
Joined: Nov 19, 2012 19:58

Re: Polygons filled using scan line algorithm

Post by Pitto »

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