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