/*
===========================================================================
Copyright (C) 1999-2005 Id Software, Inc.
Copyright (C) 2006 Robert Beckebans <trebor_7@users.sourceforge.net>

This file is part of XreaL source code.

XreaL source code is free software; you can redistribute it
and/or modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the License,
or (at your option) any later version.

XreaL source code is distributed in the hope that it will be
useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with XreaL source code; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
===========================================================================
*/

/*****************************************************************************
 * name:		be_aas_sample.c
 *
 * desc:		AAS environment sampling
 *
 * $Archive: /MissionPack/code/botlib/be_aas_sample.c $
 *
 *****************************************************************************/

#include "../common/shared.h"
#include "l_memory.h"
#include "l_script.h"
#include "l_precomp.h"
#include "l_struct.h"
#ifndef BSPC
#include "l_libvar.h"
#endif
#include "aasfile.h"
#include "../../mod/game/botlib.h"
#include "../../mod/game/be_aas.h"
#include "be_interface.h"
#include "be_aas_funcs.h"
#include "be_aas_def.h"

extern botlib_import_t botimport;

//#define AAS_SAMPLE_DEBUG

#define BBOX_NORMAL_EPSILON		0.001

#define ON_EPSILON					0	//0.0005

#define TRACEPLANE_EPSILON			0.125

typedef struct aas_tracestack_s
{
	vec3_t          start;		//start point of the piece of line to trace
	vec3_t          end;		//end point of the piece of line to trace
	int             planenum;	//last plane used as splitter
	int             nodenum;	//node found after splitting with planenum
} aas_tracestack_t;

int             numaaslinks;

//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_PresenceTypeBoundingBox(int presencetype, vec3_t mins, vec3_t maxs)
{
	int             index;

	//bounding box size for each presence type
	vec3_t          boxmins[3] = { {0, 0, 0}, {-15, -15, -24}, {-15, -15, -24} };
	vec3_t          boxmaxs[3] = { {0, 0, 0}, {15, 15, 32}, {15, 15, 8} };

	if(presencetype == PRESENCE_NORMAL)
		index = 1;
	else if(presencetype == PRESENCE_CROUCH)
		index = 2;
	else
	{
		botimport.Print(PRT_FATAL, "AAS_PresenceTypeBoundingBox: unknown presence type\n");
		index = 2;
	}							//end if
	VectorCopy(boxmins[index], mins);
	VectorCopy(boxmaxs[index], maxs);
}								//end of the function AAS_PresenceTypeBoundingBox

//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_InitAASLinkHeap(void)
{
	int             i, max_aaslinks;

	max_aaslinks = aasworld.linkheapsize;
	//if there's no link heap present
	if(!aasworld.linkheap)
	{
#ifdef BSPC
		max_aaslinks = 6144;
#else
		max_aaslinks = (int)LibVarValue("max_aaslinks", "6144");
#endif
		if(max_aaslinks < 0)
			max_aaslinks = 0;
		aasworld.linkheapsize = max_aaslinks;
		aasworld.linkheap = (aas_link_t *) GetHunkMemory(max_aaslinks * sizeof(aas_link_t));
	}							//end if
	//link the links on the heap
	aasworld.linkheap[0].prev_ent = NULL;
	aasworld.linkheap[0].next_ent = &aasworld.linkheap[1];
	for(i = 1; i < max_aaslinks - 1; i++)
	{
		aasworld.linkheap[i].prev_ent = &aasworld.linkheap[i - 1];
		aasworld.linkheap[i].next_ent = &aasworld.linkheap[i + 1];
	}							//end for
	aasworld.linkheap[max_aaslinks - 1].prev_ent = &aasworld.linkheap[max_aaslinks - 2];
	aasworld.linkheap[max_aaslinks - 1].next_ent = NULL;
	//pointer to the first free link
	aasworld.freelinks = &aasworld.linkheap[0];
	//
	numaaslinks = max_aaslinks;
}								//end of the function AAS_InitAASLinkHeap

//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_FreeAASLinkHeap(void)
{
	if(aasworld.linkheap)
		FreeMemory(aasworld.linkheap);
	aasworld.linkheap = NULL;
	aasworld.linkheapsize = 0;
}								//end of the function AAS_FreeAASLinkHeap

//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
aas_link_t     *AAS_AllocAASLink(void)
{
	aas_link_t     *link;

	link = aasworld.freelinks;
	if(!link)
	{
#ifndef BSPC
		if(bot_developer)
#endif
		{
			botimport.Print(PRT_FATAL, "empty aas link heap\n");
		}						//end if
		return NULL;
	}							//end if
	if(aasworld.freelinks)
		aasworld.freelinks = aasworld.freelinks->next_ent;
	if(aasworld.freelinks)
		aasworld.freelinks->prev_ent = NULL;
	numaaslinks--;
	return link;
}								//end of the function AAS_AllocAASLink

//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_DeAllocAASLink(aas_link_t * link)
{
	if(aasworld.freelinks)
		aasworld.freelinks->prev_ent = link;
	link->prev_ent = NULL;
	link->next_ent = aasworld.freelinks;
	link->prev_area = NULL;
	link->next_area = NULL;
	aasworld.freelinks = link;
	numaaslinks++;
}								//end of the function AAS_DeAllocAASLink

//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_InitAASLinkedEntities(void)
{
	if(!aasworld.loaded)
		return;
	if(aasworld.arealinkedentities)
		FreeMemory(aasworld.arealinkedentities);
	aasworld.arealinkedentities = (aas_link_t **) GetClearedHunkMemory(aasworld.numareas * sizeof(aas_link_t *));
}								//end of the function AAS_InitAASLinkedEntities

//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_FreeAASLinkedEntities(void)
{
	if(aasworld.arealinkedentities)
		FreeMemory(aasworld.arealinkedentities);
	aasworld.arealinkedentities = NULL;
}								//end of the function AAS_InitAASLinkedEntities

//===========================================================================
// returns the AAS area the point is in
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_PointAreaNum(vec3_t point)
{
	int             nodenum;
	vec_t           dist;
	aas_node_t     *node;
	aas_plane_t    *plane;

	if(!aasworld.loaded)
	{
		botimport.Print(PRT_ERROR, "AAS_PointAreaNum: aas not loaded\n");
		return 0;
	}							//end if

	//start with node 1 because node zero is a dummy used for solid leafs
	nodenum = 1;
	while(nodenum > 0)
	{
//      botimport.Print(PRT_MESSAGE, "[%d]", nodenum);
#ifdef AAS_SAMPLE_DEBUG
		if(nodenum >= aasworld.numnodes)
		{
			botimport.Print(PRT_ERROR, "nodenum = %d >= aasworld.numnodes = %d\n", nodenum, aasworld.numnodes);
			return 0;
		}						//end if
#endif							//AAS_SAMPLE_DEBUG
		node = &aasworld.nodes[nodenum];
#ifdef AAS_SAMPLE_DEBUG
		if(node->planenum < 0 || node->planenum >= aasworld.numplanes)
		{
			botimport.Print(PRT_ERROR, "node->planenum = %d >= aasworld.numplanes = %d\n", node->planenum, aasworld.numplanes);
			return 0;
		}						//end if
#endif							//AAS_SAMPLE_DEBUG
		plane = &aasworld.planes[node->planenum];
		dist = DotProduct(point, plane->normal) - plane->dist;
		if(dist > 0)
			nodenum = node->children[0];
		else
			nodenum = node->children[1];
	}							//end while
	if(!nodenum)
	{
#ifdef AAS_SAMPLE_DEBUG
		botimport.Print(PRT_MESSAGE, "in solid\n");
#endif							//AAS_SAMPLE_DEBUG
		return 0;
	}							//end if
	return -nodenum;
}								//end of the function AAS_PointAreaNum

//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int AAS_PointReachabilityAreaIndex(vec3_t origin)
{
	int             areanum, cluster, i, index;

	if(!aasworld.initialized)
		return 0;

	if(!origin)
	{
		index = 0;
		for(i = 0; i < aasworld.numclusters; i++)
		{
			index += aasworld.clusters[i].numreachabilityareas;
		}						//end for
		return index;
	}							//end if

	areanum = AAS_PointAreaNum(origin);
	if(!areanum || !AAS_AreaReachability(areanum))
		return 0;
	cluster = aasworld.areasettings[areanum].cluster;
	areanum = aasworld.areasettings[areanum].clusterareanum;
	if(cluster < 0)
	{
		cluster = aasworld.portals[-cluster].frontcluster;
		areanum = aasworld.portals[-cluster].clusterareanum[0];
	}							//end if

	index = 0;
	for(i = 0; i < cluster; i++)
	{
		index += aasworld.clusters[i].numreachabilityareas;
	}							//end for
	index += areanum;
	return index;
}								//end of the function AAS_PointReachabilityAreaIndex

//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_AreaCluster(int areanum)
{
	if(areanum <= 0 || areanum >= aasworld.numareas)
	{
		botimport.Print(PRT_ERROR, "AAS_AreaCluster: invalid area number\n");
		return 0;
	}							//end if
	return aasworld.areasettings[areanum].cluster;
}								//end of the function AAS_AreaCluster

//===========================================================================
// returns the presence types of the given area
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_AreaPresenceType(int areanum)
{
	if(!aasworld.loaded)
		return 0;
	if(areanum <= 0 || areanum >= aasworld.numareas)
	{
		botimport.Print(PRT_ERROR, "AAS_AreaPresenceType: invalid area number\n");
		return 0;
	}							//end if
	return aasworld.areasettings[areanum].presencetype;
}								//end of the function AAS_AreaPresenceType

//===========================================================================
// returns the presence type at the given point
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_PointPresenceType(vec3_t point)
{
	int             areanum;

	if(!aasworld.loaded)
		return 0;

	areanum = AAS_PointAreaNum(point);
	if(!areanum)
		return PRESENCE_NONE;
	return aasworld.areasettings[areanum].presencetype;
}								//end of the function AAS_PointPresenceType

//===========================================================================
// calculates the minimum distance between the origin of the box and the
// given plane when both will collide on the given side of the plane
//
// normal   =   normal vector of plane to calculate distance from
// mins     =   minimums of box relative to origin
// maxs     =   maximums of box relative to origin
// side     =   side of the plane we want to calculate the distance from
//                  0 normal vector side
//                  1 not normal vector side
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
vec_t AAS_BoxOriginDistanceFromPlane(vec3_t normal, vec3_t mins, vec3_t maxs, int side)
{
	vec3_t          v1, v2;
	int             i;

	//swap maxs and mins when on the other side of the plane
	if(side)
	{
		//get a point of the box that would be one of the first
		//to collide with the plane
		for(i = 0; i < 3; i++)
		{
			if(normal[i] > BBOX_NORMAL_EPSILON)
				v1[i] = maxs[i];
			else if(normal[i] < -BBOX_NORMAL_EPSILON)
				v1[i] = mins[i];
			else
				v1[i] = 0;
		}						//end for
	}							//end if
	else
	{
		//get a point of the box that would be one of the first
		//to collide with the plane
		for(i = 0; i < 3; i++)
		{
			if(normal[i] > BBOX_NORMAL_EPSILON)
				v1[i] = mins[i];
			else if(normal[i] < -BBOX_NORMAL_EPSILON)
				v1[i] = maxs[i];
			else
				v1[i] = 0;
		}						//end for
	}							//end else
	//
	VectorCopy(normal, v2);
	VectorInverse(v2);
//  VectorNegate(normal, v2);
	return DotProduct(v1, v2);
}								//end of the function AAS_BoxOriginDistanceFromPlane

//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
qboolean AAS_AreaEntityCollision(int areanum, vec3_t start, vec3_t end, int presencetype, int passent, aas_trace_t * trace)
{
	int             collision;
	vec3_t          boxmins, boxmaxs;
	aas_link_t     *link;
	bsp_trace_t     bsptrace;

	AAS_PresenceTypeBoundingBox(presencetype, boxmins, boxmaxs);

	Com_Memset(&bsptrace, 0, sizeof(bsp_trace_t));	//make compiler happy
	//assume no collision
	bsptrace.fraction = 1;
	collision = qfalse;
	for(link = aasworld.arealinkedentities[areanum]; link; link = link->next_ent)
	{
		//ignore the pass entity
		if(link->entnum == passent)
			continue;
		//
		if(AAS_EntityCollision(link->entnum, start, boxmins, boxmaxs, end, CONTENTS_SOLID | CONTENTS_PLAYERCLIP, &bsptrace))
		{
			collision = qtrue;
		}						//end if
	}							//end for
	if(collision)
	{
		trace->startsolid = bsptrace.startsolid;
		trace->ent = bsptrace.ent;
		VectorCopy(bsptrace.endpos, trace->endpos);
		trace->area = 0;
		trace->planenum = 0;
		return qtrue;
	}							//end if
	return qfalse;
}								//end of the function AAS_AreaEntityCollision

//===========================================================================
// recursive subdivision of the line by the BSP tree.
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
aas_trace_t AAS_TraceClientBBox(vec3_t start, vec3_t end, int presencetype, int passent)
{
	int             side, nodenum, tmpplanenum;
	float           front, back, frac;
	vec3_t          cur_start, cur_end, cur_mid, v1, v2;
	aas_tracestack_t tracestack[127];
	aas_tracestack_t *tstack_p;
	aas_node_t     *aasnode;
	aas_plane_t    *plane;
	aas_trace_t     trace;

	//clear the trace structure
	Com_Memset(&trace, 0, sizeof(aas_trace_t));

	if(!aasworld.loaded)
		return trace;

	tstack_p = tracestack;
	//we start with the whole line on the stack
	VectorCopy(start, tstack_p->start);
	VectorCopy(end, tstack_p->end);
	tstack_p->planenum = 0;
	//start with node 1 because node zero is a dummy for a solid leaf
	tstack_p->nodenum = 1;		//starting at the root of the tree
	tstack_p++;

	while(1)
	{
		//pop up the stack
		tstack_p--;
		//if the trace stack is empty (ended up with a piece of the
		//line to be traced in an area)
		if(tstack_p < tracestack)
		{
			tstack_p++;
			//nothing was hit
			trace.startsolid = qfalse;
			trace.fraction = 1.0;
			//endpos is the end of the line
			VectorCopy(end, trace.endpos);
			//nothing hit
			trace.ent = 0;
			trace.area = 0;
			trace.planenum = 0;
			return trace;
		}						//end if
		//number of the current node to test the line against
		nodenum = tstack_p->nodenum;
		//if it is an area
		if(nodenum < 0)
		{
#ifdef AAS_SAMPLE_DEBUG
			if(-nodenum > aasworld.numareasettings)
			{
				botimport.Print(PRT_ERROR, "AAS_TraceBoundingBox: -nodenum out of range\n");
				return trace;
			}					//end if
#endif							//AAS_SAMPLE_DEBUG
			//botimport.Print(PRT_MESSAGE, "areanum = %d, must be %d\n", -nodenum, AAS_PointAreaNum(start));
			//if can't enter the area because it hasn't got the right presence type
			if(!(aasworld.areasettings[-nodenum].presencetype & presencetype))
			{
				//if the start point is still the initial start point
				//NOTE: no need for epsilons because the points will be
				//exactly the same when they're both the start point
				if(tstack_p->start[0] == start[0] && tstack_p->start[1] == start[1] && tstack_p->start[2] == start[2])
				{
					trace.startsolid = qtrue;
					trace.fraction = 0.0;
					VectorClear(v1);
				}				//end if
				else
				{
					trace.startsolid = qfalse;
					VectorSubtract(end, start, v1);
					VectorSubtract(tstack_p->start, start, v2);
					trace.fraction = VectorLength(v2) / VectorNormalize(v1);
					VectorMA(tstack_p->start, -0.125, v1, tstack_p->start);
				}				//end else
				VectorCopy(tstack_p->start, trace.endpos);
				trace.ent = 0;
				trace.area = -nodenum;
//              VectorSubtract(end, start, v1);
				trace.planenum = tstack_p->planenum;
				//always take the plane with normal facing towards the trace start
				plane = &aasworld.planes[trace.planenum];
				if(DotProduct(v1, plane->normal) > 0)
					trace.planenum ^= 1;
				return trace;
			}					//end if
			else
			{
				if(passent >= 0)
				{
					if(AAS_AreaEntityCollision(-nodenum, tstack_p->start, tstack_p->end, presencetype, passent, &trace))
					{
						if(!trace.startsolid)
						{
							VectorSubtract(end, start, v1);
							VectorSubtract(trace.endpos, start, v2);
							trace.fraction = VectorLength(v2) / VectorLength(v1);
						}		//end if
						return trace;
					}			//end if
				}				//end if
			}					//end else
			trace.lastarea = -nodenum;
			continue;
		}						//end if
		//if it is a solid leaf
		if(!nodenum)
		{
			//if the start point is still the initial start point
			//NOTE: no need for epsilons because the points will be
			//exactly the same when they're both the start point
			if(tstack_p->start[0] == start[0] && tstack_p->start[1] == start[1] && tstack_p->start[2] == start[2])
			{
				trace.startsolid = qtrue;
				trace.fraction = 0.0;
				VectorClear(v1);
			}					//end if
			else
			{
				trace.startsolid = qfalse;
				VectorSubtract(end, start, v1);
				VectorSubtract(tstack_p->start, start, v2);
				trace.fraction = VectorLength(v2) / VectorNormalize(v1);
				VectorMA(tstack_p->start, -0.125, v1, tstack_p->start);
			}					//end else
			VectorCopy(tstack_p->start, trace.endpos);
			trace.ent = 0;
			trace.area = 0;		//hit solid leaf
//          VectorSubtract(end, start, v1);
			trace.planenum = tstack_p->planenum;
			//always take the plane with normal facing towards the trace start
			plane = &aasworld.planes[trace.planenum];
			if(DotProduct(v1, plane->normal) > 0)
				trace.planenum ^= 1;
			return trace;
		}						//end if
#ifdef AAS_SAMPLE_DEBUG
		if(nodenum > aasworld.numnodes)
		{
			botimport.Print(PRT_ERROR, "AAS_TraceBoundingBox: nodenum out of range\n");
			return trace;
		}						//end if
#endif							//AAS_SAMPLE_DEBUG
		//the node to test against
		aasnode = &aasworld.nodes[nodenum];
		//start point of current line to test against node
		VectorCopy(tstack_p->start, cur_start);
		//end point of the current line to test against node
		VectorCopy(tstack_p->end, cur_end);
		//the current node plane
		plane = &aasworld.planes[aasnode->planenum];

		switch (plane->type)
		{						/*FIXME: wtf doesn't this work? obviously the axial node planes aren't always facing positive!!!
								   //check for axial planes
								   case PLANE_X:
								   {
								   front = cur_start[0] - plane->dist;
								   back = cur_end[0] - plane->dist;
								   break;
								   } //end case
								   case PLANE_Y:
								   {
								   front = cur_start[1] - plane->dist;
								   back = cur_end[1] - plane->dist;
								   break;
								   } //end case
								   case PLANE_Z:
								   {
								   front = cur_start[2] - plane->dist;
								   back = cur_end[2] - plane->dist;
								   break;
								   } //end case */
			default:			//gee it's not an axial plane
			{
				front = DotProduct(cur_start, plane->normal) - plane->dist;
				back = DotProduct(cur_end, plane->normal) - plane->dist;
				break;
			}					//end default
		}						//end switch
		// bk010221 - old location of FPE hack and divide by zero expression
		//if the whole to be traced line is totally at the front of this node
		//only go down the tree with the front child
		if((front >= -ON_EPSILON && back >= -ON_EPSILON))
		{
			//keep the current start and end point on the stack
			//and go down the tree with the front child
			tstack_p->nodenum = aasnode->children[0];
			tstack_p++;
			if(tstack_p >= &tracestack[127])
			{
				botimport.Print(PRT_ERROR, "AAS_TraceBoundingBox: stack overflow\n");
				return trace;
			}					//end if
		}						//end if
		//if the whole to be traced line is totally at the back of this node
		//only go down the tree with the back child
		else if((front < ON_EPSILON && back < ON_EPSILON))
		{
			//keep the current start and end point on the stack
			//and go down the tree with the back child
			tstack_p->nodenum = aasnode->children[1];
			tstack_p++;
			if(tstack_p >= &tracestack[127])
			{
				botimport.Print(PRT_ERROR, "AAS_TraceBoundingBox: stack overflow\n");
				return trace;
			}					//end if
		}						//end if
		//go down the tree both at the front and back of the node
		else
		{
			tmpplanenum = tstack_p->planenum;
			// bk010221 - new location of divide by zero (see above)
			if(front == back)
				front -= 0.001f;	// bk0101022 - hack/FPE 
			//calculate the hitpoint with the node (split point of the line)
			//put the crosspoint TRACEPLANE_EPSILON pixels on the near side
			if(front < 0)
				frac = (front + TRACEPLANE_EPSILON) / (front - back);
			else
				frac = (front - TRACEPLANE_EPSILON) / (front - back);	// bk010221
			//
			if(frac < 0)
				frac = 0.001f;	//0
			else if(frac > 1)
				frac = 0.999f;	//1
			//frac = front / (front-back);
			//
			cur_mid[0] = cur_start[0] + (cur_end[0] - cur_start[0]) * frac;
			cur_mid[1] = cur_start[1] + (cur_end[1] - cur_start[1]) * frac;
			cur_mid[2] = cur_start[2] + (cur_end[2] - cur_start[2]) * frac;

//          AAS_DrawPlaneCross(cur_mid, plane->normal, plane->dist, plane->type, LINECOLOR_RED);
			//side the front part of the line is on
			side = front < 0;
			//first put the end part of the line on the stack (back side)
			VectorCopy(cur_mid, tstack_p->start);
			//not necesary to store because still on stack
			//VectorCopy(cur_end, tstack_p->end);
			tstack_p->planenum = aasnode->planenum;
			tstack_p->nodenum = aasnode->children[!side];
			tstack_p++;
			if(tstack_p >= &tracestack[127])
			{
				botimport.Print(PRT_ERROR, "AAS_TraceBoundingBox: stack overflow\n");
				return trace;
			}					//end if
			//now put the part near the start of the line on the stack so we will
			//continue with thats part first. This way we'll find the first
			//hit of the bbox
			VectorCopy(cur_start, tstack_p->start);
			VectorCopy(cur_mid, tstack_p->end);
			tstack_p->planenum = tmpplanenum;
			tstack_p->nodenum = aasnode->children[side];
			tstack_p++;
			if(tstack_p >= &tracestack[127])
			{
				botimport.Print(PRT_ERROR, "AAS_TraceBoundingBox: stack overflow\n");
				return trace;
			}					//end if
		}						//end else
	}							//end while
//  return trace;
}								//end of the function AAS_TraceClientBBox

//===========================================================================
// recursive subdivision of the line by the BSP tree.
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_TraceAreas(vec3_t start, vec3_t end, int *areas, vec3_t * points, int maxareas)
{
	int             side, nodenum, tmpplanenum;
	int             numareas;
	float           front, back, frac;
	vec3_t          cur_start, cur_end, cur_mid;
	aas_tracestack_t tracestack[127];
	aas_tracestack_t *tstack_p;
	aas_node_t     *aasnode;
	aas_plane_t    *plane;

	numareas = 0;
	areas[0] = 0;
	if(!aasworld.loaded)
		return numareas;

	tstack_p = tracestack;
	//we start with the whole line on the stack
	VectorCopy(start, tstack_p->start);
	VectorCopy(end, tstack_p->end);
	tstack_p->planenum = 0;
	//start with node 1 because node zero is a dummy for a solid leaf
	tstack_p->nodenum = 1;		//starting at the root of the tree
	tstack_p++;

	while(1)
	{
		//pop up the stack
		tstack_p--;
		//if the trace stack is empty (ended up with a piece of the
		//line to be traced in an area)
		if(tstack_p < tracestack)
		{
			return numareas;
		}						//end if
		//number of the current node to test the line against
		nodenum = tstack_p->nodenum;
		//if it is an area
		if(nodenum < 0)
		{
#ifdef AAS_SAMPLE_DEBUG
			if(-nodenum > aasworld.numareasettings)
			{
				botimport.Print(PRT_ERROR, "AAS_TraceAreas: -nodenum = %d out of range\n", -nodenum);
				return numareas;
			}					//end if
#endif							//AAS_SAMPLE_DEBUG
			//botimport.Print(PRT_MESSAGE, "areanum = %d, must be %d\n", -nodenum, AAS_PointAreaNum(start));
			areas[numareas] = -nodenum;
			if(points)
				VectorCopy(tstack_p->start, points[numareas]);
			numareas++;
			if(numareas >= maxareas)
				return numareas;
			continue;
		}						//end if
		//if it is a solid leaf
		if(!nodenum)
		{
			continue;
		}						//end if
#ifdef AAS_SAMPLE_DEBUG
		if(nodenum > aasworld.numnodes)
		{
			botimport.Print(PRT_ERROR, "AAS_TraceAreas: nodenum out of range\n");
			return numareas;
		}						//end if
#endif							//AAS_SAMPLE_DEBUG
		//the node to test against
		aasnode = &aasworld.nodes[nodenum];
		//start point of current line to test against node
		VectorCopy(tstack_p->start, cur_start);
		//end point of the current line to test against node
		VectorCopy(tstack_p->end, cur_end);
		//the current node plane
		plane = &aasworld.planes[aasnode->planenum];

		switch (plane->type)
		{						/*FIXME: wtf doesn't this work? obviously the node planes aren't always facing positive!!!
								   //check for axial planes
								   case PLANE_X:
								   {
								   front = cur_start[0] - plane->dist;
								   back = cur_end[0] - plane->dist;
								   break;
								   } //end case
								   case PLANE_Y:
								   {
								   front = cur_start[1] - plane->dist;
								   back = cur_end[1] - plane->dist;
								   break;
								   } //end case
								   case PLANE_Z:
								   {
								   front = cur_start[2] - plane->dist;
								   back = cur_end[2] - plane->dist;
								   break;
								   } //end case */
			default:			//gee it's not an axial plane
			{
				front = DotProduct(cur_start, plane->normal) - plane->dist;
				back = DotProduct(cur_end, plane->normal) - plane->dist;
				break;
			}					//end default
		}						//end switch

		//if the whole to be traced line is totally at the front of this node
		//only go down the tree with the front child
		if(front > 0 && back > 0)
		{
			//keep the current start and end point on the stack
			//and go down the tree with the front child
			tstack_p->nodenum = aasnode->children[0];
			tstack_p++;
			if(tstack_p >= &tracestack[127])
			{
				botimport.Print(PRT_ERROR, "AAS_TraceAreas: stack overflow\n");
				return numareas;
			}					//end if
		}						//end if
		//if the whole to be traced line is totally at the back of this node
		//only go down the tree with the back child
		else if(front <= 0 && back <= 0)
		{
			//keep the current start and end point on the stack
			//and go down the tree with the back child
			tstack_p->nodenum = aasnode->children[1];
			tstack_p++;
			if(tstack_p >= &tracestack[127])
			{
				botimport.Print(PRT_ERROR, "AAS_TraceAreas: stack overflow\n");
				return numareas;
			}					//end if
		}						//end if
		//go down the tree both at the front and back of the node
		else
		{
			tmpplanenum = tstack_p->planenum;
			//calculate the hitpoint with the node (split point of the line)
			//put the crosspoint TRACEPLANE_EPSILON pixels on the near side
			if(front < 0)
				frac = (front) / (front - back);
			else
				frac = (front) / (front - back);
			if(frac < 0)
				frac = 0;
			else if(frac > 1)
				frac = 1;
			//frac = front / (front-back);
			//
			cur_mid[0] = cur_start[0] + (cur_end[0] - cur_start[0]) * frac;
			cur_mid[1] = cur_start[1] + (cur_end[1] - cur_start[1]) * frac;
			cur_mid[2] = cur_start[2] + (cur_end[2] - cur_start[2]) * frac;

//          AAS_DrawPlaneCross(cur_mid, plane->normal, plane->dist, plane->type, LINECOLOR_RED);
			//side the front part of the line is on
			side = front < 0;
			//first put the end part of the line on the stack (back side)
			VectorCopy(cur_mid, tstack_p->start);
			//not necesary to store because still on stack
			//VectorCopy(cur_end, tstack_p->end);
			tstack_p->planenum = aasnode->planenum;
			tstack_p->nodenum = aasnode->children[!side];
			tstack_p++;
			if(tstack_p >= &tracestack[127])
			{
				botimport.Print(PRT_ERROR, "AAS_TraceAreas: stack overflow\n");
				return numareas;
			}					//end if
			//now put the part near the start of the line on the stack so we will
			//continue with thats part first. This way we'll find the first
			//hit of the bbox
			VectorCopy(cur_start, tstack_p->start);
			VectorCopy(cur_mid, tstack_p->end);
			tstack_p->planenum = tmpplanenum;
			tstack_p->nodenum = aasnode->children[side];
			tstack_p++;
			if(tstack_p >= &tracestack[127])
			{
				botimport.Print(PRT_ERROR, "AAS_TraceAreas: stack overflow\n");
				return numareas;
			}					//end if
		}						//end else
	}							//end while
//  return numareas;
}								//end of the function AAS_TraceAreas

//===========================================================================
// a simple cross product
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
// void AAS_OrthogonalToVectors(vec3_t v1, vec3_t v2, vec3_t res)
#define AAS_OrthogonalToVectors(v1, v2, res) \
	(res)[0] = ((v1)[1] * (v2)[2]) - ((v1)[2] * (v2)[1]);\
	(res)[1] = ((v1)[2] * (v2)[0]) - ((v1)[0] * (v2)[2]);\
	(res)[2] = ((v1)[0] * (v2)[1]) - ((v1)[1] * (v2)[0]);
//===========================================================================
// tests if the given point is within the face boundaries
//
// Parameter:               face        : face to test if the point is in it
//                              pnormal : normal of the plane to use for the face
//                              point       : point to test if inside face boundaries
// Returns:                 qtrue if the point is within the face boundaries
// Changes Globals:     -
//===========================================================================
qboolean AAS_InsideFace(aas_face_t * face, vec3_t pnormal, vec3_t point, float epsilon)
{
	int             i, firstvertex, edgenum;
	vec3_t          v0;
	vec3_t          edgevec, pointvec, sepnormal;
	aas_edge_t     *edge;

#ifdef AAS_SAMPLE_DEBUG
	int             lastvertex = 0;
#endif							//AAS_SAMPLE_DEBUG

	if(!aasworld.loaded)
		return qfalse;

	for(i = 0; i < face->numedges; i++)
	{
		edgenum = aasworld.edgeindex[face->firstedge + i];
		edge = &aasworld.edges[abs(edgenum)];
		//get the first vertex of the edge
		firstvertex = edgenum < 0;
		VectorCopy(aasworld.vertexes[edge->v[firstvertex]], v0);
		//edge vector
		VectorSubtract(aasworld.vertexes[edge->v[!firstvertex]], v0, edgevec);
		//
#ifdef AAS_SAMPLE_DEBUG
		if(lastvertex && lastvertex != edge->v[firstvertex])
		{
			botimport.Print(PRT_MESSAGE, "winding not counter clockwise\n");
		}						//end if
		lastvertex = edge->v[!firstvertex];
#endif							//AAS_SAMPLE_DEBUG
		//vector from first edge point to point possible in face
		VectorSubtract(point, v0, pointvec);
		//get a vector pointing inside the face orthogonal to both the
		//edge vector and the normal vector of the plane the face is in
		//this vector defines a plane through the origin (first vertex of
		//edge) and through both the edge vector and the normal vector
		//of the plane
		AAS_OrthogonalToVectors(edgevec, pnormal, sepnormal);
		//check on wich side of the above plane the point is
		//this is done by checking the sign of the dot product of the
		//vector orthogonal vector from above and the vector from the
		//origin (first vertex of edge) to the point 
		//if the dotproduct is smaller than zero the point is outside the face
		if(DotProduct(pointvec, sepnormal) < -epsilon)
			return qfalse;
	}							//end for
	return qtrue;
}								//end of the function AAS_InsideFace

//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
qboolean AAS_PointInsideFace(int facenum, vec3_t point, float epsilon)
{
	int             i, firstvertex, edgenum;
	vec_t          *v1, *v2;
	vec3_t          edgevec, pointvec, sepnormal;
	aas_edge_t     *edge;
	aas_plane_t    *plane;
	aas_face_t     *face;

	if(!aasworld.loaded)
		return qfalse;

	face = &aasworld.faces[facenum];
	plane = &aasworld.planes[face->planenum];
	//
	for(i = 0; i < face->numedges; i++)
	{
		edgenum = aasworld.edgeindex[face->firstedge + i];
		edge = &aasworld.edges[abs(edgenum)];
		//get the first vertex of the edge
		firstvertex = edgenum < 0;
		v1 = aasworld.vertexes[edge->v[firstvertex]];
		v2 = aasworld.vertexes[edge->v[!firstvertex]];
		//edge vector
		VectorSubtract(v2, v1, edgevec);
		//vector from first edge point to point possible in face
		VectorSubtract(point, v1, pointvec);
		//
		CrossProduct(edgevec, plane->normal, sepnormal);
		//
		if(DotProduct(pointvec, sepnormal) < -epsilon)
			return qfalse;
	}							//end for
	return qtrue;
}								//end of the function AAS_PointInsideFace

//===========================================================================
// returns the ground face the given point is above in the given area
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
aas_face_t     *AAS_AreaGroundFace(int areanum, vec3_t point)
{
	int             i, facenum;
	vec3_t          up = { 0, 0, 1 };
	vec3_t          normal;
	aas_area_t     *area;
	aas_face_t     *face;

	if(!aasworld.loaded)
		return NULL;

	area = &aasworld.areas[areanum];
	for(i = 0; i < area->numfaces; i++)
	{
		facenum = aasworld.faceindex[area->firstface + i];
		face = &aasworld.faces[abs(facenum)];
		//if this is a ground face
		if(face->faceflags & FACE_GROUND)
		{
			//get the up or down normal
			if(aasworld.planes[face->planenum].normal[2] < 0)
				VectorNegate(up, normal);
			else
				VectorCopy(up, normal);
			//check if the point is in the face
			if(AAS_InsideFace(face, normal, point, 0.01f))
				return face;
		}						//end if
	}							//end for
	return NULL;
}								//end of the function AAS_AreaGroundFace

//===========================================================================
// returns the face the trace end position is situated in
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_FacePlane(int facenum, vec3_t normal, float *dist)
{
	aas_plane_t    *plane;

	plane = &aasworld.planes[aasworld.faces[facenum].planenum];
	VectorCopy(plane->normal, normal);
	*dist = plane->dist;
}								//end of the function AAS_FacePlane

//===========================================================================
// returns the face the trace end position is situated in
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
aas_face_t     *AAS_TraceEndFace(aas_trace_t * trace)
{
	int             i, facenum;
	aas_area_t     *area;
	aas_face_t     *face, *firstface = NULL;

	if(!aasworld.loaded)
		return NULL;

	//if started in solid no face was hit
	if(trace->startsolid)
		return NULL;
	//trace->lastarea is the last area the trace was in
	area = &aasworld.areas[trace->lastarea];
	//check which face the trace.endpos was in
	for(i = 0; i < area->numfaces; i++)
	{
		facenum = aasworld.faceindex[area->firstface + i];
		face = &aasworld.faces[abs(facenum)];
		//if the face is in the same plane as the trace end point
		if((face->planenum & ~1) == (trace->planenum & ~1))
		{
			//firstface is used for optimization, if theres only one
			//face in the plane then it has to be the good one
			//if there are more faces in the same plane then always
			//check the one with the fewest edges first
/*			if (firstface)
			{
				if (firstface->numedges < face->numedges)
				{
					if (AAS_InsideFace(firstface,
						aasworld.planes[face->planenum].normal, trace->endpos))
					{
						return firstface;
					} //end if
					firstface = face;
				} //end if
				else
				{
					if (AAS_InsideFace(face,
						aasworld.planes[face->planenum].normal, trace->endpos))
					{
						return face;
					} //end if
				} //end else
			} //end if
			else
			{
				firstface = face;
			} //end else*/
			if(AAS_InsideFace(face, aasworld.planes[face->planenum].normal, trace->endpos, 0.01f))
				return face;
		}						//end if
	}							//end for
	return firstface;
}								//end of the function AAS_TraceEndFace

//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_BoxOnPlaneSide2(vec3_t absmins, vec3_t absmaxs, aas_plane_t * p)
{
	int             i, sides;
	float           dist1, dist2;
	vec3_t          corners[2];

	for(i = 0; i < 3; i++)
	{
		if(p->normal[i] < 0)
		{
			corners[0][i] = absmins[i];
			corners[1][i] = absmaxs[i];
		}						//end if
		else
		{
			corners[1][i] = absmins[i];
			corners[0][i] = absmaxs[i];
		}						//end else
	}							//end for
	dist1 = DotProduct(p->normal, corners[0]) - p->dist;
	dist2 = DotProduct(p->normal, corners[1]) - p->dist;
	sides = 0;
	if(dist1 >= 0)
		sides = 1;
	if(dist2 < 0)
		sides |= 2;

	return sides;
}								//end of the function AAS_BoxOnPlaneSide2

//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
//int AAS_BoxOnPlaneSide(vec3_t absmins, vec3_t absmaxs, aas_plane_t *p)
#define AAS_BoxOnPlaneSide(absmins, absmaxs, p) (\
	( (p)->type < 3) ?\
	(\
		( (p)->dist <= (absmins)[(p)->type]) ?\
		(\
			1\
		)\
		:\
		(\
			( (p)->dist >= (absmaxs)[(p)->type]) ?\
			(\
				2\
			)\
			:\
			(\
				3\
			)\
		)\
	)\
	:\
	(\
		AAS_BoxOnPlaneSide2((absmins), (absmaxs), (p))\
	)\
)								//end of the function AAS_BoxOnPlaneSide
//===========================================================================
// remove the links to this entity from all areas
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_UnlinkFromAreas(aas_link_t * areas)
{
	aas_link_t     *link, *nextlink;

	for(link = areas; link; link = nextlink)
	{
		//next area the entity is linked in
		nextlink = link->next_area;
		//remove the entity from the linked list of this area
		if(link->prev_ent)
			link->prev_ent->next_ent = link->next_ent;
		else
			aasworld.arealinkedentities[link->areanum] = link->next_ent;
		if(link->next_ent)
			link->next_ent->prev_ent = link->prev_ent;
		//deallocate the link structure
		AAS_DeAllocAASLink(link);
	}							//end for
}								//end of the function AAS_UnlinkFromAreas

//===========================================================================
// link the entity to the areas the bounding box is totally or partly
// situated in. This is done with recursion down the tree using the
// bounding box to test for plane sides
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================

typedef struct
{
	int             nodenum;	//node found after splitting
} aas_linkstack_t;

aas_link_t     *AAS_AASLinkEntity(vec3_t absmins, vec3_t absmaxs, int entnum)
{
	int             side, nodenum;
	aas_linkstack_t linkstack[128];
	aas_linkstack_t *lstack_p;
	aas_node_t     *aasnode;
	aas_plane_t    *plane;
	aas_link_t     *link, *areas;

	if(!aasworld.loaded)
	{
		botimport.Print(PRT_ERROR, "AAS_LinkEntity: aas not loaded\n");
		return NULL;
	}							//end if

	areas = NULL;
	//
	lstack_p = linkstack;
	//we start with the whole line on the stack
	//start with node 1 because node zero is a dummy used for solid leafs
	lstack_p->nodenum = 1;		//starting at the root of the tree
	lstack_p++;

	while(1)
	{
		//pop up the stack
		lstack_p--;
		//if the trace stack is empty (ended up with a piece of the
		//line to be traced in an area)
		if(lstack_p < linkstack)
			break;
		//number of the current node to test the line against
		nodenum = lstack_p->nodenum;
		//if it is an area
		if(nodenum < 0)
		{
			//NOTE: the entity might have already been linked into this area
			// because several node children can point to the same area
			for(link = aasworld.arealinkedentities[-nodenum]; link; link = link->next_ent)
			{
				if(link->entnum == entnum)
					break;
			}					//end for
			if(link)
				continue;
			//
			link = AAS_AllocAASLink();
			if(!link)
				return areas;
			link->entnum = entnum;
			link->areanum = -nodenum;
			//put the link into the double linked area list of the entity
			link->prev_area = NULL;
			link->next_area = areas;
			if(areas)
				areas->prev_area = link;
			areas = link;
			//put the link into the double linked entity list of the area
			link->prev_ent = NULL;
			link->next_ent = aasworld.arealinkedentities[-nodenum];
			if(aasworld.arealinkedentities[-nodenum])
				aasworld.arealinkedentities[-nodenum]->prev_ent = link;
			aasworld.arealinkedentities[-nodenum] = link;
			//
			continue;
		}						//end if
		//if solid leaf
		if(!nodenum)
			continue;
		//the node to test against
		aasnode = &aasworld.nodes[nodenum];
		//the current node plane
		plane = &aasworld.planes[aasnode->planenum];
		//get the side(s) the box is situated relative to the plane
		side = AAS_BoxOnPlaneSide2(absmins, absmaxs, plane);
		//if on the front side of the node
		if(side & 1)
		{
			lstack_p->nodenum = aasnode->children[0];
			lstack_p++;
		}						//end if
		if(lstack_p >= &linkstack[127])
		{
			botimport.Print(PRT_ERROR, "AAS_LinkEntity: stack overflow\n");
			break;
		}						//end if
		//if on the back side of the node
		if(side & 2)
		{
			lstack_p->nodenum = aasnode->children[1];
			lstack_p++;
		}						//end if
		if(lstack_p >= &linkstack[127])
		{
			botimport.Print(PRT_ERROR, "AAS_LinkEntity: stack overflow\n");
			break;
		}						//end if
	}							//end while
	return areas;
}								//end of the function AAS_AASLinkEntity

//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
aas_link_t     *AAS_LinkEntityClientBBox(vec3_t absmins, vec3_t absmaxs, int entnum, int presencetype)
{
	vec3_t          mins, maxs;
	vec3_t          newabsmins, newabsmaxs;

	AAS_PresenceTypeBoundingBox(presencetype, mins, maxs);
	VectorSubtract(absmins, maxs, newabsmins);
	VectorSubtract(absmaxs, mins, newabsmaxs);
	//relink the entity
	return AAS_AASLinkEntity(newabsmins, newabsmaxs, entnum);
}								//end of the function AAS_LinkEntityClientBBox

//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_BBoxAreas(vec3_t absmins, vec3_t absmaxs, int *areas, int maxareas)
{
	aas_link_t     *linkedareas, *link;
	int             num;

	linkedareas = AAS_AASLinkEntity(absmins, absmaxs, -1);
	num = 0;
	for(link = linkedareas; link; link = link->next_area)
	{
		areas[num] = link->areanum;
		num++;
		if(num >= maxareas)
			break;
	}							//end for
	AAS_UnlinkFromAreas(linkedareas);
	return num;
}								//end of the function AAS_BBoxAreas

//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_AreaInfo(int areanum, aas_areainfo_t * info)
{
	aas_areasettings_t *settings;

	if(!info)
		return 0;
	if(areanum <= 0 || areanum >= aasworld.numareas)
	{
		botimport.Print(PRT_ERROR, "AAS_AreaInfo: areanum %d out of range\n", areanum);
		return 0;
	}							//end if
	settings = &aasworld.areasettings[areanum];
	info->cluster = settings->cluster;
	info->contents = settings->contents;
	info->flags = settings->areaflags;
	info->presencetype = settings->presencetype;
	VectorCopy(aasworld.areas[areanum].mins, info->mins);
	VectorCopy(aasworld.areas[areanum].maxs, info->maxs);
	VectorCopy(aasworld.areas[areanum].center, info->center);
	return sizeof(aas_areainfo_t);
}								//end of the function AAS_AreaInfo

//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
aas_plane_t    *AAS_PlaneFromNum(int planenum)
{
	if(!aasworld.loaded)
		return 0;

	return &aasworld.planes[planenum];
}								//end of the function AAS_PlaneFromNum
