main/editor/fixseg.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  * $Source: /cvs/cvsroot/d2x/main/editor/fixseg.c,v $
  15  * $Revision: 1.1 $
  16  * $Author: btb $
  17  * $Date: 2004-12-19 13:54:27 $
  18  *
  19  * Functions to make faces planar and probably other things.
  20  *
  21  * $Log: not supported by cvs2svn $
  22  * Revision 1.2  2003/03/09 06:34:09  donut
  23  * change byte typedef to sbyte to avoid conflict with win32 byte which is unsigned
  24  *
  25  * Revision 1.1.1.1  1999/06/14 22:03:05  donut
  26  * Import of d1x 1.37 source.
  27  *
  28  * Revision 2.0  1995/02/27  11:36:25  john
  29  * Version 2.0. Ansi-fied.
  30  *
  31  * Revision 1.7  1994/11/27  23:18:01  matt
  32  * Made changes for new mprintf calling convention
  33  *
  34  * Revision 1.6  1994/11/17  14:48:00  mike
  35  * validation functions moved from editor to game.
  36  *
  37  * Revision 1.5  1994/08/04  19:13:26  matt
  38  * Changed a bunch of vecmat calls to use multiple-function routines, and to
  39  * allow the use of C macros for some functions
  40  *
  41  * Revision 1.4  1994/02/10  15:36:31  matt
  42  * Various changes to make editor compile out.
  43  *
  44  * Revision 1.3  1993/12/03  18:45:09  mike
  45  * initial stuff.
  46  *
  47  * Revision 1.2  1993/11/30  17:05:09  mike
  48  * Added part of code to make a side planar.
  49  *
  50  * Revision 1.1  1993/11/30  10:05:36  mike
  51  * Initial revision
  52  *
  53  *
  54  */
  55
  56
  57 #ifdef RCS
  58 static char rcsid[] = "$Id: fixseg.c,v 1.1 2004-12-19 13:54:27 btb Exp $";
  59 #endif
  60
  61 #include <stdio.h>
  62 #include <stdlib.h>
  63 #include <math.h>
  64 #include <string.h>
  65
  66 #include "mono.h"
  67 #include "key.h"
  68 #include "gr.h"
  69
  70 #include "inferno.h"
  71 #include "segment.h"
  72 //#include "segment2.h"
  73 #include        "editor.h"
  74 #include "error.h"
  75 #include "gameseg.h"
  76
  77 #define SWAP(a,b) {temp = (a); (a) = (b); (b) = temp;}
  78
  79 //      -----------------------------------------------------------------------------------------------------------------
  80 //      Gauss-Jordan elimination solution of a system of linear equations.
  81 //      a[1..n][1..n] is the input matrix.  b[1..n][1..m] is input containing the m right-hand side vectors.
  82 //      On output, a is replaced by its matrix inverse and b is replaced by the corresponding set of solution vectors.
  83 void gaussj(fix **a, int n, fix **b, int m)
  84 {
  85         int     indxc[4], indxr[4], ipiv[4];
  86         int     i, icol=0, irow=0, j, k, l, ll;
  87         fix     big, dum, pivinv, temp;
  88
  89         if (n > 4) {
  90                 mprintf((0,"Error -- array too large in gaussj.\n"));
  91                 Int3();
  92         }
  93
  94         for (j=1; j<=n; j++)
  95                 ipiv[j] = 0;
  96
  97         for (i=1; i<=n; i++) {
  98                 big = 0;
  99                 for (j=1; j<=n; j++)
 100                         if (ipiv[j] != 1)
 101                                 for (k=1; k<=n; k++) {
 102                                         if (ipiv[k] == 0) {
 103                                                 if (abs(a[j][k]) >= big) {
 104                                                         big = abs(a[j][k]);
 105                                                         irow = j;
 106                                                         icol = k;
 107                                                 }
 108                                         } else if (ipiv[k] > 1) {
 109                                                 mprintf((0,"Error: Singular matrix-1\n"));
 110                                                 Int3();
 111                                         }
 112                                 }
 113
 114                 ++(ipiv[icol]);
 115
 116                 // We now have the pivot element, so we interchange rows, if needed, to put the pivot
 117                 //      element on the diagonal.  The columns are not physically interchanged, only relabeled:
 118                 //      indxc[i], the column of the ith pivot element, is the ith column that is reduced, while
 119                 //      indxr[i] is the row in which that pivot element was originally located.  If indxr[i] !=
 120                 //      indxc[i] there is an implied column interchange.  With this form of bookkeeping, the
 121                 //      solution b's will end up in the correct order, and the inverse matrix will be scrambled
 122                 //      by columns.
 123
 124                 if (irow != icol) {
 125                         for (l=1; l<=n; l++)
 126                                 SWAP(a[irow][l], a[icol][l]);
 127                         for (l=1; l<=m; l++)
 128                                 SWAP(b[irow][l], b[icol][l]);
 129                 }
 130
 131                 indxr[i] = irow;
 132                 indxc[i] = icol;
 133                 if (a[icol][icol] == 0) {
 134                         mprintf((0,"Error: Singular matrix-2\n"));
 135                         Int3();
 136                 }
 137                 pivinv = fixdiv(F1_0, a[icol][icol]);
 138                 a[icol][icol] = F1_0;
 139
 140                 for (l=1; l<=n; l++)
 141                         a[icol][l] = fixmul(a[icol][l], pivinv);
 142                 for (l=1; l<=m; l++)
 143                         b[icol][l] = fixmul(b[icol][l], pivinv);
 144
 145                 for (ll=1; ll<=n; ll++)
 146                         if (ll != icol) {
 147                                 dum = a[ll][icol];
 148                                 a[ll][icol] = 0;
 149                                 for (l=1; l<=n; l++)
 150                                         a[ll][l] -= a[icol][l]*dum;
 151                                 for (l=1; l<=m; l++)
 152                                         b[ll][l] -= b[icol][l]*dum;
 153                         }
 154         }
 155
 156         //      This is the end of the main loop over columns of the reduction.  It only remains to unscramble
 157         //      the solution in view of the column interchanges.  We do this by interchanging pairs of
 158         //      columns in the reverse order that the permutation was built up.
 159         for (l=n; l>=1; l--) {
 160                 if (indxr[l] != indxc[l])
 161                         for (k=1; k<=n; k++)
 162                                 SWAP(a[k][indxr[l]], a[k][indxc[l]]);
 163         }
 164
 165 }
 166
 167
 168 //      -----------------------------------------------------------------------------------------------------------------
 169 //      Return true if side is planar, else return false.
 170 int side_is_planar_p(segment *sp, int side)
 171 {
 172         sbyte                   *vp;
 173         vms_vector      *v0,*v1,*v2,*v3;
 174         vms_vector      va,vb;
 175
 176         vp = Side_to_verts[side];
 177         v0 = &Vertices[sp->verts[vp[0]]];
 178         v1 = &Vertices[sp->verts[vp[1]]];
 179         v2 = &Vertices[sp->verts[vp[2]]];
 180         v3 = &Vertices[sp->verts[vp[3]]];
 181
 182         vm_vec_normalize(vm_vec_normal(&va,v0,v1,v2));
 183         vm_vec_normalize(vm_vec_normal(&vb,v0,v2,v3));
 184
 185         // If the two vectors are very close to being the same, then generate one quad, else generate two triangles.
 186         return (vm_vec_dist(&va,&vb) < F1_0/1000);
 187 }
 188
 189 //      -------------------------------------------------------------------------------------------------
 190 //      Return coordinates of a vertex which is vertex v moved so that all sides of which it is a part become planar.
 191 void compute_planar_vert(segment *sp, int side, int v, vms_vector *vp)
 192 {
 193         if ((sp) && (side > -3))
 194                 *vp = Vertices[v];
 195 }
 196
 197 //      -------------------------------------------------------------------------------------------------
 198 //      Making Cursegp:Curside planar.
 199 //      If already planar, return.
 200 //      for each vertex v on side, not part of another segment
 201 //              choose the vertex v which can be moved to make all sides of which it is a part planar, minimizing distance moved
 202 //      if there is no vertex v on side, not part of another segment, give up in disgust
 203 //      Return value:
 204 //              0       curside made planar (or already was)
 205 //              1       did not make curside planar
 206 int make_curside_planar(void)
 207 {
 208         int                     v;
 209         sbyte                   *vp;
 210         vms_vector      planar_verts[4];                        // store coordinates of up to 4 vertices which will make Curside planar, corresponding to each of 4 vertices on side
 211         int                     present_verts[4];                       //      set to 1 if vertex is present
 212
 213         if (side_is_planar_p(Cursegp, Curside))
 214                 return 0;
 215
 216         //      Look at all vertices in side to find a free one.
 217         for (v=0; v<4; v++)
 218                 present_verts[v] = 0;
 219
 220         vp = Side_to_verts[Curside];
 221
 222         for (v=0; v<4; v++) {
 223                 int v1 = vp[v];         // absolute vertex id
 224                 if (is_free_vertex(Cursegp->verts[v1])) {
 225                         compute_planar_vert(Cursegp, Curside, Cursegp->verts[v1], &planar_verts[v]);
 226                         present_verts[v] = 1;
 227                 }
 228         }
 229
 230         //      Now, for each v for which present_verts[v] == 1, there is a vector (point) in planar_verts[v].
 231         //      See which one is closest to the plane defined by the other three points.
 232         //      Nah...just use the first one we find.
 233         for (v=0; v<4; v++)
 234                 if (present_verts[v]) {
 235                         med_set_vertex(vp[v],&planar_verts[v]);
 236                         validate_segment(Cursegp);
 237                         // -- should propagate tmaps to segments or something here...
 238
 239                         return 0;
 240                 }
 241         //      We tried, but we failed, to make Curside planer.
 242         return 1;
 243 }
 244