home *** CD-ROM | disk | FTP | other *** search
/ Quake 'em / QUAKEEM.BIN / doom_i / program / bsp11w.exe / PICKNODE.C < prev    next >
Encoding:
C/C++ Source or Header  |  1995-07-16  |  7.1 KB  |  213 lines
  1. /*- PICKNODE.C --------------------------------------------------------------*
  2.  To be able to divide the nodes down, this routine must decide which is the
  3.  best Seg to use as a nodeline. It does this by selecting the line with least
  4.  splits and has least difference of Segs on either side of it.
  5.  
  6.  Credit to Raphael Quinet and DEU, this routine is a copy of the nodeline
  7.  picker used in DEU5beta. I am using this method because the method I 
  8.  originally used was not so good.
  9.  
  10.  (Some stuff was optimized, check out 'picknode.old' for original code - Alex.)
  11. *---------------------------------------------------------------------------*/
  12. #include "prottype.h"
  13.  
  14. struct Seg *PickNode(struct Seg *ts)
  15. {
  16.     int num_splits,num_left,num_right;
  17.     int min_splits,min_diff,val;
  18.     struct Seg *part,*check,*best;
  19.     int max,new,grade = 0,bestgrade = 32767,seg_count;
  20.  
  21. //   min_splits = 32767;
  22. //   min_diff = 32767;
  23.    best = ts;                                    /* Set best to first (failsafe measure)*/
  24.  
  25.     for(part=ts;part;part = part->next)    /* Use each Seg as partition*/
  26.         {
  27.         progress();                                /* Something for the user to look at.*/
  28.         
  29.         psx = vertices[part->start].x;    /* Calculate this here, cos it doesn't*/
  30.         psy = vertices[part->start].y;    /* change for all the interations of*/
  31.         pex = vertices[part->end].x;        /* the inner loop!*/
  32.         pey = vertices[part->end].y;
  33.         pdx = psx - pex;            /* Partition line DX,DY*/
  34.         pdy = psy - pey;
  35.     
  36.         num_splits = 0;
  37.         num_left = 0;
  38.         num_right = 0;
  39.  
  40.         seg_count = 0;
  41.         for(check=ts;check;check=check->next)    /* Check partition against all Segs*/
  42.             {
  43.             seg_count++;
  44.             if(check == part) num_right++;        /* If same as partition, inc right count*/
  45.             else
  46.                 {
  47.                 lsx = vertices[check->start].x;    /* Calculate this here, cos it doesn't*/
  48.                 lsy = vertices[check->start].y;    /* change for all the interations of*/
  49.                 lex = vertices[check->end].x;        /* the inner loop!*/
  50.                 ley = vertices[check->end].y;
  51.                 val = DoLinesIntersect();            /* get state of lines relation to each other*/
  52.                 if((val&2 && val&64) || (val&4 && val&32))
  53.                     {
  54.                     num_splits++;                        /* If line is split, inc splits*/
  55.                     num_left++;                            /* and add one line into both*/
  56.                     num_right++;                        /* sides*/
  57.                     }
  58.                 else
  59.                     {
  60.                     if(val&1 && val&16)                /* If line is totally in same*/
  61.                         {                                    /* direction*/
  62.                         if(check->flip == part->flip) num_right++;
  63.                         else num_left++;                /* add to side according to flip*/
  64.                         }
  65.                     else                                    /* So, now decide which side*/
  66.                         {                                    /* the line is on*/
  67.                         if(val&34) num_left++;        /* and inc the appropriate*/
  68.                         if(val&68) num_right++;        /* count*/
  69.                         }
  70.                     }
  71.                 }
  72. //            if(num_splits > min_splits) break;    /* If more splits than last, reject*/
  73.             }
  74.  
  75.         if(num_right > 0 && num_left > 0)        /* Make sure at least one Seg is*/
  76.             {                                                /* on either side of the partition*/
  77.             max = max(num_right,num_left);
  78.             new = (num_right + num_left) - seg_count;
  79.             grade = max+new*8;
  80.  
  81.             if(grade < bestgrade)
  82.                 {
  83.                 bestgrade = grade;
  84.                 best = part;                            /* and remember which Seg*/
  85.                 }
  86.             }
  87.         }
  88.     return best;                                        /* all finished, return best Seg*/
  89. }
  90.  
  91. /*---------------------------------------------------------------------------*
  92.  Because this is used a horrendous amount of times in the inner loops, the
  93.  coordinate of the lines are setup outside of the routine in global variables
  94.  psx,psy,pex,pey = partition line coordinates
  95.  lsx,lsy,lex,ley = checking line coordinates
  96.  The routine returns 'val' which has 3 bits assigned to the the start and 3
  97.  to the end. These allow a decent evaluation of the lines state.
  98.  bit 0,1,2 = checking lines starting point and bits 4,5,6 = end point
  99.  these bits mean     0,4 = point is on the same line
  100.             1,5 = point is to the left of the line
  101.             2,6 = point is to the right of the line
  102.  There are some failsafes in here, these mainly check for small errors in the
  103.  side checker.
  104.  
  105.  ( I made some changes here to eliminate sqrt() functions - Alex) 
  106. *---------------------------------------------------------------------------*/
  107.  
  108. int DoLinesIntersect()
  109. {
  110.     short int x,y,val = 0;
  111.  
  112.     long dx2,dy2,dx3,dy3,a,b;
  113.     
  114.     dx2 = psx - lsx;                                    /* Checking line -> partition*/
  115.     dy2 = psy - lsy;
  116.     dx3 = psx - lex;
  117.     dy3 = psy - ley;
  118.     
  119.     a = pdy*dx2 - pdx*dy2;
  120.     b = pdy*dx3 - pdx*dy3;
  121.  
  122.     if((a<0 && b>0) || (a>0 && b<0))   /* Line is split, just check that*/
  123.         {
  124.         ComputeIntersection(&x,&y);
  125.         dx2 = lsx - x;           /* Find distance from line start*/
  126.         dy2 = lsy - y;           /* to split point*/
  127.         if(dx2 == 0 && dy2 == 0) a = 0;
  128.         else
  129.             if( dx2*dx2 + dy2*dy2 < 4) a = 0;    
  130.                               /* If either ends of the split    */
  131.                            /* are smaller than 2 pixs then   */
  132.                            /* assume this starts on part line*/ 
  133.  
  134.         dx3 = lex - x;              /* Find distance from line end*/
  135.         dy3 = ley - y;            /* to split point*/
  136.         if(dx3 == 0 && dy3 == 0) b = 0;
  137.         else
  138.                     if ( dx3*dx3 + dy3*dy3 < 4) b = 0; 
  139.         }
  140.  
  141.     if(a == 0) val = val | 16;         /* start is on middle*/
  142.     if(a < 0) val  = val | 32;        /* start is on left side*/
  143.     if(a > 0) val  = val | 64;        /* start is on right side*/
  144.  
  145.     if(b == 0) val = val | 1;        /* end is on middle*/
  146.     if(b < 0) val  = val | 2;        /* end is on left side*/
  147.     if(b > 0) val  = val | 4;        /* end is on right side*/
  148.  
  149.     return val;
  150. }
  151.  
  152. /*---------------------------------------------------------------------------*
  153.  Calculate the point of intersection of two lines. ps?->pe? & ls?->le?
  154.  returns int xcoord, int ycoord
  155.  
  156.  ( Profiling revealed that this was most time-consuming routine here
  157.    so I rewrote it completly and new one is more than 2 times faster
  158.    than previous (w/o coprocessor) - Alex)
  159. *---------------------------------------------------------------------------*/
  160.  
  161. void _fastcall ComputeIntersection(short int *outx,short int *outy)
  162. {
  163.  /* Now, algorithm is based on solving the system of 2 linear equaltions of
  164.     given lines  - Alex*/
  165.  
  166.     double X,Y, a1,b1,a2;
  167.     long   dx1,dy1,dx2,dy2;
  168.  
  169.     dx1 = (long)pex - psx;
  170.     dy1 = (long)pey - psy;
  171.     dx2 = (long)lex - lsx;
  172.     dy2 = (long)ley - lsy;
  173.  
  174.     if( (!dx1 && !dy1) || (!dx2 && !dy2) ) 
  175.                               ProgError("Invalid line encountered");
  176.  
  177.     if( !dx1 && !dy2) { *outx = psx; *outy = lsy; return; }
  178.  
  179.     if( !dy1 && !dx2) { *outx = lsx; *outy = psy; return; }
  180.  
  181.     if( !dx1 || !dx2)
  182.       {
  183.          a1 = (double)((long)pex-psx)/((long)pey-psy);
  184.          a2 = (double)((long)lex-lsx)/((long)ley-lsy);
  185.  
  186.          if( a1 == a2 ) { *outx = lsx; *outy = lsy;  return; }
  187.  
  188.          b1 = psx - a1*psy;
  189.          X = (lsx - a2*lsy - b1)/(a1-a2);
  190.          Y = a1*X + b1;
  191.  
  192.         *outx = (int)(Y + ((Y<0)?-0.5:0.5));
  193.         *outy = (int)(X + ((X<0)?-0.5:0.5));
  194.       }
  195.     else
  196.       {
  197.          a1 = (double)((long)pey-psy)/((long)pex-psx);
  198.          a2 = (double)((long)ley-lsy)/((long)lex-lsx);
  199.  
  200.          if( a1 == a2 ) { *outx = lsx; *outy = lsy;  return; }
  201.  
  202.          b1 = psy - a1*psx;
  203.          X = (lsy - a2*lsx - b1)/(a1-a2);
  204.          Y = a1*X + b1;
  205.  
  206.         *outx = (short int)(X + ((X<0)?-0.5:0.5));
  207.         *outy = (short int)(Y + ((Y<0)?-0.5:0.5));
  208.       }
  209. }
  210.  
  211. /*--------------------------------------------------------------------------*/
  212.  
  213.