static int Ballistics( const idVec3 &start, const idVec3 &end, float speed, float gravity, ballistics_t bal[2] ) {
	int n, i;
	float x, y, a, b, c, d, sqrtd, inva, p[2];

	x = ( end.ToVec2() - start.ToVec2() ).Length();
	y = end[2] - start[2];

	a = 4.0f * y * y + 4.0f * x * x;
	b = -4.0f * speed * speed - 4.0f * y * gravity;
	c = gravity * gravity;

	d = b * b - 4.0f * a * c;
	if ( d <= 0.0f || a == 0.0f ) {
		return 0;
	}
	sqrtd = idMath::Sqrt( d );
	inva = 0.5f / a;
	p[0] = ( - b + sqrtd ) * inva;
	p[1] = ( - b - sqrtd ) * inva;
	n = 0;
	for ( i = 0; i < 2; i++ ) {
		if ( p[i] <= 0.0f ) {
			continue;
		}
		d = idMath::Sqrt( p[i] );
		bal[n].angle = atan2( 0.5f * ( 2.0f * y * p[i] - gravity ) / d, d * x );
		bal[n].time = x / ( cos( bal[n].angle ) * speed );
		bal[n].angle = idMath::AngleNormalize180( RAD2DEG( bal[n].angle ) );
		n++;
	}

	return n;
}

/*
===================
R_ClipLineToLight

If neither point is clearly behind the clipping
plane, the edge will be passed unmodified.  A sil edge that
is on a border plane must be drawn.

If one point is clearly clipped by the plane and the
other point is on the plane, it will be completely removed.
===================
*/
ID_STATIC_TEMPLATE ID_INLINE bool R_ClipLineToLight( const idVec3 &a, const idVec3 &b, const idPlane frustum[6], idVec3 &p1, idVec3 &p2 ) {
	float	*clip;
	int		j;
	float	d1, d2;
	float	f;
	p1 = a;
	p2 = b;
	// clip it
	for( j = 0; j < 6; j++ ) {
		d1 = frustum[j].Distance( p1 );
		d2 = frustum[j].Distance( p2 );
		// if both on or in front, not clipped to this plane
		if( d1 > -LIGHT_CLIP_EPSILON && d2 > -LIGHT_CLIP_EPSILON ) {
			continue;
		}
		// if one is behind and the other isn't clearly in front, the edge is clipped off
		if( d1 <= -LIGHT_CLIP_EPSILON && d2 < LIGHT_CLIP_EPSILON ) {
			return false;
		}
		if( d2 <= -LIGHT_CLIP_EPSILON && d1 < LIGHT_CLIP_EPSILON ) {
			return false;
		}
		// clip it, keeping the negative side
		if( d1 < 0 ) {
			clip = p1.ToFloatPtr();
		} else {
			clip = p2.ToFloatPtr();
		}
		f = d1 / ( d1 - d2 );
		clip[0] = p1[0] + f * ( p2[0] - p1[0] );
		clip[1] = p1[1] + f * ( p2[1] - p1[1] );
		clip[2] = p1[2] + f * ( p2[2] - p1[2] );
	}
	return true;	// retain a fragment
}

void idSimpleWindow::SetupTransforms( float x, float y )
{
	static idMat3 trans;
	static idVec3 org;
	
	trans.Identity();
	org.Set( origin.x + x, origin.y + y, 0 );
	if( rotate )
	{
		static idRotation rot;
		static idVec3 vec( 0, 0, 1 );
		rot.Set( org, vec, rotate );
		trans = rot.ToMat3();
	}
	
	static idMat3 smat;
	smat.Identity();
	if( shear.x() || shear.y() )
	{
		smat[0][1] = shear.x();
		smat[1][0] = shear.y();
		trans *= smat;
	}
	
	if( !trans.IsIdentity() )
	{
		dc->SetTransformInfo( org, trans );
	}
}

/*
============
idAASLocal::GetEdge
============
*/
void idAASLocal::GetEdge( int edgeNum, idVec3 &start, idVec3 &end ) const {
	if ( !file ) {
		start.Zero();
		end.Zero();
		return;
	}
	const int *v = file->GetEdge( abs(edgeNum) ).vertexNum;
	start = file->GetVertex( v[INTSIGNBITSET(edgeNum)] );
	end = file->GetVertex( v[INTSIGNBITNOTSET(edgeNum)] );
}

/*
============
idAI::FindPathAroundObstacles

  Finds a path around dynamic obstacles using a path tree with clockwise and counter clockwise edge walks.
============
*/
bool idAI::FindPathAroundObstacles( const idPhysics *physics, const idAAS *aas, const idEntity *ignore, const idVec3 &startPos, const idVec3 &seekPos, obstaclePath_t &path ) {
	int numObstacles, areaNum, insideObstacle;
	obstacle_t obstacles[MAX_OBSTACLES];
	idBounds clipBounds;
	idBounds bounds;
	pathNode_t *root;
	bool pathToGoalExists;
	path.seekPos = seekPos;
	path.firstObstacle = NULL;
	path.startPosOutsideObstacles = startPos;
	path.startPosObstacle = NULL;
	path.seekPosOutsideObstacles = seekPos;
	path.seekPosObstacle = NULL;
	if( !aas ) {
		return true;
	}
	bounds[1] = aas->GetSettings()->boundingBoxes[0][1];
	bounds[0] = -bounds[1];
	bounds[1].z = 32.0f;
	// get the AAS area number and a valid point inside that area
	areaNum = aas->PointReachableAreaNum( path.startPosOutsideObstacles, bounds, ( AREA_REACHABLE_WALK | AREA_REACHABLE_FLY ) );
	aas->PushPointIntoAreaNum( areaNum, path.startPosOutsideObstacles );
	// get all the nearby obstacles
	numObstacles = GetObstacles( physics, aas, ignore, areaNum, path.startPosOutsideObstacles, path.seekPosOutsideObstacles, obstacles, MAX_OBSTACLES, clipBounds );
	// get a source position outside the obstacles
	GetPointOutsideObstacles( obstacles, numObstacles, path.startPosOutsideObstacles.ToVec2(), &insideObstacle, NULL );
	if( insideObstacle != -1 ) {
		path.startPosObstacle = obstacles[insideObstacle].entity;
	}
	// get a goal position outside the obstacles
	GetPointOutsideObstacles( obstacles, numObstacles, path.seekPosOutsideObstacles.ToVec2(), &insideObstacle, NULL );
	if( insideObstacle != -1 ) {
		path.seekPosObstacle = obstacles[insideObstacle].entity;
	}
	// if start and destination are pushed to the same point, we don't have a path around the obstacle
	if( ( path.seekPosOutsideObstacles.ToVec2() - path.startPosOutsideObstacles.ToVec2() ).LengthSqr() < Square( 1.0f ) ) {
		if( ( seekPos.ToVec2() - startPos.ToVec2() ).LengthSqr() > Square( 2.0f ) ) {
			return false;
		}
	}
	// build a path tree
	root = BuildPathTree( obstacles, numObstacles, clipBounds, path.startPosOutsideObstacles.ToVec2(), path.seekPosOutsideObstacles.ToVec2(), path );
	// draw the path tree
	if( ai_showObstacleAvoidance.GetBool() ) {
		DrawPathTree( root, physics->GetOrigin().z );
	}
	// prune the tree
	PrunePathTree( root, path.seekPosOutsideObstacles.ToVec2() );
	// find the optimal path
	pathToGoalExists = FindOptimalPath( root, obstacles, numObstacles, physics->GetOrigin().z, physics->GetLinearVelocity(), path.seekPos );
	// free the tree
	FreePathTree_r( root );
	return pathToGoalExists;
}

/*
================
idBrittleFracture::DropShard
================
*/
void idBrittleFracture::DropShard( shard_t* shard, const idVec3& point, const idVec3& dir, const float impulse, const int time )
{
	int i, j, clipModelId;
	float dist, f;
	idVec3 dir2, origin;
	idMat3 axis;
	shard_t* neighbour;
	
	// don't display decals on dropped shards
	shard->decals.DeleteContents( true );
	
	// remove neighbour pointers of neighbours pointing to this shard
	for( i = 0; i < shard->neighbours.Num(); i++ )
	{
		neighbour = shard->neighbours[i];
		for( j = 0; j < neighbour->neighbours.Num(); j++ )
		{
			if( neighbour->neighbours[j] == shard )
			{
				neighbour->neighbours.RemoveIndex( j );
				break;
			}
		}
	}
	
	// remove neighbour pointers
	shard->neighbours.Clear();
	
	// remove the clip model from the static physics object
	clipModelId = shard->clipModel->GetId();
	physicsObj.SetClipModel( NULL, 1.0f, clipModelId, false );
	
	origin = shard->clipModel->GetOrigin();
	axis = shard->clipModel->GetAxis();
	
	// set the dropped time for fading
	shard->droppedTime = time;
	
	dir2 = origin - point;
	dist = dir2.Normalize();
	f = dist > maxShatterRadius ? 1.0f : idMath::Sqrt( idMath::Fabs( dist - minShatterRadius ) ) * ( 1.0f / idMath::Sqrt( idMath::Fabs( maxShatterRadius - minShatterRadius ) ) );
	
	// setup the physics
	shard->physicsObj.SetSelf( this );
	shard->physicsObj.SetClipModel( shard->clipModel, density );
	shard->physicsObj.SetMass( shardMass );
	shard->physicsObj.SetOrigin( origin );
	shard->physicsObj.SetAxis( axis );
	shard->physicsObj.SetBouncyness( bouncyness );
	shard->physicsObj.SetFriction( 0.6f, 0.6f, friction );
	shard->physicsObj.SetGravity( gameLocal.GetGravity() );
	shard->physicsObj.SetContents( CONTENTS_RENDERMODEL );
	shard->physicsObj.SetClipMask( MASK_SOLID | CONTENTS_MOVEABLECLIP );
	shard->physicsObj.ApplyImpulse( 0, origin, impulse * linearVelocityScale * dir );
	shard->physicsObj.SetAngularVelocity( dir.Cross( dir2 ) * ( f * angularVelocityScale ) );
	
	shard->clipModel->SetId( clipModelId );
	
	BecomeActive( TH_PHYSICS );
}

float Aimbot::AdvancedHumanization( float distance, idVec3 targetVelocity )
{
	//targetVelocity.z = 0;
	float targetSpeed = targetVelocity.Length(); //speed in units/seconds
	float returnValue = max( distance / 1000.0f, 1.192092896e-07f );
	return returnValue + targetSpeed / 320.0f;
}

/*
=====================
idPhysics_Monster::SlideMove
=====================
*/
monsterMoveResult_t idPhysics_Monster::SlideMove(idVec3 &start, idVec3 &velocity, const idVec3 &delta)
{
	int i;
	trace_t tr;
	idVec3 move;

	blockingEntity = NULL;
	move = delta;

	for (i = 0; i < 3; i++) {
		gameLocal.clip.Translation(tr, start, start + move, clipModel, clipModel->GetAxis(), clipMask, self);

		start = tr.endpos;

		if (tr.fraction == 1.0f) {
			if (i > 0) {
				return MM_SLIDING;
			}

			return MM_OK;
		}

		if (tr.c.entityNum != ENTITYNUM_NONE) {
			blockingEntity = gameLocal.entities[ tr.c.entityNum ];
		}

		// clip the movement delta and velocity
		move.ProjectOntoPlane(tr.c.normal, OVERCLIP);
		velocity.ProjectOntoPlane(tr.c.normal, OVERCLIP);
	}

	return MM_BLOCKED;
}

/*
============
idAASSettings::ParseVector
============
*/
bool idAASSettings::ParseVector( idLexer &src, idVec3 &vec )
{
    if ( !src.ExpectTokenString( "=" ) )
    {
        return false;
    }
    return ( src.Parse1DMatrix( 3, vec.ToFloatPtr() ) != 0 );
}

/*
================
idCollisionModelManagerLocal::CollisionBetweenEdgeBounds

  verifies if the collision of two edges occurs between the edge bounds
  also calculates the collision point and collision plane normal if the collision occurs between the bounds
================
*/
int idCollisionModelManagerLocal::CollisionBetweenEdgeBounds( cm_traceWork_t *tw, const idVec3 &va, const idVec3 &vb,
												   const idVec3 &vc, const idVec3 &vd, float tanHalfAngle,
												   idVec3 &collisionPoint, idVec3 &collisionNormal ) {
	float d1, d2, d;
	idVec3 at, bt, dir, dir1, dir2;
	idPluecker	pl1, pl2;

	at = va;
	bt = vb;
	if ( tanHalfAngle != 0.0f ) {
		CM_RotateEdge( at, bt, tw->origin, tw->axis, tanHalfAngle );
	}

	dir1 = (at - tw->origin).Cross( tw->axis );
	dir2 = (bt - tw->origin).Cross( tw->axis );
	if ( dir1 * dir1 > dir2 * dir2 ) {
		dir = dir1;
	}
	else {
		dir = dir2;
	}
	if ( tw->angle < 0.0f ) {
		dir = -dir;
	}

	pl1.FromLine( at, bt );
	pl2.FromRay( vc, dir );
	d1 = pl1.PermutedInnerProduct( pl2 );
	pl2.FromRay( vd, dir );
	d2 = pl1.PermutedInnerProduct( pl2 );
	if ( ( d1 > 0.0f && d2 > 0.0f ) || ( d1 < 0.0f && d2 < 0.0f ) ) {
		return false;
	}

	pl1.FromLine( vc, vd );
	pl2.FromRay( at, dir );
	d1 = pl1.PermutedInnerProduct( pl2 );
	pl2.FromRay( bt, dir );
	d2 = pl1.PermutedInnerProduct( pl2 );
	if ( ( d1 > 0.0f && d2 > 0.0f ) || ( d1 < 0.0f && d2 < 0.0f ) ) {
		return false;
	}

	// collision point on the edge at-bt
	dir1 = (vd - vc).Cross( dir );
	d = dir1 * vc;
	d1 = dir1 * at - d;
	d2 = dir1 * bt - d;
	if ( d1 == d2 ) {
		return false;
	}
	collisionPoint = at + ( d1 / (d1 - d2) ) * ( bt - at );

	// normal is cross product of the rotated edge va-vb and the edge vc-vd
	collisionNormal.Cross( bt-at, vd-vc );

	return true;
}

/*
=================
R_MirrorVector
=================
*/
static void R_MirrorVector( const idVec3 in, orientation_t* surface, orientation_t* camera, idVec3& out )
{
	out.Zero();
	for( int i = 0; i < 3; i++ )
	{
		const float d = in * surface->axis[i];
		out += d * camera->axis[i];
	}
}

/*
============
idAASLocal::GetAreaNumAndLocation
============
*/
bool idAASLocal::GetAreaNumAndLocation( idCVar &cvar, const idVec3 &origin, int &areaNum, idVec3 &location ) const {

	areaNum = 0;
	location.Zero();

	if ( cvar.GetString()[0] == '\0' ) {
		return false;
	}

	if ( idStr::Icmp( cvar.GetString(), "memory" ) == 0 ) {
		cvar.SetString( aas_locationMemory.GetString() );
	}

	if ( idStr::Icmp( cvar.GetString(), "current" ) == 0 ) {
		cvar.SetString( origin.ToString() );
	}

	idLexer src( LEXFL_NOERRORS|LEXFL_NOWARNINGS );
	src.LoadMemory( cvar.GetString(), idStr::Length( cvar.GetString() ), "areaNum" );

	bool error = false;
	location.x = src.ParseFloat( &error );
	location.y = src.ParseFloat( &error );
	location.z = src.ParseFloat( &error );

	if ( !error ) {
		areaNum = PointReachableAreaNum( location, DefaultSearchBounds(), AAS_AREA_REACHABLE_WALK, TravelFlagInvalidForTeam() );
		PushPointIntoArea( areaNum, location );
		return true;
	}

	src.Reset();

	areaNum = src.ParseInt();

	if ( ( areaNum > 0 ) && ( areaNum < file->GetNumAreas() ) ) {
		location = AreaCenter( areaNum );
		return true;
	}

	return false;
}

/*
================
idDict::GetVector
================
*/
bool idDict::GetVector( const char *key, const char *defaultString, idVec3 &out ) const {
	bool		found;
	const char	*s;
	if( !defaultString ) {
		defaultString = "0 0 0";
	}
	found = GetString( key, defaultString, &s );
	out.Zero();
	sscanf( s, "%f %f %f", &out.x, &out.y, &out.z );
	return found;
}

/*
================
idThread::Event_VecToOrthoBasisAngles
================
*/
void idThread::Event_VecToOrthoBasisAngles( idVec3 &vec ) {
	idVec3 left, up;
	idAngles ang;

	vec.OrthogonalBasis( left, up );
	idMat3 axis( left, up, vec );

	ang = axis.ToAngles();

	ReturnVector( idVec3( ang[0], ang[1], ang[2] ) );
}

/*
================
idLiquid::Collide
Spawns a splash particle and attaches a sound to the colliding entity.
================
*/
bool idLiquid::Collide( const trace_t &collision, const idVec3 &velocity ) {
	idEntity *e = gameLocal.entities[collision.c.entityNum];
	idPhysics_Liquid *phys = static_cast<idPhysics_Liquid *>( this->GetPhysics() );
	const idDeclParticle *splash;
	const char *sName;
	float eMass;
	idVec3 splashSpot;
	float velSquare = velocity.LengthSqr();
	ProcCollisionStims( e, collision.c.id );
	eMass = e->GetPhysics()->GetMass();
	splashSpot = collision.c.point;
	if( velSquare > phys->GetMinSplashVelocity().LengthSqr() ) {
		// pick which splash particle to spawn
		// first we check the entity, if it's not defined we use
		// one defined for this liquid.
		sName = e->spawnArgs.GetString( this->smokeName.c_str() );
		if( *sName != '\0' ) {
			// load entity particle
			splash = static_cast<const idDeclParticle *>( declManager->FindType( DECL_PARTICLE, sName ) );
		} else {
			// load a liquid particle based on the mass of the splashing entity
			if( eMass < SMALL_SPLASH ) {
				splash = this->splash[0];
			} else if( eMass < MEDIUM_SPLASH ) {
				splash = this->splash[1];
			} else {
				splash = this->splash[2];
			}
		}
		// play the sound for a splash
		e->StartSound( this->soundName.c_str(), SND_CHANNEL_ANY, 0, false, NULL );
		// grayman #3413 - propagate the global sound for the splash
		idStr size = e->spawnArgs.GetString( "spr_object_size" );
		if( size.IsEmpty() ) {
			if( eMass < SMALL_SPLASH ) {
				size = "small";
			} else if( eMass < MEDIUM_SPLASH ) {
				size = "medium";
			} else {
				size = "large";
			}
		}
		idStr splashName = idStr( "splash_" ) + size;
		e->PropSoundS( NULL, splashName, 0, 0 );
	} else if( velSquare > phys->GetMinWaveVelocity().LengthSqr() ) {
		splash = this->waves;
	} else {
		// the object is moving to slow so we abort
		return true;
	}
	// spawn the particle
	gameLocal.smokeParticles->EmitSmoke( splash, gameLocal.time, gameLocal.random.RandomFloat(), splashSpot, collision.endAxis );
	return true;
}

/*
=====================
sdClientAnimated::GetJointWorldTransform
=====================
*/
bool sdClientAnimated::GetJointWorldTransform( jointHandle_t jointHandle, int currentTime, idVec3 &offset, idMat3 &axis ) {
	if ( !animator.GetJointTransform( jointHandle, currentTime, offset, axis ) ) {
		offset.Zero();
		axis.Identity();
		return false;
	}

	offset = renderEntity.origin + offset * renderEntity.axis;
	axis *= renderEntity.axis;
	return true;
}

/*
================
CM_RotateEdge

  rotates an edge about an arbitrary axis using the tangent of half the rotation angle
================
*/
void CM_RotateEdge( idVec3 &start, idVec3 &end, const idVec3 &origin, const idVec3 &axis, const float tanHalfAngle ) {
	double d, t, s, c;
	idVec3 proj, v1, v2;
	// r = tan( a / 2 );
	// sin(a) = 2*r/(1+r*r);
	// cos(a) = (1-r*r)/(1+r*r);
	t = tanHalfAngle * tanHalfAngle;
	d = 1.0f / ( 1.0f + t );
	s = 2.0f * tanHalfAngle * d;
	c = ( 1.0f - t ) * d;
	start -= origin;
	proj = axis * ( start * axis );
	v1 = start - proj;
	v2 = axis.Cross( v1 );
	start = v1 * c - v2 * s + proj + origin;
	end -= origin;
	proj = axis * ( end * axis );
	v1 = end - proj;
	v2 = axis.Cross( v1 );
	end = v1 * c - v2 * s + proj + origin;
}

/*
================
glLabeledPoint
================
*/
void glLabeledPoint(idVec4 &color, idVec3 &point, float size, const char *label) {
	qglColor3fv( color.ToFloatPtr() );
	qglPointSize( size );
	qglBegin( GL_POINTS );
	qglVertex3fv( point.ToFloatPtr() );
	qglEnd();
	idVec3 v = point;
	v.x += 1;
	v.y += 1;
	v.z += 1;
	qglRasterPos3fv( v.ToFloatPtr() );
	qglCallLists( strlen(label), GL_UNSIGNED_BYTE, label );
}

void DrawLine( idVec3 v1, idVec3 v2, int color ) {
	if( !dmapGlobals.drawflag ) {
		return;
	}
	switch( color ) {
	case 0:
		GL_Color( 0.0f, 0.0f, 0.0f );
		break;
	case 1:
		GL_Color( 0.0f, 0.0f, 1.0f );
		break;
	case 2:
		GL_Color( 0.0f, 1.0f, 0.0f );
		break;
	case 3:
		GL_Color( 0.0f, 1.0f, 1.0f );
		break;
	case 4:
		GL_Color( 1.0f, 0.0f, 0.0f );
		break;
	case 5:
		GL_Color( 1.0f, 0.0f, 1.0f );
		break;
	case 6:
		GL_Color( 1.0f, 1.0f, 0.0f );
		break;
	case 7:
		GL_Color( 1.0f, 1.0f, 1.0f );
		break;
	}
	glBegin( GL_LINES );
	glVertex3fv( v1.ToFloatPtr() );
	glVertex3fv( v2.ToFloatPtr() );
	glEnd();
	glFlush();
}

/*
================
CM_RotatePoint

  rotates a point about an arbitrary axis using the tangent of half the rotation angle
================
*/
void CM_RotatePoint( idVec3 &point, const idVec3 &origin, const idVec3 &axis, const float tanHalfAngle ) {
	double d, t, s, c;
	idVec3 proj, v1, v2;
	point -= origin;
	proj = axis * ( point * axis );
	v1 = point - proj;
	v2 = axis.Cross( v1 );
	// r = tan( a / 2 );
	// sin(a) = 2*r/(1+r*r);
	// cos(a) = (1-r*r)/(1+r*r);
	t = tanHalfAngle * tanHalfAngle;
	d = 1.0f / ( 1.0f + t );
	s = 2.0f * tanHalfAngle * d;
	c = ( 1.0f - t ) * d;
	point = v1 * c - v2 * s + proj + origin;
}