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