Create filled triangles line by line

Blitz3D Forums/Blitz3D Programming/Create filled triangles line by line

Axel Wheeler

(Posted 2011) [#1]

Here is a CreateTriangle() function that should be quicker than the pixel-by-pixel approach used by the functions that work for all polygons. This one's just for triangles.

There may already be one in the archives, but I did this partly as an exercise so here it is anywayj:

;DrawTriangle code

Local x0,y0,x1,y1,x2,y2
Graphics3D(1024,768,32,2)
SetBuffer(FrontBuffer())
Print "Press any key to create a new triangle, or press Esc to exit."

While Not KeyHit(1)
	;Create three random points
	x0=Rand(GraphicsWidth())
	y0=Rand(GraphicsHeight())
	x1=Rand(GraphicsWidth())
	y1=Rand(GraphicsHeight())
	x2=Rand(GraphicsWidth())
	y2=Rand(GraphicsHeight())
	
	;Pick a random color
	Color(Rnd(255),Rnd(255),Rnd(255))
	
	;Draw that mofo
	DrawTriangle(x0,y0,x1,y1,x2,y2,1)
	
	WaitKey()
Wend

Function DrawTriangle(x0#,y0#,x1#,y1#,x2#,y2#,filled=0)
	If filled=1
		
		;Filled triangle
		Local Ya#=y0,Xa#=x0,Yb#=y1,Xb#=x1,Yc#=y2,Xc#=x2,x,y,proportionA#,ProportionB#,Xlong,Xshort,Xtemp#,Ytemp#
		
	;Here we sort the three points from highest (Xa,Ya) to lowest (Xc,Yc).  This sorting routine does that.
		If Yb<Ya
			Xtemp=Xa
			Ytemp=Ya
			Xa=Xb
			Ya=Yb
			Xb=Xtemp
			Yb=Ytemp
		EndIf
		
		If Yc<Ya 
			Xtemp=Xa
			Ytemp=Ya
			Xa=Xc
			Ya=Yc
			Xc=Xtemp
			Yc=Ytemp
		EndIf
		
		If Yc<Yb
			Xtemp=Xb
			Ytemp=Yb
			Xb=Xc
			Yb=Yc
			Xc=Xtemp
			Yc=Ytemp
		EndIf
		
	;Now, for each y value between the topmost point and the bottommost point, draw horizontal lines with interpolated x values
		For y=Ya To Yc
			
		;One side will go from the top point to the bottom point.  Xlong is the interpolated x value on this line
			If Yc=Ya Then Yc=Yc+.00001  ;This line prevents a division by zero issue
			proportionA#=(y-Ya)/(Yc-Ya)
			Xlong=Xa+(Xc-Xa)*proportionA
			
			If y<Yb
				
			;For y values above the middle point, interpolate Xshort
				If Yb=Ya Then Yb=.00001  ;This line prevents a division by zero issue
				ProportionB#=(y-Ya)/(Yb-Ya)
				Xshort=Xa+(Xb-Xa)*ProportionB
				
			Else
				
			;For values below the middle point, interpolate Xshort
				If Yc=Yb Then Yc=.00001  ;This line prevents a division by zero issue
				ProportionB#=(y-Yb)/(Yc-Yb)
				Xshort=Xb+(Xc-Xb)*ProportionB
				
			EndIf
			
		;Draw a horizontal line on y from Xlong to Xshort.
			Line(Xlong,y,Xshort,y)
			
		Next
		
	Else
		
		;Unfilled triangle
		Line(x0,y0,x1,y1)
		Line(x1,y1,x2,y2)
		Line (x2,y2,x0,y0)
		
	EndIf
End Function

Yasha

(Posted 2011) [#2]

Ooo, a challenge! I say pixel-by-pixel can be fast...

;DrawTriangle code

Local x0,y0,x1,y1,x2,y2
Graphics3D(1024,768,32,2)
SetBuffer(FrontBuffer())
Print "Press any key to create a new triangle, or press Esc to exit."

While Not KeyHit(1)
	;Create three random points
	x0=Rand(GraphicsWidth())
	y0=Rand(GraphicsHeight())
	x1=Rand(GraphicsWidth())
	y1=Rand(GraphicsHeight())
	x2=Rand(GraphicsWidth())
	y2=Rand(GraphicsHeight())
	
	;Pick a random color
	Color(Rnd(255),Rnd(255),Rnd(255))
	Local pixel = $FF000000 Or (ColorRed() Shl 16) Or (ColorGreen() Shl 8) Or ColorBlue()
	
	Local i, start
	
	start=MilliSecs()
	For i=1 To 200
		;Draw that mofo
		DrawTriangle1(x0,y0,x1,y1,x2,y2,1)
	Next
	Print MilliSecs()-start
	
	start=MilliSecs()
	For i=1 To 200
		DrawTriangle2(pixel, x0, x1, x2, y0, y1, y2)
	Next
	Print MilliSecs()-start
	
	WaitKey()
Wend

Function DrawTriangle1(x0#,y0#,x1#,y1#,x2#,y2#,filled=0)
	If filled=1
		
		;Filled triangle
		Local Ya#=y0,Xa#=x0,Yb#=y1,Xb#=x1,Yc#=y2,Xc#=x2,x,y,proportionA#,ProportionB#,Xlong,Xshort,Xtemp#,Ytemp#
		
	;Here we sort the three points from highest (Xa,Ya) to lowest (Xc,Yc).  This sorting routine does that.
		If Yb<Ya
			Xtemp=Xa
			Ytemp=Ya
			Xa=Xb
			Ya=Yb
			Xb=Xtemp
			Yb=Ytemp
		EndIf
		
		If Yc<Ya 
			Xtemp=Xa
			Ytemp=Ya
			Xa=Xc
			Ya=Yc
			Xc=Xtemp
			Yc=Ytemp
		EndIf
		
		If Yc<Yb
			Xtemp=Xb
			Ytemp=Yb
			Xb=Xc
			Yb=Yc
			Xc=Xtemp
			Yc=Ytemp
		EndIf
		
	;Now, for each y value between the topmost point and the bottommost point, draw horizontal lines with interpolated x values
		For y=Ya To Yc
			
		;One side will go from the top point to the bottom point.  Xlong is the interpolated x value on this line
			If Yc=Ya Then Yc=Yc+.00001  ;This line prevents a division by zero issue
			proportionA#=(y-Ya)/(Yc-Ya)
			Xlong=Xa+(Xc-Xa)*proportionA
			
			If y<Yb
				
			;For y values above the middle point, interpolate Xshort
				If Yb=Ya Then Yb=.00001  ;This line prevents a division by zero issue
				ProportionB#=(y-Ya)/(Yb-Ya)
				Xshort=Xa+(Xb-Xa)*ProportionB
				
			Else
				
			;For values below the middle point, interpolate Xshort
				If Yc=Yb Then Yc=.00001  ;This line prevents a division by zero issue
				ProportionB#=(y-Yb)/(Yc-Yb)
				Xshort=Xb+(Xc-Xb)*ProportionB
				
			EndIf
			
		;Draw a horizontal line on y from Xlong to Xshort.
			Line(Xlong,y,Xshort,y)
			
		Next
		
	Else
		
		;Unfilled triangle
		Line(x0,y0,x1,y1)
		Line(x1,y1,x2,y2)
		Line (x2,y2,x0,y0)
		
	EndIf
End Function

Function DrawTriangle2(pixel,trix0,trix1,trix2,triy0,triy1,triy2)
	Local c0,c1,c2,cx0,cx1,cx2,cy0,cy1,cy2
	Local dx01,dx12,dx20,dy01,dy12,dy20
	Local x,y,minx,miny,maxx,maxy
	
	minx=TriMin(trix0,trix1,trix2)
	miny=TriMin(triy0,triy1,triy2)
	maxx=TriMax(trix0,trix1,trix2)
	maxy=TriMax(triy0,triy1,triy2)
	
	dx01=trix0-trix1:dy01=triy0-triy1
	dx12=trix1-trix2:dy12=triy1-triy2
	dx20=trix2-trix0:dy20=triy2-triy0
	
	c0=dy01 * trix0 - dx01 * triy0
	c1=dy12 * trix1 - dx12 * triy1
	c2=dy20 * trix2 - dx20 * triy2
	
	If dy01<0 Or (dy01=0 And dx01>0) Then c0=c0+1
	If dy12<0 Or (dy12=0 And dx12>0) Then c1=c1+1
	If dy20<0 Or (dy20=0 And dx20>0) Then c2=c2+1
	
	cy0=c0 + dx01 * miny - dy01 * minx
	cy1=c1 + dx12 * miny - dy12 * minx
	cy2=c2 + dx20 * miny - dy20 * minx
	
	LockBuffer
	For y=miny To maxy
		cx0=cy0
		cx1=cy1
		cx2=cy2
		
		For x=minx To maxx
			
			If cx0 >= 0
				If cx1 >= 0
					If cx2 >= 0
						WritePixelFast x,y,pixel
					EndIf
				EndIf
			EndIf
			
			cx0=cx0-dy01
			cx1=cx1-dy12
			cx2=cx2-dy20
			
		Next
		
		cy0=cy0+dx01
		cy1=cy1+dx12
		cy2=cy2+dx20
	Next
	UnlockBuffer
End Function

Function TriMin(a,b,c)
    If a<b
        If a<c Then Return a:Else Return c
    Else
        If b<c Then Return b:Else Return c
    EndIf
End Function

Function TriMax(a,b,c)
    If a>b
        If a>c Then Return a:Else Return c
    Else
        If b>c Then Return b:Else Return c
	EndIf
End Function

Although I'm cheating, I already had that lying around.

Last edited 2011

Axel Wheeler

(Posted 2011) [#3]

Two points:

1. Some of your triangles aren't actually being drawn, at least on my screen. When I change

		DrawTriangle1(x0,y0,x1,y1,x2,y2,1)

		DrawTriangle1(x0,y0,x1,y1,x2,y2,0)

most of the triangles don't appear. When they do (triangles 2 and 5, for example) the speed difference is less, but still considerable. However,

2. The reason is LockBuffer, which I just discovered makes a huge difference on ordinary drawing commands, like Line. (I thought it was just for WritePixelFast and such.)

With the changes below CreateTriangle1 is faster on 2 and 5 at least. Still, CreateTriangle2 is pretty fast considering it's point-by-point... ;-)

;DrawTriangle code

Local x0,y0,x1,y1,x2,y2
Graphics3D(1024,768,32,2)
SetBuffer(FrontBuffer())
Print "Press any key to create a new triangle, or press Esc to exit."

While Not KeyHit(1)
	;Create three random points
	x0=Rand(GraphicsWidth())
	y0=Rand(GraphicsHeight())
	x1=Rand(GraphicsWidth())
	y1=Rand(GraphicsHeight())
	x2=Rand(GraphicsWidth())
	y2=Rand(GraphicsHeight())
	
	;Pick a random color
	Color(Rnd(255),Rnd(255),Rnd(255))
	Local pixel = $FF000000 Or (ColorRed() Shl 16) Or (ColorGreen() Shl 8) Or ColorBlue()
	
	Local i, start
	
	start=MilliSecs()
	For i=1 To 200
		;Draw that mofo
		DrawTriangle1(x0,y0,x1,y1,x2,y2,1)
	Next
	Print MilliSecs()-start
	
	start=MilliSecs()
	For i=1 To 200
		DrawTriangle2(pixel, x0, x1, x2, y0, y1, y2)
	Next
	Print MilliSecs()-start
	
	WaitKey()
Wend

Function DrawTriangle1(x0#,y0#,x1#,y1#,x2#,y2#,filled=0)
	If filled=1
		
		;Filled triangle
		Local Ya#=y0,Xa#=x0,Yb#=y1,Xb#=x1,Yc#=y2,Xc#=x2,x,y,proportionA#,ProportionB#,Xlong,Xshort,Xtemp#,Ytemp#
		
	;Here we sort the three points from highest (Xa,Ya) to lowest (Xc,Yc).  This sorting routine does that.
		If Yb<Ya
			Xtemp=Xa
			Ytemp=Ya
			Xa=Xb
			Ya=Yb
			Xb=Xtemp
			Yb=Ytemp
		EndIf
		
		If Yc<Ya 
			Xtemp=Xa
			Ytemp=Ya
			Xa=Xc
			Ya=Yc
			Xc=Xtemp
			Yc=Ytemp
		EndIf
		
		If Yc<Yb
			Xtemp=Xb
			Ytemp=Yb
			Xb=Xc
			Yb=Yc
			Xc=Xtemp
			Yc=Ytemp
		EndIf
		
	;Now, for each y value between the topmost point and the bottommost point, draw horizontal lines with interpolated x values
		LockBuffer()
		For y=Ya To Yc
			
		;One side will go from the top point to the bottom point.  Xlong is the interpolated x value on this line
			If Yc=Ya Then Yc=Yc+.00001  ;This line prevents a division by zero issue
			proportionA#=(y-Ya)/(Yc-Ya)
			Xlong=Xa+(Xc-Xa)*proportionA
			
			If y<Yb
				
			;For y values above the middle point, interpolate Xshort
				If Yb=Ya Then Yb=.00001  ;This line prevents a division by zero issue
				ProportionB#=(y-Ya)/(Yb-Ya)
				Xshort=Xa+(Xb-Xa)*ProportionB
				
			Else
				
			;For values below the middle point, interpolate Xshort
				If Yc=Yb Then Yc=.00001  ;This line prevents a division by zero issue
				ProportionB#=(y-Yb)/(Yc-Yb)
				Xshort=Xb+(Xc-Xb)*ProportionB
				
			EndIf
			
		;Draw a horizontal line on y from Xlong to Xshort.
			Line(Xlong,y,Xshort,y)
			
		Next
		UnlockBuffer()
	Else
		
		;Unfilled triangle
		Line(x0,y0,x1,y1)
		Line(x1,y1,x2,y2)
		Line (x2,y2,x0,y0)
		
	EndIf
End Function

Function DrawTriangle2(pixel,trix0,trix1,trix2,triy0,triy1,triy2)
	Local c0,c1,c2,cx0,cx1,cx2,cy0,cy1,cy2
	Local dx01,dx12,dx20,dy01,dy12,dy20
	Local x,y,minx,miny,maxx,maxy
	
	minx=TriMin(trix0,trix1,trix2)
	miny=TriMin(triy0,triy1,triy2)
	maxx=TriMax(trix0,trix1,trix2)
	maxy=TriMax(triy0,triy1,triy2)
	
	dx01=trix0-trix1:dy01=triy0-triy1
	dx12=trix1-trix2:dy12=triy1-triy2
	dx20=trix2-trix0:dy20=triy2-triy0
	
	c0=dy01 * trix0 - dx01 * triy0
	c1=dy12 * trix1 - dx12 * triy1
	c2=dy20 * trix2 - dx20 * triy2
	
	If dy01<0 Or (dy01=0 And dx01>0) Then c0=c0+1
	If dy12<0 Or (dy12=0 And dx12>0) Then c1=c1+1
	If dy20<0 Or (dy20=0 And dx20>0) Then c2=c2+1
	
	cy0=c0 + dx01 * miny - dy01 * minx
	cy1=c1 + dx12 * miny - dy12 * minx
	cy2=c2 + dx20 * miny - dy20 * minx
	
	LockBuffer
	For y=miny To maxy
		cx0=cy0
		cx1=cy1
		cx2=cy2
		
		For x=minx To maxx
			
			If cx0 >= 0
				If cx1 >= 0
					If cx2 >= 0
						WritePixelFast x,y,pixel
					EndIf
				EndIf
			EndIf
			
			cx0=cx0-dy01
			cx1=cx1-dy12
			cx2=cx2-dy20
			
		Next
		
		cy0=cy0+dx01
		cy1=cy1+dx12
		cy2=cy2+dx20
	Next
	UnlockBuffer
End Function

Function TriMin(a,b,c)
    If a<b
        If a<c Then Return a:Else Return c
    Else
        If b<c Then Return b:Else Return c
    EndIf
End Function

Function TriMax(a,b,c)
    If a>b
        If a>c Then Return a:Else Return c
    Else
        If b>c Then Return b:Else Return c
	EndIf
End Function

Matty

(Posted 2011) [#4]

So are we going to see a software renderer soon, now that we can draw triangles quickly...

Yasha

(Posted 2011) [#5]

I thought it was just for WritePixelFast and such.

Same here. That's an interesting discovery!

And... yeah at one time I thought it would be fun to try working on a software renderer, but didn't get much further than trying to texture triangles. It just seems a bit pointless given that a B3D one wouldn't be usable, while even mobile devices now have hardware 3D. (If I'm lucky, the triangles not being drawn had the wrong "spin", i.e. backfaces - otherwise I guess my triangle routine is broken.)

That said, Devil's Child made one a while back. Try searching for VirtualGL.

Charrua

(Posted 2011) [#6]

use that searcher
(sure you know it!)

http://blitzbasic.com/Community/posts.php?topic=88773#1007957

Juan

bytecode77

(Posted 2011) [#7]

you might all want to check out this:

http://stuff.dev-ch.de/index.php?loc=13

my software renderer entirely written in Blitz. there is also a c++ version, which is about 10x faster

Last edited 2011

Yasha

(Posted 2011) [#8]

That is extremely cool.

You've got my attention with the C++ one. Software rendering is cool... fast software rendering is awesome!

Kryzon

(Posted 2011) [#9]

There's also the Ray SoftwareRenderer from the SoftPixel engine: http://softpixelengine.sourceforge.net/softwarerenderer.html

For C, comes with source.

Last edited 2011

bytecode77

(Posted 2011) [#10]

thanks :)
my c++ software renderer also supports stencil shadows, see:

Warner

(Posted 2011) [#11]

That's really cool.. Looks great

Yasha

(Posted 2011) [#12]

What's the licence on that (specifically, on the source)?

I for one want to look through it and learn something, but without a licence tag...

bytecode77

(Posted 2011) [#13]

everything there is open source, so free to use and modify. if you use complete parts of the code, i would appreciate a comment with my name and a link to the page.
but yes, it's free.

Yasha

(Posted 2011) [#14]

Thanks, that's very generous.

Andy_A

(Posted 2011) [#15]

@Axel Wheeler, can I use your fill triangle function, as part of an entry of my code, in the Code Archive?

In other words, since the Code Archive is strictly Public Domain code can I use your function, in my function which will be posted as Public Domain code?

Proper credits will be posted in the code at the top of listing and at the location of the triangle fill function.

Nevermind. I used something else.

Last edited 2011