Pixmap edges and normals

This code has been declared by its author to be Public Domain code.

Pixmap edges and normals by TWH

2010

Quite fast. A 200x200 bitmap took 4ms on my PC in release, 50ms in debug.

This is somewhat similar to the heighmap contour finder by Malice, available here:
http://www.blitzbasic.com/codearcs/codearcs.php?code=2762

except, this is for 2D games and finds normals. Useful for resolving collisions.

You could use it in a worms- or Liero-like game, updating edges and normals each time the terrain is modified.

Or you could use it to calc the collision map and normals of a bitmap game object once and store it.

Edit: found a bug. normals for single pixels and 1-pixel thick lines are not found. Will fix in the morning.

'written by torbjoern haugen 7.september 2010
'based on pseudo-code from "Mathematics and Physics for Programmmers by Danny Kodicek"
'expects the bitmap to be black and white
type TimageNormals
	field originalImage:TPixmap
	field edgemap:int[] 'is pixel a edge? true/false
	field normals:vec2[]
	field smoothedNormals:vec2[]
	field width:int, height:int
	field grayLimit:int = $ff010101''$fffffffa
	
	field vecZero:vec2 = vec2.create( 0,0 )
	field vecU:vec2 = vec2.create( 0,-1)
	field vecD:vec2 = vec2.create( 0, 1)
	field vecL:vec2 = vec2.create(-1, 0)
	field vecR:vec2 = vec2.create( 1, 0)
	field vecUL:vec2 = vec2.create(-1,-1)
	field vecUR:vec2 = vec2.create( 1,-1)
	field vecDL:vec2 = vec2.create(-1, 1)
	field vecDR:vec2 = vec2.create( 1, 1)

	method findEdges(pixmap:TPixmap)
		originalImage = pixmap
		width = pixmap.width
		height = pixmap.height
		edgemap = new int[width*height]
		normals = new vec2[width*height]
		smoothedNormals = new vec2[width*height]

		_findEdges()
		_calcNormals()
		_smoothNormals()
	end method

	'save edge pixels in edgemap
	method _findEdges()
		local i:int
		local j:int
		for i=1 until originalImage.width-1
		for j=1 until originalImage.height-1
			local u_pixel:int = originalImage.readpixel(i,j-1)
			local d_pixel:int = originalImage.readpixel(i,j+1)
			local l_pixel:int = originalImage.readpixel(i-1,j)
			local r_pixel:int = originalImage.readpixel(i+1,j)
			local current_pixel:int = originalImage.readpixel(i,j)
			
			if current_pixel< grayLimit and (u_pixel>grayLimit or d_pixel>grayLimit or l_pixel>grayLimit or r_pixel>grayLimit)
				edgemap[i*height+j] = 1
			else
				edgemap[i*height+j] = 0
			endif
		next
		next
	end method
	
	'for each edge, look at its neighbours and decide normal
	method _calcNormals()
		local i:int
		local j:int
		
		for i=1 until originalImage.width-1
		for j=1 until originalImage.height-1		
			if edgemap[i*height+j] 
				local v:vec2 = new vec2
				v.x = 0; v.y = 0;
				local neigh:int = 0 'holds count of which edge neighbours this pixel has
				
				local hasU:int = false
				local hasD:int = false
				local hasL:int = false
				local hasR:int = false
				
				if originalImage.readpixel(i,j-1) > grayLimit
					hasU = true
					neigh:+1
				endif
				
				if originalImage.readpixel(i,j+1) > grayLimit
					hasD = true
					neigh:+1
				endif
				
				if originalImage.readpixel(i-1,j) > grayLimit
					hasL = true
					neigh:+1
				endif
				
				if originalImage.readpixel(i+1,j) > grayLimit
					hasR = true
					neigh:+1
				endif

				'We want the normal to point away from neighbour pixels
				if(neigh=0)
					v.x=0; v.y=0; 'no normal
				else if neigh=1 'has 1 neighbour, normal is minus vec to neighbour
					if(hasL) v = vecR
					if(hasR) v = vecL
					if(hasU) v = vecD
					if(hasD) v = vecU
				else if neigh=2
					if     (hasD and hasU) 
						v = vecZero
					else if(hasL and hasR)
						v = vecZero
					else if(hasD and hasR) 
						v = vecUL
					else if(hasD and hasL)
						v = vecUR
					else if(hasU and hasR)
						v = vecDL
					else if(hasU and hasL)
						v = vecDR
					else 'has U and D or L and R
						local avgx# = hasL + -hasR
						local avgy# = hasD + -hasU
						v.x = -avgx; v.y = -avgy;
					endif
				else if neigh=3 'left||right and up||down
					' v = the non-heighbour vector
					v.x = 0; v.y = 0;
					if(hasL) v.x :+ 1
					if(hasR) v.x :- 1
					if(hasU) v.y :+ 1
					if(hasD) v.y :- 1
				endif
				
				if neigh > 0
					local length:int = sqr(v.x*v.x+v.y*v.y)
					v.x :/ length
					v.y :/ length
				endif
				
				normals[i*height+j] = v	
			endif
		next		
		next
	end method
	
	method _smoothNormals()
		local i:int
		local j:int
		for i=1 until originalImage.width-1
		for j=1 until originalImage.height-1	
			if edgemap[i*height+j]
				local current_norm:vec2 = normals[i*height+j]
				local u_norm:vec2 = normals[i*height+(j-1)]
				local d_norm:vec2 = normals[i*height+(j+1)]
				local l_norm:vec2 = normals[(i-1)*height+j]
				local r_norm:vec2 = normals[(i+1)*height+j]
				
				local ul_norm:vec2 = normals[(i-1)*height+(j-1)]
				local ur_norm:vec2 = normals[(i+1)*height+(j-1)]
				local dl_norm:vec2 = normals[(i-1)*height+(j+1)]
				local dr_norm:vec2 = normals[(i+1)*height+(j+1)]
				
				local count:int = 1
				local avgx#=0
				local avgy#=0
				avgx :+ current_norm.x; avgy :+ current_norm.y
				if(edgemap[i*height+(j-1)])
					avgx :+ u_norm.x; avgy :+ u_norm.y
					count :+1
				endif
				
				if(edgemap[i*height+(j+1)])
					avgx :+ d_norm.x; avgy :+ d_norm.y
					count :+1
				endif
				
				if(edgemap[(i-1)*height+j])
					avgx :+ l_norm.x; avgy :+ l_norm.y
					count :+1
				endif
				
				if(edgemap[(i+1)*height+j])
					avgx :+ r_norm.x; avgy :+ r_norm.y
					count :+1
				endif
				
				'Up+Left or right
				if(edgemap[(i-1)*height+(j-1)])
					avgx :+ ul_norm.x; avgy :+ ul_norm.y
					count :+1
				endif
				
				if(edgemap[(i+1)*height+(j-1)])
					avgx :+ ur_norm.x; avgy :+ ur_norm.y
					count :+1
				endif
				'Down+left or right
				if(edgemap[(i-1)*height+(j+1)])
					avgx :+ dl_norm.x; avgy :+ dl_norm.y
					count :+1
				endif
				
				if(edgemap[(i+1)*height+(j+1)])
					avgx :+ dr_norm.x; avgy :+ dr_norm.y
					count :+1
				endif
				
				avgx :/ count
				avgy :/ count
				
				
				smoothedNormals[i*height+j] = vec2.create(avgx,avgy)
			
			endif
		next
		next	
	end method
end type


type vec2
	field x#,y#
	
	function create:vec2(x#,y#)
		local tmp:vec2 = new vec2
		tmp.x = x; tmp.y = y
		return tmp
	end function 
	
end type

function unpackARGB(argb:int, a% var, r% var, g% var, b% var)
	a = argb shr 24 & $ff
	r = (argb shr 16) & $ff
	g = (argb shr 8) & $ff
	b = argb & $ff
end function

Comments

TWH

2010

An example of how to use it:

superstrict

include "tpixmapnormals.bmx"

graphics 800,600,0,0,2

local pixmap:TPixmap = loadpixmap("bitmap.bmp")



local imgNorm:TimageNormals= new TimageNormals

local perfTim1:int = millisecs()
local iters:int = 5
local i:int 
for i=0 until iters
imgNorm.findEdges(pixmap)
next
local perfTim2:int = millisecs()
print "millisecs used finding normals:"+(perfTim2-perfTim1)/iters

while not keyhit(KEY_ESCAPE)
	cls
	
	drawpixmap(pixmap,0,0)
	
	'Draw edges and normals
	local i:int
	local j:int
	local scale# = 2;
	for i=1 until pixmap.width
	for j=1 until pixmap.height
		
		'draw edge pixels. warning: normals are null at non-edge pixels. So, check if pixel
		'exists in edgemap before reading smoothedNormals[]
		if imgNorm.edgemap[i*pixmap.height+j]
			local scx# = i*scale + pixmap.width 
			local scy# = j*scale
			setcolor 255,255,255
			drawrect scx,scy,scale,scale
			local vx# = imgNorm.smoothedNormals[i*pixmap.height+j].x*(scale*2)
			local vy# = imgNorm.smoothedNormals[i*pixmap.height+j].y*(scale*2)

			local pixcenterx# = scx+scale*.5
			local pixcentery# = scy+scale*.5
			setcolor 0,255,0
			drawline pixcenterx,pixcentery, pixcenterx-vx,pixcentery-vy
		endif
	next
	next
	
	flip
wend

Code Archives Forum