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 /*
  15  *
  16  * Functions to make faces planar and probably other things.
  17  *
  18  */
  19
  20 #ifdef HAVE_CONFIG_H
  21 #include "conf.h"
  22 #endif
  23
  24 #include <stdio.h>
  25 #include <stdlib.h>
  26 #include <math.h>
  27 #include <string.h>
  28
  29 #include "mono.h"
  30 #include "key.h"
  31 #include "gr.h"
  32
  33 #include "inferno.h"
  34 #include "segment.h"
  35 //#include "segment2.h"
  36 #include        "editor.h"
  37 #include "error.h"
  38 #include "gameseg.h"
  39
  40 #define SWAP(a,b) {temp = (a); (a) = (b); (b) = temp;}
  41
  42 //      -----------------------------------------------------------------------------------------------------------------
  43 //      Gauss-Jordan elimination solution of a system of linear equations.
  44 //      a[1..n][1..n] is the input matrix.  b[1..n][1..m] is input containing the m right-hand side vectors.
  45 //      On output, a is replaced by its matrix inverse and b is replaced by the corresponding set of solution vectors.
  46 void gaussj(fix **a, int n, fix **b, int m)
  47 {
  48         int     indxc[4], indxr[4], ipiv[4];
  49         int     i, icol=0, irow=0, j, k, l, ll;
  50         fix     big, dum, pivinv, temp;
  51
  52         if (n > 4) {
  53                 mprintf((0,"Error -- array too large in gaussj.\n"));
  54                 Int3();
  55         }
  56
  57         for (j=1; j<=n; j++)
  58                 ipiv[j] = 0;
  59
  60         for (i=1; i<=n; i++) {
  61                 big = 0;
  62                 for (j=1; j<=n; j++)
  63                         if (ipiv[j] != 1)
  64                                 for (k=1; k<=n; k++) {
  65                                         if (ipiv[k] == 0) {
  66                                                 if (abs(a[j][k]) >= big) {
  67                                                         big = abs(a[j][k]);
  68                                                         irow = j;
  69                                                         icol = k;
  70                                                 }
  71                                         } else if (ipiv[k] > 1) {
  72                                                 mprintf((0,"Error: Singular matrix-1\n"));
  73                                                 Int3();
  74                                         }
  75                                 }
  76
  77                 ++(ipiv[icol]);
  78
  79                 // We now have the pivot element, so we interchange rows, if needed, to put the pivot
  80                 //      element on the diagonal.  The columns are not physically interchanged, only relabeled:
  81                 //      indxc[i], the column of the ith pivot element, is the ith column that is reduced, while
  82                 //      indxr[i] is the row in which that pivot element was originally located.  If indxr[i] !=
  83                 //      indxc[i] there is an implied column interchange.  With this form of bookkeeping, the
  84                 //      solution b's will end up in the correct order, and the inverse matrix will be scrambled
  85                 //      by columns.
  86
  87                 if (irow != icol) {
  88                         for (l=1; l<=n; l++)
  89                                 SWAP(a[irow][l], a[icol][l]);
  90                         for (l=1; l<=m; l++)
  91                                 SWAP(b[irow][l], b[icol][l]);
  92                 }
  93
  94                 indxr[i] = irow;
  95                 indxc[i] = icol;
  96                 if (a[icol][icol] == 0) {
  97                         mprintf((0,"Error: Singular matrix-2\n"));
  98                         Int3();
  99                 }
 100                 pivinv = fixdiv(F1_0, a[icol][icol]);
 101                 a[icol][icol] = F1_0;
 102
 103                 for (l=1; l<=n; l++)
 104                         a[icol][l] = fixmul(a[icol][l], pivinv);
 105                 for (l=1; l<=m; l++)
 106                         b[icol][l] = fixmul(b[icol][l], pivinv);
 107
 108                 for (ll=1; ll<=n; ll++)
 109                         if (ll != icol) {
 110                                 dum = a[ll][icol];
 111                                 a[ll][icol] = 0;
 112                                 for (l=1; l<=n; l++)
 113                                         a[ll][l] -= a[icol][l]*dum;
 114                                 for (l=1; l<=m; l++)
 115                                         b[ll][l] -= b[icol][l]*dum;
 116                         }
 117         }
 118
 119         //      This is the end of the main loop over columns of the reduction.  It only remains to unscramble
 120         //      the solution in view of the column interchanges.  We do this by interchanging pairs of
 121         //      columns in the reverse order that the permutation was built up.
 122         for (l=n; l>=1; l--) {
 123                 if (indxr[l] != indxc[l])
 124                         for (k=1; k<=n; k++)
 125                                 SWAP(a[k][indxr[l]], a[k][indxc[l]]);
 126         }
 127
 128 }
 129
 130
 131 //      -----------------------------------------------------------------------------------------------------------------
 132 //      Return true if side is planar, else return false.
 133 int side_is_planar_p(segment *sp, int side)
 134 {
 135         sbyte                   *vp;
 136         vms_vector      *v0,*v1,*v2,*v3;
 137         vms_vector      va,vb;
 138
 139         vp = Side_to_verts[side];
 140         v0 = &Vertices[sp->verts[vp[0]]];
 141         v1 = &Vertices[sp->verts[vp[1]]];
 142         v2 = &Vertices[sp->verts[vp[2]]];
 143         v3 = &Vertices[sp->verts[vp[3]]];
 144
 145         vm_vec_normalize(vm_vec_normal(&va,v0,v1,v2));
 146         vm_vec_normalize(vm_vec_normal(&vb,v0,v2,v3));
 147
 148         // If the two vectors are very close to being the same, then generate one quad, else generate two triangles.
 149         return (vm_vec_dist(&va,&vb) < F1_0/1000);
 150 }
 151
 152 //      -------------------------------------------------------------------------------------------------
 153 //      Return coordinates of a vertex which is vertex v moved so that all sides of which it is a part become planar.
 154 void compute_planar_vert(segment *sp, int side, int v, vms_vector *vp)
 155 {
 156         if ((sp) && (side > -3))
 157                 *vp = Vertices[v];
 158 }
 159
 160 //      -------------------------------------------------------------------------------------------------
 161 //      Making Cursegp:Curside planar.
 162 //      If already planar, return.
 163 //      for each vertex v on side, not part of another segment
 164 //              choose the vertex v which can be moved to make all sides of which it is a part planar, minimizing distance moved
 165 //      if there is no vertex v on side, not part of another segment, give up in disgust
 166 //      Return value:
 167 //              0       curside made planar (or already was)
 168 //              1       did not make curside planar
 169 int make_curside_planar(void)
 170 {
 171         int                     v;
 172         sbyte                   *vp;
 173         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
 174         int                     present_verts[4];                       //      set to 1 if vertex is present
 175
 176         if (side_is_planar_p(Cursegp, Curside))
 177                 return 0;
 178
 179         //      Look at all vertices in side to find a free one.
 180         for (v=0; v<4; v++)
 181                 present_verts[v] = 0;
 182
 183         vp = Side_to_verts[Curside];
 184
 185         for (v=0; v<4; v++) {
 186                 int v1 = vp[v];         // absolute vertex id
 187                 if (is_free_vertex(Cursegp->verts[v1])) {
 188                         compute_planar_vert(Cursegp, Curside, Cursegp->verts[v1], &planar_verts[v]);
 189                         present_verts[v] = 1;
 190                 }
 191         }
 192
 193         //      Now, for each v for which present_verts[v] == 1, there is a vector (point) in planar_verts[v].
 194         //      See which one is closest to the plane defined by the other three points.
 195         //      Nah...just use the first one we find.
 196         for (v=0; v<4; v++)
 197                 if (present_verts[v]) {
 198                         med_set_vertex(vp[v],&planar_verts[v]);
 199                         validate_segment(Cursegp);
 200                         // -- should propagate tmaps to segments or something here...
 201
 202                         return 0;
 203                 }
 204         //      We tried, but we failed, to make Curside planer.
 205         return 1;
 206 }
 207