main/gameseg.c

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