home *** CD-ROM | disk | FTP | other *** search
/ WADS of WADS / WadsOfWads.1994.zip / OTHER / DOOMBSP / BUILDBSP.M next >
Text File  |  1994-04-06  |  10KB  |  528 lines
  1. #import "doombsp.h"
  2.  
  3. // I assume that a grid 8 is used for the maps, so a point will be considered
  4. // on a line if it is within 8 pixels of it.  The accounts for floating error.
  5.  
  6. int        cuts;            // number of new lines generated by BSP process
  7.  
  8. /*
  9. ==================
  10. =
  11. = DivlineFromWorldline
  12. =
  13. ==================
  14. */
  15.  
  16. void    DivlineFromWorldline (divline_t *d, line_t *w)
  17. {
  18.     d->pt = w->p1;
  19.     d->dx = w->p2.x - w->p1.x;
  20.     d->dy = w->p2.y - w->p1.y;
  21. }
  22.  
  23. /*
  24. ==================
  25. =
  26. = PointOnSide
  27. =
  28. = Returns side 0 (front), 1 (back), or -1 (colinear)
  29. ==================
  30. */
  31.  
  32. int    PointOnSide (NXPoint *p, divline_t *l)
  33. {
  34.     float    dx,dy;
  35.     float    left, right;
  36.     float    a,b,c,d;
  37.     
  38.     if (!l->dx)
  39.     {
  40.         if (p->x > l->pt.x-2 && p->x < l->pt.x+2)
  41.             return -1;
  42.         if (p->x < l->pt.x)
  43.             return l->dy > 0;
  44.         return l->dy < 0;
  45.     }
  46.     if (!l->dy)
  47.     {
  48.         if (p->y > l->pt.y-2 && p->y < l->pt.y+2)
  49.             return -1;
  50.         if (p->y < l->pt.y)
  51.             return l->dx < 0;
  52.         return l->dx > 0;
  53.     }
  54.  
  55.     dx = l->pt.x - p->x;
  56.     dy = l->pt.y - p->y;
  57.     a = l->dx*l->dx + l->dy*l->dy;
  58.     b = 2*(l->dx*dx + l->dy*dy);
  59.     c = dx*dx+dy*dy - 2*2;        // 2 unit radius
  60.     d = b*b - 4*a*c;
  61.     if (d>0)
  62.         return -1;        // within four pixels of line
  63.     
  64.     
  65.     dx = p->x - l->pt.x;
  66.     dy = p->y - l->pt.y;
  67.     
  68.     left = l->dy * dx;
  69.     right = dy * l->dx;
  70.     
  71.     if ( fabs (left-right) < 0.5 )    // allow slop
  72.         return -1;        // on line
  73.     if (right < left)
  74.         return 0;        // front side
  75.     return 1;            // back side
  76. }
  77.  
  78. /*
  79. =============
  80. =
  81. = sign
  82. =
  83. = Returns -1, 0, or 1, based on the input sign
  84. =
  85. ==============
  86. */
  87.  
  88. int sign (float i)
  89. {
  90.     if (i<0)
  91.         return -1;
  92.     else if (i>0)
  93.         return 1;
  94.     return 0;
  95. }
  96.  
  97. /*
  98. ==================
  99. =
  100. = LineOnSide
  101. =
  102. = Returns side 0 / 1, or -2 if line must be split
  103. = If the line is colinear, it will be placed on the front side if
  104. = it is going the same direction as the dividing line
  105. ==================
  106. */
  107.  
  108. boolean    LineOnSide (line_t *wl, divline_t *bl)
  109. {
  110.     int        s1,s2;
  111.     float    dx, dy;
  112.     
  113.     s1 = PointOnSide (&wl->p1, bl);
  114.     s2 = PointOnSide (&wl->p2, bl);
  115.  
  116.     if (s1 == s2)
  117.     {
  118.         if (s1 == -1)
  119.         {    // colinear, so see if the directions are the same
  120.             dx = wl->p2.x - wl->p1.x;
  121.             dy = wl->p2.y - wl->p1.y;
  122.             if (sign(dx) == sign (bl->dx) && sign(dy) == sign(bl->dy) )
  123.                 return 0;
  124.             return 1;
  125.         }
  126.         return s1;
  127.     }
  128.     if (s1 == -1)
  129.         return s2;
  130.     if (s2 == -1)
  131.         return s1;
  132.         
  133.     return -2;
  134. }
  135.  
  136. /*
  137. ===============
  138. =
  139. = InterceptVector
  140. =
  141. = Returns the fractional intercept point along first vector
  142. ===============
  143. */
  144.  
  145. float InterceptVector (divline_t *v2, divline_t *v1)
  146. {
  147. #if 0
  148.  
  149. v1.x + f1*v1.xs = v2.x + f2*v2.xs    (parametric x coordinates)
  150. f1*v1.xs = v2.x - v1.x + f2*v2.xs
  151. f1 = (v2.x - v1.x +f2*v2.xs) / v1.xs
  152.  
  153. v1.y + f1*v1.ys = v2.y + f2*v2.ys    (parametric y coordinates)
  154. f1 = (v2.y - v1.y + f2*v2.ys) / v1.ys
  155.  
  156. f1 = (v2.x - v1.x +f2*v2.xs) / v1.xs = (v2.y - v1.y + f2*v2.ys) / v1.ys
  157. v1.ys*v2.x - v1.ys*v1.x + v1.ys*v2.xs*f2 = v1.xs*v2.y - v1.xs*v1.y + v1.xs*v2.ys*f2
  158. (v1.ys*v2.xs - v1.xs*v2.ys)*f2 = -v1.ys*v2.x + v1.ys*v1.x + v1.xs*v2.y - v1.xs*v1.y
  159.                             = v1.ys*(v1.x-v2.x) + v1.xs*(v2.y-v1.y)
  160.                             
  161. f2 = (v1.ys*(v1.x-v2.x) + v1.xs*(v2.y-v1.y)) / (v1.ys*v2.xs - v1.xs*v2.ys)
  162. #endif
  163.  
  164.     float    frac, num, den;
  165.     
  166.     den = v1->dy*v2->dx - v1->dx*v2->dy;
  167.     if (den == 0)
  168.         Error ("InterceptVector: parallel");
  169.     num = (v1->pt.x - v2->pt.x)*v1->dy + (v2->pt.y - v1->pt.y)*v1->dx;
  170.     frac = num / den;
  171.  
  172.     if (frac <= 0.0 || frac >= 1.0)
  173.         Error ("InterceptVector: intersection outside line");
  174.         
  175.     return frac;
  176. }
  177.  
  178.  
  179. /*
  180. ==================
  181. =
  182. = CutLine
  183. =
  184. = Truncates the given worldline to the front side of the divline
  185. = and returns the cut off back side in a newly allocated worldline
  186. ==================
  187. */
  188.  
  189. float round (float x)
  190. {
  191.     if (x>0)
  192.     {
  193.         if (x - (int)x < 0.1)
  194.             return (int)x;
  195.         else if (x - (int)x > 0.9)
  196.             return (int)x+1;
  197.         else
  198.             return x;
  199.     }
  200.     
  201.     if ((int)x - x < 0.1)
  202.         return (int)x;
  203.     else if ((int)x - x > 0.9)
  204.         return  (int)x - 1;
  205.     return x;
  206. }
  207.  
  208. line_t    *CutLine (line_t *wl, divline_t *bl)
  209. {
  210.     int            side;
  211.     line_t        *new_p;
  212.     divline_t    wld;
  213.     float        frac;
  214.     NXPoint        intr;
  215.     int            offset;
  216.     
  217.     cuts++;
  218.     DivlineFromWorldline (&wld, wl);
  219.     new_p = malloc (sizeof(line_t));
  220.     memset (new_p,0,sizeof(*new_p));
  221.     *new_p = *wl; 
  222.     
  223.     frac = InterceptVector (&wld, bl);
  224.     intr.x = wld.pt.x + round(wld.dx*frac);
  225.     intr.y = wld.pt.y + round(wld.dy*frac);
  226.     offset = wl->offset + round(frac*sqrt(wld.dx*wld.dx+wld.dy*wld.dy));
  227.     side = PointOnSide (&wl->p1, bl);
  228.     if (side == 0)
  229.     {    // line starts on front side
  230.         wl->p2 = intr;
  231.         new_p->p1 = intr;
  232.         new_p->offset = offset;
  233.     }
  234.     else
  235.     {    // line starts on back side
  236.         wl->p1 = intr;
  237.         wl->offset = offset;
  238.         new_p->p2 = intr;
  239.     }
  240.     
  241.     return new_p;
  242. }
  243.  
  244.  
  245. /*
  246. ================
  247. =
  248. = EvaluateSplit
  249. =
  250. = Returns a number grading the quality of a split along the givent line
  251. = for the current list of lines.  Evaluation is halted as soon as it is
  252. = determined that a better split already exists
  253. = 
  254. = A split is good if it divides the lines evenly without cutting many lines
  255. = A horizontal or vertical split is better than a sloping split
  256. =
  257. = The LOWER the returned value, the better.  If the split line does not divide
  258. = any of the lines at all, MAXINT will be returned
  259. ================
  260. */
  261.  
  262. int EvaluateSplit (id lines_i, line_t *spliton, int bestgrade)
  263. {
  264.     int                i,c,side;
  265.     line_t            *line_p;
  266.     divline_t        divline;
  267.     int                frontcount, backcount, max, new;
  268.     int                grade;
  269.     worldline_t        *wl;
  270.     
  271.     wl = [linestore_i elementAt: spliton->linedef];
  272. #if 0
  273.     if (wl->special == BSPSLIDEENDSPECIAL)
  274.         return MAXINT;    // NEVER split on this, because it moves
  275. #endif
  276.     DivlineFromWorldline (&divline, spliton);
  277.     
  278.     frontcount = backcount = 0;
  279.     c = [lines_i count];
  280.     grade = 0;
  281.         
  282.     for (i=0 ; i<c ; i++)
  283.     {
  284.         line_p = [lines_i elementAt:i];
  285.         if (line_p == spliton)
  286.             side = 0;
  287.         else
  288.             side = LineOnSide (line_p, &divline);
  289.         switch (side)
  290.         {
  291.         case 0:
  292.             frontcount++;
  293.             break;
  294.         case 1:
  295.             backcount++;
  296.             break;
  297.         case -2:
  298.             wl = [linestore_i elementAt: line_p->linedef];
  299. #if 0
  300.             if (wl->special == BSPSLIDESIDESPECIAL)
  301.                 return MAXINT;    // NEVER split this line, because it slides
  302. #endif
  303.             frontcount++;
  304.             backcount++;
  305.             break;
  306.         }
  307.         
  308.         max = MAX(frontcount,backcount);
  309.         new = (frontcount+backcount) - c;
  310.         grade = max+new*8;
  311.         if (grade > bestgrade)
  312.             return grade;        // might as well stop now
  313.     }
  314.     
  315.     if (frontcount == 0 || backcount == 0)
  316.         return MAXINT;            // line does not partition at all
  317.         
  318.     return grade;
  319. }
  320.  
  321.  
  322. /*
  323. ================
  324. =
  325. = ExecuteSplit
  326. =
  327. = Actually splits the line list as EvaluateLines predicted
  328. ================
  329. */
  330.  
  331. void ExecuteSplit (id lines_i, line_t *spliton
  332.     , id frontlist_i, id backlist_i)
  333. {
  334.     int                i,c,side;
  335.     line_t            *line_p, *newline_p;
  336.     divline_t        divline;
  337.     
  338.     DivlineFromWorldline (&divline, spliton);
  339.     DrawDivLine (&divline);
  340.     
  341.     c = [lines_i count];
  342.         
  343.     for (i=0 ; i<c ; i++)
  344.     {
  345.         line_p = [lines_i elementAt:i];
  346.         if (line_p == spliton)
  347.             side = 0;
  348.         else
  349.             side = LineOnSide (line_p, &divline);
  350.         switch (side)
  351.         {
  352.         case 0:
  353.             [frontlist_i addElement: line_p];
  354.             break;
  355.         case 1:
  356.             [backlist_i addElement: line_p];
  357.             break;
  358.         case -2:
  359.             newline_p = CutLine (line_p, &divline);
  360.             [frontlist_i addElement: line_p];
  361.             [backlist_i addElement: newline_p];
  362.             break;
  363.         default:
  364.             Error ("ExecuteSplit: bad side");
  365.         }
  366.     }
  367. }
  368.  
  369.  
  370. /*
  371. ================
  372. =
  373. = BSPList
  374. =
  375. = Takes a storage of lines and recursively partitions the list
  376. = Returns a bspnode_t
  377. ================
  378. */
  379.  
  380. float    gray = NX_WHITE;
  381.  
  382. bspnode_t *BSPList (id lines_i)
  383. {
  384.     id                frontlist_i, backlist_i;
  385.     int                i,c, step;
  386.     line_t            *line_p, *bestline_p;
  387.     int                v, bestv;
  388.     bspnode_t        *node_p;
  389.     
  390.     if (draw)
  391.         PSsetgray (gray);
  392.     gray = 1.0 - gray;
  393.     DrawLineStore (lines_i);
  394.     
  395.     node_p = malloc (sizeof(*node_p));
  396.     memset (node_p, 0, sizeof(*node_p));
  397.  
  398. //
  399. // find the best line to partition on 
  400. //
  401.     c = [lines_i count];
  402.     bestv = MAXINT;    
  403.     bestline_p = NULL;
  404.     step = (c/40)+1;        // set this to 1 for an exhaustive search
  405. research:
  406.     for (i=0 ; i<c ; i+=step)
  407.     {
  408.         line_p = [lines_i elementAt:i];
  409.         v = EvaluateSplit (lines_i, line_p, bestv);
  410.         if (v<bestv)
  411.         {
  412.             bestv = v;
  413.             bestline_p = line_p;
  414.         }
  415.     }
  416.     
  417. //
  418. // if none of the lines should be split, the remaining lines
  419. // are convex, and form a terminal node
  420. //
  421. //printf ("bestv:%i\n",bestv);
  422.  
  423.     if (bestv == MAXINT)
  424.     {
  425.         if (step > 1)
  426.         {    // possible to get here with non convex area if BSPSLIDE specials
  427.             // caused rejections
  428.             step = 1;
  429.             goto research;
  430.         }
  431.         node_p->lines_i = lines_i;
  432.         return node_p;
  433.     }
  434.     
  435. //
  436. // divide the line list into two nodes along the best split line
  437. //
  438.     DivlineFromWorldline (&node_p->divline, bestline_p);
  439.  
  440.     frontlist_i =
  441.     [[Storage alloc]
  442.         initCount:        0
  443.         elementSize:    sizeof(line_t)
  444.         description:    NULL];
  445.     backlist_i =
  446.     [[Storage alloc]
  447.         initCount:        0
  448.         elementSize:    sizeof(line_t)
  449.         description:    NULL];
  450.         
  451.     ExecuteSplit (lines_i, bestline_p, frontlist_i, backlist_i);
  452.  
  453. //
  454. // recursively divide the lists
  455. //
  456.     node_p->side[0] = BSPList (frontlist_i);
  457.     node_p->side[1] = BSPList (backlist_i);
  458.     
  459.     return node_p;
  460. }
  461.  
  462.  
  463.  
  464. /*
  465. =====================
  466. =
  467. = MakeSegs
  468. =
  469. =====================
  470. */
  471.  
  472. id segstore_i;
  473.  
  474. void MakeSegs (void)
  475. {
  476.     int                i, count;
  477.     worldline_t        *wl;
  478.     line_t            li;
  479.  
  480.     segstore_i =
  481.     [[Storage alloc]
  482.         initCount:        0
  483.         elementSize:    sizeof(line_t)
  484.         description:    NULL];
  485.     
  486.     count = [linestore_i count];
  487.     wl = [linestore_i elementAt:0];
  488.     for (i= 0 ; i<count ; i++, wl++)
  489.     {
  490.         li.p1 = wl->p1;
  491.         li.p2 = wl->p2;
  492.         li.linedef = i;
  493.         li.side = 0;
  494.         li.offset = 0;
  495.         li.grouped = false;
  496.         [segstore_i addElement: &li];
  497.         
  498.         if (wl->flags & ML_TWOSIDED)
  499.         {
  500.             li.p1 = wl->p2;
  501.             li.p2 = wl->p1;
  502.             li.linedef = i;
  503.             li.side = 1;
  504.             li.offset = 0;
  505.             li.grouped = false;
  506.             [segstore_i addElement: &li];
  507.         }
  508.     }        
  509. }
  510.  
  511.  
  512. /*
  513. =====================
  514. =
  515. = BuildBSP
  516. =
  517. =====================
  518. */
  519.  
  520. bspnode_t    *startnode;
  521.  
  522. void BuildBSP (void)
  523. {
  524.     MakeSegs ();
  525.     cuts = 0;
  526.     startnode = BSPList (segstore_i);
  527. }
  528.