1/* 2Copyright (C) 1996-1997 Id Software, Inc. 3 4This program is free software; you can redistribute it and/or 5modify it under the terms of the GNU General Public License 6as published by the Free Software Foundation; either version 2 7of the License, or (at your option) any later version. 8 9This program is distributed in the hope that it will be useful, 10but WITHOUT ANY WARRANTY; without even the implied warranty of 11MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 12 13See the GNU General Public License for more details. 14 15You should have received a copy of the GNU General Public License 16along with this program; if not, write to the Free Software 17Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 18 19*/ 20#include "quakedef.h" 21 22static hull_t box_hull; 23static dclipnode_t box_clipnodes[6]; 24static mplane_t box_planes[6]; 25 26extern vec3_t player_mins; 27extern vec3_t player_maxs; 28 29/* 30=================== 31PM_InitBoxHull 32 33Set up the planes and clipnodes so that the six floats of a bounding box 34can just be stored out and get a proper hull_t structure. 35=================== 36*/ 37void PM_InitBoxHull (void) 38{ 39 int i; 40 int side; 41 42 box_hull.clipnodes = box_clipnodes; 43 box_hull.planes = box_planes; 44 box_hull.firstclipnode = 0; 45 box_hull.lastclipnode = 5; 46 47 for (i=0 ; i<6 ; i++) 48 { 49 box_clipnodes[i].planenum = i; 50 51 side = i&1; 52 53 box_clipnodes[i].children[side] = CONTENTS_EMPTY; 54 if (i != 5) 55 box_clipnodes[i].children[side^1] = i + 1; 56 else 57 box_clipnodes[i].children[side^1] = CONTENTS_SOLID; 58 59 box_planes[i].type = i>>1; 60 box_planes[i].normal[i>>1] = 1; 61 } 62 63} 64 65 66/* 67=================== 68PM_HullForBox 69 70To keep everything totally uniform, bounding boxes are turned into small 71BSP trees instead of being compared directly. 72=================== 73*/ 74hull_t *PM_HullForBox (vec3_t mins, vec3_t maxs) 75{ 76 box_planes[0].dist = maxs[0]; 77 box_planes[1].dist = mins[0]; 78 box_planes[2].dist = maxs[1]; 79 box_planes[3].dist = mins[1]; 80 box_planes[4].dist = maxs[2]; 81 box_planes[5].dist = mins[2]; 82 83 return &box_hull; 84} 85 86 87/* 88================== 89PM_HullPointContents 90 91================== 92*/ 93int PM_HullPointContents (hull_t *hull, int num, vec3_t p) 94{ 95 float d; 96 dclipnode_t *node; 97 mplane_t *plane; 98 99 while (num >= 0) 100 { 101 if (num < hull->firstclipnode || num > hull->lastclipnode) 102 Sys_Error ("PM_HullPointContents: bad node number"); 103 104 node = hull->clipnodes + num; 105 plane = hull->planes + node->planenum; 106 107 if (plane->type < 3) 108 d = p[plane->type] - plane->dist; 109 else 110 d = DotProduct (plane->normal, p) - plane->dist; 111 if (d < 0) 112 num = node->children[1]; 113 else 114 num = node->children[0]; 115 } 116 117 return num; 118} 119 120/* 121================== 122PM_PointContents 123 124================== 125*/ 126int PM_PointContents (vec3_t p) 127{ 128 float d; 129 dclipnode_t *node; 130 mplane_t *plane; 131 hull_t *hull; 132 int num; 133 134 hull = &pmove.physents[0].model->hulls[0]; 135 136 num = hull->firstclipnode; 137 138 while (num >= 0) 139 { 140 if (num < hull->firstclipnode || num > hull->lastclipnode) 141 Sys_Error ("PM_HullPointContents: bad node number"); 142 143 node = hull->clipnodes + num; 144 plane = hull->planes + node->planenum; 145 146 if (plane->type < 3) 147 d = p[plane->type] - plane->dist; 148 else 149 d = DotProduct (plane->normal, p) - plane->dist; 150 if (d < 0) 151 num = node->children[1]; 152 else 153 num = node->children[0]; 154 } 155 156 return num; 157} 158 159/* 160=============================================================================== 161 162LINE TESTING IN HULLS 163 164=============================================================================== 165*/ 166 167// 1/32 epsilon to keep floating point happy 168#define DIST_EPSILON (0.03125) 169 170/* 171================== 172PM_RecursiveHullCheck 173 174================== 175*/ 176qboolean PM_RecursiveHullCheck (hull_t *hull, int num, float p1f, float p2f, vec3_t p1, vec3_t p2, pmtrace_t *trace) 177{ 178 dclipnode_t *node; 179 mplane_t *plane; 180 float t1, t2; 181 float frac; 182 int i; 183 vec3_t mid; 184 int side; 185 float midf; 186 187// check for empty 188 if (num < 0) 189 { 190 if (num != CONTENTS_SOLID) 191 { 192 trace->allsolid = false; 193 if (num == CONTENTS_EMPTY) 194 trace->inopen = true; 195 else 196 trace->inwater = true; 197 } 198 else 199 trace->startsolid = true; 200 return true; // empty 201 } 202 203 if (num < hull->firstclipnode || num > hull->lastclipnode) 204 Sys_Error ("PM_RecursiveHullCheck: bad node number"); 205 206// 207// find the point distances 208// 209 node = hull->clipnodes + num; 210 plane = hull->planes + node->planenum; 211 212 if (plane->type < 3) 213 { 214 t1 = p1[plane->type] - plane->dist; 215 t2 = p2[plane->type] - plane->dist; 216 } 217 else 218 { 219 t1 = DotProduct (plane->normal, p1) - plane->dist; 220 t2 = DotProduct (plane->normal, p2) - plane->dist; 221 } 222 223#if 1 224 if (t1 >= 0 && t2 >= 0) 225 return PM_RecursiveHullCheck (hull, node->children[0], p1f, p2f, p1, p2, trace); 226 if (t1 < 0 && t2 < 0) 227 return PM_RecursiveHullCheck (hull, node->children[1], p1f, p2f, p1, p2, trace); 228#else 229 if ( (t1 >= DIST_EPSILON && t2 >= DIST_EPSILON) || (t2 > t1 && t1 >= 0) ) 230 return PM_RecursiveHullCheck (hull, node->children[0], p1f, p2f, p1, p2, trace); 231 if ( (t1 <= -DIST_EPSILON && t2 <= -DIST_EPSILON) || (t2 < t1 && t1 <= 0) ) 232 return PM_RecursiveHullCheck (hull, node->children[1], p1f, p2f, p1, p2, trace); 233#endif 234 235// put the crosspoint DIST_EPSILON pixels on the near side 236 if (t1 < 0) 237 frac = (t1 + DIST_EPSILON)/(t1-t2); 238 else 239 frac = (t1 - DIST_EPSILON)/(t1-t2); 240 if (frac < 0) 241 frac = 0; 242 if (frac > 1) 243 frac = 1; 244 245 midf = p1f + (p2f - p1f)*frac; 246 for (i=0 ; i<3 ; i++) 247 mid[i] = p1[i] + frac*(p2[i] - p1[i]); 248 249 side = (t1 < 0); 250 251// move up to the node 252 if (!PM_RecursiveHullCheck (hull, node->children[side], p1f, midf, p1, mid, trace) ) 253 return false; 254 255#ifdef PARANOID 256 if (PM_HullPointContents (pm_hullmodel, mid, node->children[side]) 257 == CONTENTS_SOLID) 258 { 259 Con_Printf ("mid PointInHullSolid\n"); 260 return false; 261 } 262#endif 263 264 if (PM_HullPointContents (hull, node->children[side^1], mid) 265 != CONTENTS_SOLID) 266// go past the node 267 return PM_RecursiveHullCheck (hull, node->children[side^1], midf, p2f, mid, p2, trace); 268 269 if (trace->allsolid) 270 return false; // never got out of the solid area 271 272//================== 273// the other side of the node is solid, this is the impact point 274//================== 275 if (!side) 276 { 277 VectorCopy (plane->normal, trace->plane.normal); 278 trace->plane.dist = plane->dist; 279 } 280 else 281 { 282 VectorSubtract (vec3_origin, plane->normal, trace->plane.normal); 283 trace->plane.dist = -plane->dist; 284 } 285 286 while (PM_HullPointContents (hull, hull->firstclipnode, mid) 287 == CONTENTS_SOLID) 288 { // shouldn't really happen, but does occasionally 289 frac -= 0.1; 290 if (frac < 0) 291 { 292 trace->fraction = midf; 293 VectorCopy (mid, trace->endpos); 294 Con_DPrintf ("backup past 0\n"); 295 return false; 296 } 297 midf = p1f + (p2f - p1f)*frac; 298 for (i=0 ; i<3 ; i++) 299 mid[i] = p1[i] + frac*(p2[i] - p1[i]); 300 } 301 302 trace->fraction = midf; 303 VectorCopy (mid, trace->endpos); 304 305 return false; 306} 307 308 309/* 310================ 311PM_TestPlayerPosition 312 313Returns false if the given player position is not valid (in solid) 314================ 315*/ 316qboolean PM_TestPlayerPosition (vec3_t pos) 317{ 318 int i; 319 physent_t *pe; 320 vec3_t mins, maxs, test; 321 hull_t *hull; 322 323 for (i=0 ; i< pmove.numphysent ; i++) 324 { 325 pe = &pmove.physents[i]; 326 // get the clipping hull 327 if (pe->model) 328 hull = &pmove.physents[i].model->hulls[1]; 329 else 330 { 331 VectorSubtract (pe->mins, player_maxs, mins); 332 VectorSubtract (pe->maxs, player_mins, maxs); 333 hull = PM_HullForBox (mins, maxs); 334 } 335 336 VectorSubtract (pos, pe->origin, test); 337 338 if (PM_HullPointContents (hull, hull->firstclipnode, test) == CONTENTS_SOLID) 339 return false; 340 } 341 342 return true; 343} 344 345/* 346================ 347PM_PlayerMove 348================ 349*/ 350pmtrace_t PM_PlayerMove (vec3_t start, vec3_t end) 351{ 352 pmtrace_t trace, total; 353 vec3_t offset; 354 vec3_t start_l, end_l; 355 hull_t *hull; 356 int i; 357 physent_t *pe; 358 vec3_t mins, maxs; 359 360// fill in a default trace 361 memset (&total, 0, sizeof(pmtrace_t)); 362 total.fraction = 1; 363 total.ent = -1; 364 VectorCopy (end, total.endpos); 365 366 for (i=0 ; i< pmove.numphysent ; i++) 367 { 368 pe = &pmove.physents[i]; 369 // get the clipping hull 370 if (pe->model) 371 hull = &pmove.physents[i].model->hulls[1]; 372 else 373 { 374 VectorSubtract (pe->mins, player_maxs, mins); 375 VectorSubtract (pe->maxs, player_mins, maxs); 376 hull = PM_HullForBox (mins, maxs); 377 } 378 379 // PM_HullForEntity (ent, mins, maxs, offset); 380 VectorCopy (pe->origin, offset); 381 382 VectorSubtract (start, offset, start_l); 383 VectorSubtract (end, offset, end_l); 384 385 // fill in a default trace 386 memset (&trace, 0, sizeof(pmtrace_t)); 387 trace.fraction = 1; 388 trace.allsolid = true; 389// trace.startsolid = true; 390 VectorCopy (end, trace.endpos); 391 392 // trace a line through the apropriate clipping hull 393 PM_RecursiveHullCheck (hull, hull->firstclipnode, 0, 1, start_l, end_l, &trace); 394 395 if (trace.allsolid) 396 trace.startsolid = true; 397 if (trace.startsolid) 398 trace.fraction = 0; 399 400 // did we clip the move? 401 if (trace.fraction < total.fraction) 402 { 403 // fix trace up by the offset 404 VectorAdd (trace.endpos, offset, trace.endpos); 405 total = trace; 406 total.ent = i; 407 } 408 409 } 410 411 return total; 412} 413 414 415