Code archives/Algorithms/Marching Squares
This code has been declared by its author to be Public Domain code.
Download source code
| |||||
the marching squares algorithm traces the outline of a 2d image. This code was heavily inspired by actionscript code by Sakri Rosenstrom: http://www.sakri.net/blog/2009/05/28/detecting-edge-pixels-with-marching-squares-algorithm/ I imagine msquares could be used to -make a magic wand tool in an image editor, trace outline of certain pixels (color hues) -visualize 2d implicit functions like x^2+y^2=5 (circle) -"ai" for a creature in a game -> it follows the contour of the level or something -cool effects like watery text -a 2d water effect if regions are filled and animated -detect outline of metashapes | |||||
'written by TWH aka Torbjoern '25. aug '-fixed multiplie out-of-bounds errors, added getOutlinePixmap( Tpixmap ) '-only the current pixel (pos.x,pos.y) is marked as tracked/visited, superstrict graphics 640,480,0,0,2 global fpsCounter:TFPSCounter= new TFPSCounter type TUIState field activeItem:int = -1 field hotItem:int = -1 end type global uistate:TUIState = new TUIState global lowerColor:TColor = TColor.Create(0,0,0) global upperColor:TColor = TColor.Create(255,255,255) function mainloop() local msquares:TMarchingSquares = new TMarchingSquares local width:int = 320 local height:int = 240 local screen:int[,] = new int[width,height] local pointList:tlist = null local brushSiz# = 10 local pixmap:TPixmap = LoadPixmap("fry.png") while not appterminate() and not keyhit(KEY_ESCAPE) cls 'draw our painting surface local i:int, j:int for i=0 until width for j=0 until height if( screen[i,j] ) setcolorARGB( screen[i,j] ) plot i,j endif next next 'Draw a bitmap using the mouse: brushSiz :+ MouseZSpeed() 'change brush size using scrollwheel brushSiz = min(30.0, max(2.0, brushSiz) ) drawCircle(mousex(), mousey(), brushSiz) 'draw our brush if mousedown(1) then paintbrush(mousex(), mousey(), brushSiz, $00ffff00, screen) if keydown(KEY_1) msquares.animated = false pointList = msquares.getOutline(screen) 'get a list of outline points endif if keydown(KEY_2) msquares.animated = true 'animate the process pointList = msquares.getOutline(screen) endif if keyhit(KEY_3) msquares.animated = false if pixmap then pointList = msquares.getOutlinePixmap(pixmap, lowerColor, upperColor) endif 'Draw all points generated by marching squares if pointList<>null setcolor 0,255,0 for local p:vec2 = eachin pointList plot p.x, p.y next endif setcolor 255,255,255 DrawLineRect(0,0,width,height) if pixmap then drawpixmap(pixmap,width+10,0) 'Begin slider code (lower and upper color threshold for pixmap) local sliderLen:int = 255 local slider_x:int = 15 local lo_r% = lowerColor.r local lo_g% = lowerColor.g local lo_b% = lowerColor.b local hi_r% = upperColor.r local hi_g% = upperColor.g local hi_b% = upperColor.b Slider(0, slider_x + (sliderLen+15)*0, height+15*4, sliderLen, $ff0000, lo_r) Slider(1, slider_x + (sliderLen+15)*1, height+15*4, sliderLen, $ff0000, hi_r) Slider(2, slider_x + (sliderLen+15)*0, height+15*5, sliderLen, $00ff00, lo_g) Slider(3, slider_x + (sliderLen+15)*1, height+15*5, sliderLen, $00ff00, hi_g) Slider(4, slider_x + (sliderLen+15)*0, height+15*6, sliderLen, $0000ff, lo_b) Slider(5, slider_x + (sliderLen+15)*1, height+15*6, sliderLen, $0000ff, hi_b) lowerColor.set(lo_r, lo_g, lo_b) upperColor.set(hi_r, hi_g, hi_b) 'End sliders local text_y_pos:int = height+100 drawtext "getOutline()-test, draw here",15, text_y_pos+15*+0 drawtext "getOutlinePixmap()-test ",15+width*1, text_y_pos+15*+0 drawtext "press key 1 update outline",15, text_y_pos+15*+1 drawtext "press key 2 to see marching squares working",15, text_y_pos+15*+2 drawtext "Sliders adjust lower lower/upper color threshold for pixmap",15, text_y_pos+15*+3 drawtext "fps: "+fpsCounter.fps, 15,graphicsheight()-30 fpsCounter.update() flip wend end function mainloop() 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 function setColorARGB(argb:int) local a:int = argb shr 24 & $ff local r:int = argb shr 16 & $ff local g:int = argb shr 8 & $ff local b:int = argb & $ff setcolor r,g,b end function 'taken from Sol's graphics tutorial at sol.gfxile.net function paintbrush(x#,y#,r:int,c:int,screen:int[,]) local i#, j:int for i=0 until 2*r step 1 local length:int = int( sqr( cos(0.5*180*(i-r)/r)) * r * 2 ); for j=0 until length local xp:int = floor(x+j-length/2.0 + 0.5); local yp:int = floor(y-r+i + 0.5); local width:int = screen.Dimensions()[0] local height:int = screen.Dimensions()[1] if(xp > 0 and xp < (width-1) and yp > 0 and yp < (height-1)) screen[xp,yp] = c; endif next next end function type vec2 field x:int,y:int function create:vec2(x:int,y:int) local tmp:vec2 = new vec2 tmp.x = x; tmp.y = y; return tmp end function end type type TMarchingSquares field bmd:int[,] field width:int, height:int field variations_cw:vec2[16] field variations_ccw:vec2[16] field tracked:int[,] 'used to remember if we've traced the pixel earlier field points:TList 'list of traced points. Might contain dupes field animated:int = false field errCase15:int = 0 field errCase0:int = 0 field foundLoop:int = 0 method new() variations_cw[ 0] = vec2.create( 0, 0) 'illegal. No way to find direction. variations_cw[ 1] = vec2.create( 1, 0) ' r variations_cw[ 2] = vec2.create( 0, 1) ' d variations_cw[ 3] = vec2.create( 1, 0) ' r variations_cw[ 4] = vec2.create( 0,-1) ' l variations_cw[ 5] = vec2.create( 0,-1) ' u variations_cw[ 6] = vec2.create( 0,-1) ' u variations_cw[ 7] = vec2.create( 0,-1) ' u variations_cw[ 8] = vec2.create( 1, 0) ' l variations_cw[ 9] = vec2.create( 1, 0) ' r variations_cw[10] = vec2.create( 0, 1) ' d variations_cw[11] = vec2.create( 1, 0) ' r variations_cw[12] = vec2.create(-1, 0) ' l variations_cw[13] = vec2.create(-1, 0) ' l variations_cw[14] = vec2.create( 0, 1) ' u variations_cw[15] = vec2.create( 0, 0) ' illegal. variations_ccw[ 0] = vec2.create( 0, 0) ' illegal variations_ccw[ 1] = vec2.create( 0, 1) ' d v variations_ccw[ 2] = vec2.create(-1, 0) ' l < variations_ccw[ 3] = vec2.create(-1, 0) ' l < variations_ccw[ 4] = vec2.create( 1, 0) ' r > variations_ccw[ 5] = vec2.create( 0, 1) ' d v variations_ccw[ 6] = vec2.create(-1, 0) ' l < variations_ccw[ 7] = vec2.create(-1, 0) ' l < variations_ccw[ 8] = vec2.create( 0,-1) ' u ^ variations_ccw[ 9] = vec2.create( 0,-1) ' u ^ variations_ccw[10] = vec2.create( 0,-1) ' u ^ variations_ccw[11] = vec2.create( 0,-1) ' u ^ variations_ccw[12] = vec2.create( 1, 0) ' r > variations_ccw[13] = vec2.create( 0, 1) ' d v variations_ccw[14] = vec2.create( 1, 0) ' r > variations_ccw[15] = vec2.create( 0, 0) ' illegal end method method getOutlinePixmap:TList( bitmapdata:TPixmap, lowerThreshold:TColor, upperThreshold:TColor ) bmd = new int[bitmapdata.width, bitmapdata.height] width = bitmapdata.width height = bitmapdata.height for local x:int = 0 until width for local y:int = 0 until height local pixel:int = readpixel(bitmapdata,x,y) local a:int, r:int, g:int, b:int 'alpha isnt used unpackARGB(pixel,a,r,g,b) local avgColor:int = (r+g+b) / 3 local color_rule:int = 1 select color_rule case 1 if avgColor > 128 bmd[x,y] = 1 'trace white-ish parts, worked images with a white background case 2 if avgColor < 128 bmd[x,y] = 1 'trace black-ish parts, workd well on shapes with black contours case 3 'all values must be witin threshold if r > lowerThreshold.r and r < upperThreshold.r or.. g > lowerThreshold.g and g < upperThreshold.g or.. b > lowerThreshold.r and b < upperThreshold.b bmd[x,y] = 1 endif 'values may be witin on or another threshold case 4 if r > lowerThreshold.r and r < upperThreshold.r or.. g > lowerThreshold.g and g < upperThreshold.g or.. b > lowerThreshold.r and b < upperThreshold.b bmd[x,y] = 1 endif end select next next return searchEachPixel() end method method getOutline:TList( bitmapdata:int[,]) bmd = bitmapdata width = bitmapdata.dimensions()[0] height = bitmapdata.dimensions()[1] return searchEachPixel() end method method searchEachPixel:TList() tracked = new int[width,height] 'memclear(varptr tracked[0,0], 4*width*height) 'is this good practice? Does bmax init arrays to 0? points = new TList ' reset error status errCase15 = 0 errCase0 = 0 foundLoop = 0 'find pixels that have something in them and are untracked so far, run marching squares on pixel 'keep boundries witin image (2x2) marching squares area for local y:int=2 until height-2 for local x:int=2 until width-2 if(bmd[x,y] > 0) if( not tracked[x,y]) marchingSquares(x,y); endif endif next next return points end method method marchingSquares(x:int,y:int) local pos:vec2 = vec2.create( x-1, y-1 ) 'move back and up from pixel local start:vec2 = vec2.create( pos.x, pos.y ) local outOfBounds:int = pos.x < 1 or pos.x > (width-2) or pos.y < 1 or pos.y > (height-2) assert not outOfBounds local iters:int = 0 while(true) iters:+1 tracked[pos.x,pos.y] :+ 1 local dirTableIndex:int = getNextEdgePoint(pos) outOfBounds = pos.x < 1 or pos.x > (width-2) or pos.y < 1 or pos.y > (height-2) if outOfBounds then return if( dirTableIndex=0 or dirTableIndex=15 ) then return 'quit if illegal marching squares state if( pos.x=start.x and pos.y=start.y ) then return 'were back at start, finished trace if( tracked[pos.x,pos.y] > 2 ) 'tracked this pixel too many times, prevent inf loops caused by bad pixel configurations. foundLoop:+1 return endif points.addLast( vec2.create(pos.x, pos.y) ) ' Visualize marching squares progress if(animated) setcolor(0,50+5*iters mod 150,0) plot(pos.x,pos.y) if(iters mod 5 = 0) flip() delay(5) endif endif wend end method 'use marching squares look-up-table to decide where to move next method getNextEdgePoint:int(pos:vec2) local x:int = pos.x; local y:int = pos.y local index:int = 0 if( bmd[x+1,y+1] > 0 ) index :+ 1; if( bmd[x,y+1] > 0 ) index :+ 2; if( bmd[x+1,y] > 0 ) index :+ 4; if( bmd[x,y] > 0 ) index :+ 8; ' Error if( index=15 ) then errCase15:+1; if( index=0) then errCase0:+1; pos.x :+ variations_ccw[index].x; pos.y :+ variations_ccw[index].y 'pos.x += variations_cw[index].x; pos.y += variations_cw[index].y return index; end method end type type TColor field r:byte, g:byte, b:byte function Create:TColor(r:byte, g:byte, b:byte) local tmp:TColor = new TColor tmp.r = r; tmp.g = g; tmp.b = b; return tmp end function method set(r:byte, g:byte, b:byte) self.r = r; self.g = g; self.b = b; end method end type 'Immidiate mode slider function 'Inspired by Sols tutorial: http://sol.gfxile.net/imgui/ch05.html 'What it does: Draws a GUI slider and modifies the slideValue sent to it 'To use a slider, specifiy an id (0 upto MAXSLIDERS) function Slider(id:int, x#, y#, length#, color:int, slideValue:int var) const MAXSLIDERS:int = 7 assert id < MAXSLIDERS-1 global mouseLock:int[MAXSLIDERS] global sliderValue:int[MAXSLIDERS] global globCtor:int = false if globCtor = false globCtor = true for local i:int = 0 until MAXSLIDERS mouseLock[i] = false sliderValue[i] = length / 2 next endif local handle_size# = 10 local handle_x_pos# = x+slideValue-handle_size/2 local handle_y_pos# = y-handle_size/2 if PointInRect(mousex(), mousey(),handle_x_pos, handle_y_pos, handle_size, handle_size) uistate.hotitem = id if( uistate.activeitem = -1 and mouseDown(1) ) uistate.activeitem = id endif endif if not mouseDown(1) then uistate.activeitem = -1 'release grip of handle setcolor 127,127,127 drawrect(x,y-2,length,4) if uistate.hotitem = id setcolor 255,255,255 else setcolor 127,127,127 endif if uistate.activeitem = id then setcolorARGB(color) drawrect(handle_x_pos, handle_y_pos, handle_size, handle_size) if uistate.activeitem = id drawtext ""+slideValue ,handle_x_pos-5,handle_y_pos-15 if( mousex() < x+length and mousex() > x ) 'limit movement to slider line slideValue = mousex()-x endif endif end function function PointInRect:int(testx#,testy#,topleftx#,toplefty#,w#,h#) if(testx >= topleftx and testx <= topleftx+w and.. testy >= toplefty and testy <= toplefty+h) return true endif return false end function Type TFPSCounter Field frames:Int=0 Field fps:Int=0 Field sec:Long = MilliSecs() Method update() If(sec < MilliSecs() ) sec = MilliSecs() + 100 fps = frames*10 frames = 0 EndIf frames :+1 End Method End Type 'circle outline func by ImaginaryHuman 'http://www.blitzbasic.com/codearcs/codearcs.php?code=1476 function drawCircle(xCenter:Int=320, yCenter:Int=240, radius:Int) Local p:int,x:int,y:Int x=0 y=radius Plot xCenter+x,yCenter+y Plot xCenter-x,yCenter+y Plot xCenter+x,yCenter-y Plot xCenter-x,yCenter-y Plot xCenter+y,yCenter+x Plot xCenter-y,yCenter+x Plot xCenter+y,yCenter-x Plot xCenter-y,yCenter-x p=1-radius While x<y If p<0 x:+1 Else x:+1 y:-1 EndIf If p<0 p=p+(x Shl 1)+1 Else p=p+((x-y) Shl 1)+1 EndIf Plot xCenter+x,yCenter+y Plot xCenter-x,yCenter+y Plot xCenter+x,yCenter-y Plot xCenter-x,yCenter-y Plot xCenter+y,yCenter+x Plot xCenter-y,yCenter+x Plot xCenter+y,yCenter-x Plot xCenter-y,yCenter-x wend End function 'DrawLineRect by drnmr 'http://www.blitzmax.com/codearcs/codearcs.php?code=1674 Function DrawLineRect(x:Int,y:Int,length:Int,height:Int) local lowerlefty% = y+height local lowerrightx% = x+length local lowerrighty% = y+height local upperrightx% = x+length DrawLine x,y,x,lowerlefty DrawLine x,lowerlefty,lowerrightx,lowerrighty DrawLine lowerrightx,lowerrighty,upperrightx,y DrawLine upperrightx,y,x,y EndFunction |
Comments
| ||
quite nice! and useful. Thanks. |
| ||
This is neat. BTW, all your array operations overflow the array boundries. I had to wrap a whole bunch of stuff in exception handlers just to get it working with real images. |
| ||
That's really cool -- very fast, too. |
| ||
I think there is an error in the code. It looks like pixels on the top and left are outlining properly, but pixels on the bottom and right are at the same coord as the source. |
| ||
Thanks for all the feedback! The bounds errors are corrected now. I prototyped this in evaldraw, and I forgot it wraps arrays when porting to Bmax. I've also got pixmaps working now. It works quite well with cartoon characters :D GW: I hadn't notice the incorrect bottom and right pixels. I think this is just the way marching squares works. To fix this add +1x or +1y depending on what state getNextEdgePoint state returns of the MarchingSquares states: http://en.wikipedia.org/wiki/Marching_squares ..hm or maybe on can just look see if the source has pixels at the current upper left square postion like this when adding points: if bmd[pos.x, pos.y] and bmd[pos.x, pos.y+1] points.addLast( vec2.create(pos.x+1, pos.y) ) else points.addLast( vec2.create(pos.x, pos.y) ) endif |
Code Archives Forum