66bfefad62a843064fecb657e1c1387189b24a7d
[btb/d2x.git] / main / gameseg.c
1 /* $Id: gameseg.c,v 1.10 2004-09-05 12:07:01 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.10 2004-09-05 12:07:01 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.
747 // Would be better to pass a paremeter 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, int recursion_count)
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 ubyte visited [MAX_SEGMENTS];
760
761         Assert((oldsegnum <= Highest_segment_index) && (oldsegnum >= 0));
762
763         if (recursion_count >= Num_segments) {
764                 con_printf (CON_DEBUG, "trace_segs: Segment not found\n");
765                 mprintf ((0,"trace_segs (gameseg.c): Error: infinite loop\n"));
766                 return -1;
767         }
768         if (recursion_count == 0)
769                 memset (visited, 0, sizeof (visited));
770         if (visited [oldsegnum])
771                 return -1;
772         visited [oldsegnum] = 1;
773
774         centermask = get_side_dists(p0,oldsegnum,side_dists);           //check old segment
775         if (centermask == 0) // we are in the old segment
776                 return oldsegnum; //..say so
777
778         for (;;) {
779                 seg = &Segments[oldsegnum];
780                 biggest_side = -1;
781                 biggest_val = 0;
782                 for (sidenum = 0, bit = 1; sidenum < 6; sidenum++, bit <<= 1)
783                         if ((centermask & bit) && (seg->children[sidenum] > -1)
784                             && side_dists[sidenum] < biggest_val) {
785                                 biggest_val = side_dists[sidenum];
786                                 biggest_side = sidenum;
787                         }
788
789                         if (biggest_side == -1)
790                                 break;
791
792                         side_dists[biggest_side] = 0;
793                         // trace into adjacent segment:
794                         check = trace_segs(p0, seg->children[biggest_side], recursion_count + 1);
795                         if (check >= 0)         //we've found a segment
796                                 return check;
797         }
798         return -1;              //we haven't found a segment
799 }
800
801
802 int     Exhaustive_count=0, Exhaustive_failed_count=0;
803
804 //Tries to find a segment for a point, in the following way:
805 // 1. Check the given segment
806 // 2. Recursively trace through attached segments
807 // 3. Check all the segmentns
808 //Returns segnum if found, or -1
809 int find_point_seg(vms_vector *p,int segnum)
810 {
811         int newseg;
812
813         //allow segnum==-1, meaning we have no idea what segment point is in
814         Assert((segnum <= Highest_segment_index) && (segnum >= -1));
815
816         if (segnum != -1) {
817                 newseg = trace_segs(p, segnum, 0);
818
819                 if (newseg != -1)                       //we found a segment!
820                         return newseg;
821         }
822
823         //couldn't find via attached segs, so search all segs
824
825         //      MK: 10/15/94
826         //      This Doing_lighting_hack_flag thing added by mk because the hundreds of scrolling messages were
827         //      slowing down lighting, and in about 98% of cases, it would just return -1 anyway.
828         //      Matt: This really should be fixed, though.  We're probably screwing up our lighting in a few places.
829         if (!Doing_lighting_hack_flag) {
830                 mprintf((1,"Warning: doing exhaustive search to find point segment (%i times)\n", ++Exhaustive_count));
831
832                 for (newseg=0;newseg <= Highest_segment_index;newseg++)
833                         if (get_seg_masks(p, newseg, 0, __FILE__, __LINE__).centermask == 0)
834                                 return newseg;
835
836                 mprintf((1,"Warning: could not find point segment (%i times)\n", ++Exhaustive_failed_count));
837
838                 return -1;              //no segment found
839         } else
840                 return -1;
841 }
842
843
844 //--repair-- // ------------------------------------------------------------------------------
845 //--repair-- void clsd_repair_center(int segnum)
846 //--repair-- {
847 //--repair--    int     sidenum;
848 //--repair--
849 //--repair--    //      --- Set repair center bit for all repair center segments.
850 //--repair--    if (Segments[segnum].special == SEGMENT_IS_REPAIRCEN) {
851 //--repair--            Lsegments[segnum].special_type |= SS_REPAIR_CENTER;
852 //--repair--            Lsegments[segnum].special_segment = segnum;
853 //--repair--    }
854 //--repair--
855 //--repair--    //      --- Set repair center bit for all segments adjacent to a repair center.
856 //--repair--    for (sidenum=0; sidenum < MAX_SIDES_PER_SEGMENT; sidenum++) {
857 //--repair--            int     s = Segments[segnum].children[sidenum];
858 //--repair--
859 //--repair--            if ( (s != -1) && (Segments[s].special==SEGMENT_IS_REPAIRCEN) ) {
860 //--repair--                    Lsegments[segnum].special_type |= SS_REPAIR_CENTER;
861 //--repair--                    Lsegments[segnum].special_segment = s;
862 //--repair--            }
863 //--repair--    }
864 //--repair-- }
865
866 //--repair-- // ------------------------------------------------------------------------------
867 //--repair-- // --- Set destination points for all Materialization centers.
868 //--repair-- void clsd_materialization_center(int segnum)
869 //--repair-- {
870 //--repair--    if (Segments[segnum].special == SEGMENT_IS_ROBOTMAKER) {
871 //--repair--
872 //--repair--    }
873 //--repair-- }
874 //--repair--
875 //--repair-- int        Lsegment_highest_segment_index, Lsegment_highest_vertex_index;
876 //--repair--
877 //--repair-- // ------------------------------------------------------------------------------
878 //--repair-- // Create data specific to mine which doesn't get written to disk.
879 //--repair-- // Highest_segment_index and Highest_object_index must be valid.
880 //--repair-- // 07/21:  set repair center bit
881 //--repair-- void create_local_segment_data(void)
882 //--repair-- {
883 //--repair--    int     segnum;
884 //--repair--
885 //--repair--    //      --- Initialize all Lsegments.
886 //--repair--    for (segnum=0; segnum <= Highest_segment_index; segnum++) {
887 //--repair--            Lsegments[segnum].special_type = 0;
888 //--repair--            Lsegments[segnum].special_segment = -1;
889 //--repair--    }
890 //--repair--
891 //--repair--    for (segnum=0; segnum <= Highest_segment_index; segnum++) {
892 //--repair--
893 //--repair--            clsd_repair_center(segnum);
894 //--repair--            clsd_materialization_center(segnum);
895 //--repair--    
896 //--repair--    }
897 //--repair--
898 //--repair--    //      Set check variables.
899 //--repair--    //      In main game loop, make sure these are valid, else Lsegments is not valid.
900 //--repair--    Lsegment_highest_segment_index = Highest_segment_index;
901 //--repair--    Lsegment_highest_vertex_index = Highest_vertex_index;
902 //--repair-- }
903 //--repair--
904 //--repair-- // ------------------------------------------------------------------------------------------
905 //--repair-- // Sort of makes sure create_local_segment_data has been called for the currently executing mine.
906 //--repair-- // It is not failsafe, as you will see if you look at the code.
907 //--repair-- // Returns 1 if Lsegments appears valid, 0 if not.
908 //--repair-- int check_lsegments_validity(void)
909 //--repair-- {
910 //--repair--    return ((Lsegment_highest_segment_index == Highest_segment_index) && (Lsegment_highest_vertex_index == Highest_vertex_index));
911 //--repair-- }
912
913 #define MAX_LOC_POINT_SEGS      64
914
915 int     Connected_segment_distance;
916
917 #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.
918 #define MAX_FCD_CACHE   8
919
920 typedef struct {
921         int     seg0, seg1, csd;
922         fix     dist;
923 } fcd_data;
924
925 int     Fcd_index = 0;
926 fcd_data Fcd_cache[MAX_FCD_CACHE];
927 fix     Last_fcd_flush_time;
928
929 //      ----------------------------------------------------------------------------------------------------------
930 void flush_fcd_cache(void)
931 {
932         int     i;
933
934         Fcd_index = 0;
935
936         for (i=0; i<MAX_FCD_CACHE; i++)
937                 Fcd_cache[i].seg0 = -1;
938 }
939
940 //      ----------------------------------------------------------------------------------------------------------
941 void add_to_fcd_cache(int seg0, int seg1, int depth, fix dist)
942 {
943         if (dist > MIN_CACHE_FCD_DIST) {
944                 Fcd_cache[Fcd_index].seg0 = seg0;
945                 Fcd_cache[Fcd_index].seg1 = seg1;
946                 Fcd_cache[Fcd_index].csd = depth;
947                 Fcd_cache[Fcd_index].dist = dist;
948
949                 Fcd_index++;
950
951                 if (Fcd_index >= MAX_FCD_CACHE)
952                         Fcd_index = 0;
953
954                 // -- mprintf((0, "Adding seg0=%i, seg1=%i to cache.\n", seg0, seg1));
955         } else {
956                 //      If it's in the cache, remove it.
957                 int     i;
958
959                 for (i=0; i<MAX_FCD_CACHE; i++)
960                         if (Fcd_cache[i].seg0 == seg0)
961                                 if (Fcd_cache[i].seg1 == seg1) {
962                                         Fcd_cache[Fcd_index].seg0 = -1;
963                                         break;
964                                 }
965         }
966
967 }
968
969 //      ----------------------------------------------------------------------------------------------------------
970 //      Determine whether seg0 and seg1 are reachable in a way that allows sound to pass.
971 //      Search up to a maximum depth of max_depth.
972 //      Return the distance.
973 fix find_connected_distance(vms_vector *p0, int seg0, vms_vector *p1, int seg1, int max_depth, int wid_flag)
974 {
975         int             cur_seg;
976         int             sidenum;
977         int             qtail = 0, qhead = 0;
978         int             i;
979         sbyte   visited[MAX_SEGMENTS];
980         seg_seg seg_queue[MAX_SEGMENTS];
981         short           depth[MAX_SEGMENTS];
982         int             cur_depth;
983         int             num_points;
984         point_seg       point_segs[MAX_LOC_POINT_SEGS];
985         fix             dist;
986
987         //      If > this, will overrun point_segs buffer
988 #ifdef WINDOWS
989         if (max_depth == -1) max_depth = 200;
990 #endif  
991
992         if (max_depth > MAX_LOC_POINT_SEGS-2) {
993                 mprintf((1, "Warning: In find_connected_distance, max_depth = %i, limited to %i\n", max_depth, MAX_LOC_POINT_SEGS-2));
994                 max_depth = MAX_LOC_POINT_SEGS-2;
995         }
996
997         if (seg0 == seg1) {
998                 Connected_segment_distance = 0;
999                 return vm_vec_dist_quick(p0, p1);
1000         } else {
1001                 int     conn_side;
1002                 if ((conn_side = find_connect_side(&Segments[seg0], &Segments[seg1])) != -1) {
1003                         if (WALL_IS_DOORWAY(&Segments[seg1], conn_side) & wid_flag) {
1004                                 Connected_segment_distance = 1;
1005                                 //mprintf((0, "\n"));
1006                                 return vm_vec_dist_quick(p0, p1);
1007                         }
1008                 }
1009         }
1010
1011         //      Periodically flush cache.
1012         if ((GameTime - Last_fcd_flush_time > F1_0*2) || (GameTime < Last_fcd_flush_time)) {
1013                 flush_fcd_cache();
1014                 Last_fcd_flush_time = GameTime;
1015         }
1016
1017         //      Can't quickly get distance, so see if in Fcd_cache.
1018         for (i=0; i<MAX_FCD_CACHE; i++)
1019                 if ((Fcd_cache[i].seg0 == seg0) && (Fcd_cache[i].seg1 == seg1)) {
1020                         Connected_segment_distance = Fcd_cache[i].csd;
1021                         // -- mprintf((0, "In cache, seg0=%i, seg1=%i.  Returning.\n", seg0, seg1));
1022                         return Fcd_cache[i].dist;
1023                 }
1024
1025         num_points = 0;
1026
1027         memset(visited, 0, Highest_segment_index+1);
1028         memset(depth, 0, sizeof(depth[0]) * (Highest_segment_index+1));
1029
1030         cur_seg = seg0;
1031         visited[cur_seg] = 1;
1032         cur_depth = 0;
1033
1034         while (cur_seg != seg1) {
1035                 segment *segp = &Segments[cur_seg];
1036
1037                 for (sidenum = 0; sidenum < MAX_SIDES_PER_SEGMENT; sidenum++) {
1038
1039                         int     snum = sidenum;
1040
1041                         if (WALL_IS_DOORWAY(segp, snum) & wid_flag) {
1042                                 int     this_seg = segp->children[snum];
1043
1044                                 if (!visited[this_seg]) {
1045                                         seg_queue[qtail].start = cur_seg;
1046                                         seg_queue[qtail].end = this_seg;
1047                                         visited[this_seg] = 1;
1048                                         depth[qtail++] = cur_depth+1;
1049                                         if (max_depth != -1) {
1050                                                 if (depth[qtail-1] == max_depth) {
1051                                                         Connected_segment_distance = 1000;
1052                                                         add_to_fcd_cache(seg0, seg1, Connected_segment_distance, F1_0*1000);
1053                                                         return -1;
1054                                                 }
1055                                         } else if (this_seg == seg1) {
1056                                                 goto fcd_done1;
1057                                         }
1058                                 }
1059
1060                         }
1061                 }       //      for (sidenum...
1062
1063                 if (qhead >= qtail) {
1064                         Connected_segment_distance = 1000;
1065                         add_to_fcd_cache(seg0, seg1, Connected_segment_distance, F1_0*1000);
1066                         return -1;
1067                 }
1068
1069                 cur_seg = seg_queue[qhead].end;
1070                 cur_depth = depth[qhead];
1071                 qhead++;
1072
1073 fcd_done1: ;
1074         }       //      while (cur_seg ...
1075
1076         //      Set qtail to the segment which ends at the goal.
1077         while (seg_queue[--qtail].end != seg1)
1078                 if (qtail < 0) {
1079                         Connected_segment_distance = 1000;
1080                         add_to_fcd_cache(seg0, seg1, Connected_segment_distance, F1_0*1000);
1081                         return -1;
1082                 }
1083
1084         while (qtail >= 0) {
1085                 int     parent_seg, this_seg;
1086
1087                 this_seg = seg_queue[qtail].end;
1088                 parent_seg = seg_queue[qtail].start;
1089                 point_segs[num_points].segnum = this_seg;
1090                 compute_segment_center(&point_segs[num_points].point,&Segments[this_seg]);
1091                 num_points++;
1092
1093                 if (parent_seg == seg0)
1094                         break;
1095
1096                 while (seg_queue[--qtail].end != parent_seg)
1097                         Assert(qtail >= 0);
1098         }
1099
1100         point_segs[num_points].segnum = seg0;
1101         compute_segment_center(&point_segs[num_points].point,&Segments[seg0]);
1102         num_points++;
1103
1104         if (num_points == 1) {
1105                 Connected_segment_distance = num_points;
1106                 return vm_vec_dist_quick(p0, p1);
1107         } else {
1108                 dist = vm_vec_dist_quick(p1, &point_segs[1].point);
1109                 dist += vm_vec_dist_quick(p0, &point_segs[num_points-2].point);
1110
1111                 for (i=1; i<num_points-2; i++) {
1112                         fix     ndist;
1113                         ndist = vm_vec_dist_quick(&point_segs[i].point, &point_segs[i+1].point);
1114                         dist += ndist;
1115                 }
1116
1117         }
1118
1119         Connected_segment_distance = num_points;
1120         add_to_fcd_cache(seg0, seg1, num_points, dist);
1121
1122         return dist;
1123
1124 }
1125
1126 sbyte convert_to_byte(fix f)
1127 {
1128         if (f >= 0x00010000)
1129                 return MATRIX_MAX;
1130         else if (f <= -0x00010000)
1131                 return -MATRIX_MAX;
1132         else
1133                 return f >> MATRIX_PRECISION;
1134 }
1135
1136 #define VEL_PRECISION 12
1137
1138 //      Create a shortpos struct from an object.
1139 //      Extract the matrix into byte values.
1140 //      Create a position relative to vertex 0 with 1/256 normal "fix" precision.
1141 //      Stuff segment in a short.
1142 void create_shortpos(shortpos *spp, object *objp, int swap_bytes)
1143 {
1144         // int  segnum;
1145         sbyte   *sp;
1146
1147         sp = spp->bytemat;
1148
1149         *sp++ = convert_to_byte(objp->orient.rvec.x);
1150         *sp++ = convert_to_byte(objp->orient.uvec.x);
1151         *sp++ = convert_to_byte(objp->orient.fvec.x);
1152         *sp++ = convert_to_byte(objp->orient.rvec.y);
1153         *sp++ = convert_to_byte(objp->orient.uvec.y);
1154         *sp++ = convert_to_byte(objp->orient.fvec.y);
1155         *sp++ = convert_to_byte(objp->orient.rvec.z);
1156         *sp++ = convert_to_byte(objp->orient.uvec.z);
1157         *sp++ = convert_to_byte(objp->orient.fvec.z);
1158
1159         spp->xo = (objp->pos.x - Vertices[Segments[objp->segnum].verts[0]].x) >> RELPOS_PRECISION;
1160         spp->yo = (objp->pos.y - Vertices[Segments[objp->segnum].verts[0]].y) >> RELPOS_PRECISION;
1161         spp->zo = (objp->pos.z - Vertices[Segments[objp->segnum].verts[0]].z) >> RELPOS_PRECISION;
1162
1163         spp->segment = objp->segnum;
1164
1165         spp->velx = (objp->mtype.phys_info.velocity.x) >> VEL_PRECISION;
1166         spp->vely = (objp->mtype.phys_info.velocity.y) >> VEL_PRECISION;
1167         spp->velz = (objp->mtype.phys_info.velocity.z) >> VEL_PRECISION;
1168
1169 // swap the short values for the big-endian machines.
1170
1171         if (swap_bytes) {
1172                 spp->xo = INTEL_SHORT(spp->xo);
1173                 spp->yo = INTEL_SHORT(spp->yo);
1174                 spp->zo = INTEL_SHORT(spp->zo);
1175                 spp->segment = INTEL_SHORT(spp->segment);
1176                 spp->velx = INTEL_SHORT(spp->velx);
1177                 spp->vely = INTEL_SHORT(spp->vely);
1178                 spp->velz = INTEL_SHORT(spp->velz);
1179         }
1180 //      mprintf((0, "Matrix: %08x %08x %08x    %08x %08x %08x\n", objp->orient.m1,objp->orient.m2,objp->orient.m3,
1181 //                                      spp->bytemat[0] << MATRIX_PRECISION,spp->bytemat[1] << MATRIX_PRECISION,spp->bytemat[2] << MATRIX_PRECISION));
1182 //
1183 //      mprintf((0, "        %08x %08x %08x    %08x %08x %08x\n", objp->orient.m4,objp->orient.m5,objp->orient.m6,
1184 //                                      spp->bytemat[3] << MATRIX_PRECISION,spp->bytemat[4] << MATRIX_PRECISION,spp->bytemat[5] << MATRIX_PRECISION));
1185 //
1186 //      mprintf((0, "        %08x %08x %08x    %08x %08x %08x\n", objp->orient.m7,objp->orient.m8,objp->orient.m9,
1187 //                                      spp->bytemat[6] << MATRIX_PRECISION,spp->bytemat[7] << MATRIX_PRECISION,spp->bytemat[8] << MATRIX_PRECISION));
1188 //
1189 //      mprintf((0, "Positn: %08x %08x %08x    %08x %08x %08x\n", objp->pos.x, objp->pos.y, objp->pos.z,
1190 //               (spp->xo << RELPOS_PRECISION) + Vertices[Segments[segnum].verts[0]].x,
1191 //               (spp->yo << RELPOS_PRECISION) + Vertices[Segments[segnum].verts[0]].y,
1192 //               (spp->zo << RELPOS_PRECISION) + Vertices[Segments[segnum].verts[0]].z));
1193 //      mprintf((0, "Segment: %3i    %3i\n", objp->segnum, spp->segment));
1194
1195 }
1196
1197 void extract_shortpos(object *objp, shortpos *spp, int swap_bytes)
1198 {
1199         int     segnum;
1200         sbyte   *sp;
1201
1202         sp = spp->bytemat;
1203
1204         objp->orient.rvec.x = *sp++ << MATRIX_PRECISION;
1205         objp->orient.uvec.x = *sp++ << MATRIX_PRECISION;
1206         objp->orient.fvec.x = *sp++ << MATRIX_PRECISION;
1207         objp->orient.rvec.y = *sp++ << MATRIX_PRECISION;
1208         objp->orient.uvec.y = *sp++ << MATRIX_PRECISION;
1209         objp->orient.fvec.y = *sp++ << MATRIX_PRECISION;
1210         objp->orient.rvec.z = *sp++ << MATRIX_PRECISION;
1211         objp->orient.uvec.z = *sp++ << MATRIX_PRECISION;
1212         objp->orient.fvec.z = *sp++ << MATRIX_PRECISION;
1213
1214         if (swap_bytes) {
1215                 spp->xo = INTEL_SHORT(spp->xo);
1216                 spp->yo = INTEL_SHORT(spp->yo);
1217                 spp->zo = INTEL_SHORT(spp->zo);
1218                 spp->segment = INTEL_SHORT(spp->segment);
1219                 spp->velx = INTEL_SHORT(spp->velx);
1220                 spp->vely = INTEL_SHORT(spp->vely);
1221                 spp->velz = INTEL_SHORT(spp->velz);
1222         }
1223
1224         segnum = spp->segment;
1225
1226         Assert((segnum >= 0) && (segnum <= Highest_segment_index));
1227
1228         objp->pos.x = (spp->xo << RELPOS_PRECISION) + Vertices[Segments[segnum].verts[0]].x;
1229         objp->pos.y = (spp->yo << RELPOS_PRECISION) + Vertices[Segments[segnum].verts[0]].y;
1230         objp->pos.z = (spp->zo << RELPOS_PRECISION) + Vertices[Segments[segnum].verts[0]].z;
1231
1232         objp->mtype.phys_info.velocity.x = (spp->velx << VEL_PRECISION);
1233         objp->mtype.phys_info.velocity.y = (spp->vely << VEL_PRECISION);
1234         objp->mtype.phys_info.velocity.z = (spp->velz << VEL_PRECISION);
1235
1236         obj_relink(objp-Objects, segnum);
1237
1238 //      mprintf((0, "Matrix: %08x %08x %08x    %08x %08x %08x\n", objp->orient.m1,objp->orient.m2,objp->orient.m3,
1239 //                                      spp->bytemat[0],spp->bytemat[1],spp->bytemat[2]));
1240 //
1241 //      mprintf((0, "        %08x %08x %08x    %08x %08x %08x\n", objp->orient.m4,objp->orient.m5,objp->orient.m6,
1242 //                                      spp->bytemat[3],spp->bytemat[4],spp->bytemat[5]));
1243 //
1244 //      mprintf((0, "        %08x %08x %08x    %08x %08x %08x\n", objp->orient.m7,objp->orient.m8,objp->orient.m9,
1245 //                                      spp->bytemat[6],spp->bytemat[7],spp->bytemat[8]));
1246 //
1247 //      mprintf((0, "Positn: %08x %08x %08x    %08x %08x %08x\n", objp->pos.x, objp->pos.y, objp->pos.z,
1248 //                      (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));
1249 //      mprintf((0, "Segment: %3i    %3i\n", objp->segnum, spp->segment));
1250
1251 }
1252
1253 //--unused-- void test_shortpos(void)
1254 //--unused-- {
1255 //--unused--    shortpos        spp;
1256 //--unused--
1257 //--unused--    create_shortpos(&spp, &Objects[0]);
1258 //--unused--    extract_shortpos(&Objects[0], &spp);
1259 //--unused--
1260 //--unused-- }
1261
1262 //      -----------------------------------------------------------------------------
1263 //      Segment validation functions.
1264 //      Moved from editor to game so we can compute surface normals at load time.
1265 // -------------------------------------------------------------------------------
1266
1267 // ------------------------------------------------------------------------------------------
1268 //      Extract a vector from a segment.  The vector goes from the start face to the end face.
1269 //      The point on each face is the average of the four points forming the face.
1270 void extract_vector_from_segment(segment *sp, vms_vector *vp, int start, int end)
1271 {
1272         int                     i;
1273         vms_vector      vs,ve;
1274
1275         vm_vec_zero(&vs);
1276         vm_vec_zero(&ve);
1277
1278         for (i=0; i<4; i++) {
1279                 vm_vec_add2(&vs,&Vertices[sp->verts[Side_to_verts[start][i]]]);
1280                 vm_vec_add2(&ve,&Vertices[sp->verts[Side_to_verts[end][i]]]);
1281         }
1282
1283         vm_vec_sub(vp,&ve,&vs);
1284         vm_vec_scale(vp,F1_0/4);
1285
1286 }
1287
1288 //create a matrix that describes the orientation of the given segment
1289 void extract_orient_from_segment(vms_matrix *m,segment *seg)
1290 {
1291         vms_vector fvec,uvec;
1292
1293         extract_vector_from_segment(seg,&fvec,WFRONT,WBACK);
1294         extract_vector_from_segment(seg,&uvec,WBOTTOM,WTOP);
1295
1296         //vector to matrix does normalizations and orthogonalizations
1297         vm_vector_2_matrix(m,&fvec,&uvec,NULL);
1298 }
1299
1300 #ifdef EDITOR
1301 // ------------------------------------------------------------------------------------------
1302 //      Extract the forward vector from segment *sp, return in *vp.
1303 //      The forward vector is defined to be the vector from the the center of the front face of the segment
1304 // to the center of the back face of the segment.
1305 void extract_forward_vector_from_segment(segment *sp,vms_vector *vp)
1306 {
1307         extract_vector_from_segment(sp,vp,WFRONT,WBACK);
1308 }
1309
1310 // ------------------------------------------------------------------------------------------
1311 //      Extract the right vector from segment *sp, return in *vp.
1312 //      The forward vector is defined to be the vector from the the center of the left face of the segment
1313 // to the center of the right face of the segment.
1314 void extract_right_vector_from_segment(segment *sp,vms_vector *vp)
1315 {
1316         extract_vector_from_segment(sp,vp,WLEFT,WRIGHT);
1317 }
1318
1319 // ------------------------------------------------------------------------------------------
1320 //      Extract the up vector from segment *sp, return in *vp.
1321 //      The forward vector is defined to be the vector from the the center of the bottom face of the segment
1322 // to the center of the top face of the segment.
1323 void extract_up_vector_from_segment(segment *sp,vms_vector *vp)
1324 {
1325         extract_vector_from_segment(sp,vp,WBOTTOM,WTOP);
1326 }
1327 #endif
1328
1329 void add_side_as_quad(segment *sp, int sidenum, vms_vector *normal)
1330 {
1331         side    *sidep = &sp->sides[sidenum];
1332
1333         sidep->type = SIDE_IS_QUAD;
1334
1335         #ifdef COMPACT_SEGS
1336                 normal = normal;                //avoid compiler warning
1337         #else
1338         sidep->normals[0] = *normal;
1339         sidep->normals[1] = *normal;
1340         #endif
1341
1342         //      If there is a connection here, we only formed the faces for the purpose of determining segment boundaries,
1343         //      so don't generate polys, else they will get rendered.
1344 //      if (sp->children[sidenum] != -1)
1345 //              sidep->render_flag = 0;
1346 //      else
1347 //              sidep->render_flag = 1;
1348
1349 }
1350
1351
1352 // -------------------------------------------------------------------------------
1353 //      Return v0, v1, v2 = 3 vertices with smallest numbers.  If *negate_flag set, then negate normal after computation.
1354 //      Note, you cannot just compute the normal by treating the points in the opposite direction as this introduces
1355 //      small differences between normals which should merely be opposites of each other.
1356 void get_verts_for_normal(int va, int vb, int vc, int vd, int *v0, int *v1, int *v2, int *v3, int *negate_flag)
1357 {
1358         int     i,j;
1359         int     v[4],w[4];
1360
1361         //      w is a list that shows how things got scrambled so we know if our normal is pointing backwards
1362         for (i=0; i<4; i++)
1363                 w[i] = i;
1364
1365         v[0] = va;
1366         v[1] = vb;
1367         v[2] = vc;
1368         v[3] = vd;
1369
1370         for (i=1; i<4; i++)
1371                 for (j=0; j<i; j++)
1372                         if (v[j] > v[i]) {
1373                                 int     t;
1374                                 t = v[j];       v[j] = v[i];    v[i] = t;
1375                                 t = w[j];       w[j] = w[i];    w[i] = t;
1376                         }
1377
1378         Assert((v[0] < v[1]) && (v[1] < v[2]) && (v[2] < v[3]));
1379
1380         //      Now, if for any w[i] & w[i+1]: w[i+1] = (w[i]+3)%4, then must swap
1381         *v0 = v[0];
1382         *v1 = v[1];
1383         *v2 = v[2];
1384         *v3 = v[3];
1385
1386         if ( (((w[0]+3) % 4) == w[1]) || (((w[1]+3) % 4) == w[2]))
1387                 *negate_flag = 1;
1388         else
1389                 *negate_flag = 0;
1390
1391 }
1392
1393 // -------------------------------------------------------------------------------
1394 void add_side_as_2_triangles(segment *sp, int sidenum)
1395 {
1396         vms_vector      norm;
1397         sbyte       *vs = Side_to_verts[sidenum];
1398         fix                     dot;
1399         vms_vector      vec_13;         //      vector from vertex 1 to vertex 3
1400
1401         side    *sidep = &sp->sides[sidenum];
1402
1403         //      Choose how to triangulate.
1404         //      If a wall, then
1405         //              Always triangulate so segment is convex.
1406         //              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.
1407         //      If not a wall, then triangulate so whatever is on the other side is triangulated the same (ie, between the same absoluate vertices)
1408         if (!IS_CHILD(sp->children[sidenum])) {
1409                 vm_vec_normal(&norm,  &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[2]]]);
1410                 vm_vec_sub(&vec_13, &Vertices[sp->verts[vs[3]]], &Vertices[sp->verts[vs[1]]]);
1411                 dot = vm_vec_dot(&norm, &vec_13);
1412
1413                 //      Now, signifiy whether to triangulate from 0:2 or 1:3
1414                 if (dot >= 0)
1415                         sidep->type = SIDE_IS_TRI_02;
1416                 else
1417                         sidep->type = SIDE_IS_TRI_13;
1418
1419                 #ifndef COMPACT_SEGS
1420                 //      Now, based on triangulation type, set the normals.
1421                 if (sidep->type == SIDE_IS_TRI_02) {
1422                         vm_vec_normal(&norm,  &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[2]]]);
1423                         sidep->normals[0] = norm;
1424                         vm_vec_normal(&norm, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[2]]], &Vertices[sp->verts[vs[3]]]);
1425                         sidep->normals[1] = norm;
1426                 } else {
1427                         vm_vec_normal(&norm, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[3]]]);
1428                         sidep->normals[0] = norm;
1429                         vm_vec_normal(&norm, &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[2]]], &Vertices[sp->verts[vs[3]]]);
1430                         sidep->normals[1] = norm;
1431                 }
1432                 #endif
1433         } else {
1434                 int     i,v[4], vsorted[4];
1435                 int     negate_flag;
1436
1437                 for (i=0; i<4; i++)
1438                         v[i] = sp->verts[vs[i]];
1439
1440                 get_verts_for_normal(v[0], v[1], v[2], v[3], &vsorted[0], &vsorted[1], &vsorted[2], &vsorted[3], &negate_flag);
1441
1442                 if ((vsorted[0] == v[0]) || (vsorted[0] == v[2])) {
1443                         sidep->type = SIDE_IS_TRI_02;
1444                         #ifndef COMPACT_SEGS
1445                         //      Now, get vertices for normal for each triangle based on triangulation type.
1446                         get_verts_for_normal(v[0], v[1], v[2], 32767, &vsorted[0], &vsorted[1], &vsorted[2], &vsorted[3], &negate_flag);
1447                         vm_vec_normal(&norm,  &Vertices[vsorted[0]], &Vertices[vsorted[1]], &Vertices[vsorted[2]]);
1448                         if (negate_flag)
1449                                 vm_vec_negate(&norm);
1450                         sidep->normals[0] = norm;
1451
1452                         get_verts_for_normal(v[0], v[2], v[3], 32767, &vsorted[0], &vsorted[1], &vsorted[2], &vsorted[3], &negate_flag);
1453                         vm_vec_normal(&norm,  &Vertices[vsorted[0]], &Vertices[vsorted[1]], &Vertices[vsorted[2]]);
1454                         if (negate_flag)
1455                                 vm_vec_negate(&norm);
1456                         sidep->normals[1] = norm;
1457                         #endif
1458                 } else {
1459                         sidep->type = SIDE_IS_TRI_13;
1460                         #ifndef COMPACT_SEGS
1461                         //      Now, get vertices for normal for each triangle based on triangulation type.
1462                         get_verts_for_normal(v[0], v[1], v[3], 32767, &vsorted[0], &vsorted[1], &vsorted[2], &vsorted[3], &negate_flag);
1463                         vm_vec_normal(&norm,  &Vertices[vsorted[0]], &Vertices[vsorted[1]], &Vertices[vsorted[2]]);
1464                         if (negate_flag)
1465                                 vm_vec_negate(&norm);
1466                         sidep->normals[0] = norm;
1467
1468                         get_verts_for_normal(v[1], v[2], v[3], 32767, &vsorted[0], &vsorted[1], &vsorted[2], &vsorted[3], &negate_flag);
1469                         vm_vec_normal(&norm,  &Vertices[vsorted[0]], &Vertices[vsorted[1]], &Vertices[vsorted[2]]);
1470                         if (negate_flag)
1471                                 vm_vec_negate(&norm);
1472                         sidep->normals[1] = norm;
1473                         #endif
1474                 }
1475         }
1476 }
1477
1478 int sign(fix v)
1479 {
1480
1481         if (v > PLANE_DIST_TOLERANCE)
1482                 return 1;
1483         else if (v < -(PLANE_DIST_TOLERANCE+1))         //neg & pos round differently
1484                 return -1;
1485         else
1486                 return 0;
1487 }
1488
1489 // -------------------------------------------------------------------------------
1490 void create_walls_on_side(segment *sp, int sidenum)
1491 {
1492         int     vm0, vm1, vm2, vm3, negate_flag;
1493         int     v0, v1, v2, v3;
1494         vms_vector vn;
1495         fix     dist_to_plane;
1496
1497         v0 = sp->verts[Side_to_verts[sidenum][0]];
1498         v1 = sp->verts[Side_to_verts[sidenum][1]];
1499         v2 = sp->verts[Side_to_verts[sidenum][2]];
1500         v3 = sp->verts[Side_to_verts[sidenum][3]];
1501
1502         get_verts_for_normal(v0, v1, v2, v3, &vm0, &vm1, &vm2, &vm3, &negate_flag);
1503
1504         vm_vec_normal(&vn, &Vertices[vm0], &Vertices[vm1], &Vertices[vm2]);
1505         dist_to_plane = abs(vm_dist_to_plane(&Vertices[vm3], &vn, &Vertices[vm0]));
1506
1507 //if ((sp-Segments == 0x7b) && (sidenum == 3)) {
1508 //      mprintf((0, "Verts = %3i %3i %3i %3i, negate flag = %3i, dist = %8x\n", vm0, vm1, vm2, vm3, negate_flag, dist_to_plane));
1509 //      mprintf((0, "  Normal = %8x %8x %8x\n", vn.x, vn.y, vn.z));
1510 //      mprintf((0, "   Vert %3i = [%8x %8x %8x]\n", vm0, Vertices[vm0].x, Vertices[vm0].y, Vertices[vm0].z));
1511 //      mprintf((0, "   Vert %3i = [%8x %8x %8x]\n", vm1, Vertices[vm1].x, Vertices[vm1].y, Vertices[vm1].z));
1512 //      mprintf((0, "   Vert %3i = [%8x %8x %8x]\n", vm2, Vertices[vm2].x, Vertices[vm2].y, Vertices[vm2].z));
1513 //      mprintf((0, "   Vert %3i = [%8x %8x %8x]\n", vm3, Vertices[vm3].x, Vertices[vm3].y, Vertices[vm3].z));
1514 //}
1515
1516 //if ((sp-Segments == 0x86) && (sidenum == 5)) {
1517 //      mprintf((0, "Verts = %3i %3i %3i %3i, negate flag = %3i, dist = %8x\n", vm0, vm1, vm2, vm3, negate_flag, dist_to_plane));
1518 //      mprintf((0, "  Normal = %8x %8x %8x\n", vn.x, vn.y, vn.z));
1519 //      mprintf((0, "   Vert %3i = [%8x %8x %8x]\n", vm0, Vertices[vm0].x, Vertices[vm0].y, Vertices[vm0].z));
1520 //      mprintf((0, "   Vert %3i = [%8x %8x %8x]\n", vm1, Vertices[vm1].x, Vertices[vm1].y, Vertices[vm1].z));
1521 //      mprintf((0, "   Vert %3i = [%8x %8x %8x]\n", vm2, Vertices[vm2].x, Vertices[vm2].y, Vertices[vm2].z));
1522 //      mprintf((0, "   Vert %3i = [%8x %8x %8x]\n", vm3, Vertices[vm3].x, Vertices[vm3].y, Vertices[vm3].z));
1523 //}
1524
1525         if (negate_flag)
1526                 vm_vec_negate(&vn);
1527
1528         if (dist_to_plane <= PLANE_DIST_TOLERANCE)
1529                 add_side_as_quad(sp, sidenum, &vn);
1530         else {
1531                 add_side_as_2_triangles(sp, sidenum);
1532
1533                 //this code checks to see if we really should be triangulated, and
1534                 //de-triangulates if we shouldn't be.
1535
1536                 {
1537                         int                     num_faces;
1538                         int                     vertex_list[6];
1539                         fix                     dist0,dist1;
1540                         int                     s0,s1;
1541                         int                     vertnum;
1542                         side                    *s;
1543
1544                         create_abs_vertex_lists(&num_faces, vertex_list, sp - Segments, sidenum, __FILE__, __LINE__);
1545
1546                         Assert(num_faces == 2);
1547
1548                         s = &sp->sides[sidenum];
1549
1550                         vertnum = min(vertex_list[0],vertex_list[2]);
1551
1552                         #ifdef COMPACT_SEGS
1553                         {
1554                         vms_vector normals[2];
1555                         get_side_normals(sp, sidenum, &normals[0], &normals[1] );
1556                         dist0 = vm_dist_to_plane(&Vertices[vertex_list[1]],&normals[1],&Vertices[vertnum]);
1557                         dist1 = vm_dist_to_plane(&Vertices[vertex_list[4]],&normals[0],&Vertices[vertnum]);
1558                         }
1559                         #else
1560                         dist0 = vm_dist_to_plane(&Vertices[vertex_list[1]],&s->normals[1],&Vertices[vertnum]);
1561                         dist1 = vm_dist_to_plane(&Vertices[vertex_list[4]],&s->normals[0],&Vertices[vertnum]);
1562                         #endif
1563
1564                         s0 = sign(dist0);
1565                         s1 = sign(dist1);
1566
1567                         if (s0==0 || s1==0 || s0!=s1) {
1568                                 sp->sides[sidenum].type = SIDE_IS_QUAD;         //detriangulate!
1569                                 #ifndef COMPACT_SEGS
1570                                 sp->sides[sidenum].normals[0] = vn;
1571                                 sp->sides[sidenum].normals[1] = vn;
1572                                 #endif
1573                         }
1574
1575                 }
1576         }
1577
1578 }
1579
1580
1581 #ifdef COMPACT_SEGS
1582
1583 //#define CACHE_DEBUG 1
1584 #define MAX_CACHE_NORMALS 128
1585 #define CACHE_MASK 127
1586
1587 typedef struct ncache_element {
1588         short segnum;
1589         ubyte sidenum;
1590         vms_vector normals[2];
1591 } ncache_element;
1592
1593 int ncache_initialized = 0;
1594 ncache_element ncache[MAX_CACHE_NORMALS];
1595
1596 #ifdef CACHE_DEBUG
1597 int ncache_counter = 0;
1598 int ncache_hits = 0;
1599 int ncache_misses = 0;
1600 #endif
1601
1602 void ncache_init()
1603 {
1604         ncache_flush();
1605         ncache_initialized = 1;
1606 }
1607
1608 void ncache_flush()
1609 {
1610         int i;
1611         for (i=0; i<MAX_CACHE_NORMALS; i++ )    {
1612                 ncache[i].segnum = -1;
1613         }       
1614 }
1615
1616
1617
1618 // -------------------------------------------------------------------------------
1619 int find_ncache_element( int segnum, int sidenum, int face_flags )
1620 {
1621         uint i;
1622
1623         if (!ncache_initialized) ncache_init();
1624
1625 #ifdef CACHE_DEBUG
1626         if (((++ncache_counter % 5000)==1) && (ncache_hits+ncache_misses > 0))
1627                 mprintf(( 0, "NCACHE %d%% missed, H:%d, M:%d\n", (ncache_misses*100)/(ncache_hits+ncache_misses), ncache_hits, ncache_misses ));
1628 #endif
1629
1630         i = ((segnum<<2) ^ sidenum) & CACHE_MASK;
1631
1632         if ((ncache[i].segnum == segnum) && ((ncache[i].sidenum&0xf)==sidenum) )        {
1633                 uint f1;
1634 #ifdef CACHE_DEBUG
1635                 ncache_hits++;
1636 #endif
1637                 f1 = ncache[i].sidenum>>4;
1638                 if ( (f1&face_flags)==face_flags )
1639                         return i;
1640                 if ( f1 & 1 )
1641                         uncached_get_side_normal( &Segments[segnum], sidenum, 1, &ncache[i].normals[1] );
1642                 else
1643                         uncached_get_side_normal( &Segments[segnum], sidenum, 0, &ncache[i].normals[0] );
1644                 ncache[i].sidenum |= face_flags<<4;
1645                 return i;
1646         }
1647 #ifdef CACHE_DEBUG
1648         ncache_misses++;
1649 #endif
1650
1651         switch( face_flags )    {
1652         case 1: 
1653                 uncached_get_side_normal( &Segments[segnum], sidenum, 0, &ncache[i].normals[0] );
1654                 break;
1655         case 2:
1656                 uncached_get_side_normal( &Segments[segnum], sidenum, 1, &ncache[i].normals[1] );
1657                 break;
1658         case 3:
1659                 uncached_get_side_normals(&Segments[segnum], sidenum, &ncache[i].normals[0], &ncache[i].normals[1] );
1660                 break;
1661         }
1662         ncache[i].segnum = segnum;
1663         ncache[i].sidenum = sidenum | (face_flags<<4);
1664         return i;
1665 }
1666
1667 void get_side_normal(segment *sp, int sidenum, int face_num, vms_vector * vm )
1668 {
1669         int i;
1670         i = find_ncache_element( sp - Segments, sidenum, 1 << face_num );
1671         *vm = ncache[i].normals[face_num];
1672         if (0) {
1673                 vms_vector tmp;
1674                 uncached_get_side_normal(sp, sidenum, face_num, &tmp );
1675                 Assert( tmp.x == vm->x );
1676                 Assert( tmp.y == vm->y );
1677                 Assert( tmp.z == vm->z );
1678         }
1679 }
1680
1681 void get_side_normals(segment *sp, int sidenum, vms_vector * vm1, vms_vector * vm2 )
1682 {
1683         int i;
1684         i = find_ncache_element( sp - Segments, sidenum, 3 );
1685         *vm1 = ncache[i].normals[0];
1686         *vm2 = ncache[i].normals[1];
1687
1688         if (0) {
1689                 vms_vector tmp;
1690                 uncached_get_side_normal(sp, sidenum, 0, &tmp );
1691                 Assert( tmp.x == vm1->x );
1692                 Assert( tmp.y == vm1->y );
1693                 Assert( tmp.z == vm1->z );
1694                 uncached_get_side_normal(sp, sidenum, 1, &tmp );
1695                 Assert( tmp.x == vm2->x );
1696                 Assert( tmp.y == vm2->y );
1697                 Assert( tmp.z == vm2->z );
1698         }
1699
1700 }
1701
1702 void uncached_get_side_normal(segment *sp, int sidenum, int face_num, vms_vector * vm )
1703 {
1704         int     vm0, vm1, vm2, vm3, negate_flag;
1705         char    *vs = Side_to_verts[sidenum];
1706
1707         switch( sp->sides[sidenum].type )       {
1708         case SIDE_IS_QUAD:
1709                 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);
1710                 vm_vec_normal(vm, &Vertices[vm0], &Vertices[vm1], &Vertices[vm2]);
1711                 if (negate_flag)
1712                         vm_vec_negate(vm);
1713                 break;
1714         case SIDE_IS_TRI_02:
1715                 if ( face_num == 0 )
1716                         vm_vec_normal(vm, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[2]]]);
1717                 else
1718                         vm_vec_normal(vm, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[2]]], &Vertices[sp->verts[vs[3]]]);
1719                 break;
1720         case SIDE_IS_TRI_13:
1721                 if ( face_num == 0 )
1722                         vm_vec_normal(vm, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[3]]]);
1723                 else
1724                         vm_vec_normal(vm, &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[2]]], &Vertices[sp->verts[vs[3]]]);
1725                 break;
1726         }
1727 }
1728
1729 void uncached_get_side_normals(segment *sp, int sidenum, vms_vector * vm1, vms_vector * vm2 )
1730 {
1731         int     vvm0, vvm1, vvm2, vvm3, negate_flag;
1732         char    *vs = Side_to_verts[sidenum];
1733
1734         switch( sp->sides[sidenum].type )       {
1735         case SIDE_IS_QUAD:
1736                 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);
1737                 vm_vec_normal(vm1, &Vertices[vvm0], &Vertices[vvm1], &Vertices[vvm2]);
1738                 if (negate_flag)
1739                         vm_vec_negate(vm1);
1740                 *vm2 = *vm1;
1741                 break;
1742         case SIDE_IS_TRI_02:
1743                 vm_vec_normal(vm1, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[2]]]);
1744                 vm_vec_normal(vm2, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[2]]], &Vertices[sp->verts[vs[3]]]);
1745                 break;
1746         case SIDE_IS_TRI_13:
1747                 vm_vec_normal(vm1, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[3]]]);
1748                 vm_vec_normal(vm2, &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[2]]], &Vertices[sp->verts[vs[3]]]);
1749                 break;
1750         }
1751 }
1752
1753 #endif
1754
1755 // -------------------------------------------------------------------------------
1756 void validate_removable_wall(segment *sp, int sidenum, int tmap_num)
1757 {
1758         create_walls_on_side(sp, sidenum);
1759
1760         sp->sides[sidenum].tmap_num = tmap_num;
1761
1762 //      assign_default_uvs_to_side(sp, sidenum);
1763 //      assign_light_to_side(sp, sidenum);
1764 }
1765
1766 // -------------------------------------------------------------------------------
1767 //      Make a just-modified segment side valid.
1768 void validate_segment_side(segment *sp, int sidenum)
1769 {
1770         if (sp->sides[sidenum].wall_num == -1)
1771                 create_walls_on_side(sp, sidenum);
1772         else
1773                 // create_removable_wall(sp, sidenum, sp->sides[sidenum].tmap_num);
1774                 validate_removable_wall(sp, sidenum, sp->sides[sidenum].tmap_num);
1775
1776         //      Set render_flag.
1777         //      If side doesn't have a child, then render wall.  If it does have a child, but there is a temporary
1778         //      wall there, then do render wall.
1779 //      if (sp->children[sidenum] == -1)
1780 //              sp->sides[sidenum].render_flag = 1;
1781 //      else if (sp->sides[sidenum].wall_num != -1)
1782 //              sp->sides[sidenum].render_flag = 1;
1783 //      else
1784 //              sp->sides[sidenum].render_flag = 0;
1785 }
1786
1787 extern int check_for_degenerate_segment(segment *sp);
1788
1789 // -------------------------------------------------------------------------------
1790 //      Make a just-modified segment valid.
1791 //              check all sides to see how many faces they each should have (0,1,2)
1792 //              create new vector normals
1793 void validate_segment(segment *sp)
1794 {
1795         int     side;
1796
1797         #ifdef EDITOR
1798         check_for_degenerate_segment(sp);
1799         #endif
1800
1801         for (side = 0; side < MAX_SIDES_PER_SEGMENT; side++)
1802                 validate_segment_side(sp, side);
1803
1804 //      assign_default_uvs_to_segment(sp);
1805 }
1806
1807 // -------------------------------------------------------------------------------
1808 //      Validate all segments.
1809 //      Highest_segment_index must be set.
1810 //      For all used segments (number <= Highest_segment_index), segnum field must be != -1.
1811 void validate_segment_all(void)
1812 {
1813         int     s;
1814
1815         for (s=0; s<=Highest_segment_index; s++)
1816                 #ifdef EDITOR
1817                 if (Segments[s].segnum != -1)
1818                 #endif
1819                         validate_segment(&Segments[s]);
1820
1821         #ifdef EDITOR
1822         {
1823                 int said=0;
1824                 for (s=Highest_segment_index+1; s<MAX_SEGMENTS; s++)
1825                         if (Segments[s].segnum != -1) {
1826                                 if (!said) {
1827                                         mprintf((0, "Segment %i has invalid segnum.  Bashing to -1.  Silently bashing all others...", s));
1828                                 }
1829                                 said++;
1830                                 Segments[s].segnum = -1;
1831                         }
1832
1833                 if (said)
1834                         mprintf((0, "%i fixed.\n", said));
1835         }
1836         #endif
1837
1838         #ifndef NDEBUG
1839         #ifndef COMPACT_SEGS
1840         if (check_segment_connections())
1841                 Int3();         //Get Matt, si vous plait.
1842         #endif
1843         #endif
1844 }
1845
1846
1847 //      ------------------------------------------------------------------------------------------------------
1848 //      Picks a random point in a segment like so:
1849 //              From center, go up to 50% of way towards any of the 8 vertices.
1850 void pick_random_point_in_seg(vms_vector *new_pos, int segnum)
1851 {
1852         int                     vnum;
1853         vms_vector      vec2;
1854
1855         compute_segment_center(new_pos, &Segments[segnum]);
1856         vnum = (d_rand() * MAX_VERTICES_PER_SEGMENT) >> 15;
1857         vm_vec_sub(&vec2, &Vertices[Segments[segnum].verts[vnum]], new_pos);
1858         vm_vec_scale(&vec2, d_rand());          // d_rand() always in 0..1/2
1859         vm_vec_add2(new_pos, &vec2);
1860 }
1861
1862
1863 //      ----------------------------------------------------------------------------------------------------------
1864 //      Set the segment depth of all segments from start_seg in *segbuf.
1865 //      Returns maximum depth value.
1866 int set_segment_depths(int start_seg, ubyte *segbuf)
1867 {
1868         int     i, curseg;
1869         ubyte   visited[MAX_SEGMENTS];
1870         int     queue[MAX_SEGMENTS];
1871         int     head, tail;
1872         int     depth;
1873         int     parent_depth=0;
1874
1875         depth = 1;
1876         head = 0;
1877         tail = 0;
1878
1879         for (i=0; i<=Highest_segment_index; i++)
1880                 visited[i] = 0;
1881
1882         if (segbuf[start_seg] == 0)
1883                 return 1;
1884
1885         queue[tail++] = start_seg;
1886         visited[start_seg] = 1;
1887         segbuf[start_seg] = depth++;
1888
1889         if (depth == 0)
1890                 depth = 255;
1891
1892         while (head < tail) {
1893                 curseg = queue[head++];
1894                 parent_depth = segbuf[curseg];
1895
1896                 for (i=0; i<MAX_SIDES_PER_SEGMENT; i++) {
1897                         int     childnum;
1898
1899                         childnum = Segments[curseg].children[i];
1900                         if (childnum != -1)
1901                                 if (segbuf[childnum])
1902                                         if (!visited[childnum]) {
1903                                                 visited[childnum] = 1;
1904                                                 segbuf[childnum] = parent_depth+1;
1905                                                 queue[tail++] = childnum;
1906                                         }
1907                 }
1908         }
1909
1910         return parent_depth+1;
1911 }
1912
1913 //these constants should match the ones in seguvs
1914 #define LIGHT_DISTANCE_THRESHOLD        (F1_0*80)
1915 #define Magical_light_constant  (F1_0*16)
1916
1917 #define MAX_CHANGED_SEGS 30
1918 short changed_segs[MAX_CHANGED_SEGS];
1919 int n_changed_segs;
1920
1921 //      ------------------------------------------------------------------------------------------
1922 //cast static light from a segment to nearby segments
1923 void apply_light_to_segment(segment *segp,vms_vector *segment_center, fix light_intensity,int recursion_depth)
1924 {
1925         vms_vector      r_segment_center;
1926         fix                     dist_to_rseg;
1927         int                     i,segnum=segp-Segments,sidenum;
1928
1929         for (i=0;i<n_changed_segs;i++)
1930                 if (changed_segs[i] == segnum)
1931                         break;
1932
1933         if (i == n_changed_segs) {
1934                 compute_segment_center(&r_segment_center, segp);
1935                 dist_to_rseg = vm_vec_dist_quick(&r_segment_center, segment_center);
1936         
1937                 if (dist_to_rseg <= LIGHT_DISTANCE_THRESHOLD) {
1938                         fix     light_at_point;
1939                         if (dist_to_rseg > F1_0)
1940                                 light_at_point = fixdiv(Magical_light_constant, dist_to_rseg);
1941                         else
1942                                 light_at_point = Magical_light_constant;
1943         
1944                         if (light_at_point >= 0) {
1945                                 segment2        *seg2p  = &Segment2s[segnum];
1946                                 light_at_point = fixmul(light_at_point, light_intensity);
1947                                 if (light_at_point >= F1_0)
1948                                         light_at_point = F1_0-1;
1949                                 if (light_at_point <= -F1_0)
1950                                         light_at_point = -(F1_0-1);
1951                                 seg2p->static_light += light_at_point;
1952                                 if (seg2p->static_light < 0)    // if it went negative, saturate
1953                                         seg2p->static_light = 0;
1954                         }       //      end if (light_at_point...
1955                 }       //      end if (dist_to_rseg...
1956
1957                 changed_segs[n_changed_segs++] = segnum;
1958         }
1959
1960         if (recursion_depth < 2)
1961                 for (sidenum=0; sidenum<6; sidenum++) {
1962                         if (WALL_IS_DOORWAY(segp,sidenum) & WID_RENDPAST_FLAG)
1963                                 apply_light_to_segment(&Segments[segp->children[sidenum]],segment_center,light_intensity,recursion_depth+1);
1964                 }
1965
1966 }
1967
1968
1969 extern object *old_viewer;
1970
1971 //update the static_light field in a segment, which is used for object lighting
1972 //this code is copied from the editor routine calim_process_all_lights()
1973 void change_segment_light(int segnum,int sidenum,int dir)
1974 {
1975         segment *segp = &Segments[segnum];
1976
1977         if (WALL_IS_DOORWAY(segp, sidenum) & WID_RENDER_FLAG) {
1978                 side    *sidep = &segp->sides[sidenum];
1979                 fix     light_intensity;
1980
1981                 light_intensity = TmapInfo[sidep->tmap_num].lighting + TmapInfo[sidep->tmap_num2 & 0x3fff].lighting;
1982
1983                 light_intensity *= dir;
1984
1985                 n_changed_segs = 0;
1986
1987                 if (light_intensity) {
1988                         vms_vector      segment_center;
1989                         compute_segment_center(&segment_center, segp);
1990                         apply_light_to_segment(segp,&segment_center,light_intensity,0);
1991                 }
1992         }
1993
1994         //this is a horrible hack to get around the horrible hack used to
1995         //smooth lighting values when an object moves between segments
1996         old_viewer = NULL;
1997
1998 }
1999
2000 //      ------------------------------------------------------------------------------------------
2001 //      dir = +1 -> add light
2002 //      dir = -1 -> subtract light
2003 //      dir = 17 -> add 17x light
2004 //      dir =  0 -> you are dumb
2005 void change_light(int segnum, int sidenum, int dir)
2006 {
2007         int     i, j, k;
2008
2009         for (i=0; i<Num_static_lights; i++) {
2010                 if ((Dl_indices[i].segnum == segnum) && (Dl_indices[i].sidenum == sidenum)) {
2011                         delta_light     *dlp;
2012                         dlp = &Delta_lights[Dl_indices[i].index];
2013
2014                         for (j=0; j<Dl_indices[i].count; j++) {
2015                                 for (k=0; k<4; k++) {
2016                                         fix     dl,new_l;
2017                                         dl = dir * dlp->vert_light[k] * DL_SCALE;
2018                                         Assert((dlp->segnum >= 0) && (dlp->segnum <= Highest_segment_index));
2019                                         Assert((dlp->sidenum >= 0) && (dlp->sidenum < MAX_SIDES_PER_SEGMENT));
2020                                         new_l = (Segments[dlp->segnum].sides[dlp->sidenum].uvls[k].l += dl);
2021                                         if (new_l < 0)
2022                                                 Segments[dlp->segnum].sides[dlp->sidenum].uvls[k].l = 0;
2023                                 }
2024                                 dlp++;
2025                         }
2026                 }
2027         }
2028
2029         //recompute static light for segment
2030         change_segment_light(segnum,sidenum,dir);
2031 }
2032
2033 //      Subtract light cast by a light source from all surfaces to which it applies light.
2034 //      This is precomputed data, stored at static light application time in the editor (the slow lighting function).
2035 // returns 1 if lights actually subtracted, else 0
2036 int subtract_light(int segnum, int sidenum)
2037 {
2038         if (Light_subtracted[segnum] & (1 << sidenum)) {
2039                 //mprintf((0, "Warning: Trying to subtract light from a source twice!\n"));
2040                 return 0;
2041         }
2042
2043         Light_subtracted[segnum] |= (1 << sidenum);
2044         change_light(segnum, sidenum, -1);
2045         return 1;
2046 }
2047
2048 //      Add light cast by a light source from all surfaces to which it applies light.
2049 //      This is precomputed data, stored at static light application time in the editor (the slow lighting function).
2050 //      You probably only want to call this after light has been subtracted.
2051 // returns 1 if lights actually added, else 0
2052 int add_light(int segnum, int sidenum)
2053 {
2054         if (!(Light_subtracted[segnum] & (1 << sidenum))) {
2055                 //mprintf((0, "Warning: Trying to add light which has never been subtracted!\n"));
2056                 return 0;
2057         }
2058
2059         Light_subtracted[segnum] &= ~(1 << sidenum);
2060         change_light(segnum, sidenum, 1);
2061         return 1;
2062 }
2063
2064 //      Light_subtracted[i] contains bit indicators for segment #i.
2065 //      If bit n (1 << n) is set, then side #n in segment #i has had light subtracted from original (editor-computed) value.
2066 ubyte   Light_subtracted[MAX_SEGMENTS];
2067
2068 //      Parse the Light_subtracted array, turning on or off all lights.
2069 void apply_all_changed_light(void)
2070 {
2071         int     i,j;
2072
2073         for (i=0; i<=Highest_segment_index; i++) {
2074                 for (j=0; j<MAX_SIDES_PER_SEGMENT; j++)
2075                         if (Light_subtracted[i] & (1 << j))
2076                                 change_light(i, j, -1);
2077         }
2078 }
2079
2080 //@@//  Scans Light_subtracted bit array.
2081 //@@//  For all light sources which have had their light subtracted, adds light back in.
2082 //@@void restore_all_lights_in_mine(void)
2083 //@@{
2084 //@@    int     i, j, k;
2085 //@@
2086 //@@    for (i=0; i<Num_static_lights; i++) {
2087 //@@            int     segnum, sidenum;
2088 //@@            delta_light     *dlp;
2089 //@@
2090 //@@            segnum = Dl_indices[i].segnum;
2091 //@@            sidenum = Dl_indices[i].sidenum;
2092 //@@            if (Light_subtracted[segnum] & (1 << sidenum)) {
2093 //@@                    dlp = &Delta_lights[Dl_indices[i].index];
2094 //@@
2095 //@@                    Light_subtracted[segnum] &= ~(1 << sidenum);
2096 //@@                    for (j=0; j<Dl_indices[i].count; j++) {
2097 //@@                            for (k=0; k<4; k++) {
2098 //@@                                    fix     dl;
2099 //@@                                    dl = dlp->vert_light[k] * DL_SCALE;
2100 //@@                                    Assert((dlp->segnum >= 0) && (dlp->segnum <= Highest_segment_index));
2101 //@@                                    Assert((dlp->sidenum >= 0) && (dlp->sidenum < MAX_SIDES_PER_SEGMENT));
2102 //@@                                    Segments[dlp->segnum].sides[dlp->sidenum].uvls[k].l += dl;
2103 //@@                            }
2104 //@@                            dlp++;
2105 //@@                    }
2106 //@@            }
2107 //@@    }
2108 //@@}
2109
2110 //      Should call this whenever a new mine gets loaded.
2111 //      More specifically, should call this whenever something global happens
2112 //      to change the status of static light in the mine.
2113 void clear_light_subtracted(void)
2114 {
2115         int     i;
2116
2117         for (i=0; i<=Highest_segment_index; i++)
2118                 Light_subtracted[i] = 0;
2119
2120 }
2121
2122 //      -----------------------------------------------------------------------------
2123 fix find_connected_distance_segments( int seg0, int seg1, int depth, int wid_flag)
2124 {
2125         vms_vector      p0, p1;
2126
2127         compute_segment_center(&p0, &Segments[seg0]);
2128         compute_segment_center(&p1, &Segments[seg1]);
2129
2130         return find_connected_distance(&p0, seg0, &p1, seg1, depth, wid_flag);
2131 }
2132
2133 #define AMBIENT_SEGMENT_DEPTH           5
2134
2135 //      -----------------------------------------------------------------------------
2136 //      Do a bfs from segnum, marking slots in marked_segs if the segment is reachable.
2137 void ambient_mark_bfs(int segnum, sbyte *marked_segs, int depth)
2138 {
2139         int     i;
2140
2141         if (depth < 0)
2142                 return;
2143
2144         marked_segs[segnum] = 1;
2145
2146         for (i=0; i<MAX_SIDES_PER_SEGMENT; i++) {
2147                 int     child = Segments[segnum].children[i];
2148
2149                 if (IS_CHILD(child) && (WALL_IS_DOORWAY(&Segments[segnum],i) & WID_RENDPAST_FLAG) && !marked_segs[child])
2150                         ambient_mark_bfs(child, marked_segs, depth-1);
2151         }
2152
2153 }
2154
2155 //      -----------------------------------------------------------------------------
2156 //      Indicate all segments which are within audible range of falling water or lava,
2157 //      and so should hear ambient gurgles.
2158 void set_ambient_sound_flags_common(int tmi_bit, int s2f_bit)
2159 {
2160         int     i, j;
2161         sbyte   marked_segs[MAX_SEGMENTS];
2162
2163         //      Now, all segments containing ambient lava or water sound makers are flagged.
2164         //      Additionally flag all segments which are within range of them.
2165         for (i=0; i<=Highest_segment_index; i++) {
2166                 marked_segs[i] = 0;
2167                 Segment2s[i].s2_flags &= ~s2f_bit;
2168         }
2169
2170         //      Mark all segments which are sources of the sound.
2171         for (i=0; i<=Highest_segment_index; i++) {
2172                 segment *segp = &Segments[i];
2173                 segment2        *seg2p = &Segment2s[i];
2174
2175                 for (j=0; j<MAX_SIDES_PER_SEGMENT; j++) {
2176                         side    *sidep = &segp->sides[j];
2177
2178                         if ((TmapInfo[sidep->tmap_num].flags & tmi_bit) || (TmapInfo[sidep->tmap_num2 & 0x3fff].flags & tmi_bit)) {
2179                                 if (!IS_CHILD(segp->children[j]) || (sidep->wall_num != -1)) {
2180                                         seg2p->s2_flags |= s2f_bit;
2181                                         marked_segs[i] = 1;             //      Say it's itself that it is close enough to to hear something.
2182                                 }
2183                         }
2184
2185                 }
2186
2187         }
2188
2189         //      Next mark all segments within N segments of a source.
2190         for (i=0; i<=Highest_segment_index; i++) {
2191                 segment2        *seg2p = &Segment2s[i];
2192
2193                 if (seg2p->s2_flags & s2f_bit)
2194                         ambient_mark_bfs(i, marked_segs, AMBIENT_SEGMENT_DEPTH);
2195         }
2196
2197         //      Now, flip bits in all segments which can hear the ambient sound.
2198         for (i=0; i<=Highest_segment_index; i++)
2199                 if (marked_segs[i])
2200                         Segment2s[i].s2_flags |= s2f_bit;
2201
2202 }
2203
2204
2205 //      -----------------------------------------------------------------------------
2206 //      Indicate all segments which are within audible range of falling water or lava,
2207 //      and so should hear ambient gurgles.
2208 //      Bashes values in Segment2s array.
2209 void set_ambient_sound_flags(void)
2210 {
2211         set_ambient_sound_flags_common(TMI_VOLATILE, S2F_AMBIENT_LAVA);
2212         set_ambient_sound_flags_common(TMI_WATER, S2F_AMBIENT_WATER);
2213 }