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