main/gameseg.c

   1 /* $Id: gameseg.c,v 1.4 2003-10-04 03:14:47 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  * Functions moved from segment.c to make editor separable from game.
  18  *
  19  * Old Log:
  20  * Revision 1.9  1995/11/08  16:26:04  allender
  21  * minor bug fix in find_connected_distance
  22  *
  23  * Revision 1.8  1995/10/12  17:36:55  allender
  24  * made trace_segs only recurse 100 times max
  25  *
  26  * Revision 1.7  1995/10/11  18:29:01  allender
  27  * removed Int3 from trace_segs
  28  *
  29  * Revision 1.6  1995/10/11  14:13:54  allender
  30  * put in stack check code into trace-segs
  31  *
  32  * Revision 1.5  1995/09/23  09:40:25  allender
  33  * put in casts in extract_shortpos to try and solve shortpos problem
  34  * with appletalk
  35  *
  36  * Revision 1.4  1995/09/20  14:26:50  allender
  37  * added flag to swap bytes on extract shortpot
  38  *
  39  * Revision 1.3  1995/08/12  12:01:27  allender
  40  * added flag to create_shortpos to swap bytes
  41  *
  42  * Revision 1.2  1995/06/06  10:42:07  allender
  43  * made shortpos routines swap bytes when extracting and making shortpos structures
  44  *
  45  * Revision 1.1  1995/05/16  15:25:46  allender
  46  * Initial revision
  47  *
  48  * Revision 2.2  1995/03/20  18:15:39  john
  49  * Added code to not store the normals in the segment structure.
  50  *
  51  * Revision 2.1  1995/03/08  12:11:39  allender
  52  * fix shortpos reading/writing
  53  *
  54  * Revision 2.0  1995/02/27  11:29:21  john
  55  * New version 2.0, which has no anonymous unions, builds with
  56  * Watcom 10.0, and doesn't require parsing BITMAPS.TBL.
  57  *
  58  * Revision 1.78  1995/02/22  13:52:22  allender
  59  * remove anonymous unions from object structure
  60  *
  61  * Revision 1.77  1995/02/22  13:24:47  john
  62  * Removed the vecmat anonymous unions.
  63  *
  64  * Revision 1.76  1995/02/13  20:35:01  john
  65  * Lintized
  66  *
  67  * Revision 1.75  1995/02/09  13:10:51  mike
  68  * remove an annoying mprintf.
  69  *
  70  * Revision 1.74  1995/02/05  17:49:28  rob
  71  * Added assert to gameseg.c.
  72  *
  73  * Revision 1.73  1995/02/02  00:49:26  mike
  74  * new automap segment-depth functionality.
  75  *
  76  * Revision 1.72  1995/01/16  21:06:51  mike
  77  * Move function pick_random_point_in_segment from fireball.c to gameseg.c.
  78  *
  79  * Revision 1.71  1994/12/21  19:54:32  matt
  80  * Added error checking
  81  *
  82  * Revision 1.70  1994/12/11  21:34:09  matt
  83  * Changed assert() to int3()
  84  *
  85  * Revision 1.69  1994/12/01  21:04:37  matt
  86  * Several important changes:
  87  *  (1) Checking against triangulated sides has been standardized a bit
  88  *  (2) Code has been added to de-triangulate some sides
  89  *  (3) BIG ONE: the tolerance for checking a point against a plane has
  90  *      been drastically relaxed
  91  *
  92  *
  93  * Revision 1.67  1994/11/27  23:12:21  matt
  94  * Made changes for new mprintf calling convention
  95  *
  96  * Revision 1.66  1994/11/26  22:51:40  matt
  97  * Removed editor-only fields from segment structure when editor is compiled
  98  * out, and padded segment structure to even multiple of 4 bytes.
  99  *
 100  * Revision 1.65  1994/11/22  16:55:38  mike
 101  * use memset in place of loop to clear array.
 102  *
 103  * Revision 1.64  1994/11/19  15:20:37  mike
 104  * rip out unused code and data
 105  *
 106  * Revision 1.63  1994/11/18  18:31:48  matt
 107  * Fixed code again (and maybe for real)
 108  *
 109  * Revision 1.62  1994/11/18  16:54:24  matt
 110  * Fixed extract_orient_from_segment()
 111  *
 112  * Revision 1.61  1994/11/17  14:56:50  mike
 113  * moved segment validation functions from editor to main.
 114  *
 115  * Revision 1.60  1994/11/16  23:38:53  mike
 116  * new improved boss teleportation behavior.
 117  *
 118  * Revision 1.59  1994/10/30  14:12:46  mike
 119  * rip out local segments stuff.
 120  *
 121  * Revision 1.58  1994/10/27  10:53:39  matt
 122  * Made connectivity error checking put up warning if errors found
 123  *
 124  * Revision 1.57  1994/10/25  21:19:26  mike
 125  * debugging code.
 126  *
 127  * Revision 1.56  1994/10/25  11:26:09  mike
 128  * *** empty log message ***
 129  *
 130  * Revision 1.55  1994/10/22  22:36:08  matt
 131  * Improved error finding routine
 132  *
 133  * Revision 1.54  1994/10/22  18:56:51  matt
 134  * Fixed obscure bug in segment trace code
 135  * Added error find routine, check_segment_connections()
 136  *
 137  * Revision 1.53  1994/10/17  14:05:19  matt
 138  * Don't give recursion assert if doing lighting
 139  *
 140  * Revision 1.52  1994/10/15  19:03:48  mike
 141  * Don't do exhaustive search in smooth lighting.
 142  *
 143  * Revision 1.51  1994/10/12  09:46:44  mike
 144  * Add debug code for trapping exhaustive searches.
 145  *
 146  * Revision 1.50  1994/10/11  20:50:41  matt
 147  * Made find_point_seg() take -1 as segnum, meaning to search all segments
 148  *
 149  * Revision 1.49  1994/10/11  17:40:31  matt
 150  * Fixed bug that caused segment trace to only go through sides you can fly through
 151  *
 152  * Revision 1.48  1994/10/10  14:48:16  matt
 153  * Fixed mistake that caused odd pauses and occasional int3's
 154  *
 155  * Revision 1.47  1994/10/09  23:50:41  matt
 156  * Made find_hitpoint_uv() work with triangulated sides
 157  *
 158  * Revision 1.46  1994/10/08  23:06:52  matt
 159  * trace_segs() didn't know about external walls
 160  *
 161  * Revision 1.45  1994/10/07  22:18:57  mike
 162  * Put in asserts to trap bad segnums.
 163  *
 164  * Revision 1.44  1994/10/06  14:08:07  matt
 165  * Added new function, extract_orient_from_segment()
 166  *
 167  * Revision 1.43  1994/10/04  16:24:11  mike
 168  * Set global Connected_segment_distance for debug reasons for aipath.c.
 169  *
 170  * Revision 1.42  1994/10/04  09:18:42  mike
 171  * Comment out a variable definition, preventing a warning message.
 172  *
 173  * Revision 1.41  1994/10/03  23:43:42  mike
 174  * Put in a warning for overrunning point_segs buffer.
 175  *
 176  * Revision 1.40  1994/10/03  20:55:43  rob
 177  * Added velocity to shortpos.
 178  *
 179  * Revision 1.39  1994/09/27  11:46:06  rob
 180  * re-fixed that same bug (ugh).
 181  *
 182  * Revision 1.38  1994/09/27  10:10:51  rob
 183  * Fixed bug in extract_shortpos (obj_relink added).
 184  *
 185  * Revision 1.37  1994/09/25  23:41:02  matt
 186  * Changed the object load & save code to read/write the structure fields one
 187  * at a time (rather than the whole structure at once).  This mean that the
 188  * object structure can be changed without breaking the load/save functions.
 189  * As a result of this change, the local_object data can be and has been
 190  * incorporated into the object array.  Also, timeleft is now a property
 191  * of all objects, and the object structure has been otherwise cleaned up.
 192  *
 193  * Revision 1.36  1994/09/22  19:03:05  mike
 194  * Add shortpos manipulation functions create_shortpos and extract_shortpos.
 195  *
 196  * Revision 1.35  1994/09/19  21:21:16  mike
 197  * Minor optimization to find_connected_distance.
 198  *
 199  * Revision 1.34  1994/09/19  21:05:25  mike
 200  * Write function find_connected_distance,
 201  * returns distance between two points as travellable through the mine.
 202  *
 203  * Revision 1.33  1994/08/30  15:07:15  matt
 204  * Changed find_point_seg() to deal with some infinite recursion problems.
 205  *
 206  * Revision 1.32  1994/08/11  18:58:32  mike
 207  * Use ints in place of shorts for optimization.
 208  *
 209  * Revision 1.31  1994/08/04  00:20:09  matt
 210  * Cleaned up fvi & physics error handling; put in code to make sure objects
 211  * are in correct segment; simplified segment finding for objects and points
 212  *
 213  * Revision 1.30  1994/08/03  16:46:12  mike
 214  * not much...
 215  *
 216  * Revision 1.29  1994/08/02  20:41:31  matt
 217  * Fixed bug in get_side_verts()
 218  *
 219  * Revision 1.28  1994/08/02  19:04:25  matt
 220  * Cleaned up vertex list functions
 221  *
 222  * Revision 1.27  1994/08/01  10:39:44  matt
 223  * find_new_seg() now will look through any kind of wall but a totally solid one
 224  *
 225  * Revision 1.26  1994/07/28  19:15:59  matt
 226  * Fixed yet another bug in get_seg_masks()
 227  *
 228  */
 229
 230 #ifdef HAVE_CONFIG_H
 231 #include <conf.h>
 232 #endif
 233
 234 #include <stdlib.h>
 235 #include <stdio.h>
 236 #include <string.h>     //      for memset()
 237
 238 #include "u_mem.h"
 239 #include "inferno.h"
 240 #include "game.h"
 241 #include "error.h"
 242 #include "mono.h"
 243 #include "vecmat.h"
 244 #include "gameseg.h"
 245 #include "wall.h"
 246 #include "fuelcen.h"
 247 #include "bm.h"
 248 #include "fvi.h"
 249 #include "byteswap.h"
 250
 251 #ifdef RCS
 252 static char rcsid[] = "$Id: gameseg.c,v 1.4 2003-10-04 03:14:47 btb Exp $";
 253 #endif
 254
 255 // How far a point can be from a plane, and still be "in" the plane
 256 #define PLANE_DIST_TOLERANCE    250
 257
 258 dl_index                Dl_indices[MAX_DL_INDICES];
 259 delta_light Delta_lights[MAX_DELTA_LIGHTS];
 260 int     Num_static_lights;
 261
 262 // ------------------------------------------------------------------------------------------
 263 // Compute the center point of a side of a segment.
 264 //      The center point is defined to be the average of the 4 points defining the side.
 265 void compute_center_point_on_side(vms_vector *vp,segment *sp,int side)
 266 {
 267         int                     v;
 268
 269         vm_vec_zero(vp);
 270
 271         for (v=0; v<4; v++)
 272                 vm_vec_add2(vp,&Vertices[sp->verts[Side_to_verts[side][v]]]);
 273
 274         vm_vec_scale(vp,F1_0/4);
 275 }
 276
 277 // ------------------------------------------------------------------------------------------
 278 // Compute segment center.
 279 //      The center point is defined to be the average of the 8 points defining the segment.
 280 void compute_segment_center(vms_vector *vp,segment *sp)
 281 {
 282         int                     v;
 283
 284         vm_vec_zero(vp);
 285
 286         for (v=0; v<8; v++)
 287                 vm_vec_add2(vp,&Vertices[sp->verts[v]]);
 288
 289         vm_vec_scale(vp,F1_0/8);
 290 }
 291
 292 // -----------------------------------------------------------------------------
 293 //      Given two segments, return the side index in the connecting segment which connects to the base segment
 294 //      Optimized by MK on 4/21/94 because it is a 2% load.
 295 int find_connect_side(segment *base_seg, segment *con_seg)
 296 {
 297         int     s;
 298         short   base_seg_num = base_seg - Segments;
 299         short *childs = con_seg->children;
 300
 301         for (s=0; s<MAX_SIDES_PER_SEGMENT; s++) {
 302                 if (*childs++ == base_seg_num)
 303                         return s;
 304         }
 305
 306
 307         // legal to return -1, used in object_move_one(), mk, 06/08/94: Assert(0);              // Illegal -- there is no connecting side between these two segments
 308         return -1;
 309
 310 }
 311
 312 // -----------------------------------------------------------------------------------
 313 //      Given a side, return the number of faces
 314 int get_num_faces(side *sidep)
 315 {
 316         switch (sidep->type) {
 317                 case SIDE_IS_QUAD:
 318                         return 1;
 319                         break;
 320                 case SIDE_IS_TRI_02:
 321                 case SIDE_IS_TRI_13:
 322                         return 2;
 323                         break;
 324                 default:
 325                         Error("Illegal type = %i\n", sidep->type);
 326                         break;
 327         }
 328
 329 }
 330
 331 // Fill in array with four absolute point numbers for a given side
 332 void get_side_verts(short *vertlist,int segnum,int sidenum)
 333 {
 334         int     i;
 335         sbyte   *sv = Side_to_verts[sidenum];
 336         short   *vp = Segments[segnum].verts;
 337
 338         for (i=4; i--;)
 339                 vertlist[i] = vp[sv[i]];
 340 }
 341
 342
 343 #ifdef EDITOR
 344 // -----------------------------------------------------------------------------------
 345 //      Create all vertex lists (1 or 2) for faces on a side.
 346 //      Sets:
 347 //              num_faces               number of lists
 348 //              vertices                        vertices in all (1 or 2) faces
 349 //      If there is one face, it has 4 vertices.
 350 //      If there are two faces, they both have three vertices, so face #0 is stored in vertices 0,1,2,
 351 //      face #1 is stored in vertices 3,4,5.
 352 // Note: these are not absolute vertex numbers, but are relative to the segment
 353 // Note:  for triagulated sides, the middle vertex of each trianle is the one NOT
 354 //   adjacent on the diagonal edge
 355 void create_all_vertex_lists(int *num_faces, int *vertices, int segnum, int sidenum)
 356 {
 357         side    *sidep = &Segments[segnum].sides[sidenum];
 358         int  *sv = Side_to_verts_int[sidenum];
 359
 360         Assert((segnum <= Highest_segment_index) && (segnum >= 0));
 361         Assert((sidenum >= 0) && (sidenum < 6));
 362
 363         switch (sidep->type) {
 364                 case SIDE_IS_QUAD:
 365
 366                         vertices[0] = sv[0];
 367                         vertices[1] = sv[1];
 368                         vertices[2] = sv[2];
 369                         vertices[3] = sv[3];
 370
 371                         *num_faces = 1;
 372                         break;
 373                 case SIDE_IS_TRI_02:
 374                         *num_faces = 2;
 375
 376                         vertices[0] = sv[0];
 377                         vertices[1] = sv[1];
 378                         vertices[2] = sv[2];
 379
 380                         vertices[3] = sv[2];
 381                         vertices[4] = sv[3];
 382                         vertices[5] = sv[0];
 383
 384                         //IMPORTANT: DON'T CHANGE THIS CODE WITHOUT CHANGING GET_SEG_MASKS()
 385                         //CREATE_ABS_VERTEX_LISTS(), CREATE_ALL_VERTEX_LISTS(), CREATE_ALL_VERTNUM_LISTS()
 386                         break;
 387                 case SIDE_IS_TRI_13:
 388                         *num_faces = 2;
 389
 390                         vertices[0] = sv[3];
 391                         vertices[1] = sv[0];
 392                         vertices[2] = sv[1];
 393
 394                         vertices[3] = sv[1];
 395                         vertices[4] = sv[2];
 396                         vertices[5] = sv[3];
 397
 398                         //IMPORTANT: DON'T CHANGE THIS CODE WITHOUT CHANGING GET_SEG_MASKS()
 399                         //CREATE_ABS_VERTEX_LISTS(), CREATE_ALL_VERTEX_LISTS(), CREATE_ALL_VERTNUM_LISTS()
 400                         break;
 401                 default:
 402                         Error("Illegal side type (1), type = %i, segment # = %i, side # = %i\n", sidep->type, segnum, sidenum);
 403                         break;
 404         }
 405
 406 }
 407 #endif
 408
 409 // -----------------------------------------------------------------------------------
 410 // Like create all vertex lists, but returns the vertnums (relative to
 411 // the side) for each of the faces that make up the side.
 412 //      If there is one face, it has 4 vertices.
 413 //      If there are two faces, they both have three vertices, so face #0 is stored in vertices 0,1,2,
 414 //      face #1 is stored in vertices 3,4,5.
 415 void create_all_vertnum_lists(int *num_faces, int *vertnums, int segnum, int sidenum)
 416 {
 417         side    *sidep = &Segments[segnum].sides[sidenum];
 418
 419         Assert((segnum <= Highest_segment_index) && (segnum >= 0));
 420
 421         switch (sidep->type) {
 422                 case SIDE_IS_QUAD:
 423
 424                         vertnums[0] = 0;
 425                         vertnums[1] = 1;
 426                         vertnums[2] = 2;
 427                         vertnums[3] = 3;
 428
 429                         *num_faces = 1;
 430                         break;
 431                 case SIDE_IS_TRI_02:
 432                         *num_faces = 2;
 433
 434                         vertnums[0] = 0;
 435                         vertnums[1] = 1;
 436                         vertnums[2] = 2;
 437
 438                         vertnums[3] = 2;
 439                         vertnums[4] = 3;
 440                         vertnums[5] = 0;
 441
 442                         //IMPORTANT: DON'T CHANGE THIS CODE WITHOUT CHANGING GET_SEG_MASKS()
 443                         //CREATE_ABS_VERTEX_LISTS(), CREATE_ALL_VERTEX_LISTS(), CREATE_ALL_VERTNUM_LISTS()
 444                         break;
 445                 case SIDE_IS_TRI_13:
 446                         *num_faces = 2;
 447
 448                         vertnums[0] = 3;
 449                         vertnums[1] = 0;
 450                         vertnums[2] = 1;
 451
 452                         vertnums[3] = 1;
 453                         vertnums[4] = 2;
 454                         vertnums[5] = 3;
 455
 456                         //IMPORTANT: DON'T CHANGE THIS CODE WITHOUT CHANGING GET_SEG_MASKS()
 457                         //CREATE_ABS_VERTEX_LISTS(), CREATE_ALL_VERTEX_LISTS(), CREATE_ALL_VERTNUM_LISTS()
 458                         break;
 459                 default:
 460                         Error("Illegal side type (2), type = %i, segment # = %i, side # = %i\n", sidep->type, segnum, sidenum);
 461                         break;
 462         }
 463
 464 }
 465
 466 // -----
 467 //like create_all_vertex_lists(), but generate absolute point numbers
 468 void create_abs_vertex_lists(int *num_faces, int *vertices, int segnum, int sidenum)
 469 {
 470         short   *vp = Segments[segnum].verts;
 471         side    *sidep = &Segments[segnum].sides[sidenum];
 472         int  *sv = Side_to_verts_int[sidenum];
 473
 474         Assert((segnum <= Highest_segment_index) && (segnum >= 0));
 475
 476         switch (sidep->type) {
 477                 case SIDE_IS_QUAD:
 478
 479                         vertices[0] = vp[sv[0]];
 480                         vertices[1] = vp[sv[1]];
 481                         vertices[2] = vp[sv[2]];
 482                         vertices[3] = vp[sv[3]];
 483
 484                         *num_faces = 1;
 485                         break;
 486                 case SIDE_IS_TRI_02:
 487                         *num_faces = 2;
 488
 489                         vertices[0] = vp[sv[0]];
 490                         vertices[1] = vp[sv[1]];
 491                         vertices[2] = vp[sv[2]];
 492
 493                         vertices[3] = vp[sv[2]];
 494                         vertices[4] = vp[sv[3]];
 495                         vertices[5] = vp[sv[0]];
 496
 497                         //IMPORTANT: DON'T CHANGE THIS CODE WITHOUT CHANGING GET_SEG_MASKS(),
 498                         //CREATE_ABS_VERTEX_LISTS(), CREATE_ALL_VERTEX_LISTS(), CREATE_ALL_VERTNUM_LISTS()
 499                         break;
 500                 case SIDE_IS_TRI_13:
 501                         *num_faces = 2;
 502
 503                         vertices[0] = vp[sv[3]];
 504                         vertices[1] = vp[sv[0]];
 505                         vertices[2] = vp[sv[1]];
 506
 507                         vertices[3] = vp[sv[1]];
 508                         vertices[4] = vp[sv[2]];
 509                         vertices[5] = vp[sv[3]];
 510
 511                         //IMPORTANT: DON'T CHANGE THIS CODE WITHOUT CHANGING GET_SEG_MASKS()
 512                         //CREATE_ABS_VERTEX_LISTS(), CREATE_ALL_VERTEX_LISTS(), CREATE_ALL_VERTNUM_LISTS()
 513                         break;
 514                 default:
 515                         Error("Illegal side type (3), type = %i, segment # = %i, side # = %i\n", sidep->type, segnum, sidenum);
 516                         break;
 517         }
 518
 519 }
 520
 521
 522 //returns 3 different bitmasks with info telling if this sphere is in
 523 //this segment.  See segmasks structure for info on fields
 524 segmasks get_seg_masks(vms_vector *checkp,int segnum,fix rad)
 525 {
 526         int                     sn,facebit,sidebit;
 527         segmasks                masks;
 528         int                     num_faces;
 529         int                     vertex_list[6];
 530         segment         *seg;
 531
 532         if (segnum==-1)
 533                 Error("segnum == -1 in get_seg_masks()");
 534
 535         Assert((segnum <= Highest_segment_index) && (segnum >= 0));
 536
 537         seg = &Segments[segnum];
 538
 539         //check point against each side of segment. return bitmask
 540
 541         masks.sidemask = masks.facemask = masks.centermask = 0;
 542
 543         for (sn=0,facebit=sidebit=1;sn<6;sn++,sidebit<<=1) {
 544                 #ifndef COMPACT_SEGS
 545                 side    *s = &seg->sides[sn];
 546                 #endif
 547                 int     side_pokes_out;
 548                 int     vertnum,fn;
 549
 550                 // Get number of faces on this side, and at vertex_list, store vertices.
 551                 //      If one face, then vertex_list indicates a quadrilateral.
 552                 //      If two faces, then 0,1,2 define one triangle, 3,4,5 define the second.
 553                 create_abs_vertex_lists( &num_faces, vertex_list, segnum, sn);
 554
 555                 //ok...this is important.  If a side has 2 faces, we need to know if
 556                 //those faces form a concave or convex side.  If the side pokes out,
 557                 //then a point is on the back of the side if it is behind BOTH faces,
 558                 //but if the side pokes in, a point is on the back if behind EITHER face.
 559
 560                 if (num_faces==2) {
 561                         fix     dist;
 562                         int     side_count,center_count;
 563                         #ifdef COMPACT_SEGS
 564                         vms_vector normals[2];
 565                         #endif
 566
 567                         vertnum = min(vertex_list[0],vertex_list[2]);
 568
 569                         #ifdef COMPACT_SEGS
 570                         get_side_normals(seg, sn, &normals[0], &normals[1] );
 571                         #endif
 572
 573                         if (vertex_list[4] < vertex_list[1])
 574                                 #ifdef COMPACT_SEGS
 575                                         dist = vm_dist_to_plane(&Vertices[vertex_list[4]],&normals[0],&Vertices[vertnum]);
 576                                 #else
 577                                         dist = vm_dist_to_plane(&Vertices[vertex_list[4]],&s->normals[0],&Vertices[vertnum]);
 578                                 #endif
 579                         else
 580                                 #ifdef COMPACT_SEGS
 581                                         dist = vm_dist_to_plane(&Vertices[vertex_list[1]],&normals[1],&Vertices[vertnum]);
 582                                 #else
 583                                         dist = vm_dist_to_plane(&Vertices[vertex_list[1]],&s->normals[1],&Vertices[vertnum]);
 584                                 #endif
 585
 586                         side_pokes_out = (dist > PLANE_DIST_TOLERANCE);
 587
 588                         side_count = center_count = 0;
 589
 590                         for (fn=0;fn<2;fn++,facebit<<=1) {
 591
 592                                 #ifdef COMPACT_SEGS
 593                                         dist = vm_dist_to_plane(checkp, &normals[fn], &Vertices[vertnum]);
 594                                 #else
 595                                         dist = vm_dist_to_plane(checkp, &s->normals[fn], &Vertices[vertnum]);
 596                                 #endif
 597
 598                                 if (dist < -PLANE_DIST_TOLERANCE)       //in front of face
 599                                         center_count++;
 600
 601                                 if (dist-rad < -PLANE_DIST_TOLERANCE) {
 602                                         masks.facemask |= facebit;
 603                                         side_count++;
 604                                 }
 605                         }
 606
 607                         if (!side_pokes_out) {          //must be behind both faces
 608
 609                                 if (side_count==2)
 610                                         masks.sidemask |= sidebit;
 611
 612                                 if (center_count==2)
 613                                         masks.centermask |= sidebit;
 614
 615                         }
 616                         else {                                                  //must be behind at least one face
 617
 618                                 if (side_count)
 619                                         masks.sidemask |= sidebit;
 620
 621                                 if (center_count)
 622                                         masks.centermask |= sidebit;
 623
 624                         }
 625
 626
 627                 }
 628                 else {                          //only one face on this side
 629                         fix dist;
 630                         int i;
 631                         #ifdef COMPACT_SEGS
 632                         vms_vector normal;
 633                         #endif
 634
 635                         //use lowest point number
 636
 637                         vertnum = vertex_list[0];
 638                         for (i=1;i<4;i++)
 639                                 if (vertex_list[i] < vertnum)
 640                                         vertnum = vertex_list[i];
 641
 642                         #ifdef COMPACT_SEGS
 643                                 get_side_normal(seg, sn, 0, &normal );
 644                                 dist = vm_dist_to_plane(checkp, &normal, &Vertices[vertnum]);
 645                         #else
 646                                 dist = vm_dist_to_plane(checkp, &s->normals[0], &Vertices[vertnum]);
 647                         #endif
 648
 649
 650                         if (dist < -PLANE_DIST_TOLERANCE)
 651                                 masks.centermask |= sidebit;
 652
 653                         if (dist-rad < -PLANE_DIST_TOLERANCE) {
 654                                 masks.facemask |= facebit;
 655                                 masks.sidemask |= sidebit;
 656                         }
 657
 658                         facebit <<= 2;
 659                 }
 660
 661         }
 662
 663         return masks;
 664
 665 }
 666
 667 //this was converted from get_seg_masks()...it fills in an array of 6
 668 //elements for the distace behind each side, or zero if not behind
 669 //only gets centermask, and assumes zero rad
 670 ubyte get_side_dists(vms_vector *checkp,int segnum,fix *side_dists)
 671 {
 672         int                     sn,facebit,sidebit;
 673         ubyte                   mask;
 674         int                     num_faces;
 675         int                     vertex_list[6];
 676         segment         *seg;
 677
 678         Assert((segnum <= Highest_segment_index) && (segnum >= 0));
 679
 680         if (segnum==-1)
 681                 Error("segnum == -1 in get_seg_dists()");
 682
 683         seg = &Segments[segnum];
 684
 685         //check point against each side of segment. return bitmask
 686
 687         mask = 0;
 688
 689         for (sn=0,facebit=sidebit=1;sn<6;sn++,sidebit<<=1) {
 690                 #ifndef COMPACT_SEGS
 691                 side    *s = &seg->sides[sn];
 692                 #endif
 693                 int     side_pokes_out;
 694                 int     fn;
 695
 696                 side_dists[sn] = 0;
 697
 698                 // Get number of faces on this side, and at vertex_list, store vertices.
 699                 //      If one face, then vertex_list indicates a quadrilateral.
 700                 //      If two faces, then 0,1,2 define one triangle, 3,4,5 define the second.
 701                 create_abs_vertex_lists( &num_faces, vertex_list, segnum, sn);
 702
 703                 //ok...this is important.  If a side has 2 faces, we need to know if
 704                 //those faces form a concave or convex side.  If the side pokes out,
 705                 //then a point is on the back of the side if it is behind BOTH faces,
 706                 //but if the side pokes in, a point is on the back if behind EITHER face.
 707
 708                 if (num_faces==2) {
 709                         fix     dist;
 710                         int     center_count;
 711                         int     vertnum;
 712                         #ifdef COMPACT_SEGS
 713                         vms_vector normals[2];
 714                         #endif
 715
 716                         vertnum = min(vertex_list[0],vertex_list[2]);
 717
 718                         #ifdef COMPACT_SEGS
 719                         get_side_normals(seg, sn, &normals[0], &normals[1] );
 720                         #endif
 721
 722                         if (vertex_list[4] < vertex_list[1])
 723                                 #ifdef COMPACT_SEGS
 724                                         dist = vm_dist_to_plane(&Vertices[vertex_list[4]],&normals[0],&Vertices[vertnum]);
 725                                 #else
 726                                         dist = vm_dist_to_plane(&Vertices[vertex_list[4]],&s->normals[0],&Vertices[vertnum]);
 727                                 #endif
 728                         else
 729                                 #ifdef COMPACT_SEGS
 730                                         dist = vm_dist_to_plane(&Vertices[vertex_list[1]],&normals[1],&Vertices[vertnum]);
 731                                 #else
 732                                         dist = vm_dist_to_plane(&Vertices[vertex_list[1]],&s->normals[1],&Vertices[vertnum]);
 733                                 #endif
 734
 735                         side_pokes_out = (dist > PLANE_DIST_TOLERANCE);
 736
 737                         center_count = 0;
 738
 739                         for (fn=0;fn<2;fn++,facebit<<=1) {
 740
 741                                 #ifdef COMPACT_SEGS
 742                                         dist = vm_dist_to_plane(checkp, &normals[fn], &Vertices[vertnum]);
 743                                 #else
 744                                         dist = vm_dist_to_plane(checkp, &s->normals[fn], &Vertices[vertnum]);
 745                                 #endif
 746
 747                                 if (dist < -PLANE_DIST_TOLERANCE) {     //in front of face
 748                                         center_count++;
 749                                         side_dists[sn] += dist;
 750                                 }
 751
 752                         }
 753
 754                         if (!side_pokes_out) {          //must be behind both faces
 755
 756                                 if (center_count==2) {
 757                                         mask |= sidebit;
 758                                         side_dists[sn] /= 2;            //get average
 759                                 }
 760
 761
 762                         }
 763                         else {                                                  //must be behind at least one face
 764
 765                                 if (center_count) {
 766                                         mask |= sidebit;
 767                                         if (center_count==2)
 768                                                 side_dists[sn] /= 2;            //get average
 769
 770                                 }
 771                         }
 772
 773
 774                 }
 775                 else {                          //only one face on this side
 776                         fix dist;
 777                         int i,vertnum;
 778                         #ifdef COMPACT_SEGS
 779                         vms_vector normal;
 780                         #endif
 781
 782
 783                         //use lowest point number
 784
 785                         vertnum = vertex_list[0];
 786                         for (i=1;i<4;i++)
 787                                 if (vertex_list[i] < vertnum)
 788                                         vertnum = vertex_list[i];
 789
 790                         #ifdef COMPACT_SEGS
 791                                 get_side_normal(seg, sn, 0, &normal );
 792                                 dist = vm_dist_to_plane(checkp, &normal, &Vertices[vertnum]);
 793                         #else
 794                                 dist = vm_dist_to_plane(checkp, &s->normals[0], &Vertices[vertnum]);
 795                         #endif
 796
 797                         if (dist < -PLANE_DIST_TOLERANCE) {
 798                                 mask |= sidebit;
 799                                 side_dists[sn] = dist;
 800                         }
 801
 802                         facebit <<= 2;
 803                 }
 804
 805         }
 806
 807         return mask;
 808
 809 }
 810
 811 #ifndef NDEBUG
 812 #ifndef COMPACT_SEGS
 813 //returns true if errors detected
 814 int check_norms(int segnum,int sidenum,int facenum,int csegnum,int csidenum,int cfacenum)
 815 {
 816         vms_vector *n0,*n1;
 817
 818         n0 = &Segments[segnum].sides[sidenum].normals[facenum];
 819         n1 = &Segments[csegnum].sides[csidenum].normals[cfacenum];
 820
 821         if (n0->x != -n1->x  ||  n0->y != -n1->y  ||  n0->z != -n1->z) {
 822                 mprintf((0,"Seg %x, side %d, norm %d doesn't match seg %x, side %d, norm %d:\n"
 823                                 "   %8x %8x %8x\n"
 824                                 "   %8x %8x %8x (negated)\n",
 825                                 segnum,sidenum,facenum,csegnum,csidenum,cfacenum,
 826                                 n0->x,n0->y,n0->z,-n1->x,-n1->y,-n1->z));
 827                 return 1;
 828         }
 829         else
 830                 return 0;
 831 }
 832
 833 //heavy-duty error checking
 834 int check_segment_connections(void)
 835 {
 836         int segnum,sidenum;
 837         int errors=0;
 838
 839         for (segnum=0;segnum<=Highest_segment_index;segnum++) {
 840                 segment *seg;
 841
 842                 seg = &Segments[segnum];
 843
 844                 for (sidenum=0;sidenum<6;sidenum++) {
 845                         side *s;
 846                         segment *cseg;
 847                         side *cs;
 848                         int num_faces,csegnum,csidenum,con_num_faces;
 849                         int vertex_list[6],con_vertex_list[6];
 850
 851                         s = &seg->sides[sidenum];
 852
 853                         create_abs_vertex_lists( &num_faces, vertex_list, segnum, sidenum);
 854
 855                         csegnum = seg->children[sidenum];
 856
 857                         if (csegnum >= 0) {
 858                                 cseg = &Segments[csegnum];
 859                                 csidenum = find_connect_side(seg,cseg);
 860
 861                                 if (csidenum == -1) {
 862                                         mprintf((0,"Could not find connected side for seg %x back to seg %x, side %d\n",csegnum,segnum,sidenum));
 863                                         errors = 1;
 864                                         continue;
 865                                 }
 866
 867                                 cs = &cseg->sides[csidenum];
 868
 869                                 create_abs_vertex_lists( &con_num_faces, con_vertex_list, csegnum, csidenum);
 870
 871                                 if (con_num_faces != num_faces) {
 872                                         mprintf((0,"Seg %x, side %d: num_faces (%d) mismatch with seg %x, side %d (%d)\n",segnum,sidenum,num_faces,csegnum,csidenum,con_num_faces));
 873                                         errors = 1;
 874                                 }
 875                                 else
 876                                         if (num_faces == 1) {
 877                                                 int t;
 878
 879                                                 for (t=0;t<4 && con_vertex_list[t]!=vertex_list[0];t++);
 880
 881                                                 if (t==4 ||
 882                                                          vertex_list[0] != con_vertex_list[t] ||
 883                                                          vertex_list[1] != con_vertex_list[(t+3)%4] ||
 884                                                          vertex_list[2] != con_vertex_list[(t+2)%4] ||
 885                                                          vertex_list[3] != con_vertex_list[(t+1)%4]) {
 886                                                         mprintf((0,"Seg %x, side %d: vertex list mismatch with seg %x, side %d\n"
 887                                                                         "  %x %x %x %x\n"
 888                                                                         "  %x %x %x %x\n",
 889                                                                         segnum,sidenum,csegnum,csidenum,
 890                                                                         vertex_list[0],vertex_list[1],vertex_list[2],vertex_list[3],
 891                                                                         con_vertex_list[0],con_vertex_list[1],con_vertex_list[2],con_vertex_list[3]));
 892                                                         errors = 1;
 893                                                 }
 894                                                 else
 895                                                         errors |= check_norms(segnum,sidenum,0,csegnum,csidenum,0);
 896
 897                                         }
 898                                         else {
 899
 900                                                 if (vertex_list[1] == con_vertex_list[1]) {
 901
 902                                                         if (vertex_list[4] != con_vertex_list[4] ||
 903                                                                  vertex_list[0] != con_vertex_list[2] ||
 904                                                                  vertex_list[2] != con_vertex_list[0] ||
 905                                                                  vertex_list[3] != con_vertex_list[5] ||
 906                                                                  vertex_list[5] != con_vertex_list[3]) {
 907                                                                 mprintf((0,"Seg %x, side %d: vertex list mismatch with seg %x, side %d\n"
 908                                                                                 "  %x %x %x  %x %x %x\n"
 909                                                                                 "  %x %x %x  %x %x %x\n",
 910                                                                                 segnum,sidenum,csegnum,csidenum,
 911                                                                                 vertex_list[0],vertex_list[1],vertex_list[2],vertex_list[3],vertex_list[4],vertex_list[5],
 912                                                                                 con_vertex_list[0],con_vertex_list[1],con_vertex_list[2],con_vertex_list[3],con_vertex_list[4],con_vertex_list[5]));
 913                                                                 mprintf((0,"Changing seg:side %4i:%i from %i to %i\n", csegnum, csidenum, Segments[csegnum].sides[csidenum].type, 5-Segments[csegnum].sides[csidenum].type));
 914                                                                 Segments[csegnum].sides[csidenum].type = 5-Segments[csegnum].sides[csidenum].type;
 915                                                         } else {
 916                                                                 errors |= check_norms(segnum,sidenum,0,csegnum,csidenum,0);
 917                                                                 errors |= check_norms(segnum,sidenum,1,csegnum,csidenum,1);
 918                                                         }
 919
 920                                                 } else {
 921
 922                                                         if (vertex_list[1] != con_vertex_list[4] ||
 923                                                                  vertex_list[4] != con_vertex_list[1] ||
 924                                                                  vertex_list[0] != con_vertex_list[5] ||
 925                                                                  vertex_list[5] != con_vertex_list[0] ||
 926                                                                  vertex_list[2] != con_vertex_list[3] ||
 927                                                                  vertex_list[3] != con_vertex_list[2]) {
 928                                                                 mprintf((0,"Seg %x, side %d: vertex list mismatch with seg %x, side %d\n"
 929                                                                                 "  %x %x %x  %x %x %x\n"
 930                                                                                 "  %x %x %x  %x %x %x\n",
 931                                                                                 segnum,sidenum,csegnum,csidenum,
 932                                                                                 vertex_list[0],vertex_list[1],vertex_list[2],vertex_list[3],vertex_list[4],vertex_list[5],
 933                                                                                 con_vertex_list[0],con_vertex_list[1],con_vertex_list[2],con_vertex_list[3],con_vertex_list[4],vertex_list[5]));
 934                                                                 mprintf((0,"Changing seg:side %4i:%i from %i to %i\n", csegnum, csidenum, Segments[csegnum].sides[csidenum].type, 5-Segments[csegnum].sides[csidenum].type));
 935                                                                 Segments[csegnum].sides[csidenum].type = 5-Segments[csegnum].sides[csidenum].type;
 936                                                         } else {
 937                                                                 errors |= check_norms(segnum,sidenum,0,csegnum,csidenum,1);
 938                                                                 errors |= check_norms(segnum,sidenum,1,csegnum,csidenum,0);
 939                                                         }
 940                                                 }
 941                                         }
 942                         }
 943                 }
 944         }
 945
 946         // mprintf((0,"\n DONE \n"));
 947
 948         return errors;
 949
 950 }
 951 #endif
 952 #endif
 953
 954 //      Used to become a constant based on editor, but I wanted to be able to set
 955 //      this for omega blob find_point_seg calls.  Would be better to pass a paremeter
 956 //      to the routine...--MK, 01/17/96
 957 int     Doing_lighting_hack_flag=0;
 958
 959 //figure out what seg the given point is in, tracing through segments
 960 //returns segment number, or -1 if can't find segment
 961 int trace_segs(vms_vector *p0,int oldsegnum)
 962 {
 963         int centermask;
 964         segment *seg;
 965         fix side_dists[6];
 966
 967         Assert((oldsegnum <= Highest_segment_index) && (oldsegnum >= 0));
 968
 969
 970         centermask = get_side_dists(p0,oldsegnum,side_dists);           //check old segment
 971
 972         if (centermask == 0)            //we're in the old segment
 973
 974                 return oldsegnum;               //..say so
 975
 976         else {                                          //not in old seg.  trace through to find seg
 977                 int biggest_side;
 978
 979                 do {
 980                         int sidenum,bit;
 981                         fix biggest_val;
 982
 983                         seg = &Segments[oldsegnum];
 984
 985                         biggest_side = -1; biggest_val = 0;
 986
 987                         for (sidenum=0,bit=1;sidenum<6;sidenum++,bit<<=1)
 988                                 if ((centermask&bit) && (seg->children[sidenum]>-1))
 989                                         if (side_dists[sidenum] < biggest_val) {
 990                                                 biggest_val = side_dists[sidenum];
 991                                                 biggest_side = sidenum;
 992                                         }
 993
 994                         if (biggest_side != -1) {
 995                                 int check;
 996
 997                                 side_dists[biggest_side] = 0;
 998
 999                                 check = trace_segs(p0,seg->children[biggest_side]);     //trace into adjacent segment
1000
1001                                 if (check != -1)                //we've found a segment
1002                                         return check;
1003                         }
1004
1005
1006                 } while (biggest_side!=-1);
1007
1008                 return -1;              //we haven't found a segment
1009         }
1010
1011 }
1012
1013
1014 int     Exhaustive_count=0, Exhaustive_failed_count=0;
1015
1016 //Tries to find a segment for a point, in the following way:
1017 // 1. Check the given segment
1018 // 2. Recursively trace through attached segments
1019 // 3. Check all the segmentns
1020 //Returns segnum if found, or -1
1021 int find_point_seg(vms_vector *p,int segnum)
1022 {
1023         int newseg;
1024
1025         //allow segnum==-1, meaning we have no idea what segment point is in
1026         Assert((segnum <= Highest_segment_index) && (segnum >= -1));
1027
1028         if (segnum != -1) {
1029                 newseg = trace_segs(p,segnum);
1030
1031                 if (newseg != -1)                       //we found a segment!
1032                         return newseg;
1033         }
1034
1035         //couldn't find via attached segs, so search all segs
1036
1037         //      MK: 10/15/94
1038         //      This Doing_lighting_hack_flag thing added by mk because the hundreds of scrolling messages were
1039         //      slowing down lighting, and in about 98% of cases, it would just return -1 anyway.
1040         //      Matt: This really should be fixed, though.  We're probably screwing up our lighting in a few places.
1041         if (!Doing_lighting_hack_flag) {
1042                 mprintf((1,"Warning: doing exhaustive search to find point segment (%i times)\n", ++Exhaustive_count));
1043
1044                 for (newseg=0;newseg <= Highest_segment_index;newseg++)
1045                         if (get_seg_masks(p,newseg,0).centermask == 0)
1046                                 return newseg;
1047
1048                 mprintf((1,"Warning: could not find point segment (%i times)\n", ++Exhaustive_failed_count));
1049
1050                 return -1;              //no segment found
1051         } else
1052                 return -1;
1053 }
1054
1055
1056 //--repair-- // ------------------------------------------------------------------------------
1057 //--repair-- void clsd_repair_center(int segnum)
1058 //--repair-- {
1059 //--repair--    int     sidenum;
1060 //--repair--
1061 //--repair--    //      --- Set repair center bit for all repair center segments.
1062 //--repair--    if (Segments[segnum].special == SEGMENT_IS_REPAIRCEN) {
1063 //--repair--            Lsegments[segnum].special_type |= SS_REPAIR_CENTER;
1064 //--repair--            Lsegments[segnum].special_segment = segnum;
1065 //--repair--    }
1066 //--repair--
1067 //--repair--    //      --- Set repair center bit for all segments adjacent to a repair center.
1068 //--repair--    for (sidenum=0; sidenum < MAX_SIDES_PER_SEGMENT; sidenum++) {
1069 //--repair--            int     s = Segments[segnum].children[sidenum];
1070 //--repair--
1071 //--repair--            if ( (s != -1) && (Segments[s].special==SEGMENT_IS_REPAIRCEN) ) {
1072 //--repair--                    Lsegments[segnum].special_type |= SS_REPAIR_CENTER;
1073 //--repair--                    Lsegments[segnum].special_segment = s;
1074 //--repair--            }
1075 //--repair--    }
1076 //--repair-- }
1077
1078 //--repair-- // ------------------------------------------------------------------------------
1079 //--repair-- // --- Set destination points for all Materialization centers.
1080 //--repair-- void clsd_materialization_center(int segnum)
1081 //--repair-- {
1082 //--repair--    if (Segments[segnum].special == SEGMENT_IS_ROBOTMAKER) {
1083 //--repair--
1084 //--repair--    }
1085 //--repair-- }
1086 //--repair--
1087 //--repair-- int        Lsegment_highest_segment_index, Lsegment_highest_vertex_index;
1088 //--repair--
1089 //--repair-- // ------------------------------------------------------------------------------
1090 //--repair-- // Create data specific to mine which doesn't get written to disk.
1091 //--repair-- // Highest_segment_index and Highest_object_index must be valid.
1092 //--repair-- // 07/21:  set repair center bit
1093 //--repair-- void create_local_segment_data(void)
1094 //--repair-- {
1095 //--repair--    int     segnum;
1096 //--repair--
1097 //--repair--    //      --- Initialize all Lsegments.
1098 //--repair--    for (segnum=0; segnum <= Highest_segment_index; segnum++) {
1099 //--repair--            Lsegments[segnum].special_type = 0;
1100 //--repair--            Lsegments[segnum].special_segment = -1;
1101 //--repair--    }
1102 //--repair--
1103 //--repair--    for (segnum=0; segnum <= Highest_segment_index; segnum++) {
1104 //--repair--
1105 //--repair--            clsd_repair_center(segnum);
1106 //--repair--            clsd_materialization_center(segnum);
1107 //--repair--
1108 //--repair--    }
1109 //--repair--
1110 //--repair--    //      Set check variables.
1111 //--repair--    //      In main game loop, make sure these are valid, else Lsegments is not valid.
1112 //--repair--    Lsegment_highest_segment_index = Highest_segment_index;
1113 //--repair--    Lsegment_highest_vertex_index = Highest_vertex_index;
1114 //--repair-- }
1115 //--repair--
1116 //--repair-- // ------------------------------------------------------------------------------------------
1117 //--repair-- // Sort of makes sure create_local_segment_data has been called for the currently executing mine.
1118 //--repair-- // It is not failsafe, as you will see if you look at the code.
1119 //--repair-- // Returns 1 if Lsegments appears valid, 0 if not.
1120 //--repair-- int check_lsegments_validity(void)
1121 //--repair-- {
1122 //--repair--    return ((Lsegment_highest_segment_index == Highest_segment_index) && (Lsegment_highest_vertex_index == Highest_vertex_index));
1123 //--repair-- }
1124
1125 #define MAX_LOC_POINT_SEGS      64
1126
1127 int     Connected_segment_distance;
1128
1129 #define MIN_CACHE_FCD_DIST      (F1_0*80)       //      Must be this far apart for cache lookup to succeed.  Recognizes small changes in distance matter at small distances.
1130 #define MAX_FCD_CACHE   8
1131
1132 typedef struct {
1133         int     seg0, seg1, csd;
1134         fix     dist;
1135 } fcd_data;
1136
1137 int     Fcd_index = 0;
1138 fcd_data Fcd_cache[MAX_FCD_CACHE];
1139 fix     Last_fcd_flush_time;
1140
1141 //      ----------------------------------------------------------------------------------------------------------
1142 void flush_fcd_cache(void)
1143 {
1144         int     i;
1145
1146         Fcd_index = 0;
1147
1148         for (i=0; i<MAX_FCD_CACHE; i++)
1149                 Fcd_cache[i].seg0 = -1;
1150 }
1151
1152 //      ----------------------------------------------------------------------------------------------------------
1153 void add_to_fcd_cache(int seg0, int seg1, int depth, fix dist)
1154 {
1155         if (dist > MIN_CACHE_FCD_DIST) {
1156                 Fcd_cache[Fcd_index].seg0 = seg0;
1157                 Fcd_cache[Fcd_index].seg1 = seg1;
1158                 Fcd_cache[Fcd_index].csd = depth;
1159                 Fcd_cache[Fcd_index].dist = dist;
1160
1161                 Fcd_index++;
1162
1163                 if (Fcd_index >= MAX_FCD_CACHE)
1164                         Fcd_index = 0;
1165
1166                 // -- mprintf((0, "Adding seg0=%i, seg1=%i to cache.\n", seg0, seg1));
1167         } else {
1168                 //      If it's in the cache, remove it.
1169                 int     i;
1170
1171                 for (i=0; i<MAX_FCD_CACHE; i++)
1172                         if (Fcd_cache[i].seg0 == seg0)
1173                                 if (Fcd_cache[i].seg1 == seg1) {
1174                                         Fcd_cache[Fcd_index].seg0 = -1;
1175                                         break;
1176                                 }
1177         }
1178
1179 }
1180
1181 //      ----------------------------------------------------------------------------------------------------------
1182 //      Determine whether seg0 and seg1 are reachable in a way that allows sound to pass.
1183 //      Search up to a maximum depth of max_depth.
1184 //      Return the distance.
1185 fix find_connected_distance(vms_vector *p0, int seg0, vms_vector *p1, int seg1, int max_depth, int wid_flag)
1186 {
1187         int             cur_seg;
1188         int             sidenum;
1189         int             qtail = 0, qhead = 0;
1190         int             i;
1191         sbyte   visited[MAX_SEGMENTS];
1192         seg_seg seg_queue[MAX_SEGMENTS];
1193         short           depth[MAX_SEGMENTS];
1194         int             cur_depth;
1195         int             num_points;
1196         point_seg       point_segs[MAX_LOC_POINT_SEGS];
1197         fix             dist;
1198
1199         //      If > this, will overrun point_segs buffer
1200 #ifdef WINDOWS
1201         if (max_depth == -1) max_depth = 200;
1202 #endif
1203
1204         if (max_depth > MAX_LOC_POINT_SEGS-2) {
1205                 mprintf((1, "Warning: In find_connected_distance, max_depth = %i, limited to %i\n", max_depth, MAX_LOC_POINT_SEGS-2));
1206                 max_depth = MAX_LOC_POINT_SEGS-2;
1207         }
1208
1209         if (seg0 == seg1) {
1210                 Connected_segment_distance = 0;
1211                 return vm_vec_dist_quick(p0, p1);
1212         } else {
1213                 int     conn_side;
1214                 if ((conn_side = find_connect_side(&Segments[seg0], &Segments[seg1])) != -1) {
1215                         if (WALL_IS_DOORWAY(&Segments[seg1], conn_side) & wid_flag) {
1216                                 Connected_segment_distance = 1;
1217                                 //mprintf((0, "\n"));
1218                                 return vm_vec_dist_quick(p0, p1);
1219                         }
1220                 }
1221         }
1222
1223         //      Periodically flush cache.
1224         if ((GameTime - Last_fcd_flush_time > F1_0*2) || (GameTime < Last_fcd_flush_time)) {
1225                 flush_fcd_cache();
1226                 Last_fcd_flush_time = GameTime;
1227         }
1228
1229         //      Can't quickly get distance, so see if in Fcd_cache.
1230         for (i=0; i<MAX_FCD_CACHE; i++)
1231                 if ((Fcd_cache[i].seg0 == seg0) && (Fcd_cache[i].seg1 == seg1)) {
1232                         Connected_segment_distance = Fcd_cache[i].csd;
1233                         // -- mprintf((0, "In cache, seg0=%i, seg1=%i.  Returning.\n", seg0, seg1));
1234                         return Fcd_cache[i].dist;
1235                 }
1236
1237         num_points = 0;
1238
1239         memset(visited, 0, Highest_segment_index+1);
1240         memset(depth, 0, sizeof(depth[0]) * (Highest_segment_index+1));
1241
1242         cur_seg = seg0;
1243         visited[cur_seg] = 1;
1244         cur_depth = 0;
1245
1246         while (cur_seg != seg1) {
1247                 segment *segp = &Segments[cur_seg];
1248
1249                 for (sidenum = 0; sidenum < MAX_SIDES_PER_SEGMENT; sidenum++) {
1250
1251                         int     snum = sidenum;
1252
1253                         if (WALL_IS_DOORWAY(segp, snum) & wid_flag) {
1254                                 int     this_seg = segp->children[snum];
1255
1256                                 if (!visited[this_seg]) {
1257                                         seg_queue[qtail].start = cur_seg;
1258                                         seg_queue[qtail].end = this_seg;
1259                                         visited[this_seg] = 1;
1260                                         depth[qtail++] = cur_depth+1;
1261                                         if (max_depth != -1) {
1262                                                 if (depth[qtail-1] == max_depth) {
1263                                                         Connected_segment_distance = 1000;
1264                                                         add_to_fcd_cache(seg0, seg1, Connected_segment_distance, F1_0*1000);
1265                                                         return -1;
1266                                                 }
1267                                         } else if (this_seg == seg1) {
1268                                                 goto fcd_done1;
1269                                         }
1270                                 }
1271
1272                         }
1273                 }       //      for (sidenum...
1274
1275                 if (qhead >= qtail) {
1276                         Connected_segment_distance = 1000;
1277                         add_to_fcd_cache(seg0, seg1, Connected_segment_distance, F1_0*1000);
1278                         return -1;
1279                 }
1280
1281                 cur_seg = seg_queue[qhead].end;
1282                 cur_depth = depth[qhead];
1283                 qhead++;
1284
1285 fcd_done1: ;
1286         }       //      while (cur_seg ...
1287
1288         //      Set qtail to the segment which ends at the goal.
1289         while (seg_queue[--qtail].end != seg1)
1290                 if (qtail < 0) {
1291                         Connected_segment_distance = 1000;
1292                         add_to_fcd_cache(seg0, seg1, Connected_segment_distance, F1_0*1000);
1293                         return -1;
1294                 }
1295
1296         while (qtail >= 0) {
1297                 int     parent_seg, this_seg;
1298
1299                 this_seg = seg_queue[qtail].end;
1300                 parent_seg = seg_queue[qtail].start;
1301                 point_segs[num_points].segnum = this_seg;
1302                 compute_segment_center(&point_segs[num_points].point,&Segments[this_seg]);
1303                 num_points++;
1304
1305                 if (parent_seg == seg0)
1306                         break;
1307
1308                 while (seg_queue[--qtail].end != parent_seg)
1309                         Assert(qtail >= 0);
1310         }
1311
1312         point_segs[num_points].segnum = seg0;
1313         compute_segment_center(&point_segs[num_points].point,&Segments[seg0]);
1314         num_points++;
1315
1316         if (num_points == 1) {
1317                 Connected_segment_distance = num_points;
1318                 return vm_vec_dist_quick(p0, p1);
1319         } else {
1320                 dist = vm_vec_dist_quick(p1, &point_segs[1].point);
1321                 dist += vm_vec_dist_quick(p0, &point_segs[num_points-2].point);
1322
1323                 for (i=1; i<num_points-2; i++) {
1324                         fix     ndist;
1325                         ndist = vm_vec_dist_quick(&point_segs[i].point, &point_segs[i+1].point);
1326                         dist += ndist;
1327                 }
1328
1329         }
1330
1331         Connected_segment_distance = num_points;
1332         add_to_fcd_cache(seg0, seg1, num_points, dist);
1333
1334         return dist;
1335
1336 }
1337
1338 sbyte convert_to_byte(fix f)
1339 {
1340         if (f >= 0x00010000)
1341                 return MATRIX_MAX;
1342         else if (f <= -0x00010000)
1343                 return -MATRIX_MAX;
1344         else
1345                 return f >> MATRIX_PRECISION;
1346 }
1347
1348 #define VEL_PRECISION 12
1349
1350 //      Create a shortpos struct from an object.
1351 //      Extract the matrix into byte values.
1352 //      Create a position relative to vertex 0 with 1/256 normal "fix" precision.
1353 //      Stuff segment in a short.
1354 void create_shortpos(shortpos *spp, object *objp, int swap_bytes)
1355 {
1356         // int  segnum;
1357         sbyte   *sp;
1358
1359         sp = spp->bytemat;
1360
1361         *sp++ = convert_to_byte(objp->orient.rvec.x);
1362         *sp++ = convert_to_byte(objp->orient.uvec.x);
1363         *sp++ = convert_to_byte(objp->orient.fvec.x);
1364         *sp++ = convert_to_byte(objp->orient.rvec.y);
1365         *sp++ = convert_to_byte(objp->orient.uvec.y);
1366         *sp++ = convert_to_byte(objp->orient.fvec.y);
1367         *sp++ = convert_to_byte(objp->orient.rvec.z);
1368         *sp++ = convert_to_byte(objp->orient.uvec.z);
1369         *sp++ = convert_to_byte(objp->orient.fvec.z);
1370
1371         spp->xo = (objp->pos.x - Vertices[Segments[objp->segnum].verts[0]].x) >> RELPOS_PRECISION;
1372         spp->yo = (objp->pos.y - Vertices[Segments[objp->segnum].verts[0]].y) >> RELPOS_PRECISION;
1373         spp->zo = (objp->pos.z - Vertices[Segments[objp->segnum].verts[0]].z) >> RELPOS_PRECISION;
1374
1375         spp->segment = objp->segnum;
1376
1377         spp->velx = (objp->mtype.phys_info.velocity.x) >> VEL_PRECISION;
1378         spp->vely = (objp->mtype.phys_info.velocity.y) >> VEL_PRECISION;
1379         spp->velz = (objp->mtype.phys_info.velocity.z) >> VEL_PRECISION;
1380
1381 // swap the short values for the big-endian machines.
1382
1383         if (swap_bytes) {
1384                 spp->xo = INTEL_SHORT(spp->xo);
1385                 spp->yo = INTEL_SHORT(spp->yo);
1386                 spp->zo = INTEL_SHORT(spp->zo);
1387                 spp->segment = INTEL_SHORT(spp->segment);
1388                 spp->velx = INTEL_SHORT(spp->velx);
1389                 spp->vely = INTEL_SHORT(spp->vely);
1390                 spp->velz = INTEL_SHORT(spp->velz);
1391         }
1392 //      mprintf((0, "Matrix: %08x %08x %08x    %08x %08x %08x\n", objp->orient.m1,objp->orient.m2,objp->orient.m3,
1393 //                                      spp->bytemat[0] << MATRIX_PRECISION,spp->bytemat[1] << MATRIX_PRECISION,spp->bytemat[2] << MATRIX_PRECISION));
1394 //
1395 //      mprintf((0, "        %08x %08x %08x    %08x %08x %08x\n", objp->orient.m4,objp->orient.m5,objp->orient.m6,
1396 //                                      spp->bytemat[3] << MATRIX_PRECISION,spp->bytemat[4] << MATRIX_PRECISION,spp->bytemat[5] << MATRIX_PRECISION));
1397 //
1398 //      mprintf((0, "        %08x %08x %08x    %08x %08x %08x\n", objp->orient.m7,objp->orient.m8,objp->orient.m9,
1399 //                                      spp->bytemat[6] << MATRIX_PRECISION,spp->bytemat[7] << MATRIX_PRECISION,spp->bytemat[8] << MATRIX_PRECISION));
1400 //
1401 //      mprintf((0, "Positn: %08x %08x %08x    %08x %08x %08x\n", objp->pos.x, objp->pos.y, objp->pos.z,
1402 //               (spp->xo << RELPOS_PRECISION) + Vertices[Segments[segnum].verts[0]].x,
1403 //               (spp->yo << RELPOS_PRECISION) + Vertices[Segments[segnum].verts[0]].y,
1404 //               (spp->zo << RELPOS_PRECISION) + Vertices[Segments[segnum].verts[0]].z));
1405 //      mprintf((0, "Segment: %3i    %3i\n", objp->segnum, spp->segment));
1406
1407 }
1408
1409 void extract_shortpos(object *objp, shortpos *spp, int swap_bytes)
1410 {
1411         int     segnum;
1412         sbyte   *sp;
1413
1414         sp = spp->bytemat;
1415
1416         objp->orient.rvec.x = *sp++ << MATRIX_PRECISION;
1417         objp->orient.uvec.x = *sp++ << MATRIX_PRECISION;
1418         objp->orient.fvec.x = *sp++ << MATRIX_PRECISION;
1419         objp->orient.rvec.y = *sp++ << MATRIX_PRECISION;
1420         objp->orient.uvec.y = *sp++ << MATRIX_PRECISION;
1421         objp->orient.fvec.y = *sp++ << MATRIX_PRECISION;
1422         objp->orient.rvec.z = *sp++ << MATRIX_PRECISION;
1423         objp->orient.uvec.z = *sp++ << MATRIX_PRECISION;
1424         objp->orient.fvec.z = *sp++ << MATRIX_PRECISION;
1425
1426         if (swap_bytes) {
1427                 spp->xo = INTEL_SHORT(spp->xo);
1428                 spp->yo = INTEL_SHORT(spp->yo);
1429                 spp->zo = INTEL_SHORT(spp->zo);
1430                 spp->segment = INTEL_SHORT(spp->segment);
1431                 spp->velx = INTEL_SHORT(spp->velx);
1432                 spp->vely = INTEL_SHORT(spp->vely);
1433                 spp->velz = INTEL_SHORT(spp->velz);
1434         }
1435
1436         segnum = spp->segment;
1437
1438         Assert((segnum >= 0) && (segnum <= Highest_segment_index));
1439
1440         objp->pos.x = (spp->xo << RELPOS_PRECISION) + Vertices[Segments[segnum].verts[0]].x;
1441         objp->pos.y = (spp->yo << RELPOS_PRECISION) + Vertices[Segments[segnum].verts[0]].y;
1442         objp->pos.z = (spp->zo << RELPOS_PRECISION) + Vertices[Segments[segnum].verts[0]].z;
1443
1444         objp->mtype.phys_info.velocity.x = (spp->velx << VEL_PRECISION);
1445         objp->mtype.phys_info.velocity.y = (spp->vely << VEL_PRECISION);
1446         objp->mtype.phys_info.velocity.z = (spp->velz << VEL_PRECISION);
1447
1448         obj_relink(objp-Objects, segnum);
1449
1450 //      mprintf((0, "Matrix: %08x %08x %08x    %08x %08x %08x\n", objp->orient.m1,objp->orient.m2,objp->orient.m3,
1451 //                                      spp->bytemat[0],spp->bytemat[1],spp->bytemat[2]));
1452 //
1453 //      mprintf((0, "        %08x %08x %08x    %08x %08x %08x\n", objp->orient.m4,objp->orient.m5,objp->orient.m6,
1454 //                                      spp->bytemat[3],spp->bytemat[4],spp->bytemat[5]));
1455 //
1456 //      mprintf((0, "        %08x %08x %08x    %08x %08x %08x\n", objp->orient.m7,objp->orient.m8,objp->orient.m9,
1457 //                                      spp->bytemat[6],spp->bytemat[7],spp->bytemat[8]));
1458 //
1459 //      mprintf((0, "Positn: %08x %08x %08x    %08x %08x %08x\n", objp->pos.x, objp->pos.y, objp->pos.z,
1460 //                      (spp->xo << RELPOS_PRECISION) + Vertices[Segments[segnum].verts[0]].x, (spp->yo << RELPOS_PRECISION) + Vertices[Segments[segnum].verts[0]].y, (spp->zo << RELPOS_PRECISION) + Vertices[Segments[segnum].verts[0]].z));
1461 //      mprintf((0, "Segment: %3i    %3i\n", objp->segnum, spp->segment));
1462
1463 }
1464
1465 //--unused-- void test_shortpos(void)
1466 //--unused-- {
1467 //--unused--    shortpos        spp;
1468 //--unused--
1469 //--unused--    create_shortpos(&spp, &Objects[0]);
1470 //--unused--    extract_shortpos(&Objects[0], &spp);
1471 //--unused--
1472 //--unused-- }
1473
1474 //      -----------------------------------------------------------------------------
1475 //      Segment validation functions.
1476 //      Moved from editor to game so we can compute surface normals at load time.
1477 // -------------------------------------------------------------------------------
1478
1479 // ------------------------------------------------------------------------------------------
1480 //      Extract a vector from a segment.  The vector goes from the start face to the end face.
1481 //      The point on each face is the average of the four points forming the face.
1482 void extract_vector_from_segment(segment *sp, vms_vector *vp, int start, int end)
1483 {
1484         int                     i;
1485         vms_vector      vs,ve;
1486
1487         vm_vec_zero(&vs);
1488         vm_vec_zero(&ve);
1489
1490         for (i=0; i<4; i++) {
1491                 vm_vec_add2(&vs,&Vertices[sp->verts[Side_to_verts[start][i]]]);
1492                 vm_vec_add2(&ve,&Vertices[sp->verts[Side_to_verts[end][i]]]);
1493         }
1494
1495         vm_vec_sub(vp,&ve,&vs);
1496         vm_vec_scale(vp,F1_0/4);
1497
1498 }
1499
1500 //create a matrix that describes the orientation of the given segment
1501 void extract_orient_from_segment(vms_matrix *m,segment *seg)
1502 {
1503         vms_vector fvec,uvec;
1504
1505         extract_vector_from_segment(seg,&fvec,WFRONT,WBACK);
1506         extract_vector_from_segment(seg,&uvec,WBOTTOM,WTOP);
1507
1508         //vector to matrix does normalizations and orthogonalizations
1509         vm_vector_2_matrix(m,&fvec,&uvec,NULL);
1510 }
1511
1512 #ifdef EDITOR
1513 // ------------------------------------------------------------------------------------------
1514 //      Extract the forward vector from segment *sp, return in *vp.
1515 //      The forward vector is defined to be the vector from the the center of the front face of the segment
1516 // to the center of the back face of the segment.
1517 void extract_forward_vector_from_segment(segment *sp,vms_vector *vp)
1518 {
1519         extract_vector_from_segment(sp,vp,WFRONT,WBACK);
1520 }
1521
1522 // ------------------------------------------------------------------------------------------
1523 //      Extract the right vector from segment *sp, return in *vp.
1524 //      The forward vector is defined to be the vector from the the center of the left face of the segment
1525 // to the center of the right face of the segment.
1526 void extract_right_vector_from_segment(segment *sp,vms_vector *vp)
1527 {
1528         extract_vector_from_segment(sp,vp,WLEFT,WRIGHT);
1529 }
1530
1531 // ------------------------------------------------------------------------------------------
1532 //      Extract the up vector from segment *sp, return in *vp.
1533 //      The forward vector is defined to be the vector from the the center of the bottom face of the segment
1534 // to the center of the top face of the segment.
1535 void extract_up_vector_from_segment(segment *sp,vms_vector *vp)
1536 {
1537         extract_vector_from_segment(sp,vp,WBOTTOM,WTOP);
1538 }
1539 #endif
1540
1541 void add_side_as_quad(segment *sp, int sidenum, vms_vector *normal)
1542 {
1543         side    *sidep = &sp->sides[sidenum];
1544
1545         sidep->type = SIDE_IS_QUAD;
1546
1547         #ifdef COMPACT_SEGS
1548                 normal = normal;                //avoid compiler warning
1549         #else
1550         sidep->normals[0] = *normal;
1551         sidep->normals[1] = *normal;
1552         #endif
1553
1554         //      If there is a connection here, we only formed the faces for the purpose of determining segment boundaries,
1555         //      so don't generate polys, else they will get rendered.
1556 //      if (sp->children[sidenum] != -1)
1557 //              sidep->render_flag = 0;
1558 //      else
1559 //              sidep->render_flag = 1;
1560
1561 }
1562
1563
1564 // -------------------------------------------------------------------------------
1565 //      Return v0, v1, v2 = 3 vertices with smallest numbers.  If *negate_flag set, then negate normal after computation.
1566 //      Note, you cannot just compute the normal by treating the points in the opposite direction as this introduces
1567 //      small differences between normals which should merely be opposites of each other.
1568 void get_verts_for_normal(int va, int vb, int vc, int vd, int *v0, int *v1, int *v2, int *v3, int *negate_flag)
1569 {
1570         int     i,j;
1571         int     v[4],w[4];
1572
1573         //      w is a list that shows how things got scrambled so we know if our normal is pointing backwards
1574         for (i=0; i<4; i++)
1575                 w[i] = i;
1576
1577         v[0] = va;
1578         v[1] = vb;
1579         v[2] = vc;
1580         v[3] = vd;
1581
1582         for (i=1; i<4; i++)
1583                 for (j=0; j<i; j++)
1584                         if (v[j] > v[i]) {
1585                                 int     t;
1586                                 t = v[j];       v[j] = v[i];    v[i] = t;
1587                                 t = w[j];       w[j] = w[i];    w[i] = t;
1588                         }
1589
1590         Assert((v[0] < v[1]) && (v[1] < v[2]) && (v[2] < v[3]));
1591
1592         //      Now, if for any w[i] & w[i+1]: w[i+1] = (w[i]+3)%4, then must swap
1593         *v0 = v[0];
1594         *v1 = v[1];
1595         *v2 = v[2];
1596         *v3 = v[3];
1597
1598         if ( (((w[0]+3) % 4) == w[1]) || (((w[1]+3) % 4) == w[2]))
1599                 *negate_flag = 1;
1600         else
1601                 *negate_flag = 0;
1602
1603 }
1604
1605 // -------------------------------------------------------------------------------
1606 void add_side_as_2_triangles(segment *sp, int sidenum)
1607 {
1608         vms_vector      norm;
1609         sbyte       *vs = Side_to_verts[sidenum];
1610         fix                     dot;
1611         vms_vector      vec_13;         //      vector from vertex 1 to vertex 3
1612
1613         side    *sidep = &sp->sides[sidenum];
1614
1615         //      Choose how to triangulate.
1616         //      If a wall, then
1617         //              Always triangulate so segment is convex.
1618         //              Use Matt's formula: Na . AD > 0, where ABCD are vertices on side, a is face formed by A,B,C, Na is normal from face a.
1619         //      If not a wall, then triangulate so whatever is on the other side is triangulated the same (ie, between the same absoluate vertices)
1620         if (!IS_CHILD(sp->children[sidenum])) {
1621                 vm_vec_normal(&norm,  &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[2]]]);
1622                 vm_vec_sub(&vec_13, &Vertices[sp->verts[vs[3]]], &Vertices[sp->verts[vs[1]]]);
1623                 dot = vm_vec_dot(&norm, &vec_13);
1624
1625                 //      Now, signifiy whether to triangulate from 0:2 or 1:3
1626                 if (dot >= 0)
1627                         sidep->type = SIDE_IS_TRI_02;
1628                 else
1629                         sidep->type = SIDE_IS_TRI_13;
1630
1631                 #ifndef COMPACT_SEGS
1632                 //      Now, based on triangulation type, set the normals.
1633                 if (sidep->type == SIDE_IS_TRI_02) {
1634                         vm_vec_normal(&norm,  &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[2]]]);
1635                         sidep->normals[0] = norm;
1636                         vm_vec_normal(&norm, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[2]]], &Vertices[sp->verts[vs[3]]]);
1637                         sidep->normals[1] = norm;
1638                 } else {
1639                         vm_vec_normal(&norm, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[3]]]);
1640                         sidep->normals[0] = norm;
1641                         vm_vec_normal(&norm, &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[2]]], &Vertices[sp->verts[vs[3]]]);
1642                         sidep->normals[1] = norm;
1643                 }
1644                 #endif
1645         } else {
1646                 int     i,v[4], vsorted[4];
1647                 int     negate_flag;
1648
1649                 for (i=0; i<4; i++)
1650                         v[i] = sp->verts[vs[i]];
1651
1652                 get_verts_for_normal(v[0], v[1], v[2], v[3], &vsorted[0], &vsorted[1], &vsorted[2], &vsorted[3], &negate_flag);
1653
1654                 if ((vsorted[0] == v[0]) || (vsorted[0] == v[2])) {
1655                         sidep->type = SIDE_IS_TRI_02;
1656                         #ifndef COMPACT_SEGS
1657                         //      Now, get vertices for normal for each triangle based on triangulation type.
1658                         get_verts_for_normal(v[0], v[1], v[2], 32767, &vsorted[0], &vsorted[1], &vsorted[2], &vsorted[3], &negate_flag);
1659                         vm_vec_normal(&norm,  &Vertices[vsorted[0]], &Vertices[vsorted[1]], &Vertices[vsorted[2]]);
1660                         if (negate_flag)
1661                                 vm_vec_negate(&norm);
1662                         sidep->normals[0] = norm;
1663
1664                         get_verts_for_normal(v[0], v[2], v[3], 32767, &vsorted[0], &vsorted[1], &vsorted[2], &vsorted[3], &negate_flag);
1665                         vm_vec_normal(&norm,  &Vertices[vsorted[0]], &Vertices[vsorted[1]], &Vertices[vsorted[2]]);
1666                         if (negate_flag)
1667                                 vm_vec_negate(&norm);
1668                         sidep->normals[1] = norm;
1669                         #endif
1670                 } else {
1671                         sidep->type = SIDE_IS_TRI_13;
1672                         #ifndef COMPACT_SEGS
1673                         //      Now, get vertices for normal for each triangle based on triangulation type.
1674                         get_verts_for_normal(v[0], v[1], v[3], 32767, &vsorted[0], &vsorted[1], &vsorted[2], &vsorted[3], &negate_flag);
1675                         vm_vec_normal(&norm,  &Vertices[vsorted[0]], &Vertices[vsorted[1]], &Vertices[vsorted[2]]);
1676                         if (negate_flag)
1677                                 vm_vec_negate(&norm);
1678                         sidep->normals[0] = norm;
1679
1680                         get_verts_for_normal(v[1], v[2], v[3], 32767, &vsorted[0], &vsorted[1], &vsorted[2], &vsorted[3], &negate_flag);
1681                         vm_vec_normal(&norm,  &Vertices[vsorted[0]], &Vertices[vsorted[1]], &Vertices[vsorted[2]]);
1682                         if (negate_flag)
1683                                 vm_vec_negate(&norm);
1684                         sidep->normals[1] = norm;
1685                         #endif
1686                 }
1687         }
1688 }
1689
1690 int sign(fix v)
1691 {
1692
1693         if (v > PLANE_DIST_TOLERANCE)
1694                 return 1;
1695         else if (v < -(PLANE_DIST_TOLERANCE+1))         //neg & pos round differently
1696                 return -1;
1697         else
1698                 return 0;
1699 }
1700
1701 // -------------------------------------------------------------------------------
1702 void create_walls_on_side(segment *sp, int sidenum)
1703 {
1704         int     vm0, vm1, vm2, vm3, negate_flag;
1705         int     v0, v1, v2, v3;
1706         vms_vector vn;
1707         fix     dist_to_plane;
1708
1709         v0 = sp->verts[Side_to_verts[sidenum][0]];
1710         v1 = sp->verts[Side_to_verts[sidenum][1]];
1711         v2 = sp->verts[Side_to_verts[sidenum][2]];
1712         v3 = sp->verts[Side_to_verts[sidenum][3]];
1713
1714         get_verts_for_normal(v0, v1, v2, v3, &vm0, &vm1, &vm2, &vm3, &negate_flag);
1715
1716         vm_vec_normal(&vn, &Vertices[vm0], &Vertices[vm1], &Vertices[vm2]);
1717         dist_to_plane = abs(vm_dist_to_plane(&Vertices[vm3], &vn, &Vertices[vm0]));
1718
1719 //if ((sp-Segments == 0x7b) && (sidenum == 3)) {
1720 //      mprintf((0, "Verts = %3i %3i %3i %3i, negate flag = %3i, dist = %8x\n", vm0, vm1, vm2, vm3, negate_flag, dist_to_plane));
1721 //      mprintf((0, "  Normal = %8x %8x %8x\n", vn.x, vn.y, vn.z));
1722 //      mprintf((0, "   Vert %3i = [%8x %8x %8x]\n", vm0, Vertices[vm0].x, Vertices[vm0].y, Vertices[vm0].z));
1723 //      mprintf((0, "   Vert %3i = [%8x %8x %8x]\n", vm1, Vertices[vm1].x, Vertices[vm1].y, Vertices[vm1].z));
1724 //      mprintf((0, "   Vert %3i = [%8x %8x %8x]\n", vm2, Vertices[vm2].x, Vertices[vm2].y, Vertices[vm2].z));
1725 //      mprintf((0, "   Vert %3i = [%8x %8x %8x]\n", vm3, Vertices[vm3].x, Vertices[vm3].y, Vertices[vm3].z));
1726 //}
1727
1728 //if ((sp-Segments == 0x86) && (sidenum == 5)) {
1729 //      mprintf((0, "Verts = %3i %3i %3i %3i, negate flag = %3i, dist = %8x\n", vm0, vm1, vm2, vm3, negate_flag, dist_to_plane));
1730 //      mprintf((0, "  Normal = %8x %8x %8x\n", vn.x, vn.y, vn.z));
1731 //      mprintf((0, "   Vert %3i = [%8x %8x %8x]\n", vm0, Vertices[vm0].x, Vertices[vm0].y, Vertices[vm0].z));
1732 //      mprintf((0, "   Vert %3i = [%8x %8x %8x]\n", vm1, Vertices[vm1].x, Vertices[vm1].y, Vertices[vm1].z));
1733 //      mprintf((0, "   Vert %3i = [%8x %8x %8x]\n", vm2, Vertices[vm2].x, Vertices[vm2].y, Vertices[vm2].z));
1734 //      mprintf((0, "   Vert %3i = [%8x %8x %8x]\n", vm3, Vertices[vm3].x, Vertices[vm3].y, Vertices[vm3].z));
1735 //}
1736
1737         if (negate_flag)
1738                 vm_vec_negate(&vn);
1739
1740         if (dist_to_plane <= PLANE_DIST_TOLERANCE)
1741                 add_side_as_quad(sp, sidenum, &vn);
1742         else {
1743                 add_side_as_2_triangles(sp, sidenum);
1744
1745                 //this code checks to see if we really should be triangulated, and
1746                 //de-triangulates if we shouldn't be.
1747
1748                 {
1749                         int                     num_faces;
1750                         int                     vertex_list[6];
1751                         fix                     dist0,dist1;
1752                         int                     s0,s1;
1753                         int                     vertnum;
1754                         side                    *s;
1755
1756                         create_abs_vertex_lists( &num_faces, vertex_list, sp-Segments, sidenum);
1757
1758                         Assert(num_faces == 2);
1759
1760                         s = &sp->sides[sidenum];
1761
1762                         vertnum = min(vertex_list[0],vertex_list[2]);
1763
1764                         #ifdef COMPACT_SEGS
1765                         {
1766                         vms_vector normals[2];
1767                         get_side_normals(sp, sidenum, &normals[0], &normals[1] );
1768                         dist0 = vm_dist_to_plane(&Vertices[vertex_list[1]],&normals[1],&Vertices[vertnum]);
1769                         dist1 = vm_dist_to_plane(&Vertices[vertex_list[4]],&normals[0],&Vertices[vertnum]);
1770                         }
1771                         #else
1772                         dist0 = vm_dist_to_plane(&Vertices[vertex_list[1]],&s->normals[1],&Vertices[vertnum]);
1773                         dist1 = vm_dist_to_plane(&Vertices[vertex_list[4]],&s->normals[0],&Vertices[vertnum]);
1774                         #endif
1775
1776                         s0 = sign(dist0);
1777                         s1 = sign(dist1);
1778
1779                         if (s0==0 || s1==0 || s0!=s1) {
1780                                 sp->sides[sidenum].type = SIDE_IS_QUAD;         //detriangulate!
1781                                 #ifndef COMPACT_SEGS
1782                                 sp->sides[sidenum].normals[0] = vn;
1783                                 sp->sides[sidenum].normals[1] = vn;
1784                                 #endif
1785                         }
1786
1787                 }
1788         }
1789
1790 }
1791
1792
1793 #ifdef COMPACT_SEGS
1794
1795 //#define CACHE_DEBUG 1
1796 #define MAX_CACHE_NORMALS 128
1797 #define CACHE_MASK 127
1798
1799 typedef struct ncache_element {
1800         short segnum;
1801         ubyte sidenum;
1802         vms_vector normals[2];
1803 } ncache_element;
1804
1805 int ncache_initialized = 0;
1806 ncache_element ncache[MAX_CACHE_NORMALS];
1807
1808 #ifdef CACHE_DEBUG
1809 int ncache_counter = 0;
1810 int ncache_hits = 0;
1811 int ncache_misses = 0;
1812 #endif
1813
1814 void ncache_init()
1815 {
1816         ncache_flush();
1817         ncache_initialized = 1;
1818 }
1819
1820 void ncache_flush()
1821 {
1822         int i;
1823         for (i=0; i<MAX_CACHE_NORMALS; i++ )    {
1824                 ncache[i].segnum = -1;
1825         }
1826 }
1827
1828
1829
1830 // -------------------------------------------------------------------------------
1831 int find_ncache_element( int segnum, int sidenum, int face_flags )
1832 {
1833         uint i;
1834
1835         if (!ncache_initialized) ncache_init();
1836
1837 #ifdef CACHE_DEBUG
1838         if (((++ncache_counter % 5000)==1) && (ncache_hits+ncache_misses > 0))
1839                 mprintf(( 0, "NCACHE %d%% missed, H:%d, M:%d\n", (ncache_misses*100)/(ncache_hits+ncache_misses), ncache_hits, ncache_misses ));
1840 #endif
1841
1842         i = ((segnum<<2) ^ sidenum) & CACHE_MASK;
1843
1844         if ((ncache[i].segnum == segnum) && ((ncache[i].sidenum&0xf)==sidenum) )        {
1845                 uint f1;
1846 #ifdef CACHE_DEBUG
1847                 ncache_hits++;
1848 #endif
1849                 f1 = ncache[i].sidenum>>4;
1850                 if ( (f1&face_flags)==face_flags )
1851                         return i;
1852                 if ( f1 & 1 )
1853                         uncached_get_side_normal( &Segments[segnum], sidenum, 1, &ncache[i].normals[1] );
1854                 else
1855                         uncached_get_side_normal( &Segments[segnum], sidenum, 0, &ncache[i].normals[0] );
1856                 ncache[i].sidenum |= face_flags<<4;
1857                 return i;
1858         }
1859 #ifdef CACHE_DEBUG
1860         ncache_misses++;
1861 #endif
1862
1863         switch( face_flags )    {
1864         case 1:
1865                 uncached_get_side_normal( &Segments[segnum], sidenum, 0, &ncache[i].normals[0] );
1866                 break;
1867         case 2:
1868                 uncached_get_side_normal( &Segments[segnum], sidenum, 1, &ncache[i].normals[1] );
1869                 break;
1870         case 3:
1871                 uncached_get_side_normals(&Segments[segnum], sidenum, &ncache[i].normals[0], &ncache[i].normals[1] );
1872                 break;
1873         }
1874         ncache[i].segnum = segnum;
1875         ncache[i].sidenum = sidenum | (face_flags<<4);
1876         return i;
1877 }
1878
1879 void get_side_normal(segment *sp, int sidenum, int face_num, vms_vector * vm )
1880 {
1881         int i;
1882         i = find_ncache_element( sp - Segments, sidenum, 1 << face_num );
1883         *vm = ncache[i].normals[face_num];
1884         if (0) {
1885                 vms_vector tmp;
1886                 uncached_get_side_normal(sp, sidenum, face_num, &tmp );
1887                 Assert( tmp.x == vm->x );
1888                 Assert( tmp.y == vm->y );
1889                 Assert( tmp.z == vm->z );
1890         }
1891 }
1892
1893 void get_side_normals(segment *sp, int sidenum, vms_vector * vm1, vms_vector * vm2 )
1894 {
1895         int i;
1896         i = find_ncache_element( sp - Segments, sidenum, 3 );
1897         *vm1 = ncache[i].normals[0];
1898         *vm2 = ncache[i].normals[1];
1899
1900         if (0) {
1901                 vms_vector tmp;
1902                 uncached_get_side_normal(sp, sidenum, 0, &tmp );
1903                 Assert( tmp.x == vm1->x );
1904                 Assert( tmp.y == vm1->y );
1905                 Assert( tmp.z == vm1->z );
1906                 uncached_get_side_normal(sp, sidenum, 1, &tmp );
1907                 Assert( tmp.x == vm2->x );
1908                 Assert( tmp.y == vm2->y );
1909                 Assert( tmp.z == vm2->z );
1910         }
1911
1912 }
1913
1914 void uncached_get_side_normal(segment *sp, int sidenum, int face_num, vms_vector * vm )
1915 {
1916         int     vm0, vm1, vm2, vm3, negate_flag;
1917         char    *vs = Side_to_verts[sidenum];
1918
1919         switch( sp->sides[sidenum].type )       {
1920         case SIDE_IS_QUAD:
1921                 get_verts_for_normal(sp->verts[vs[0]], sp->verts[vs[1]], sp->verts[vs[2]], sp->verts[vs[3]], &vm0, &vm1, &vm2, &vm3, &negate_flag);
1922                 vm_vec_normal(vm, &Vertices[vm0], &Vertices[vm1], &Vertices[vm2]);
1923                 if (negate_flag)
1924                         vm_vec_negate(vm);
1925                 break;
1926         case SIDE_IS_TRI_02:
1927                 if ( face_num == 0 )
1928                         vm_vec_normal(vm, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[2]]]);
1929                 else
1930                         vm_vec_normal(vm, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[2]]], &Vertices[sp->verts[vs[3]]]);
1931                 break;
1932         case SIDE_IS_TRI_13:
1933                 if ( face_num == 0 )
1934                         vm_vec_normal(vm, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[3]]]);
1935                 else
1936                         vm_vec_normal(vm, &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[2]]], &Vertices[sp->verts[vs[3]]]);
1937                 break;
1938         }
1939 }
1940
1941 void uncached_get_side_normals(segment *sp, int sidenum, vms_vector * vm1, vms_vector * vm2 )
1942 {
1943         int     vvm0, vvm1, vvm2, vvm3, negate_flag;
1944         char    *vs = Side_to_verts[sidenum];
1945
1946         switch( sp->sides[sidenum].type )       {
1947         case SIDE_IS_QUAD:
1948                 get_verts_for_normal(sp->verts[vs[0]], sp->verts[vs[1]], sp->verts[vs[2]], sp->verts[vs[3]], &vvm0, &vvm1, &vvm2, &vvm3, &negate_flag);
1949                 vm_vec_normal(vm1, &Vertices[vvm0], &Vertices[vvm1], &Vertices[vvm2]);
1950                 if (negate_flag)
1951                         vm_vec_negate(vm1);
1952                 *vm2 = *vm1;
1953                 break;
1954         case SIDE_IS_TRI_02:
1955                 vm_vec_normal(vm1, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[2]]]);
1956                 vm_vec_normal(vm2, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[2]]], &Vertices[sp->verts[vs[3]]]);
1957                 break;
1958         case SIDE_IS_TRI_13:
1959                 vm_vec_normal(vm1, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[3]]]);
1960                 vm_vec_normal(vm2, &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[2]]], &Vertices[sp->verts[vs[3]]]);
1961                 break;
1962         }
1963 }
1964
1965 #endif
1966
1967 // -------------------------------------------------------------------------------
1968 void validate_removable_wall(segment *sp, int sidenum, int tmap_num)
1969 {
1970         create_walls_on_side(sp, sidenum);
1971
1972         sp->sides[sidenum].tmap_num = tmap_num;
1973
1974 //      assign_default_uvs_to_side(sp, sidenum);
1975 //      assign_light_to_side(sp, sidenum);
1976 }
1977
1978 // -------------------------------------------------------------------------------
1979 //      Make a just-modified segment side valid.
1980 void validate_segment_side(segment *sp, int sidenum)
1981 {
1982         if (sp->sides[sidenum].wall_num == -1)
1983                 create_walls_on_side(sp, sidenum);
1984         else
1985                 // create_removable_wall(sp, sidenum, sp->sides[sidenum].tmap_num);
1986                 validate_removable_wall(sp, sidenum, sp->sides[sidenum].tmap_num);
1987
1988         //      Set render_flag.
1989         //      If side doesn't have a child, then render wall.  If it does have a child, but there is a temporary
1990         //      wall there, then do render wall.
1991 //      if (sp->children[sidenum] == -1)
1992 //              sp->sides[sidenum].render_flag = 1;
1993 //      else if (sp->sides[sidenum].wall_num != -1)
1994 //              sp->sides[sidenum].render_flag = 1;
1995 //      else
1996 //              sp->sides[sidenum].render_flag = 0;
1997 }
1998
1999 extern int check_for_degenerate_segment(segment *sp);
2000
2001 // -------------------------------------------------------------------------------
2002 //      Make a just-modified segment valid.
2003 //              check all sides to see how many faces they each should have (0,1,2)
2004 //              create new vector normals
2005 void validate_segment(segment *sp)
2006 {
2007         int     side;
2008
2009         #ifdef EDITOR
2010         check_for_degenerate_segment(sp);
2011         #endif
2012
2013         for (side = 0; side < MAX_SIDES_PER_SEGMENT; side++)
2014                 validate_segment_side(sp, side);
2015
2016 //      assign_default_uvs_to_segment(sp);
2017 }
2018
2019 // -------------------------------------------------------------------------------
2020 //      Validate all segments.
2021 //      Highest_segment_index must be set.
2022 //      For all used segments (number <= Highest_segment_index), segnum field must be != -1.
2023 void validate_segment_all(void)
2024 {
2025         int     s;
2026
2027         for (s=0; s<=Highest_segment_index; s++)
2028                 #ifdef EDITOR
2029                 if (Segments[s].segnum != -1)
2030                 #endif
2031                         validate_segment(&Segments[s]);
2032
2033         #ifdef EDITOR
2034         {
2035                 int said=0;
2036                 for (s=Highest_segment_index+1; s<MAX_SEGMENTS; s++)
2037                         if (Segments[s].segnum != -1) {
2038                                 if (!said) {
2039                                         mprintf((0, "Segment %i has invalid segnum.  Bashing to -1.  Silently bashing all others...", s));
2040                                 }
2041                                 said++;
2042                                 Segments[s].segnum = -1;
2043                         }
2044
2045                 if (said)
2046                         mprintf((0, "%i fixed.\n", said));
2047         }
2048         #endif
2049
2050         #ifndef NDEBUG
2051         #ifndef COMPACT_SEGS
2052         if (check_segment_connections())
2053                 Int3();         //Get Matt, si vous plait.
2054         #endif
2055         #endif
2056 }
2057
2058
2059 //      ------------------------------------------------------------------------------------------------------
2060 //      Picks a random point in a segment like so:
2061 //              From center, go up to 50% of way towards any of the 8 vertices.
2062 void pick_random_point_in_seg(vms_vector *new_pos, int segnum)
2063 {
2064         int                     vnum;
2065         vms_vector      vec2;
2066
2067         compute_segment_center(new_pos, &Segments[segnum]);
2068         vnum = (rand() * MAX_VERTICES_PER_SEGMENT) >> 15;
2069         vm_vec_sub(&vec2, &Vertices[Segments[segnum].verts[vnum]], new_pos);
2070         vm_vec_scale(&vec2, rand());                    //      rand() always in 0..1/2
2071         vm_vec_add2(new_pos, &vec2);
2072 }
2073
2074
2075 //      ----------------------------------------------------------------------------------------------------------
2076 //      Set the segment depth of all segments from start_seg in *segbuf.
2077 //      Returns maximum depth value.
2078 int set_segment_depths(int start_seg, ubyte *segbuf)
2079 {
2080         int     i, curseg;
2081         ubyte   visited[MAX_SEGMENTS];
2082         int     queue[MAX_SEGMENTS];
2083         int     head, tail;
2084         int     depth;
2085         int     parent_depth=0;
2086
2087         depth = 1;
2088         head = 0;
2089         tail = 0;
2090
2091         for (i=0; i<=Highest_segment_index; i++)
2092                 visited[i] = 0;
2093
2094         if (segbuf[start_seg] == 0)
2095                 return 1;
2096
2097         queue[tail++] = start_seg;
2098         visited[start_seg] = 1;
2099         segbuf[start_seg] = depth++;
2100
2101         if (depth == 0)
2102                 depth = 255;
2103
2104         while (head < tail) {
2105                 curseg = queue[head++];
2106                 parent_depth = segbuf[curseg];
2107
2108                 for (i=0; i<MAX_SIDES_PER_SEGMENT; i++) {
2109                         int     childnum;
2110
2111                         childnum = Segments[curseg].children[i];
2112                         if (childnum != -1)
2113                                 if (segbuf[childnum])
2114                                         if (!visited[childnum]) {
2115                                                 visited[childnum] = 1;
2116                                                 segbuf[childnum] = parent_depth+1;
2117                                                 queue[tail++] = childnum;
2118                                         }
2119                 }
2120         }
2121
2122         return parent_depth+1;
2123 }
2124
2125 //these constants should match the ones in seguvs
2126 #define LIGHT_DISTANCE_THRESHOLD        (F1_0*80)
2127 #define Magical_light_constant  (F1_0*16)
2128
2129 #define MAX_CHANGED_SEGS 30
2130 short changed_segs[MAX_CHANGED_SEGS];
2131 int n_changed_segs;
2132
2133 //      ------------------------------------------------------------------------------------------
2134 //cast static light from a segment to nearby segments
2135 void apply_light_to_segment(segment *segp,vms_vector *segment_center, fix light_intensity,int recursion_depth)
2136 {
2137         vms_vector      r_segment_center;
2138         fix                     dist_to_rseg;
2139         int                     i,segnum=segp-Segments,sidenum;
2140
2141         for (i=0;i<n_changed_segs;i++)
2142                 if (changed_segs[i] == segnum)
2143                         break;
2144
2145         if (i == n_changed_segs) {
2146                 compute_segment_center(&r_segment_center, segp);
2147                 dist_to_rseg = vm_vec_dist_quick(&r_segment_center, segment_center);
2148
2149                 if (dist_to_rseg <= LIGHT_DISTANCE_THRESHOLD) {
2150                         fix     light_at_point;
2151                         if (dist_to_rseg > F1_0)
2152                                 light_at_point = fixdiv(Magical_light_constant, dist_to_rseg);
2153                         else
2154                                 light_at_point = Magical_light_constant;
2155
2156                         if (light_at_point >= 0) {
2157                                 segment2        *seg2p  = &Segment2s[segnum];
2158                                 light_at_point = fixmul(light_at_point, light_intensity);
2159                                 if (light_at_point >= F1_0)
2160                                         light_at_point = F1_0-1;
2161                                 if (light_at_point <= -F1_0)
2162                                         light_at_point = -(F1_0-1);
2163                                 seg2p->static_light += light_at_point;
2164                                 if (seg2p->static_light < 0)    // if it went negative, saturate
2165                                         seg2p->static_light = 0;
2166                         }       //      end if (light_at_point...
2167                 }       //      end if (dist_to_rseg...
2168
2169                 changed_segs[n_changed_segs++] = segnum;
2170         }
2171
2172         if (recursion_depth < 2)
2173                 for (sidenum=0; sidenum<6; sidenum++) {
2174                         if (WALL_IS_DOORWAY(segp,sidenum) & WID_RENDPAST_FLAG)
2175                                 apply_light_to_segment(&Segments[segp->children[sidenum]],segment_center,light_intensity,recursion_depth+1);
2176                 }
2177
2178 }
2179
2180
2181 extern object *old_viewer;
2182
2183 //update the static_light field in a segment, which is used for object lighting
2184 //this code is copied from the editor routine calim_process_all_lights()
2185 void change_segment_light(int segnum,int sidenum,int dir)
2186 {
2187         segment *segp = &Segments[segnum];
2188
2189         if (WALL_IS_DOORWAY(segp, sidenum) & WID_RENDER_FLAG) {
2190                 side    *sidep = &segp->sides[sidenum];
2191                 fix     light_intensity;
2192
2193                 light_intensity = TmapInfo[sidep->tmap_num].lighting + TmapInfo[sidep->tmap_num2 & 0x3fff].lighting;
2194
2195                 light_intensity *= dir;
2196
2197                 n_changed_segs = 0;
2198
2199                 if (light_intensity) {
2200                         vms_vector      segment_center;
2201                         compute_segment_center(&segment_center, segp);
2202                         apply_light_to_segment(segp,&segment_center,light_intensity,0);
2203                 }
2204         }
2205
2206         //this is a horrible hack to get around the horrible hack used to
2207         //smooth lighting values when an object moves between segments
2208         old_viewer = NULL;
2209
2210 }
2211
2212 //      ------------------------------------------------------------------------------------------
2213 //      dir = +1 -> add light
2214 //      dir = -1 -> subtract light
2215 //      dir = 17 -> add 17x light
2216 //      dir =  0 -> you are dumb
2217 void change_light(int segnum, int sidenum, int dir)
2218 {
2219         int     i, j, k;
2220
2221         for (i=0; i<Num_static_lights; i++) {
2222                 if ((Dl_indices[i].segnum == segnum) && (Dl_indices[i].sidenum == sidenum)) {
2223                         delta_light     *dlp;
2224                         dlp = &Delta_lights[Dl_indices[i].index];
2225
2226                         for (j=0; j<Dl_indices[i].count; j++) {
2227                                 for (k=0; k<4; k++) {
2228                                         fix     dl,new_l;
2229                                         dl = dir * dlp->vert_light[k] * DL_SCALE;
2230                                         Assert((dlp->segnum >= 0) && (dlp->segnum <= Highest_segment_index));
2231                                         Assert((dlp->sidenum >= 0) && (dlp->sidenum < MAX_SIDES_PER_SEGMENT));
2232                                         new_l = (Segments[dlp->segnum].sides[dlp->sidenum].uvls[k].l += dl);
2233                                         if (new_l < 0)
2234                                                 Segments[dlp->segnum].sides[dlp->sidenum].uvls[k].l = 0;
2235                                 }
2236                                 dlp++;
2237                         }
2238                 }
2239         }
2240
2241         //recompute static light for segment
2242         change_segment_light(segnum,sidenum,dir);
2243 }
2244
2245 //      Subtract light cast by a light source from all surfaces to which it applies light.
2246 //      This is precomputed data, stored at static light application time in the editor (the slow lighting function).
2247 // returns 1 if lights actually subtracted, else 0
2248 int subtract_light(int segnum, int sidenum)
2249 {
2250         if (Light_subtracted[segnum] & (1 << sidenum)) {
2251                 //mprintf((0, "Warning: Trying to subtract light from a source twice!\n"));
2252                 return 0;
2253         }
2254
2255         Light_subtracted[segnum] |= (1 << sidenum);
2256         change_light(segnum, sidenum, -1);
2257         return 1;
2258 }
2259
2260 //      Add light cast by a light source from all surfaces to which it applies light.
2261 //      This is precomputed data, stored at static light application time in the editor (the slow lighting function).
2262 //      You probably only want to call this after light has been subtracted.
2263 // returns 1 if lights actually added, else 0
2264 int add_light(int segnum, int sidenum)
2265 {
2266         if (!(Light_subtracted[segnum] & (1 << sidenum))) {
2267                 //mprintf((0, "Warning: Trying to add light which has never been subtracted!\n"));
2268                 return 0;
2269         }
2270
2271         Light_subtracted[segnum] &= ~(1 << sidenum);
2272         change_light(segnum, sidenum, 1);
2273         return 1;
2274 }
2275
2276 //      Light_subtracted[i] contains bit indicators for segment #i.
2277 //      If bit n (1 << n) is set, then side #n in segment #i has had light subtracted from original (editor-computed) value.
2278 ubyte   Light_subtracted[MAX_SEGMENTS];
2279
2280 //      Parse the Light_subtracted array, turning on or off all lights.
2281 void apply_all_changed_light(void)
2282 {
2283         int     i,j;
2284
2285         for (i=0; i<=Highest_segment_index; i++) {
2286                 for (j=0; j<MAX_SIDES_PER_SEGMENT; j++)
2287                         if (Light_subtracted[i] & (1 << j))
2288                                 change_light(i, j, -1);
2289         }
2290 }
2291
2292 //@@//  Scans Light_subtracted bit array.
2293 //@@//  For all light sources which have had their light subtracted, adds light back in.
2294 //@@void restore_all_lights_in_mine(void)
2295 //@@{
2296 //@@    int     i, j, k;
2297 //@@
2298 //@@    for (i=0; i<Num_static_lights; i++) {
2299 //@@            int     segnum, sidenum;
2300 //@@            delta_light     *dlp;
2301 //@@
2302 //@@            segnum = Dl_indices[i].segnum;
2303 //@@            sidenum = Dl_indices[i].sidenum;
2304 //@@            if (Light_subtracted[segnum] & (1 << sidenum)) {
2305 //@@                    dlp = &Delta_lights[Dl_indices[i].index];
2306 //@@
2307 //@@                    Light_subtracted[segnum] &= ~(1 << sidenum);
2308 //@@                    for (j=0; j<Dl_indices[i].count; j++) {
2309 //@@                            for (k=0; k<4; k++) {
2310 //@@                                    fix     dl;
2311 //@@                                    dl = dlp->vert_light[k] * DL_SCALE;
2312 //@@                                    Assert((dlp->segnum >= 0) && (dlp->segnum <= Highest_segment_index));
2313 //@@                                    Assert((dlp->sidenum >= 0) && (dlp->sidenum < MAX_SIDES_PER_SEGMENT));
2314 //@@                                    Segments[dlp->segnum].sides[dlp->sidenum].uvls[k].l += dl;
2315 //@@                            }
2316 //@@                            dlp++;
2317 //@@                    }
2318 //@@            }
2319 //@@    }
2320 //@@}
2321
2322 //      Should call this whenever a new mine gets loaded.
2323 //      More specifically, should call this whenever something global happens
2324 //      to change the status of static light in the mine.
2325 void clear_light_subtracted(void)
2326 {
2327         int     i;
2328
2329         for (i=0; i<=Highest_segment_index; i++)
2330                 Light_subtracted[i] = 0;
2331
2332 }
2333
2334 //      -----------------------------------------------------------------------------
2335 fix find_connected_distance_segments( int seg0, int seg1, int depth, int wid_flag)
2336 {
2337         vms_vector      p0, p1;
2338
2339         compute_segment_center(&p0, &Segments[seg0]);
2340         compute_segment_center(&p1, &Segments[seg1]);
2341
2342         return find_connected_distance(&p0, seg0, &p1, seg1, depth, wid_flag);
2343 }
2344
2345 #define AMBIENT_SEGMENT_DEPTH           5
2346
2347 //      -----------------------------------------------------------------------------
2348 //      Do a bfs from segnum, marking slots in marked_segs if the segment is reachable.
2349 void ambient_mark_bfs(int segnum, sbyte *marked_segs, int depth)
2350 {
2351         int     i;
2352
2353         if (depth < 0)
2354                 return;
2355
2356         marked_segs[segnum] = 1;
2357
2358         for (i=0; i<MAX_SIDES_PER_SEGMENT; i++) {
2359                 int     child = Segments[segnum].children[i];
2360
2361                 if (IS_CHILD(child) && (WALL_IS_DOORWAY(&Segments[segnum],i) & WID_RENDPAST_FLAG) && !marked_segs[child])
2362                         ambient_mark_bfs(child, marked_segs, depth-1);
2363         }
2364
2365 }
2366
2367 //      -----------------------------------------------------------------------------
2368 //      Indicate all segments which are within audible range of falling water or lava,
2369 //      and so should hear ambient gurgles.
2370 void set_ambient_sound_flags_common(int tmi_bit, int s2f_bit)
2371 {
2372         int     i, j;
2373         sbyte   marked_segs[MAX_SEGMENTS];
2374
2375         //      Now, all segments containing ambient lava or water sound makers are flagged.
2376         //      Additionally flag all segments which are within range of them.
2377         for (i=0; i<=Highest_segment_index; i++) {
2378                 marked_segs[i] = 0;
2379                 Segment2s[i].s2_flags &= ~s2f_bit;
2380         }
2381
2382         //      Mark all segments which are sources of the sound.
2383         for (i=0; i<=Highest_segment_index; i++) {
2384                 segment *segp = &Segments[i];
2385                 segment2        *seg2p = &Segment2s[i];
2386
2387                 for (j=0; j<MAX_SIDES_PER_SEGMENT; j++) {
2388                         side    *sidep = &segp->sides[j];
2389
2390                         if ((TmapInfo[sidep->tmap_num].flags & tmi_bit) || (TmapInfo[sidep->tmap_num2 & 0x3fff].flags & tmi_bit)) {
2391                                 if (!IS_CHILD(segp->children[j]) || (sidep->wall_num != -1)) {
2392                                         seg2p->s2_flags |= s2f_bit;
2393                                         marked_segs[i] = 1;             //      Say it's itself that it is close enough to to hear something.
2394                                 }
2395                         }
2396
2397                 }
2398
2399         }
2400
2401         //      Next mark all segments within N segments of a source.
2402         for (i=0; i<=Highest_segment_index; i++) {
2403                 segment2        *seg2p = &Segment2s[i];
2404
2405                 if (seg2p->s2_flags & s2f_bit)
2406                         ambient_mark_bfs(i, marked_segs, AMBIENT_SEGMENT_DEPTH);
2407         }
2408
2409         //      Now, flip bits in all segments which can hear the ambient sound.
2410         for (i=0; i<=Highest_segment_index; i++)
2411                 if (marked_segs[i])
2412                         Segment2s[i].s2_flags |= s2f_bit;
2413
2414 }
2415
2416
2417 //      -----------------------------------------------------------------------------
2418 //      Indicate all segments which are within audible range of falling water or lava,
2419 //      and so should hear ambient gurgles.
2420 //      Bashes values in Segment2s array.
2421 void set_ambient_sound_flags(void)
2422 {
2423         set_ambient_sound_flags_common(TMI_VOLATILE, S2F_AMBIENT_LAVA);
2424         set_ambient_sound_flags_common(TMI_WATER, S2F_AMBIENT_WATER);
2425 }