Correct Filled Polygon

This code has been declared by its author to be Public Domain code.

Correct Filled Polygon by dw817

2016

A quick and dirty way of building a filled polygon where FillPoly() provided by BlitzMAX makes a mess of it for concave angles.

Does not require any additional libs, dlls, or mods.

Any questions or comments, especially about the BlitzMAX commands or functions used in this code, please address them below.

'    ___________________________________________
'   //                                        //
'  //    "Perfect" Filled Polygon            //
' //    Written by David W (dw817) 01/12/16 //
'//________________________________________//

' What's up ?? Added boundary check, thanks to Bobysait

Strict
SetGraphicsDriver(GLMax2DDriver()) ' no problems w intensive pixel reading
Graphics 640,480
SetBlend alphablend ' allow for transparency

Global vec$="3U^jV\lf]7RGN3P" ' all vector images are in 8x8 grid
Global typ

typ=0
' 0 (zero) to use my polygon plotter
' 1 (one) to use BlitzMAX's own flawed plotter

If typ=0 Then drawvec vec$
If typ=1 Then drawvec2 vec$
Flip
WaitKey

Function drawvec(t$)
Local x,y,x2,y2,p,a,i,j,k,m,z=Len(t$),ok,pic:TPixmap
  For p=1 To z
    a=Asc(Mid$(t$,p))-40 ' pull out a vector
    x=a Mod 9*16 ' retrieve horizontal
    y=a/9*16 ' retrieve vertical
    If p>1 And p<z ' if not first iteration nor last, draw vector
      DrawLine x2,y2,x,y
    ElseIf p=z ' last iteration, let's do our fill
      pic=GrabPixmap(0,0,128,128) ' grab image for massive pixel updates
      WritePixel pic,x,y+8,$fffffffe ' +8 as paint vector falls on existing edge
' needs to be $fe to differentiate between edges that are $ff
      Repeat
        ok=1 ' flag that no changes have been made
        For i=0 To 127 ' field of 8x8 grid, snap on 16
          For j=0 To 127
            If j+m>=0 And i+k>=0 ' confirm within range of screen
              If ReadPixel(pic,j,i)=$fffffffe ' found our paint pixel
                For k=-1 To 1
                  For m=-1 To 1
                    If j+m>=0 And i+k>=0 And j+m<=127 And i+k<=127 ' confirm within ange
                      If ReadPixel(pic,j+m,i+k)=$ff000000 And(k=0 Or m=0) ' ensure search is cross and not square
                        WritePixel pic,j+m,i+k,$fffffffe ' it's empty so fill it in
                        ok=0 ' flag for cannot exit just yet
                      EndIf
                    EndIf
                  Next
                Next
              EndIf
            EndIf
          Next
        Next
      Until ok ' no changes above means we're finally done
      DrawPixmap pic,0,0 ' draw back the changes
    EndIf
    x2=x
    y2=y
  Next
EndFunction

Function drawvec2(t$) ' System's own polygon plotter
Local vec#[Len(t$)*2],a,i
  For i=1 To Len(t$)
    a=Asc(Mid$(t$,i))-40
    vec#[i*2-2]=a Mod 9*16+20 ' store X
    vec#[i*2-1]=a/9*16+20 ' store Y
  Next
  DrawPoly vec# ' use system's own plotter, flawed
EndFunction

Comments

SimonasQu

2016

Why pix-mapping it? I've the code to draw filled textured polygons with native openGL/DirectX functions.

Bobysait

2016

I won't comment on the "writepixel" method, it can be usefull for writing concave polygons to textures.

I just will mention this :

for i=1 To Len(t$)
    a=Asc(Mid$(t$,i))-40
    [...]

you'll get a more user-friendly syntax (and improved performances) by using the byte buffer attached to the string.

For i = 0 Until t.length
   a = t[i] - 40;
Next

This will give the same result.

ps :
BTW, your code won't compile on debug because you try to write pixel outside of the pixmap range.
For j = 0 to 127
For m = -1 to 1
ReadPixel(pic,j+m,i+k)
-> your "j+m" so as the "i+k" coordinates are in the range [-1, 128] and it will crash on debug mode.

Bobysait

2016

This is the ear-clipping method for filling a concave polygon
It should computes polygons fast enough to be used in realtime.

SuperStrict

Function extractPolys:Float[][](t:String)
	
	' generate the points list
	Local pt:Float[][] = New Float[][t.length-1];
	For Local p:Int = 0 Until t.length-1
		pt[p] = [VecX(t[p]-40), VecY(t[p]-40)];
	Next;
	
	' initialize polygon list
	Local polys:Float[][] = New Float[][0];
	
	' current vertex to test.
	Local v:Int = 0;
	
	While pt.length>3
		
		Local ptl:Int = pt.length;
		Local v0:Int = v Mod(ptl), v1:Int = (v+1) Mod (ptl), v2:Int = (v1+1) Mod (ptl);
		
		' coordinates of the triangle to test
		Local x0:Float = pt[v0][0], y0:Float = pt[v0][1];
		Local x1:Float = pt[v1][0], y1:Float = pt[v1][1];
		Local x2:Float = pt[v2][0], y2:Float = pt[v2][1];
		
		' cross product -> Z Front (Front =-1)
		If (x2-x0)*(y2-y1)-(y2-y0)*(x2-x1)>=0 ' if triangle backward -> skip point
			v = v1;
		Else
			' test no point are in the triangle v0,v1,v2
			Local t:Int=False;
			For Local p__:Int = 0 Until pt.length
				' don't test vertices of the triangle ^^
				If p__<>v0 And p__<>v1 And p__<>v2
					' point in the triangle -> skip this triangle.
					If InTriangle( pt[p__][0], pt[p__][1], x0,y0, x1,y1, x2,y2 ) Then t = True; v = v1; Exit;
				EndIf;
			Next;
			
			If t=False ' no point the triangle
				' output new triangle
				polys = polys+[[pt[v0][0],pt[v0][1],..
							 	pt[v1][0],pt[v1][1],..
							 	pt[v2][0],pt[v2][1]]];
				
				' remove v1 from points list
				If v1=0 ' first point -> points = points after v1
					pt = pt[v1+1..];
				ElseIf v1=pt.length-1 ' last point -> points = points before v1
					pt = pt[..v1];
				Else ' points = start of points until v1 + points after v1
					pt = pt[..v1]+pt[v1+1..];
				EndIf;
			EndIf;
			
		EndIf;
		
	Wend;
	
	Return polys;
	
End Function

Function InTriangle:Byte ( x0:Float,y0:Float, x1:Float,y1:Float, x2:Float,y2:Float, x3:Float,y3:Float )
	Local b0:Float =  1.0 / (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
	If ( ( ((x2 - x0) * (y3 - y0) - (x3 - x0) * (y2 - y0)) * b0 ) <= 0) Then Return False;
	If ( ( ((x3 - x0) * (y1 - y0) - (x1 - x0) * (y3 - y0)) * b0 ) <= 0) Then Return False;
	Return ( ( ((x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0)) * b0 ) > 0)
End Function


' small sdk to convert string data to coordinates
Function VecX:Float(a:Int)
	Return a Mod(9) * 16
End Function
Function VecY:Float(a:Int)
	Return a/9 * 16
End Function


SetGraphicsDriver(GLMax2DDriver()) ' no problems w intensive pixel reading
Graphics (640,480, 0, 0)

Local vec:String="3U^jV\lf]7RGN3P";
vec = vec[..vec.length-1]; ' remove last vertex -> it overrides the first vertex.

' generates a list of polygons ( each polygon is in fact a triangle -> float[x0,y0,x1,y1,x2,y2] )
Local polys:Float[][] = extractPolys(vec);

Cls
SetColor 150,150,150

For Local p:Float[] = EachIn polys
	DrawPoly(p);
Next

Flip True
WaitKey()
End

dw817

2016

Ok ... I am finally understanding what is going on here. You are taking my polygon image and 'shaping' it so the flawed DrawPoly() can finally draw it the correct way. You are essentially adding crutches, and - if that's what is needed.

Quite a bit of work - nice job of that ! :)

As for the coordinates, yes - I need to add a check boundaries.

Corrected - Code Updated

Code Archives Forum