fast .PNG tracing and outline collision !
Monkey Forums/User Modules/fast .PNG tracing and outline collision !
| ||
| UPDATE 2: Made it a little faster and a float/int bug UPDATE 1: Now with collision detection and better polygon data. Small fix, and now with atlas support. Main target: ios/android/desktop Other targets: You need to get PNG data to extend this script with your target Its very simple, use a transparent png file, en this script get the outline. Then you can convert the outline to a polygon and use that for collision detection. Tested with several complex figures.
Strict
Import mojo
Import opengl.gles11
Import classes.point
Class Pngtracer
Field outline:Stack<Point>
Field simplyfied_outline:Stack<Point>
Field data:Int[]
Field verts:Float[]
Method Trace:Stack<Point>(path:String, tolerance:Int=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 = data.Resize(w * h)
For Local y:Int = 0 Until h
For Local x:Int = 0 Until w
Local j:Int = db.PeekInt( ( (startY + y) * info[0] + (startX + x)) * 4)
data[y * w + x] = (j & $ff000000) | ( (j & $00ff0000) Shr 16) | (j & $0000ff00) | ( (j & $000000ff) Shl 16)
If startPixelX=-1 And startPixelY=-1 And (data[y*w+x] shr 24) & $FF Then
startPixelX=x
startPixelY=y
End
Next
Next
db = Null
squaresAlg(startPixelX,startPixelY,w,h)
If highestQuality=False Then
simplifyRadialDistance(outline,tolerance)
simplifyDouglasPeucker(simplyfied_outline,tolerance)
Else
simplifyDouglasPeucker(outline,tolerance)
End
toPolyData(simplyfied_outline)
Return outline
End
Method getSquareValue:Int(_x:Int,_y:Int, _w:Int, _h:Int)
Local squareValue:Int=0
' checking upper left pixel
If (_y-1)*_w+(_x-1)>=0 And (data[(_y-1)*_w+(_x-1)] shr 24) & $FF Then
squareValue+=1;
End
'' checking upper pixel
If (_y-1)*_w+_x>=0 And (data[(_y-1)*_w+_x] shr 24) & $FF Then
squareValue+=2;
End
'' checking left pixel
If _y*_w+(_x-1)>=0 And _y*_w+(_x-1)<=data.Length And (data[_y*_w+(_x-1)] shr 24) & $FF Then
squareValue+=4;
End
'' checking the pixel itself
If _y*_w+_x>=0 And _y*_w+_x<=data.Length And (data[_y*_w+_x] shr 24) & $FF Then
squareValue+=8;
End
Return squareValue
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:Int=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:Int=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 squaresAlg:Void(_x:Int,_y:Int,_w:Int,_h:Int)
Local pX:Int=_x
Local pY:Int=_y
Local stepX:Int
Local stepY:Int
Local prevX:Int
Local prevY:Int
Local closedLoop:Bool=False
outline = New Stack<Point>()
While closedLoop=False
Select getSquareValue(pX,pY,_w,_h)
Case 1,5,13
stepX=0
stepY=-1
Case 8,10,11
stepX=0
stepY=1
Case 4,12,14
stepX=-1
stepY=0
Case 2,3,7
stepX=1
stepY=0
Case 6
If prevX=0 And prevY=-1 Then
stepX=-1
stepY=0
Else
stepX=1
stepY=0
End
Case 9
If prevX=1 And prevY=0 Then
stepX=0
stepY=-1
Else
stepX=0
stepY=1
End
End
pX+=stepX
pY+=stepY
outline.Push(new Point(pX, pY))
prevX=stepX
prevY=stepY
If pX=_x And pY=_y Then
closedLoop=true
End
End
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
example
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
Method New()
Local PNGTrace:Pngtracer = New Pngtracer()
PNGTrace.Trace("monkey://data/test-thing2.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,660,1207,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
' DrawPoly(verts) '<--- MONKEY fails, but the poly data is correct !!!
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
|
| ||
| Looks very handy! |
| ||
Oh, that's some nice code! Great result with this test:  |
| ||
| within some time i will post the outline points2poly code to check a collision. i have to find a code to convert all the coordinates to clockwise polygon verts. |
   |