Rectangle Drawing Optimisation

Take this example (2 cases):



If you were drawing these rects as filled rects of the same colour, instead of drawing two whole rectangles you could optimise the number of pixels drawn to be only the total area (to avoid drawing the same pixels twice). In case 1 you would need two rectangles (a slightly shorter top one and a full size bottom one). In case2, you would need 3 vertical rectangles (I know you could do it horizontally too), I have included dotted lines to show what I mean.

Has anyone got any algorithms to do this or can you suggest a way to do it very quickly. If the algorithm is too slow there won't be any point in applying the optimisation. Also I guess this is better on bigger rectangles as if they are too small, splitting them into (up to 50%) more smaller ones could have a drawing overhead just based on more "For x/y" loops being iterated through in the drawing code.

Look forward to your ideas.

You should expand the area to encompass the two rectangles. Why? Don't assume you will only have two rects overlapping - It's quicker mathematically and it's quicker to draw (1 draw command instead of 3 or more). Dirty Rects are done that way for a reason - it's better :D

All these optimisations are really crappy. You won't get speedups like that.

When blitting or doing large drawing like rects, doing less rects is better than doing more rects, despite how much screen they cover. Same for Drawimage. It is better to do less calls to drawimage and draw larger images than doing lots of little draws.

You're optimising stuff that does not matter.

If stuff is slow, then think about a whole paradigm change rather than tiny optimisations here and there which make no difference on todays hardware...

Ultimately you should only do any optimising when the game is finished anyway. Cos chances are if you aint gonna finish it, all this is wasting your time.

Thing is Rob, you can't have two areas overlapping as you'll get stange results when doing stuff with blend modes.

This is a software render in Blitzplus remember, you don't want to re-calculate the alpha of every pixel every frame when only 1 object moved do you.

Grey...

There is an algorithm to do it because I have done such a thing before ( a few years ago actually).

1. Cordon off the whole area of the two rects. Take the MinX, MinY, MaxX and MaxY of the area.

2. Use a scanning function starting at MinX,MinY then simply check if that point is within the area of a rectangle within. If it is, then plot it.

3. Move onto the next point minX+1, MinY etc... Continue until the whole area is done.

Points to note: This method will ensure that you only plot once at a certain point. To increase the speed you can copy a valid plot point (x & y) into an array (instead of plotting) then when scanning has finished you simply read the array and plot all the valid points in one go.

Point taken Tim, didn't think of that.

Prof, I understand your method but it's a bit loop intensive. I just wanted to work out how to split the rects into two/three smaller non overlapping rects i.e. end up with two/three sets of rect coords (x,y,w,h) that's all.

One Eyed Jack: I need to get the opmisations in now because the game engine (+title/menus/basic gameplay/sound/music) is done, I just need to add extra graphics and gameplay elements, but I don't want to have to redo that code later. I wanted to get the optimised engine in place now to save time in the long run. Forget "today's hardware"! The game needs to run on machines maybe 5 or more years old e.g. 500MHz PCs with no 3D card = BIG MARKET. My 3.2GHz PC can handle pretty much anything I can throw at it in Blitz but without dirty rects a 1GHz PC is borderline if it will drop frames and as for any less forget it, unless optimisations are made. The main optimisation I made was Dirty Rects full stop, this one might not make a massive difference but I'd thought I'd try it and see.

Also, yes in theory too many rects will slow down BUT remember that it's NOT doing a straight mem copy because it's going from a 24bit graphics buffer to a 32bit graphics buffer thus the CPU can do a batch mem copy it has to read 3 bytes, write 3 bytes and move the souce pointer by 3 and the dest pointer by 4. If you can reduce the amount of pixel read/writes by 20% or more by a bit of simple maths then it really should be faster unless the rects are really small (as I've already said).

Tim: I know I could do a bounding rect (and I see why it's useful) but as with the above point the CPU isn't doing a straight mem copy so a "bad" bounding rect could be very inefficient. Imagine a tall rect overlapping a long horiz rect, the bounding box could be a massive square yet the two rects may only be pixels wide!

I understand where you're coming from GA. Are there really that many people with P3 500's who are willing to pay for a game that will run on it?

I'm not disagreeing, I'd just like to know where the stats come from. I've never really thought about designing a game around a target market, perhaps I should...?

Well P3 500 is maybe a slight exageration but think of all the unoptimised Dells out there for example with no 3D card maybe 3-5 years old. Kids have them, old ladies have them, offices have them! Win98, not enough RAM etc. Plenty of people of these forums have 1GHz or thereabouts machines.

"I've never really thought about designing a game around a target market, perhaps I should" WEll that's pretty much the first rule of business (specifically marketing and sales). Identify target market, make the product for the market, not the other way round.

Grey, Simple - Don't make big long images :D

haha, oK what about lots of square images all overlapping in a giant L shape ;-p

Now why would they want to do that? One other thing - when objects are moving at a fair rate you really don't need to blend them - no one will notice.

I check on my game if you follow one with your eyes you can see the pixels but yes it's hard. However you can PAUSE the game and then all the horridy pixels show up. However, I'm not gonna alphablend all the bojects anyway just the particle effects and scores etc, that will use enough CPU time. The code above is really gonna be just to get the ordinary Blitz Drawing code fast enough for a wider platform of machines.

I'm certain this can be simplified. I'm also certain it could be made more elegant - sorry, I didn't get much sleep last night. Also, please excuse my use of a keyword as a type name. ;)

Type Rect
	Field x1, y1, x2, y2
	Field r, g, b
End Type

Function rect_new.Rect(x1=0, y1=0, x2=0, y2=0, red=0, g=1, b=1)
	r.Rect = New Rect
	If x1 > x2 Then temp = x2 : x2 = x1 : x1 = temp
	If y1 > y2 Then temp = y2 : y2 = y1 : y1 = temp
	r\x1 = x1 : r\y1 = y1 : r\x2 = x2 : r\y2 = y2
	r\r = red : r\g = g : r\b = b
	Return r
End Function

Function math_max(a, b)
  If a > b Then Return a Else Return b
End Function

Function math_min(a, b)
  If a < b Then Return a Else Return b
End Function

Function optimize_rects.Rect(r1.Rect, r2.Rect)

	If Not((r1\x1 < r2\x2) And (r1\x2 > r2\x1) And (r1\y1 < r2\y2) And (r1\y2 > r2\y1)) Then Return Null

	If r2\x1 < r1\x1 Then temp.Rect = r2 : r2 = r1 : r1 = temp
	; r2 is horizontally inset in r1
	If r2\x2 < r1\x2 Then
		r3.Rect = rect_new(r2\x2, r1\y1, r1\x2, r1\y2)
		r1\x2 = r2\x1
		r2\y1 = math_min(r1\y1, r2\y1)
		r2\y2 = math_max(r1\y2, r2\y2)
		Return r3
	EndIf

	If r2\y1 < r1\y1 Then temp.Rect = r2 : r2 = r1 : r1 = temp
	; r2 is vertically inset in r1
	If r2\y2 < r1\y2 Then
		r3.Rect = rect_new(r1\x1, r2\y2, r1\x2, r1\y2)
		r1\y2 = r2\y1
		r2\x1 = math_min(r1\x1, r2\x1)
		r2\x2 = math_max(r1\x2, r2\x2)
		Return r3
	EndIf

	; diag solution
	If r2\y1 < r1\y1 Then temp.Rect = r2 : r2 = r1 : r1 = temp
	r3.Rect = rect_new(math_min(r1\x1, r2\x1), math_max(r1\y1, r2\y1), math_max(r1\x2, r2\x2), math_min(r1\y2, r2\y2))
	r1\y2 = r3\y1
	r2\y1 = r3\y2
	Return r3
End Function

Function show_rects(solid)
	If solid = True Then brightness = 63 Else brightness = 255
	For r.Rect = Each Rect
		Color brightness*r\r, brightness*r\g, brightness*r\b
		Rect(r\x1, r\y1, r\x2-r\x1, r\y2-r\y1, solid)
	Next
End Function



Graphics 800, 600

While Not(KeyHit(1))
	
	r1.Rect = rect_new(Rand(0, 800), Rand(0, 600), Rand(0, 800), Rand(0, 600), 0, 0, 1)
	r2.Rect = rect_new(Rand(0, 800), Rand(0, 600), Rand(0, 800), Rand(0, 600), 0, 1, 0)
	show_rects(True)
	r3.Rect = optimize_rects(r1, r2)
	show_rects(False)

	WaitKey
	Cls

	Delete r1
	Delete r2
	If r3 <> Null Then Delete r3

Wend

There are further optimizations to be done. Sometimes a third rectangle isn't necessary. Hell, sometimes a second rectangle isn't necessary! Hopefully this should get you going though! :)

Grey, don't forget that if you use the splitting rectangle method it will slow right down if the second rectangle is higher than the first one you drew. Remember that it is best to draw in Y order so that you can draw as much as possible with the sunchronization of the display.

My method is a bit loop intensive as you say but that is not what slows the operation down - its the drawing that slows things down. Thats why the scanning method that I mentioned might be a better alternative because it will always draw from the Minimum Y coordinate to the Maxaimum Y coordinate - keeping things fast!

Use writepixelfast to make it even faster.

wow, that's REALLY neat Octothope, it just needs a flip after show_rects(False) in fullscreen mode!
Now all I gotta do is understand it! Then bug test it.

I notice it always makes 3 rects though, it never bothers with my case 1 which only requires two really. [edi]t oh yeah you said that already.

Thanks

Yeah thanks prof, although as Blitz uses double buffering the 'drawing in Y order to avoid the current raster line' is not an issue, but I would tend to draw that way anyway from habit :-)

Yeah this is the one! Now how would I invert the selection?

I'm too tired to answer that (see how I cunningly avoided saying I don't know) ;-)

Dirty Rects... is that a gay porno? :P

ROFL, you made my day big10p.

Anyone?