home *** CD-ROM | disk | FTP | other *** search
/ The Complete Doom Accessory Pack 2 / TheCompleteDoomAccessoryPackVolumeII.iso / editors / bspwin / picknode.old < prev    next >
Text File  |  1994-05-24  |  7KB  |  197 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. #include "prottype.h"
  11.  
  12. struct Seg *PickNode(struct Seg *ts)
  13. {
  14.     int num_splits,num_left,num_right;
  15.     int min_splits,min_diff,val;
  16.     struct Seg *part,*check,*best;
  17.     int max,new,grade = 0,bestgrade = 32767,seg_count;
  18.  
  19. //   min_splits = 32767;
  20. //   min_diff = 32767;
  21.    best = ts;                                    /* Set best to first (failsafe measure)*/
  22.  
  23.     for(part=ts;part;part = part->next)    /* Use each Seg as partition*/
  24.         {
  25.         progress();                                /* Something for the user to look at.*/
  26.         
  27.         psx = vertices[part->start].x;    /* Calculate this here, cos it doesn't*/
  28.         psy = vertices[part->start].y;    /* change for all the interations of*/
  29.         pex = vertices[part->end].x;        /* the inner loop!*/
  30.         pey = vertices[part->end].y;
  31.         pdx = psx - pex;            /* Partition line DX,DY*/
  32.         pdy = psy - pey;
  33.     
  34.         num_splits = 0;
  35.         num_left = 0;
  36.         num_right = 0;
  37.  
  38.         seg_count = 0;
  39.         for(check=ts;check;check=check->next)    /* Check partition against all Segs*/
  40.             {
  41.             seg_count++;
  42.             if(check == part) num_right++;        /* If same as partition, inc right count*/
  43.             else
  44.                 {
  45.                 lsx = vertices[check->start].x;    /* Calculate this here, cos it doesn't*/
  46.                 lsy = vertices[check->start].y;    /* change for all the interations of*/
  47.                 lex = vertices[check->end].x;        /* the inner loop!*/
  48.                 ley = vertices[check->end].y;
  49.                 val = DoLinesIntersect();            /* get state of lines relation to each other*/
  50.                 if((val&2 && val&64) || (val&4 && val&32))
  51.                     {
  52.                     num_splits++;                        /* If line is split, inc splits*/
  53.                     num_left++;                            /* and add one line into both*/
  54.                     num_right++;                        /* sides*/
  55.                     }
  56.                 else
  57.                     {
  58.                     if(val&1 && val&16)                /* If line is totally in same*/
  59.                         {                                    /* direction*/
  60.                         if(check->flip == part->flip) num_right++;
  61.                         else num_left++;                /* add to side according to flip*/
  62.                         }
  63.                     else                                    /* So, now decide which side*/
  64.                         {                                    /* the line is on*/
  65.                         if(val&34) num_left++;        /* and inc the appropriate*/
  66.                         if(val&68) num_right++;        /* count*/
  67.                         }
  68.                     }
  69.                 }
  70. //            if(num_splits > min_splits) break;    /* If more splits than last, reject*/
  71.             }
  72.  
  73.         if(num_right > 0 && num_left > 0)        /* Make sure at least one Seg is*/
  74.             {                                                /* on either side of the partition*/
  75.             max = max(num_right,num_left);
  76.             new = (num_right + num_left) - seg_count;
  77.             grade = max+new*8;
  78.  
  79.             if(grade < bestgrade)
  80.                 {
  81.                 bestgrade = grade;
  82.                 best = part;                            /* and remember which Seg*/
  83.                 }
  84.             }
  85.         }
  86.     return best;                                        /* all finished, return best Seg*/
  87. }
  88.  
  89. /*---------------------------------------------------------------------------*
  90.  Because this is used a horrendous amount of times in the inner loops, the
  91.  coordinate of the lines are setup outside of the routine in global variables
  92.  psx,psy,pex,pey = partition line coordinates
  93.  lsx,lsy,lex,ley = checking line coordinates
  94.  The routine returns 'val' which has 3 bits assigned to the the start and 3
  95.  to the end. These allow a decent evaluation of the lines state.
  96.  bit 0,1,2 = checking lines starting point and bits 4,5,6 = end point
  97.  these bits mean     0,4 = point is on the same line
  98.             1,5 = point is to the left of the line
  99.             2,6 = point is to the right of the line
  100.  There are some failsafes in here, these mainly check for small errors in the
  101.  side checker.
  102. *---------------------------------------------------------------------------*/
  103.  
  104. int DoLinesIntersect()
  105. {
  106.     short int x,y,val = 0;
  107.  
  108.     long dx2,dy2,dx3,dy3,a,b,l;
  109.     
  110.     dx2 = psx - lsx;                                    /* Checking line -> partition*/
  111.     dy2 = psy - lsy;
  112.     dx3 = psx - lex;
  113.     dy3 = psy - ley;
  114.     
  115.     a = pdy*dx2 - pdx*dy2;
  116.     b = pdy*dx3 - pdx*dy3;
  117.  
  118.     if((a<0 && b>0) || (a>0 && b<0))   /* Line is split, just check that*/
  119.         {
  120.         ComputeIntersection(&x,&y);
  121.         dx2 = lsx - x;           /* Find distance from line start*/
  122.         dy2 = lsy - y;           /* to split point*/
  123.         if(dx2 == 0 && dy2 == 0) a = 0;
  124.         else
  125.             {
  126.             l = (long)sqrt((float)((dx2*dx2)+(dy2*dy2)));
  127.                                       /* If either ends of the split    */
  128.             if(l < 2) a = 0;    /* are smaller than 2 pixs then   */
  129.             }            /* assume this starts on part line*/
  130.         dx3 = lex - x;              /* Find distance from line end*/
  131.         dy3 = ley - y;            /* to split point*/
  132.         if(dx3 == 0 && dy3 == 0) b = 0;
  133.         else
  134.             {
  135.             l = (long)sqrt((float)((dx3*dx3)+(dy3*dy3))); /* same as start of line*/
  136.             if(l < 2) b = 0;
  137.             }
  138.         }
  139.  
  140.     if(a == 0) val = val | 16;         /* start is on middle*/
  141.     if(a < 0) val = val | 32;        /* start is on left side*/
  142.     if(a > 0) val = val | 64;        /* start is on right side*/
  143.  
  144.     if(b == 0) val = val | 1;        /* end is on middle*/
  145.     if(b < 0) val = val | 2;        /* end is on left side*/
  146.     if(b > 0) val = val | 4;        /* end is on right side*/
  147.  
  148.     return val;
  149. }
  150.  
  151. /*---------------------------------------------------------------------------*
  152.  Calculate the point of intersection of two lines. ps?->pe? & ls?->le?
  153.  returns int xcoord, int ycoord
  154. *---------------------------------------------------------------------------*/
  155.  
  156. void ComputeIntersection(short int *outx,short int *outy)
  157. {
  158.     double a,b,a2,b2,l,l2,w,d,z;
  159.     
  160.     long dx,dy,dx2,dy2;
  161.  
  162.     dx = pex - psx;
  163.     dy = pey - psy;
  164.     dx2 = lex - lsx;
  165.     dy2 = ley - lsy;
  166.  
  167.     if(dx == 0 && dy == 0) ProgError("Trouble in ComputeIntersection dx,dy");
  168.     l = (long)sqrt((float)((dx*dx) + (dy*dy)));
  169.     if(dx2 == 0 && dy2 == 0) ProgError("Trouble in ComputeIntersection dx2,dy2");
  170.     l2 = (long)sqrt((float)((dx2*dx2) + (dy2*dy2)));
  171.     
  172.     a = dx / l;          /* Compute cosine of p line angle  ( cos(a1) ) */
  173.     b = dy / l;          /*           sine of p line angle  ( sin(a1) ) */
  174.     a2 = dx2 / l2;       /*         cosine of l line angle  ( cos(a2) ) */
  175.     b2 = dy2 / l2;       /*           sine of l line angle  ( sin(a2) ) */
  176.     d = b * a2 - a * b2; /*           sine of difference    ( sin(a1-a2) ) */
  177.     w = lsx;
  178.     z = lsy;
  179.     if(d != 0.0)         /* if lines are not parralel... ( sin(a1-a2)!=0 ) */
  180.         {
  181.         w = (((a*(lsy-psy))+(b*(psx-lsx))) / d);
  182.     
  183. /*        printf("Intersection at (%f,%f)\n",x2+(a2*w),y2+(b2*w));*/
  184.     
  185.         a = lsx+(a2*w);
  186.         b = lsy+(b2*w);
  187.         modf((float)(a)+ ((a<0)?-0.5:0.5) ,&w);
  188.         modf((float)(b)+ ((b<0)?-0.5:0.5) ,&z);
  189.         }
  190.     
  191.     *outx = w;
  192.     *outy = z;
  193. }
  194.  
  195. /*--------------------------------------------------------------------------*/
  196.  
  197.