Seperating Axis Theorem Problem

Übersicht BlitzMax, BlitzMax NG Allgemein

Neue Antwort erstellen

ToeB

Betreff: Seperating Axis Theorem Problem

 BeitragDi, März 27, 2012 15:42
Antworten mit Zitat
Benutzer-Profile anzeigen
Hi!

Ich habe mir mal SAT (Seperating Axis Theorem) im 2D Raum angeguckt, was ein Verfahren zum Prüfen von Kollisionen zwischen zwei convexen Polygonen. Leider klappt das nicht so wie ich das Möchte :/ Ich hoffe ihr könnt mir helfen !

Ich habe eine Polygone-Klasse, welche eine Liste an Vertices enthält, im Urhzeigersinn geordnet. Der Mittelpunkt wird aus dem Mittelwert aller Vertices gewählt.

Hier mal meine Polyklasse:
BlitzMax: [AUSKLAPPEN] 
Type TBody
	Global List:TList = CreateList()
	Field link:TLink
	
	Field color:Int[3]
	Field min_x:Float, min_y:Float, max_x:Float, max_y:Float
	
	Field position:TVec2
	Field rotation:TVec2
	
	Field velocity:TVec2
	Field rotationVel:Float
	
	Field parent:TBody
	
	Method New( )
		link = List.AddLast( Self )
		position = Vec2()
		rotation = Vec2(1,0)
		velocity = Vec2()
	End Method
	Method Remove( )
		link.Remove( )
	End Method
	Method _Update:Byte()		
		position = position.Add( velocity )
		rotation = rotation.Turn( rotationVel )
		GetMinMax()
		If min_x < 0 Then 
			velocity.x = -velocity.x
			position.x :- min_x
			rotationVel = - rotationVel
		EndIf 
		If min_y < 0 Then 
			velocity.y = -velocity.y
			position.y :- min_y
			rotationVel = - rotationVel
		EndIf 
		If max_x > GraphicsWidth() Then 
			velocity.x = -velocity.x
			position.x :+ GraphicsWidth()-max_x
			rotationVel = - rotationVel
		EndIf  
		If max_y > GraphicsHeight() Then 
			velocity.y = -velocity.y
			position.y :+ GraphicsHeight()-max_y
			rotationVel = - rotationVel
		EndIf 
		Update( )
	End Method 
	Method _Draw( )
		Draw( )
		SetColor( 0, 255, 0 )
		SetAlpha( 0.1 )
		SetBlend( ALPHABLEND )
		DrawRect( min_x, min_y, max_x-min_x, max_y-min_y )'position.x+min_x, position.y+min_y, position.x+(max_x-min_x), position.y+(max_y-min_y) )
		SetAlpha( 1 )
	End Method 
	Method Update() Abstract 
	Method Draw() Abstract  
	Method GetMinMax(  sys:Tvec2=Null ) Abstract 
	Method Copy:TBody( s:Float=1 ) Abstract 
	Method SetPosition( x:Float, y:Float )
		position = Vec2( x, y )
	End Method
	Method SetRotation( a:Float )
		rotation = Vec2A( a )
	End Method 
	Method SetVelocity( velx:Float, vely:Float )
		velocity = Vec2( velx, vely )
	End Method 
	Method GetRotation:Float( )
		Return rotation.GetA()
	End Method 
	Method TFormPoint:TVec2( p:TVec2, sys:TVec2=Null )
		Return p.TForm( rotation, sys ).Add( position )
	End Method 
	Method TFormVector:TVec2( v:TVec2, sys:TVec2=Null )
		Return TFormPoint( position.Add( v ), sys )
	End Method
End Type 

Type TPoly Extends TBody
	Field vertices:TList, count:Int
	Method New( )
		vertices = CreateList()
		color[0] = Rand(100,200)
		color[1] = Rand(100,200)
		color[2] = Rand(100,200)	
	EndMethod
	
	Method AddVertex( x:Float, y:Float )
		vertices.AddLast( Vec2( x, y ) )
		count :+ 1
	End Method 
	
	Method _getpos:TVec2( p:TVec2, sys:TVec2=Null )
		If sys = Null Then sys = Vec2(1,0)
		Return p.TForm( rotation, sys ).Add( position )
	End Method 
	
	Method setup()
		Local x:Float, y:Float, c:Float = Float( CountList(vertices) )		
		For Local p:TVec2 = EachIn vertices
			x :+ p.x
			y :+ p.y
		Next 
		x :/ c
		y :/ c
		For Local p:TVec2 = EachIn vertices
			p.x :- x
			p.y :- y
		Next 
		GetMinMax()
	End Method
	
	Method GetMinMax( sys:Tvec2=Null)
		If sys = Null Then sys = Vec2(1, 0)	
		min_x = 10000
		max_x = -10000
		min_y = 10000
		max_y = -10000		
		For Local p:TVec2 = EachIn vertices		
			Local pt:Tvec2 = _getpos( p, sys )	
			min_x = Min( min_x, pt.x )
			min_y = Min( min_y, pt.y )
			max_x = Max( max_x, pt.x )
			max_y = Max( max_y, pt.y )
		Next 
	End Method  
	
	Method Update()
		For Local poly:TPoly = EachIn TPoly.List
			If poly <> Self Then 
				Local check:Byte = intersect( poly )
				If check Then 
					color[0] = 255; color[1] = 0; color[2] = 0
				Else
					color[0] = 100; color[1] = 100; color[2] = 200
				EndIf 
			EndIf  
		Next 
	End Method
	
	Method Draw()
		SetColor( color[0], color[1], color[2] )
		Local count:Int = CountList(vertices)*2
		Local poly:Float[] = New Float[ count ], i:Int = 0
		For Local tmp:TVec2 = EachIn vertices
			Local vec:TVec2 = tmp.turn( rotation.GetA()-45 ).Add( position )
			poly[i] = vec.x
			poly[i+1] = vec.y
			i :+ 2
		Next
		DrawPoly( poly )
		SetColor( 255, 255, 255 )
		For i = 2 To count-1 Step 2
			DrawLine( poly[i-2], poly[i-1], poly[i], poly[i+1] )
		Next 
		DrawLine( poly[count-2], poly[count-1], poly[0], poly[1] ) 
		DrawOval( position.x-2, position.y-2, 5, 5 )
	End Method
	
	Method Copy:TBody( s:Float=1.0 )
		Local c:TPoly = New TPoly
		For Local tmp:TVec2 = EachIn vertices
			c.AddVertex( tmp.x*s, tmp.y*s )
		Next 
		c.setup()
		For Local i:Byte = 0 To 2
			c.color[i] = color[i]
		Next 
		Return c
	End Method
	
	Method Intersect:Byte( poly:TPoly )
		Local axis1:TVec2[] = Self.GetAxis( )
		Local axis2:TVec2[] = poly.GetAxis( )
		'Print "Axis1: "+ats(axis1)
		'Print "Axis2: "+ats(axis2)
		Local offset:TVec2 = position.Sub( poly.position )
		Local i:Int 
		For i = 0 To axis1.length-1
			Local s1:TProjection = Self.Project( axis1[i], offset )
			Local s2:TProjection = poly.Project( axis1[i], offset )
			If Not s1.overlap( s2 ) Then Return False
		Next 
		For i = 0 To axis2.length-1
			Local s1:TProjection = Self.Project( axis2[i], offset )
			Local s2:TProjection = poly.Project( axis2[i], offset )
			If Not s1.overlap( s2 ) Then Return False
		Next 
		Return True
	End Method  
	
	Method GetAxis:TVec2[]( )
		Local axis:TVec2[count]
		For Local i:Int = 0 To count-1
			Local k:Int = i + 1
			If k > count-1 Then k = 0
			Local p1:TVec2 = Vertex( i )
			Local p2:Tvec2 = Vertex( k )
			Local edge:TVec2 = p1.Sub( p2 )
			Local normal:TVec2 = edge.Normal().Normalize()
			axis[i] = normal
		Next 
		Return axis
	End Method 
	
	Method Project:TProjection( axis:TVec2, offset:Tvec2 )
		Local amin:Float, amax:Float
		amin = axis.dot( vertex( 0 ) )
		amax = amin
		For Local i:Int = 1 To count-1
			Local p:Float = axis.dot( vertex(i) )
			If p > amax Then  
				amax = p
			ElseIf p < amin
				amin = p
			EndIf 
		Next 
		Local voffset:Float = axis.dot( offset )
		amin :+ voffset
		amax :+ voffset
		Return (New TProjection).Create( amin, amax )
	End Method 
	
	Method Vertex:TVec2( index:Int, glob:Byte=1 )
		index = Min( Max( index, 0 ), count-1 )
		Local p:TVec2 = TVec2( vertices.ValueAtIndex( index ) )
		If glob Then p = _getpos( p )
		Return p
	End Method 
End Type

Type TProjection
	Field val_min:Float
	Field val_max:Float
	Method Create:TProjection( mi:Float, ma:Float )
		val_min = mi
		val_max = ma
		If val_min > val_max Then 
			mi = val_max
			ma = val_min
			val_min = mi
			val_max = ma
		EndIf
		Return Self
	End Method 
	Method Overlap:Byte( p:TProjection )
		Local d1:Float = val_min - p.val_max
		Local d2:Float = p.val_min - val_max
		If d1 > 0 Or d2 > 0 Then Return True
		Return False
	End Method
End Type


Hier noch die "Vector.bmx aus der die TVec2-Klasse stammt:
BlitzMax: [AUSKLAPPEN] 
Type TVec2
	Field x:Float
	Field y:Float
	
	Method New( )
		x = 0
		y = 0
	End Method
	
	Method Copy:TVec2( vn:TVec2=Null )
		If vn = Null Then vn = New TVec2
		vn.x = x
		vn.y = y
		Return vn
	End Method  
	
	Method Turn:TVec2( a:Float )
		Local l:Float = GetL( )
		Return Vec2A( a+GetA( ), l )
	End Method 
	
	Method GetA:Float( )
		Return ATan2( y, x )
	End Method
	Method GetL:Float( )
		Return Sqr( x*x + y*y )
	End Method 
	
	Method _Print:String( )
		Return "["+x+","+y+"; "+GetA()+"° ]"
	End Method 
	
	Method TForm:TVec2( old_vec:TVec2, new_vec:TVec2 )
		If old_vec = Null Then old_vec = Vec2( 1, 0 )
		If new_vec = Null Then new_vec = Vec2( 1, 0 )
		Local da:TVec2 =  old_vec.DeltaA( new_vec.GetA() ) 
		Local l:Float = GetL()
		Local v:TVec2 = Vec2A( GetA() + da.GetA(), l )
		Return v
	End Method 
	
	Method DeltaA:TVec2( a:Float )
		Local a2:Float = GetA()
		Local d:Float = a2 - a
		If d < -180 Then d:+360
		If d > 180 Then d:-360
		Return Vec2A( d, GetL() )
	End Method 
	 
	
	Method Normalize:TVec2( )
		Local l:Float = GetL()
		If l = 0 Then Return Vec2()
		Return Vec2( x / l, y / l )
	End Method 
	
	Method Normal:TVec2( )
		Return Vec2( -y, x )
	End Method 
	
	Method Add:TVec2( v:TVec2, z:Int=1 )
		z = Sgn( z ) + (z=0)
		Return Vec2( x+z*v.x, y+z*v.y )
	End Method 
	
	Method Sub:TVec2( v:TVec2 )
		Return Vec2( x-v.x, y-v.y )
	End Method 
	
	Method Scalar:TVec2( v:Float )
		Return Vec2( x*v, y*v )
	End Method 
	
	Method Dot:Float( vec:TVec2 )
		Return x*vec.x + y*vec.y
	End Method 
End Type 

Function Vec2:TVec2( x:Float=0, y:Float=0 )
	Local v:TVec2 = New TVec2
	v.x = x
	v.y = y
	Return v
End Function 

Function Vec2A:TVec2( a:Float=0, l:Float=1 )
	Local v:TVec2 = New TVec2
	v.x = Cos( a )*l
	v.y = Sin( a )*l
	Return v
End Function

Function Vec2P:TVec2( p1:TVec2, p2:TVec2 )
	Return Vec2( p2.x-p1.x, p2.y-p1.y )
End Function 


Function AddVec( v1:TVec2, v2:TVec2, z:Int=1 )
	z = Sgn( z ) + (z=0)
	v1.x :+ z*v2.x
	v1.y :+ z*v2.y 
End Function 

Function Scalar:TVec2( v:TVec2, a:Float )
	Return Vec2( v.x*a, v.y*a )
End Function  

Function AddVecA( v1:TVec2, v2:TVec2, z:Int=1 )
	z = Sgn( z ) + (z=0)
	Local a:Float = v1.GetA() + z*v2.GetA()
	Local l:Float = v1.GetL()
	v1.x = Cos( a ) * l
	v1.y = Sin( a ) * l
End Function


Funktionieren tut hier leider gar nichts Sad
Meine Quelle: http://www.codezealot.org/archives/55

Hoffe ihr findet den Fehler.. ich hab echt keine Ahnung woran es liegt !

Lg
Religiöse Kriege sind Streitigkeiten erwachsener Männer darum, wer den besten imaginären Freund hat.
Race-Project - Das Rennspiel der etwas anderen Art
SimpleUDP3.0 - Neuste Version der Netzwerk-Bibliothek
Vielen Dank an dieser Stelle nochmal an Pummelie, welcher mir einen Teil seines VServers für das Betreiben meines Masterservers zur verfügung stellt!

ToeB

 BeitragMi, März 28, 2012 17:17
Antworten mit Zitat
Benutzer-Profile anzeigen
Okay, habs gelöst, lag an der prüfung der Überlappung der Projektionen. Hier die aktualisierte Version in TProjection:
BlitzMax: [AUSKLAPPEN] 
Method Overlap:Byte( p:TProjection )
		Local d1:Float = val_min - p.val_max
		Local d2:Float = p.val_min - val_max
		If d1 > 0 Or d2 > 0 Then Return False
		Return True
	End Method


Geht nun alles super aber trotzdem Danke den Leuten die sich vielleicht doch die mühe gegeben haben sich das wenigstens mal anzuschauen Wink

Lg
Religiöse Kriege sind Streitigkeiten erwachsener Männer darum, wer den besten imaginären Freund hat.
Race-Project - Das Rennspiel der etwas anderen Art
SimpleUDP3.0 - Neuste Version der Netzwerk-Bibliothek
Vielen Dank an dieser Stelle nochmal an Pummelie, welcher mir einen Teil seines VServers für das Betreiben meines Masterservers zur verfügung stellt!

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG Allgemein

Nach Oben

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group