again stuck with contour tracing :(
Monkey Forums/Monkey Programming/again stuck with contour tracing :(
| ||
| I created a contour tracing code for PNG files, and there are special cases that its not working 100% correct. several weeks later, still looking for a solution to trace a PNG image to get the full outline clockwise, so I can create a polygon and/or do other stuff later. I found many methods and did try everything. This is the not 100% correct one: http://www.monkey-x.com/Community/posts.php?topic=9748 Using marching squares. And below is the last one using this algorithm http://en.wikipedia.org/wiki/Moore_neighborhood But i'm missing 4 pixels using that code.  Using this image png image:  ignore the other functions in it. they only work after the points are clockwise order.
Strict
Import mojo
Import opengl.gles11
Import classes.pngtracer
Function Main:Int()
New MyApp()
Return 0
End
Class MyApp Extends App
Field thing:Sprite
Method OnCreate:Int()
SetUpdateRate(60)
thing = New Sprite()
Return 0
End
Method OnUpdate:Int()
thing.Update()
Return 0
End
Method OnRender:Int()
Cls(255,255,255)
thing.Draw()
Return 0
End
End
Class Sprite
Field visible_outline:Stack<Point> = New Stack<Point>()
Field simplyfied_outline:Stack<Point> = New Stack<Point>()
Field verts:Float[]
Field hit:Bool
Field imgSlice:Image
Field PNGTrace:Pngtracer = New Pngtracer()
Method New()
PNGTrace.Trace("monkey://data/bord.png",1,True)
visible_outline = PNGTrace.outline
simplyfied_outline = PNGTrace.simplyfied_outline
verts = PNGTrace.verts
' or atlas file
'PNGTrace.Trace("monkey://data/atlas-world1.png",1,True,2715,417,242,132)
'visible_outline = PNGTrace.outline
'simplyfied_outline = PNGTrace.simplyfied_outline
'verts = PNGTrace.verts
'imgSlice = CreateImage(242, 132)
'imgSlice.WritePixels(PNGTrace.data, 0, 0, 242, 132)
' ! I WILL USE IT LIKE THIS
' I save the verts in a json file, so I don't have to calculate it before
' Monkey has a bug or it yust don't want to work with my poly data, I don't know why yet.
' DrawPoly(verts) don't work, but hit detection and other poly math do work.
'
End
Method Draw:Void()
'' DrawImage(imgSlice,0,0)
'' If hit Then
'' SetColor(255,0,0)
'' For Local point:Point = Eachin simplyfied_outline
'' DrawPoint(point.x,point.y)
'' Next
'' Else
SetColor(0,0,255)
For Local point:Point = Eachin visible_outline
DrawPoint(point.x,point.y)
Next
'' End
End
Method Update:Void()
'' If PointInPoly(MouseX(),MouseY(),verts) Then
'' hit = True
'' Else
'' hit = False
'' End
End
Function PointInPoly:Bool(x:Float, y:Float, poly:Float[])
Local i:Int, j:Int, c:Bool
Local v1:Bool, v2:Bool, v3:Bool, v4:Bool, v5#, v6#, v7#
c = False
Local p_count% = (poly.Length() / 2)
For i = 0 To p_count-1
j = (i+1) Mod p_count
v1 = (poly[i*2+1] <= y)
v2 = (y < poly[j*2+1])
v3 = (poly[j*2+1] <= y)
v4 = (y < poly[i*2+1])
v5 = (poly[j*2]-poly[i*2]) * (y-poly[i*2+1])
v6 = (poly[j*2+1]-poly[i*2+1])
If v6 = 0.0 Then v6 = 0.0001
v7 = poly[i*2]
If (((v1 And v2) Or (v3 And v4)) And (x < v5 / v6 + v7)) Then c = Not c
Next
Return c
End
End
Strict
Import mojo
Import monkey.math
Import opengl.gles11
Function AllocateArrayInt:Int[][]( i:Int, j:Int)
Local arr:Int[][] = New Int[i][]
For Local ind:Int = 0 Until i
arr[ind] = New Int[j]
Next
Return arr
End
Class Pngtracer
Field outline:Stack<Point>
Field simplyfied_outline:Stack<Point>
Field data:Int[][]
Field verts:Float[]
Method Trace:Stack<Point>(path:String, tolerance:Float=1,highestQuality:Bool=True, startX:Int=0, startY:Int=0, w:Int=-1, h:Int=-1)
Local info:Int[2]
Local db:DataBuffer = LoadImageData(path, info)
Local startPixelX:Int = -1
Local startPixelY:Int = -1
If w=-1 Then w=info[0]
If h=-1 Then h=info[1]
data = AllocateArrayInt(info[0],info[1])
For Local x:Int = 0 Until w
For Local y:Int = 0 Until h
Local j:Int = db.PeekInt( ( y * info[0] + x ) * 4)
data[x][y] = (j & $ff000000) | ( (j & $00ff0000) Shr 16) | (j & $0000ff00) | ( (j & $000000ff) Shl 16)
Next
Next
outline = moorNeighbor(w,h)
db = Null
If highestQuality=False Then
simplifyRadialDistance(outline,tolerance)
simplifyDouglasPeucker(simplyfied_outline,tolerance)
Else
simplifyDouglasPeucker(outline,tolerance)
End
toPolyData(outline)
Return outline
End
Method isPixelSolid:Bool(x:int, y:int,w:Int, h:Int)
Return (data[x][y] shr 24) & $FF > 0
End
Method moorNeighbor:Stack<Point>(w:Int,h:Int)
Local clockwiseOffset:StringMap<Point> = New StringMap<Point>()
clockwiseOffset.Set("1,0",New Point(1,-1))
clockwiseOffset.Set("1,-1",New Point(0,-1))
clockwiseOffset.Set("0,-1",New Point(-1,-1))
clockwiseOffset.Set("-1,-1",New Point(-1,0))
clockwiseOffset.Set("-1,0",New Point(-1,1))
clockwiseOffset.Set("-1,1",New Point(0,1))
clockwiseOffset.Set("0,1",New Point(1,1))
clockwiseOffset.Set("1,1",New Point(1,0))
Local out:Stack<Point> = New Stack<Point>()
Local prev:Point
Local curr:Point
Local boundary:Point
Local first:Point
Local firstPrev:Point
' find first pixel
For Local y:Int = h-1 To 0 Step -1
firstPrev = New Point(0,y-1)
For Local x:Int = 0 Until w-1
If isPixelSolid(x,y,w,h) Then
first = New Point(x,y)
Exit ' quite this for loop
End
firstPrev = New Point(x,y)
Next
If first <> Null Then
Exit ' found the first pixel quit this for loop
End
Next
prev = firstPrev
out.Push(first)
boundary = first
curr = Clockwise(clockwiseOffset,boundary,prev)
Local stopLoop:Bool = False
While stopLoop = False
If curr.y >= 0 And curr.x >= 0 And
curr.y < h And curr.x < w And
isPixelSolid(curr.x,curr.y,w,h) Then
out.Push(curr)
prev = boundary
boundary = curr
curr = Clockwise(clockwiseOffset,boundary, prev)
Else
prev = curr
curr = Clockwise(clockwiseOffset,boundary, prev)
End
stopLoop = ((curr.x = first.x And curr.y = first.y) OR (prev.x = firstPrev.x And prev.y = firstPrev.y))
Wend
Return out
End
Method Clockwise:Point(_clockwiseOffset:StringMap<Point>,target:Point,prev:Point)
Local clock:Point = _clockwiseOffset.Get((prev.x - target.x)+","+(prev.y - target.y))
Return New Point(clock.x+target.x,clock.y+target.y)
End
Method getSquareDistance:Float(p1:Point, p2:Point)
Local dx:Float = p1.x - p2.x
Local dy:Float = p1.y - p2.y
Return dx * dx + dy * dy
End
Method simplifyRadialDistance:Stack<Point>(points:Stack<Point>, tolerance:Float=1)
Local length:Int = points.Length()
Local prev_point:Point = points.Get(0)
Local new_points:Stack<Point> = New Stack<Point>()
new_points.Push(prev_point)
Local point:Point
For Local i:Int = 0 Until length
point = points.Get(i)
If getSquareDistance(point, prev_point) > tolerance Then
new_points.Push(point)
prev_point = point
End
Next
If prev_point <> point Then
new_points.Push(point)
End
simplyfied_outline = new_points
Return new_points
End
Method getSquareSegmentDistance:Float(p:Point, p1:Point, p2:Point)
Local x:Float = p1.x
Local y:Float = p1.y
Local dx:Float = p2.x - x
Local dy:Float = p2.y - y
If dx <> 0 or dy <> 0 Then
Local t:Float = ((p.x - x) * dx + (p.y - y) * dy) / (dx * dx + dy * dy)
If t > 1 Then
x = p2.x
y = p2.y
Elseif t > 0 Then
x += dx * t
y += dy * t
End
End
dx = p.x - x
dy = p.y - y
Return dx * dx + dy * dy
End
Method simplifyDouglasPeucker:Stack<Point>(points:Stack<Point>, tolerance:Float=1)
Local length:Int = points.Length()
Local markers:Int[] = New Int[length]
Local f:Int = 0
Local l:Int = length-1
Local first_stack:IntStack = New IntStack()
Local last_stack:IntStack = New IntStack()
Local new_points:Stack<Point> = New Stack<Point>()
markers[f] = 1
markers[l] = 1
Local index:Int = 0
Local max_sqdist:Float = 0
Local stop:Bool = False
While stop=False
max_sqdist = 0
For Local i:Int = f Until l
Local sqdist:Float = getSquareSegmentDistance(points.Get(i), points.Get(f), points.Get(l))
If sqdist > max_sqdist Then
index = i
max_sqdist = sqdist
End
Next
If max_sqdist > tolerance Then
markers[index] = 1
first_stack.Push(f)
last_stack.Push(index)
first_stack.Push(index)
last_stack.Push(l)
End
If first_stack.IsEmpty() Then
f = 0
Else
f = first_stack.Pop()
End
If last_stack.IsEmpty() Then
l = 0
stop = True
Else
l = last_stack.Pop()
End
End
For Local i:Int = 0 Until length
If markers[i] Then
new_points.Push(points.Get(i))
End
Next
simplyfied_outline = new_points
Return new_points
End
Method toPolyData:Float[](points:Stack<Point>)
verts = verts.Resize(points.Length*2)
Local tmpI:Int = 0
For Local point:Point = Eachin points
verts[tmpI] = point.x
tmpI=tmpI+1
verts[tmpI] = point.y
tmpI=tmpI+1
Next
Return verts
End
End
Class Point
Field x:Int
Field y:Int
Method New(_x:Int,_y:Int)
x=_x
y=_y
End
End
But maybe its very simple, because I can get the full outline with this simple code below. But the problem with that is that the coordinate order is not clockwise, so I can't create a polygon and do other things with it. For example create less points using the method simplifyDouglasPeucker(outline,tolerance) This is because i'm scanning from x (left right) to y (top bottom)
Method Trace:Stack<Point>(path:String, tolerance:Float=1,highestQuality:Bool=True, startX:Int=0, startY:Int=0, w:Int=-1, h:Int=-1)
Local info:Int[2]
Local db:DataBuffer = LoadImageData(path, info)
Local startPixelX:Int = -1
Local startPixelY:Int = -1
If w=-1 Then w=info[0]
If h=-1 Then h=info[1]
data = AllocateArrayInt(info[0],info[1])
For Local x:Int = 0 Until w
For Local y:Int = 0 Until h
Local j:Int = db.PeekInt( ( y * info[0] + x ) * 4)
data[x][y] = (j & $ff000000) | ( (j & $00ff0000) Shr 16) | (j & $0000ff00) | ( (j & $000000ff) Shl 16)
Next
Next
Local data2:Int[][] = AllocateArrayInt(info[0],info[1])
outline = New Stack<Point>()
For Local x:Int = 0 Until w
For Local y:Int = 0 Until h
If isPixelSolid(x,y,w,h) Then
data2[x][y]=1
Else
data2[x][y]=0
End
Next
Next
For Local x:Int = 0 Until w
For Local y:Int = 0 Until h
If ((x = 0) Or (x = w - 1) Or (y = 0) Or (y = h - 1)) Then
If (data2[x][y]) Then
outline.Push(New Point(x,y))
End
Else
If (data2[x][y] And
(data2[x - 1][y - 1]=0 Or data2[x][y - 1]=0 Or
data2[x + 1][y - 1]=0 Or
data2[x - 1][y]=0 Or data2[x + 1][y]=0 Or
data2[x - 1][y + 1]=0 Or
data2[x][y + 1]=0 Or data2[x + 1][y + 1]=0)) Then
outline.Push(New Point(x,y))
End
End
Next
Next
db = Null
Return outline
End
Other option maybe... I can create a map with data2 like this [ 0000000000000 0111111111110 0100000000010 0101111111010 0101000001010 0101000001010 0101000001010 0101000001010 0111000001110 ] As you can see the 1 is the image contour line But what is then the algorithm to get the coordinates clockwise ? |
| ||
| Just test whether they are anti-clockwise (unless they always are) and reverse them if they are! ABC -> CBA |
| ||
| but the they arent clockwise and not anti clokwise in the last example, they are from x top left to bottom right. in that rare order. |
| ||
| Ah, there's no magic way to do it. You have to put them in in the right order. How about making four rows: furthest left, furthest right, topmost, and bottom-most pixels, by moving in from the edges / top / bottom until you hit the object. It will work for most simple shapes. Then put all four rows in the right order and direction to get a polygon. If you want something more general, you might have to 'trace' around the edge in code. Possibly after magnifying the image and smoothing the edges, to avoid corners that make that harder. |
| ||
| i was had a idea about a analog clock. using the middle and scan the 12 hours. with using the the map above. but dont know how to make this clock haha. |
| ||
| Maybe if you expanded the image by a factor of 3 and applied a smoothing step to get rid of corners, you could apply an algorithm similar to 'marching squares' to walk around it without any problems from awkward spots. |
| ||
| I put my old code up in the original post here: http://www.monkey-x.com/Community/posts.php?topic=8626#105178 Maybe it will help. |
| ||
| Oke I will have a look , thanks ! |
| ||
| @Raph, Can't run your code because its missing one class: Global edgePoints:List<Edge> = New List<Edge> |
| ||
| Is this for detecting mouseclicks in a game? If so, you can always fall back to making a boolean array from the rectangle containing the image, and checking if the click hit a valid pixel. That will be 32 times smaller than the image, and you can always compress it further by shrinking the image by a factor of 2 or 3. So whether you do it in-game or separately, it won't make your memory consumption grow out of control. |
| ||
| Huh, it should have been at the bottom. I will update in the other post. Edit: I take it back. The Edge class IS at the bottom. Did you not copy everything into your file, perhaps? |
| ||
| Just a shot in the dark, but maybe try this? Just the two changes Essentially, skip the 'x' test for lines that have y1=y2, ie. perfectly horizontal. Otherwise you might get unpredictable results. |
| ||
| @gerry its in the first place to automatic create a png border, that can be used to detect collision. For example using point in poly That boolean thing sounds like a good idea, but there are many possibilitys when i get the polygon. @raph Ow sorry, i see it now. @nullterm Pointinpoly did work oke for me, but only for valid poly points. Or is this a pointinToXToBottomLeftArea now? |
| ||
| GC-Martijn, if what you want is to do collision, you probably DON'T want an algorithm that gives you an accurate poly contour. You want a simpler hull for collision that you can use PointInPoly with. My code generates actual outlines, concave hulls -- I used it for shadowcasters. You might want to try Warpy's convex hull code: http://www.monkey-x.com/Community/posts.php?topic=709 |
| ||
| @Raph The next step is to simplify the point to only the corner points (that code is working already) And in my code I already made the convex hull thing, but the problem with that is that its not working for that image. I guess because I need a concave hull then. But with all those idea's and hints I can try another month now haha :) Then I have - transparent png [done] - fast contour scan [done] - reorder contour to clockwise (or something) - simplify points [done] - point in polygon [done] The simplify points are only the corners in clockwise order, and I save them in a xml file. Then when the game loads, I reload them to use them for collision. And I can use the contour from step 2 to create extra FX things. |
   |