#include "server.h"
#define STRUCT_FROM_LINK(l, t, m) ((t *)((byte *)l - (uintptr_t) & (((t *)0)->m)))
#define EDICT_FROM_AREA(l) STRUCT_FROM_LINK(l, edict_t, area)
typedef struct areanode_s {
int axis; 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[CMODEL_COUNT][AREA_NODES];
int sv_numareanodes[CMODEL_COUNT];
float *area_mins, *area_maxs;
edict_t **area_list;
int area_count, area_maxcount;
int area_type;
int SV_HullForEntity(edict_t *ent);
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;
}
areanode_t *SV_CreateAreaNode(int cmodel_index, int depth, vec3_t mins, vec3_t maxs) {
areanode_t *anode;
vec3_t size;
vec3_t mins1, maxs1, mins2, maxs2;
anode = &sv_areanodes[cmodel_index][sv_numareanodes[cmodel_index]];
sv_numareanodes[cmodel_index]++;
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(cmodel_index, depth + 1, mins2, maxs2);
anode->children[1] = SV_CreateAreaNode(cmodel_index, depth + 1, mins1, maxs1);
return anode;
}
void SV_ClearWorld(int cmodel_index) {
memset(sv_areanodes[cmodel_index], 0, sizeof(sv_areanodes[0]));
sv_numareanodes[cmodel_index] = 0;
SV_CreateAreaNode(cmodel_index, 0, sv.models[CMODEL_A][0]->mins, sv.models[CMODEL_A][0]->maxs);
}
void SV_UnlinkEdict(edict_t *ent) {
if(!ent->area.prev)
return; RemoveLink(&ent->area);
ent->area.prev = ent->area.next = NULL;
}
#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);
if(ent == ge->edicts)
return;
if(!ent->inuse)
return;
int cmodel_index = ent->s.cmodel_index;
VectorSubtract(ent->maxs, ent->mins, ent->size);
if(ent->solid == SOLID_BBOX && !(ent->svflags & SVF_DEADMONSTER)) { i = ent->maxs[0] / 8;
if(i < 1)
i = 1;
if(i > 31)
i = 31;
j = (-ent->mins[2]) / 8;
if(j < 1)
j = 1;
if(j > 31)
j = 31;
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; } else
ent->s.solid = 0;
if(ent->solid == SOLID_BSP && (ent->s.angles[0] || ent->s.angles[1] || ent->s.angles[2])) { 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 { VectorAdd(ent->s.origin, ent->mins, ent->absmin);
VectorAdd(ent->s.origin, ent->maxs, ent->absmax);
}
ent->absmin[0] -= 1;
ent->absmin[1] -= 1;
ent->absmin[2] -= 1;
ent->absmax[0] += 1;
ent->absmax[1] += 1;
ent->absmax[2] += 1;
ent->num_clusters = 0;
ent->areanum = 0;
ent->areanum2 = 0;
num_leafs = CM_BoxLeafnums(cmodel_index, ent->absmin, ent->absmax, leafs, MAX_TOTAL_ENT_LEAFS, &topnode);
for(i = 0; i < num_leafs; i++) {
clusters[i] = CM_LeafCluster(cmodel_index, leafs[i]);
area = CM_LeafArea(cmodel_index, leafs[i]);
if(area) { 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) { ent->num_clusters = -1;
ent->headnode = topnode;
} else {
ent->num_clusters = 0;
for(i = 0; i < num_leafs; i++) {
if(clusters[i] == -1)
continue; for(j = 0; j < i; j++)
if(clusters[j] == clusters[i])
break;
if(j == i) {
if(ent->num_clusters == MAX_ENT_CLUSTERS) { ent->num_clusters = -1;
ent->headnode = topnode;
break;
}
ent->clusternums[ent->num_clusters++] = clusters[i];
}
}
}
if(!ent->linkcount) {
VectorCopy(ent->s.origin, ent->s.old_origin);
}
ent->linkcount++;
if(ent->solid == SOLID_NOT)
return;
node = sv_areanodes[cmodel_index];
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; }
if(ent->solid == SOLID_TRIGGER)
InsertLinkBefore(&ent->area, &node->trigger_edicts);
else
InsertLinkBefore(&ent->area, &node->solid_edicts);
}
void SV_AreaEdicts_r(areanode_t *node) {
link_t *l, *next, *start;
edict_t *check;
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; 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;
if(area_count == area_maxcount) {
Com_Printf("SV_AreaEdicts: MAXCOUNT\n");
return;
}
area_list[area_count] = check;
area_count++;
}
if(node->axis == -1)
return;
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]);
}
int SV_AreaEdicts(int cmodel_index, 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[cmodel_index]);
return area_count;
}
int SV_PointContents(int cmodel_index, vec3_t p) {
edict_t *touch[MAX_EDICTS], *hit;
int i, num;
int contents, c2;
int headnode;
contents = CM_PointContents(cmodel_index, p, sv.models[cmodel_index][0]->headnode);
num = SV_AreaEdicts(cmodel_index, p, p, touch, MAX_EDICTS, AREA_SOLID);
for(i = 0; i < num; i++) {
hit = touch[i];
headnode = SV_HullForEntity(hit);
c2 = CM_TransformedPointContents(cmodel_index, p, headnode, hit->s.origin, hit->s.angles);
contents |= c2;
}
return contents;
}
typedef struct {
vec3_t boxmins, boxmaxs; float *mins, *maxs; vec3_t mins2, maxs2; float *start, *end;
trace_t trace;
edict_t *passedict;
int contentmask;
} moveclip_t;
int SV_HullForEntity(edict_t *ent) {
cmodel_t *model;
if(ent->solid == SOLID_BSP) { model = sv.models[ent->s.modelindex - 1][ent->s.modelindex2];
if(!model)
Com_Error(ERR_FATAL, "MOVETYPE_PUSH with a non bsp model");
return model->headnode;
}
return CM_HeadnodeForBox(ent->s.cmodel_index, ent->mins, ent->maxs);
}
void SV_ClipMoveToEntities(int cmodel_index, moveclip_t *clip) {
int i, num;
edict_t *touchlist[MAX_EDICTS], *touch;
trace_t trace;
int headnode;
float *angles;
num = SV_AreaEdicts(cmodel_index, clip->boxmins, clip->boxmaxs, touchlist, MAX_EDICTS, AREA_SOLID);
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; if(clip->passedict->owner == touch)
continue; }
if(!(clip->contentmask & CONTENTS_DEADMONSTER) && (touch->svflags & SVF_DEADMONSTER))
continue;
headnode = SV_HullForEntity(touch);
angles = touch->s.angles;
if(touch->solid != SOLID_BSP)
angles = vec3_origin;
if(touch->svflags & SVF_MONSTER)
trace = CM_TransformedBoxTrace(cmodel_index, clip->start, clip->end, clip->mins2, clip->maxs2, headnode,
clip->contentmask, touch->s.origin, angles);
else
trace = CM_TransformedBoxTrace(cmodel_index, 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;
}
}
void SV_TraceBounds(vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, vec3_t boxmins, vec3_t boxmaxs) {
#if 0#else
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;
}
}
#endif
}
trace_t SV_Trace(int cmodel_index, 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.trace = CM_BoxTrace(cmodel_index, start, end, mins, maxs, 0, contentmask);
clip.trace.ent = ge->edicts;
if(clip.trace.fraction == 0)
return clip.trace;
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);
SV_TraceBounds(start, clip.mins2, clip.maxs2, end, clip.boxmins, clip.boxmaxs);
SV_ClipMoveToEntities(cmodel_index, &clip);
return clip.trace;
}