home *** CD-ROM | disk | FTP | other *** search
/ Quake 'em / QUAKEEM.BIN / quake / programs / readmap / brush.c next >
Encoding:
C/C++ Source or Header  |  1996-08-29  |  12.0 KB  |  560 lines
  1. /*-------------------------------------------------------------------------
  2. File    : brush.c
  3. Author  : John Carmack (id Software) and C. Newham.
  4. Version : 1.0
  5. Date    : 96/08/29
  6.  
  7. Description
  8. -----------
  9. Creates the brush windings.  ie: works out the polygons from the
  10. planes specified in the MAP file, determines the vertices and
  11. calculates texture scaling.
  12.  
  13. Comments
  14. --------
  15. freeWindings doesn't free memory as in the original.
  16. -------------------------------------------------------------------------*/
  17.  
  18. #include <stdio.h>
  19. #include <math.h>
  20. #include "brush.h"
  21. #include "io.h"
  22.  
  23.  
  24. /*--------------------------------------
  25. TextureAxisFromPlane
  26. --------------------------------------*/
  27. float TextureAxisFromPlane(plane_t *pln, float *xv, float *yv)
  28. {
  29.   int     bestaxis;
  30.   float   dot,best;
  31.   int     i;
  32.  
  33.   best = 0;
  34.   bestaxis = 0;
  35.  
  36.   for (i=0 ; i<6 ; i++)
  37.   {
  38.     dot = DotProduct (pln->normal, baseaxis[i*3]);
  39.     if (dot > best)
  40.     {
  41.       best = dot;
  42.       bestaxis = i;
  43.     }
  44.   }
  45.  
  46.   VectorCopy (baseaxis[bestaxis*3+1], xv);
  47.   VectorCopy (baseaxis[bestaxis*3+2], yv);
  48.  
  49.   return lightaxis[bestaxis>>1];
  50. }
  51.  
  52.  
  53.  
  54. /*--------------------------------------
  55. CheckFace
  56.  
  57. Note: this will not catch 0 area polygons
  58. --------------------------------------*/
  59. void CheckFace (face_t *f)
  60. {
  61.  int       i, j;
  62.  float     *p1, *p2;
  63.  float     d, edgedist;
  64.  vec3_t    dir, edgenormal;
  65.  winding_t *w;
  66.  
  67.  w = f->w;
  68.  if (!w)
  69.    Error (0, "CheckFace: no winding\n");
  70.  
  71.  if (w->numpoints < 3)
  72.    Error (0,"CheckFace: points < 3\n");
  73.  
  74.  for (i=0 ; i<w->numpoints ; i++)
  75.  {
  76.    p1 = w->points[i];
  77.  
  78.    for (j=0 ; j<3 ; j++)
  79.      if (p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE)
  80.        Error (0,"CheckFace: outside BOGUS_RANGE\n");
  81.  
  82.    j = i+1 == w->numpoints ? 0 : i+1;
  83.  
  84.    /* check the point is on the face plane */
  85.    d = DotProduct (p1, f->plane.normal) - f->plane.dist;
  86.  
  87.    if (d < -ON_EPSILON || d > ON_EPSILON)
  88.      Error (0,"CheckFace: point off plane\n");
  89.  
  90.    /* check the edge isn't degenerate */
  91.    p2 = w->points[j];
  92.    VectorSubtract (p2, p1, dir);
  93.  
  94.    if (VectorLength (dir) < ON_EPSILON)
  95.      Error (0,"CheckFace: degenerate edge\n");
  96.  
  97.    CrossProduct (f->plane.normal, dir, edgenormal);
  98.    VectorNormalize (edgenormal);
  99.    edgedist = DotProduct (p1, edgenormal);
  100.    edgedist += ON_EPSILON;
  101.  
  102.    /* all other points must be on front side */
  103.    for (j=0 ; j<w->numpoints ; j++)
  104.    {
  105.      if (j == i)
  106.        continue;
  107.      d = DotProduct (w->points[j], edgenormal);
  108.      if (d > edgedist)
  109.        Error (0,"CheckFace: non-convex");
  110.     }
  111.   }
  112. }
  113.  
  114.  
  115.  
  116. /*--------------------------------------
  117. NewWinding
  118. --------------------------------------*/
  119. winding_t *NewWinding (int points)
  120. {
  121.   winding_t       *w;
  122.   int             size;
  123.  
  124.   if (points > MAX_POINTS_ON_WINDING)
  125.     Error (0,"NewWinding: too many points\n");
  126.  
  127.   size = (int)((winding_t *)0)->points[points];
  128.   w = (winding_t *)malloc (size);
  129.   memset (w, 0, size);
  130.  
  131.   return w;
  132. }
  133.  
  134.  
  135. /*--------------------------------------
  136. --------------------------------------*/
  137. void freeWindings()
  138. {
  139.   int i;
  140.  
  141.   for (i=0 ; i<MAX_FACES ; i++)
  142.     if (faces[i].w)
  143.     {
  144.       /*free (faces[i].w);  MARK*/
  145.       faces[i].w = NULL;
  146.     }
  147. }
  148.  
  149.  
  150.  
  151. /*--------------------------------------
  152. BasePolyForPlane
  153.  
  154. There has GOT to be a better way of doing this...
  155. --------------------------------------*/
  156. winding_t *BasePolyForPlane (face_t *f)
  157. {
  158.   int             i, x;
  159.   float           max, v;
  160.   vec3_t          org, vright, vup;
  161.   vec3_t          xaxis, yaxis;
  162.   winding_t       *w;
  163.   texturedef_t    *td;
  164.   plane_t         *p;
  165.   float           ang, sinv, cosv;
  166.   float           s, t, ns, nt;
  167.  
  168.   p = &f->plane;
  169.  
  170.   /* find the major axis */
  171.  
  172.   max = -BOGUS_RANGE;
  173.   x = -1;
  174.   for (i=0 ; i<3; i++)
  175.   {
  176.     v = fabs(p->normal[i]);
  177.     if (v > max)
  178.     {
  179.       x = i;
  180.       max = v;
  181.     }
  182.   }
  183.  
  184.   if (x==-1)
  185.     Error (0,"BasePolyForPlane: no axis found");
  186.  
  187.     VectorCopy (vec3_origin, vup);
  188.     switch (x)
  189.     {
  190.       case 0:
  191.       case 1:
  192.         vup[2] = 1;
  193.         break;
  194.       case 2:
  195.         vup[0] = 1;
  196.         break;
  197.     }
  198.  
  199.     v = DotProduct (vup, p->normal);
  200.  
  201.     VectorMA (vup, -v, p->normal, vup);
  202.     VectorNormalize (vup);
  203.  
  204.     VectorScale (p->normal, p->dist, org);
  205.  
  206.     CrossProduct (vup, p->normal, vright);
  207.  
  208.     VectorScale (vup, 8192, vup);
  209.     VectorScale (vright, 8192, vright);
  210.  
  211.     /* project a really big axis aligned box onto the plane */
  212.     w = NewWinding (4);
  213.     w->numpoints = 4;
  214.  
  215.     VectorSubtract (org, vright, w->points[0]);
  216.     VectorAdd (w->points[0], vup, w->points[0]);
  217.  
  218.     VectorAdd (org, vright, w->points[1]);
  219.     VectorAdd (w->points[1], vup, w->points[1]);
  220.  
  221.     VectorAdd (org, vright, w->points[2]);
  222.     VectorSubtract (w->points[2], vup, w->points[2]);
  223.  
  224.     VectorSubtract (org, vright, w->points[3]);
  225.     VectorSubtract (w->points[3], vup, w->points[3]);
  226.  
  227.  
  228.     /* set texture values */
  229.     f->light = TextureAxisFromPlane(&f->plane, xaxis, yaxis);
  230.     td = &f->texture;
  231.  
  232.     /* rotate axis */
  233.     ang = td->rotate / 180 * M_PI;
  234.     sinv = sin(ang);
  235.     cosv = cos(ang);
  236.  
  237.     if (!td->scale[0])
  238.       td->scale[0] = 1;
  239.  
  240.     if (!td->scale[1])
  241.       td->scale[1] = 1;
  242.  
  243.     for (i=0 ; i<4 ; i++)
  244.     {
  245.       s = DotProduct (w->points[i], xaxis);
  246.       t = DotProduct (w->points[i], yaxis);
  247.  
  248.       ns = cosv * s - sinv * t;
  249.       nt = sinv * s +  cosv * t;
  250.  
  251.       w->points[i][3] = ns/td->scale[0] + td->shift[0];
  252.       w->points[i][4] = nt/td->scale[1] + td->shift[1];
  253.     }
  254.  
  255.  
  256.     return w;
  257. }
  258.  
  259.  
  260.  
  261.  
  262. /*--------------------------------------
  263. ClipWinding
  264.  
  265. Clips the winding to the plane, returning the new winding on the positive side
  266. Frees the input winding.
  267. --------------------------------------*/
  268. winding_t *ClipWinding (winding_t *in, plane_t *split)
  269. {
  270.   float           dists[MAX_POINTS_ON_WINDING];
  271.   int             sides[MAX_POINTS_ON_WINDING];
  272.   int             counts[3];
  273.   float           dot;
  274.   int             i, j;
  275.   float           *p1, *p2, *mid;
  276.   winding_t       *neww;
  277.   int             maxpts;
  278.  
  279.   counts[0] = counts[1] = counts[2] = 0;
  280.  
  281.   /* determine sides for each point */
  282.  
  283.   for (i=0 ; i<in->numpoints ; i++)
  284.   {
  285.     dot = DotProduct (in->points[i], split->normal);
  286.     dot -= split->dist;
  287.     dists[i] = dot;
  288.     if (dot > ON_EPSILON)
  289.       sides[i] = SIDE_FRONT;
  290.     else if (dot < -ON_EPSILON)
  291.       sides[i] = SIDE_BACK;
  292.     else
  293.     {
  294.       sides[i] = SIDE_ON;
  295.     }
  296.     counts[sides[i]]++;
  297.   }
  298.  
  299.   sides[i] = sides[0];
  300.   dists[i] = dists[0];
  301.  
  302.   if (!counts[0] && !counts[1])
  303.     return in;
  304.  
  305.   if (!counts[0])
  306.   {
  307.     free (in);
  308.     return NULL;
  309.   }
  310.  
  311.   if (!counts[1])
  312.     return in;
  313.  
  314.   maxpts = in->numpoints+4;   /* can't use counts[0]+2 because */
  315.                               /* of fp groupin */
  316.   neww = NewWinding (maxpts);
  317.  
  318.   for (i=0 ; i<in->numpoints ; i++)
  319.   {
  320.     p1 = in->points[i];
  321.  
  322.     mid = neww->points[neww->numpoints];
  323.  
  324.     if (sides[i] == SIDE_FRONT || sides[i] == SIDE_ON)
  325.     {
  326.       VectorCopy (p1, mid);
  327.       mid[3] = p1[3];
  328.       mid[4] = p1[4];
  329.       neww->numpoints++;
  330.       if (sides[i] == SIDE_ON)
  331.         continue;
  332.       mid = neww->points[neww->numpoints];
  333.     }
  334.  
  335.     if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
  336.       continue;
  337.  
  338.     /* generate a split point */
  339.     if (i == in->numpoints - 1)
  340.       p2 = in->points[0];
  341.     else
  342.       p2 = p1 + 5;
  343.  
  344.     neww->numpoints++;
  345.  
  346.     dot = dists[i] / (dists[i]-dists[i+1]);
  347.  
  348.     for (j=0 ; j<3 ; j++)
  349.     {
  350.       /* avoid round off error when possible */
  351.       if (split->normal[j] == 1)
  352.         mid[j] = split->dist;
  353.       else if (split->normal[j] == -1)
  354.         mid[j] = -split->dist;
  355.  
  356.       mid[j] = p1[j] + dot*(p2[j]-p1[j]);
  357.      }
  358.  
  359.      mid[3] = p1[3] + dot*(p2[3]-p1[3]);
  360.      mid[4] = p1[4] + dot*(p2[4]-p1[4]);
  361.    }
  362.  
  363.    if (neww->numpoints > maxpts)
  364.      Error (0,"ClipWinding: points exceeded estimate");
  365.  
  366.    /* free the original winding */
  367.    free (in);
  368.  
  369.    return neww;
  370. }
  371.  
  372.  
  373. /*--------------------------------------
  374. calcWindings
  375.  
  376. recalc the faces and mins / maxs from the
  377. planes.
  378.  
  379. If a face has a NULL winding, it is an
  380. overconstraining plane and can be removed.
  381. --------------------------------------*/
  382. void calcWindings()
  383. {
  384.   int                     i,j, k;
  385.   float                   v;
  386.   face_t                  *f;
  387.   winding_t               *w;
  388.   plane_t                 plane;
  389.   vec3_t                  t1, t2, t3;
  390.   int                     useplane[MAX_FACES];
  391.  
  392.   bmins[0] = bmins[1] = bmins[2] = 99999;
  393.   bmaxs[0] = bmaxs[1] = bmaxs[2] = -99999;
  394.   invalid = FALSE;
  395.  
  396.   freeWindings();
  397.  
  398.   for (i=0 ; i<MAX_FACES ; i++)
  399.   {
  400.     f = &faces[i];
  401.  
  402.     /* calc a plane from the points */
  403.     for (j=0 ; j<3 ; j++)
  404.     {
  405.       t1[j] = f->planepts[0][j] - f->planepts[1][j];
  406.       t2[j] = f->planepts[2][j] - f->planepts[1][j];
  407.       t3[j] = f->planepts[1][j];
  408.     }
  409.  
  410.     CrossProduct(t1,t2, f->plane.normal);
  411.  
  412.     if (VectorCompare (f->plane.normal, vec3_origin))
  413.     {
  414.        useplane[i] = FALSE;
  415.        break;
  416.     }
  417.  
  418.     VectorNormalize (f->plane.normal);
  419.     f->plane.dist = DotProduct (t3, f->plane.normal);
  420.  
  421.     /* if the plane duplicates another plane, ignore it
  422.        (assume it is a brush being edited that will be fixed) */
  423.  
  424.     useplane[i] = TRUE;
  425.  
  426.     for (j=0 ; j< i ; j++)
  427.     {
  428.       if ( f->plane.normal[0] == faces[j].plane.normal[0]
  429.         && f->plane.normal[1] == faces[j].plane.normal[1]
  430.         && f->plane.normal[2] == faces[j].plane.normal[2]
  431.         && f->plane.dist == faces[j].plane.dist )
  432.       {
  433.         printf("Warning: duplicate plane detected!\n");
  434.         useplane[i] = FALSE;
  435.         break;
  436.       }
  437.     }
  438.   }
  439.  
  440.   for (i=0 ; i<numfaces ; i++)
  441.   {
  442.     if (!useplane[i])
  443.       continue;                       /* duplicate plane */
  444.  
  445.     f = &faces[i];
  446.  
  447.     w = BasePolyForPlane (f);
  448.  
  449.     for (j=0 ; j<numfaces && w ; j++)
  450.     {
  451.       if (j == i)
  452.         continue;
  453.  
  454.       /* flip the plane, because we want to keep the back side */
  455.  
  456.       VectorSubtract (vec3_origin, faces[j].plane.normal, plane.normal);
  457.       plane.dist = -faces[j].plane.dist;
  458.  
  459.       w = ClipWinding (w, &plane);
  460.     }
  461.  
  462.     f->w = w;
  463.  
  464.     if (w)
  465.     {
  466.       CheckFace (f);
  467.       for (j=0 ; j<w->numpoints ; j++)
  468.       {
  469.         for (k=0 ; k<3 ; k++)
  470.         {
  471.           v = w->points[j][k];
  472.  
  473.           if (fabs(v - rint(v)) < FP_EPSILON)
  474.             v = w->points[j][k] = rint(v);
  475.             if (v < bmins[k])
  476.               bmins[k] = v;
  477.             if (v > bmaxs[k])
  478.               bmaxs[k] = v;
  479.         }
  480.       }
  481.     }
  482.   }
  483.  
  484.   if (bmins[0] == 99999)
  485.   {
  486.     invalid = TRUE;
  487.     VectorCopy (vec3_origin, bmins);
  488.     VectorCopy (vec3_origin, bmaxs);
  489.  
  490.   }
  491.  
  492. }
  493.  
  494.  
  495.  
  496. /*--------------------------------------
  497. Read a Brush
  498. --------------------------------------*/
  499. void ReadBrush (char *token, int *scriptline, char *dat, int *location)
  500. {
  501.   face_t  *f;
  502.   int     i,j;
  503.  
  504. printf (">>read brush\n");
  505.  
  506.   f = faces;
  507.   numfaces = 0;
  508.  
  509.   while (1)
  510.   {
  511.     if (!GetToken(TRUE, token, scriptline, dat, location))
  512.       break;
  513.     if (!strcmp (token, "}") )
  514.       break;
  515.  
  516.     for (i=0 ; i<3 ; i++)
  517.     {
  518.       if (i != 0)
  519.         /* get opening bracket of the vertex def */
  520.         GetToken(TRUE, token, scriptline, dat, location);
  521.         if (strcmp (token, "(") )
  522.           Error (*scriptline, "parsing map file - missing (\n");
  523.  
  524.           for (j=0 ; j<3 ; j++)
  525.           {
  526.             /* get the 3 values that define a vertex */
  527.             GetToken(FALSE, token, scriptline, dat, location);
  528.             f->planepts[i][j] = atoi(token);
  529.           }
  530.  
  531.           /* get the closing bracket of the vertex def */
  532.           GetToken(FALSE, token, scriptline, dat, location);
  533.           if (strcmp (token, ")") )
  534.             Error (*scriptline, "parsing map file - missing )");
  535.     }
  536.  
  537.     GetToken(FALSE, token, scriptline, dat, location);
  538.     strcpy (f->texture.texture, token);
  539.     GetToken(FALSE, token, scriptline, dat, location);
  540.     f->texture.shift[0] = atof(token);
  541.     GetToken(FALSE, token, scriptline, dat, location);
  542.     f->texture.shift[1] = atof(token);
  543.     GetToken(FALSE, token, scriptline, dat, location);
  544.     f->texture.rotate = atof(token);
  545.     GetToken(FALSE, token, scriptline, dat, location);
  546.     f->texture.scale[0] = atof(token);
  547.     GetToken(FALSE, token, scriptline, dat, location);
  548.     f->texture.scale[1] = atof(token);
  549.  
  550.  
  551.     f++;
  552.     numfaces++;
  553.   }
  554.  
  555.   calcWindings();
  556.  
  557. }
  558.  
  559.  
  560.