main/editor/fixseg.c

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