/*
* Copyright(c) 1997-2001 Id Software, Inc.
* Copyright(c) 2002 The Quakeforge Project.
* Copyright(c) 2006 Quetoo.
*
* This program 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.
* 
* This program 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 this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
*/

/*
* world query functions
*/ 

#include "server.h"

/*
 
ENTITY AREA CHECKING
 
FIXME: this use of "area" is different from the bsp file use
*/

//(type *)STRUCT_FROM_LINK(link_t *link, type, member)
// ent = STRUCT_FROM_LINK(link,entity_t,order)
// FIXME: remove this mess!
#include <inttypes.h>
#define STRUCT_FROM_LINK(l,t,m)((t *)((byte *)l -(intptr_t)&(((t *)0)->m)))

#define EDICT_FROM_AREA(l) STRUCT_FROM_LINK(l,edict_t,area)

typedef struct areanode_s {
	int axis;  // -1 = leaf node
	float dist;
	struct areanode_s	*children[2];
	link_t trigger_edicts;
	link_t solid_edicts;
} areanode_t;

#define AREA_DEPTH	4
#define AREA_NODES	32

areanode_t sv_areanodes[AREA_NODES];
int sv_numareanodes;

float *area_mins, *area_maxs;
edict_t **area_list;
int area_count, area_maxcount;
int area_type;

int SV_HullForEntity(edict_t *ent);


// ClearLink is used for new headnodes
void ClearLink(link_t *l){
	l->prev = l->next = l;
}

void RemoveLink(link_t *l){
	l->next->prev = l->prev;
	l->prev->next = l->next;
}

void InsertLinkBefore(link_t *l, link_t *before){
	l->next = before;
	l->prev = before->prev;
	l->prev->next = l;
	l->next->prev = l;
}

/*
SV_CreateAreaNode
 
Builds a uniformly subdivided tree for the given world size
*/
areanode_t *SV_CreateAreaNode(int depth, vec3_t mins, vec3_t maxs){
	areanode_t *anode;
	vec3_t size;
	vec3_t mins1, maxs1, mins2, maxs2;
	
	anode = &sv_areanodes[sv_numareanodes];
	sv_numareanodes++;
	
	ClearLink(&anode->trigger_edicts);
	ClearLink(&anode->solid_edicts);
	
	if(depth == AREA_DEPTH){
		anode->axis = -1;
		anode->children[0] = anode->children[1] = NULL;
		return anode;
	}
	
	VectorSubtract(maxs, mins, size);
	if(size[0] > size[1])
		anode->axis = 0;
	else
		anode->axis = 1;
		
	anode->dist = 0.5 *(maxs[anode->axis] + mins[anode->axis]);
	VectorCopy(mins, mins1);
	VectorCopy(mins, mins2);
	VectorCopy(maxs, maxs1);
	VectorCopy(maxs, maxs2);
	
	maxs1[anode->axis] = mins2[anode->axis] = anode->dist;
	
	anode->children[0] = SV_CreateAreaNode(depth + 1, mins2, maxs2);
	anode->children[1] = SV_CreateAreaNode(depth + 1, mins1, maxs1);
	
	return anode;
}

/*
SV_ClearWorld
 
*/
void SV_ClearWorld(void){
	memset(sv_areanodes, 0, sizeof(sv_areanodes));
	sv_numareanodes = 0;
	SV_CreateAreaNode(0, sv.models[1]->mins, sv.models[1]->maxs);
}


/*
SV_UnlinkEdict
 
*/
void SV_UnlinkEdict(edict_t *ent){
	if(!ent->area.prev)
		return;  // not linked in anywhere
	RemoveLink(&ent->area);
	ent->area.prev = ent->area.next = NULL;
}


/*
SV_LinkEdict
 
*/
#define MAX_TOTAL_ENT_LEAFS		128
void SV_LinkEdict(edict_t *ent){
	areanode_t *node;
	int leafs[MAX_TOTAL_ENT_LEAFS];
	int clusters[MAX_TOTAL_ENT_LEAFS];
	int num_leafs;
	int i, j, k;
	int area;
	int topnode;
	
	if(ent->area.prev)
		SV_UnlinkEdict(ent);  // unlink from old position
		
	if(ent == ge->edicts)
		return;  // don't add the world
		
	if(!ent->inuse)
		return;
		
	// set the size
	VectorSubtract(ent->maxs, ent->mins, ent->size);
	
	// encode the size into the entity_state for client prediction
	if(ent->solid == SOLID_BBOX && !(ent->svflags & SVF_DEADMONSTER)){  // assume that x/y are equal and symetric
		i = ent->maxs[0] / 8;
		if(i < 1)
			i = 1;
		if(i > 31)
			i = 31;
			
		// z is not symetric
		j =(-ent->mins[2]) / 8;
		if(j < 1)
			j = 1;
		if(j > 31)
			j = 31;
			
		// and z maxs can be negative...
		k =(ent->maxs[2] + 32) / 8;
		if(k < 1)
			k = 1;
		if(k > 63)
			k = 63;
			
		ent->s.solid =(k << 10) |(j << 5) | i;
	} else if(ent->solid == SOLID_BSP){
		ent->s.solid = 31;  // a solid_bbox will never create this value
	} else
		ent->s.solid = 0;
		
	// set the abs box
	if(ent->solid == SOLID_BSP &&
			(ent->s.angles[0] || ent->s.angles[1] || ent->s.angles[2])){  // expand for rotation
		float max, v;
		int i;
		
		max = 0;
		for(i = 0; i < 3; i++){
			v = fabs(ent->mins[i]);
			if(v > max)
				max = v;
			v = fabs(ent->maxs[i]);
			if(v > max)
				max = v;
		}
		for(i = 0; i < 3; i++){
			ent->absmin[i] = ent->s.origin[i] - max;
			ent->absmax[i] = ent->s.origin[i] + max;
		}
	} else {  // normal
		VectorAdd(ent->s.origin, ent->mins, ent->absmin);
		VectorAdd(ent->s.origin, ent->maxs, ent->absmax);
	}
	
	// because movement is clipped an epsilon away from an actual edge,
	// we must fully check even when bounding boxes don't quite touch
	ent->absmin[0] -= 1;
	ent->absmin[1] -= 1;
	ent->absmin[2] -= 1;
	ent->absmax[0] += 1;
	ent->absmax[1] += 1;
	ent->absmax[2] += 1;
	
	// link to PVS leafs
	ent->num_clusters = 0;
	ent->areanum = 0;
	ent->areanum2 = 0;
	
	//get all leafs, including solids
	num_leafs = CM_BoxLeafnums(ent->absmin, ent->absmax,
								leafs, MAX_TOTAL_ENT_LEAFS, &topnode);
								
	// set areas
	for(i = 0; i < num_leafs; i++){
		clusters[i] = CM_LeafCluster(leafs[i]);
		area = CM_LeafArea(leafs[i]);
		if(area){  // doors may legally straggle two areas,
	// but nothing should evern need more than that
			if(ent->areanum && ent->areanum != area){
				if(ent->areanum2 && ent->areanum2 != area && sv.state == ss_loading)
					Com_DPrintf("Object touching 3 areas at %f %f %f\n",
								 ent->absmin[0], ent->absmin[1], ent->absmin[2]);
				ent->areanum2 = area;
			} else
				ent->areanum = area;
		}
	}
	
	if(num_leafs >= MAX_TOTAL_ENT_LEAFS){  // assume we missed some leafs, and mark by headnode
		ent->num_clusters = -1;
		ent->headnode = topnode;
	} else {
		ent->num_clusters = 0;
		for(i = 0; i < num_leafs; i++){
			if(clusters[i] == -1)
				continue;  // not a visible leaf
			for(j = 0; j < i; j++)
				if(clusters[j] == clusters[i])
					break;
			if(j == i){
				if(ent->num_clusters == MAX_ENT_CLUSTERS){  // assume we missed some leafs, and mark by headnode
					ent->num_clusters = -1;
					ent->headnode = topnode;
					break;
				}
				
				ent->clusternums[ent->num_clusters++] = clusters[i];
			}
		}
	}
	
	// if first time, make sure old_origin is valid
	if(!ent->linkcount){
		VectorCopy(ent->s.origin, ent->s.old_origin);
	}
	ent->linkcount++;
	
	if(ent->solid == SOLID_NOT)
		return;
		
	// find the first node that the ent's box crosses
	node = sv_areanodes;
	while(1){
		if(node->axis == -1)
			break;
		if(ent->absmin[node->axis] > node->dist)
			node = node->children[0];
		else if(ent->absmax[node->axis] < node->dist)
			node = node->children[1];
		else
			break;  // crosses the node
	}
	
	// link it in
	if(ent->solid == SOLID_TRIGGER)
		InsertLinkBefore(&ent->area, &node->trigger_edicts);
	else
		InsertLinkBefore(&ent->area, &node->solid_edicts);
		
}


/*
SV_AreaEdicts_r
 
*/
void SV_AreaEdicts_r(areanode_t *node){
	link_t *l, *next, *start;
	edict_t *check;
	int count;
	
	count = 0;
	
	// touch linked edicts
	if(area_type == AREA_SOLID)
		start = &node->solid_edicts;
	else
		start = &node->trigger_edicts;
		
	for(l = start->next; l != start; l = next){
		next = l->next;
		check = EDICT_FROM_AREA(l);
		
		if(check->solid == SOLID_NOT)
			continue;  // deactivated
		if(check->absmin[0] > area_maxs[0]
				|| check->absmin[1] > area_maxs[1]
				|| check->absmin[2] > area_maxs[2]
				|| check->absmax[0] < area_mins[0]
				|| check->absmax[1] < area_mins[1]
				|| check->absmax[2] < area_mins[2])
			continue;  // not touching
			
		if(area_count == area_maxcount){
			Com_Printf("SV_AreaEdicts: MAXCOUNT\n");
			return;
		}
		
		area_list[area_count] = check;
		area_count++;
	}
	
	if(node->axis == -1)
		return;  // terminal node
		
	// recurse down both sides
	if(area_maxs[node->axis] > node->dist)
		SV_AreaEdicts_r(node->children[0]);
	if(area_mins[node->axis] < node->dist)
		SV_AreaEdicts_r(node->children[1]);
}

/*
SV_AreaEdicts
*/
int SV_AreaEdicts(vec3_t mins, vec3_t maxs, edict_t **list,
				   int maxcount, int areatype){
	area_mins = mins;
	area_maxs = maxs;
	area_list = list;
	area_count = 0;
	area_maxcount = maxcount;
	area_type = areatype;
	
	SV_AreaEdicts_r(sv_areanodes);
	
	return area_count;
}



/*
SV_PointContents
*/
int SV_PointContents(vec3_t p){
	edict_t *touch[MAX_EDICTS], *hit;
	int i, num;
	int contents, c2;
	int headnode;
	float *angles;
	
	// get base contents from world
	contents = CM_PointContents(p, sv.models[1]->headnode);
	
	// or in contents from all the other entities
	num = SV_AreaEdicts(p, p, touch, MAX_EDICTS, AREA_SOLID);
	
	for(i = 0; i < num; i++){
		hit = touch[i];
		
	// might intersect, so do an exact clip
		headnode = SV_HullForEntity(hit);
		angles = hit->s.angles;
		if(hit->solid != SOLID_BSP)
			angles = vec3_origin;  // boxes don't rotate
			
		c2 = CM_TransformedPointContents(p, headnode, hit->s.origin, hit->s.angles);
		
		contents |= c2;
	}
	
	return contents;
}



typedef struct {
	vec3_t boxmins, boxmaxs; // enclose the test object along entire move
	float *mins, *maxs;  // size of the moving object
	vec3_t mins2, maxs2;  // size when clipping against mosnters
	float *start, *end;
	trace_t trace;
	edict_t *passedict;
	int contentmask;
}
moveclip_t;



/*
SV_HullForEntity
 
Returns a headnode that can be used for testing or clipping an
object of mins/maxs size.
Offset is filled in to contain the adjustment that must be added to the
testing object's origin to get a point to use with the returned hull.
*/
int SV_HullForEntity(edict_t *ent){
	cmodel_t *model;
	
	// decide which clipping hull to use, based on the size
	if(ent->solid == SOLID_BSP){  // explicit hulls in the BSP model
		model = sv.models[ ent->s.modelindex ];
		
		if(!model)
			Com_Error(ERR_FATAL, "MOVETYPE_PUSH with a non bsp model");
			
		return model->headnode;
	}
	
	// create a temp hull from bounding box sizes
	
	return CM_HeadnodeForBox(ent->mins, ent->maxs);
}



/*
SV_ClipMoveToEntities
 
*/
void SV_ClipMoveToEntities(moveclip_t *clip){
	int i, num;
	edict_t *touchlist[MAX_EDICTS], *touch;
	trace_t trace;
	int headnode;
	float *angles;
	
	num = SV_AreaEdicts(clip->boxmins, clip->boxmaxs, touchlist
						 , MAX_EDICTS, AREA_SOLID);
						 
	// be careful, it is possible to have an entity in this
	// list removed before we get to it(killtriggered)
	for(i = 0; i < num; i++){
		touch = touchlist[i];
		if(touch->solid == SOLID_NOT)
			continue;
		if(touch == clip->passedict)
			continue;
		if(clip->trace.allsolid)
			return;
		if(clip->passedict){
			if(touch->owner == clip->passedict)
				continue;  // don't clip against own missiles
			if(clip->passedict->owner == touch)
				continue;  // don't clip against owner
		}
		
		if(!(clip->contentmask & CONTENTS_DEADMONSTER)
				&&(touch->svflags & SVF_DEADMONSTER))
			continue;
			
	// might intersect, so do an exact clip
		headnode = SV_HullForEntity(touch);
		angles = touch->s.angles;
		if(touch->solid != SOLID_BSP)
			angles = vec3_origin;  // boxes don't rotate
			
		if(touch->svflags & SVF_MONSTER)
			trace = CM_TransformedBoxTrace(clip->start, clip->end,
											clip->mins2, clip->maxs2, headnode, clip->contentmask,
											touch->s.origin, angles);
		else
			trace = CM_TransformedBoxTrace(clip->start, clip->end,
											clip->mins, clip->maxs, headnode, clip->contentmask,
											touch->s.origin, angles);
											
		if(trace.allsolid || trace.startsolid ||
				trace.fraction < clip->trace.fraction){
			trace.ent = touch;
			if(clip->trace.startsolid){
				clip->trace = trace;
				clip->trace.startsolid = true;
			} else
				clip->trace = trace;
		} else if(trace.startsolid)
			clip->trace.startsolid = true;
	}
}


/*
SV_TraceBounds
*/
void SV_TraceBounds(vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, vec3_t boxmins, vec3_t boxmaxs){
	
	int i;
	
	for(i = 0; i < 3; i++){
		if(end[i] > start[i]){
			boxmins[i] = start[i] + mins[i] - 1;
			boxmaxs[i] = end[i] + maxs[i] + 1;
		} else {
			boxmins[i] = end[i] + mins[i] - 1;
			boxmaxs[i] = start[i] + maxs[i] + 1;
		}
	}
}

/*
SV_Trace
 
Moves the given mins/maxs volume through the world from start to end.
 
Passedict and edicts owned by passedict are explicitly not checked.
 
*/
trace_t SV_Trace(vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, edict_t *passedict, int contentmask){
	moveclip_t clip;
	
	if(!mins)
		mins = vec3_origin;
	if(!maxs)
		maxs = vec3_origin;
		
	memset(&clip, 0, sizeof(moveclip_t));
	
	// clip to world
	clip.trace = CM_BoxTrace(start, end, mins, maxs, 0, contentmask);
	clip.trace.ent = ge->edicts;
	if(clip.trace.fraction == 0)
		return clip.trace;  // blocked by the world
	
	clip.contentmask = contentmask;
	clip.start = start;
	clip.end = end;
	clip.mins = mins;
	clip.maxs = maxs;
	clip.passedict = passedict;
	
	VectorCopy(mins, clip.mins2);
	VectorCopy(maxs, clip.maxs2);
	
	// create the bounding box of the entire move
	SV_TraceBounds(start, clip.mins2, clip.maxs2, end, clip.boxmins, clip.boxmaxs);
	
	// clip to other solid entities
	SV_ClipMoveToEntities(&clip);
	
	return clip.trace;
}