Type TCollision

	Global list:TList=New TList ' list containing collision setup info
	'Global ent_list:TList=New TList ' list containing collision entities

	Global ent_lists:TList[100]

	Field src_type
	Field des_type
	Field col_method=0
	Field response=0
	
	' Set this to match application scale..
	Const unitsPerMeter# = 100.0
	
	Method New()
	
		If LOG_NEW
			DebugLog "New TCollision"
		EndIf
	
	End Method
	
	Method Delete()
	
		If LOG_DEL
			DebugLog "Del TCollision"
		EndIf
	
	End Method

	Function UpdateCollisions()

		For Local col:TCollision=EachIn TCollision.list
		
			If TCollision.ent_lists[col.src_type]=Null Or TCollision.ent_lists[col.des_type]=Null Then Continue
		
			For Local ent:TEntity=EachIn TCollision.ent_lists[col.src_type]
			
				ent.no_collisions=0
				ent.collision=ent.collision[..0]
				
				If ent.parent_hidden=True Or ent.hidden=True Then Continue
			
				For Local ent2:TEntity=EachIn TCollision.ent_lists[col.des_type]
				
					If ent2.parent_hidden=True Or ent2.hidden=True Then Continue

					If col.col_method=1
						
						If SphereToSphere(ent,ent2) ' dynamic sphere to sphere

							ent.no_collisions=ent.no_collisions+1			
							Local i=ent.no_collisions-1		
							ent.collision=ent.collision[..i+1]		
							ent.collision[i]=New TCollisionImpact
							ent.collision[i].ent=ent2
							
						EndIf
				
					EndIf
					
					If col.col_method=2
					
						If QuickCheck(ent,ent2)=True
						
							TMesh(ent2).TreeCheck() ' create collision tree for mesh if necessary

							SphereToMesh(ent,ent2) ' dynamic ellipsoid to static mesh (faster, limited ellipsoid support)
				
						EndIf
																
					EndIf
					
					' update src ent 'old' position
					ent2.old_x=ent2.EntityX(True)
					ent2.old_y=ent2.EntityY(True)
					ent2.old_z=ent2.EntityZ(True)
															
				Next
				
				' update src ent 'old' position
				ent.old_x=ent.EntityX(True)
				ent.old_y=ent.EntityY(True)
				ent.old_z=ent.EntityZ(True)
								
			Next
											
		Next
							
	End Function

	Function SphereToSphere(ent1:TEntity,ent2:TEntity,t#=0.0)

		Const EPSILON=0.001

		Local s1:TVector=TVector.Create(ent1.old_x#,ent1.old_y#,ent1.old_z#)
		Local sr1:Float=ent1.radius_x
		
		Local s2:TVector=TVector.Create(ent2.old_x#,ent2.old_y#,ent2.old_z#)
		Local sr2:Float=ent2.radius_x
										
		Local v1:TVector=New TVector
		v1.x=ent1.EntityX(True)-ent1.old_x#
		v1.y=ent1.EntityY(True)-ent1.old_y#
		v1.z=ent1.EntityZ(True)-ent1.old_z#
		
		Local v2:TVector=New TVector
		v2.x=ent2.EntityX(True)-ent2.old_x#
		v2.y=ent2.EntityY(True)-ent2.old_y#
		v2.z=ent2.EntityZ(True)-ent2.old_z#					
	
		Local s:TVector=New TVector
		s=s2.Subtract(s1)
		
		Local v:TVector=New TVector
		v=v2.Subtract(v1)
		
		Local r#=sr2+sr1
		Local c#=(s.Dot(s))-r*r
		
		If c<0.0
			' Spheres initially overlapping so exit directly
			t=0.0
			Return True
		EndIf
			
		Local a#=v.Dot(v)
		If a<EPSILON Return 0 ' Sphere not moving relative to each other
		
		Local b#=v.Dot(s)
		If b>=0.0 Return 0 ' Spheres not moving towards each other
		
		Local d#=(b*b)-(a*c)
		If d<0.0 Return 0 ' No real-value root, spheres do not interesect
		
		t=(-b-Sqr(d))/a

		If t>=0.0 And t<=1.0
			Return True 
		EndIf

	End Function
	
	' perform quick check to see whether it is possible that ent and ent 2 are intersecting
	Function QuickCheck(ent:TEntity,ent2:TEntity)
	
		' check to see if src ent has moved since last update - if not, no intersection
		Local ent_moved=False
		If ent.old_x<>ent.EntityX(True) Or ent.old_y<>ent.EntityY(True) Or ent.old_z<>ent.EntityZ(True) Then ent_moved=True
		If ent_moved=False Then Return False
		
		' check to see whether moving src ent intersects dest ent
		
		' get bounding box of moving src ent
		Local x1:Float,y1:Float,z1:Float,x2:Float,y2:Float,z2:Float
		
		BoxFromPoints(	ent.old_x#,ent.old_y#,ent.old_z#,..
						ent.EntityX(True),ent.EntityY(True),ent.EntityZ(True),..
						x1,y1,z1,x2,y2,z2)
						
		x1:-ent.radius_x
		y1:-ent.radius_y
		z1:-ent.radius_x
		x2:+ent.radius_x
		y2:+ent.radius_y
		z2:+ent.radius_x
		
		' get bounding sphere of dest ent
		Local sx:Float,sy:Float,sz:Float,sr:Float
		ent2.BoundingSphereNew(sx,sy,sz,sr)
		
		' check if box and sphere intersect
		If BoxSphereIntersection(x1,y1,z1,x2,y2,z2,sx,sy,sz,sr)=False Then Return False

		Return True
	
	End Function

	Function SphereToMesh(ent:TEntity,ent2:TEntity)
	
		' ent = source entity (sphere)
		' ent2 = destination entity (mesh)
		
		' create new collision 'packet' - used in SlideSphereAgainstMesh
		Global collisionPackage:TCollisionPacket=New TCollisionPacket
		collisionPackage.method_no=4
		collisionPackage.ent=ent
		collisionPackage.ent2=ent2
					
		' get src ent radius
		Local rx:Float=ent.radius_x
		Local ry:Float=ent.radius_y
		Local rz:Float=ent.radius_x
	
		' convert dest ent scale to src ent scale
		rx=rx/ent2.EntityScaleX(True)
		ry=ry/ent2.EntityScaleY(True)
		rz=rz/ent2.EntityScaleZ(True)	
				
		' get src ent 'old' position
		Local pos:TVector=TVector.Create(ent.old_x#,ent.old_y#,ent.old_z#)

		' get src ent velocity by subtracting old position from current position
		Local vel:TVector=TVector.Create(0.0,0.0,0.0)
		vel.x=ent.EntityX(True)-ent.old_x#
		vel.y=ent.EntityY(True)-ent.old_y#
		vel.z=ent.EntityZ(True)-ent.old_z#
	
		' convert src ent position to dest ent space
		TEntity.TFormPoint(pos.x,pos.y,pos.z,Null,ent2)
		pos.x=TEntity.tformed_x
		pos.y=TEntity.tformed_y
		pos.z=TEntity.tformed_z
	
		' convert src ent velocity to dest ent space
		TEntity.TFormVector(vel.x,vel.y,vel.z,Null,ent2)
		vel.x=TEntity.tformed_x
		vel.y=TEntity.tformed_y
		vel.z=TEntity.tformed_z
				
		' get bounding box of moving src ent transformed in dest ent space
		BoxFromPoints(	pos.x,pos.y,pos.z,..
						pos.x+vel.x,pos.y+vel.y,pos.z+vel.z,..
						collisionPackage.x1,collisionPackage.y1,collisionPackage.z1,..
						collisionPackage.x2,collisionPackage.y2,collisionPackage.z2)
		collisionPackage.x1:-rx
		collisionPackage.y1:-ry
		collisionPackage.z1:-rz
		collisionPackage.x2:+rx
		collisionPackage.y2:+ry
		collisionPackage.z2:+rz
		
		' convert src ent position, velocity to ellipsoid space
		pos.x=pos.x/rx
		pos.y=pos.y/ry
		pos.z=pos.z/rz
		
		vel.x=vel.x/rx
		vel.y=vel.y/ry
		vel.z=vel.z/rz

		' slide src ent against dest mesh, get final position
		Local fpos:TVector = SlideSphereAgainstMesh(pos,vel,collisionPackage,True)

		' convert final position back from ellipsoid space
		fpos.x=fpos.x*rx
		fpos.y=fpos.y*ry
		fpos.z=fpos.z*rz	

		' convert final position back from dest ent space to src ent space
		TEntity.TFormPoint(fpos.x,fpos.y,fpos.z,ent2,Null)
		fpos.x=TEntity.tformed_x
		fpos.y=TEntity.tformed_y
		fpos.z=TEntity.tformed_z

		' Position entity	
		ent.PositionEntity(fpos.x,fpos.y,fpos.z,True)
	
	End Function
	
	Function SlideSphereAgainstMesh:TVector(pos:TVector,vel:TVector,collisionPackage:TCollisionPacket,reset=False)

		Local ms=MilliSecs()
			
		Global collisionRecursionDepth
		If reset=True Then collisionRecursionDepth=0
	
		' All hard-coded distances in this function is
		' scaled to fit the setting above..
		Local unitScale# = unitsPerMeter / 100.0
		Local veryCloseDistance# = 0.001 * unitScale '0.005f * unitScale
		
		' do we need to worry?
		If collisionRecursionDepth>5 Or vel.length() < veryCloseDistance*2 Return pos
		
		' Ok, we need to worry:
		collisionPackage.velocity = vel.Copy()
		collisionPackage.normalizedVelocity = vel.Copy()
		collisionPackage.normalizedVelocity.normalize()
		collisionPackage.basePoint = pos.Copy()
		collisionPackage.foundCollision = False
		collisionPackage.nearestDistance = 10000000
			
		' Check for collision (calls the collision routines)
		' Application specific!!
		Local polys:TPolygon[]=TMesh(collisionPackage.ent2).col_tree.TreePolysBox(..
		collisionPackage.x1,collisionPackage.y1,collisionPackage.z1,..
		collisionPackage.x2,collisionPackage.y2,collisionPackage.z2)
				
		TCollision.PolysCheckCollision(collisionPackage:TCollisionPacket,polys)
		
		' If no collision we just move along the velocity
		If collisionPackage.foundCollision = False Return pos.Add(vel)

		' --- Collision occured ---
		' The original destination point
		Local destinationPoint:TVector = pos.Add(vel)
		Local newSourcePoint:TVector = pos.Copy()
		
		' only update if we are not already very close
		' and if so we only move very close to intersection..not
		' to the exact spot.
		Local V:TVector = vel.Copy()
		
		' If we are at the ideal point, just back off
		If(collisionPackage.nearestDistance=0.0) Return pos.Add(vel)

		V.SetLength( collisionPackage.nearestDistance)
		newSourcePoint = collisionPackage.basePoint.Add(V)

		' Determine the sliding plane
		Local slidePlaneNormal:TVector = newSourcePoint.Subtract(collisionPackage.intersectionPoint)
		slidePlaneNormal.normalize()

		' If this was the initial collision, ouput in CollisionTrace
		If collisionRecursionDepth=0
	
				Local ent:TEntity=collisionPackage.ent
				Local ent2:TEntity=collisionPackage.ent2
	
				ent.no_collisions=ent.no_collisions+1
							
				Local i=ent.no_collisions-1
							
				ent.collision=ent.collision[..i+1]
							
				ent.collision[i]=New TCollisionImpact
				ent.collision[i].x#=collisionPackage.intersectionPoint.x#
				ent.collision[i].y#=collisionPackage.intersectionPoint.y#
				ent.collision[i].z#=collisionPackage.intersectionPoint.z#
				ent.collision[i].nx#=slidePlaneNormal.x
				ent.collision[i].ny#=slidePlaneNormal.y
				ent.collision[i].nz#=slidePlaneNormal.z
				ent.collision[i].ent=ent2
				ent.collision[i].surf=collisionPackage.surf
				ent.collision[i].tri=collisionPackage.tri
		
				If collisionPackage.method_no=2
		
					' tform collision positions from model space into world space
					TEntity.TFormPoint(ent.collision[i].x#,ent.collision[i].y#,ent.collision[i].z#,ent2,Null)
					ent.collision[i].x#=TEntity.TFormedX#()
					ent.collision[i].y#=TEntity.TFormedY#()
					ent.collision[i].z#=TEntity.TFormedZ#()
				
				EndIf
				
				' tform collision positions from model space into world space
				TEntity.TFormNormal(ent.collision[i].nx#,ent.collision[i].ny#,ent.collision[i].nz#,ent2,Null)
				ent.collision[i].nx#=TEntity.TFormedX#()
				ent.collision[i].ny#=TEntity.TFormedY#()
				ent.collision[i].nz#=TEntity.TFormedZ#()
									
		EndIf
		
		' If no response needed, return the collision point
		'If collisionPackage.response=0
		
			'Return newSourcePoint
		
		'EndIf
	
		' Determine the displacement vector
		Local factor#
	
		V.SetLength(veryCloseDistance)
		If( V.dot(slidePlaneNormal) = 0.0)
			factor = 0.0;
		Else 
			factor = veryCloseDistance / ( V.dot(slidePlaneNormal) )
		EndIf
	
		Local displacementVector:TVector=V.Multiply(factor)

		' Move away
		newSourcePoint = newSourcePoint.Add(displacementVector)
		collisionPackage.intersectionPoint = collisionPackage.intersectionPoint.Add(displacementVector)
	
		Local slidePlaneOrigin:TVector = collisionPackage.intersectionPoint.Copy()	
		Local slidingPlane:TPlane=TPlane.CreatePlane(slidePlaneOrigin,slidePlaneNormal)
		
		' Again, sorry about formatting.. but look carefully )
		Local newDestinationPoint:TVector = destinationPoint.Subtract(slidePlaneNormal.Multiply(slidingPlane.signedDistanceTo(destinationPoint)))

		' Generate the slide vector, which will become our new
		' velocity vector for the next iteration
		Local newVelocityVector:TVector = newDestinationPoint.Subtract(collisionPackage.intersectionPoint)
	
		' Recurse:
		' dont recurse if the new velocity is very small	
		If (newVelocityVector.length() <= veryCloseDistance)
			Return newSourcePoint
		EndIf
	
		collisionRecursionDepth:+1
		Return SlideSphereAgainstMesh(newSourcePoint,newVelocityVector,collisionPackage)

	End Function
	
	' check col_tree polys for collision
	Function PolysCheckCollision(collisionPackage:TCollisionPacket,polys:TPolygon[])

		Const X=0,Y=1,Z=2

		Global col_pack:Float[14]
		Global a:Float[3]
		Global b:Float[3]
		Global c:Float[3]

		Local ent:TEntity=collisionPackage.ent
		Local ent2:TEntity=collisionPackage.ent2

		Local r:TVector=TVector.Create(0,0,0)
		r.x=ent.radius_x/ent2.EntityScaleX(True)
		r.y=ent.radius_y/ent2.EntityScaleY(True)
		r.z=ent.radius_x/ent2.EntityScaleZ(True)

		col_pack[0]=collisionPackage.velocity.x
		col_pack[1]=collisionPackage.velocity.y
		col_pack[2]=collisionPackage.velocity.z
		col_pack[3]=collisionPackage.normalizedVelocity.x
		col_pack[4]=collisionPackage.normalizedVelocity.y
		col_pack[5]=collisionPackage.normalizedVelocity.z
		col_pack[6]=collisionPackage.basePoint.x
		col_pack[7]=collisionPackage.basePoint.y
		col_pack[8]=collisionPackage.basePoint.z

		col_pack[9]=collisionPackage.foundCollision
		col_pack[10]=collisionPackage.nearestDistance
		col_pack[11]=collisionPackage.intersectionPoint.x
		col_pack[12]=collisionPackage.intersectionPoint.y
		col_pack[13]=collisionPackage.intersectionPoint.z

		For Local poly:TPolygon=EachIn polys

			If poly.no_verts=3
					
				a[X]=poly.verts[0].x; a[Y]=poly.verts[0].y; a[Z]=poly.verts[0].z
				b[X]=poly.verts[1].x; b[Y]=poly.verts[1].y; b[Z]=poly.verts[1].z
				c[X]=poly.verts[2].x; c[Y]=poly.verts[2].y; c[Z]=poly.verts[2].z

				a[X]:/r.x
				a[Y]:/r.y
				a[Z]:/r.z
				
				b[X]:/r.x
				b[Y]:/r.y
				b[Z]:/r.z
				
				c[X]:/r.x
				c[Y]:/r.y
				c[Z]:/r.z
				
				Local check_tri=False
				
				If USE_C
					check_tri=C_checkTriangle(col_pack,a,b,c)
				Else
					check_tri=CheckTriangle(collisionPackage,a,b,c)
				EndIf
				
				If check_tri
				
					If USE_C
						collisionPackage.foundCollision=col_pack[9]
						collisionPackage.nearestDistance=col_pack[10]
						collisionPackage.intersectionPoint.x=col_pack[11]
						collisionPackage.intersectionPoint.y=col_pack[12]
						collisionPackage.intersectionPoint.z=col_pack[13]
					EndIf
							
					collisionPackage.collision=True
					collisionPackage.surf=poly.surf
					collisionPackage.tri=poly.tri
					collisionPackage.no_tris=collisionPackage.no_tris+1

				EndIf

			EndIf
			
		Next

	End Function
	
	' and below a function that’ll check a single triangle for collision:
	' Assumes: p1,p2 And p3 are given in ellipsoid space:
	Function CheckTriangle(colPackage:TCollisionPacket Var,a:Float[],b:Float[],c:Float[])
		
		Local p1:TVector=TVector.Create(a[0],a[1],a[2])
		Local p2:TVector=TVector.Create(b[0],b[1],b[2])
		Local p3:TVector=TVector.Create(c[0],c[1],c[2])
		
		' Make the plane containing this triangle.
		Local trianglePlane:TPlane=TPlane.CreatePlaneFromTriangle(p1,p2,p3)
		
		' Is triangle front-facing to the velocity vector?
		' We only check front-facing triangles
		' (your choice of course)
		If (trianglePlane.isFrontFacingTo(colPackage.normalizedVelocity))
		
			' Get interval of plane intersection:
			Local t0#, t1#
			
			Local embeddedInPlane = False
			
			' Calculate the signed distance from sphere position to triangle plane
			Local signedDistToTrianglePlane# = trianglePlane.signedDistanceTo(colPackage.basePoint)
			
			' cache this as we’re going to use it a few times below:
			Local normalDotVelocity# = trianglePlane.normal.Dot(colPackage.velocity)
			
			' If sphere is travelling parrallel to the plane:
			If (normalDotVelocity = 0.0)
					
				If (Abs(signedDistToTrianglePlane) >= 1.0)
				
					' Sphere is not embedded in plane.
					' No collision possible:
					Return
					
				Else
		
					' sphere is embedded in plane.
					' It intersects in the whole range [0..1]
					embeddedInPlane = True
					t0 = 0.0
					t1 = 1.0
					
				EndIf
	
			Else
			
				' N dot D is Not 0. Calculate intersection interval:
				t0=(-1.0-signedDistToTrianglePlane)/normalDotVelocity
				t1=( 1.0-signedDistToTrianglePlane)/normalDotVelocity
		
				' Swap so t0 < t1
				If (t0 > t1)
					Local temp# = t1
					t1# = t0
					t0 = temp
				EndIf
				
				' Check that at least one result is within range:
				If (t0 > 1.0 Or t1 < 0.0)
				
					' Both t values are outside values [0,1]
					' No collision possible:
					Return
				
				EndIf
		
				' Clamp To [0,1]
				If (t0 < 0.0) t0 = 0.0
				If (t1 < 0.0) t1 = 0.0
				If (t0 > 1.0) t0 = 1.0
				If (t1 > 1.0) t1 = 1.0
				
			EndIf
	
			' OK, at this point we have two time values t0 and t1
			' between which the swept sphere intersects with the
			' triangle plane. If any collision is to occur it must
			' happen within this interval.
			Local collisionPoint:TVector
			Local foundCollison = False
			Local t# = 1.0
		
			' First we check for the easy case - collision inside
			' the triangle. If this happens it must be at time t0
			' as this is when the sphere rests on the front side
			' of the triangle plane. Note, this can only happen if
			' the sphere is Not embedded in the triangle plane.
			If (Not embeddedInPlane)
				Local planeIntersectionPoint:TVector = (colPackage.basePoint.Subtract(trianglePlane.normal)).Add(colPackage.velocity.Multiply(t0))
				If (checkPointInTriangle(planeIntersectionPoint,p1,p2,p3))
					foundCollison = True
					t = t0
					collisionPoint=planeIntersectionPoint.Copy()
				EndIf
			EndIf
				
			' If we haven’t found a collision already we’ll have to
			' sweep sphere against points and edges of the triangle.
			' Note: A collision inside the triangle (the check above)
			' will always happen before a vertex or edge collision!
			' This is why we can skip the swept test if the above
			' gives a collision!
			If foundCollison = False
			
				' some commonly used terms:
				Local velocity:TVector = colPackage.velocity.Copy()
				Local base:TVector = colPackage.basePoint.Copy()
				Local velocitySquaredLength# = velocity.squaredLength()
				Local a#,b#,c# ' params for equation
				Local newT:Float
							
				' For each vertex or edge a quadratic equation have to
				' be solved. We parameterize this equation as
				' a*t^2 + b*t + c = 0 and below we calculate the
				' parameters a,b And c for each test.
				
				' Check against points:
				
				a = velocitySquaredLength
				
				' P1
				b = 2.0*(velocity.Dot(base.Subtract(p1)))
				c = (p1.Subtract(base)).squaredLength() - 1.0
				If getLowestRoot(a,b,c,t,newT)
					t = newT
					foundCollison = True
					collisionPoint = p1.Copy()
				EndIf
				
				' P2
				b = 2.0*(velocity.dot(base.Subtract(p2)))
				c = (p2.Subtract(base)).squaredLength() - 1.0
				If getLowestRoot(a,b,c,t,newT)
					t = newT
					foundCollison = True
					collisionPoint = p2.Copy()
				EndIf
				
				' P3
				b = 2.0*(velocity.dot(base.Subtract(p3)))
				c = (p3.Subtract(base)).squaredLength() - 1.0
				If getLowestRoot(a,b,c,t,newT)
					t = newT
					foundCollison = True
					collisionPoint = p3.Copy()
				EndIf
				
				' Check against edges:
				
				' p1 . p2:
				Local edge:TVector = p2.Subtract(p1)
				Local baseToVertex:TVector = p1.Subtract(base)
				Local edgeSquaredLength# = edge.squaredLength()
				Local edgeDotVelocity# = edge.Dot(velocity)
				Local edgeDotBaseToVertex# = edge.Dot(baseToVertex)
				
				' Calculate parameters for equation
				a = edgeSquaredLength*-velocitySquaredLength +edgeDotVelocity*edgeDotVelocity
				b = edgeSquaredLength*(2*velocity.dot(baseToVertex))-2.0*edgeDotVelocity*edgeDotBaseToVertex
				c = edgeSquaredLength*(1-baseToVertex.squaredLength())+edgeDotBaseToVertex*edgeDotBaseToVertex
				
				' Does the swept sphere collide against infinite edge?
				If getLowestRoot(a,b,c,t,newT)
					' Check if intersection is within line segment:
					Local f#=(edgeDotVelocity*newT-edgeDotBaseToVertex)/edgeSquaredLength
					If f >= 0.0 And f <= 1.0
						' intersection took place within segment.
						t = newT
						foundCollison = True
						collisionPoint = p1.Add(edge.Multiply(f))
					EndIf
				EndIf
				
				' p2 . p3:
				edge:TVector = p3.Subtract(p2)
				baseToVertex:TVector = p2.Subtract(base)
				edgeSquaredLength# = edge.squaredLength()
				edgeDotVelocity# = edge.Dot(velocity)
				edgeDotBaseToVertex# = edge.Dot(baseToVertex)
				a = edgeSquaredLength*-velocitySquaredLength +edgeDotVelocity*edgeDotVelocity
				b = edgeSquaredLength*(2*velocity.dot(baseToVertex))-2.0*edgeDotVelocity*edgeDotBaseToVertex
				c = edgeSquaredLength*(1-baseToVertex.squaredLength())+edgeDotBaseToVertex*edgeDotBaseToVertex
				If getLowestRoot(a,b,c,t,newT)
					Local f#=(edgeDotVelocity*newT-edgeDotBaseToVertex)/edgeSquaredLength
					If (f >= 0.0 And f <= 1.0)
						t = newT
						foundCollison = True
						collisionPoint = p2.Add(edge.Multiply(f))
					EndIf
				EndIf
				
				' p3 . p1:
				edge:TVector = p1.Subtract(p3)
				baseToVertex:TVector = p3.Subtract(base)
				edgeSquaredLength# = edge.squaredLength()
				edgeDotVelocity# = edge.Dot(velocity)
				edgeDotBaseToVertex# = edge.Dot(baseToVertex)
				a = edgeSquaredLength*-velocitySquaredLength +edgeDotVelocity*edgeDotVelocity
				b = edgeSquaredLength*(2*velocity.dot(baseToVertex))-2.0*edgeDotVelocity*edgeDotBaseToVertex
				c = edgeSquaredLength*(1-baseToVertex.squaredLength())+edgeDotBaseToVertex*edgeDotBaseToVertex
				If getLowestRoot(a,b,c,t,newT)
					Local f#=(edgeDotVelocity*newT-edgeDotBaseToVertex)/edgeSquaredLength
					If (f >= 0.0 And f <= 1.0)
						t = newT
						foundCollison = True
						collisionPoint = p3.Add(edge.Multiply(f))
					EndIf
				EndIf
				
			EndIf
				
			' Set result:
			If (foundCollison = True)
	
				' distance To collision: ’t’ is time of collision
				Local distToCollision# = t*colPackage.velocity.length()
			
				' Does this triangle qualify for the closest hit?
				' it does if it’s the first hit or the closest
				If (colPackage.foundCollision = False Or distToCollision < colPackage.nearestDistance)
				
					' Collision information nessesary for sliding
					colPackage.nearestDistance = distToCollision
					colPackage.intersectionPoint=collisionPoint.Copy()
				
					colPackage.foundCollision = True
					
					Return True
				
				EndIf
			
			EndIf ' If Not backface
	
		EndIf
			
	End Function

	Rem
	Utility functions
	Below is a Function that determines if a point is inside a triangle Or not. This
	is used in the collision detection step.
	End Rem
	Function CheckPointInTriangle(p:TVector,a:TVector,b:TVector,c:TVector)
		
		Local u#,v#,w#
		
		Barycentric(a,b,c,p,u#,v#,w#)
	
		If v>=0.0 And w>=0.0 And (v+w) <= 1.0 Return True Else Return False
	
	End Function

	Function Barycentric(a:TVector,b:TVector,c:TVector,p:TVector,u# Var,v# Var,w# Var)
	
		Local v0:TVector=b.Subtract(a)
		Local v1:TVector=c.Subtract(a)
		Local v2:TVector=p.Subtract(a)
		
		Local d00#=v0.Dot(v0)
		Local d01#=v0.Dot(v1)
		Local d11#=v1.Dot(v1)
		Local d20#=v2.Dot(v0)
		Local d21#=v2.Dot(v1)
		Local denom#=d00*d11-d01*d01
		
		v=(d11*d20-d01*d21)/denom
		w=(d00*d21-d01*d20)/denom
		u=1.0-v-w
	
	End Function

	Rem
	Solving quadratic equations
	Below is a snippet of code that solves a quadratic equation And returns the
	lowest root, below a certain treshold (the maxR parameter):
	End Rem

	Function getLowestRoot(a#,b#,c#,maxR#,root# Var)
		
		' Check if a solution exists
		Local determinant# = b*b - 4.0*a*c
		
		' If determinant is negative it means no solutions.
		If (determinant < 0.0) Return False
		
		' calculate the two roots: (If determinant == 0 then
		' x1==x2 but let’s disregard that slight optimization)
		Local sqrtD# = Sqr(determinant)
		Local r1# = (-b - sqrtD#) / (2*a)
		Local r2# = (-b + sqrtD#) / (2*a)
		
		' Sort so x1 <= x2
		If (r1 > r2)
			Local temp# = r2
			r2 = r1
			r1 = temp
		EndIf
		
		' Get lowest root
		If (r1 > 0 And r1 < maxR)
			root = r1
			Return True
		EndIf
	
		' It is possible that we want x2 - this can happen
		' If x1 < 0
		If (r2 > 0 And r2 < maxR)
			root = r2
			Return True
		EndIf
		
		' No (valid) solutions
		Return False
		
	End Function

End Type

Rem
Data about the move is coming in through the
CollisionPacket and this is also where we put the result of the check against
the triangle.
End Rem
Type TCollisionPacket

	Method New()
	
		If LOG_NEW
			DebugLog "New TCollisionPacket"
		EndIf
	
	End Method
	
	Method Delete()
	
		If LOG_DEL
			DebugLog "Del TCollisionPacket"
		EndIf
	
	End Method
		
	' added

	Field method_no
	Field response

	Field ent:TEntity
	Field ent2:TEntity

	Field x1:Float,x2:Float,y1:Float,y2:Float,z1:Float,z2:Float ' bounding box of moving sphere in dest ent space
	
	Field collision
	
	Field no_tris
	Field tri
	Field surf:TSurface
	
	' original

	' Information about the move being requested: (in R3)
	Field R3Velocity:TVector=New TVector
	Field R3Position:TVector=New TVector
	
	' Information about the move being requested: (in eSpace)
	Field velocity:TVector=New TVector
	Field normalizedVelocity:TVector=New TVector
	Field basePoint:TVector=New TVector
	
	' Hit information
	Field foundCollision
	Field nearestDistance#
	Field intersectionPoint:TVector=New TVector
			
End Type

Type TCollisionImpact

	Method New()
		
		If LOG_NEW
			DebugLog "New TCollisionImpact"
		EndIf
	
	End Method
	
	Method Delete()
	
		If LOG_DEL
			DebugLog "Del TCollisionImpact"
		EndIf

	End Method

	Field x#,y#,z#
	Field nx#,ny#,nz#
	Field time#
	Field ent:TEntity
	Field surf:TSurface
	Field tri

End Type
