From 49103816aa305086338c024347d7b461c4d3de06 Mon Sep 17 00:00:00 2001 From: havoc Date: Fri, 21 Feb 2003 09:24:53 +0000 Subject: [PATCH] added new method of culling irrelevant entity collisions - a grid of areas the areanode system still lingers because it can cope with things the grid can not (entities outside the grid, or too large for the alloted 16 grid links per entity) git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@2775 d7cf8633-e32d-0410-b094-e92efae38249 --- progs.h | 5 + world.c | 435 +++++++++++++++++++++++++++++++++++++++++++------------- 2 files changed, 343 insertions(+), 97 deletions(-) diff --git a/progs.h b/progs.h index 1438dce2..6d3fb999 100644 --- a/progs.h +++ b/progs.h @@ -37,9 +37,12 @@ typedef union eval_s typedef struct link_s { + void *entity; struct link_s *prev, *next; } link_t; +#define ENTITYGRIDAREAS 16 + // the entire server entity structure typedef struct edict_s { @@ -47,6 +50,8 @@ typedef struct edict_s qboolean free; // physics area this edict is linked into link_t area; + // physics grid areas this edict is linked into + link_t areagrid[ENTITYGRIDAREAS]; // old entity protocol, not used #ifdef QUAKEENTITIES diff --git a/world.c b/world.c index 395f54e1..7505c86f 100644 --- a/world.c +++ b/world.c @@ -25,7 +25,7 @@ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. entities never clip against themselves, or their owner -line of sight checks trace->crosscontent, but bullets don't +line of sight checks trace->inopen and trace->inwater, but bullets don't */ @@ -36,22 +36,46 @@ void SV_World_Init(void) { Cvar_RegisterVariable(&sv_useareanodes); Cvar_RegisterVariable(&sv_polygoncollisions); - Collision_Init (); + Collision_Init(); } +typedef struct +{ + // bounding box of entire move area + vec3_t boxmins, boxmaxs; + + // size of the moving object + vec3_t mins, maxs; + + // size when clipping against monsters + vec3_t mins2, maxs2; + + // size when clipping against brush models + vec3_t hullmins, hullmaxs; -void ClearLink (link_t *l); -void RemoveLink (link_t *l); -void InsertLinkBefore (link_t *l, link_t *before); -void InsertLinkAfter (link_t *l, link_t *after); + // start and end origin of move + vec3_t start, end; -#define EDICT_FROM_AREA(l) ((edict_t *)((qbyte *)l - (int)&(((edict_t *)0)->area))) + // trace results + trace_t trace; + + // type of move (like ignoring monsters, or similar) + int type; + + // the edict that is moving (if any) + edict_t *passedict; +} +moveclip_t; + +//#define EDICT_FROM_AREA(l) ((edict_t *)((qbyte *)l - (int)&(((edict_t *)0)->area))) +#define EDICT_FROM_AREA(l) ((edict_t *)l->entity) //============================================================================ // ClearLink is used for new headnodes void ClearLink (link_t *l) { + l->entity = NULL; l->prev = l->next = l; } @@ -61,13 +85,15 @@ void RemoveLink (link_t *l) l->prev->next = l->next; } -void InsertLinkBefore (link_t *l, link_t *before) +void InsertLinkBefore (link_t *l, link_t *before, void *ent) { + l->entity = ent; l->next = before; l->prev = before->prev; l->prev->next = l; l->next->prev = l; } + void InsertLinkAfter (link_t *l, link_t *after) { l->next = after->next; @@ -77,35 +103,6 @@ void InsertLinkAfter (link_t *l, link_t *after) } -typedef struct -{ - // bounding box of entire move area - vec3_t boxmins, boxmaxs; - - // size of the moving object - vec3_t mins, maxs; - - // size when clipping against monsters - vec3_t mins2, maxs2; - - // size when clipping against brush models - vec3_t hullmins, hullmaxs; - - // start and end origin of move - vec3_t start, end; - - // trace results - trace_t trace; - - // type of move (like ignoring monsters, or similar) - int type; - - // the edict that is moving (if any) - edict_t *passedict; -} -moveclip_t; - - /* =============================================================================== @@ -116,18 +113,20 @@ ENTITY AREA CHECKING 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; + // -1 = leaf node + int axis; + float dist; + struct areanode_s *children[2]; + link_t trigger_edicts; + link_t solid_edicts; +} +areanode_t; -#define AREA_DEPTH 10 -#define AREA_NODES (1 << (AREA_DEPTH + 1)) +#define AREA_DEPTH 1 +#define AREA_NODES (1 << (AREA_DEPTH + 1)) -static areanode_t sv_areanodes[AREA_NODES]; -static int sv_numareanodes; +static areanode_t sv_areanodes[AREA_NODES]; +static int sv_numareanodes; /* =============== @@ -137,9 +136,8 @@ SV_CreateAreaNode */ areanode_t *SV_CreateAreaNode (int depth, vec3_t mins, vec3_t maxs) { - areanode_t *anode; - vec3_t size; - vec3_t mins1, maxs1, mins2, maxs2; + areanode_t *anode; + vec3_t size, mins1, maxs1, mins2, maxs2; anode = &sv_areanodes[sv_numareanodes]; sv_numareanodes++; @@ -174,6 +172,33 @@ areanode_t *SV_CreateAreaNode (int depth, vec3_t mins, vec3_t maxs) return anode; } +typedef struct areagrid_s +{ + link_t trigger_edicts; + link_t solid_edicts; +} +areagrid_t; + +#define AREA_GRID 32 +#define AREA_GRIDNODES (AREA_GRID * AREA_GRID) + +static areagrid_t sv_areagrid[AREA_GRIDNODES]; +static vec3_t sv_areagridbias, sv_areagridscale; + +void SV_CreateAreaGrid (vec3_t mins, vec3_t maxs) +{ + int i; + VectorNegate(mins, sv_areagridbias); + sv_areagridscale[0] = AREA_GRID / (maxs[0] + sv_areagridbias[0]); + sv_areagridscale[1] = AREA_GRID / (maxs[1] + sv_areagridbias[1]); + sv_areagridscale[2] = AREA_GRID / (maxs[2] + sv_areagridbias[2]); + for (i = 0;i < AREA_GRIDNODES;i++) + { + ClearLink (&sv_areagrid[i].trigger_edicts); + ClearLink (&sv_areagrid[i].solid_edicts); + } +} + /* =============== SV_ClearWorld @@ -182,10 +207,11 @@ SV_ClearWorld */ void SV_ClearWorld (void) { - memset (sv_areanodes, 0, sizeof(sv_areanodes)); + memset(sv_areanodes, 0, sizeof(sv_areanodes)); sv_numareanodes = 0; Mod_CheckLoaded(sv.worldmodel); - SV_CreateAreaNode (0, sv.worldmodel->normalmins, sv.worldmodel->normalmaxs); + SV_CreateAreaNode(0, sv.worldmodel->normalmins, sv.worldmodel->normalmaxs); + SV_CreateAreaGrid(sv.worldmodel->normalmins, sv.worldmodel->normalmaxs); } @@ -197,23 +223,33 @@ 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; + int i; + for (i = 0;i < ENTITYGRIDAREAS;i++) + { + if (ent->areagrid[i].prev) + { + RemoveLink (&ent->areagrid[i]); + ent->areagrid[i].prev = ent->areagrid[i].next = NULL; + } + } + if (ent->area.prev) + { + RemoveLink (&ent->area); + ent->area.prev = ent->area.next = NULL; + } } /* ==================== -SV_TouchLinks +SV_TouchAreaNodes ==================== */ -void SV_TouchLinks ( edict_t *ent, areanode_t *node ) +void SV_TouchAreaNodes ( edict_t *ent, areanode_t *node ) { - link_t *l, *next; - edict_t *touch; - int old_self, old_other; + link_t *l, *next; + edict_t *touch; + int old_self, old_other; loc0: // touch linked edicts @@ -251,7 +287,7 @@ loc0: if (ent->v->absmax[node->axis] > node->dist) { if (ent->v->absmin[node->axis] < node->dist) - SV_TouchLinks(ent, node->children[1]); // order reversed to reduce code + SV_TouchAreaNodes(ent, node->children[1]); // order reversed to reduce code node = node->children[0]; goto loc0; } @@ -265,6 +301,114 @@ loc0: } } +void SV_TouchAreaGrid(edict_t *ent, areanode_t *node) +{ + link_t *l, *next; + edict_t *touch; + areagrid_t *grid; + int old_self, old_other, igrid[3], igridmins[3], igridmaxs[3]; + + igridmins[0] = (int) ((ent->v->absmin[0] + sv_areagridbias[0]) * sv_areagridscale[0]); + igridmins[1] = (int) ((ent->v->absmin[1] + sv_areagridbias[1]) * sv_areagridscale[1]); + //igridmins[2] = (int) ((ent->v->absmin[2] + sv_areagridbias[2]) * sv_areagridscale[2]); + igridmaxs[0] = (int) ((ent->v->absmax[0] + sv_areagridbias[0]) * sv_areagridscale[0]) + 1; + igridmaxs[1] = (int) ((ent->v->absmax[1] + sv_areagridbias[1]) * sv_areagridscale[1]) + 1; + //igridmaxs[2] = (int) ((ent->v->absmax[2] + sv_areagridbias[2]) * sv_areagridscale[2]) + 1; + igridmins[0] = max(0, igridmins[0]); + igridmins[1] = max(0, igridmins[1]); + //igridmins[2] = max(0, igridmins[2]); + igridmaxs[0] = min(AREA_GRID, igridmaxs[0]); + igridmaxs[1] = min(AREA_GRID, igridmaxs[1]); + //igridmaxs[2] = min(AREA_GRID, igridmaxs[2]); + + for (igrid[1] = igridmins[1];igrid[1] < igridmaxs[1];igrid[1]++) + { + grid = sv_areagrid + igrid[1] * AREA_GRID + igridmins[0]; + for (igrid[0] = igridmins[0];igrid[0] < igridmaxs[0];igrid[0]++, grid++) + { + for (l = grid->trigger_edicts.next;l != &grid->trigger_edicts;l = next) + { + next = l->next; + touch = EDICT_FROM_AREA(l); + if (touch == ent) + continue; + if (!touch->v->touch || touch->v->solid != SOLID_TRIGGER) + continue; + if (ent->v->absmin[0] > touch->v->absmax[0] + || ent->v->absmin[1] > touch->v->absmax[1] + || ent->v->absmin[2] > touch->v->absmax[2] + || ent->v->absmax[0] < touch->v->absmin[0] + || ent->v->absmax[1] < touch->v->absmin[1] + || ent->v->absmax[2] < touch->v->absmin[2]) + continue; + old_self = pr_global_struct->self; + old_other = pr_global_struct->other; + + pr_global_struct->self = EDICT_TO_PROG(touch); + pr_global_struct->other = EDICT_TO_PROG(ent); + pr_global_struct->time = sv.time; + PR_ExecuteProgram (touch->v->touch, ""); + + pr_global_struct->self = old_self; + pr_global_struct->other = old_other; + } + } + } +} + +void SV_LinkEdict_AreaNode(edict_t *ent) +{ + areanode_t *node; + // find the first node that the ent's box crosses + node = sv_areanodes; + while (1) + { + if (node->axis == -1) + break; + if (ent->v->absmin[node->axis] > node->dist) + node = node->children[0]; + else if (ent->v->absmax[node->axis] < node->dist) + node = node->children[1]; + else + break; // crosses the node + } + + // link it in + + if (ent->v->solid == SOLID_TRIGGER) + InsertLinkBefore (&ent->area, &node->trigger_edicts, ent); + else + InsertLinkBefore (&ent->area, &node->solid_edicts, ent); +} + +int SV_LinkEdict_AreaGrid(edict_t *ent) +{ + areagrid_t *grid; + int igrid[3], igridmins[3], igridmaxs[3], gridnum; + + igridmins[0] = (int) ((ent->v->absmin[0] + sv_areagridbias[0]) * sv_areagridscale[0]); + igridmins[1] = (int) ((ent->v->absmin[1] + sv_areagridbias[1]) * sv_areagridscale[1]); + //igridmins[2] = (int) ((ent->v->absmin[2] + sv_areagridbias[2]) * sv_areagridscale[2]); + igridmaxs[0] = (int) ((ent->v->absmax[0] + sv_areagridbias[0]) * sv_areagridscale[0]) + 1; + igridmaxs[1] = (int) ((ent->v->absmax[1] + sv_areagridbias[1]) * sv_areagridscale[1]) + 1; + //igridmaxs[2] = (int) ((ent->v->absmax[2] + sv_areagridbias[2]) * sv_areagridscale[2]) + 1; + if (igridmins[0] < 0 || igridmaxs[0] > AREA_GRID || igridmins[1] < 0 || igridmaxs[1] > AREA_GRID || ((igridmaxs[0] - igridmins[0]) * (igridmaxs[1] - igridmins[1])) > ENTITYGRIDAREAS) + return false; + + gridnum = 0; + for (igrid[1] = igridmins[1];igrid[1] < igridmaxs[1];igrid[1]++) + { + grid = sv_areagrid + igrid[1] * AREA_GRID + igridmins[0]; + for (igrid[0] = igridmins[0];igrid[0] < igridmaxs[0];igrid[0]++, grid++, gridnum++) + { + if (ent->v->solid == SOLID_TRIGGER) + InsertLinkBefore (&ent->areagrid[gridnum], &grid->trigger_edicts, ent); + else + InsertLinkBefore (&ent->areagrid[gridnum], &grid->solid_edicts, ent); + } + } + return true; +} /* =============== @@ -274,10 +418,9 @@ SV_LinkEdict */ void SV_LinkEdict (edict_t *ent, qboolean touch_triggers) { - model_t *model; - areanode_t *node; + model_t *model; - if (ent->area.prev) + if (ent->area.prev || ent->areagrid[0].prev) SV_UnlinkEdict (ent); // unlink from old position if (ent == sv.edicts) @@ -317,14 +460,14 @@ void SV_LinkEdict (edict_t *ent, qboolean touch_triggers) else { // SOLID_BSP with no model is valid, mainly because some QC setup code does so temporarily - VectorAdd (ent->v->origin, ent->v->mins, ent->v->absmin); - VectorAdd (ent->v->origin, ent->v->maxs, ent->v->absmax); + VectorAdd(ent->v->origin, ent->v->mins, ent->v->absmin); + VectorAdd(ent->v->origin, ent->v->maxs, ent->v->absmax); } } else { - VectorAdd (ent->v->origin, ent->v->mins, ent->v->absmin); - VectorAdd (ent->v->origin, ent->v->maxs, ent->v->absmax); + VectorAdd(ent->v->origin, ent->v->mins, ent->v->absmin); + VectorAdd(ent->v->origin, ent->v->maxs, ent->v->absmax); } // @@ -355,30 +498,16 @@ void SV_LinkEdict (edict_t *ent, qboolean touch_triggers) if (ent->v->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->v->absmin[node->axis] > node->dist) - node = node->children[0]; - else if (ent->v->absmax[node->axis] < node->dist) - node = node->children[1]; - else - break; // crosses the node - } - -// link it in - - if (ent->v->solid == SOLID_TRIGGER) - InsertLinkBefore (&ent->area, &node->trigger_edicts); - else - InsertLinkBefore (&ent->area, &node->solid_edicts); + // try to link into areagrid, if that fails fall back on areanode + if (!SV_LinkEdict_AreaGrid(ent)) + SV_LinkEdict_AreaNode(ent); // if touch_triggers, touch all entities at this node and descend for more if (touch_triggers) - SV_TouchLinks ( ent, sv_areanodes ); + { + SV_TouchAreaNodes(ent, sv_areanodes); + SV_TouchAreaGrid(ent, sv_areanodes); + } } @@ -458,16 +587,16 @@ trace_t SV_ClipMoveToEntity (edict_t *ent, vec3_t start, vec3_t mins, vec3_t max /* ==================== -SV_ClipToLinks +SV_ClipToAreaNodes Mins and maxs enclose the entire area swept by the move ==================== */ -void SV_ClipToLinks ( areanode_t *node, moveclip_t *clip ) +void SV_ClipToAreaNodes ( areanode_t *node, moveclip_t *clip ) { - link_t *l, *next; - edict_t *touch; - trace_t trace; + link_t *l, *next; + edict_t *touch; + trace_t trace; loc0: if (clip->trace.allsolid) @@ -550,7 +679,7 @@ loc0: if (clip->boxmaxs[node->axis] > node->dist) { if (clip->boxmins[node->axis] < node->dist) - SV_ClipToLinks(node->children[1], clip); + SV_ClipToAreaNodes(node->children[1], clip); node = node->children[0]; goto loc0; } @@ -561,6 +690,117 @@ loc0: } } +/* +==================== +SV_ClipToAreaGrid + +Mins and maxs enclose the entire area swept by the move +==================== +*/ +void SV_ClipToAreaGrid(moveclip_t *clip) +{ + link_t *l, *next; + edict_t *touch; + areagrid_t *grid; + int igrid[3], igridmins[3], igridmaxs[3]; + trace_t trace; + + if (clip->trace.allsolid) + return; + + igridmins[0] = (int) ((clip->boxmins[0] + sv_areagridbias[0]) * sv_areagridscale[0]); + igridmins[1] = (int) ((clip->boxmins[1] + sv_areagridbias[1]) * sv_areagridscale[1]); + //igridmins[2] = (int) ((clip->boxmins[2] + sv_areagridbias[2]) * sv_areagridscale[2]); + igridmaxs[0] = (int) ((clip->boxmaxs[0] + sv_areagridbias[0]) * sv_areagridscale[0]) + 1; + igridmaxs[1] = (int) ((clip->boxmaxs[1] + sv_areagridbias[1]) * sv_areagridscale[1]) + 1; + //igridmaxs[2] = (int) ((clip->boxmaxs[2] + sv_areagridbias[2]) * sv_areagridscale[2]) + 1; + igridmins[0] = max(0, igridmins[0]); + igridmins[1] = max(0, igridmins[1]); + //igridmins[2] = max(0, igridmins[2]); + igridmaxs[0] = min(AREA_GRID, igridmaxs[0]); + igridmaxs[1] = min(AREA_GRID, igridmaxs[1]); + //igridmaxs[2] = min(AREA_GRID, igridmaxs[2]); + + for (igrid[1] = igridmins[1];igrid[1] < igridmaxs[1];igrid[1]++) + { + grid = sv_areagrid + igrid[1] * AREA_GRID + igridmins[0]; + for (igrid[0] = igridmins[0];igrid[0] < igridmaxs[0];igrid[0]++, grid++) + { + for (l = grid->solid_edicts.next;l != &grid->solid_edicts;l = next) + { + next = l->next; + touch = EDICT_FROM_AREA(l); + if (touch->v->solid == SOLID_NOT) + continue; + if (touch == clip->passedict) + continue; + if (touch->v->solid == SOLID_TRIGGER) + { + ED_Print(touch); + Host_Error ("Trigger in clipping list"); + } + + if (clip->type == MOVE_NOMONSTERS && touch->v->solid != SOLID_BSP) + continue; + + if (clip->boxmins[0] > touch->v->absmax[0] + || clip->boxmaxs[0] < touch->v->absmin[0] + || clip->boxmins[1] > touch->v->absmax[1] + || clip->boxmaxs[1] < touch->v->absmin[1] + || clip->boxmins[2] > touch->v->absmax[2] + || clip->boxmaxs[2] < touch->v->absmin[2]) + continue; + + if (clip->passedict) + { + if (clip->passedict->v->size[0] && !touch->v->size[0]) + continue; // points never interact + if (PROG_TO_EDICT(touch->v->owner) == clip->passedict) + continue; // don't clip against own missiles + if (PROG_TO_EDICT(clip->passedict->v->owner) == touch) + continue; // don't clip against owner + // LordHavoc: corpse code + if (clip->passedict->v->solid == SOLID_CORPSE && (touch->v->solid == SOLID_SLIDEBOX || touch->v->solid == SOLID_CORPSE)) + continue; + if (clip->passedict->v->solid == SOLID_SLIDEBOX && touch->v->solid == SOLID_CORPSE) + continue; + } + + // might interact, so do an exact clip + if (touch->v->solid == SOLID_BSP) + trace = SV_ClipMoveToEntity (touch, clip->start, clip->hullmins, clip->hullmaxs, clip->end); + else if ((int)touch->v->flags & FL_MONSTER) + trace = SV_ClipMoveToEntity (touch, clip->start, clip->mins2, clip->maxs2, clip->end); + else + trace = SV_ClipMoveToEntity (touch, clip->start, clip->mins, clip->maxs, clip->end); + // LordHavoc: take the 'best' answers from the new trace and combine with existing data + if (trace.allsolid) + clip->trace.allsolid = true; + if (trace.startsolid) + { + clip->trace.startsolid = true; + if (!clip->trace.ent) + clip->trace.ent = trace.ent; + } + if (trace.inopen) + clip->trace.inopen = true; + if (trace.inwater) + clip->trace.inwater = true; + if (trace.fraction < clip->trace.fraction) + { + clip->trace.fraction = trace.fraction; + VectorCopy(trace.endpos, clip->trace.endpos); + clip->trace.plane = trace.plane; + clip->trace.endcontents = trace.endcontents; + clip->trace.ent = trace.ent; + } + if (clip->trace.allsolid) + return; + } + } + } +} + /* ================== @@ -646,7 +886,8 @@ trace_t SV_Move (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, int type, e // create the bounding box of the entire move SV_MoveBounds ( start, bigmins, bigmaxs, end, clip.boxmins, clip.boxmaxs ); - SV_ClipToLinks ( sv_areanodes, &clip ); + SV_ClipToAreaNodes(sv_areanodes, &clip); + SV_ClipToAreaGrid(&clip); return clip.trace; } -- 2.39.2