main/fvi.c

   1 /* $Id: fvi.c,v 1.3 2003-10-10 09:36:35 btb Exp $ */
   2 /*
   3 THE COMPUTER CODE CONTAINED HEREIN IS THE SOLE PROPERTY OF PARALLAX
   4 SOFTWARE CORPORATION ("PARALLAX").  PARALLAX, IN DISTRIBUTING THE CODE TO
   5 END-USERS, AND SUBJECT TO ALL OF THE TERMS AND CONDITIONS HEREIN, GRANTS A
   6 ROYALTY-FREE, PERPETUAL LICENSE TO SUCH END-USERS FOR USE BY SUCH END-USERS
   7 IN USING, DISPLAYING,  AND CREATING DERIVATIVE WORKS THEREOF, SO LONG AS
   8 SUCH USE, DISPLAY OR CREATION IS FOR NON-COMMERCIAL, ROYALTY OR REVENUE
   9 FREE PURPOSES.  IN NO EVENT SHALL THE END-USER USE THE COMPUTER CODE
  10 CONTAINED HEREIN FOR REVENUE-BEARING PURPOSES.  THE END-USER UNDERSTANDS
  11 AND AGREES TO THE TERMS HEREIN AND ACCEPTS THE SAME BY USE OF THIS FILE.
  12 COPYRIGHT 1993-1999 PARALLAX SOFTWARE CORPORATION.  ALL RIGHTS RESERVED.
  13 */
  14
  15 /*
  16  *
  17  * New home for find_vector_intersection()
  18  *
  19  * Old Log:
  20  * Revision 1.7  1995/10/21  23:52:18  allender
  21  * #ifdef'ed out stack debug stuff
  22  *
  23  * Revision 1.6  1995/10/10  12:07:42  allender
  24  * add forgotten ;
  25  *
  26  * Revision 1.5  1995/10/10  11:47:27  allender
  27  * put in stack space check
  28  *
  29  * Revision 1.4  1995/08/23  21:34:08  allender
  30  * fix mcc compiler warning
  31  *
  32  * Revision 1.3  1995/08/14  14:35:18  allender
  33  * changed transparency to 0
  34  *
  35  * Revision 1.2  1995/07/05  16:50:51  allender
  36  * transparency/kitchen change
  37  *
  38  * Revision 1.1  1995/05/16  15:24:59  allender
  39  * Initial revision
  40  *
  41  * Revision 2.3  1995/03/24  14:49:04  john
  42  * Added cheat for player to go thru walls.
  43  *
  44  * Revision 2.2  1995/03/21  17:58:32  john
  45  * Fixed bug with normals..
  46  *
  47  *
  48  * Revision 2.1  1995/03/20  18:15:37  john
  49  * Added code to not store the normals in the segment structure.
  50  *
  51  * Revision 2.0  1995/02/27  11:27:41  john
  52  * New version 2.0, which has no anonymous unions, builds with
  53  * Watcom 10.0, and doesn't require parsing BITMAPS.TBL.
  54  *
  55  * Revision 1.49  1995/02/22  14:45:47  allender
  56  * remove anonymous unions from object structure
  57  *
  58  * Revision 1.48  1995/02/22  13:24:50  john
  59  * Removed the vecmat anonymous unions.
  60  *
  61  * Revision 1.47  1995/02/07  16:17:26  matt
  62  * Disabled all robot-robot collisions except those involving two green
  63  * guys.  Used to do collisions if either robot was green guy.
  64  *
  65  * Revision 1.46  1995/02/02  14:07:53  matt
  66  * Fixed confusion about which segment you are touching when you're
  67  * touching a wall.  This manifested itself in spurious lava burns.
  68  *
  69  * Revision 1.45  1995/02/02  13:45:53  matt
  70  * Made a bunch of lint-inspired changes
  71  *
  72  * Revision 1.44  1995/01/24  12:10:17  matt
  73  * Fudged collisions for player/player, and player weapon/other player in
  74  * coop games.
  75  *
  76  * Revision 1.43  1995/01/14  19:16:45  john
  77  * First version of new bitmap paging code.
  78  *
  79  * Revision 1.42  1994/12/15  12:22:40  matt
  80  * Small change which may or may not help
  81  *
  82  * Revision 1.41  1994/12/14  11:45:51  matt
  83  * Fixed (hopefully) little bug with invalid segnum
  84  *
  85  * Revision 1.40  1994/12/13  17:12:01  matt
  86  * Increased edge tolerance a bunch more
  87  *
  88  * Revision 1.39  1994/12/13  14:37:59  matt
  89  * Fixed another stupid little bug
  90  *
  91  * Revision 1.38  1994/12/13  13:25:44  matt
  92  * Increased tolerance massively to avoid catching on corners
  93  *
  94  * Revision 1.37  1994/12/13  12:02:20  matt
  95  * Fixed small bug
  96  *
  97  * Revision 1.36  1994/12/13  11:17:35  matt
  98  * Lots of changes to hopefully fix objects leaving the mine.  Note that
  99  * this code should be considered somewhat experimental - one problem I
 100  * know about is that you can get stuck on edges more easily than before.
 101  * There may be other problems I don't know about yet.
 102  *
 103  * Revision 1.35  1994/12/12  01:20:57  matt
 104  * Added hack in object-object collisions that treats claw guys as
 105  * if they have 3/4 of their actual radius.
 106  *
 107  * Revision 1.34  1994/12/04  22:48:39  matt
 108  * Physics & FVI now only build seglist for player objects, and they
 109  * responsilby deal with buffer full conditions
 110  *
 111  * Revision 1.33  1994/12/04  22:07:05  matt
 112  * Added better handing of buffer full condition
 113  *
 114  * Revision 1.32  1994/12/01  21:06:33  matt
 115  * Several important changes:
 116  *  (1) Checking against triangulated sides has been standardized a bit
 117  *  (2) Code has been added to de-triangulate some sides
 118  *  (3) BIG ONE: the tolerance for checking a point against a plane has
 119  *      been drastically relaxed
 120  *
 121  *
 122  * Revision 1.31  1994/11/27  23:15:03  matt
 123  * Made changes for new mprintf calling convention
 124  *
 125  * Revision 1.30  1994/11/19  15:20:30  mike
 126  * rip out unused code and data
 127  *
 128  * Revision 1.29  1994/11/16  12:18:17  mike
 129  * hack for green_guy:green_guy collision detection.
 130  *
 131  * Revision 1.28  1994/11/10  13:08:54  matt
 132  * Added support for new run-length-encoded bitmaps
 133  *
 134  * Revision 1.27  1994/10/31  12:27:51  matt
 135  * Added new function object_intersects_wall()
 136  *
 137  * Revision 1.26  1994/10/20  13:59:27  matt
 138  * Added assert
 139  *
 140  * Revision 1.25  1994/10/09  23:51:09  matt
 141  * Made find_hitpoint_uv() work with triangulated sides
 142  *
 143  * Revision 1.24  1994/09/25  00:39:29  matt
 144  * Took out mprintf's
 145  *
 146  * Revision 1.23  1994/09/25  00:37:53  matt
 147  * Made the 'find the point in the bitmap where something hit' system
 148  * publicly accessible.
 149  *
 150  * Revision 1.22  1994/09/21  16:58:22  matt
 151  * Fixed bug in trans wall check that was checking against verically
 152  * flipped bitmap (i.e., the y coord was negative when checking).
 153  *
 154  * Revision 1.21  1994/09/02  11:31:40  matt
 155  * Fixed object/object collisions, so you can't fly through robots anymore.
 156  * Cleaned up object damage system.
 157  *
 158  * Revision 1.20  1994/08/26  09:42:03  matt
 159  * Increased the size of a buffer
 160  *
 161  * Revision 1.19  1994/08/11  18:57:53  mike
 162  * Convert shorts to ints for optimization.
 163  *
 164  * Revision 1.18  1994/08/08  21:38:24  matt
 165  * Put in small optimization
 166  *
 167  * Revision 1.17  1994/08/08  12:21:52  yuan
 168  * Fixed assert
 169  *
 170  * Revision 1.16  1994/08/08  11:47:04  matt
 171  * Cleaned up fvi and physics a little
 172  *
 173  * Revision 1.15  1994/08/04  00:21:04  matt
 174  * Cleaned up fvi & physics error handling; put in code to make sure objects
 175  * are in correct segment; simplified segment finding for objects and points
 176  *
 177  * Revision 1.14  1994/08/02  19:04:26  matt
 178  * Cleaned up vertex list functions
 179  *
 180  * Revision 1.13  1994/08/02  09:56:28  matt
 181  * Put in check for bad value find_plane_line_intersection()
 182  *
 183  * Revision 1.12  1994/08/01  17:27:26  matt
 184  * Added support for triangulated walls in trans point check
 185  *
 186  * Revision 1.11  1994/08/01  13:30:40  matt
 187  * Made fvi() check holes in transparent walls, and changed fvi() calling
 188  * parms to take all input data in query structure.
 189  *
 190  * Revision 1.10  1994/07/13  21:47:17  matt
 191  * FVI() and physics now keep lists of segments passed through which the
 192  * trigger code uses.
 193  *
 194  * Revision 1.9  1994/07/09  21:21:40  matt
 195  * Fixed, hopefull, bugs in sphere-to-vector intersection code
 196  *
 197  * Revision 1.8  1994/07/08  14:26:42  matt
 198  * Non-needed powerups don't get picked up now; this required changing FVI to
 199  * take a list of ingore objects rather than just one ignore object.
 200  *
 201  * Revision 1.7  1994/07/06  20:02:37  matt
 202  * Made change to match gameseg that uses lowest point number as reference
 203  * point when checking against a plane
 204  *
 205  * Revision 1.6  1994/06/29  15:43:58  matt
 206  * When computing intersection of vector and sphere, use the radii of both
 207  * objects.
 208  *
 209  * Revision 1.5  1994/06/14  15:57:58  matt
 210  * Took out asserts, and added other hacks, pending real bug fixes
 211  *
 212  * Revision 1.4  1994/06/13  23:10:08  matt
 213  * Fixed problems with triangulated sides
 214  *
 215  * Revision 1.3  1994/06/09  12:11:14  matt
 216  * Fixed confusing use of two variables, hit_objnum & fvi_hit_object, to
 217  * keep the same information in different ways.
 218  *
 219  * Revision 1.2  1994/06/09  09:58:38  matt
 220  * Moved find_vector_intersection() from physics.c to new file fvi.c
 221  *
 222  * Revision 1.1  1994/06/09  09:25:57  matt
 223  * Initial revision
 224  *
 225  *
 226  */
 227
 228
 229 #define NEW_FVI_STUFF 1
 230
 231 #ifdef HAVE_CONFIG_H
 232 #include <conf.h>
 233 #endif
 234
 235 #include <stdio.h>
 236 #include <stdlib.h>
 237 #include <string.h>
 238
 239 #ifdef MACINTOSH
 240 #include <Memory.h>
 241 #endif
 242
 243 #include "pstypes.h"
 244 #include "u_mem.h"
 245 #include "error.h"
 246 #include "mono.h"
 247
 248 #include "inferno.h"
 249 #include "fvi.h"
 250 #include "segment.h"
 251 #include "object.h"
 252 #include "wall.h"
 253 #include "laser.h"
 254 #include "rle.h"
 255 #include "robot.h"
 256 #include "piggy.h"
 257 #include "player.h"
 258
 259 extern int Physics_cheat_flag;
 260
 261 #define face_type_num(nfaces,face_num,tri_edge) ((nfaces==1)?0:(tri_edge*2 + face_num))
 262
 263 #include "fvi_a.h"
 264
 265 //find the point on the specified plane where the line intersects
 266 //returns true if point found, false if line parallel to plane
 267 //new_pnt is the found point on the plane
 268 //plane_pnt & plane_norm describe the plane
 269 //p0 & p1 are the ends of the line
 270 int find_plane_line_intersection(vms_vector *new_pnt,vms_vector *plane_pnt,vms_vector *plane_norm,vms_vector *p0,vms_vector *p1,fix rad)
 271 {
 272         vms_vector d,w;
 273         fix num,den;
 274
 275         vm_vec_sub(&d,p1,p0);
 276         vm_vec_sub(&w,p0,plane_pnt);
 277
 278         num =  vm_vec_dot(plane_norm,&w);
 279         den = -vm_vec_dot(plane_norm,&d);
 280
 281 //Why does this assert hit so often
 282 //      Assert(num > -rad);
 283
 284         num -= rad;                     //move point out by rad
 285
 286         //check for various bad values
 287
 288         if ( (den==0) ||                                        //moving parallel to wall, so can't hit it
 289                   ((den>0) &&
 290                         ( (num>den) ||                          //frac greater than one
 291                      (-num>>15)>=den)) ||       //will overflow (large negative)
 292                   (den<0 && num<den))           //frac greater than one
 293                 return 0;
 294
 295 //if (num>0) {mprintf(1,"HEY! num>0 in FVI!!!"); return 0;}
 296 //??    Assert(num>=0);
 297 //    Assert(num >= den);
 298
 299         //do check for potenial overflow
 300         {
 301                 fix k;
 302
 303                 if (labs(num)/(f1_0/2) >= labs(den)) {Int3(); return 0;}
 304                 k = fixdiv(num,den);
 305
 306                 Assert(k<=f1_0);                //should be trapped above
 307
 308 //              Assert(k>=0);
 309                 if (oflow_check(d.x,k) || oflow_check(d.y,k) || oflow_check(d.z,k)) return 0;
 310                 //Note: it is ok for k to be greater than 1, since this might mean
 311                 //that an object with a non-zero radius that moved from p0 to p1
 312                 //actually hit the wall on the "other side" of p0.
 313         }
 314
 315         vm_vec_scale2(&d,num,den);
 316
 317         vm_vec_add(new_pnt,p0,&d);
 318
 319         //we should have vm_vec_scale2_add2()
 320
 321         return 1;
 322
 323 }
 324
 325 typedef struct vec2d {
 326         fix i,j;
 327 } vec2d;
 328
 329 //given largest componant of normal, return i & j
 330 //if largest componant is negative, swap i & j
 331 int ij_table[3][2] =        {
 332                                                         {2,1},          //pos x biggest
 333                                                         {0,2},          //pos y biggest
 334                                                         {1,0},          //pos z biggest
 335                                                 };
 336
 337 //intersection types
 338 #define IT_NONE 0       //doesn't touch face at all
 339 #define IT_FACE 1       //touches face
 340 #define IT_EDGE 2       //touches edge of face
 341 #define IT_POINT        3       //touches vertex
 342
 343 //see if a point in inside a face by projecting into 2d
 344 uint check_point_to_face(vms_vector *checkp, side *s,int facenum,int nv,int *vertex_list)
 345 {
 346         vms_vector_array *checkp_array;
 347         vms_vector_array norm;
 348         vms_vector t;
 349         int biggest;
 350 ///
 351         int i,j,edge;
 352         uint edgemask;
 353         fix check_i,check_j;
 354         vms_vector_array *v0,*v1;
 355
 356         #ifdef COMPACT_SEGS
 357                 get_side_normal(sp, s-sp->sides, facenum, (vms_vector *)&norm );
 358         #else
 359                 memcpy( &norm, &s->normals[facenum], sizeof(vms_vector_array));
 360         #endif
 361         checkp_array = (vms_vector_array *)checkp;
 362
 363         //now do 2d check to see if point is in side
 364
 365         //project polygon onto plane by finding largest component of normal
 366         t.x = labs(norm.xyz[0]); t.y = labs(norm.xyz[1]); t.z = labs(norm.xyz[2]);
 367
 368         if (t.x > t.y) if (t.x > t.z) biggest=0; else biggest=2;
 369         else if (t.y > t.z) biggest=1; else biggest=2;
 370
 371         if (norm.xyz[biggest] > 0) {
 372                 i = ij_table[biggest][0];
 373                 j = ij_table[biggest][1];
 374         }
 375         else {
 376                 i = ij_table[biggest][1];
 377                 j = ij_table[biggest][0];
 378         }
 379
 380         //now do the 2d problem in the i,j plane
 381
 382         check_i = checkp_array->xyz[i];
 383         check_j = checkp_array->xyz[j];
 384
 385         for (edge=edgemask=0;edge<nv;edge++) {
 386                 vec2d edgevec,checkvec;
 387                 fix d;
 388
 389                 v0 = (vms_vector_array *)&Vertices[vertex_list[facenum*3+edge]];
 390                 v1 = (vms_vector_array *)&Vertices[vertex_list[facenum*3+((edge+1)%nv)]];
 391
 392                 edgevec.i = v1->xyz[i] - v0->xyz[i];
 393                 edgevec.j = v1->xyz[j] - v0->xyz[j];
 394
 395                 checkvec.i = check_i - v0->xyz[i];
 396                 checkvec.j = check_j - v0->xyz[j];
 397
 398                 d = fixmul(checkvec.i,edgevec.j) - fixmul(checkvec.j,edgevec.i);
 399
 400                 if (d < 0)                              //we are outside of triangle
 401                         edgemask |= (1<<edge);
 402         }
 403
 404         return edgemask;
 405
 406 }
 407
 408
 409 //check if a sphere intersects a face
 410 int check_sphere_to_face(vms_vector *pnt, side *s,int facenum,int nv,fix rad,int *vertex_list)
 411 {
 412         vms_vector checkp=*pnt;
 413         uint edgemask;
 414
 415         //now do 2d check to see if point is in side
 416
 417         edgemask = check_point_to_face(pnt,s,facenum,nv,vertex_list);
 418
 419         //we've gone through all the sides, are we inside?
 420
 421         if (edgemask == 0)
 422                 return IT_FACE;
 423         else {
 424                 vms_vector edgevec,checkvec;            //this time, real 3d vectors
 425                 vms_vector closest_point;
 426                 fix edgelen,d,dist;
 427                 vms_vector *v0,*v1;
 428                 int itype;
 429                 int edgenum;
 430
 431                 //get verts for edge we're behind
 432
 433                 for (edgenum=0;!(edgemask&1);(edgemask>>=1),edgenum++);
 434
 435                 v0 = &Vertices[vertex_list[facenum*3+edgenum]];
 436                 v1 = &Vertices[vertex_list[facenum*3+((edgenum+1)%nv)]];
 437
 438                 //check if we are touching an edge or point
 439
 440                 vm_vec_sub(&checkvec,&checkp,v0);
 441                 edgelen = vm_vec_normalized_dir(&edgevec,v1,v0);
 442
 443                 //find point dist from planes of ends of edge
 444
 445                 d = vm_vec_dot(&edgevec,&checkvec);
 446
 447                 if (d+rad < 0) return IT_NONE;                  //too far behind start point
 448
 449                 if (d-rad > edgelen) return IT_NONE;    //too far part end point
 450
 451                 //find closest point on edge to check point
 452
 453                 itype = IT_POINT;
 454
 455                 if (d < 0) closest_point = *v0;
 456                 else if (d > edgelen) closest_point = *v1;
 457                 else {
 458                         itype = IT_EDGE;
 459
 460                         //vm_vec_scale(&edgevec,d);
 461                         //vm_vec_add(&closest_point,v0,&edgevec);
 462
 463                         vm_vec_scale_add(&closest_point,v0,&edgevec,d);
 464                 }
 465
 466                 dist = vm_vec_dist(&checkp,&closest_point);
 467
 468                 if (dist <= rad)
 469                         return (itype==IT_POINT)?IT_NONE:itype;
 470                 else
 471                         return IT_NONE;
 472         }
 473
 474
 475 }
 476
 477 //returns true if line intersects with face. fills in newp with intersection
 478 //point on plane, whether or not line intersects side
 479 //facenum determines which of four possible faces we have
 480 //note: the seg parm is temporary, until the face itself has a point field
 481 int check_line_to_face(vms_vector *newp,vms_vector *p0,vms_vector *p1,segment *seg,int side,int facenum,int nv,fix rad)
 482 {
 483         vms_vector checkp;
 484         int pli;
 485         struct side *s=&seg->sides[side];
 486         int vertex_list[6];
 487         int num_faces;
 488         int vertnum;
 489         vms_vector norm;
 490
 491         #ifdef COMPACT_SEGS
 492                 get_side_normal(seg, side, facenum, &norm );
 493         #else
 494                 norm = seg->sides[side].normals[facenum];
 495         #endif
 496
 497         if ((seg-Segments)==-1)
 498                 Error("segnum == -1 in check_line_to_face()");
 499
 500         create_abs_vertex_lists(&num_faces,vertex_list,seg-Segments,side);
 501
 502         //use lowest point number
 503         if (num_faces==2) {
 504                 vertnum = min(vertex_list[0],vertex_list[2]);
 505         }
 506         else {
 507                 int i;
 508                 vertnum = vertex_list[0];
 509                 for (i=1;i<4;i++)
 510                         if (vertex_list[i] < vertnum)
 511                                 vertnum = vertex_list[i];
 512         }
 513
 514         pli = find_plane_line_intersection(newp,&Vertices[vertnum],&norm,p0,p1,rad);
 515
 516         if (!pli) return IT_NONE;
 517
 518         checkp = *newp;
 519
 520         //if rad != 0, project the point down onto the plane of the polygon
 521
 522         if (rad!=0)
 523                 vm_vec_scale_add2(&checkp,&norm,-rad);
 524
 525         return check_sphere_to_face(&checkp,s,facenum,nv,rad,vertex_list);
 526
 527 }
 528
 529 //returns the value of a determinant
 530 fix calc_det_value(vms_matrix *det)
 531 {
 532         return  fixmul(det->rvec.x,fixmul(det->uvec.y,det->fvec.z)) -
 533                                 fixmul(det->rvec.x,fixmul(det->uvec.z,det->fvec.y)) -
 534                                 fixmul(det->rvec.y,fixmul(det->uvec.x,det->fvec.z)) +
 535                                 fixmul(det->rvec.y,fixmul(det->uvec.z,det->fvec.x)) +
 536                                 fixmul(det->rvec.z,fixmul(det->uvec.x,det->fvec.y)) -
 537                                 fixmul(det->rvec.z,fixmul(det->uvec.y,det->fvec.x));
 538 }
 539
 540 //computes the parameters of closest approach of two lines
 541 //fill in two parameters, t0 & t1.  returns 0 if lines are parallel, else 1
 542 int check_line_to_line(fix *t1,fix *t2,vms_vector *p1,vms_vector *v1,vms_vector *p2,vms_vector *v2)
 543 {
 544         vms_matrix det;
 545         fix d,cross_mag2;               //mag squared cross product
 546
 547         vm_vec_sub(&det.rvec,p2,p1);
 548         vm_vec_cross(&det.fvec,v1,v2);
 549         cross_mag2 = vm_vec_dot(&det.fvec,&det.fvec);
 550
 551         if (cross_mag2 == 0)
 552                 return 0;                       //lines are parallel
 553
 554         det.uvec = *v2;
 555         d = calc_det_value(&det);
 556         if (oflow_check(d,cross_mag2))
 557                 return 0;
 558         else
 559                 *t1 = fixdiv(d,cross_mag2);
 560
 561         det.uvec = *v1;
 562         d = calc_det_value(&det);
 563         if (oflow_check(d,cross_mag2))
 564                 return 0;
 565         else
 566                 *t2 = fixdiv(d,cross_mag2);
 567
 568         return 1;               //found point
 569 }
 570
 571 #ifdef NEW_FVI_STUFF
 572 int disable_new_fvi_stuff=0;
 573 #else
 574 #define disable_new_fvi_stuff 1
 575 #endif
 576
 577 //this version is for when the start and end positions both poke through
 578 //the plane of a side.  In this case, we must do checks against the edge
 579 //of faces
 580 int special_check_line_to_face(vms_vector *newp,vms_vector *p0,vms_vector *p1,segment *seg,int side,int facenum,int nv,fix rad)
 581 {
 582         vms_vector move_vec;
 583         fix edge_t,move_t,edge_t2,move_t2,closest_dist;
 584         fix edge_len,move_len;
 585         int vertex_list[6];
 586         int num_faces,edgenum;
 587         uint edgemask;
 588         vms_vector *edge_v0,*edge_v1,edge_vec;
 589         struct side *s=&seg->sides[side];
 590         vms_vector closest_point_edge,closest_point_move;
 591
 592         if (disable_new_fvi_stuff)
 593                 return check_line_to_face(newp,p0,p1,seg,side,facenum,nv,rad);
 594
 595         //calc some basic stuff
 596
 597         if ((seg-Segments)==-1)
 598                 Error("segnum == -1 in special_check_line_to_face()");
 599
 600         create_abs_vertex_lists(&num_faces,vertex_list,seg-Segments,side);
 601         vm_vec_sub(&move_vec,p1,p0);
 602
 603         //figure out which edge(s) to check against
 604
 605         edgemask = check_point_to_face(p0,s,facenum,nv,vertex_list);
 606
 607         if (edgemask == 0)
 608                 return check_line_to_face(newp,p0,p1,seg,side,facenum,nv,rad);
 609
 610         for (edgenum=0;!(edgemask&1);edgemask>>=1,edgenum++);
 611
 612         edge_v0 = &Vertices[vertex_list[facenum*3+edgenum]];
 613         edge_v1 = &Vertices[vertex_list[facenum*3+((edgenum+1)%nv)]];
 614
 615         vm_vec_sub(&edge_vec,edge_v1,edge_v0);
 616
 617         //is the start point already touching the edge?
 618
 619         //??
 620
 621         //first, find point of closest approach of vec & edge
 622
 623         edge_len = vm_vec_normalize(&edge_vec);
 624         move_len = vm_vec_normalize(&move_vec);
 625
 626         check_line_to_line(&edge_t,&move_t,edge_v0,&edge_vec,p0,&move_vec);
 627
 628         //make sure t values are in valid range
 629
 630         if (move_t<0 || move_t>move_len+rad)
 631                 return IT_NONE;
 632
 633         if (move_t > move_len)
 634                 move_t2 = move_len;
 635         else
 636                 move_t2 = move_t;
 637
 638         if (edge_t < 0)         //saturate at points
 639                 edge_t2 = 0;
 640         else
 641                 edge_t2 = edge_t;
 642
 643         if (edge_t2 > edge_len)         //saturate at points
 644                 edge_t2 = edge_len;
 645
 646         //now, edge_t & move_t determine closest points.  calculate the points.
 647
 648         vm_vec_scale_add(&closest_point_edge,edge_v0,&edge_vec,edge_t2);
 649         vm_vec_scale_add(&closest_point_move,p0,&move_vec,move_t2);
 650
 651         //find dist between closest points
 652
 653         closest_dist = vm_vec_dist(&closest_point_edge,&closest_point_move);
 654
 655         //could we hit with this dist?
 656
 657         //note massive tolerance here
 658 //      if (closest_dist < (rad*18)/20) {               //we hit.  figure out where
 659         if (closest_dist < (rad*15)/20) {               //we hit.  figure out where
 660
 661                 //now figure out where we hit
 662
 663                 vm_vec_scale_add(newp,p0,&move_vec,move_t-rad);
 664
 665                 return IT_EDGE;
 666
 667         }
 668         else
 669                 return IT_NONE;                 //no hit
 670
 671 }
 672
 673 //maybe this routine should just return the distance and let the caller
 674 //decide it it's close enough to hit
 675 //determine if and where a vector intersects with a sphere
 676 //vector defined by p0,p1
 677 //returns dist if intersects, and fills in intp
 678 //else returns 0
 679 int check_vector_to_sphere_1(vms_vector *intp,vms_vector *p0,vms_vector *p1,vms_vector *sphere_pos,fix sphere_rad)
 680 {
 681         vms_vector d,dn,w,closest_point;
 682         fix mag_d,dist,w_dist,int_dist;
 683
 684         //this routine could be optimized if it's taking too much time!
 685
 686         vm_vec_sub(&d,p1,p0);
 687         vm_vec_sub(&w,sphere_pos,p0);
 688
 689         mag_d = vm_vec_copy_normalize(&dn,&d);
 690
 691         if (mag_d == 0) {
 692                 int_dist = vm_vec_mag(&w);
 693                 *intp = *p0;
 694                 return (int_dist<sphere_rad)?int_dist:0;
 695         }
 696
 697         w_dist = vm_vec_dot(&dn,&w);
 698
 699         if (w_dist < 0)         //moving away from object
 700                  return 0;
 701
 702         if (w_dist > mag_d+sphere_rad)
 703                 return 0;               //cannot hit
 704
 705         vm_vec_scale_add(&closest_point,p0,&dn,w_dist);
 706
 707         dist = vm_vec_dist(&closest_point,sphere_pos);
 708
 709         if (dist < sphere_rad) {
 710                 fix dist2,rad2,shorten;
 711
 712                 dist2 = fixmul(dist,dist);
 713                 rad2 = fixmul(sphere_rad,sphere_rad);
 714
 715                 shorten = fix_sqrt(rad2 - dist2);
 716
 717                 int_dist = w_dist-shorten;
 718
 719                 if (int_dist > mag_d || int_dist < 0) {
 720                         //past one or the other end of vector, which means we're inside
 721
 722                         *intp = *p0;            //don't move at all
 723                         return 1;
 724                 }
 725
 726                 vm_vec_scale_add(intp,p0,&dn,int_dist);         //calc intersection point
 727
 728 //              {
 729 //                      fix dd = vm_vec_dist(intp,sphere_pos);
 730 //                      Assert(dd == sphere_rad);
 731 //                      mprintf(0,"dd=%x, rad=%x, delta=%x\n",dd,sphere_rad,dd-sphere_rad);
 732 //              }
 733
 734
 735                 return int_dist;
 736         }
 737         else
 738                 return 0;
 739 }
 740
 741 /*
 742 //$$fix get_sphere_int_dist(vms_vector *w,fix dist,fix rad);
 743 //$$
 744 //$$#pragma aux get_sphere_int_dist parm [esi] [ebx] [ecx] value [eax] modify exact [eax ebx ecx edx] = \
 745 //$$    "mov eax,ebx"           \
 746 //$$    "imul eax"                      \
 747 //$$                                                    \
 748 //$$    "mov ebx,eax"           \
 749 //$$   "mov eax,ecx"            \
 750 //$$    "mov ecx,edx"           \
 751 //$$                                                    \
 752 //$$    "imul eax"                      \
 753 //$$                                                    \
 754 //$$    "sub eax,ebx"           \
 755 //$$    "sbb edx,ecx"           \
 756 //$$                                                    \
 757 //$$    "call quad_sqrt"        \
 758 //$$                                                    \
 759 //$$    "push eax"                      \
 760 //$$                                                    \
 761 //$$    "push ebx"                      \
 762 //$$    "push ecx"                      \
 763 //$$                                                    \
 764 //$$    "mov eax,[esi]" \
 765 //$$    "imul eax"                      \
 766 //$$    "mov ebx,eax"           \
 767 //$$    "mov ecx,edx"           \
 768 //$$    "mov eax,4[esi]"        \
 769 //$$    "imul eax"                      \
 770 //$$    "add ebx,eax"           \
 771 //$$    "adc ecx,edx"           \
 772 //$$    "mov eax,8[esi]"        \
 773 //$$    "imul eax"                      \
 774 //$$    "add eax,ebx"           \
 775 //$$    "adc edx,ecx"           \
 776 //$$                                                    \
 777 //$$    "pop ecx"                       \
 778 //$$    "pop ebx"                       \
 779 //$$                                                    \
 780 //$$    "sub eax,ebx"           \
 781 //$$    "sbb edx,ecx"           \
 782 //$$                                                    \
 783 //$$    "call quad_sqrt"        \
 784 //$$                                                    \
 785 //$$    "pop ebx"                       \
 786 //$$    "sub eax,ebx";
 787 //$$
 788 //$$
 789 //$$//determine if and where a vector intersects with a sphere
 790 //$$//vector defined by p0,p1
 791 //$$//returns dist if intersects, and fills in intp. if no intersect, return 0
 792 //$$fix check_vector_to_sphere_2(vms_vector *intp,vms_vector *p0,vms_vector *p1,vms_vector *sphere_pos,fix sphere_rad)
 793 //$${
 794 //$$    vms_vector d,w,c;
 795 //$$    fix mag_d,dist,mag_c,mag_w;
 796 //$$    vms_vector wn,dn;
 797 //$$
 798 //$$    vm_vec_sub(&d,p1,p0);
 799 //$$    vm_vec_sub(&w,sphere_pos,p0);
 800 //$$
 801 //$$    //wn = w; mag_w = vm_vec_normalize(&wn);
 802 //$$    //dn = d; mag_d = vm_vec_normalize(&dn);
 803 //$$
 804 //$$    mag_w = vm_vec_copy_normalize(&wn,&w);
 805 //$$    mag_d = vm_vec_copy_normalize(&dn,&d);
 806 //$$
 807 //$$    //vm_vec_cross(&c,&w,&d);
 808 //$$    vm_vec_cross(&c,&wn,&dn);
 809 //$$
 810 //$$    mag_c = vm_vec_mag(&c);
 811 //$$    //mag_d = vm_vec_mag(&d);
 812 //$$
 813 //$$    //dist = fixdiv(mag_c,mag_d);
 814 //$$
 815 //$$dist = fixmul(mag_c,mag_w);
 816 //$$
 817 //$$    if (dist < sphere_rad) {        //we intersect.  find point of intersection
 818 //$$            fix int_dist;                   //length of vector to intersection point
 819 //$$            fix k;                                  //portion of p0p1 we want
 820 //$$//@@                fix dist2,rad2,shorten,mag_w2;
 821 //$$
 822 //$$//@@                mag_w2 = vm_vec_dot(&w,&w);     //the square of the magnitude
 823 //$$//@@                //WHAT ABOUT OVERFLOW???
 824 //$$//@@                dist2 = fixmul(dist,dist);
 825 //$$//@@                rad2 = fixmul(sphere_rad,sphere_rad);
 826 //$$//@@                shorten = fix_sqrt(rad2 - dist2);
 827 //$$//@@                int_dist = fix_sqrt(mag_w2 - dist2) - shorten;
 828 //$$
 829 //$$            int_dist = get_sphere_int_dist(&w,dist,sphere_rad);
 830 //$$
 831 //$$if (labs(int_dist) > mag_d) //I don't know why this would happen
 832 //$$    if (int_dist > 0)
 833 //$$            k = f1_0;
 834 //$$    else
 835 //$$            k = -f1_0;
 836 //$$else
 837 //$$            k = fixdiv(int_dist,mag_d);
 838 //$$
 839 //$$//          vm_vec_scale(&d,k);                     //vec from p0 to intersection point
 840 //$$//          vm_vec_add(intp,p0,&d);         //intersection point
 841 //$$            vm_vec_scale_add(intp,p0,&d,k); //calc new intersection point
 842 //$$
 843 //$$            return int_dist;
 844 //$$    }
 845 //$$    else
 846 //$$            return 0;       //no intersection
 847 //$$}
 848 */
 849
 850 //determine if a vector intersects with an object
 851 //if no intersects, returns 0, else fills in intp and returns dist
 852 fix check_vector_to_object(vms_vector *intp,vms_vector *p0,vms_vector *p1,fix rad,object *obj,object *otherobj)
 853 {
 854         fix size = obj->size;
 855
 856         if (obj->type == OBJ_ROBOT && Robot_info[obj->id].attack_type)
 857                 size = (size*3)/4;
 858
 859         //if obj is player, and bumping into other player or a weapon of another coop player, reduce radius
 860         if (obj->type == OBJ_PLAYER &&
 861                         ((otherobj->type == OBJ_PLAYER) ||
 862                         ((Game_mode&GM_MULTI_COOP) && otherobj->type == OBJ_WEAPON && otherobj->ctype.laser_info.parent_type == OBJ_PLAYER)))
 863                 size = size/2;
 864
 865         return check_vector_to_sphere_1(intp,p0,p1,&obj->pos,size+rad);
 866
 867 }
 868
 869
 870 #define MAX_SEGS_VISITED 100
 871 int n_segs_visited;
 872 short segs_visited[MAX_SEGS_VISITED];
 873
 874 int fvi_nest_count;
 875
 876 //these vars are used to pass vars from fvi_sub() to find_vector_intersection()
 877 int fvi_hit_object;     // object number of object hit in last find_vector_intersection call.
 878 int fvi_hit_seg;                // what segment the hit point is in
 879 int fvi_hit_side;               // what side was hit
 880 int fvi_hit_side_seg;// what seg the hitside is in
 881 vms_vector wall_norm;   //ptr to surface normal of hit wall
 882 int fvi_hit_seg2;               // what segment the hit point is in
 883
 884 int fvi_sub(vms_vector *intp,int *ints,vms_vector *p0,int startseg,vms_vector *p1,fix rad,short thisobjnum,int *ignore_obj_list,int flags,int *seglist,int *n_segs,int entry_seg);
 885
 886 //What the hell is fvi_hit_seg for???
 887
 888 //Find out if a vector intersects with anything.
 889 //Fills in hit_data, an fvi_info structure (see header file).
 890 //Parms:
 891 //  p0 & startseg       describe the start of the vector
 892 //  p1                                  the end of the vector
 893 //  rad                                         the radius of the cylinder
 894 //  thisobjnum          used to prevent an object with colliding with itself
 895 //  ingore_obj                  ignore collisions with this object
 896 //  check_obj_flag      determines whether collisions with objects are checked
 897 //Returns the hit_data->hit_type
 898 int find_vector_intersection(fvi_query *fq,fvi_info *hit_data)
 899 {
 900         int hit_type,hit_seg,hit_seg2;
 901         vms_vector hit_pnt;
 902         int i;
 903
 904         Assert(fq->ignore_obj_list != (int *)(-1));
 905         Assert((fq->startseg <= Highest_segment_index) && (fq->startseg >= 0));
 906
 907         fvi_hit_seg = -1;
 908         fvi_hit_side = -1;
 909
 910         fvi_hit_object = -1;
 911
 912         //check to make sure start point is in seg its supposed to be in
 913         //Assert(check_point_in_seg(p0,startseg,0).centermask==0);      //start point not in seg
 914
 915         // Viewer is not in segment as claimed, so say there is no hit.
 916         if(!(get_seg_masks(fq->p0,fq->startseg,0).centermask==0)) {
 917
 918                 hit_data->hit_type = HIT_BAD_P0;
 919                 hit_data->hit_pnt = *fq->p0;
 920                 hit_data->hit_seg = fq->startseg;
 921                 hit_data->hit_side = hit_data->hit_object = 0;
 922                 hit_data->hit_side_seg = -1;
 923
 924                 return hit_data->hit_type;
 925         }
 926
 927         segs_visited[0] = fq->startseg;
 928
 929         n_segs_visited=1;
 930
 931         fvi_nest_count = 0;
 932
 933         hit_seg2 = fvi_hit_seg2 = -1;
 934
 935         hit_type = fvi_sub(&hit_pnt,&hit_seg2,fq->p0,fq->startseg,fq->p1,fq->rad,fq->thisobjnum,fq->ignore_obj_list,fq->flags,hit_data->seglist,&hit_data->n_segs,-2);
 936         //!!hit_seg = find_point_seg(&hit_pnt,fq->startseg);
 937         if (hit_seg2!=-1 && !get_seg_masks(&hit_pnt,hit_seg2,0).centermask)
 938                 hit_seg = hit_seg2;
 939         else
 940                 hit_seg = find_point_seg(&hit_pnt,fq->startseg);
 941
 942 //MATT: TAKE OUT THIS HACK AND FIX THE BUGS!
 943         if (hit_type == HIT_WALL && hit_seg==-1)
 944                 if (fvi_hit_seg2!=-1 && get_seg_masks(&hit_pnt,fvi_hit_seg2,0).centermask==0)
 945                         hit_seg = fvi_hit_seg2;
 946
 947         if (hit_seg == -1) {
 948                 int new_hit_type;
 949                 int new_hit_seg2=-1;
 950                 vms_vector new_hit_pnt;
 951
 952                 //because of code that deal with object with non-zero radius has
 953                 //problems, try using zero radius and see if we hit a wall
 954
 955                 new_hit_type = fvi_sub(&new_hit_pnt,&new_hit_seg2,fq->p0,fq->startseg,fq->p1,0,fq->thisobjnum,fq->ignore_obj_list,fq->flags,hit_data->seglist,&hit_data->n_segs,-2);
 956
 957                 if (new_hit_seg2 != -1) {
 958                         hit_seg = new_hit_seg2;
 959                         hit_pnt = new_hit_pnt;
 960                 }
 961         }
 962
 963
 964 if (hit_seg!=-1 && fq->flags&FQ_GET_SEGLIST)
 965         if (hit_seg != hit_data->seglist[hit_data->n_segs-1] && hit_data->n_segs<MAX_FVI_SEGS-1)
 966                 hit_data->seglist[hit_data->n_segs++] = hit_seg;
 967
 968 if (hit_seg!=-1 && fq->flags&FQ_GET_SEGLIST)
 969         for (i=0;i<hit_data->n_segs && i<MAX_FVI_SEGS-1;i++)
 970                 if (hit_data->seglist[i] == hit_seg) {
 971                         hit_data->n_segs = i+1;
 972                         break;
 973                 }
 974
 975 //I'm sorry to say that sometimes the seglist isn't correct.  I did my
 976 //best.  Really.
 977
 978
 979 //{     //verify hit list
 980 //
 981 //      int i,ch;
 982 //
 983 //      Assert(hit_data->seglist[0] == startseg);
 984 //
 985 //      for (i=0;i<hit_data->n_segs-1;i++) {
 986 //              for (ch=0;ch<6;ch++)
 987 //                      if (Segments[hit_data->seglist[i]].children[ch] == hit_data->seglist[i+1])
 988 //                              break;
 989 //              Assert(ch<6);
 990 //      }
 991 //
 992 //      Assert(hit_data->seglist[hit_data->n_segs-1] == hit_seg);
 993 //}
 994
 995
 996 //MATT: PUT THESE ASSERTS BACK IN AND FIX THE BUGS!
 997 //!!    Assert(hit_seg!=-1);
 998 //!!    Assert(!((hit_type==HIT_WALL) && (hit_seg == -1)));
 999         //When this assert happens, get Matt.  Matt:  Look at hit_seg2 &
1000         //fvi_hit_seg.  At least one of these should be set.  Why didn't
1001         //find_new_seg() find something?
1002
1003 //      Assert(fvi_hit_seg==-1 || fvi_hit_seg == hit_seg);
1004
1005         Assert(!(hit_type==HIT_OBJECT && fvi_hit_object==-1));
1006
1007         hit_data->hit_type              = hit_type;
1008         hit_data->hit_pnt               = hit_pnt;
1009         hit_data->hit_seg               = hit_seg;
1010         hit_data->hit_side              = fvi_hit_side; //looks at global
1011         hit_data->hit_side_seg  = fvi_hit_side_seg;     //looks at global
1012         hit_data->hit_object            = fvi_hit_object;       //looks at global
1013         hit_data->hit_wallnorm  = wall_norm;            //looks at global
1014
1015 //      if(hit_seg!=-1 && get_seg_masks(&hit_data->hit_pnt,hit_data->hit_seg,0).centermask!=0)
1016 //              Int3();
1017
1018         return hit_type;
1019
1020 }
1021
1022 //--unused-- fix check_dist(vms_vector *v0,vms_vector *v1)
1023 //--unused-- {
1024 //--unused--    return vm_vec_dist(v0,v1);
1025 //--unused-- }
1026
1027 int obj_in_list(int objnum,int *obj_list)
1028 {
1029         int t;
1030
1031         while ((t=*obj_list)!=-1 && t!=objnum) obj_list++;
1032
1033         return (t==objnum);
1034
1035 }
1036
1037 int check_trans_wall(vms_vector *pnt,segment *seg,int sidenum,int facenum);
1038
1039 int fvi_sub(vms_vector *intp,int *ints,vms_vector *p0,int startseg,vms_vector *p1,fix rad,short thisobjnum,int *ignore_obj_list,int flags,int *seglist,int *n_segs,int entry_seg)
1040 {
1041         segment *seg;                           //the segment we're looking at
1042         int startmask,endmask;  //mask of faces
1043         //@@int sidemask;                               //mask of sides - can be on back of face but not side
1044         int centermask;                 //where the center point is
1045         int objnum;
1046         segmasks masks;
1047         vms_vector hit_point,closest_hit_point;         //where we hit
1048         fix d,closest_d=0x7fffffff;                                     //distance to hit point
1049         int hit_type=HIT_NONE;                                                  //what sort of hit
1050         int hit_seg=-1;
1051         int hit_none_seg=-1;
1052         int hit_none_n_segs=0;
1053         int hit_none_seglist[MAX_FVI_SEGS];
1054         int cur_nest_level = fvi_nest_count;
1055
1056         //fvi_hit_object = -1;
1057
1058         if (flags&FQ_GET_SEGLIST)
1059                 *seglist = startseg;
1060         *n_segs=1;
1061
1062         seg = &Segments[startseg];
1063
1064         fvi_nest_count++;
1065
1066         //first, see if vector hit any objects in this segment
1067         if (flags & FQ_CHECK_OBJS)
1068                 for (objnum=seg->objects;objnum!=-1;objnum=Objects[objnum].next)
1069                         if (    !(Objects[objnum].flags & OF_SHOULD_BE_DEAD) &&
1070                                         !(thisobjnum == objnum ) &&
1071                                         (ignore_obj_list==NULL || !obj_in_list(objnum,ignore_obj_list)) &&
1072                                         !laser_are_related( objnum, thisobjnum ) &&
1073                                         !((thisobjnum  > -1)    &&
1074                                                 (CollisionResult[Objects[thisobjnum].type][Objects[objnum].type] == RESULT_NOTHING ) &&
1075                                                 (CollisionResult[Objects[objnum].type][Objects[thisobjnum].type] == RESULT_NOTHING ))) {
1076                                 int fudged_rad = rad;
1077
1078                                 //      If this is a powerup, don't do collision if flag FQ_IGNORE_POWERUPS is set
1079                                 if (Objects[objnum].type == OBJ_POWERUP)
1080                                         if (flags & FQ_IGNORE_POWERUPS)
1081                                                 continue;
1082
1083                                 //      If this is a robot:robot collision, only do it if both of them have attack_type != 0 (eg, green guy)
1084                                 if (Objects[thisobjnum].type == OBJ_ROBOT)
1085                                         if (Objects[objnum].type == OBJ_ROBOT)
1086                                                 // -- MK: 11/18/95, 4claws glomming together...this is easy.  -- if (!(Robot_info[Objects[objnum].id].attack_type && Robot_info[Objects[thisobjnum].id].attack_type))
1087                                                         continue;
1088
1089                                 if (Objects[thisobjnum].type == OBJ_ROBOT && Robot_info[Objects[thisobjnum].id].attack_type)
1090                                         fudged_rad = (rad*3)/4;
1091
1092                                 //if obj is player, and bumping into other player or a weapon of another coop player, reduce radius
1093                                 if (Objects[thisobjnum].type == OBJ_PLAYER &&
1094                                                 ((Objects[objnum].type == OBJ_PLAYER) ||
1095                                                 ((Game_mode&GM_MULTI_COOP) &&  Objects[objnum].type == OBJ_WEAPON && Objects[objnum].ctype.laser_info.parent_type == OBJ_PLAYER)))
1096                                         fudged_rad = rad/2;     //(rad*3)/4;
1097
1098                                 d = check_vector_to_object(&hit_point,p0,p1,fudged_rad,&Objects[objnum],&Objects[thisobjnum]);
1099
1100                                 if (d)          //we have intersection
1101                                         if (d < closest_d) {
1102                                                 fvi_hit_object = objnum;
1103                                                 Assert(fvi_hit_object!=-1);
1104                                                 closest_d = d;
1105                                                 closest_hit_point = hit_point;
1106                                                 hit_type=HIT_OBJECT;
1107                                         }
1108                         }
1109
1110         if (    (thisobjnum > -1 ) && (CollisionResult[Objects[thisobjnum].type][OBJ_WALL] == RESULT_NOTHING ) )
1111                 rad = 0;                //HACK - ignore when edges hit walls
1112
1113         //now, check segment walls
1114
1115         startmask = get_seg_masks(p0,startseg,rad).facemask;
1116
1117         masks = get_seg_masks(p1,startseg,rad);    //on back of which faces?
1118         endmask = masks.facemask;
1119         //@@sidemask = masks.sidemask;
1120         centermask = masks.centermask;
1121
1122         if (centermask==0) hit_none_seg = startseg;
1123
1124         if (endmask != 0) {                             //on the back of at least one face
1125
1126                 int side,bit,face;
1127
1128                 //for each face we are on the back of, check if intersected
1129
1130                 for (side=0,bit=1;side<6 && endmask>=bit;side++) {
1131                         int num_faces;
1132                         num_faces = get_num_faces(&seg->sides[side]);
1133
1134                         if (num_faces == 0)
1135                                 num_faces = 1;
1136
1137                         // commented out by mk on 02/13/94:: if ((num_faces=seg->sides[side].num_faces)==0) num_faces=1;
1138
1139                         for (face=0;face<2;face++,bit<<=1) {
1140
1141                                 if (endmask & bit) {            //on the back of this face
1142                                         int face_hit_type;      //in what way did we hit the face?
1143
1144
1145                                         if (seg->children[side] == entry_seg)
1146                                                 continue;               //don't go back through entry side
1147
1148                                         //did we go through this wall/door?
1149
1150                                         //#ifdef NEW_FVI_STUFF
1151                                         if (startmask & bit)            //start was also though.  Do extra check
1152                                                 face_hit_type = special_check_line_to_face( &hit_point,
1153                                                                                 p0,p1,seg,side,
1154                                                                                 face,
1155                                                                                 ((num_faces==1)?4:3),rad);
1156                                         else
1157                                         //#endif
1158                                                 //NOTE LINK TO ABOVE!!
1159                                                 face_hit_type = check_line_to_face( &hit_point,
1160                                                                                 p0,p1,seg,side,
1161                                                                                 face,
1162                                                                                 ((num_faces==1)?4:3),rad);
1163
1164
1165                                         if (face_hit_type) {            //through this wall/door
1166                                                 int wid_flag;
1167
1168                                                 //if what we have hit is a door, check the adjoining seg
1169
1170                                                 if ( (thisobjnum == Players[Player_num].objnum) && (Physics_cheat_flag==0xBADA55) )     {
1171                                                         wid_flag = WALL_IS_DOORWAY(seg, side);
1172                                                         if (seg->children[side] >= 0 )
1173                                                                 wid_flag |= WID_FLY_FLAG;
1174                                                 } else {
1175                                                         wid_flag = WALL_IS_DOORWAY(seg, side);
1176                                                 }
1177
1178                                                 if ((wid_flag & WID_FLY_FLAG) ||
1179                                                         (((wid_flag & WID_RENDER_FLAG) && (wid_flag & WID_RENDPAST_FLAG)) &&
1180                                                                 ((flags & FQ_TRANSWALL) || (flags & FQ_TRANSPOINT && check_trans_wall(&hit_point,seg,side,face))))) {
1181
1182                                                         int newsegnum;
1183                                                         vms_vector sub_hit_point;
1184                                                         int sub_hit_type,sub_hit_seg;
1185                                                         vms_vector save_wall_norm = wall_norm;
1186                                                         int save_hit_objnum=fvi_hit_object;
1187                                                         int i;
1188
1189                                                         //do the check recursively on the next seg.
1190
1191                                                         newsegnum = seg->children[side];
1192
1193                                                         for (i=0;i<n_segs_visited && newsegnum!=segs_visited[i];i++);
1194
1195                                                         if (i==n_segs_visited) {                //haven't visited here yet
1196                                                                 int temp_seglist[MAX_FVI_SEGS],temp_n_segs;
1197
1198                                                                 segs_visited[n_segs_visited++] = newsegnum;
1199
1200                                                                 if (n_segs_visited >= MAX_SEGS_VISITED)
1201                                                                         goto quit_looking;              //we've looked a long time, so give up
1202
1203                                                                 sub_hit_type = fvi_sub(&sub_hit_point,&sub_hit_seg,p0,newsegnum,p1,rad,thisobjnum,ignore_obj_list,flags,temp_seglist,&temp_n_segs,startseg);
1204
1205                                                                 if (sub_hit_type != HIT_NONE) {
1206
1207                                                                         d = vm_vec_dist(&sub_hit_point,p0);
1208
1209                                                                         if (d < closest_d) {
1210
1211                                                                                 closest_d = d;
1212                                                                                 closest_hit_point = sub_hit_point;
1213                                                                                 hit_type = sub_hit_type;
1214                                                                                 if (sub_hit_seg!=-1) hit_seg = sub_hit_seg;
1215
1216                                                                                 //copy seglist
1217                                                                                 if (flags&FQ_GET_SEGLIST) {
1218                                                                                         int ii;
1219                                                                                         for (ii=0;i<temp_n_segs && *n_segs<MAX_FVI_SEGS-1;)
1220                                                                                                 seglist[(*n_segs)++] = temp_seglist[ii++];
1221                                                                                 }
1222
1223                                                                                 Assert(*n_segs < MAX_FVI_SEGS);
1224                                                                         }
1225                                                                         else {
1226                                                                                 wall_norm = save_wall_norm;     //global could be trashed
1227                                                                                 fvi_hit_object = save_hit_objnum;
1228                                                                         }
1229
1230                                                                 }
1231                                                                 else {
1232                                                                         wall_norm = save_wall_norm;     //global could be trashed
1233                                                                         if (sub_hit_seg!=-1) hit_none_seg = sub_hit_seg;
1234                                                                         //copy seglist
1235                                                                         if (flags&FQ_GET_SEGLIST) {
1236                                                                                 int ii;
1237                                                                                 for (ii=0;ii<temp_n_segs && ii<MAX_FVI_SEGS-1;ii++)
1238                                                                                         hit_none_seglist[ii] = temp_seglist[ii];
1239                                                                         }
1240                                                                         hit_none_n_segs = temp_n_segs;
1241                                                                 }
1242                                                         }
1243                                                 }
1244                                                 else {          //a wall
1245
1246                                                                 //is this the closest hit?
1247
1248                                                                 d = vm_vec_dist(&hit_point,p0);
1249
1250                                                                 if (d < closest_d) {
1251                                                                         closest_d = d;
1252                                                                         closest_hit_point = hit_point;
1253                                                                         hit_type = HIT_WALL;
1254
1255                                                                         #ifdef COMPACT_SEGS
1256                                                                                 get_side_normal(seg, side, face, &wall_norm );
1257                                                                         #else
1258                                                                                 wall_norm = seg->sides[side].normals[face];
1259                                                                         #endif
1260
1261
1262                                                                         if (get_seg_masks(&hit_point,startseg,rad).centermask==0)
1263                                                                                 hit_seg = startseg;             //hit in this segment
1264                                                                         else
1265                                                                                 fvi_hit_seg2 = startseg;
1266
1267                                                                         //@@else         {
1268                                                                         //@@    mprintf( 0, "Warning on line 991 in physics.c\n" );
1269                                                                         //@@    hit_seg = startseg;             //hit in this segment
1270                                                                         //@@    //Int3();
1271                                                                         //@@}
1272
1273                                                                         fvi_hit_seg = hit_seg;
1274                                                                         fvi_hit_side =  side;
1275                                                                         fvi_hit_side_seg = startseg;
1276
1277                                                                 }
1278                                                 }
1279                                         }
1280                                 }
1281                         }
1282                 }
1283         }
1284
1285 //      Assert(centermask==0 || hit_seg!=startseg);
1286
1287 //      Assert(sidemask==0);            //Error("Didn't find side we went though");
1288
1289 quit_looking:
1290         ;
1291
1292         if (hit_type == HIT_NONE) {     //didn't hit anything, return end point
1293                 int i;
1294
1295                 *intp = *p1;
1296                 *ints = hit_none_seg;
1297                 //MATT: MUST FIX THIS!!!!
1298                 //Assert(!centermask);
1299
1300                 if (hit_none_seg!=-1) {                 ///(centermask == 0)
1301                         if (flags&FQ_GET_SEGLIST)
1302                                 //copy seglist
1303                                 for (i=0;i<hit_none_n_segs && *n_segs<MAX_FVI_SEGS-1;)
1304                                         seglist[(*n_segs)++] = hit_none_seglist[i++];
1305                 }
1306                 else
1307                         if (cur_nest_level!=0)
1308                                 *n_segs=0;
1309
1310         }
1311         else {
1312                 *intp = closest_hit_point;
1313                 if (hit_seg==-1)
1314                         if (fvi_hit_seg2 != -1)
1315                                 *ints = fvi_hit_seg2;
1316                         else
1317                                 *ints = hit_none_seg;
1318                 else
1319                         *ints = hit_seg;
1320         }
1321
1322         Assert(!(hit_type==HIT_OBJECT && fvi_hit_object==-1));
1323
1324         return hit_type;
1325
1326 }
1327
1328 /*
1329 //--unused-- //compute the magnitude of a 2d vector
1330 //--unused-- fix mag2d(vec2d *v);
1331 //--unused-- #pragma aux mag2d parm [esi] value [eax] modify exact [eax ebx ecx edx] = \
1332 //--unused--    "mov    eax,[esi]"              \
1333 //--unused--    "imul   eax"                            \
1334 //--unused--    "mov    ebx,eax"                        \
1335 //--unused--    "mov    ecx,edx"                        \
1336 //--unused--    "mov    eax,4[esi]"             \
1337 //--unused--    "imul   eax"                            \
1338 //--unused--    "add    eax,ebx"                        \
1339 //--unused--    "adc    edx,ecx"                        \
1340 //--unused--    "call   quad_sqrt";
1341 */
1342
1343 //--unused-- //returns mag
1344 //--unused-- fix normalize_2d(vec2d *v)
1345 //--unused-- {
1346 //--unused--    fix mag;
1347 //--unused--
1348 //--unused--    mag = mag2d(v);
1349 //--unused--
1350 //--unused--    v->i = fixdiv(v->i,mag);
1351 //--unused--    v->j = fixdiv(v->j,mag);
1352 //--unused--
1353 //--unused--    return mag;
1354 //--unused-- }
1355
1356 #include "textures.h"
1357 #include "texmerge.h"
1358
1359 #define cross(v0,v1) (fixmul((v0)->i,(v1)->j) - fixmul((v0)->j,(v1)->i))
1360
1361 //finds the uv coords of the given point on the given seg & side
1362 //fills in u & v. if l is non-NULL fills it in also
1363 void find_hitpoint_uv(fix *u,fix *v,fix *l,vms_vector *pnt,segment *seg,int sidenum,int facenum)
1364 {
1365         vms_vector_array *pnt_array;
1366         vms_vector_array normal_array;
1367         int segnum = seg-Segments;
1368         int num_faces;
1369         int biggest,ii,jj;
1370         side *side = &seg->sides[sidenum];
1371         int vertex_list[6],vertnum_list[6];
1372         vec2d p1,vec0,vec1,checkp;      //@@,checkv;
1373         uvl uvls[3];
1374         fix k0,k1;
1375         int i;
1376
1377         //mprintf(0,"\ncheck_trans_wall  vec=%x,%x,%x\n",pnt->x,pnt->y,pnt->z);
1378
1379         //do lasers pass through illusory walls?
1380
1381         //when do I return 0 & 1 for non-transparent walls?
1382
1383         if (segnum < 0 || segnum > Highest_segment_index) {
1384                 mprintf((0,"Bad segnum (%d) in find_hitpoint_uv()\n",segnum));
1385                 *u = *v = 0;
1386                 return;
1387         }
1388
1389         if (segnum==-1)
1390                 Error("segnum == -1 in find_hitpoint_uv()");
1391
1392         create_abs_vertex_lists(&num_faces,vertex_list,segnum,sidenum);
1393         create_all_vertnum_lists(&num_faces,vertnum_list,segnum,sidenum);
1394
1395         //now the hard work.
1396
1397         //1. find what plane to project this wall onto to make it a 2d case
1398
1399         #ifdef COMPACT_SEGS
1400                 get_side_normal(seg, sidenum, facenum, (vms_vector *)&normal_array );
1401         #else
1402                 memcpy( &normal_array, &side->normals[facenum], sizeof(vms_vector_array) );
1403         #endif
1404         biggest = 0;
1405
1406         if (abs(normal_array.xyz[1]) > abs(normal_array.xyz[biggest])) biggest = 1;
1407         if (abs(normal_array.xyz[2]) > abs(normal_array.xyz[biggest])) biggest = 2;
1408
1409         if (biggest == 0) ii=1; else ii=0;
1410         if (biggest == 2) jj=1; else jj=2;
1411
1412         //2. compute u,v of intersection point
1413
1414         //vec from 1 -> 0
1415         pnt_array = (vms_vector_array *)&Vertices[vertex_list[facenum*3+1]];
1416         p1.i = pnt_array->xyz[ii];
1417         p1.j = pnt_array->xyz[jj];
1418
1419         pnt_array = (vms_vector_array *)&Vertices[vertex_list[facenum*3+0]];
1420         vec0.i = pnt_array->xyz[ii] - p1.i;
1421         vec0.j = pnt_array->xyz[jj] - p1.j;
1422
1423         //vec from 1 -> 2
1424         pnt_array = (vms_vector_array *)&Vertices[vertex_list[facenum*3+2]];
1425         vec1.i = pnt_array->xyz[ii] - p1.i;
1426         vec1.j = pnt_array->xyz[jj] - p1.j;
1427
1428         //vec from 1 -> checkpoint
1429         pnt_array = (vms_vector_array *)pnt;
1430         checkp.i = pnt_array->xyz[ii];
1431         checkp.j = pnt_array->xyz[jj];
1432
1433         //@@checkv.i = checkp.i - p1.i;
1434         //@@checkv.j = checkp.j - p1.j;
1435
1436         //mprintf(0," vec0   = %x,%x  ",vec0.i,vec0.j);
1437         //mprintf(0," vec1   = %x,%x  ",vec1.i,vec1.j);
1438         //mprintf(0," checkv = %x,%x\n",checkv.i,checkv.j);
1439
1440         k1 = -fixdiv(cross(&checkp,&vec0) + cross(&vec0,&p1),cross(&vec0,&vec1));
1441         if (abs(vec0.i) > abs(vec0.j))
1442                 k0 = fixdiv(fixmul(-k1,vec1.i) + checkp.i - p1.i,vec0.i);
1443         else
1444                 k0 = fixdiv(fixmul(-k1,vec1.j) + checkp.j - p1.j,vec0.j);
1445
1446         //mprintf(0," k0,k1  = %x,%x\n",k0,k1);
1447
1448         for (i=0;i<3;i++)
1449                 uvls[i] = side->uvls[vertnum_list[facenum*3+i]];
1450
1451         *u = uvls[1].u + fixmul( k0,uvls[0].u - uvls[1].u) + fixmul(k1,uvls[2].u - uvls[1].u);
1452         *v = uvls[1].v + fixmul( k0,uvls[0].v - uvls[1].v) + fixmul(k1,uvls[2].v - uvls[1].v);
1453
1454         if (l)
1455                 *l = uvls[1].l + fixmul( k0,uvls[0].l - uvls[1].l) + fixmul(k1,uvls[2].l - uvls[1].l);
1456
1457         //mprintf(0," u,v    = %x,%x\n",*u,*v);
1458 }
1459
1460 //check if a particular point on a wall is a transparent pixel
1461 //returns 1 if can pass though the wall, else 0
1462 int check_trans_wall(vms_vector *pnt,segment *seg,int sidenum,int facenum)
1463 {
1464         grs_bitmap *bm;
1465         side *side = &seg->sides[sidenum];
1466         int bmx,bmy;
1467         fix u,v;
1468
1469 //      Assert(WALL_IS_DOORWAY(seg,sidenum) == WID_TRANSPARENT_WALL);
1470
1471         find_hitpoint_uv(&u,&v,NULL,pnt,seg,sidenum,facenum);   //      Don't compute light value.
1472
1473         if (side->tmap_num2 != 0)       {
1474                 bm = texmerge_get_cached_bitmap( side->tmap_num, side->tmap_num2 );
1475         } else {
1476                 bm = &GameBitmaps[Textures[side->tmap_num].index];
1477                 PIGGY_PAGE_IN( Textures[side->tmap_num] );
1478         }
1479
1480         if (bm->bm_flags & BM_FLAG_RLE)
1481                 bm = rle_expand_texture(bm);
1482
1483         bmx = ((unsigned) f2i(u*bm->bm_w)) % bm->bm_w;
1484         bmy = ((unsigned) f2i(v*bm->bm_h)) % bm->bm_h;
1485
1486 //note: the line above had -v, but that was wrong, so I changed it.  if
1487 //something doesn't work, and you want to make it negative again, you
1488 //should figure out what's going on.
1489
1490         //mprintf(0," bmx,y  = %d,%d, color=%x\n",bmx,bmy,bm->bm_data[bmy*64+bmx]);
1491
1492         return (bm->bm_data[bmy*bm->bm_w+bmx] == TRANSPARENCY_COLOR);
1493 }
1494
1495 //new function for Mike
1496 //note: n_segs_visited must be set to zero before this is called
1497 int sphere_intersects_wall(vms_vector *pnt,int segnum,fix rad)
1498 {
1499         int facemask;
1500         segment *seg;
1501
1502         segs_visited[n_segs_visited++] = segnum;
1503
1504         facemask = get_seg_masks(pnt,segnum,rad).facemask;
1505
1506         seg = &Segments[segnum];
1507
1508         if (facemask != 0) {                            //on the back of at least one face
1509
1510                 int side,bit,face;
1511
1512                 //for each face we are on the back of, check if intersected
1513
1514                 for (side=0,bit=1;side<6 && facemask>=bit;side++) {
1515
1516                         for (face=0;face<2;face++,bit<<=1) {
1517
1518                                 if (facemask & bit) {            //on the back of this face
1519                                         int face_hit_type;      //in what way did we hit the face?
1520                                         int num_faces,vertex_list[6];
1521
1522                                         //did we go through this wall/door?
1523
1524                                         if ((seg-Segments)==-1)
1525                                                 Error("segnum == -1 in sphere_intersects_wall()");
1526
1527                                         create_abs_vertex_lists(&num_faces,vertex_list,seg-Segments,side);
1528
1529                                         face_hit_type = check_sphere_to_face( pnt,&seg->sides[side],
1530                                                                                 face,((num_faces==1)?4:3),rad,vertex_list);
1531
1532                                         if (face_hit_type) {            //through this wall/door
1533                                                 int child,i;
1534
1535                                                 //if what we have hit is a door, check the adjoining seg
1536
1537                                                 child = seg->children[side];
1538
1539                                                 for (i=0;i<n_segs_visited && child!=segs_visited[i];i++);
1540
1541                                                 if (i==n_segs_visited) {                //haven't visited here yet
1542
1543                                                         if (!IS_CHILD(child))
1544                                                                 return 1;
1545                                                         else {
1546
1547                                                                 if (sphere_intersects_wall(pnt,child,rad))
1548                                                                         return 1;
1549                                                         }
1550                                                 }
1551                                         }
1552                                 }
1553                         }
1554                 }
1555         }
1556
1557         return 0;
1558 }
1559
1560 //Returns true if the object is through any walls
1561 int object_intersects_wall(object *objp)
1562 {
1563         n_segs_visited = 0;
1564
1565         return sphere_intersects_wall(&objp->pos,objp->segnum,objp->size);
1566 }
1567
1568