1 /* 2 Copyright (C) 1996-1997 Id Software, Inc. 3 4 This program is free software; you can redistribute it and/or 5 modify it under the terms of the GNU General Public License 6 as published by the Free Software Foundation; either version 2 7 of the License, or (at your option) any later version. 8 9 This program is distributed in the hope that it will be useful, 10 but WITHOUT ANY WARRANTY; without even the implied warranty of 11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 12 13 See the GNU General Public License for more details. 14 15 You should have received a copy of the GNU General Public License 16 along with this program; if not, write to the Free Software 17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 18 19 */ 20 #include "quakedef.h" 21 22 static hull_t box_hull; 23 static dclipnode_t box_clipnodes[6]; 24 static mplane_t box_planes[6]; 25 26 extern vec3_t player_mins; 27 extern vec3_t player_maxs; 28 29 /* 30 =================== 31 PM_InitBoxHull 32 33 Set up the planes and clipnodes so that the six floats of a bounding box 34 can just be stored out and get a proper hull_t structure. 35 =================== 36 */ 37 void 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 =================== 68 PM_HullForBox 69 70 To keep everything totally uniform, bounding boxes are turned into small 71 BSP trees instead of being compared directly. 72 =================== 73 */ 74 hull_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 ================== 89 PM_HullPointContents 90 91 ================== 92 */ 93 int 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 ================== 122 PM_PointContents 123 124 ================== 125 */ 126 int 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 162 LINE 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 ================== 172 PM_RecursiveHullCheck 173 174 ================== 175 */ 176 qboolean 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 ================ 311 PM_TestPlayerPosition 312 313 Returns false if the given player position is not valid (in solid) 314 ================ 315 */ 316 qboolean 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 ================ 347 PM_PlayerMove 348 ================ 349 */ 350 pmtrace_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
