Triangle fill algorithm

BalrogSoft · Post by **BalrogSoft** » Tue Feb 13, 2007 1:09 pm

Hi, i'm working on a 64kb intro for Amiga, and i made a triangle fill algorithm that i tested before on Purebasic (windows), it use fixed point math, and words to store values, with a 6 bits of precision you can draw triangles on a screen of 1024x1024 maximum, but you can change the algorithm to accept bigger values (change word variables to long).

Code: Select all

EnableExplicit 
#FP = 6

Procedure filltriangle(x1,y1,x2,y2,x3,y3,color) 

Define.w x, y, x0,y0, dx1, dx2, dx3, scanleftx, scanrightx, leftadd, rightadd, beginx, endx
Define.b bucle

; Sort algorithm using swap method, two iterations is enough to sort an array with 3 items
For bucle = 0 To 1
  If y1>y2 : x0=x2 : x2=x1 : x1=x0 : y0=y2 : y2=y1 : y1=y0 :  EndIf  
  If y2>y3 : x0=x3 : x3=x2:  x2=x0 : y0=y3 : y3=y2 : y2=y0 :  EndIf 
Next bucle

If y2 <> y1
  dx1=((x2-x1)<<#FP)/(y2-y1) 
EndIf
If y3 <> y1
  dx2=((x3-x1)<<#FP)/(y3-y1) 
EndIf
If y3<> y2 
  dx3=((x3-x2)<<#FP)/(y3-y2) 
EndIf

scanleftx = x1 << #FP
scanrightx = x1 << #FP

If dx1 < dx2
  leftadd=dx1
  rightadd=dx2
Else
  leftadd=dx2
  rightadd=dx1
EndIf

For y = y1 To y2-1
  beginx = scanleftx >> #FP
  endx = scanrightx >> #FP
  LineXY(beginx, y, endx, y, color)
  scanleftx + leftadd
  scanrightx + rightadd
Next y

If dx2 > dx3
  leftadd = dx2
  rightadd = dx3
Else
  leftadd = dx3
  rightadd = dx2
EndIf

For y = y2 To y3
  beginx = scanleftx >> #FP
  endx = scanrightx >> #FP
  LineXY(beginx, y, endx, y, color)
  scanleftx + leftadd
  scanrightx + rightadd
Next y

EndProcedure

Derek · Post by **Derek** » Tue Feb 13, 2007 2:18 pm

Surprisingly fast. Nice.

dell_jockey · Post by **dell_jockey** » Wed Mar 14, 2007 7:35 pm

Very nice code.

There seems to be an issue with horizontal coordinates in excess of 512 (some sort of coordinate wrap-around is taking place) and vertical coordinates in excess of 256 (no wrap-around in this case, but 'flattened line intersections'). I'm going to look into it some more, so far I didn't find a solution.

BalrogSoft · Post by **BalrogSoft** » Thu Mar 15, 2007 9:11 pm

Here is another triangle fill algorithm, with linear texture mapping, i think that it solve some bugs of previous example.

Code: Select all

InitSprite()

EnableExplicit 

Define t.w,x.w,y.w

#TEXTURE_SIZE = 64

Global Dim texture(#TEXTURE_SIZE,#TEXTURE_SIZE)

#FP = 7

Procedure fAbs(value.w)
If value.w < 0
  value.w = - value.w
EndIf
ProcedureReturn value.w
EndProcedure

Procedure filltriangle(x1,y1,x2,y2,x3,y3,u1,v1,u2,v2,u3,v3) 

Define.l x, y, x0,y0,u0,v0,u1,v1,u2,v2,u3,v3, dx1, dx2, dx3, scanleftx, scanrightx, leftadd, rightadd, beginx, endx
Define.l dudx,dvdx,dudy,dvdy,dx,dy,dxdyb
Define.l xa, xb, ua, va,u,v,ut,vt
Define.l dxdya, dxdyb, dudya, dvdya
Define.l denom
Define.b bucle

; Sort algorithm using swap method, two iterations is enough to sort an array with 3 items
For bucle = 0 To 1
  If y1>y2 : x0=x2 : x2=x1 : x1=x0 : y0=y2 : y2=y1 : y1=y0 : u0=u2 : u2=u1 : u1=u0 : v0=v2 : v2=v1 : v1=v0 : EndIf  
  If y2>y3 : x0=x3 : x3=x2:  x2=x0 : y0=y3 : y3=y2 : y2=y0 : u0=u2 : u2=u1 : u1=u0 : v0=v2 : v2=v1 : v1=v0 : EndIf 
Next bucle

denom = ((x3 - x1) * (y2 - y1) - (x2 - x1) * (y3 - y1)) >> #FP

If denom
  dudx = ((u3 - u1) * (y2 - y1) - (u2 - u1) * (y3 - y1)) / denom
  dvdx = ((v3 - v1) * (y2 - y1) - (v2 - v1) * (y3 - y1)) / denom
  dudy = ((u2 - u1) * (x3 - x1) - (u3 - u1) * (x2 - x1)) / denom
  dvdy = ((v2 - v1) * (x3 - x1) - (v3 - v1) * (x2 - x1)) / denom
Else
  dudx = ((u3 - u1) * (y2 - y1) - (u2 - u1) * (y3 - y1))
  dvdx = ((v3 - v1) * (y2 - y1) - (v2 - v1) * (y3 - y1))
  dudy = ((u2 - u1) * (x3 - x1) - (u3 - u1) * (x2 - x1))
  dvdy = ((v2 - v1) * (x3 - x1) - (v3 - v1) * (x2 - x1))
EndIf

If y2 <> y1
  dx1=(((x2-x1)<<#FP)/(y2-y1))
Else
  dx1=((x2-x1)<<#FP) 
EndIf
If y3 <> y1
  dx2=(((x3-x1)<<#FP)/(y3-y1))
Else
  dx2=((x3-x1)<<#FP)
EndIf
If y3 <> y2 
  dx3=(((x3-x2)<<#FP)/(y3-y2))
Else
  dx3=((x3-x2)<<#FP)
EndIf
		
scanleftx = x1 << #FP
scanrightx = x1 << #FP

If dx1 < dx2
  leftadd=dx1
  rightadd=dx2
Else
  leftadd=dx2
  rightadd=dx1
EndIf

dudya = ((leftadd * dudx) >> #FP) + dudy
dvdya = ((leftadd * dvdx) >> #FP) + dvdy

ua = u1 + dudya
va = v1 + dvdya

If y1 <> y2
  For y = y1 To y2-1
    beginx = scanleftx >> #FP
    endx = scanrightx >> #FP
  	u = ua + dudx
  	v = va + dvdx
  	If endx-beginx > 0
      For x = beginx To endx
        Plot(Abs(x),Abs(y), texture((u>>#FP)%#TEXTURE_SIZE, (v>>#FP)%#TEXTURE_SIZE))
        u + dudx
    		v + dvdx
      Next x
     	ua + dudya
    	va + dvdya
    EndIf
    scanleftx + leftadd
    scanrightx + rightadd
  Next y
Else
	ua + dudya
	va + dvdya
  scanleftx + leftadd
  scanrightx + rightadd
EndIf

If dx2 > dx3
  leftadd = dx2
  rightadd = dx3
Else
  leftadd = dx3
  rightadd = dx2
EndIf

dudya = ((leftadd * dudx) >> #FP) + dudy
dvdya = ((leftadd * dvdx) >> #FP) + dvdy

If y2 <> y3
  For y = y2 To y3
    beginx = scanleftx >> #FP
    endx = scanrightx >> #FP
  	u = ua + dudx
  	v = va + dvdx
  	If beginx <> endx
      For x = beginx To endx
        Plot(Abs(x),Abs(y), texture((u>>#FP)%#TEXTURE_SIZE, (v>>#FP)%#TEXTURE_SIZE))
        u + dudx
    		v + dvdx
      Next x
    	ua + dudya
    	va + dvdya
  	EndIf
    scanleftx + leftadd
    scanrightx + rightadd
  Next y
EndIf
  
EndProcedure 
  
Define WEvent, Quit

If OpenWindow(0, 0, 0, 320, 240, "Texture mapping", #PB_Window_SystemMenu|#PB_Window_ScreenCentered)
  OpenWindowedScreen(WindowID(0), 0, 0, 320, 240, 0, 0, 0)

  LoadImage(0,"c:\logo.bmp")

  StartDrawing(ImageOutput(0))
    For y = 0 To #TEXTURE_SIZE - 1
      For x = 0 To #TEXTURE_SIZE - 1
        texture(x, y) = Point(x, y)
      Next x
    Next y
  StopDrawing()

  Repeat
    
    WEvent = WindowEvent()
    
    If WEvent = #PB_Event_CloseWindow
      Quit = #True
    EndIf

    StartDrawing(ScreenOutput())

     filltriangle(5+Random(310),5+Random(230),5+Random(310),5+Random(230),5+Random(310),5+Random(230),0,0,63,0,0,63)

    StopDrawing()
   
    FlipBuffers()
    ClearScreen(0)
 
    Delay(10)
  Until Quit = #True  
  CloseWindow(0)
EndIf

dell_jockey · Post by **dell_jockey** » Tue May 22, 2007 2:31 pm

Hi BalrogSoft,

I've taken your last example, and stripped out all texture mapping stuff to be able to better test the triangle fill algorithm.
To speed things up, I replaced the pixel plot method (that you needed to implement texture mapping) for a LineXY() for each scanline.
I also added a magenta triangle outline, to check whether the triangle fill code computes the correct scanline x-start and x-end. See for yourself.
It looks like there are some issues, most notably on the right and bottom side of triangles.

Code: Select all

InitSprite() 

EnableExplicit 

#FP = 7 

Procedure filltriangle(x1,y1,x2,y2,x3,y3) 

Define.l x, y, x0,y0, dx1, dx2, dx3, scanleftx, scanrightx, leftadd, rightadd, beginx, endx 
Define.b bucle 

; magenta outline for debugging purposes
; theoretically the magenta should be overwritten by the white triangle
LineXY(x1, y1 , x2, y2, RGB(128,0,255)) 
LineXY(x2, y2 , x3, y3, RGB(128,0,255)) 
LineXY(x3, y3 , x1, y1, RGB(128,0,255)) 
                     
; Sort algorithm using swap method, two iterations is enough to sort an array with 3 items 
For bucle = 0 To 1 
  If y1>y2 : x0=x2 : x2=x1 : x1=x0 : y0=y2 : y2=y1 : y1=y0 :  EndIf  
  If y2>y3 : x0=x3 : x3=x2:  x2=x0 : y0=y3 : y3=y2 : y2=y0 :  EndIf 
Next bucle 

If y2 <> y1 
  dx1=(((x2-x1)<<#FP)/(y2-y1)) 
Else 
  dx1=((x2-x1)<<#FP) 
EndIf
 
If y3 <> y1 
  dx2=(((x3-x1)<<#FP)/(y3-y1)) 
Else 
  dx2=((x3-x1)<<#FP) 
EndIf 

If y3 <> y2 
  dx3=(((x3-x2)<<#FP)/(y3-y2)) 
Else 
  dx3=((x3-x2)<<#FP) 
EndIf 
       
scanleftx = x1 << #FP 
scanrightx = x1 << #FP 

If dx1 < dx2 
  leftadd=dx1 
  rightadd=dx2 
Else 
  leftadd=dx2 
  rightadd=dx1 
EndIf 

If y1 <> y2 
  For y = y1 To y2-1 
    beginx = scanleftx >> #FP 
    endx = scanrightx >> #FP 
    If endx-beginx > 0 
       LineXY(beginx, y , endx, y, RGB(255,255,255)) 
    EndIf 
    scanleftx + leftadd 
    scanrightx + rightadd 
  Next y 
Else
  scanleftx + leftadd 
  scanrightx + rightadd 
EndIf 

If dx2 > dx3 
  leftadd = dx2 
  rightadd = dx3 
Else 
  leftadd = dx3 
  rightadd = dx2 
EndIf 

If y2 <> y3 
  For y = y2 To y3 
    beginx = scanleftx >> #FP 
    endx = scanrightx >> #FP 
    If beginx <> endx
      LineXY(beginx, y , endx, y, RGB(255,255,255)) 
    EndIf 
    scanleftx + leftadd 
    scanrightx + rightadd 
  Next y 
EndIf 
  
EndProcedure 
  
Define WEvent, Quit 

If OpenWindow(0, 0, 0, 1024, 768, "Texture mapping", #PB_Window_SystemMenu|#PB_Window_ScreenCentered) 
  OpenWindowedScreen(WindowID(0), 0, 0, 1024, 768, 0, 0, 0) 
  Repeat 
    WEvent = WindowEvent() 
    If WEvent = #PB_Event_CloseWindow 
      Quit = #True 
    EndIf 
    StartDrawing(ScreenOutput()) 
       filltriangle(5+Random(1014),5+Random(758),5+Random(1014),5+Random(758),5+Random(1014),5+Random(758)) 
    StopDrawing() 
    FlipBuffers() 
    ClearScreen(0) 
    Delay(1) 
  Until Quit = #True  
  CloseWindow(0) 
EndIf

Are the issues I noticed perhaps rounding errors caused by the repeated shifts left and right of coordinate values? I'd like to extend your code to fill (rotated) rectangles, that's why I'm interested in getting this right before I move on.

Thanks for any help!

AndyX · Post by **AndyX** » Wed Jun 27, 2007 4:51 pm

you could get some more speed if you take the function calls like Plot() and Abs() out of the inner loops.

Edit: actually i´ve written something similar some time ago, with more stuff like 3D camera with rotation and movement, a terrain generator, perspective correct texture mapping, z-buffering,.. you can download it here: Test.zip
It is very buggy and slow, the source is not very readable (few comments etc.), but maybe some of you can use a bit of it.