main/editor/segment.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-1998 PARALLAX SOFTWARE CORPORATION.  ALL RIGHTS RESERVED.
  12 */
  13
  14 /*
  15  * $Source: /cvs/cvsroot/d2x/main/editor/segment.c,v $
  16  * $Revision: 1.1 $
  17  * $Author: bradleyb $
  18  * $Date: 2001-10-25 02:27:17 $
  19  *
  20  * Interrogation functions for segment data structure.
  21  *
  22  * $Log: not supported by cvs2svn $
  23  * Revision 1.2  1999/09/02 13:37:06  sekmu
  24  * remove warning in editor compile
  25  *
  26  * Revision 1.1.1.1  1999/06/14 22:04:21  donut
  27  * Import of d1x 1.37 source.
  28  *
  29  * Revision 2.0  1995/02/27  11:35:21  john
  30  * Version 2.0! No anonymous unions, Watcom 10.0, with no need
  31  * for bitmaps.tbl.
  32  *
  33  * Revision 1.191  1995/02/22  15:28:30  allender
  34  * remove anonymous unions from object structure
  35  *
  36  * Revision 1.190  1995/02/02  02:59:40  yuan
  37  * Working on exterminating bogus matcen_nums... (harmless though)
  38  *
  39  * Revision 1.189  1995/02/01  16:29:51  yuan
  40  * Stabilizing triggers and matcens.
  41  *
  42  * Revision 1.188  1995/02/01  11:31:47  yuan
  43  * Trigger bug fixed.
  44  *
  45  * Revision 1.187  1994/11/27  23:17:24  matt
  46  * Made changes for new mprintf calling convention
  47  *
  48  * Revision 1.186  1994/11/17  14:48:12  mike
  49  * validation functions moved from editor to game.
  50  *
  51  * Revision 1.185  1994/10/30  14:13:17  mike
  52  * rip out local segment stuff.
  53  *
  54  * Revision 1.184  1994/10/27  10:04:24  matt
  55  * When triangulating, don't use WID() to see if connected, look at children
  56  *
  57  * Revision 1.183  1994/10/26  13:40:23  mike
  58  * debug code for matt.
  59  *
  60  * Revision 1.182  1994/10/24  16:34:00  mike
  61  * Force render after mine compress to prevent bugs in segment selection via clicking in 3d window.
  62  *
  63  * Revision 1.181  1994/10/20  18:16:15  mike
  64  * Initialize ControlCenterTriggers.num_links in create_new_mine.
  65  *
  66  * Revision 1.180  1994/10/18  16:29:14  mike
  67  * Write function to automatically fix bogus segnums in segment array.
  68  *
  69  * Revision 1.179  1994/10/08  17:10:41  matt
  70  * Correctly set current_level_num when loading/creating mine in editor
  71  *
  72  * Revision 1.178  1994/09/25  14:17:51  mike
  73  * Initialize (to 0) Num_robot_centers and Num_open_doors at mine creation.
  74  *
  75  * Revision 1.177  1994/09/20  14:36:06  mike
  76  * Write function to find overlapping segments.
  77  *
  78  * Revision 1.176  1994/08/25  21:55:57  mike
  79  * IS_CHILD stuff.
  80  *
  81  * Revision 1.175  1994/08/23  15:28:03  mike
  82  * Fix peculiarity in med_combine_duplicate_vertices.
  83  *
  84  * Revision 1.174  1994/08/09  16:06:17  john
  85  * Added the ability to place players.  Made old
  86  * Player variable be ConsoleObject.
  87  *
  88  * Revision 1.173  1994/08/05  21:18:10  matt
  89  * Allow two doors to be linked together
  90  *
  91  * Revision 1.172  1994/08/04  19:13:16  matt
  92  * Changed a bunch of vecmat calls to use multiple-function routines, and to
  93  * allow the use of C macros for some functions
  94  *
  95  * Revision 1.171  1994/07/22  12:37:00  matt
  96  * Cleaned up editor/game interactions some more.
  97  *
  98  * Revision 1.170  1994/07/22  11:20:08  mike
  99  * Set Lsegments validity.
 100  *
 101  * Revision 1.169  1994/07/21  19:02:49  mike
 102  * lsegment stuff.
 103  *
 104  * Revision 1.168  1994/07/21  13:27:17  matt
 105  * Ripped out remants of old demo system, and added demo
 106  * disables object movement and game options from menu.
 107  *
 108  * Revision 1.167  1994/07/19  20:15:48  matt
 109  * Name for each level now saved in the .SAV file & stored in Current_level_name
 110  *
 111  * Revision 1.166  1994/07/06  12:42:45  john
 112  * Made generic messages for hostages.
 113  *
 114  * Revision 1.165  1994/06/24  17:04:29  john
 115  * *** empty log message ***
 116  *
 117  * Revision 1.164  1994/06/15  15:42:40  mike
 118  * Initialize static_light field in new segments.
 119  *
 120  * Revision 1.163  1994/06/13  17:49:19  mike
 121  * Fix bug in med_validate_side which was toasting lighting for removable walls.
 122  *
 123  * Revision 1.162  1994/06/13  10:52:20  mike
 124  * Fix bug in triangulation of sides between connected segments.
 125  * Was assigning SIDE_IS_02 regardless of how triangulated, was
 126  * causing physics bugs.
 127  *
 128  * Revision 1.161  1994/06/08  18:14:16  mike
 129  * Fix triangulation of sides in hallways (ie, where there is no wall),
 130  * so they get triangulated the same way, so find_new_seg doesn't get
 131  * stuck in an infinite recursion.
 132  *
 133  * Revision 1.160  1994/06/08  11:44:31  mike
 134  * Fix bug in normals not being opposite on opposite sides of a segment.
 135  * Problem occurred due to difference in handling of remainder in signed divide.
 136  *
 137  * Revision 1.159  1994/05/31  19:00:15  yuan
 138  * Fixed gamestate restore.
 139  *
 140  * Revision 1.158  1994/05/30  20:22:36  yuan
 141  * New triggers.
 142  *
 143  * Revision 1.157  1994/05/26  19:32:51  mike
 144  * Add bfs_parse.
 145  *
 146  * Revision 1.156  1994/05/23  14:56:46  mike
 147  * make current segment be add segment.,
 148  *
 149  */
 150
 151 #ifdef HAVE_CONFIG_H
 152 #include <conf.h>
 153 #endif
 154
 155 #include <stdio.h>
 156 #include <stdlib.h>
 157 #include <math.h>
 158 #include <string.h>
 159
 160 #include "mono.h"
 161 #include "key.h"
 162 #include "gr.h"
 163
 164 #include "inferno.h"
 165 #include "segment.h"
 166 // #include "segment2.h"
 167 #include "editor.h"
 168 #include "error.h"
 169 #include "object.h"
 170
 171 #include "gameseg.h"
 172 #include "render.h"
 173 #include "game.h"
 174
 175 #include "wall.h"
 176 #include "switch.h"
 177 #include "fuelcen.h"
 178 #include "cntrlcen.h"
 179 #include "seguvs.h"
 180 #include "gameseq.h"
 181
 182 #include "medwall.h"
 183 #include "hostage.h"
 184
 185 int     Do_duplicate_vertex_check = 0;          // Gets set to 1 in med_create_duplicate_vertex, means to check for duplicate vertices in compress_mine
 186
 187 #define BOTTOM_STUFF    0
 188
 189 //      Remap all vertices in polygons in a segment through translation table xlate_verts.
 190 #if BOTTOM_STUFF
 191 void remap_vertices(segment *segp, int *xlate_verts)
 192 {
 193         int     sidenum, facenum, polynum, v;
 194
 195         for (sidenum=0; sidenum<MAX_SIDES_PER_SEGMENT; sidenum++)
 196                 for (facenum=0; facenum<segp->sides[sidenum].num_faces; facenum++)
 197                         for (polynum=0; polynum<segp->sides[sidenum].faces[facenum].num_polys; polynum++) {
 198                                 poly *pp = &segp->sides[sidenum].faces[facenum].polys[polynum];
 199                                 for (v=0; v<pp->num_vertices; v++)
 200                                         pp->verts[v] = xlate_verts[pp->verts[v]];
 201                         }
 202 }
 203
 204 //      Copy everything from sourceside to destside except sourceside->faces[xx].polys[xx].verts
 205 void copy_side_except_vertex_ids(side *destside, side *sourceside)
 206 {
 207         int     facenum, polynum, v;
 208
 209         destside->num_faces = sourceside->num_faces;
 210         destside->tri_edge = sourceside->tri_edge;
 211         destside->wall_num = sourceside->wall_num;
 212
 213         for (facenum=0; facenum<sourceside->num_faces; facenum++) {
 214                 face *destface = &destside->faces[facenum];
 215                 face *sourceface = &sourceside->faces[facenum];
 216
 217                 destface->num_polys = sourceface->num_polys;
 218                 destface->normal = sourceface->normal;
 219
 220                 for (polynum=0; polynum<sourceface->num_polys; polynum++) {
 221                         poly *destpoly = &destface->polys[polynum];
 222                         poly *sourcepoly = &sourceface->polys[polynum];
 223
 224                         destpoly->num_vertices = sourcepoly->num_vertices;
 225                         destpoly->face_type = sourcepoly->face_type;
 226                         destpoly->tmap_num = sourcepoly->tmap_num;
 227                         destpoly->tmap_num2 = sourcepoly->tmap_num2;
 228
 229                         for (v=0; v<sourcepoly->num_vertices; v++)
 230                                 destpoly->uvls[v] = sourcepoly->uvls[v];
 231                 }
 232
 233         }
 234 }
 235
 236 //      [side] [index] [cur:next]
 237 //      To remap the vertices on a side after a forward rotation
 238 byte xlate_previous[6][4][2] = {
 239 { {7, 3}, {3, 2}, {2, 6}, {6, 7} },             // remapping left to left
 240 { {5, 4}, {4, 0}, {7, 3}, {6, 7} },             // remapping back to top
 241 { {5, 4}, {1, 5}, {0, 1}, {4, 0} },             // remapping right to right
 242 { {0, 1}, {1, 5}, {2, 6}, {3, 2} },             //      remapping front to bottom
 243 { {1, 5}, {5, 4}, {6, 7}, {2, 6} },             // remapping bottom to back
 244 { {4, 0}, {0, 1}, {3, 2}, {7, 3} },             // remapping top to front
 245 };
 246
 247 void remap_vertices_previous(segment *segp, int sidenum)
 248 {
 249         int     v, w, facenum, polynum;
 250
 251         for (facenum=0; facenum<segp->sides[sidenum].num_faces; facenum++) {
 252                 for (polynum=0; polynum<segp->sides[sidenum].faces[facenum].num_polys; polynum++) {
 253                         poly *pp = &segp->sides[sidenum].faces[facenum].polys[polynum];
 254
 255                         for (v=0; v<pp->num_vertices; v++) {
 256                                 for (w=0; w<4; w++) {
 257                                         if (pp->verts[v] == xlate_previous[sidenum][w][0]) {
 258                                                 pp->verts[v] = xlate_previous[sidenum][w][1];
 259                                                 break;
 260                                         }
 261                                 }
 262                                 Assert(w<4);    // If w == 4, then didn't find current vertex in list, which means xlate_previous table is bogus
 263                         }
 264                 }
 265         }
 266 }
 267
 268 byte xlate_previous_right[6][4][2] = {
 269 { {5, 6}, {6, 7}, {2, 3}, {1, 2} },             // bottom to left
 270 { {6, 7}, {7, 4}, {3, 0}, {2, 3} },             // left to top
 271 { {7, 4}, {4, 5}, {0, 1}, {3, 0} },             // top to right
 272 { {4, 5}, {5, 6}, {1, 2}, {0, 1} },             // right to bottom
 273 { {6, 7}, {5, 6}, {4, 5}, {7, 4} },             // back to back
 274 { {3, 2}, {0, 3}, {1, 0}, {2, 1} },             // front to front
 275 };
 276
 277 void remap_vertices_previous_right(segment *segp, int sidenum)
 278 {
 279         int     v, w, facenum, polynum;
 280
 281         for (facenum=0; facenum<segp->sides[sidenum].num_faces; facenum++) {
 282                 for (polynum=0; polynum<segp->sides[sidenum].faces[facenum].num_polys; polynum++) {
 283                         poly *pp = &segp->sides[sidenum].faces[facenum].polys[polynum];
 284
 285                         for (v=0; v<pp->num_vertices; v++) {
 286                                 for (w=0; w<4; w++) {
 287                                         if (pp->verts[v] == xlate_previous_right[sidenum][w][0]) {
 288                                                 pp->verts[v] = xlate_previous_right[sidenum][w][1];
 289                                                 break;
 290                                         }
 291                                 }
 292                                 Assert(w<4);    // If w == 4, then didn't find current vertex in list, which means xlate_previous table is bogus
 293                         }
 294                 }
 295         }
 296 }
 297
 298
 299 // -----------------------------------------------------------------------------------
 300 //      Takes top to front
 301 void med_rotate_segment_forward(segment *segp)
 302 {
 303         segment seg_copy;
 304         int             i;
 305
 306         seg_copy = *segp;
 307
 308         seg_copy.verts[0] = segp->verts[4];
 309         seg_copy.verts[1] = segp->verts[0];
 310         seg_copy.verts[2] = segp->verts[3];
 311         seg_copy.verts[3] = segp->verts[7];
 312         seg_copy.verts[4] = segp->verts[5];
 313         seg_copy.verts[5] = segp->verts[1];
 314         seg_copy.verts[6] = segp->verts[2];
 315         seg_copy.verts[7] = segp->verts[6];
 316
 317         seg_copy.children[WFRONT] = segp->children[WTOP];
 318         seg_copy.children[WTOP] = segp->children[WBACK];
 319         seg_copy.children[WBACK] = segp->children[WBOTTOM];
 320         seg_copy.children[WBOTTOM] = segp->children[WFRONT];
 321
 322         seg_copy.sides[WFRONT] = segp->sides[WTOP];
 323         seg_copy.sides[WTOP] = segp->sides[WBACK];
 324         seg_copy.sides[WBACK] = segp->sides[WBOTTOM];
 325         seg_copy.sides[WBOTTOM] = segp->sides[WFRONT];
 326
 327         for (i=0; i<6; i++)
 328                 remap_vertices_previous(&seg_copy, i);
 329
 330         *segp = seg_copy;
 331 }
 332
 333 // -----------------------------------------------------------------------------------
 334 //      Takes top to right
 335 void med_rotate_segment_right(segment *segp)
 336 {
 337         segment seg_copy;
 338         int             i;
 339
 340         seg_copy = *segp;
 341
 342         seg_copy.verts[4] = segp->verts[7];
 343         seg_copy.verts[5] = segp->verts[4];
 344         seg_copy.verts[1] = segp->verts[0];
 345         seg_copy.verts[0] = segp->verts[3];
 346         seg_copy.verts[3] = segp->verts[2];
 347         seg_copy.verts[2] = segp->verts[1];
 348         seg_copy.verts[6] = segp->verts[5];
 349         seg_copy.verts[7] = segp->verts[6];
 350
 351         seg_copy.children[WRIGHT] = segp->children[WTOP];
 352         seg_copy.children[WBOTTOM] = segp->children[WRIGHT];
 353         seg_copy.children[WLEFT] = segp->children[WBOTTOM];
 354         seg_copy.children[WTOP] = segp->children[WLEFT];
 355
 356         seg_copy.sides[WRIGHT] = segp->sides[WTOP];
 357         seg_copy.sides[WBOTTOM] = segp->sides[WRIGHT];
 358         seg_copy.sides[WLEFT] = segp->sides[WBOTTOM];
 359         seg_copy.sides[WTOP] = segp->sides[WLEFT];
 360
 361         for (i=0; i<6; i++)
 362                 remap_vertices_previous_right(&seg_copy, i);
 363
 364         *segp = seg_copy;
 365 }
 366
 367 void make_curside_bottom_side(void)
 368 {
 369         switch (Curside) {
 370                 case WRIGHT:    med_rotate_segment_right(Cursegp);              break;
 371                 case WTOP:              med_rotate_segment_right(Cursegp);              med_rotate_segment_right(Cursegp);              break;
 372                 case WLEFT:             med_rotate_segment_right(Cursegp);              med_rotate_segment_right(Cursegp);              med_rotate_segment_right(Cursegp);              break;
 373                 case WBOTTOM:   break;
 374                 case WFRONT:    med_rotate_segment_forward(Cursegp);    break;
 375                 case WBACK:             med_rotate_segment_forward(Cursegp);    med_rotate_segment_forward(Cursegp);    med_rotate_segment_forward(Cursegp);    break;
 376         }
 377         Update_flags = UF_WORLD_CHANGED;
 378 }
 379 #endif
 380
 381 int ToggleBottom(void)
 382 {
 383         Render_only_bottom = !Render_only_bottom;
 384         Update_flags = UF_WORLD_CHANGED;
 385         return 0;
 386 }
 387
 388 // ---------------------------------------------------------------------------------------------
 389 //           ---------- Segment interrogation functions ----------
 390 // ----------------------------------------------------------------------------
 391 //      Return a pointer to the list of vertex indices for the current segment in vp and
 392 //      the number of vertices in *nv.
 393 void med_get_vertex_list(segment *s,int *nv,short **vp)
 394 {
 395         *vp = s->verts;
 396         *nv = MAX_VERTICES_PER_SEGMENT;
 397 }
 398
 399 // -------------------------------------------------------------------------------
 400 //      Return number of times vertex vi appears in all segments.
 401 //      This function can be used to determine whether a vertex is used exactly once in
 402 //      all segments, in which case it can be freely moved because it is not connected
 403 //      to any other segment.
 404 int med_vertex_count(int vi)
 405 {
 406         int             s,v;
 407         segment *sp;
 408         int             count;
 409
 410         count = 0;
 411
 412         for (s=0; s<MAX_SEGMENTS; s++) {
 413                 sp = &Segments[s];
 414                 if (sp->segnum != -1)
 415                         for (v=0; v<MAX_VERTICES_PER_SEGMENT; v++)
 416                                 if (sp->verts[v] == vi)
 417                                         count++;
 418         }
 419
 420         return count;
 421 }
 422
 423 // -------------------------------------------------------------------------------
 424 int is_free_vertex(int vi)
 425 {
 426         return med_vertex_count(vi) == 1;
 427 }
 428
 429
 430 // -------------------------------------------------------------------------------
 431 // Move a free vertex in the segment by adding the vector *vofs to its coordinates.
 432 //      Error handling:
 433 //      If the point is not free then:
 434 //              If the point is not valid (probably valid = in 0..7) then:
 435 //              If adding *vofs will cause a degenerate segment then:
 436 //      Note, pi is the point index relative to the segment, not an absolute point index.
 437 // For example, 3 is always the front upper left vertex.
 438 void med_move_vertex(segment *sp, int pi, vms_vector *vofs)
 439 {
 440         int     abspi;
 441
 442         Assert((pi >= 0) && (pi <= 7));         // check valid range of point indices.
 443
 444         abspi = sp->verts[pi];
 445
 446         // Make sure vertex abspi is free.  If it is free, it appears exactly once in Vertices
 447         Assert(med_vertex_count(abspi) == 1);
 448
 449         Assert(abspi <= MAX_SEGMENT_VERTICES);                  // Make sure vertex id is not bogus.
 450
 451         vm_vec_add(&Vertices[abspi],&Vertices[abspi],vofs);
 452
 453         // Here you need to validate the geometry of the segment, which will be quite tricky.
 454         // You need to make sure:
 455         //              The segment is not concave.
 456         //              None of the sides are concave.
 457         validate_segment(sp);
 458
 459 }
 460
 461 // -------------------------------------------------------------------------------
 462 //      Move a free wall in the segment by adding the vector *vofs to its coordinates.
 463 //      Wall indices: 0/1/2/3/4/5 = left/top/right/bottom/back/front
 464 void med_move_wall(segment *sp,int wi, vms_vector *vofs)
 465 {
 466         char *vp;
 467         int     i;
 468
 469         Assert( (wi >= 0) && (wi <= 5) );
 470
 471         vp = Side_to_verts[wi];
 472         for (i=0; i<4; i++) {
 473                 med_move_vertex(sp,*vp,vofs);
 474                 vp++;
 475         }
 476
 477         validate_segment(sp);
 478 }
 479
 480 // -------------------------------------------------------------------------------
 481 //      Return true if one fixed point number is very close to another, else return false.
 482 int fnear(fix f1, fix f2)
 483 {
 484         return (abs(f1 - f2) <= FIX_EPSILON);
 485 }
 486
 487 // -------------------------------------------------------------------------------
 488 int vnear(vms_vector *vp1, vms_vector *vp2)
 489 {
 490         return fnear(vp1->x, vp2->x) && fnear(vp1->y, vp2->y) && fnear(vp1->z, vp2->z);
 491 }
 492
 493 // -------------------------------------------------------------------------------
 494 //      Add the vertex *vp to the global list of vertices, return its index.
 495 //      Search until a matching vertex is found (has nearly the same coordinates) or until Num_vertices
 496 // vertices have been looked at without a match.  If no match, add a new vertex.
 497 int med_add_vertex(vms_vector *vp)
 498 {
 499         int     v,free_index;
 500         int     count;                                  // number of used vertices found, for loops exits when count == Num_vertices
 501
 502 //      set_vertex_counts();
 503
 504         Assert(Num_vertices < MAX_SEGMENT_VERTICES);
 505
 506         count = 0;
 507         free_index = -1;
 508         for (v=0; (v < MAX_SEGMENT_VERTICES) && (count < Num_vertices); v++)
 509                 if (Vertex_active[v]) {
 510                         count++;
 511                         if (vnear(vp,&Vertices[v])) {
 512                                 // mprintf((0,"[%4i]  ",v));
 513                                 return v;
 514                         }
 515                 } else if (free_index == -1)
 516                         free_index = v;                                 // we want free_index to be the first free slot to add a vertex
 517
 518         if (free_index == -1)
 519                 free_index = Num_vertices;
 520
 521         while (Vertex_active[free_index] && (free_index < MAX_VERTICES))
 522                 free_index++;
 523
 524         Assert(free_index < MAX_VERTICES);
 525
 526         Vertices[free_index] = *vp;
 527         Vertex_active[free_index] = 1;
 528
 529         Num_vertices++;
 530
 531         if (free_index > Highest_vertex_index)
 532                 Highest_vertex_index = free_index;
 533
 534         return free_index;
 535 }
 536
 537 // ------------------------------------------------------------------------------------------
 538 //      Returns the index of a free segment.
 539 //      Scans the Segments array.
 540 int get_free_segment_number(void)
 541 {
 542         int     segnum;
 543
 544         for (segnum=0; segnum<MAX_SEGMENTS; segnum++)
 545                 if (Segments[segnum].segnum == -1) {
 546                         Num_segments++;
 547                         if (segnum > Highest_segment_index)
 548                                 Highest_segment_index = segnum;
 549                         return segnum;
 550                 }
 551
 552         Assert(0);
 553
 554         return 0;
 555 }
 556
 557 // -------------------------------------------------------------------------------
 558 //      Create a new segment, duplicating exactly, including vertex ids and children, the passed segment.
 559 int med_create_duplicate_segment(segment *sp)
 560 {
 561         int     segnum;
 562
 563         segnum = get_free_segment_number();
 564
 565         Segments[segnum] = *sp;
 566
 567         return segnum;
 568 }
 569
 570 // -------------------------------------------------------------------------------
 571 //      Add the vertex *vp to the global list of vertices, return its index.
 572 //      This is the same as med_add_vertex, except that it does not search for the presence of the vertex.
 573 int med_create_duplicate_vertex(vms_vector *vp)
 574 {
 575         int     free_index;
 576
 577         Assert(Num_vertices < MAX_SEGMENT_VERTICES);
 578
 579         Do_duplicate_vertex_check = 1;
 580
 581         free_index = Num_vertices;
 582
 583         while (Vertex_active[free_index] && (free_index < MAX_VERTICES))
 584                 free_index++;
 585
 586         Assert(free_index < MAX_VERTICES);
 587
 588         Vertices[free_index] = *vp;
 589         Vertex_active[free_index] = 1;
 590
 591         Num_vertices++;
 592
 593         if (free_index > Highest_vertex_index)
 594                 Highest_vertex_index = free_index;
 595
 596         return free_index;
 597 }
 598
 599
 600 // -------------------------------------------------------------------------------
 601 //      Set the vertex *vp at index vnum in the global list of vertices, return its index (just for compatibility).
 602 int med_set_vertex(int vnum,vms_vector *vp)
 603 {
 604         Assert(vnum < MAX_VERTICES);
 605
 606         Vertices[vnum] = *vp;
 607
 608         // Just in case this vertex wasn't active, mark it as active.
 609         if (!Vertex_active[vnum]) {
 610                 Vertex_active[vnum] = 1;
 611                 Num_vertices++;
 612                 if ((vnum > Highest_vertex_index) && (vnum < NEW_SEGMENT_VERTICES)) {
 613                         mprintf((0,"Warning -- setting a previously unset vertex, index = %i.\n",vnum));
 614                         Highest_vertex_index = vnum;
 615                 }
 616         }
 617
 618         return vnum;
 619 }
 620
 621
 622
 623 //      ----
 624 //      A side is determined to be degenerate if the cross products of 3 consecutive points does not point outward.
 625 int check_for_degenerate_side(segment *sp, int sidenum)
 626 {
 627         char                    *vp = Side_to_verts[sidenum];
 628         vms_vector      vec1, vec2, cross, vec_to_center;
 629         vms_vector      segc, sidec;
 630         fix                     dot;
 631         int                     degeneracy_flag = 0;
 632
 633         compute_segment_center(&segc, sp);
 634         compute_center_point_on_side(&sidec, sp, sidenum);
 635         vm_vec_sub(&vec_to_center, &segc, &sidec);
 636
 637         //vm_vec_sub(&vec1, &Vertices[sp->verts[vp[1]]], &Vertices[sp->verts[vp[0]]]);
 638         //vm_vec_sub(&vec2, &Vertices[sp->verts[vp[2]]], &Vertices[sp->verts[vp[1]]]);
 639         //vm_vec_normalize(&vec1);
 640         //vm_vec_normalize(&vec2);
 641         vm_vec_normalized_dir(&vec1, &Vertices[sp->verts[(int) vp[1]]], &Vertices[sp->verts[(int) vp[0]]]);
 642         vm_vec_normalized_dir(&vec2, &Vertices[sp->verts[(int) vp[2]]], &Vertices[sp->verts[(int) vp[1]]]);
 643         vm_vec_cross(&cross, &vec1, &vec2);
 644
 645         dot = vm_vec_dot(&vec_to_center, &cross);
 646         if (dot <= 0)
 647                 degeneracy_flag |= 1;
 648
 649         //vm_vec_sub(&vec1, &Vertices[sp->verts[vp[2]]], &Vertices[sp->verts[vp[1]]]);
 650         //vm_vec_sub(&vec2, &Vertices[sp->verts[vp[3]]], &Vertices[sp->verts[vp[2]]]);
 651         //vm_vec_normalize(&vec1);
 652         //vm_vec_normalize(&vec2);
 653         vm_vec_normalized_dir(&vec1, &Vertices[sp->verts[(int) vp[2]]], &Vertices[sp->verts[(int) vp[1]]]);
 654         vm_vec_normalized_dir(&vec2, &Vertices[sp->verts[(int) vp[3]]], &Vertices[sp->verts[(int) vp[2]]]);
 655         vm_vec_cross(&cross, &vec1, &vec2);
 656
 657         dot = vm_vec_dot(&vec_to_center, &cross);
 658         if (dot <= 0)
 659                 degeneracy_flag |= 1;
 660
 661         return degeneracy_flag;
 662
 663 }
 664
 665 // -------------------------------------------------------------------------------
 666 void create_removable_wall(segment *sp, int sidenum, int tmap_num)
 667 {
 668         create_walls_on_side(sp, sidenum);
 669
 670         sp->sides[sidenum].tmap_num = tmap_num;
 671
 672         assign_default_uvs_to_side(sp, sidenum);
 673         assign_light_to_side(sp, sidenum);
 674 }
 675
 676 //      ----
 677 //      See if a segment has gotten turned inside out, or something.
 678 //      If so, set global Degenerate_segment_found and return 1, else return 0.
 679 int check_for_degenerate_segment(segment *sp)
 680 {
 681         vms_vector      fvec, rvec, uvec, cross;
 682         fix                     dot;
 683         int                     i, degeneracy_flag = 0;                         // degeneracy flag for current segment
 684
 685         extract_forward_vector_from_segment(sp, &fvec);
 686         extract_right_vector_from_segment(sp, &rvec);
 687         extract_up_vector_from_segment(sp, &uvec);
 688
 689         vm_vec_normalize(&fvec);
 690         vm_vec_normalize(&rvec);
 691         vm_vec_normalize(&uvec);
 692
 693         vm_vec_cross(&cross, &fvec, &rvec);
 694         dot = vm_vec_dot(&cross, &uvec);
 695
 696         if (dot > 0)
 697                 degeneracy_flag = 0;
 698         else {
 699                 mprintf((0, "segment #%i is degenerate due to cross product check.\n", sp-Segments));
 700                 degeneracy_flag = 1;
 701         }
 702
 703         //      Now, see if degenerate because of any side.
 704         for (i=0; i<MAX_SIDES_PER_SEGMENT; i++)
 705                 degeneracy_flag |= check_for_degenerate_side(sp, i);
 706
 707         Degenerate_segment_found |= degeneracy_flag;
 708
 709         return degeneracy_flag;
 710
 711 }
 712
 713 #if 0
 714
 715 // ---------------------------------------------------------------------------------------------
 716 //      Orthogonalize matrix smat, returning result in rmat.
 717 //      Does not modify smat.
 718 //      Uses Gram-Schmidt process.
 719 //      See page 172 of Strang, Gilbert, Linear Algebra and its Applications
 720 //      Matt -- This routine should be moved to the vector matrix library.
 721 //      It IS legal for smat == rmat.
 722 //      We should also have the functions:
 723 //              mat_a = mat_b * scalar;                         // we now have mat_a = mat_a * scalar;
 724 //              mat_a = mat_b + mat_c * scalar; // or maybe not, maybe this is not primitive
 725 void make_orthogonal(vms_matrix *rmat,vms_matrix *smat)
 726 {
 727         vms_matrix              tmat;
 728         vms_vector              tvec1,tvec2;
 729         float                           dot;
 730
 731         // Copy source matrix to work area.
 732         tmat = *smat;
 733
 734         // Normalize the three rows of the matrix tmat.
 735         vm_vec_normalize(&tmat.xrow);
 736         vm_vec_normalize(&tmat.yrow);
 737         vm_vec_normalize(&tmat.zrow);
 738
 739         //      Now, compute the first vector.
 740         // This is very easy -- just copy the (normalized) source vector.
 741         rmat->zrow = tmat.zrow;
 742
 743         // Now, compute the second vector.
 744         // From page 172 of Strang, we use the equation:
 745         //              b' = b - [transpose(q1) * b] * q1
 746         //      where:  b  = the second row of tmat
 747         //                              q1 = the first row of rmat
 748         //                              b' = the second row of rmat
 749
 750         // Compute: transpose(q1) * b
 751         dot = vm_vec_dotprod(&rmat->zrow,&tmat.yrow);
 752
 753         // Compute: b - dot * q1
 754         rmat->yrow.x = tmat.yrow.x - fixmul(dot,rmat->zrow.x);
 755         rmat->yrow.y = tmat.yrow.y - fixmul(dot,rmat->zrow.y);
 756         rmat->yrow.z = tmat.yrow.z - fixmul(dot,rmat->zrow.z);
 757
 758         // Now, compute the third vector.
 759         // From page 173 of Strang, we use the equation:
 760         //              c' = c - (q1*c)*q1 - (q2*c)*q2
 761         //      where:  c  = the third row of tmat
 762         //                              q1 = the first row of rmat
 763         //                              q2 = the second row of rmat
 764         //                              c' = the third row of rmat
 765
 766         // Compute: q1*c
 767         dot = vm_vec_dotprod(&rmat->zrow,&tmat.xrow);
 768
 769         tvec1.x = fixmul(dot,rmat->zrow.x);
 770         tvec1.y = fixmul(dot,rmat->zrow.y);
 771         tvec1.z = fixmul(dot,rmat->zrow.z);
 772
 773         // Compute: q2*c
 774         dot = vm_vec_dotprod(&rmat->yrow,&tmat.xrow);
 775
 776         tvec2.x = fixmul(dot,rmat->yrow.x);
 777         tvec2.y = fixmul(dot,rmat->yrow.y);
 778         tvec2.z = fixmul(dot,rmat->yrow.z);
 779
 780         vm_vec_sub(&rmat->xrow,vm_vec_sub(&rmat->xrow,&tmat.xrow,&tvec1),&tvec2);
 781 }
 782
 783 #endif
 784
 785 // ------------------------------------------------------------------------------------------
 786 // Given a segment, extract the rotation matrix which defines it.
 787 // Do this by extracting the forward, right, up vectors and then making them orthogonal.
 788 // In the process of making the vectors orthogonal, favor them in the order forward, up, right.
 789 // This means that the forward vector will remain unchanged.
 790 void med_extract_matrix_from_segment(segment *sp,vms_matrix *rotmat)
 791 {
 792         vms_vector      forwardvec,upvec;
 793
 794         extract_forward_vector_from_segment(sp,&forwardvec);
 795         extract_up_vector_from_segment(sp,&upvec);
 796
 797         if (((forwardvec.x == 0) && (forwardvec.y == 0) && (forwardvec.z == 0)) || ((upvec.x == 0) && (upvec.y == 0) && (upvec.z == 0))) {
 798                 mprintf((0, "Trapped null vector in med_extract_matrix_from_segment, returning identity matrix.\n"));
 799                 *rotmat = vmd_identity_matrix;
 800                 return;
 801         }
 802
 803
 804         vm_vector_2_matrix(rotmat,&forwardvec,&upvec,NULL);
 805
 806 #if 0
 807         vms_matrix      rm;
 808
 809         extract_forward_vector_from_segment(sp,&rm.zrow);
 810         extract_right_vector_from_segment(sp,&rm.xrow);
 811         extract_up_vector_from_segment(sp,&rm.yrow);
 812
 813         vm_vec_normalize(&rm.xrow);
 814         vm_vec_normalize(&rm.yrow);
 815         vm_vec_normalize(&rm.zrow);
 816
 817         make_orthogonal(rotmat,&rm);
 818
 819         vm_vec_normalize(&rotmat->xrow);
 820         vm_vec_normalize(&rotmat->yrow);
 821         vm_vec_normalize(&rotmat->zrow);
 822
 823 // *rotmat = rm; // include this line (and remove the call to make_orthogonal) if you don't want the matrix orthogonalized
 824 #endif
 825
 826 }
 827
 828 // ------------------------------------------------------------------------------------------
 829 //      Given a rotation matrix *rotmat which describes the orientation of a segment
 830 //      and a side destside, return the rotation matrix which describes the orientation for the side.
 831 void    set_matrix_based_on_side(vms_matrix *rotmat,int destside)
 832 {
 833         vms_angvec      rotvec,*tmpvec;
 834         vms_matrix      r1,rtemp;
 835
 836         switch (destside) {
 837                 case WLEFT:
 838                         tmpvec=vm_angvec_make(&rotvec,0,0,-16384);
 839                         vm_angles_2_matrix(&r1,&rotvec);
 840                         vm_matrix_x_matrix(&rtemp,rotmat,&r1);
 841                         *rotmat = rtemp;
 842                         break;
 843
 844                 case WTOP:
 845                         tmpvec=vm_angvec_make(&rotvec,-16384,0,0);
 846                         vm_angles_2_matrix(&r1,&rotvec);
 847                         vm_matrix_x_matrix(&rtemp,rotmat,&r1);
 848                         *rotmat = rtemp;
 849                         break;
 850
 851                 case WRIGHT:
 852                         tmpvec=vm_angvec_make(&rotvec,0,0,16384);
 853                         vm_angles_2_matrix(&r1,&rotvec);
 854                         vm_matrix_x_matrix(&rtemp,rotmat,&r1);
 855                         *rotmat = rtemp;
 856                         break;
 857
 858                 case WBOTTOM:
 859                         tmpvec=vm_angvec_make(&rotvec,+16384,-32768,0);        // bank was -32768, but I think that was an erroneous compensation
 860                         vm_angles_2_matrix(&r1,&rotvec);
 861                         vm_matrix_x_matrix(&rtemp,rotmat,&r1);
 862                         *rotmat = rtemp;
 863                         break;
 864
 865                 case WFRONT:
 866                         tmpvec=vm_angvec_make(&rotvec,0,0,-32768);
 867                         vm_angles_2_matrix(&r1,&rotvec);
 868                         vm_matrix_x_matrix(&rtemp,rotmat,&r1);
 869                         *rotmat = rtemp;
 870                         break;
 871
 872                 case WBACK:
 873                         break;
 874         }
 875
 876 }
 877
 878 //      -------------------------------------------------------------------------------------
 879 void change_vertex_occurrences(int dest, int src)
 880 {
 881         int     g,s,v;
 882
 883         // Fix vertices in groups
 884         for (g=0;g<num_groups;g++)
 885                 for (v=0; v<GroupList[g].num_vertices; v++)
 886                         if (GroupList[g].vertices[v] == src)
 887                                 GroupList[g].vertices[v] = dest;
 888
 889         // now scan all segments, changing occurrences of src to dest
 890         for (s=0; s<=Highest_segment_index; s++)
 891                 if (Segments[s].segnum != -1)
 892                         for (v=0; v<MAX_VERTICES_PER_SEGMENT; v++)
 893                                 if (Segments[s].verts[v] == src)
 894                                         Segments[s].verts[v] = dest;
 895 }
 896
 897 // --------------------------------------------------------------------------------------------------
 898 void compress_vertices(void)
 899 {
 900         int             hole,vert;
 901
 902         if (Highest_vertex_index == Num_vertices - 1)
 903                 return;
 904
 905         vert = Highest_vertex_index;    //MAX_SEGMENT_VERTICES-1;
 906
 907         for (hole=0; hole < vert; hole++)
 908                 if (!Vertex_active[hole]) {
 909                         // found an unused vertex which is a hole if a used vertex follows (not necessarily immediately) it.
 910                         for ( ; (vert>hole) && (!Vertex_active[vert]); vert--)
 911                                 ;
 912
 913                         if (vert > hole) {
 914
 915                                 // Ok, hole is the index of a hole, vert is the index of a vertex which follows it.
 916                                 // Copy vert into hole, update pointers to it.
 917                                 Vertices[hole] = Vertices[vert];
 918
 919                                 change_vertex_occurrences(hole, vert);
 920
 921                                 vert--;
 922                         }
 923                 }
 924
 925         Highest_vertex_index = Num_vertices-1;
 926 }
 927
 928 // --------------------------------------------------------------------------------------------------
 929 void compress_segments(void)
 930 {
 931         int             hole,seg;
 932
 933         if (Highest_segment_index == Num_segments - 1)
 934                 return;
 935
 936         seg = Highest_segment_index;
 937
 938         for (hole=0; hole < seg; hole++)
 939                 if (Segments[hole].segnum == -1) {
 940                         // found an unused segment which is a hole if a used segment follows (not necessarily immediately) it.
 941                         for ( ; (seg>hole) && (Segments[seg].segnum == -1); seg--)
 942                                 ;
 943
 944                         if (seg > hole) {
 945                                 int             f,g,l,s,t,w;
 946                                 segment *sp;
 947                                 int objnum;
 948
 949                                 // Ok, hole is the index of a hole, seg is the index of a segment which follows it.
 950                                 // Copy seg into hole, update pointers to it, update Cursegp, Markedsegp if necessary.
 951                                 Segments[hole] = Segments[seg];
 952                                 Segments[seg].segnum = -1;
 953
 954                                 if (Cursegp == &Segments[seg])
 955                                         Cursegp = &Segments[hole];
 956
 957                                 if (Markedsegp == &Segments[seg])
 958                                         Markedsegp = &Segments[hole];
 959
 960                                 // Fix segments in groups
 961                                 for (g=0;g<num_groups;g++)
 962                                         for (s=0; s<GroupList[g].num_segments; s++)
 963                                                 if (GroupList[g].segments[s] == seg)
 964                                                         GroupList[g].segments[s] = hole;
 965
 966                                 // Fix walls
 967                                 for (w=0;w<Num_walls;w++)
 968                                         if (Walls[w].segnum == seg)
 969                                                 Walls[w].segnum = hole;
 970
 971                                 // Fix fuelcenters, robotcens, and triggers... added 2/1/95 -Yuan
 972                                 for (f=0;f<Num_fuelcenters;f++)
 973                                         if (Station[f].segnum == seg)
 974                                                 Station[f].segnum = hole;
 975
 976                                 for (f=0;f<Num_robot_centers;f++)
 977                                         if (RobotCenters[f].segnum == seg)
 978                                                 RobotCenters[f].segnum = hole;
 979
 980                                 for (t=0;t<Num_triggers;t++)
 981                                         for (l=0;l<Triggers[t].num_links;l++)
 982                                                 if (Triggers[t].seg[l] == seg)
 983                                                         Triggers[t].seg[l] = hole;
 984
 985                                 sp = &Segments[hole];
 986                                 for (s=0; s<MAX_SIDES_PER_SEGMENT; s++) {
 987                                         if (IS_CHILD(sp->children[s])) {
 988                                                 segment *csegp;
 989                                                 csegp = &Segments[sp->children[s]];
 990
 991                                                 // Find out on what side the segment connection to the former seg is on in *csegp.
 992                                                 for (t=0; t<MAX_SIDES_PER_SEGMENT; t++) {
 993                                                         if (csegp->children[t] == seg) {
 994                                                                 csegp->children[t] = hole;                                      // It used to be connected to seg, so make it connected to hole
 995                                                         }
 996                                                 }       // end for t
 997                                         }       // end if
 998                                 }       // end for s
 999
1000                                 //Update object segment pointers
1001                                 for (objnum = sp->objects; objnum != -1; objnum = Objects[objnum].next) {
1002                                         Assert(Objects[objnum].segnum == seg);
1003                                         Objects[objnum].segnum = hole;
1004                                 }
1005
1006                                 seg--;
1007
1008                         }       // end if (seg > hole)
1009                 }       // end if
1010
1011         Highest_segment_index = Num_segments-1;
1012         med_create_new_segment_from_cursegp();
1013
1014 }
1015
1016
1017 // -------------------------------------------------------------------------------
1018 //      Combine duplicate vertices.
1019 //      If two vertices have the same coordinates, within some small tolerance, then assign
1020 //      the same vertex number to the two vertices, freeing up one of the vertices.
1021 void med_combine_duplicate_vertices(byte *vlp)
1022 {
1023         int     v,w;
1024
1025         for (v=0; v<Highest_vertex_index; v++)          // Note: ok to do to <, rather than <= because w for loop starts at v+1
1026                 if (vlp[v]) {
1027                         vms_vector *vvp = &Vertices[v];
1028                         for (w=v+1; w<=Highest_vertex_index; w++)
1029                                 if (vlp[w]) {   //      used to be Vertex_active[w]
1030                                         if (vnear(vvp, &Vertices[w])) {
1031                                                 change_vertex_occurrences(v, w);
1032                                         }
1033                                 }
1034                 }
1035
1036 }
1037
1038 // ------------------------------------------------------------------------------
1039 //      Compress mine at Segments and Vertices by squeezing out all holes.
1040 //      If no holes (ie, an unused segment followed by a used segment), then no action.
1041 //      If Cursegp or Markedsegp is a segment which gets moved to fill in a hole, then
1042 //      they are properly updated.
1043 void med_compress_mine(void)
1044 {
1045         if (Do_duplicate_vertex_check) {
1046                 med_combine_duplicate_vertices(Vertex_active);
1047                 Do_duplicate_vertex_check = 0;
1048         }
1049
1050         compress_segments();
1051         compress_vertices();
1052         set_vertex_counts();
1053
1054         //--repair-- create_local_segment_data();
1055
1056         //      This is necessary becuase a segment search (due to click in 3d window) uses the previous frame's
1057         //      segment information, which could get changed by this.
1058         Update_flags = UF_WORLD_CHANGED;
1059 }
1060
1061
1062 // ------------------------------------------------------------------------------------------
1063 //      Copy texture map ids for each face in sseg to dseg.
1064 void copy_tmap_ids(segment *dseg, segment *sseg)
1065 {
1066         int     s;
1067
1068         for (s=0; s<MAX_SIDES_PER_SEGMENT; s++) {
1069                 dseg->sides[s].tmap_num = sseg->sides[s].tmap_num;
1070                 dseg->sides[s].tmap_num2 = 0;
1071         }
1072 }
1073
1074 // ------------------------------------------------------------------------------------------
1075 //      Attach a segment with a rotated orientation.
1076 // Return value:
1077 //  0 = successful attach
1078 //  1 = No room in Segments[].
1079 //  2 = No room in Vertices[].
1080 //  3 = newside != WFRONT -- for now, the new segment must be attached at its (own) front side
1081 //       4 = already a face attached on destseg:destside
1082 int med_attach_segment_rotated(segment *destseg, segment *newseg, int destside, int newside,vms_matrix *attmat)
1083 {
1084         char                    *dvp;
1085         segment         *nsp;
1086         segment2        *nsp2;
1087         int                     side,v;
1088         vms_matrix      rotmat,rotmat1,rotmat2,rotmat3,rotmat4;
1089         vms_vector      vr,vc,tvs[4],xlate_vec;
1090         int                     segnum;
1091         vms_vector      forvec,upvec;
1092
1093         // Return if already a face attached on this side.
1094         if (IS_CHILD(destseg->children[destside]))
1095                 return 4;
1096
1097         segnum = get_free_segment_number();
1098
1099         forvec = attmat->fvec;
1100         upvec = attmat->uvec;
1101
1102         //      We are pretty confident we can add the segment.
1103         nsp = &Segments[segnum];
1104         nsp2 = &Segment2s[segnum];
1105
1106         nsp->segnum = segnum;
1107         nsp->objects = -1;
1108         nsp2->matcen_num = -1;
1109
1110         // Copy group value.
1111         nsp->group = destseg->group;
1112
1113         // Add segment to proper group list.
1114         if (nsp->group > -1)
1115                 add_segment_to_group(nsp-Segments, nsp->group);
1116
1117         // Copy the texture map ids.
1118         copy_tmap_ids(nsp,newseg);
1119
1120         // clear all connections
1121         for (side=0; side<MAX_SIDES_PER_SEGMENT; side++) {
1122                 nsp->children[side] = -1;
1123                 nsp->sides[side].wall_num = -1;
1124         }
1125
1126         // Form the connection
1127         destseg->children[destside] = segnum;
1128 //      destseg->sides[destside].render_flag = 0;
1129         nsp->children[newside] = destseg-Segments;
1130
1131         // Copy vertex indices of the four vertices forming the joint
1132         dvp = Side_to_verts[destside];
1133
1134         // Set the vertex indices for the four vertices forming the front of the new side
1135         for (v=0; v<4; v++)
1136                 nsp->verts[v] = destseg->verts[(int) dvp[v]];
1137
1138         // The other 4 vertices must be created.
1139         // Their coordinates are determined by the 4 welded vertices and the vector from front
1140         // to back of the original *newseg.
1141
1142         // Do lots of hideous matrix stuff, about 3/4 of which could probably be simplified out.
1143         med_extract_matrix_from_segment(destseg,&rotmat);               // get orientation matrix for destseg (orthogonal rotation matrix)
1144         set_matrix_based_on_side(&rotmat,destside);
1145         vm_vector_2_matrix(&rotmat1,&forvec,&upvec,NULL);
1146         vm_matrix_x_matrix(&rotmat4,&rotmat,&rotmat1);                  // this is the desired orientation of the new segment
1147         med_extract_matrix_from_segment(newseg,&rotmat3);               // this is the current orientation of the new segment
1148         vm_transpose_matrix(&rotmat3);                                                          // get the inverse of the current orientation matrix
1149         vm_matrix_x_matrix(&rotmat2,&rotmat4,&rotmat3);                 // now rotmat2 takes the current segment to the desired orientation
1150
1151         // Warning -- look at this line!
1152         vm_transpose_matrix(&rotmat2);  // added 12:33 pm, 10/01/93
1153
1154         // Compute and rotate the center point of the attaching face.
1155         compute_center_point_on_side(&vc,newseg,newside);
1156         vm_vec_rotate(&vr,&vc,&rotmat2);
1157
1158         // Now rotate the free vertices in the segment
1159         for (v=0; v<4; v++)
1160                 vm_vec_rotate(&tvs[v],&Vertices[newseg->verts[v+4]],&rotmat2);
1161
1162         // Now translate the new segment so that the center point of the attaching faces are the same.
1163         compute_center_point_on_side(&vc,destseg,destside);
1164         vm_vec_sub(&xlate_vec,&vc,&vr);
1165
1166         // Create and add the 4 new vertices.
1167         for (v=0; v<4; v++) {
1168                 vm_vec_add2(&tvs[v],&xlate_vec);
1169                 nsp->verts[v+4] = med_add_vertex(&tvs[v]);
1170         }
1171
1172         set_vertex_counts();
1173
1174         // Now all the vertices are in place.  Create the faces.
1175         validate_segment(nsp);
1176
1177         //      Say to not render at the joint.
1178 //      destseg->sides[destside].render_flag = 0;
1179 //      nsp->sides[newside].render_flag = 0;
1180
1181         Cursegp = nsp;
1182
1183         return  0;
1184 }
1185
1186 // @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
1187
1188 // ------------------------------------------------------------------------------------------
1189 void scale_free_vertices(segment *sp,vms_vector *vp,fix scale_factor,int min_side,int max_side)
1190 {
1191         int     i;
1192         char    *verts;
1193
1194         verts = Side_to_verts[min_side];
1195
1196         for (i=0; i<4; i++)
1197                 if (is_free_vertex(sp->verts[(int) verts[i]])) {
1198                         Vertices[sp->verts[(int) verts[i]]].x = fixmul(vp->x,scale_factor)/2;
1199                         Vertices[sp->verts[(int) verts[i]]].y = fixmul(vp->y,scale_factor)/2;
1200                         Vertices[sp->verts[(int) verts[i]]].z = fixmul(vp->z,scale_factor)/2;
1201                 }
1202
1203         verts = Side_to_verts[max_side];
1204
1205         for (i=0; i<4; i++)
1206                 if (is_free_vertex(sp->verts[(int) verts[i]])) {
1207                         Vertices[sp->verts[(int) verts[i]]].x = fixmul(vp->x,scale_factor)/2;
1208                         Vertices[sp->verts[(int) verts[i]]].y = fixmul(vp->y,scale_factor)/2;
1209                         Vertices[sp->verts[(int) verts[i]]].z = fixmul(vp->z,scale_factor)/2;
1210                 }
1211 }
1212
1213
1214 // ------------------------------------------------------------------------------------------
1215 // Attach side newside of newseg to side destside of destseg.
1216 // Copies *newseg into global array Segments, increments Num_segments.
1217 // Forms a weld between the two segments by making the new segment fit to the old segment.
1218 // Updates number of faces per side if necessitated by new vertex coordinates.
1219 //      Updates Cursegp.
1220 // Return value:
1221 //  0 = successful attach
1222 //  1 = No room in Segments[].
1223 //  2 = No room in Vertices[].
1224 //  3 = newside != WFRONT -- for now, the new segment must be attached at its (own) front side
1225 //       4 = already a face attached on side newside
1226 int med_attach_segment(segment *destseg, segment *newseg, int destside, int newside)
1227 {
1228         int             rval;
1229         segment *ocursegp = Cursegp;
1230
1231         vms_angvec      tang = {0,0,0};
1232         vms_matrix      rotmat;
1233
1234         vm_angles_2_matrix(&rotmat,&tang);
1235         rval = med_attach_segment_rotated(destseg,newseg,destside,newside,&rotmat);
1236         med_propagate_tmaps_to_segments(ocursegp,Cursegp,0);
1237         med_propagate_tmaps_to_back_side(Cursegp, Side_opposite[newside],0);
1238         copy_uvs_seg_to_seg(&New_segment,Cursegp);
1239
1240         return rval;
1241 }
1242
1243 // -------------------------------------------------------------------------------
1244 //      Delete a vertex, sort of.
1245 //      Decrement the vertex count.  If the count goes to 0, then the vertex is free (has been deleted).
1246 void delete_vertex(short v)
1247 {
1248         Assert(v < MAX_VERTICES);                       // abort if vertex is not in array Vertices
1249         Assert(Vertex_active[v] >= 1);  // abort if trying to delete a non-existent vertex
1250
1251         Vertex_active[v]--;
1252 }
1253
1254 // -------------------------------------------------------------------------------
1255 //      Update Num_vertices.
1256 //      This routine should be called by anyone who calls delete_vertex.  It could be called in delete_vertex,
1257 //      but then it would be called much more often than necessary, and it is a slow routine.
1258 void update_num_vertices(void)
1259 {
1260         int     v;
1261
1262         // Now count the number of vertices.
1263         Num_vertices = 0;
1264         for (v=0; v<=Highest_vertex_index; v++)
1265                 if (Vertex_active[v])
1266                         Num_vertices++;
1267 }
1268
1269 // -------------------------------------------------------------------------------
1270 //      Set Vertex_active to number of occurrences of each vertex.
1271 //      Set Num_vertices.
1272 void set_vertex_counts(void)
1273 {
1274         int     s,v;
1275
1276         Num_vertices = 0;
1277
1278         for (v=0; v<=Highest_vertex_index; v++)
1279                 Vertex_active[v] = 0;
1280
1281         // Count number of occurrences of each vertex.
1282         for (s=0; s<=Highest_segment_index; s++)
1283                 if (Segments[s].segnum != -1)
1284                         for (v=0; v<MAX_VERTICES_PER_SEGMENT; v++) {
1285                                 if (!Vertex_active[Segments[s].verts[v]])
1286                                         Num_vertices++;
1287                                 Vertex_active[Segments[s].verts[v]]++;
1288                         }
1289 }
1290
1291 // -------------------------------------------------------------------------------
1292 //      Delete all vertices in segment *sp from the vertex list if they are not contained in another segment.
1293 //      This is kind of a dangerous routine.  It modifies the global array Vertex_active, using the field as
1294 //      a count.
1295 void delete_vertices_in_segment(segment *sp)
1296 {
1297         int     v;
1298
1299 //      init_vertices();
1300
1301         set_vertex_counts();
1302
1303         // Subtract one count for each appearance of vertex in deleted segment
1304         for (v=0; v<MAX_VERTICES_PER_SEGMENT; v++)
1305                 delete_vertex(sp->verts[v]);
1306
1307         update_num_vertices();
1308 }
1309
1310 extern void validate_segment_side(segment *sp, int sidenum);
1311
1312 // -------------------------------------------------------------------------------
1313 //      Delete segment *sp in Segments array.
1314 // Return value:
1315 //              0       successfully deleted.
1316 //              1       unable to delete.
1317 int med_delete_segment(segment *sp)
1318 {
1319         int             s,side,segnum;
1320         int             objnum;
1321
1322         segnum = sp-Segments;
1323
1324         // Cannot delete segment if only segment.
1325         if (Num_segments == 1)
1326                 return 1;
1327
1328         // Don't try to delete if segment doesn't exist.
1329         if (sp->segnum == -1) {
1330                 mprintf((0,"Hey -- you tried to delete a non-existent segment (segnum == -1)\n"));
1331                 return 1;
1332         }
1333
1334         // Delete its refueling center if it has one
1335         fuelcen_delete(sp);
1336
1337         delete_vertices_in_segment(sp);
1338
1339         Num_segments--;
1340
1341         // If deleted segment has walls on any side, wipe out the wall.
1342         for (side=0; side < MAX_SIDES_PER_SEGMENT; side++)
1343                 if (sp->sides[side].wall_num != -1)
1344                         wall_remove_side(sp, side);
1345
1346         // Find out what this segment was connected to and break those connections at the other end.
1347         for (side=0; side < MAX_SIDES_PER_SEGMENT; side++)
1348                 if (IS_CHILD(sp->children[side])) {
1349                         segment *csp;                                                                   // the connecting segment
1350                         int             s;
1351
1352                         csp = &Segments[sp->children[side]];
1353                         for (s=0; s<MAX_SIDES_PER_SEGMENT; s++)
1354                                 if (csp->children[s] == segnum) {
1355                                         csp->children[s] = -1;                          // this is the side of connection, break it
1356                                         validate_segment_side(csp,s);                                   // we have converted a connection to a side so validate the segment
1357                                         med_propagate_tmaps_to_back_side(csp,s,0);
1358                                 }
1359                         Cursegp = csp;
1360                         med_create_new_segment_from_cursegp();
1361                         copy_uvs_seg_to_seg(&New_segment,Cursegp);
1362                 }
1363
1364         sp->segnum = -1;                                                                                // Mark segment as inactive.
1365
1366         // If deleted segment = marked segment, then say there is no marked segment
1367         if (sp == Markedsegp)
1368                 Markedsegp = 0;
1369
1370         //      If deleted segment = a Group segment ptr, then wipe it out.
1371         for (s=0;s<num_groups;s++)
1372                 if (sp == Groupsegp[s])
1373                         Groupsegp[s] = 0;
1374
1375         // If deleted segment = group segment, wipe it off the group list.
1376         if (sp->group > -1)
1377                         delete_segment_from_group(sp-Segments, sp->group);
1378
1379         // If we deleted something which was not connected to anything, must now select a new current segment.
1380         if (Cursegp == sp)
1381                 for (s=0; s<MAX_SEGMENTS; s++)
1382                         if ((Segments[s].segnum != -1) && (s!=segnum) ) {
1383                                 Cursegp = &Segments[s];
1384                                 med_create_new_segment_from_cursegp();
1385                         break;
1386                         }
1387
1388         // If deleted segment contains objects, wipe out all objects
1389         if (sp->objects != -1)  {
1390 //              if (objnum == Objects[objnum].next) {
1391 //                      mprintf((0, "Warning -- object #%i points to itself.  Setting next to -1.\n", objnum));
1392 //                      Objects[objnum].next = -1;
1393 //              }
1394                 for (objnum=sp->objects;objnum!=-1;objnum=Objects[objnum].next)         {
1395
1396                         //if an object is in the seg, delete it
1397                         //if the object is the player, move to new curseg
1398
1399                         if (objnum == (ConsoleObject-Objects))  {
1400                                 compute_segment_center(&ConsoleObject->pos,Cursegp);
1401                                 obj_relink(objnum,Cursegp-Segments);
1402                         } else
1403                                 obj_delete(objnum);
1404                 }
1405         }
1406
1407         // Make sure everything deleted ok...
1408         Assert( sp->objects==-1 );
1409
1410         // If we are leaving many holes in Segments or Vertices, then compress mine, because it is inefficient to be that way
1411 //      if ((Highest_segment_index > Num_segments+4) || (Highest_vertex_index > Num_vertices+4*8))
1412 //              med_compress_mine();
1413
1414         return 0;
1415 }
1416
1417 // ------------------------------------------------------------------------------------------
1418 //      Copy texture maps from sseg to dseg
1419 void copy_tmaps_to_segment(segment *dseg, segment *sseg)
1420 {
1421         int     s;
1422
1423         for (s=0; s<MAX_SIDES_PER_SEGMENT; s++) {
1424                 dseg->sides[s].type = sseg->sides[s].type;
1425                 dseg->sides[s].tmap_num = sseg->sides[s].tmap_num;
1426                 dseg->sides[s].tmap_num2 = sseg->sides[s].tmap_num2;
1427         }
1428
1429 }
1430
1431 // ------------------------------------------------------------------------------------------
1432 // Rotate the segment *seg by the pitch, bank, heading defined by *rot, destructively
1433 // modifying its four free vertices in the global array Vertices.
1434 // It is illegal to rotate a segment which has connectivity != 1.
1435 // Pitch, bank, heading are about the point which is the average of the four points
1436 // forming the side of connection.
1437 // Return value:
1438 //  0 = successful rotation
1439 //  1 = Connectivity makes rotation illegal (connected to 0 or 2+ segments)
1440 //  2 = Rotation causes degeneracy, such as self-intersecting segment.
1441 //       3 = Unable to rotate because not connected to exactly 1 segment.
1442 int med_rotate_segment(segment *seg, vms_matrix *rotmat)
1443 {
1444         segment *destseg;
1445         int             newside=0,destside,s;
1446         int             count;
1447         int             back_side,side_tmaps[MAX_SIDES_PER_SEGMENT];
1448
1449         // Find side of attachment
1450         count = 0;
1451         for (s=0; s<MAX_SIDES_PER_SEGMENT; s++)
1452                 if (IS_CHILD(seg->children[s])) {
1453                         count++;
1454                         newside = s;
1455                 }
1456
1457         // Return if passed in segment is connected to other than 1 segment.
1458         if (count != 1)
1459                 return 3;
1460
1461         destseg = &Segments[seg->children[newside]];
1462
1463         destside = 0;
1464         while ((destseg->children[destside] != seg-Segments) && (destside < MAX_SIDES_PER_SEGMENT))
1465                 destside++;
1466
1467         // Before deleting the segment, copy its texture maps to New_segment
1468         copy_tmaps_to_segment(&New_segment,seg);
1469
1470         if (med_delete_segment(seg))
1471                 mprintf((0,"Error in rotation: Unable to delete segment %i\n",seg-Segments));
1472
1473         if (Curside == WFRONT)
1474                 Curside = WBACK;
1475
1476         med_attach_segment_rotated(destseg,&New_segment,destside,AttachSide,rotmat);
1477
1478         //      Save tmap_num on each side to restore after call to med_propagate_tmaps_to_segments and _back_side
1479         //      which will change the tmap nums.
1480         for (s=0; s<MAX_SIDES_PER_SEGMENT; s++)
1481                 side_tmaps[s] = seg->sides[s].tmap_num;
1482
1483         back_side = Side_opposite[find_connect_side(destseg, seg)];
1484
1485         med_propagate_tmaps_to_segments(destseg, seg,0);
1486         med_propagate_tmaps_to_back_side(seg, back_side,0);
1487
1488         for (s=0; s<MAX_SIDES_PER_SEGMENT; s++)
1489                 if (s != back_side)
1490                         seg->sides[s].tmap_num = side_tmaps[s];
1491
1492         return  0;
1493 }
1494
1495 // ----------------------------------------------------------------------------------------
1496 int med_rotate_segment_ang(segment *seg, vms_angvec *ang)
1497 {
1498         vms_matrix      rotmat;
1499
1500         return med_rotate_segment(seg,vm_angles_2_matrix(&rotmat,ang));
1501 }
1502
1503 // @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
1504
1505 // ----------------------------------------------------------------------------
1506 //      Compute the sum of the distances between the four pairs of points.
1507 //      The connections are:
1508 //              firstv1 : 0             (firstv1+1)%4 : 1               (firstv1+2)%4 : 2               (firstv1+3)%4 : 3
1509 fix seg_seg_vertex_distsum(segment *seg1, int side1, segment *seg2, int side2, int firstv1)
1510 {
1511         fix     distsum;
1512         int     secondv;
1513
1514         distsum = 0;
1515         for (secondv=0; secondv<4; secondv++) {
1516                 int                     firstv;
1517
1518                 firstv = (4-secondv + (3 - firstv1)) % 4;
1519                 distsum += vm_vec_dist(&Vertices[seg1->verts[Side_to_verts[side1][firstv]]],&Vertices[seg2->verts[Side_to_verts[side2][secondv]]]);
1520         }
1521
1522         return distsum;
1523
1524 }
1525
1526 // ----------------------------------------------------------------------------
1527 //      Determine how to connect two segments together with the least amount of twisting.
1528 //      Returns vertex index in 0..3 on first segment.  Assumed ordering of vertices
1529 //      on second segment is 0,1,2,3.
1530 //      So, if return value is 2, connect 2:0 3:1 0:2 1:3.
1531 //      Theory:
1532 //              We select an ordering of vertices for connection.  For the first pair of vertices to be connected,
1533 //              compute the vector.  For the three remaining pairs of vertices, compute the vectors from one vertex
1534 //              to the other.  Compute the dot products of these vectors with the original vector.  Add them up.
1535 //              The close we are to 3, the better fit we have.  Reason:  The largest value for the dot product is
1536 //              1.0, and this occurs for a parallel set of vectors.
1537 int get_index_of_best_fit(segment *seg1, int side1, segment *seg2, int side2)
1538 {
1539         int     firstv;
1540         fix     min_distance;
1541         int     best_index=0;
1542
1543         min_distance = F1_0*30000;
1544
1545         for (firstv=0; firstv<4; firstv++) {
1546                 fix t;
1547                 t = seg_seg_vertex_distsum(seg1, side1, seg2, side2, firstv);
1548                 if (t <= min_distance) {
1549                         min_distance = t;
1550                         best_index = firstv;
1551                 }
1552         }
1553
1554         return best_index;
1555
1556 }
1557
1558
1559 #define MAX_VALIDATIONS 50
1560
1561 // ----------------------------------------------------------------------------
1562 //      Remap uv coordinates in all sides in segment *sp which have a vertex in vp[4].
1563 //      vp contains absolute vertex indices.
1564 void remap_side_uvs(segment *sp,int *vp)
1565 {
1566         int     s,i,v;
1567
1568         for (s=0; s<MAX_SIDES_PER_SEGMENT; s++) {
1569                 for (v=0; v<4; v++)
1570                         for (i=0; i<4; i++)                                                                                             // scan each vertex in vp[4]
1571                                 if (Side_to_verts[s][v] == vp[i]) {
1572                                         assign_default_uvs_to_side(sp,s);                                       // Side s needs to be remapped
1573                                         goto next_side;
1574                                 }
1575 next_side: ;
1576         }
1577 }
1578
1579 // ----------------------------------------------------------------------------
1580 //      Assign default uv coordinates to Curside.
1581 void assign_default_uvs_to_curside(void)
1582 {
1583         assign_default_uvs_to_side(Cursegp, Curside);
1584 }
1585
1586 // ----------------------------------------------------------------------------
1587 //      Assign default uv coordinates to all sides in Curside.
1588 void assign_default_uvs_to_curseg(void)
1589 {
1590         int     s;
1591
1592         for (s=0; s<MAX_SIDES_PER_SEGMENT; s++)
1593                 assign_default_uvs_to_side(Cursegp,s);                                  // Side s needs to be remapped
1594 }
1595
1596 // ----------------------------------------------------------------------------
1597 //      Modify seg2 to share side2 with seg1:side1.  This forms a connection between
1598 //      two segments without creating a new segment.  It modifies seg2 by sharing
1599 //      vertices from seg1.  seg1 is not modified.  Four vertices from seg2 are
1600 //      deleted.
1601 //      Return code:
1602 //              0                       joint formed
1603 //              1                       -- no, this is legal! -- unable to form joint because one or more vertices of side2 is not free
1604 //              2                       unable to form joint because side1 is already used
1605 int med_form_joint(segment *seg1, int side1, segment *seg2, int side2)
1606 {
1607         char            *vp1,*vp2;
1608         int             bfi,v,s,sv,s1,nv;
1609         int             lost_vertices[4],remap_vertices[4];
1610         int             validation_list[MAX_VALIDATIONS];
1611
1612         //      Make sure that neither side is connected.
1613         if (IS_CHILD(seg1->children[side1]) || IS_CHILD(seg2->children[side2]))
1614                 return 2;
1615
1616         // Make sure there is no wall there
1617         if ((seg1->sides[side1].wall_num != -1) || (seg2->sides[side2].wall_num != -1))
1618                 return 2;
1619
1620         //      We can form the joint.  Find the best orientation of vertices.
1621         bfi = get_index_of_best_fit(seg1, side1, seg2, side2);
1622
1623         vp1 = Side_to_verts[side1];
1624         vp2 = Side_to_verts[side2];
1625
1626         //      Make a copy of the list of vertices in seg2 which will be deleted and set the
1627         //      associated vertex number, so that all occurrences of the vertices can be replaced.
1628         for (v=0; v<4; v++)
1629                 lost_vertices[v] = seg2->verts[(int) vp2[v]];
1630
1631         //      Now, for each vertex in lost_vertices, determine which vertex it maps to.
1632         for (v=0; v<4; v++)
1633                 remap_vertices[3 - ((v + bfi) % 4)] = seg1->verts[(int) vp1[v]];
1634
1635         // Now, in all segments, replace all occurrences of vertices in lost_vertices with remap_vertices
1636
1637         // Put the one segment we know are being modified into the validation list.
1638         // Note: seg1 does not require a full validation, only a validation of the affected side.  Its vertices do not move.
1639         nv = 1;
1640         validation_list[0] = seg2 - Segments;
1641
1642         for (v=0; v<4; v++)
1643                 for (s=0; s<=Highest_segment_index; s++)
1644                         if (Segments[s].segnum != -1)
1645                                 for (sv=0; sv<MAX_VERTICES_PER_SEGMENT; sv++)
1646                                         if (Segments[s].verts[sv] == lost_vertices[v]) {
1647                                                 Segments[s].verts[sv] = remap_vertices[v];
1648                                                 // Add segment to list of segments to be validated.
1649                                                 for (s1=0; s1<nv; s1++)
1650                                                         if (validation_list[s1] == s)
1651                                                                 break;
1652                                                 if (s1 == nv)
1653                                                         validation_list[nv++] = s;
1654                                                 Assert(nv < MAX_VALIDATIONS);
1655                                         }
1656
1657         //      Form new connections.
1658         seg1->children[side1] = seg2 - Segments;
1659         seg2->children[side2] = seg1 - Segments;
1660
1661         // validate all segments
1662         validate_segment_side(seg1,side1);
1663         for (s=0; s<nv; s++) {
1664                 validate_segment(&Segments[validation_list[s]]);
1665                 remap_side_uvs(&Segments[validation_list[s]],remap_vertices);   // remap uv coordinates on sides which were reshaped (ie, have a vertex in lost_vertices)
1666                 warn_if_concave_segment(&Segments[validation_list[s]]);
1667         }
1668
1669         set_vertex_counts();
1670
1671         //      Make sure connection is open, ie renderable.
1672 //      seg1->sides[side1].render_flag = 0;
1673 //      seg2->sides[side2].render_flag = 0;
1674
1675 //--// debug -- check all segments, make sure if a children[s] == -1, then side[s].num_faces != 0
1676 //--{
1677 //--int seg,side;
1678 //--for (seg=0; seg<MAX_SEGMENTS; seg++)
1679 //--    if (Segments[seg].segnum != -1)
1680 //--            for (side=0; side<MAX_SIDES_PER_SEGMENT; side++)
1681 //--                    if (Segments[seg].children[side] == -1) {
1682 //--                            if (Segments[seg].sides[side].num_faces == 0) {
1683 //--                                    mprintf((0,"Error: Segment %i, side %i is not connected, but has 0 faces.\n",seg,side));
1684 //--                                    Int3();
1685 //--                            }
1686 //--                    } else if (Segments[seg].sides[side].num_faces != 0) {
1687 //--                            mprintf((0,"Error: Segment %i, side %i is connected, but has %i faces.\n",seg,side,Segments[seg].sides[side].num_faces));
1688 //--                            Int3();
1689 //--                    }
1690 //--}
1691
1692         return 0;
1693 }
1694
1695 // ----------------------------------------------------------------------------
1696 //      Create a new segment and use it to form a bridge between two existing segments.
1697 //      Specify two segment:side pairs.  If either segment:side is not open (ie, segment->children[side] != -1)
1698 //      then it is not legal to form the brider.
1699 //      Return:
1700 //              0       bridge segment formed
1701 //              1       unable to form bridge because one (or both) of the sides is not open.
1702 //      Note that no new vertices are created by this process.
1703 int med_form_bridge_segment(segment *seg1, int side1, segment *seg2, int side2)
1704 {
1705         segment         *bs;
1706         char                    *sv;
1707         int                     v,bfi,i;
1708
1709         if (IS_CHILD(seg1->children[side1]) || IS_CHILD(seg2->children[side2]))
1710                 return 1;
1711
1712         bs = &Segments[get_free_segment_number()];
1713 // mprintf((0,"Forming bridge segment %i from %i to %i\n",bs-Segments,seg1-Segments,seg2-Segments));
1714
1715         bs->segnum = bs-Segments;
1716         bs->objects = -1;
1717
1718         // Copy vertices from seg2 into last 4 vertices of bridge segment.
1719         sv = Side_to_verts[side2];
1720         for (v=0; v<4; v++)
1721                 bs->verts[(3-v)+4] = seg2->verts[(int) sv[v]];
1722
1723         // Copy vertices from seg1 into first 4 vertices of bridge segment.
1724         bfi = get_index_of_best_fit(seg1, side1, seg2, side2);
1725
1726         sv = Side_to_verts[side1];
1727         for (v=0; v<4; v++)
1728                 bs->verts[(v + bfi) % 4] = seg1->verts[(int) sv[v]];
1729
1730         // Form connections to children, first initialize all to unconnected.
1731         for (i=0; i<MAX_SIDES_PER_SEGMENT; i++) {
1732                 bs->children[i] = -1;
1733                 bs->sides[i].wall_num = -1;
1734         }
1735
1736         // Now form connections between segments.
1737
1738         bs->children[AttachSide] = seg1 - Segments;
1739         bs->children[(int) Side_opposite[AttachSide]] = seg2 - Segments;
1740
1741         seg1->children[side1] = bs-Segments; //seg2 - Segments;
1742         seg2->children[side2] = bs-Segments; //seg1 - Segments;
1743
1744         //      Validate bridge segment, and if degenerate, clean up mess.
1745         Degenerate_segment_found = 0;
1746
1747         validate_segment(bs);
1748
1749         if (Degenerate_segment_found) {
1750                 seg1->children[side1] = -1;
1751                 seg2->children[side2] = -1;
1752                 bs->children[AttachSide] = -1;
1753                 bs->children[(int) Side_opposite[AttachSide]] = -1;
1754                 if (med_delete_segment(bs)) {
1755                         mprintf((0, "Oops, tried to delete bridge segment (because it's degenerate), but couldn't.\n"));
1756                         Int3();
1757                 }
1758                 editor_status("Bridge segment would be degenerate, not created.\n");
1759                 return 1;
1760         } else {
1761                 validate_segment(seg1); // used to only validate side, but segment does more error checking: ,side1);
1762                 validate_segment(seg2); // ,side2);
1763                 med_propagate_tmaps_to_segments(seg1,bs,0);
1764
1765                 editor_status("Bridge segment formed.");
1766                 warn_if_concave_segment(bs);
1767                 return 0;
1768         }
1769 }
1770
1771 // -------------------------------------------------------------------------------
1772 //      Create a segment given center, dimensions, rotation matrix.
1773 //      Note that the created segment will always have planar sides and rectangular cross sections.
1774 //      It will be created with walls on all sides, ie not connected to anything.
1775 void med_create_segment(segment *sp,fix cx, fix cy, fix cz, fix length, fix width, fix height, vms_matrix *mp)
1776 {
1777         int                     i,f;
1778         vms_vector      v0,v1,cv;
1779         segment2 *sp2;
1780
1781         Num_segments++;
1782
1783         sp->segnum = 1;                                         // What to put here?  I don't know.
1784         sp2 = &Segment2s[sp->segnum];
1785
1786         // Form connections to children, of which it has none.
1787         for (i=0; i<MAX_SIDES_PER_SEGMENT; i++) {
1788                 sp->children[i] = -1;
1789 //              sp->sides[i].render_flag = 0;
1790                 sp->sides[i].wall_num  = -1;
1791         }
1792
1793         sp->group = -1;
1794         sp2->matcen_num = -1;
1795
1796         //      Create relative-to-center vertices, which are the rotated points on the box defined by length, width, height
1797         sp->verts[0] = med_add_vertex(vm_vec_rotate(&v1,vm_vec_make(&v0,+width/2,+height/2,-length/2),mp));
1798         sp->verts[1] = med_add_vertex(vm_vec_rotate(&v1,vm_vec_make(&v0,+width/2,-height/2,-length/2),mp));
1799         sp->verts[2] = med_add_vertex(vm_vec_rotate(&v1,vm_vec_make(&v0,-width/2,-height/2,-length/2),mp));
1800         sp->verts[3] = med_add_vertex(vm_vec_rotate(&v1,vm_vec_make(&v0,-width/2,+height/2,-length/2),mp));
1801         sp->verts[4] = med_add_vertex(vm_vec_rotate(&v1,vm_vec_make(&v0,+width/2,+height/2,+length/2),mp));
1802         sp->verts[5] = med_add_vertex(vm_vec_rotate(&v1,vm_vec_make(&v0,+width/2,-height/2,+length/2),mp));
1803         sp->verts[6] = med_add_vertex(vm_vec_rotate(&v1,vm_vec_make(&v0,-width/2,-height/2,+length/2),mp));
1804         sp->verts[7] = med_add_vertex(vm_vec_rotate(&v1,vm_vec_make(&v0,-width/2,+height/2,+length/2),mp));
1805
1806         // Now create the vector which is the center of the segment and add that to all vertices.
1807         while (!vm_vec_make(&cv,cx,cy,cz));
1808
1809         //      Now, add the center to all vertices, placing the segment in 3 space.
1810         for (i=0; i<MAX_VERTICES_PER_SEGMENT; i++)
1811                 vm_vec_add(&Vertices[sp->verts[i]],&Vertices[sp->verts[i]],&cv);
1812
1813         //      Set scale vector.
1814 //      sp->scale.x = width;
1815 //      sp->scale.y = height;
1816 //      sp->scale.z = length;
1817
1818         //      Add faces to all sides.
1819         for (f=0; f<MAX_SIDES_PER_SEGMENT; f++)
1820                 create_walls_on_side(sp,f);
1821
1822         sp->objects = -1;               //no objects in this segment
1823
1824         // Assume nothing special about this segment
1825         sp2->special = 0;
1826         sp2->value = 0;
1827         sp2->static_light = 0;
1828         sp2->matcen_num = -1;
1829
1830         copy_tmaps_to_segment(sp, &New_segment);
1831
1832         assign_default_uvs_to_segment(sp);
1833 }
1834
1835 // ----------------------------------------------------------------------------------------------
1836 //      Create New_segment using a specified scale factor.
1837 void med_create_new_segment(vms_vector *scale)
1838 {
1839         int                     s,t;
1840         vms_vector      v0;
1841         segment         *sp = &New_segment;
1842         segment2 *sp2;
1843
1844         fix                     length,width,height;
1845
1846         length = scale->z;
1847         width = scale->x;
1848         height = scale->y;
1849
1850         sp->segnum = 1;                                         // What to put here?  I don't know.
1851         sp2 = &Segment2s[sp->segnum];
1852
1853         //      Create relative-to-center vertices, which are the points on the box defined by length, width, height
1854         t = Num_vertices;
1855         sp->verts[0] = med_set_vertex(NEW_SEGMENT_VERTICES+0,vm_vec_make(&v0,+width/2,+height/2,-length/2));
1856         sp->verts[1] = med_set_vertex(NEW_SEGMENT_VERTICES+1,vm_vec_make(&v0,+width/2,-height/2,-length/2));
1857         sp->verts[2] = med_set_vertex(NEW_SEGMENT_VERTICES+2,vm_vec_make(&v0,-width/2,-height/2,-length/2));
1858         sp->verts[3] = med_set_vertex(NEW_SEGMENT_VERTICES+3,vm_vec_make(&v0,-width/2,+height/2,-length/2));
1859         sp->verts[4] = med_set_vertex(NEW_SEGMENT_VERTICES+4,vm_vec_make(&v0,+width/2,+height/2,+length/2));
1860         sp->verts[5] = med_set_vertex(NEW_SEGMENT_VERTICES+5,vm_vec_make(&v0,+width/2,-height/2,+length/2));
1861         sp->verts[6] = med_set_vertex(NEW_SEGMENT_VERTICES+6,vm_vec_make(&v0,-width/2,-height/2,+length/2));
1862         sp->verts[7] = med_set_vertex(NEW_SEGMENT_VERTICES+7,vm_vec_make(&v0,-width/2,+height/2,+length/2));
1863         Num_vertices = t;
1864
1865 //      sp->scale = *scale;
1866
1867         // Form connections to children, of which it has none, init faces and tmaps.
1868         for (s=0; s<MAX_SIDES_PER_SEGMENT; s++) {
1869                 sp->children[s] = -1;
1870 //              sp->sides[s].render_flag = 0;
1871                 sp->sides[s].wall_num = -1;
1872                 create_walls_on_side(sp,s);
1873                 sp->sides[s].tmap_num = s;                                      // assign some stupid old tmap to this side.
1874                 sp->sides[s].tmap_num2 = 0;
1875         }
1876
1877         Seg_orientation.p = 0;  Seg_orientation.b = 0;  Seg_orientation.h = 0;
1878
1879         sp->objects = -1;               //no objects in this segment
1880
1881         assign_default_uvs_to_segment(sp);
1882
1883         // Assume nothing special about this segment
1884         sp2->special = 0;
1885         sp2->value = 0;
1886         sp2->static_light = 0;
1887         sp2->matcen_num = -1;
1888 }
1889
1890 // -------------------------------------------------------------------------------
1891 void med_create_new_segment_from_cursegp(void)
1892 {
1893         vms_vector      scalevec;
1894         vms_vector      uvec, rvec, fvec;
1895
1896         med_extract_up_vector_from_segment_side(Cursegp, Curside, &uvec);
1897         med_extract_right_vector_from_segment_side(Cursegp, Curside, &rvec);
1898         extract_forward_vector_from_segment(Cursegp, &fvec);
1899
1900         scalevec.x = vm_vec_mag(&rvec);
1901         scalevec.y = vm_vec_mag(&uvec);
1902         scalevec.z = vm_vec_mag(&fvec);
1903
1904         med_create_new_segment(&scalevec);
1905 }
1906
1907 // -------------------------------------------------------------------------------
1908 //      Initialize all vertices to inactive status.
1909 void init_all_vertices(void)
1910 {
1911         int             v;
1912         int     s;
1913
1914         for (v=0; v<MAX_SEGMENT_VERTICES; v++)
1915                 Vertex_active[v] = 0;
1916
1917         for (s=0; s<MAX_SEGMENTS; s++)
1918                 Segments[s].segnum = -1;
1919
1920 }
1921
1922 // --------------------------------------------------------------------------------------
1923 //      Create a new mine, set global variables.
1924 int create_new_mine(void)
1925 {
1926         int     s;
1927         vms_vector      sizevec;
1928         vms_matrix      m1 = IDENTITY_MATRIX;
1929
1930         // initialize_mine_arrays();
1931
1932 //      gamestate_not_restored = 1;
1933
1934         // Clear refueling center code
1935         fuelcen_reset();
1936         hostage_init_all();
1937
1938         init_all_vertices();
1939
1940         Current_level_num = 0;          //0 means not a real level
1941         Current_level_name[0] = 0;
1942
1943         Cur_object_index = -1;
1944         reset_objects(1);               //just one object, the player
1945
1946         num_groups = 0;
1947         current_group = -1;
1948
1949         Num_vertices = 0;               // Number of vertices in global array.
1950         Num_segments = 0;               // Number of segments in global array, will get increased in med_create_segment
1951         Cursegp = Segments;     // Say current segment is the only segment.
1952         Curside = WBACK;                // The active side is the back side
1953         Markedsegp = 0;         // Say there is no marked segment.
1954         Markedside = WBACK;     //      Shouldn't matter since Markedsegp == 0, but just in case...
1955         for (s=0;s<MAX_GROUPS+1;s++) {
1956                 GroupList[s].num_segments = 0;
1957                 GroupList[s].num_vertices = 0;
1958                 Groupsegp[s] = NULL;
1959                 Groupside[s] = 0;
1960         }
1961
1962         Num_robot_centers = 0;
1963         Num_open_doors = 0;
1964         wall_init();
1965         trigger_init();
1966
1967         // Create New_segment, which is the segment we will be adding at each instance.
1968         med_create_new_segment(vm_vec_make(&sizevec,DEFAULT_X_SIZE,DEFAULT_Y_SIZE,DEFAULT_Z_SIZE));             // New_segment = Segments[0];
1969 //      med_create_segment(Segments,0,0,0,DEFAULT_X_SIZE,DEFAULT_Y_SIZE,DEFAULT_Z_SIZE,vm_mat_make(&m1,F1_0,0,0,0,F1_0,0,0,0,F1_0));
1970         med_create_segment(Segments,0,0,0,DEFAULT_X_SIZE,DEFAULT_Y_SIZE,DEFAULT_Z_SIZE,&m1);
1971
1972         N_found_segs = 0;
1973         N_selected_segs = 0;
1974         N_warning_segs = 0;
1975
1976         //--repair-- create_local_segment_data();
1977
1978         ControlCenterTriggers.num_links = 0;
1979
1980     //editor_status("New mine created.");
1981         return  0;                      // say no error
1982 }
1983
1984 // --------------------------------------------------------------------------------------------------
1985 // Copy a segment from *ssp to *dsp.  Do not simply copy the struct.  Use *dsp's vertices, copying in
1986 //      just the values, not the indices.
1987 void med_copy_segment(segment *dsp,segment *ssp)
1988 {
1989         int     v;
1990         int     verts_copy[MAX_VERTICES_PER_SEGMENT];
1991
1992         //      First make a copy of the vertex list.
1993         for (v=0; v<MAX_VERTICES_PER_SEGMENT; v++)
1994                 verts_copy[v] = dsp->verts[v];
1995
1996         // Now copy the whole struct.
1997         *dsp = *ssp;
1998
1999         // Now restore the vertex indices.
2000         for (v=0; v<MAX_VERTICES_PER_SEGMENT; v++)
2001                 dsp->verts[v] = verts_copy[v];
2002
2003         // Now destructively modify the vertex values for all vertex indices.
2004         for (v=0; v<MAX_VERTICES_PER_SEGMENT; v++)
2005                 Vertices[dsp->verts[v]] = Vertices[ssp->verts[v]];
2006 }
2007
2008 // -----------------------------------------------------------------------------
2009 //      Create coordinate axes in orientation of specified segment, stores vertices at *vp.
2010 void create_coordinate_axes_from_segment(segment *sp,short *vertnums)
2011 {
2012         vms_matrix      rotmat;
2013         vms_vector t;
2014
2015         med_extract_matrix_from_segment(sp,&rotmat);
2016
2017         compute_segment_center(&Vertices[vertnums[0]],sp);
2018
2019         t = rotmat.rvec;
2020         vm_vec_scale(&t,i2f(32));
2021         vm_vec_add(&Vertices[vertnums[1]],&Vertices[vertnums[0]],&t);
2022
2023         t = rotmat.uvec;
2024         vm_vec_scale(&t,i2f(32));
2025         vm_vec_add(&Vertices[vertnums[2]],&Vertices[vertnums[0]],&t);
2026
2027         t = rotmat.fvec;
2028         vm_vec_scale(&t,i2f(32));
2029         vm_vec_add(&Vertices[vertnums[3]],&Vertices[vertnums[0]],&t);
2030 }
2031
2032 // -----------------------------------------------------------------------------
2033 //      Determine if a segment is concave. Returns true if concave
2034 int check_seg_concavity(segment *s)
2035 {
2036         int sn,vn;
2037         vms_vector n0,n1;
2038
2039         for (sn=0;sn<MAX_SIDES_PER_SEGMENT;sn++)
2040                 for (vn=0;vn<=4;vn++) {
2041
2042                         vm_vec_normal(&n1,
2043                                 &Vertices[s->verts[Side_to_verts[sn][vn%4]]],
2044                                 &Vertices[s->verts[Side_to_verts[sn][(vn+1)%4]]],
2045                                 &Vertices[s->verts[Side_to_verts[sn][(vn+2)%4]]]);
2046
2047                         //vm_vec_normalize(&n1);
2048
2049                         if (vn>0) if (vm_vec_dotprod(&n0,&n1) < f0_5) return 1;
2050
2051                         n0 = n1;
2052                 }
2053
2054         return 0;
2055 }
2056
2057
2058 // -----------------------------------------------------------------------------
2059 //      Find all concave segments and add to list
2060 void find_concave_segs()
2061 {
2062         int i;
2063         segment *s;
2064
2065         N_warning_segs = 0;
2066
2067         for (s=Segments,i=Highest_segment_index;i>=0;s++,i--)
2068                 if (s->segnum != -1)
2069                         if (check_seg_concavity(s)) Warning_segs[N_warning_segs++]=SEG_PTR_2_NUM(s);
2070
2071
2072 }
2073
2074
2075 // -----------------------------------------------------------------------------
2076 void warn_if_concave_segments(void)
2077 {
2078         char temp[1];
2079
2080         find_concave_segs();
2081
2082         if (N_warning_segs) {
2083                 editor_status("*** WARNING *** %d concave segments in mine! *** WARNING ***",N_warning_segs);
2084                 sprintf( temp, "%d", N_warning_segs );
2085     }
2086 }
2087
2088 // -----------------------------------------------------------------------------
2089 //      Check segment s, if concave, warn
2090 void warn_if_concave_segment(segment *s)
2091 {
2092     char temp[1];
2093         int     result;
2094
2095         result = check_seg_concavity(s);
2096
2097         if (result) {
2098                 Warning_segs[N_warning_segs++] = s-Segments;
2099
2100         if (N_warning_segs) {
2101                         editor_status("*** WARNING *** New segment is concave! *** WARNING ***");
2102             sprintf( temp, "%d", N_warning_segs );
2103         }
2104         //else
2105            // editor_status("");
2106         } //else
2107         //editor_status("");
2108 }
2109
2110
2111 // -------------------------------------------------------------------------------
2112 //      Find segment adjacent to sp:side.
2113 //      Adjacent means a segment which shares all four vertices.
2114 //      Return true if segment found and fill in segment in adj_sp and side in adj_side.
2115 //      Return false if unable to find, in which case adj_sp and adj_side are undefined.
2116 int med_find_adjacent_segment_side(segment *sp, int side, segment **adj_sp, int *adj_side)
2117 {
2118         int                     seg,s,v,vv;
2119         int                     abs_verts[4];
2120
2121         //      Stuff abs_verts[4] array with absolute vertex indices
2122         for (v=0; v<4; v++)
2123                 abs_verts[v] = sp->verts[Side_to_verts[side][v]];
2124
2125         //      Scan all segments, looking for a segment which contains the four abs_verts
2126         for (seg=0; seg<=Highest_segment_index; seg++) {
2127                 if (seg != sp-Segments) {
2128                         for (v=0; v<4; v++) {                                                                                           // do for each vertex in abs_verts
2129                                 for (vv=0; vv<MAX_VERTICES_PER_SEGMENT; vv++)                   // do for each vertex in segment
2130                                         if (abs_verts[v] == Segments[seg].verts[vv])
2131                                                 goto fass_found1;                                                                                       // Current vertex (indexed by v) is present in segment, try next
2132                                 goto fass_next_seg;                                                                                             // This segment doesn't contain the vertex indexed by v
2133                         fass_found1: ;
2134                         }               // end for v
2135
2136                         //      All four vertices in sp:side are present in segment seg.
2137                         //      Determine side and return
2138                         for (s=0; s<MAX_SIDES_PER_SEGMENT; s++) {
2139                                 for (v=0; v<4; v++) {
2140                                         for (vv=0; vv<4; vv++) {
2141                                                 if (Segments[seg].verts[Side_to_verts[s][v]] == abs_verts[vv])
2142                                                         goto fass_found2;
2143                                         }
2144                                         goto fass_next_side;                                                                                    // Couldn't find vertex v in current side, so try next side.
2145                                 fass_found2: ;
2146                                 }
2147                                 // Found all four vertices in current side.  We are done!
2148                                 *adj_sp = &Segments[seg];
2149                                 *adj_side = s;
2150                                 return 1;
2151                         fass_next_side: ;
2152                         }
2153                         Assert(0);      // Impossible -- we identified this segment as containing all 4 vertices of side "side", but we couldn't find them.
2154                         return 0;
2155                 fass_next_seg: ;
2156                 }
2157         }
2158
2159         return 0;
2160 }
2161
2162
2163 #define JOINT_THRESHOLD 10000*F1_0              // (Huge threshold)
2164
2165 // -------------------------------------------------------------------------------
2166 //      Find segment closest to sp:side.
2167 //      Return true if segment found and fill in segment in adj_sp and side in adj_side.
2168 //      Return false if unable to find, in which case adj_sp and adj_side are undefined.
2169 int med_find_closest_threshold_segment_side(segment *sp, int side, segment **adj_sp, int *adj_side, fix threshold)
2170 {
2171         int                     seg,s;
2172         vms_vector  vsc, vtc;           // original segment center, test segment center
2173         fix                     current_dist, closest_seg_dist;
2174
2175         if (IS_CHILD(sp->children[side]))
2176                 return 0;
2177
2178         compute_center_point_on_side(&vsc, sp, side);
2179
2180         closest_seg_dist = JOINT_THRESHOLD;
2181
2182         //      Scan all segments, looking for a segment which contains the four abs_verts
2183         for (seg=0; seg<=Highest_segment_index; seg++)
2184                 if (seg != sp-Segments)
2185                         for (s=0;s<MAX_SIDES_PER_SEGMENT;s++) {
2186                                 if (!IS_CHILD(Segments[seg].children[s])) {
2187                                         compute_center_point_on_side(&vtc, &Segments[seg], s);
2188                                         current_dist = vm_vec_dist( &vsc, &vtc );
2189                                         if (current_dist < closest_seg_dist) {
2190                                                 *adj_sp = &Segments[seg];
2191                                                 *adj_side = s;
2192                                                 closest_seg_dist = current_dist;
2193                                         }
2194                                 }
2195                         }
2196
2197         if (closest_seg_dist < threshold)
2198                 return 1;
2199         else
2200                 return 0;
2201 }
2202
2203
2204
2205 void med_check_all_vertices()
2206 {
2207         int             s,v;
2208         segment *sp;
2209         int             count;
2210
2211         count = 0;
2212
2213         for (s=0; s<Num_segments; s++) {
2214                 sp = &Segments[s];
2215                 if (sp->segnum != -1)
2216                         for (v=0; v<MAX_VERTICES_PER_SEGMENT; v++)
2217                                 Assert(sp->verts[v] <= Highest_vertex_index);
2218
2219         }
2220
2221 }
2222
2223 //      -----------------------------------------------------------------------------------------------------
2224 void check_for_overlapping_segment(int segnum)
2225 {
2226         int     i, v;
2227         segmasks        masks;
2228         vms_vector      segcenter;
2229
2230         compute_segment_center(&segcenter, &Segments[segnum]);
2231
2232         for (i=0;i<=Highest_segment_index; i++) {
2233                 if (i != segnum) {
2234                         masks = get_seg_masks(&segcenter, i, 0);
2235                         if (masks.centermask == 0) {
2236                                 mprintf((0, "Segment %i center is contained in segment %i\n", segnum, i));
2237                                 continue;
2238                         }
2239
2240                         for (v=0; v<8; v++) {
2241                                 vms_vector      pdel, presult;
2242
2243                                 vm_vec_sub(&pdel, &Vertices[Segments[segnum].verts[v]], &segcenter);
2244                                 vm_vec_scale_add(&presult, &segcenter, &pdel, (F1_0*15)/16);
2245                                 masks = get_seg_masks(&presult, i, 0);
2246                                 if (masks.centermask == 0) {
2247                                         mprintf((0, "Segment %i near vertex %i is contained in segment %i\n", segnum, v, i));
2248                                         break;
2249                                 }
2250                         }
2251                 }
2252         }
2253
2254 }
2255
2256 //      -----------------------------------------------------------------------------------------------------
2257 //      Check for overlapping segments.
2258 void check_for_overlapping_segments(void)
2259 {
2260         int     i;
2261
2262         med_compress_mine();
2263
2264         for (i=0; i<=Highest_segment_index; i++) {
2265                 mprintf((0, "+"));
2266                 check_for_overlapping_segment(i);
2267         }
2268
2269         mprintf((0, "\nDone!\n"));
2270 }
2271