Filled Triangles

BlitzPlus Forums/BlitzPlus Programming/Filled Triangles

Cold Harbour

(Posted 2004) [#1]

Anyone know a technique to draw filled 2D triangles. Specifically right angled tris.

At the moment I have a ridiculously slow bit of code that uses trig to slowly go up the hypotenuse of a triangle one pixel at a time and then draws a line down to the base line.

It works but is terrible slow – I have to draw about 1000 triangle per flip (don’t ask).

Any know a better way? If I search the web I just get information about DirectX triangles and this obviously isn’t what I want.

Thanks!

skidracer

(Posted 2004) [#2]

Try searching the Code Archives for entries such as :

http://www.blitzbasic.com/codearcs/codearcs.php?code=136

Cold Harbour

(Posted 2004) [#3]

Yeah I saw that. It doesn't work on my PC but from the code it looks like he's using the same method as me.

Rottbott

(Posted 2004) [#4]

Maybe it would be faster to just draw three Lines and use a flood fill function?

sswift

(Posted 2004) [#5]

I don't know why his function would fail to work on your PC, but try this demo. I wrote a custom loop for drawing the pixels manually to a locked buffer. It's 3x faster on average than the original. I have my doubts that you could make it much faster. I have no idea why Simon used that slow rect function in the original. :-) I didn't try the line function though because presumably that would be even slower than the rect fill function.

You might be able to get 10fps with this version, assuming you don't have much overdraw. I've heard Blitzplus is much faster though at 2D drawing operations than Blitz 3D which is what I tested in. So that might give you a more reasonable rate.

Dim xval(20)
Dim yval(20)

Graphics 640,480

SetBuffer BackBuffer()

Color 255,0,255

T1 = MilliSecs()
For Loop = 0 To 1000
	Triangle(-10,-10, 180,20, 230,220)
Next
T2 = MilliSecs()


T3 = MilliSecs()
For Loop = 0 To 1000
	FastTriangle(-10,-10, 180,20, 230,220)
Next
T4 = MilliSecs()


Color 255,255,255
Text 16, 16, T2-T1
Text 16, 32, T4-T3


Flip
WaitKey
End



Function Triangle(x0,y0,x1,y1,x2,y2)
	xval(0)=x0
	yval(0)=y0
	xval(1)=x1
	yval(1)=y1
	xval(2)=x2
	yval(2)=y2
	poly(3)
End Function

Function FastTriangle(x0,y0,x1,y1,x2,y2)
	xval(0)=x0
	yval(0)=y0
	xval(1)=x1
	yval(1)=y1
	xval(2)=x2
	yval(2)=y2
	FastPoly(3)
End Function

Function Quad(x0,y0,x1,y1,x2,y2,x3,y3)
	xval(0)=x0
	yval(0)=y0
	xval(1)=x1
	yval(1)=y1
	xval(2)=x2
	yval(2)=y2
	xval(3)=x3
	yval(3)=y3
	poly(4)
End Function

Function poly(vcount)

; get clipping region
	width=GraphicsWidth()
	height=GraphicsHeight()
; find top verticy
	b=vcount-1
	y=yval(0)
	While c<>b
		c=c+1
		yy=yval(c)
		If yy<y y=yy d=c
	Wend
	c=d 
	t=c
; draw top to bottom
	While y<height
; get left gradient
		If y=yval(c)
			While y=yval(c)
				x0=xval(c) Shl 16
				c=c+1
				If c>b c=a
				If c=t Return
				If y>yval(c) Return
			Wend
			h=yval(c)-y
			g0=((xval(c) Shl 16)-x0)/h
		EndIf
; get right gradient
		If y=yval(d)
			While y=yval(d)
				x1=xval(d) Shl 16
				d=d-1
				If d<a d=b
				If y>yval(d) Return
			Wend
			h=yval(d)-y
			g1=((xval(d) Shl 16)-x1)/h
		EndIf
; calc horizontal span
		x=x1 Sar 16
		w=((x0 Sar 16)-x)+1
; draw down to next vert
		If (w>0 And y>-1 And x<width And x+w>0)
			If x<0 w=w+x x=0	;crop left
			If x+w>width w=width-x	;crop right
			Rect x,y,w,1
		EndIf
; next	
		x0=x0+g0
		x1=x1+g1
		y=y+1
	Wend
End Function



Function FastPoly(vcount)

	RGBColor = ColorBlue() Or (ColorGreen() Shl 8) Or (ColorRed() Shl 16) Or ($ff000000)

	; get clipping region
	width=GraphicsWidth()
	height=GraphicsHeight()
	
	; Lock the current drawing buffer.
	LockBuffer()
	
	; find top verticy
	b=vcount-1
	y=yval(0)
	While c<>b
		c=c+1
		yy=yval(c)
		If yy<y y=yy d=c
	Wend
	c=d 
	t=c

	; draw top to bottom
	While y<height
		
		; get left gradient
		If y=yval(c)
			While y=yval(c)
				x0=xval(c) Shl 16
				c=c+1
				If c>b c=a
				If c=t Goto Finish
				If y>yval(c) Goto Finish
			Wend
			h=yval(c)-y
			g0=((xval(c) Shl 16)-x0)/h
		EndIf

		; get right gradient
		If y=yval(d)
			While y=yval(d)
				x1=xval(d) Shl 16
				d=d-1
				If d<a d=b
				If y>yval(d) Goto Finish
			Wend
			h=yval(d)-y
			g1=((xval(d) Shl 16)-x1)/h
		EndIf

		; calc horizontal span
		x=x1 Sar 16
		w=((x0 Sar 16)-x)+1

		; draw down to next vert
		If (w > 0) And (y > -1) And (x < width) And ((x+w) > 0)
	
			;crop left
			If x < 0 
				w=w+x
				x=0		
			EndIf
			
			;crop right
			If (x+w) > width
				w=width-x
			EndIf	
			
			; Draw scanline.
			For Lx = x To (x+w)
				WritePixelFast Lx, y, RGBColor
			Next
			
		EndIf
		
		; next	
		x0=x0+g0
		x1=x1+g1
		y=y+1
		
	Wend

	.Finish
	
	; Unlock the draw buffer.
	UnlockBuffer()
	
End Function

Cold Harbour

(Posted 2004) [#6]

Thanks sswift, interesting idea using a locked buffer.

Since I only need right angled triangles I can simplify your code a lot as there’s only one gradient to calculate. Can’t say I understand how you’re finding the gradient using all that bit shifting. I’m using trig myself.

Is TAN() quite slow in Blitz+?

Also, what’s faster, drawing lines or drawing filled rectangles?

Cheers!

sswift

(Posted 2004) [#7]

Don't ask me how the gradient is found, ask Simon. I coudln't easily figure out what the heck he was doing, and I didn't feel like investing the time trying to understand it. All I did check was to make sure that he was rasterizing it properly, drawing each horizontal scanline once, and clipping at the borders of the screen, and he appears to have done that, so I have to assume it's pretty fast. :-) I think he's using bresenham's line drawing algorithm but I'd have to study that algoithm and his code in depth to be sure.

Why use bresenham instead of Tan? Well, it USED to be faster to use fixed point math rather than floating point, but now... Well, there's not really a good reason to use it. It's much slower to draw the lines than to calculate where to put the next pixel.

Theoretically drawing filled rectangles should be much faster than drawing arbitrary lines. But the lines I draw aren't arbitrary, they're horizontal. Still, it's odd that Blitz's rect function, written in C, is slower than my function coded in Blitz. Drawing a rect one pixel wide should not be noticeably slower than drawing a horizontal line.

Cold Harbour

(Posted 2004) [#8]

Once again, thanks sswift. The only way I’ll really know what’s faster is to write test programs and time them - rather then ask arbitrary “What’s faster x or y?” questions.

skidracer

(Posted 2004) [#9]

To run my test code in BlitzPlus you need to add a Flip command before the WaitKey.

Sswift, if you remove your buffer locking and lock the buffer for the whole test like so, you're code doesn't look so fast:

LockBuffer()


T1 = MilliSecs()
For Loop = 0 To 1000
	Triangle(-10,-10, 180,20, 230,220)
Next
T2 = MilliSecs()


T3 = MilliSecs()
For Loop = 0 To 1000
	FastTriangle(-10,-10, 180,20, 230,220)
Next
T4 = MilliSecs()

UnlockBuffer()