[bmx] Correct Filled Polygon by dw817 [ 1+ years ago ]

[BlitzBot]

Title : Correct Filled Polygon
Author : dw817
Posted : 1+ years ago

Description :

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.

Code :

Code (blitzmax) Select Expand

'    ___________________________________________
'   //                                        //
'  //    "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^jVlf]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(Posted 1+ years ago)

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


Bobysait(Posted 1+ years ago)

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

Code Select Expand

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.

Code Select Expand

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 127For m = -1 to 1ReadPixel(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(Posted 1+ years ago)

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

Code Select Expand

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^jVlf]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(Posted 1+ years ago)

 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 [/i]