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