check if a pixmap is a subrect of another

BlitzMax Forums/BlitzMax Programming/check if a pixmap is a subrect of another

nitti

(Posted 2012) [#1]

Hi

actual question:

what would be the fastest way of checking if an image/pixmap is also actually a subrect on another image/pixmap ?

context:
I am in the process of writing a texture atlas generator, it's working rather well. In my case I'll be having many pre-rendered rotated 'voxel' bodyparts as images.

because i plan to have bodyparts that are rolled/yawed/pitched and bones of a few lengths/shapes/dimensions the numbers add up very quickly.

so i had an idea to drastically cut down the amount of images in the atlas; start with saving bones images with the biggest length, and for each bone that is sort of the same but shorter -> check if the desired image would be an subimage of the bigger length bone image ...

oh and the actual rectpacking is working and might be usefull for someone:

SuperStrict

SeedRnd(MilliSecs())

Local packer:TRectanglePacker = TSimpleRectanglePacker.Create(768,768)
Local place:TPoint
Local shapeList:TList = CreateList()

prepareShapes(shapelist, packer, place)

Graphics 1024,768

While Not KeyDown(key_escape)
	Cls
	
	
	For Local s:TShape = EachIn shapelist
		SetColor s.r, s.g, s.b
		DrawRect s.x, s.y, s.w, s.h
	Next
	
	
	
	Flip

Wend

Function prepareShapes(shapelist:TList, packer:TRectanglePacker, place:TPoint)
	Local t:Int = MilliSecs()
	
	For Local i:Int = 0 Until 10000
		Local rectWidth:Int =Rand(4,10)
		Local rectHeight:Int =Rand(4,10)
		
		Local shape:TShape = TShape.Create(rectWidth, rectHeight)
		ListAddLast (shapeList, shape)
	Next
	
	
	SortList(shapelist, False, SortonHeight)

	Local count:Int = 0
	For Local s:TShape = EachIn shapelist
		
		If packer.tryPack(s.w,s.h, place)
			s.x = place.x
			s.y = place.y
			count:+1
		Else
			Throw("area full at "+count+" rectangles")
		EndIf
	
	Next
	
	Print (MilliSecs()-t)+" ms for "+count
EndFunction

Function SortOnHeight:Int(o1:Object, o2:Object)
    If TShape(o1).h < TShape(o2).h
        Return -1
    ElseIf TShape(o1).h > TShape(o2).h
        Return 1
    Else
        Return 0
    EndIf
End Function


Type TShape
	Field w:Int,h:Int
	Field x:Int,y:Int
	Field r:Int, g:Int, b:Int
	
	Function Create:TShape(w:Int,h:Int)
		Local ent:TShape = New TShape
		ent.w = w
		ent.h = h 
		ent.r = Rand(255)
		ent.g = Rand(255)
		ent.b = Rand(255)
		Return ent
		
	EndFunction
EndType

Type TPoint
	Global zero:TPoint = TPoint.Create(0,0)
	Field x:Int, y:Int
	
	Function Create:TPoint(x:Int, y:Int)
		Local ent:TPoint = New TPoint
		ent.x = x
		ent.y = y 
		Return ent
	EndFunction
EndType


Type TSimpleRectanglePacker Extends TRectanglePacker
	Field currentLine:Int
	Field lineHeight:Int
	Field column:Int
	
	Function Create:TSimpleRectanglePacker(packingAreaWidth:Int, packingAreaHeight:Int)
		Local ent:TSimpleRectanglePacker = New TSimpleRectanglePacker
		ent.packingAreaWidth = packingAreaWidth
		ent.packingAreaHeight = packingAreaHeight
		Return ent
	EndFunction
	
	Method tryPack:Int(rectangleWidth:Int, rectangleHeight:Int, placement:TPoint Var)
		' // If the rectangle is larger than the packing area in any dimension, it will never fit!
		If rectangleWidth > packingAreaWidth Or rectangleHeight > packingAreaHeight
			placement = TPoint.Zero
			Return False
		EndIf
		
		' // Do we have to start a new line ?
		If (column + rectangleWidth > packingAreaWidth)
			currentLine :+ lineHeight
			lineHeight = 0
			column = 0
		EndIf
		
		' // If it doesn't fit vertically now, the packing area is considered full
		If (currentLine + rectangleHeight > packingAreaHeight)
			placement = TPoint.Zero
			Return False
		EndIf
		
		'  // The rectangle appears to fit at the current location
		placement = TPoint.Create(column, currentLine)
		
		column:+rectangleWidth
		
		If rectangleHeight > lineheight Then lineHeight = rectangleHeight
		
		Return True
		
	EndMethod
	 
	
EndType

Type TRectanglePacker
	Field packingAreaWidth:Int
	Field packingAreaHeight:Int
	
	Method pack:TPoint(rectWidth:Int, rectHeight:Int)
		Local placement:TPoint = New Tpoint
		
		If Not tryPack(rectWidth, rectHeight, placement)
			Throw("rectangle doesn't fit")
		Else
			Return placement
		EndIf
	EndMethod
	
	Method tryPack:Int(rectWidth:Int, rectHeight:Int, placement:TPoint Var)
	EndMethod
EndType

on my system it packs 10000 images in 18 ms, very neatly packed also