/* THE COMPUTER CODE CONTAINED HEREIN IS THE SOLE PROPERTY OF PARALLAX SOFTWARE CORPORATION ("PARALLAX"). PARALLAX, IN DISTRIBUTING THE CODE TO END-USERS, AND SUBJECT TO ALL OF THE TERMS AND CONDITIONS HEREIN, GRANTS A ROYALTY-FREE, PERPETUAL LICENSE TO SUCH END-USERS FOR USE BY SUCH END-USERS IN USING, DISPLAYING, AND CREATING DERIVATIVE WORKS THEREOF, SO LONG AS SUCH USE, DISPLAY OR CREATION IS FOR NON-COMMERCIAL, ROYALTY OR REVENUE FREE PURPOSES. IN NO EVENT SHALL THE END-USER USE THE COMPUTER CODE CONTAINED HEREIN FOR REVENUE-BEARING PURPOSES. THE END-USER UNDERSTANDS AND AGREES TO THE TERMS HEREIN AND ACCEPTS THE SAME BY USE OF THIS FILE. COPYRIGHT 1993-1998 PARALLAX SOFTWARE CORPORATION. ALL RIGHTS RESERVED. */ /* * $Source: f:/miner/source/main/rcs/gameseg.c $ * $Revision: 2.2 $ * $Author: john $ * $Date: 1995/03/20 18:15:39 $ * * Functions moved from segment.c to make editor separable from game. * * $Log: gameseg.c $ * Revision 2.2 1995/03/20 18:15:39 john * Added code to not store the normals in the segment structure. * * Revision 2.1 1995/03/08 12:11:39 allender * fix shortpos reading/writing * * Revision 2.0 1995/02/27 11:29:21 john * New version 2.0, which has no anonymous unions, builds with * Watcom 10.0, and doesn't require parsing BITMAPS.TBL. * * Revision 1.78 1995/02/22 13:52:22 allender * remove anonymous unions from object structure * * Revision 1.77 1995/02/22 13:24:47 john * Removed the vecmat anonymous unions. * * Revision 1.76 1995/02/13 20:35:01 john * Lintized * * Revision 1.75 1995/02/09 13:10:51 mike * remove an annoying mprintf. * * Revision 1.74 1995/02/05 17:49:28 rob * Added assert to gameseg.c. * * Revision 1.73 1995/02/02 00:49:26 mike * new automap segment-depth functionality. * * Revision 1.72 1995/01/16 21:06:51 mike * Move function pick_random_point_in_segment from fireball.c to gameseg.c. * * Revision 1.71 1994/12/21 19:54:32 matt * Added error checking * * Revision 1.70 1994/12/11 21:34:09 matt * Changed assert() to int3() * * Revision 1.69 1994/12/01 21:04:37 matt * Several important changes: * (1) Checking against triangulated sides has been standardized a bit * (2) Code has been added to de-triangulate some sides * (3) BIG ONE: the tolerance for checking a point against a plane has * been drastically relaxed * * * Revision 1.67 1994/11/27 23:12:21 matt * Made changes for new mprintf calling convention * * Revision 1.66 1994/11/26 22:51:40 matt * Removed editor-only fields from segment structure when editor is compiled * out, and padded segment structure to even multiple of 4 bytes. * * Revision 1.65 1994/11/22 16:55:38 mike * use memset in place of loop to clear array. * * Revision 1.64 1994/11/19 15:20:37 mike * rip out unused code and data * * Revision 1.63 1994/11/18 18:31:48 matt * Fixed code again (and maybe for real) * * Revision 1.62 1994/11/18 16:54:24 matt * Fixed extract_orient_from_segment() * * Revision 1.61 1994/11/17 14:56:50 mike * moved segment validation functions from editor to main. * * Revision 1.60 1994/11/16 23:38:53 mike * new improved boss teleportation behavior. * * Revision 1.59 1994/10/30 14:12:46 mike * rip out local segments stuff. * * Revision 1.58 1994/10/27 10:53:39 matt * Made connectivity error checking put up warning if errors found * * Revision 1.57 1994/10/25 21:19:26 mike * debugging code. * * Revision 1.56 1994/10/25 11:26:09 mike * *** empty log message *** * * Revision 1.55 1994/10/22 22:36:08 matt * Improved error finding routine * * Revision 1.54 1994/10/22 18:56:51 matt * Fixed obscure bug in segment trace code * Added error find routine, check_segment_connections() * * Revision 1.53 1994/10/17 14:05:19 matt * Don't give recursion assert if doing lighting * * Revision 1.52 1994/10/15 19:03:48 mike * Don't do exhaustive search in smooth lighting. * * Revision 1.51 1994/10/12 09:46:44 mike * Add debug code for trapping exhaustive searches. * * Revision 1.50 1994/10/11 20:50:41 matt * Made find_point_seg() take -1 as segnum, meaning to search all segments * * Revision 1.49 1994/10/11 17:40:31 matt * Fixed bug that caused segment trace to only go through sides you can fly through * * Revision 1.48 1994/10/10 14:48:16 matt * Fixed mistake that caused odd pauses and occasional int3's * * Revision 1.47 1994/10/09 23:50:41 matt * Made find_hitpoint_uv() work with triangulated sides * * Revision 1.46 1994/10/08 23:06:52 matt * trace_segs() didn't know about external walls * * Revision 1.45 1994/10/07 22:18:57 mike * Put in asserts to trap bad segnums. * * Revision 1.44 1994/10/06 14:08:07 matt * Added new function, extract_orient_from_segment() * * Revision 1.43 1994/10/04 16:24:11 mike * Set global Connected_segment_distance for debug reasons for aipath.c. * * Revision 1.42 1994/10/04 09:18:42 mike * Comment out a variable definition, preventing a warning message. * * Revision 1.41 1994/10/03 23:43:42 mike * Put in a warning for overrunning point_segs buffer. * * Revision 1.40 1994/10/03 20:55:43 rob * Added velocity to shortpos. * * Revision 1.39 1994/09/27 11:46:06 rob * re-fixed that same bug (ugh). * * Revision 1.38 1994/09/27 10:10:51 rob * Fixed bug in extract_shortpos (obj_relink added). * * Revision 1.37 1994/09/25 23:41:02 matt * Changed the object load & save code to read/write the structure fields one * at a time (rather than the whole structure at once). This mean that the * object structure can be changed without breaking the load/save functions. * As a result of this change, the local_object data can be and has been * incorporated into the object array. Also, timeleft is now a property * of all objects, and the object structure has been otherwise cleaned up. * * Revision 1.36 1994/09/22 19:03:05 mike * Add shortpos manipulation functions create_shortpos and extract_shortpos. * * Revision 1.35 1994/09/19 21:21:16 mike * Minor optimization to find_connected_distance. * * Revision 1.34 1994/09/19 21:05:25 mike * Write function find_connected_distance, * returns distance between two points as travellable through the mine. * * Revision 1.33 1994/08/30 15:07:15 matt * Changed find_point_seg() to deal with some infinite recursion problems. * * Revision 1.32 1994/08/11 18:58:32 mike * Use ints in place of shorts for optimization. * * Revision 1.31 1994/08/04 00:20:09 matt * Cleaned up fvi & physics error handling; put in code to make sure objects * are in correct segment; simplified segment finding for objects and points * * Revision 1.30 1994/08/03 16:46:12 mike * not much... * * Revision 1.29 1994/08/02 20:41:31 matt * Fixed bug in get_side_verts() * * Revision 1.28 1994/08/02 19:04:25 matt * Cleaned up vertex list functions * * Revision 1.27 1994/08/01 10:39:44 matt * find_new_seg() now will look through any kind of wall but a totally solid one * * Revision 1.26 1994/07/28 19:15:59 matt * Fixed yet another bug in get_seg_masks() * */ #include #include #include //for stackavail() #include // for memset() #include "inferno.h" #include "game.h" #include "error.h" #include "mono.h" #include "vecmat.h" #include "gameseg.h" #include "wall.h" #include "fuelcen.h" #pragma off (unreferenced) static char rcsid[] = "$Id: gameseg.c 2.2 1995/03/20 18:15:39 john Exp $"; #pragma on (unreferenced) // How far a point can be from a plane, and still be "in" the plane #define PLANE_DIST_TOLERANCE 250 // ------------------------------------------------------------------------------------------ // Compute the center point of a side of a segment. // The center point is defined to be the average of the 4 points defining the side. void compute_center_point_on_side(vms_vector *vp,segment *sp,int side) { int v; vm_vec_zero(vp); for (v=0; v<4; v++) vm_vec_add2(vp,&Vertices[sp->verts[Side_to_verts[side][v]]]); vm_vec_scale(vp,F1_0/4); } // ------------------------------------------------------------------------------------------ // Compute segment center. // The center point is defined to be the average of the 8 points defining the segment. void compute_segment_center(vms_vector *vp,segment *sp) { int v; vm_vec_zero(vp); for (v=0; v<8; v++) vm_vec_add2(vp,&Vertices[sp->verts[v]]); vm_vec_scale(vp,F1_0/8); } // ----------------------------------------------------------------------------- // Given two segments, return the side index in the connecting segment which connects to the base segment // Optimized by MK on 4/21/94 because it is a 2% load. int find_connect_side(segment *base_seg, segment *con_seg) { int s; short base_seg_num = base_seg - Segments; short *childs = con_seg->children; for (s=0; stype) { case SIDE_IS_QUAD: return 1; break; case SIDE_IS_TRI_02: case SIDE_IS_TRI_13: return 2; break; default: Error("Illegal type = %i\n", sidep->type); break; } } // Fill in array with four absolute point numbers for a given side get_side_verts(short *vertlist,int segnum,int sidenum) { int i; byte *sv = Side_to_verts[sidenum]; short *vp = Segments[segnum].verts; for (i=4; i--;) vertlist[i] = vp[sv[i]]; } #ifdef EDITOR // ----------------------------------------------------------------------------------- // Create all vertex lists (1 or 2) for faces on a side. // Sets: // num_faces number of lists // vertices vertices in all (1 or 2) faces // If there is one face, it has 4 vertices. // If there are two faces, they both have three vertices, so face #0 is stored in vertices 0,1,2, // face #1 is stored in vertices 3,4,5. // Note: these are not absolute vertex numbers, but are relative to the segment // Note: for triagulated sides, the middle vertex of each trianle is the one NOT // adjacent on the diagonal edge void create_all_vertex_lists(int *num_faces, int *vertices, int segnum, int sidenum) { side *sidep = &Segments[segnum].sides[sidenum]; int *sv = Side_to_verts_int[sidenum]; Assert((segnum <= Highest_segment_index) && (segnum >= 0)); Assert((sidenum >= 0) && (sidenum < 6)); switch (sidep->type) { case SIDE_IS_QUAD: vertices[0] = sv[0]; vertices[1] = sv[1]; vertices[2] = sv[2]; vertices[3] = sv[3]; *num_faces = 1; break; case SIDE_IS_TRI_02: *num_faces = 2; vertices[0] = sv[0]; vertices[1] = sv[1]; vertices[2] = sv[2]; vertices[3] = sv[2]; vertices[4] = sv[3]; vertices[5] = sv[0]; //IMPORTANT: DON'T CHANGE THIS CODE WITHOUT CHANGING GET_SEG_MASKS() //CREATE_ABS_VERTEX_LISTS(), CREATE_ALL_VERTEX_LISTS(), CREATE_ALL_VERTNUM_LISTS() break; case SIDE_IS_TRI_13: *num_faces = 2; vertices[0] = sv[3]; vertices[1] = sv[0]; vertices[2] = sv[1]; vertices[3] = sv[1]; vertices[4] = sv[2]; vertices[5] = sv[3]; //IMPORTANT: DON'T CHANGE THIS CODE WITHOUT CHANGING GET_SEG_MASKS() //CREATE_ABS_VERTEX_LISTS(), CREATE_ALL_VERTEX_LISTS(), CREATE_ALL_VERTNUM_LISTS() break; default: Error("Illegal side type, type = %i, segment # = %i, side # = %i\n", sidep->type, segnum, sidenum); break; } } #endif // ----------------------------------------------------------------------------------- // Like create all vertex lists, but returns the vertnums (relative to // the side) for each of the faces that make up the side. // If there is one face, it has 4 vertices. // If there are two faces, they both have three vertices, so face #0 is stored in vertices 0,1,2, // face #1 is stored in vertices 3,4,5. void create_all_vertnum_lists(int *num_faces, int *vertnums, int segnum, int sidenum) { side *sidep = &Segments[segnum].sides[sidenum]; Assert((segnum <= Highest_segment_index) && (segnum >= 0)); switch (sidep->type) { case SIDE_IS_QUAD: vertnums[0] = 0; vertnums[1] = 1; vertnums[2] = 2; vertnums[3] = 3; *num_faces = 1; break; case SIDE_IS_TRI_02: *num_faces = 2; vertnums[0] = 0; vertnums[1] = 1; vertnums[2] = 2; vertnums[3] = 2; vertnums[4] = 3; vertnums[5] = 0; //IMPORTANT: DON'T CHANGE THIS CODE WITHOUT CHANGING GET_SEG_MASKS() //CREATE_ABS_VERTEX_LISTS(), CREATE_ALL_VERTEX_LISTS(), CREATE_ALL_VERTNUM_LISTS() break; case SIDE_IS_TRI_13: *num_faces = 2; vertnums[0] = 3; vertnums[1] = 0; vertnums[2] = 1; vertnums[3] = 1; vertnums[4] = 2; vertnums[5] = 3; //IMPORTANT: DON'T CHANGE THIS CODE WITHOUT CHANGING GET_SEG_MASKS() //CREATE_ABS_VERTEX_LISTS(), CREATE_ALL_VERTEX_LISTS(), CREATE_ALL_VERTNUM_LISTS() break; default: Error("Illegal side type, type = %i, segment # = %i, side # = %i\n", sidep->type, segnum, sidenum); break; } } // ----- //like create_all_vertex_lists(), but generate absolute point numbers void create_abs_vertex_lists(int *num_faces, int *vertices, int segnum, int sidenum) { short *vp = Segments[segnum].verts; side *sidep = &Segments[segnum].sides[sidenum]; int *sv = Side_to_verts_int[sidenum]; Assert((segnum <= Highest_segment_index) && (segnum >= 0)); switch (sidep->type) { case SIDE_IS_QUAD: vertices[0] = vp[sv[0]]; vertices[1] = vp[sv[1]]; vertices[2] = vp[sv[2]]; vertices[3] = vp[sv[3]]; *num_faces = 1; break; case SIDE_IS_TRI_02: *num_faces = 2; vertices[0] = vp[sv[0]]; vertices[1] = vp[sv[1]]; vertices[2] = vp[sv[2]]; vertices[3] = vp[sv[2]]; vertices[4] = vp[sv[3]]; vertices[5] = vp[sv[0]]; //IMPORTANT: DON'T CHANGE THIS CODE WITHOUT CHANGING GET_SEG_MASKS(), //CREATE_ABS_VERTEX_LISTS(), CREATE_ALL_VERTEX_LISTS(), CREATE_ALL_VERTNUM_LISTS() break; case SIDE_IS_TRI_13: *num_faces = 2; vertices[0] = vp[sv[3]]; vertices[1] = vp[sv[0]]; vertices[2] = vp[sv[1]]; vertices[3] = vp[sv[1]]; vertices[4] = vp[sv[2]]; vertices[5] = vp[sv[3]]; //IMPORTANT: DON'T CHANGE THIS CODE WITHOUT CHANGING GET_SEG_MASKS() //CREATE_ABS_VERTEX_LISTS(), CREATE_ALL_VERTEX_LISTS(), CREATE_ALL_VERTNUM_LISTS() break; default: Error("Illegal side type, type = %i, segment # = %i, side # = %i\n", sidep->type, segnum, sidenum); break; } } //returns 3 different bitmasks with info telling if this sphere is in //this segment. See segmasks structure for info on fields segmasks get_seg_masks(vms_vector *checkp,int segnum,fix rad) { int sn,facebit,sidebit; segmasks masks; int num_faces; int vertex_list[6]; segment *seg; Assert((segnum <= Highest_segment_index) && (segnum >= 0)); seg = &Segments[segnum]; //check point against each side of segment. return bitmask masks.sidemask = masks.facemask = masks.centermask = 0; for (sn=0,facebit=sidebit=1;sn<6;sn++,sidebit<<=1) { #ifndef COMPACT_SEGS side *s = &seg->sides[sn]; #endif int side_pokes_out; int vertnum,fn; // Get number of faces on this side, and at vertex_list, store vertices. // If one face, then vertex_list indicates a quadrilateral. // If two faces, then 0,1,2 define one triangle, 3,4,5 define the second. create_abs_vertex_lists( &num_faces, vertex_list, segnum, sn); //ok...this is important. If a side has 2 faces, we need to know if //those faces form a concave or convex side. If the side pokes out, //then a point is on the back of the side if it is behind BOTH faces, //but if the side pokes in, a point is on the back if behind EITHER face. if (num_faces==2) { fix dist; int side_count,center_count; #ifdef COMPACT_SEGS vms_vector normals[2]; #endif vertnum = min(vertex_list[0],vertex_list[2]); #ifdef COMPACT_SEGS get_side_normals(seg, sn, &normals[0], &normals[1] ); #endif if (vertex_list[4] < vertex_list[1]) #ifdef COMPACT_SEGS dist = vm_dist_to_plane(&Vertices[vertex_list[4]],&normals[0],&Vertices[vertnum]); #else dist = vm_dist_to_plane(&Vertices[vertex_list[4]],&s->normals[0],&Vertices[vertnum]); #endif else #ifdef COMPACT_SEGS dist = vm_dist_to_plane(&Vertices[vertex_list[1]],&normals[1],&Vertices[vertnum]); #else dist = vm_dist_to_plane(&Vertices[vertex_list[1]],&s->normals[1],&Vertices[vertnum]); #endif side_pokes_out = (dist > PLANE_DIST_TOLERANCE); side_count = center_count = 0; for (fn=0;fn<2;fn++,facebit<<=1) { #ifdef COMPACT_SEGS dist = vm_dist_to_plane(checkp, &normals[fn], &Vertices[vertnum]); #else dist = vm_dist_to_plane(checkp, &s->normals[fn], &Vertices[vertnum]); #endif if (dist < -PLANE_DIST_TOLERANCE) //in front of face center_count++; if (dist-rad < -PLANE_DIST_TOLERANCE) { masks.facemask |= facebit; side_count++; } } if (!side_pokes_out) { //must be behind both faces if (side_count==2) masks.sidemask |= sidebit; if (center_count==2) masks.centermask |= sidebit; } else { //must be behind at least one face if (side_count) masks.sidemask |= sidebit; if (center_count) masks.centermask |= sidebit; } } else { //only one face on this side fix dist; int i; #ifdef COMPACT_SEGS vms_vector normal; #endif //use lowest point number vertnum = vertex_list[0]; for (i=1;i<4;i++) if (vertex_list[i] < vertnum) vertnum = vertex_list[i]; #ifdef COMPACT_SEGS get_side_normal(seg, sn, 0, &normal ); dist = vm_dist_to_plane(checkp, &normal, &Vertices[vertnum]); #else dist = vm_dist_to_plane(checkp, &s->normals[0], &Vertices[vertnum]); #endif if (dist < -PLANE_DIST_TOLERANCE) masks.centermask |= sidebit; if (dist-rad < -PLANE_DIST_TOLERANCE) { masks.facemask |= facebit; masks.sidemask |= sidebit; } facebit <<= 2; } } return masks; } //this was converted from get_seg_masks()...it fills in an array of 6 //elements for the distace behind each side, or zero if not behind //only gets centermask, and assumes zero rad ubyte get_side_dists(vms_vector *checkp,int segnum,fix *side_dists) { int sn,facebit,sidebit; ubyte mask; int num_faces; int vertex_list[6]; segment *seg; Assert((segnum <= Highest_segment_index) && (segnum >= 0)); seg = &Segments[segnum]; //check point against each side of segment. return bitmask mask = 0; for (sn=0,facebit=sidebit=1;sn<6;sn++,sidebit<<=1) { #ifndef COMPACT_SEGS side *s = &seg->sides[sn]; #endif int side_pokes_out; int fn; side_dists[sn] = 0; // Get number of faces on this side, and at vertex_list, store vertices. // If one face, then vertex_list indicates a quadrilateral. // If two faces, then 0,1,2 define one triangle, 3,4,5 define the second. create_abs_vertex_lists( &num_faces, vertex_list, segnum, sn); //ok...this is important. If a side has 2 faces, we need to know if //those faces form a concave or convex side. If the side pokes out, //then a point is on the back of the side if it is behind BOTH faces, //but if the side pokes in, a point is on the back if behind EITHER face. if (num_faces==2) { fix dist; int center_count; int vertnum; #ifdef COMPACT_SEGS vms_vector normals[2]; #endif vertnum = min(vertex_list[0],vertex_list[2]); #ifdef COMPACT_SEGS get_side_normals(seg, sn, &normals[0], &normals[1] ); #endif if (vertex_list[4] < vertex_list[1]) #ifdef COMPACT_SEGS dist = vm_dist_to_plane(&Vertices[vertex_list[4]],&normals[0],&Vertices[vertnum]); #else dist = vm_dist_to_plane(&Vertices[vertex_list[4]],&s->normals[0],&Vertices[vertnum]); #endif else #ifdef COMPACT_SEGS dist = vm_dist_to_plane(&Vertices[vertex_list[1]],&normals[1],&Vertices[vertnum]); #else dist = vm_dist_to_plane(&Vertices[vertex_list[1]],&s->normals[1],&Vertices[vertnum]); #endif side_pokes_out = (dist > PLANE_DIST_TOLERANCE); center_count = 0; for (fn=0;fn<2;fn++,facebit<<=1) { #ifdef COMPACT_SEGS dist = vm_dist_to_plane(checkp, &normals[fn], &Vertices[vertnum]); #else dist = vm_dist_to_plane(checkp, &s->normals[fn], &Vertices[vertnum]); #endif if (dist < -PLANE_DIST_TOLERANCE) { //in front of face center_count++; side_dists[sn] += dist; } } if (!side_pokes_out) { //must be behind both faces if (center_count==2) { mask |= sidebit; side_dists[sn] /= 2; //get average } } else { //must be behind at least one face if (center_count) { mask |= sidebit; if (center_count==2) side_dists[sn] /= 2; //get average } } } else { //only one face on this side fix dist; int i,vertnum; #ifdef COMPACT_SEGS vms_vector normal; #endif //use lowest point number vertnum = vertex_list[0]; for (i=1;i<4;i++) if (vertex_list[i] < vertnum) vertnum = vertex_list[i]; #ifdef COMPACT_SEGS get_side_normal(seg, sn, 0, &normal ); dist = vm_dist_to_plane(checkp, &normal, &Vertices[vertnum]); #else dist = vm_dist_to_plane(checkp, &s->normals[0], &Vertices[vertnum]); #endif if (dist < -PLANE_DIST_TOLERANCE) { mask |= sidebit; side_dists[sn] = dist; } facebit <<= 2; } } return mask; } #ifndef NDEBUG #ifndef COMPACT_SEGS //returns true if errors detected int check_norms(int segnum,int sidenum,int facenum,int csegnum,int csidenum,int cfacenum) { vms_vector *n0,*n1; n0 = &Segments[segnum].sides[sidenum].normals[facenum]; n1 = &Segments[csegnum].sides[csidenum].normals[cfacenum]; if (n0->x != -n1->x || n0->y != -n1->y || n0->z != -n1->z) { mprintf((0,"Seg %x, side %d, norm %d doesn't match seg %x, side %d, norm %d:\n" " %8x %8x %8x\n" " %8x %8x %8x (negated)\n", segnum,sidenum,facenum,csegnum,csidenum,cfacenum, n0->x,n0->y,n0->z,-n1->x,-n1->y,-n1->z)); return 1; } else return 0; } //heavy-duty error checking int check_segment_connections(void) { int segnum,sidenum; int errors=0; for (segnum=0;segnum<=Highest_segment_index;segnum++) { segment *seg; seg = &Segments[segnum]; for (sidenum=0;sidenum<6;sidenum++) { side *s; segment *cseg; side *cs; int num_faces,csegnum,csidenum,con_num_faces; int vertex_list[6],con_vertex_list[6]; s = &seg->sides[sidenum]; create_abs_vertex_lists( &num_faces, vertex_list, segnum, sidenum); csegnum = seg->children[sidenum]; if (csegnum >= 0) { cseg = &Segments[csegnum]; csidenum = find_connect_side(seg,cseg); if (csidenum == -1) { mprintf((0,"Could not find connected side for seg %x back to seg %x, side %d\n",csegnum,segnum,sidenum)); errors = 1; continue; } cs = &cseg->sides[csidenum]; create_abs_vertex_lists( &con_num_faces, con_vertex_list, csegnum, csidenum); if (con_num_faces != num_faces) { mprintf((0,"Seg %x, side %d: num_faces (%d) mismatch with seg %x, side %d (%d)\n",segnum,sidenum,num_faces,csegnum,csidenum,con_num_faces)); errors = 1; } else if (num_faces == 1) { int t; for (t=0;t<4 && con_vertex_list[t]!=vertex_list[0];t++); if (t==4 || vertex_list[0] != con_vertex_list[t] || vertex_list[1] != con_vertex_list[(t+3)%4] || vertex_list[2] != con_vertex_list[(t+2)%4] || vertex_list[3] != con_vertex_list[(t+1)%4]) { mprintf((0,"Seg %x, side %d: vertex list mismatch with seg %x, side %d\n" " %x %x %x %x\n" " %x %x %x %x\n", segnum,sidenum,csegnum,csidenum, vertex_list[0],vertex_list[1],vertex_list[2],vertex_list[3], con_vertex_list[0],con_vertex_list[1],con_vertex_list[2],con_vertex_list[3])); errors = 1; } else errors |= check_norms(segnum,sidenum,0,csegnum,csidenum,0); } else { if (vertex_list[1] == con_vertex_list[1]) { if (vertex_list[4] != con_vertex_list[4] || vertex_list[0] != con_vertex_list[2] || vertex_list[2] != con_vertex_list[0] || vertex_list[3] != con_vertex_list[5] || vertex_list[5] != con_vertex_list[3]) { mprintf((0,"Seg %x, side %d: vertex list mismatch with seg %x, side %d\n" " %x %x %x %x %x %x\n" " %x %x %x %x %x %x\n", segnum,sidenum,csegnum,csidenum, vertex_list[0],vertex_list[1],vertex_list[2],vertex_list[3],vertex_list[4],vertex_list[5], con_vertex_list[0],con_vertex_list[1],con_vertex_list[2],con_vertex_list[3],con_vertex_list[4],con_vertex_list[5])); mprintf((0,"Changing seg:side %4i:%i from %i to %i\n", csegnum, csidenum, Segments[csegnum].sides[csidenum].type, 5-Segments[csegnum].sides[csidenum].type)); Segments[csegnum].sides[csidenum].type = 5-Segments[csegnum].sides[csidenum].type; } else { errors |= check_norms(segnum,sidenum,0,csegnum,csidenum,0); errors |= check_norms(segnum,sidenum,1,csegnum,csidenum,1); } } else { if (vertex_list[1] != con_vertex_list[4] || vertex_list[4] != con_vertex_list[1] || vertex_list[0] != con_vertex_list[5] || vertex_list[5] != con_vertex_list[0] || vertex_list[2] != con_vertex_list[3] || vertex_list[3] != con_vertex_list[2]) { mprintf((0,"Seg %x, side %d: vertex list mismatch with seg %x, side %d\n" " %x %x %x %x %x %x\n" " %x %x %x %x %x %x\n", segnum,sidenum,csegnum,csidenum, vertex_list[0],vertex_list[1],vertex_list[2],vertex_list[3],vertex_list[4],vertex_list[5], con_vertex_list[0],con_vertex_list[1],con_vertex_list[2],con_vertex_list[3],con_vertex_list[4],vertex_list[5])); mprintf((0,"Changing seg:side %4i:%i from %i to %i\n", csegnum, csidenum, Segments[csegnum].sides[csidenum].type, 5-Segments[csegnum].sides[csidenum].type)); Segments[csegnum].sides[csidenum].type = 5-Segments[csegnum].sides[csidenum].type; } else { errors |= check_norms(segnum,sidenum,0,csegnum,csidenum,1); errors |= check_norms(segnum,sidenum,1,csegnum,csidenum,0); } } } } } } // mprintf((0,"\n DONE \n")); return errors; } #endif #endif #ifdef EDITOR int Doing_lighting_hack_flag=0; #else #define Doing_lighting_hack_flag 0 #endif //figure out what seg the given point is in, tracing through segments //returns segment number, or -1 if can't find segment int trace_segs(vms_vector *p0,int oldsegnum) { int centermask; segment *seg; fix side_dists[6]; Assert((oldsegnum <= Highest_segment_index) && (oldsegnum >= 0)); if (stackavail() < 1024) { //if no debugging, we'll get past assert #ifndef NDEBUG if (!Doing_lighting_hack_flag) Int3(); // Please get Matt, or if you cannot, then type // "?p0->xyz,segnum" at the DBG prompt, write down // the values (a 3-element vector and a segment number), // and make a copy of the mine you are playing. #endif return oldsegnum; //just say we're in this segment and be done with it } centermask = get_side_dists(p0,oldsegnum,side_dists); //check old segment if (centermask == 0) //we're in the old segment return oldsegnum; //..say so else { //not in old seg. trace through to find seg int biggest_side; do { int sidenum,bit; fix biggest_val; seg = &Segments[oldsegnum]; biggest_side = -1; biggest_val = 0; for (sidenum=0,bit=1;sidenum<6;sidenum++,bit<<=1) if ((centermask&bit) && (seg->children[sidenum]>-1)) if (side_dists[sidenum] < biggest_val) { biggest_val = side_dists[sidenum]; biggest_side = sidenum; } if (biggest_side != -1) { int check; side_dists[biggest_side] = 0; check = trace_segs(p0,seg->children[biggest_side]); //trace into adjacent segment if (check != -1) //we've found a segment return check; } } while (biggest_side!=-1); return -1; //we haven't found a segment } } int Exhaustive_count=0, Exhaustive_failed_count=0; //Tries to find a segment for a point, in the following way: // 1. Check the given segment // 2. Recursively trace through attached segments // 3. Check all the segmentns //Returns segnum if found, or -1 int find_point_seg(vms_vector *p,int segnum) { int newseg; //allow segnum==-1, meaning we have no idea what segment point is in Assert((segnum <= Highest_segment_index) && (segnum >= -1)); if (segnum != -1) { newseg = trace_segs(p,segnum); if (newseg != -1) //we found a segment! return newseg; } //couldn't find via attached segs, so search all segs // MK: 10/15/94 // This Doing_lighting_hack_flag thing added by mk because the hundreds of scrolling messages were // slowing down lighting, and in about 98% of cases, it would just return -1 anyway. // Matt: This really should be fixed, though. We're probably screwing up our lighting in a few places. if (!Doing_lighting_hack_flag) { mprintf((1,"Warning: doing exhaustive search to find point segment (%i times)\n", ++Exhaustive_count)); for (newseg=0;newseg <= Highest_segment_index;newseg++) if (get_seg_masks(p,newseg,0).centermask == 0) return newseg; mprintf((1,"Warning: could not find point segment (%i times)\n", ++Exhaustive_failed_count)); return -1; //no segment found } else return -1; } //--repair-- // ------------------------------------------------------------------------------ //--repair-- void clsd_repair_center(int segnum) //--repair-- { //--repair-- int sidenum; //--repair-- //--repair-- // --- Set repair center bit for all repair center segments. //--repair-- if (Segments[segnum].special == SEGMENT_IS_REPAIRCEN) { //--repair-- Lsegments[segnum].special_type |= SS_REPAIR_CENTER; //--repair-- Lsegments[segnum].special_segment = segnum; //--repair-- } //--repair-- //--repair-- // --- Set repair center bit for all segments adjacent to a repair center. //--repair-- for (sidenum=0; sidenum < MAX_SIDES_PER_SEGMENT; sidenum++) { //--repair-- int s = Segments[segnum].children[sidenum]; //--repair-- //--repair-- if ( (s != -1) && (Segments[s].special==SEGMENT_IS_REPAIRCEN) ) { //--repair-- Lsegments[segnum].special_type |= SS_REPAIR_CENTER; //--repair-- Lsegments[segnum].special_segment = s; //--repair-- } //--repair-- } //--repair-- } //--repair-- // ------------------------------------------------------------------------------ //--repair-- // --- Set destination points for all Materialization centers. //--repair-- void clsd_materialization_center(int segnum) //--repair-- { //--repair-- if (Segments[segnum].special == SEGMENT_IS_ROBOTMAKER) { //--repair-- //--repair-- } //--repair-- } //--repair-- //--repair-- int Lsegment_highest_segment_index, Lsegment_highest_vertex_index; //--repair-- //--repair-- // ------------------------------------------------------------------------------ //--repair-- // Create data specific to mine which doesn't get written to disk. //--repair-- // Highest_segment_index and Highest_object_index must be valid. //--repair-- // 07/21: set repair center bit //--repair-- void create_local_segment_data(void) //--repair-- { //--repair-- int segnum; //--repair-- //--repair-- // --- Initialize all Lsegments. //--repair-- for (segnum=0; segnum <= Highest_segment_index; segnum++) { //--repair-- Lsegments[segnum].special_type = 0; //--repair-- Lsegments[segnum].special_segment = -1; //--repair-- } //--repair-- //--repair-- for (segnum=0; segnum <= Highest_segment_index; segnum++) { //--repair-- //--repair-- clsd_repair_center(segnum); //--repair-- clsd_materialization_center(segnum); //--repair-- //--repair-- } //--repair-- //--repair-- // Set check variables. //--repair-- // In main game loop, make sure these are valid, else Lsegments is not valid. //--repair-- Lsegment_highest_segment_index = Highest_segment_index; //--repair-- Lsegment_highest_vertex_index = Highest_vertex_index; //--repair-- } //--repair-- //--repair-- // ------------------------------------------------------------------------------------------ //--repair-- // Sort of makes sure create_local_segment_data has been called for the currently executing mine. //--repair-- // It is not failsafe, as you will see if you look at the code. //--repair-- // Returns 1 if Lsegments appears valid, 0 if not. //--repair-- int check_lsegments_validity(void) //--repair-- { //--repair-- return ((Lsegment_highest_segment_index == Highest_segment_index) && (Lsegment_highest_vertex_index == Highest_vertex_index)); //--repair-- } #define MAX_LOC_POINT_SEGS 64 int Connected_segment_distance; // ---------------------------------------------------------------------------------------------------------- // Determine whether seg0 and seg1 are reachable in a way that allows sound to pass. // Search up to a maximum depth of max_depth. // Return the distance. fix find_connected_distance(vms_vector *p0, int seg0, vms_vector *p1, int seg1, int max_depth, int wid_flag) { int cur_seg; int sidenum; int qtail = 0, qhead = 0; int i; byte visited[MAX_SEGMENTS]; seg_seg seg_queue[MAX_SEGMENTS]; short depth[MAX_SEGMENTS]; int cur_depth; int num_points; point_seg point_segs[MAX_LOC_POINT_SEGS]; fix dist; // If > this, will overrun point_segs buffer if (max_depth > MAX_LOC_POINT_SEGS-2) { mprintf((1, "Warning: In find_connected_distance, max_depth = %i, limited to %i\n", max_depth, MAX_LOC_POINT_SEGS-2)); max_depth = MAX_LOC_POINT_SEGS-2; } if (seg0 == seg1) { Connected_segment_distance = 0; return vm_vec_dist_quick(p0, p1); } else if (find_connect_side(&Segments[seg0], &Segments[seg1]) != -1) { Connected_segment_distance = 1; return vm_vec_dist_quick(p0, p1); } num_points = 0; // for (i=0; i<=Highest_segment_index; i++) { // visited[i] = 0; // depth[i] = 0; // } memset(visited, 0, Highest_segment_index+1); memset(depth, 0, Highest_segment_index+1); cur_seg = seg0; visited[cur_seg] = 1; cur_depth = 0; while (cur_seg != seg1) { segment *segp = &Segments[cur_seg]; for (sidenum = 0; sidenum < MAX_SIDES_PER_SEGMENT; sidenum++) { int snum = sidenum; if (WALL_IS_DOORWAY(segp, snum) & wid_flag) { int this_seg = segp->children[snum]; if (!visited[this_seg]) { seg_queue[qtail].start = cur_seg; seg_queue[qtail].end = this_seg; visited[this_seg] = 1; depth[qtail++] = cur_depth+1; if (max_depth != -1) { if (depth[qtail-1] == max_depth) { Connected_segment_distance = 1000; return -1; // seg1 = seg_queue[qtail-1].end; // goto fcd_done1; } } else if (this_seg == seg1) { goto fcd_done1; } } } } // for (sidenum... if (qhead >= qtail) { Connected_segment_distance = 1000; return -1; } cur_seg = seg_queue[qhead].end; cur_depth = depth[qhead]; qhead++; fcd_done1: ; } // while (cur_seg ... // Set qtail to the segment which ends at the goal. while (seg_queue[--qtail].end != seg1) if (qtail < 0) { Connected_segment_distance = 1000; return -1; } while (qtail >= 0) { int parent_seg, this_seg; this_seg = seg_queue[qtail].end; parent_seg = seg_queue[qtail].start; point_segs[num_points].segnum = this_seg; compute_segment_center(&point_segs[num_points].point,&Segments[this_seg]); num_points++; if (parent_seg == seg0) break; while (seg_queue[--qtail].end != parent_seg) Assert(qtail >= 0); } point_segs[num_points].segnum = seg0; compute_segment_center(&point_segs[num_points].point,&Segments[seg0]); num_points++; // Compute distance // mprintf((0, "Path = ")); // for (i=0; i= 0x00010000) return MATRIX_MAX; else if (f <= -0x00010000) return -MATRIX_MAX; else return f >> MATRIX_PRECISION; } #define VEL_PRECISION 12 // Create a shortpos struct from an object. // Extract the matrix into byte values. // Create a position relative to vertex 0 with 1/256 normal "fix" precision. // Stuff segment in a short. void create_shortpos(shortpos *spp, object *objp) { // int segnum; byte *sp; sp = spp->bytemat; *sp++ = convert_to_byte(objp->orient.rvec.x); *sp++ = convert_to_byte(objp->orient.uvec.x); *sp++ = convert_to_byte(objp->orient.fvec.x); *sp++ = convert_to_byte(objp->orient.rvec.y); *sp++ = convert_to_byte(objp->orient.uvec.y); *sp++ = convert_to_byte(objp->orient.fvec.y); *sp++ = convert_to_byte(objp->orient.rvec.z); *sp++ = convert_to_byte(objp->orient.uvec.z); *sp++ = convert_to_byte(objp->orient.fvec.z); spp->xo = (objp->pos.x - Vertices[Segments[objp->segnum].verts[0]].x) >> RELPOS_PRECISION; spp->yo = (objp->pos.y - Vertices[Segments[objp->segnum].verts[0]].y) >> RELPOS_PRECISION; spp->zo = (objp->pos.z - Vertices[Segments[objp->segnum].verts[0]].z) >> RELPOS_PRECISION; spp->segment = objp->segnum; spp->velx = (objp->mtype.phys_info.velocity.x) >> VEL_PRECISION; spp->vely = (objp->mtype.phys_info.velocity.y) >> VEL_PRECISION; spp->velz = (objp->mtype.phys_info.velocity.z) >> VEL_PRECISION; // mprintf((0, "Matrix: %08x %08x %08x %08x %08x %08x\n", objp->orient.m1,objp->orient.m2,objp->orient.m3, // spp->bytemat[0] << MATRIX_PRECISION,spp->bytemat[1] << MATRIX_PRECISION,spp->bytemat[2] << MATRIX_PRECISION)); // // mprintf((0, " %08x %08x %08x %08x %08x %08x\n", objp->orient.m4,objp->orient.m5,objp->orient.m6, // spp->bytemat[3] << MATRIX_PRECISION,spp->bytemat[4] << MATRIX_PRECISION,spp->bytemat[5] << MATRIX_PRECISION)); // // mprintf((0, " %08x %08x %08x %08x %08x %08x\n", objp->orient.m7,objp->orient.m8,objp->orient.m9, // spp->bytemat[6] << MATRIX_PRECISION,spp->bytemat[7] << MATRIX_PRECISION,spp->bytemat[8] << MATRIX_PRECISION)); // // mprintf((0, "Positn: %08x %08x %08x %08x %08x %08x\n", objp->pos.x, objp->pos.y, objp->pos.z, // (spp->xo << RELPOS_PRECISION) + Vertices[Segments[segnum].verts[0]].x, // (spp->yo << RELPOS_PRECISION) + Vertices[Segments[segnum].verts[0]].y, // (spp->zo << RELPOS_PRECISION) + Vertices[Segments[segnum].verts[0]].z)); // mprintf((0, "Segment: %3i %3i\n", objp->segnum, spp->segment)); } void extract_shortpos(object *objp, shortpos *spp) { int segnum; byte *sp; sp = spp->bytemat; objp->orient.rvec.x = *sp++ << MATRIX_PRECISION; objp->orient.uvec.x = *sp++ << MATRIX_PRECISION; objp->orient.fvec.x = *sp++ << MATRIX_PRECISION; objp->orient.rvec.y = *sp++ << MATRIX_PRECISION; objp->orient.uvec.y = *sp++ << MATRIX_PRECISION; objp->orient.fvec.y = *sp++ << MATRIX_PRECISION; objp->orient.rvec.z = *sp++ << MATRIX_PRECISION; objp->orient.uvec.z = *sp++ << MATRIX_PRECISION; objp->orient.fvec.z = *sp++ << MATRIX_PRECISION; segnum = spp->segment; Assert((segnum >= 0) && (segnum <= Highest_segment_index)); objp->pos.x = (spp->xo << RELPOS_PRECISION) + Vertices[Segments[segnum].verts[0]].x; objp->pos.y = (spp->yo << RELPOS_PRECISION) + Vertices[Segments[segnum].verts[0]].y; objp->pos.z = (spp->zo << RELPOS_PRECISION) + Vertices[Segments[segnum].verts[0]].z; objp->mtype.phys_info.velocity.x = (spp->velx << VEL_PRECISION); objp->mtype.phys_info.velocity.y = (spp->vely << VEL_PRECISION); objp->mtype.phys_info.velocity.z = (spp->velz << VEL_PRECISION); obj_relink(objp-Objects, segnum); // mprintf((0, "Matrix: %08x %08x %08x %08x %08x %08x\n", objp->orient.m1,objp->orient.m2,objp->orient.m3, // spp->bytemat[0],spp->bytemat[1],spp->bytemat[2])); // // mprintf((0, " %08x %08x %08x %08x %08x %08x\n", objp->orient.m4,objp->orient.m5,objp->orient.m6, // spp->bytemat[3],spp->bytemat[4],spp->bytemat[5])); // // mprintf((0, " %08x %08x %08x %08x %08x %08x\n", objp->orient.m7,objp->orient.m8,objp->orient.m9, // spp->bytemat[6],spp->bytemat[7],spp->bytemat[8])); // // mprintf((0, "Positn: %08x %08x %08x %08x %08x %08x\n", objp->pos.x, objp->pos.y, objp->pos.z, // (spp->xo << RELPOS_PRECISION) + Vertices[Segments[segnum].verts[0]].x, (spp->yo << RELPOS_PRECISION) + Vertices[Segments[segnum].verts[0]].y, (spp->zo << RELPOS_PRECISION) + Vertices[Segments[segnum].verts[0]].z)); // mprintf((0, "Segment: %3i %3i\n", objp->segnum, spp->segment)); } //--unused-- void test_shortpos(void) //--unused-- { //--unused-- shortpos spp; //--unused-- //--unused-- create_shortpos(&spp, &Objects[0]); //--unused-- extract_shortpos(&Objects[0], &spp); //--unused-- //--unused-- } // ----------------------------------------------------------------------------- // Segment validation functions. // Moved from editor to game so we can compute surface normals at load time. // ------------------------------------------------------------------------------- // ------------------------------------------------------------------------------------------ // Extract a vector from a segment. The vector goes from the start face to the end face. // The point on each face is the average of the four points forming the face. void extract_vector_from_segment(segment *sp, vms_vector *vp, int start, int end) { int i; vms_vector vs,ve; vm_vec_zero(&vs); vm_vec_zero(&ve); for (i=0; i<4; i++) { vm_vec_add2(&vs,&Vertices[sp->verts[Side_to_verts[start][i]]]); vm_vec_add2(&ve,&Vertices[sp->verts[Side_to_verts[end][i]]]); } vm_vec_sub(vp,&ve,&vs); vm_vec_scale(vp,F1_0/4); } //create a matrix that describes the orientation of the given segment void extract_orient_from_segment(vms_matrix *m,segment *seg) { vms_vector fvec,uvec; extract_vector_from_segment(seg,&fvec,WFRONT,WBACK); extract_vector_from_segment(seg,&uvec,WBOTTOM,WTOP); //vector to matrix does normalizations and orthogonalizations vm_vector_2_matrix(m,&fvec,&uvec,NULL); } #ifdef EDITOR // ------------------------------------------------------------------------------------------ // Extract the forward vector from segment *sp, return in *vp. // The forward vector is defined to be the vector from the the center of the front face of the segment // to the center of the back face of the segment. void extract_forward_vector_from_segment(segment *sp,vms_vector *vp) { extract_vector_from_segment(sp,vp,WFRONT,WBACK); } // ------------------------------------------------------------------------------------------ // Extract the right vector from segment *sp, return in *vp. // The forward vector is defined to be the vector from the the center of the left face of the segment // to the center of the right face of the segment. void extract_right_vector_from_segment(segment *sp,vms_vector *vp) { extract_vector_from_segment(sp,vp,WLEFT,WRIGHT); } // ------------------------------------------------------------------------------------------ // Extract the up vector from segment *sp, return in *vp. // The forward vector is defined to be the vector from the the center of the bottom face of the segment // to the center of the top face of the segment. void extract_up_vector_from_segment(segment *sp,vms_vector *vp) { extract_vector_from_segment(sp,vp,WBOTTOM,WTOP); } #endif void add_side_as_quad(segment *sp, int sidenum, vms_vector *normal) { side *sidep = &sp->sides[sidenum]; sidep->type = SIDE_IS_QUAD; #ifdef COMPACT_SEGS normal = normal; //avoid compiler warning #else sidep->normals[0] = *normal; sidep->normals[1] = *normal; #endif // If there is a connection here, we only formed the faces for the purpose of determining segment boundaries, // so don't generate polys, else they will get rendered. // if (sp->children[sidenum] != -1) // sidep->render_flag = 0; // else // sidep->render_flag = 1; } // ------------------------------------------------------------------------------- // Return v0, v1, v2 = 3 vertices with smallest numbers. If *negate_flag set, then negate normal after computation. // Note, you cannot just compute the normal by treating the points in the opposite direction as this introduces // small differences between normals which should merely be opposites of each other. get_verts_for_normal(int va, int vb, int vc, int vd, int *v0, int *v1, int *v2, int *v3, int *negate_flag) { int i,j; int v[4],w[4]; // w is a list that shows how things got scrambled so we know if our normal is pointing backwards for (i=0; i<4; i++) w[i] = i; v[0] = va; v[1] = vb; v[2] = vc; v[3] = vd; for (i=1; i<4; i++) for (j=0; j v[i]) { int t; t = v[j]; v[j] = v[i]; v[i] = t; t = w[j]; w[j] = w[i]; w[i] = t; } Assert((v[0] < v[1]) && (v[1] < v[2]) && (v[2] < v[3])); // Now, if for any w[i] & w[i+1]: w[i+1] = (w[i]+3)%4, then must swap *v0 = v[0]; *v1 = v[1]; *v2 = v[2]; *v3 = v[3]; if ( (((w[0]+3) % 4) == w[1]) || (((w[1]+3) % 4) == w[2])) *negate_flag = 1; else *negate_flag = 0; } // ------------------------------------------------------------------------------- void add_side_as_2_triangles(segment *sp, int sidenum) { vms_vector norm; char *vs = Side_to_verts[sidenum]; fix dot; vms_vector vec_13; // vector from vertex 1 to vertex 3 side *sidep = &sp->sides[sidenum]; // Choose how to triangulate. // If a wall, then // Always triangulate so segment is convex. // Use Matt's formula: Na . AD > 0, where ABCD are vertices on side, a is face formed by A,B,C, Na is normal from face a. // If not a wall, then triangulate so whatever is on the other side is triangulated the same (ie, between the same absoluate vertices) if (!IS_CHILD(sp->children[sidenum])) { vm_vec_normal(&norm, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[2]]]); vm_vec_sub(&vec_13, &Vertices[sp->verts[vs[3]]], &Vertices[sp->verts[vs[1]]]); dot = vm_vec_dot(&norm, &vec_13); // Now, signifiy whether to triangulate from 0:2 or 1:3 if (dot >= 0) sidep->type = SIDE_IS_TRI_02; else sidep->type = SIDE_IS_TRI_13; #ifndef COMPACT_SEGS // Now, based on triangulation type, set the normals. if (sidep->type == SIDE_IS_TRI_02) { vm_vec_normal(&norm, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[2]]]); sidep->normals[0] = norm; vm_vec_normal(&norm, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[2]]], &Vertices[sp->verts[vs[3]]]); sidep->normals[1] = norm; } else { vm_vec_normal(&norm, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[3]]]); sidep->normals[0] = norm; vm_vec_normal(&norm, &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[2]]], &Vertices[sp->verts[vs[3]]]); sidep->normals[1] = norm; } #endif } else { int i,v[4], vsorted[4]; int negate_flag; for (i=0; i<4; i++) v[i] = sp->verts[vs[i]]; get_verts_for_normal(v[0], v[1], v[2], v[3], &vsorted[0], &vsorted[1], &vsorted[2], &vsorted[3], &negate_flag); if ((vsorted[0] == v[0]) || (vsorted[0] == v[2])) { sidep->type = SIDE_IS_TRI_02; #ifndef COMPACT_SEGS // Now, get vertices for normal for each triangle based on triangulation type. get_verts_for_normal(v[0], v[1], v[2], 32767, &vsorted[0], &vsorted[1], &vsorted[2], &vsorted[3], &negate_flag); vm_vec_normal(&norm, &Vertices[vsorted[0]], &Vertices[vsorted[1]], &Vertices[vsorted[2]]); if (negate_flag) vm_vec_negate(&norm); sidep->normals[0] = norm; get_verts_for_normal(v[0], v[2], v[3], 32767, &vsorted[0], &vsorted[1], &vsorted[2], &vsorted[3], &negate_flag); vm_vec_normal(&norm, &Vertices[vsorted[0]], &Vertices[vsorted[1]], &Vertices[vsorted[2]]); if (negate_flag) vm_vec_negate(&norm); sidep->normals[1] = norm; #endif } else { sidep->type = SIDE_IS_TRI_13; #ifndef COMPACT_SEGS // Now, get vertices for normal for each triangle based on triangulation type. get_verts_for_normal(v[0], v[1], v[3], 32767, &vsorted[0], &vsorted[1], &vsorted[2], &vsorted[3], &negate_flag); vm_vec_normal(&norm, &Vertices[vsorted[0]], &Vertices[vsorted[1]], &Vertices[vsorted[2]]); if (negate_flag) vm_vec_negate(&norm); sidep->normals[0] = norm; get_verts_for_normal(v[1], v[2], v[3], 32767, &vsorted[0], &vsorted[1], &vsorted[2], &vsorted[3], &negate_flag); vm_vec_normal(&norm, &Vertices[vsorted[0]], &Vertices[vsorted[1]], &Vertices[vsorted[2]]); if (negate_flag) vm_vec_negate(&norm); sidep->normals[1] = norm; #endif } } } int sign(fix v) { if (v > PLANE_DIST_TOLERANCE) return 1; else if (v < -(PLANE_DIST_TOLERANCE+1)) //neg & pos round differently return -1; else return 0; } // ------------------------------------------------------------------------------- void create_walls_on_side(segment *sp, int sidenum) { int vm0, vm1, vm2, vm3, negate_flag; int v0, v1, v2, v3; vms_vector vn; fix dist_to_plane; v0 = sp->verts[Side_to_verts[sidenum][0]]; v1 = sp->verts[Side_to_verts[sidenum][1]]; v2 = sp->verts[Side_to_verts[sidenum][2]]; v3 = sp->verts[Side_to_verts[sidenum][3]]; get_verts_for_normal(v0, v1, v2, v3, &vm0, &vm1, &vm2, &vm3, &negate_flag); vm_vec_normal(&vn, &Vertices[vm0], &Vertices[vm1], &Vertices[vm2]); dist_to_plane = abs(vm_dist_to_plane(&Vertices[vm3], &vn, &Vertices[vm0])); //if ((sp-Segments == 0x7b) && (sidenum == 3)) { // mprintf((0, "Verts = %3i %3i %3i %3i, negate flag = %3i, dist = %8x\n", vm0, vm1, vm2, vm3, negate_flag, dist_to_plane)); // mprintf((0, " Normal = %8x %8x %8x\n", vn.x, vn.y, vn.z)); // mprintf((0, " Vert %3i = [%8x %8x %8x]\n", vm0, Vertices[vm0].x, Vertices[vm0].y, Vertices[vm0].z)); // mprintf((0, " Vert %3i = [%8x %8x %8x]\n", vm1, Vertices[vm1].x, Vertices[vm1].y, Vertices[vm1].z)); // mprintf((0, " Vert %3i = [%8x %8x %8x]\n", vm2, Vertices[vm2].x, Vertices[vm2].y, Vertices[vm2].z)); // mprintf((0, " Vert %3i = [%8x %8x %8x]\n", vm3, Vertices[vm3].x, Vertices[vm3].y, Vertices[vm3].z)); //} //if ((sp-Segments == 0x86) && (sidenum == 5)) { // mprintf((0, "Verts = %3i %3i %3i %3i, negate flag = %3i, dist = %8x\n", vm0, vm1, vm2, vm3, negate_flag, dist_to_plane)); // mprintf((0, " Normal = %8x %8x %8x\n", vn.x, vn.y, vn.z)); // mprintf((0, " Vert %3i = [%8x %8x %8x]\n", vm0, Vertices[vm0].x, Vertices[vm0].y, Vertices[vm0].z)); // mprintf((0, " Vert %3i = [%8x %8x %8x]\n", vm1, Vertices[vm1].x, Vertices[vm1].y, Vertices[vm1].z)); // mprintf((0, " Vert %3i = [%8x %8x %8x]\n", vm2, Vertices[vm2].x, Vertices[vm2].y, Vertices[vm2].z)); // mprintf((0, " Vert %3i = [%8x %8x %8x]\n", vm3, Vertices[vm3].x, Vertices[vm3].y, Vertices[vm3].z)); //} if (negate_flag) vm_vec_negate(&vn); if (dist_to_plane <= PLANE_DIST_TOLERANCE) add_side_as_quad(sp, sidenum, &vn); else { add_side_as_2_triangles(sp, sidenum); //this code checks to see if we really should be triangulated, and //de-triangulates if we shouldn't be. { int num_faces; int vertex_list[6]; fix dist0,dist1; int s0,s1; int vertnum; side *s; create_abs_vertex_lists( &num_faces, vertex_list, sp-Segments, sidenum); Assert(num_faces == 2); s = &sp->sides[sidenum]; vertnum = min(vertex_list[0],vertex_list[2]); #ifdef COMPACT_SEGS { vms_vector normals[2]; get_side_normals(sp, sidenum, &normals[0], &normals[1] ); dist0 = vm_dist_to_plane(&Vertices[vertex_list[1]],&normals[1],&Vertices[vertnum]); dist1 = vm_dist_to_plane(&Vertices[vertex_list[4]],&normals[0],&Vertices[vertnum]); } #else dist0 = vm_dist_to_plane(&Vertices[vertex_list[1]],&s->normals[1],&Vertices[vertnum]); dist1 = vm_dist_to_plane(&Vertices[vertex_list[4]],&s->normals[0],&Vertices[vertnum]); #endif s0 = sign(dist0); s1 = sign(dist1); if (s0==0 || s1==0 || s0!=s1) { sp->sides[sidenum].type = SIDE_IS_QUAD; //detriangulate! #ifndef COMPACT_SEGS sp->sides[sidenum].normals[0] = vn; sp->sides[sidenum].normals[1] = vn; #endif } } } } #ifdef COMPACT_SEGS //#define CACHE_DEBUG 1 #define MAX_CACHE_NORMALS 128 #define CACHE_MASK 127 typedef struct ncache_element { short segnum; ubyte sidenum; vms_vector normals[2]; } ncache_element; int ncache_initialized = 0; ncache_element ncache[MAX_CACHE_NORMALS]; #ifdef CACHE_DEBUG int ncache_counter = 0; int ncache_hits = 0; int ncache_misses = 0; #endif void ncache_init() { ncache_flush(); ncache_initialized = 1; } void ncache_flush() { int i; for (i=0; i 0)) mprintf(( 0, "NCACHE %d%% missed, H:%d, M:%d\n", (ncache_misses*100)/(ncache_hits+ncache_misses), ncache_hits, ncache_misses )); #endif i = ((segnum<<2) ^ sidenum) & CACHE_MASK; if ((ncache[i].segnum == segnum) && ((ncache[i].sidenum&0xf)==sidenum) ) { uint f1; #ifdef CACHE_DEBUG ncache_hits++; #endif f1 = ncache[i].sidenum>>4; if ( (f1&face_flags)==face_flags ) return i; if ( f1 & 1 ) uncached_get_side_normal( &Segments[segnum], sidenum, 1, &ncache[i].normals[1] ); else uncached_get_side_normal( &Segments[segnum], sidenum, 0, &ncache[i].normals[0] ); ncache[i].sidenum |= face_flags<<4; return i; } #ifdef CACHE_DEBUG ncache_misses++; #endif switch( face_flags ) { case 1: uncached_get_side_normal( &Segments[segnum], sidenum, 0, &ncache[i].normals[0] ); break; case 2: uncached_get_side_normal( &Segments[segnum], sidenum, 1, &ncache[i].normals[1] ); break; case 3: uncached_get_side_normals(&Segments[segnum], sidenum, &ncache[i].normals[0], &ncache[i].normals[1] ); break; } ncache[i].segnum = segnum; ncache[i].sidenum = sidenum | (face_flags<<4); return i; } void get_side_normal(segment *sp, int sidenum, int face_num, vms_vector * vm ) { int i; i = find_ncache_element( sp - Segments, sidenum, 1 << face_num ); *vm = ncache[i].normals[face_num]; if (0) { vms_vector tmp; uncached_get_side_normal(sp, sidenum, face_num, &tmp ); Assert( tmp.x == vm->x ); Assert( tmp.y == vm->y ); Assert( tmp.z == vm->z ); } } void get_side_normals(segment *sp, int sidenum, vms_vector * vm1, vms_vector * vm2 ) { int i; i = find_ncache_element( sp - Segments, sidenum, 3 ); *vm1 = ncache[i].normals[0]; *vm2 = ncache[i].normals[1]; if (0) { vms_vector tmp; uncached_get_side_normal(sp, sidenum, 0, &tmp ); Assert( tmp.x == vm1->x ); Assert( tmp.y == vm1->y ); Assert( tmp.z == vm1->z ); uncached_get_side_normal(sp, sidenum, 1, &tmp ); Assert( tmp.x == vm2->x ); Assert( tmp.y == vm2->y ); Assert( tmp.z == vm2->z ); } } void uncached_get_side_normal(segment *sp, int sidenum, int face_num, vms_vector * vm ) { int vm0, vm1, vm2, vm3, negate_flag; char *vs = Side_to_verts[sidenum]; switch( sp->sides[sidenum].type ) { case SIDE_IS_QUAD: get_verts_for_normal(sp->verts[vs[0]], sp->verts[vs[1]], sp->verts[vs[2]], sp->verts[vs[3]], &vm0, &vm1, &vm2, &vm3, &negate_flag); vm_vec_normal(vm, &Vertices[vm0], &Vertices[vm1], &Vertices[vm2]); if (negate_flag) vm_vec_negate(vm); break; case SIDE_IS_TRI_02: if ( face_num == 0 ) vm_vec_normal(vm, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[2]]]); else vm_vec_normal(vm, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[2]]], &Vertices[sp->verts[vs[3]]]); break; case SIDE_IS_TRI_13: if ( face_num == 0 ) vm_vec_normal(vm, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[3]]]); else vm_vec_normal(vm, &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[2]]], &Vertices[sp->verts[vs[3]]]); break; } } void uncached_get_side_normals(segment *sp, int sidenum, vms_vector * vm1, vms_vector * vm2 ) { int vvm0, vvm1, vvm2, vvm3, negate_flag; char *vs = Side_to_verts[sidenum]; switch( sp->sides[sidenum].type ) { case SIDE_IS_QUAD: get_verts_for_normal(sp->verts[vs[0]], sp->verts[vs[1]], sp->verts[vs[2]], sp->verts[vs[3]], &vvm0, &vvm1, &vvm2, &vvm3, &negate_flag); vm_vec_normal(vm1, &Vertices[vvm0], &Vertices[vvm1], &Vertices[vvm2]); if (negate_flag) vm_vec_negate(vm1); *vm2 = *vm1; break; case SIDE_IS_TRI_02: vm_vec_normal(vm1, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[2]]]); vm_vec_normal(vm2, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[2]]], &Vertices[sp->verts[vs[3]]]); break; case SIDE_IS_TRI_13: vm_vec_normal(vm1, &Vertices[sp->verts[vs[0]]], &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[3]]]); vm_vec_normal(vm2, &Vertices[sp->verts[vs[1]]], &Vertices[sp->verts[vs[2]]], &Vertices[sp->verts[vs[3]]]); break; } } #endif // ------------------------------------------------------------------------------- void validate_removable_wall(segment *sp, int sidenum, int tmap_num) { create_walls_on_side(sp, sidenum); sp->sides[sidenum].tmap_num = tmap_num; // assign_default_uvs_to_side(sp, sidenum); // assign_light_to_side(sp, sidenum); } // ------------------------------------------------------------------------------- // Make a just-modified segment side valid. void validate_segment_side(segment *sp, int sidenum) { if (sp->sides[sidenum].wall_num == -1) create_walls_on_side(sp, sidenum); else // create_removable_wall(sp, sidenum, sp->sides[sidenum].tmap_num); validate_removable_wall(sp, sidenum, sp->sides[sidenum].tmap_num); // Set render_flag. // If side doesn't have a child, then render wall. If it does have a child, but there is a temporary // wall there, then do render wall. // if (sp->children[sidenum] == -1) // sp->sides[sidenum].render_flag = 1; // else if (sp->sides[sidenum].wall_num != -1) // sp->sides[sidenum].render_flag = 1; // else // sp->sides[sidenum].render_flag = 0; } extern int check_for_degenerate_segment(segment *sp); // ------------------------------------------------------------------------------- // Make a just-modified segment valid. // check all sides to see how many faces they each should have (0,1,2) // create new vector normals void validate_segment(segment *sp) { int side; #ifdef EDITOR check_for_degenerate_segment(sp); #endif for (side = 0; side < MAX_SIDES_PER_SEGMENT; side++) validate_segment_side(sp, side); // assign_default_uvs_to_segment(sp); } // ------------------------------------------------------------------------------- // Validate all segments. // Highest_segment_index must be set. // For all used segments (number <= Highest_segment_index), segnum field must be != -1. void validate_segment_all(void) { int s; for (s=0; s<=Highest_segment_index; s++) #ifdef EDITOR if (Segments[s].segnum != -1) #endif validate_segment(&Segments[s]); #ifdef EDITOR { int said=0; for (s=Highest_segment_index+1; s> 15; vm_vec_sub(&vec2, &Vertices[Segments[segnum].verts[vnum]], new_pos); vm_vec_scale(&vec2, rand()); // rand() always in 0..1/2 vm_vec_add2(new_pos, &vec2); } // ---------------------------------------------------------------------------------------------------------- // Set the segment depth of all segments from start_seg in *segbuf. // Returns maximum depth value. int set_segment_depths(int start_seg, ubyte *segbuf) { int i, curseg; ubyte visited[MAX_SEGMENTS]; int queue[MAX_SEGMENTS]; int head, tail; int depth; int parent_depth; depth = 1; head = 0; tail = 0; for (i=0; i<=Highest_segment_index; i++) visited[i] = 0; if (segbuf[start_seg] == 0) return 1; queue[tail++] = start_seg; visited[start_seg] = 1; segbuf[start_seg] = depth++; if (depth == 0) depth = 255; while (head < tail) { curseg = queue[head++]; parent_depth = segbuf[curseg]; for (i=0; i