home *** CD-ROM | disk | FTP | other *** search
/ Doom 2 Explosion / Doom2Explosion.bin / doom2exp / programs / ibsp101s / buildbsp.c next >
C/C++ Source or Header  |  1994-07-10  |  16KB  |  720 lines
  1. #include "idbsp.h"
  2.  
  3. /*
  4.    I assume that a grid 8 is used for the maps, so a point will be considered
  5.    on a line if it is within 8 pixels of it.  The accounts for floating error.
  6.  */
  7.  
  8. int                 cuts;        /* number of new lines generated by BSP process */
  9.  
  10. /*
  11.    ==================
  12.    =
  13.    = DivlineFromWorldline
  14.    =
  15.    ==================
  16.  */
  17.  
  18. void                DivlineFromWorldline(divline_t * d, line_t * w)
  19. {
  20.     d -> pt = w -> p1;
  21.     d -> dx = w -> p2.x - w -> p1.x;
  22.     d -> dy = w -> p2.y - w -> p1.y;
  23. }
  24.  
  25. /*
  26.    ==================
  27.    =
  28.    = PointOnSide
  29.    =
  30.    = Returns side 0 (front), 1 (back), or -1 (colinear)
  31.    ==================
  32.  */
  33.  
  34. /*
  35.     #define POS_RADIUS   2.0         // original
  36.  
  37.     sometimes a radius of 1.5 has produced better results.
  38. */
  39.  
  40. #define POS_RADIUS    2.0
  41. #define NEWPOS
  42.  
  43. int                 PointOnSideTol(NXPoint * p, divline_t * l, double Tol)
  44. {
  45.     int                 retval;
  46.  
  47. #ifdef NEWPOS
  48.     float               y;
  49. #else
  50.     float               dx,
  51.                         dy;
  52.     float               left,
  53.                         right;
  54.     float               a,
  55.                         b,
  56.                         c,
  57.                         d;
  58.  
  59. #endif
  60.  
  61.  
  62.  
  63. #ifdef NEWPOS
  64.     y = ((p -> y - l -> pt.y) * l -> dx - (p -> x - l -> pt.x) * l -> dy) /
  65.         sqrt(l -> dx * l -> dx + l -> dy * l -> dy);
  66.  
  67.     if (fabs(y) < Tol)
  68.         retval = -1;
  69.     else
  70.         retval = (y < 0.0) ? 0 : 1;
  71. #else
  72.     if (!l -> dx)
  73.         {
  74.         if (p -> x > (l -> pt.x - Tol) && p -> x < (l -> pt.x + Tol))
  75.             retval = -1;
  76.         else
  77.             {
  78.             if (p -> x < l -> pt.x)
  79.                 retval = l -> dy > 0;
  80.             else
  81.                 retval = l -> dy < 0;
  82.             }
  83.         }
  84.     else if (!l -> dy)
  85.         {
  86.         if (p -> y > (l -> pt.y - Tol) && p -> y < (l -> pt.y + Tol))
  87.             retval = -1;
  88.         else
  89.             {
  90.             if (p -> y < l -> pt.y)
  91.                 retval = l -> dx < 0;
  92.             else
  93.                 retval = l -> dx > 0;
  94.             }
  95.         }
  96.     else
  97.         {
  98.  
  99.         dx = l -> pt.x - p -> x;
  100.         dy = l -> pt.y - p -> y;
  101.         a = l -> dx * l -> dx + l -> dy * l -> dy;
  102.         b = 2 * (l -> dx * dx + l -> dy * dy);
  103.         c = dx * dx + dy * dy - (POS_RADIUS * POS_RADIUS);
  104.         d = b * b - 4 * a * c;
  105.  
  106.         if (d > 0)
  107.             retval = -1;
  108.         else
  109.             {
  110.             dx = p -> x - l -> pt.x;
  111.             dy = p -> y - l -> pt.y;
  112.  
  113.             left = l -> dy * dx;
  114.             right = dy * l -> dx;
  115.  
  116.             if (fabs(left - right) < 0.5)
  117.                 retval = -1;           /* on line */
  118.             else
  119.                 {
  120.                 if (right < left)
  121.                     retval = 0;           /* front side */
  122.                 else
  123.                     retval = 1;           /* back side */
  124.                 }
  125.             }
  126.         }
  127. #endif
  128.  
  129. /*if (myval != retval)
  130.    {
  131.    printf("\nPOS: line (% 5g, % 5g) - % 5g, % 5g: pt (% 5g, % 5g): me % d: JC % d:\n",
  132.    l->pt.x, l->pt.y, l->dx, l->dy, p->x, p->y, myval, retval);
  133.    } */
  134. /*return myval; */
  135.     return retval;
  136. }
  137.  
  138. int                 PointOnSide(NXPoint * p, divline_t * l)
  139. {
  140.     return PointOnSideTol(p, l, POS_RADIUS);
  141. }
  142.  
  143. /*
  144.    =============
  145.    =
  146.    = sign
  147.    =
  148.    = Returns -1, 0, or 1, based on the input sign
  149.    =
  150.    ==============
  151.  */
  152.  
  153. int                 sign(float i)
  154. {
  155.     if (i < 0)
  156.         return -1;
  157.     else if (i > 0)
  158.         return 1;
  159.     return 0;
  160. }
  161.  
  162. /*
  163.    ==================
  164.    =
  165.    = LineOnSide
  166.    =
  167.    = Returns side 0 / 1, or -2 if line must be split
  168.    = If the line is colinear, it will be placed on the front side if
  169.    = it is going the same direction as the dividing line
  170.    ==================
  171.  */
  172.  
  173. #define NEWLOS
  174.  
  175. boolean             LineOnSide(line_t * wl, divline_t * bl)
  176. {
  177.     int                 s1,
  178.                         s2;
  179.     float               dx,
  180.                         dy;
  181.  
  182.     s1 = PointOnSide(&wl -> p1, bl);
  183.     s2 = PointOnSide(&wl -> p2, bl);
  184.  
  185.     if (s1 == s2)
  186.         {
  187.         if (s1 == -1)
  188.             {                           /* colinear, so see if the directions are the same */
  189.             dx = wl -> p2.x - wl -> p1.x;
  190.             dy = wl -> p2.y - wl -> p1.y;
  191.  
  192. #ifdef NEWLOS
  193.             if (((bl -> dx * dx + bl -> dy * dy) / sqrt(dx * dx + dy * dy)) > 0.0)
  194. #else
  195.             if (sign(dx) == sign(bl -> dx) && sign(dy) == sign(bl -> dy))
  196. #endif
  197.  
  198.                 return 0;
  199.             return 1;
  200.             }
  201.         return s1;
  202.         }
  203.     if (s1 == -1)
  204.         return s2;
  205.     if (s2 == -1)
  206.         return s1;
  207.  
  208.     return -2;
  209. }
  210.  
  211. /*
  212.    ===============
  213.    =
  214.    = InterceptVector
  215.    =
  216.    = Returns the fractional intercept point along first vector
  217.    ===============
  218.  */
  219.  
  220. double              InterceptVector(divline_t * v2, divline_t * v1)
  221. {
  222.  
  223. #if 0
  224.     v1.x + f1 * v1.xs = v2.x + f2 * v2.xs(parametric x coordinates)
  225.         f1                 *v1.xs = v2.x - v1.x + f2 * v2.xs
  226.     f1 = (v2.x - v1.x + f2 * v2.xs) / v1.xs
  227.  
  228.     v1.y + f1 * v1.ys = v2.y + f2 * v2.ys(parametric y coordinates)
  229.     f1 = (v2.y - v1.y + f2 * v2.ys) / v1.ys
  230.  
  231.     f1 = (v2.x - v1.x + f2 * v2.xs) / v1.xs = (v2.y - v1.y + f2 * v2.ys) / v1.ys
  232.     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
  233.     (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
  234.     = v1.ys * (v1.x - v2.x) + v1.xs * (v2.y - v1.y)
  235.  
  236.     f2 = (v1.ys * (v1.x - v2.x) + v1.xs * (v2.y - v1.y)) / (v1.ys * v2.xs - v1.xs * v2.ys)
  237. #endif
  238.  
  239.  
  240.     float frac,
  241.                         num,
  242.                         den;
  243.  
  244.  
  245.     den = v1 -> dy * v2 -> dx - v1 -> dx * v2 -> dy;
  246.     if (den == 0)
  247.         Error("InterceptVector: parallel");
  248.     num = (v1 -> pt.x - v2 -> pt.x) * v1 -> dy + (v2 -> pt.y - v1 -> pt.y) * v1 -> dx;
  249.     frac = num / den;
  250.  
  251.     if (frac <= 0.0 || frac >= 1.0)
  252.         Error("InterceptVector: intersection outside line");
  253.  
  254.     return frac;
  255. }
  256.  
  257.  
  258. /*
  259.    ==================
  260.    =
  261.    = CutLine
  262.    =
  263.    = Truncates the given worldline to the front side of the divline
  264.    = and returns the cut off back side in a newly allocated worldline
  265.    ==================
  266.  */
  267.  
  268. double              round(float x)
  269. {
  270.     if (x > 0)
  271.         {
  272.         if (x - (int)x < 0.1)
  273.             return (int)x;
  274.         else if (x - (int)x > 0.9)
  275.             return (int)x + 1;
  276.         else
  277.             return x;
  278.         }
  279.  
  280.     if ((int)x - x < 0.1)
  281.         return (int)x;
  282.     else if ((int)x - x > 0.9)
  283.         return (int)x - 1;
  284.     return x;
  285. }
  286.  
  287. line_t             *CutLine(line_t * wl, divline_t * bl)
  288. {
  289.     int                 side;
  290.     line_t             *new_p;
  291.     divline_t           wld;
  292.     float               frac;
  293.     NXPoint             intr;
  294.     int                 offset;
  295.     double              ndx,
  296.                         ndy;
  297.  
  298.     cuts++;
  299.     DivlineFromWorldline(&wld, wl);
  300.     new_p = (line_t *) malloc(sizeof(line_t));
  301.     memset(new_p, 0, sizeof(*new_p));
  302.     *new_p = *wl;
  303.  
  304.     frac = InterceptVector(&wld, bl);
  305.     ndx = floor((wld.dx * frac) + 0.5);
  306.     ndy = floor((wld.dy * frac) + 0.5);
  307.     intr.x = wld.pt.x + (int)ndx;
  308.     intr.y = wld.pt.y + (int)ndy;
  309.     offset = wl -> offset + (int)floor(sqrt(ndx * ndx + ndy * ndy) + 0.5);
  310.     side = PointOnSide(&wl -> p1, bl);
  311.     if (side == 0)
  312.         {                               /* line starts on front side */
  313.         wl -> p2 = intr;
  314.         new_p -> p1 = intr;
  315.         new_p -> offset = offset;
  316.         }
  317.     else
  318.         {                               /* line starts on back side */
  319.         wl -> p1 = intr;
  320.         wl -> offset = offset;
  321.         new_p -> p2 = intr;
  322.         }
  323.  
  324.     return new_p;
  325. }
  326.  
  327.  
  328. /*
  329.    ================
  330.    =
  331.    = EvaluateSplit
  332.    =
  333.    = Returns a number grading the quality of a split along the givent line
  334.    = for the current list of lines.  Evaluation is halted as soon as it is
  335.    = determined that a better split already exists
  336.    =
  337.    = A split is good if it divides the lines evenly without cutting many lines
  338.    = A horizontal or vertical split is better than a sloping split
  339.    =
  340.    = The LOWER the returned value, the better.  If the split line does not divide
  341.    = any of the lines at all, MAXINT will be returned
  342.    ================
  343.  */
  344.  
  345. /*int EvaluateSplit (id lines_i, line_t *spliton, int bestgrade)
  346.  */
  347. int                 EvaluateSplit(STORAGE * lines_i, line_t * spliton, int bestgrade)
  348. {
  349.     int                 i,
  350.                         c,
  351.                         side;
  352.     line_t             *line_p;
  353.     divline_t           divline;
  354.     int                 frontcount,
  355.                         backcount,
  356.                         max,
  357.                         new;
  358.     int                 grade;
  359.     worldline_t        *wl;
  360.  
  361. /*      wl = [linestore_i elementAt: spliton->linedef];
  362.  */
  363.     wl = (worldline_t *) linestore_i -> data + spliton -> linedef;
  364.  
  365. #if 0
  366.     if (wl -> special == BSPSLIDEENDSPECIAL)
  367.         return MAXINT;                   /* NEVER split on this, because it moves */
  368. #endif
  369.  
  370.     DivlineFromWorldline(&divline, spliton);
  371.  
  372.     frontcount = backcount = 0;
  373. /*      c = [lines_i count];
  374.  */
  375.     c = lines_i -> count;
  376.     grade = 0;
  377.  
  378.     for (i = 0; i < c; i++)
  379.         {
  380. /*              line_p = [lines_i elementAt:i];
  381.  */
  382.         line_p = (line_t *) lines_i -> data + i;
  383.         if (line_p == spliton)
  384.             side = 0;
  385.         else
  386.             side = LineOnSide(line_p, &divline);
  387.         switch (side)
  388.             {
  389.             case 0:
  390.             frontcount++;
  391.             break;
  392.             case 1:
  393.             backcount++;
  394.             break;
  395.             case -2:
  396. /*                      wl = [linestore_i elementAt: line_p->linedef];
  397.  */
  398.             wl = (worldline_t *) linestore_i -> data + line_p -> linedef;
  399.  
  400. #if 0
  401.             if (wl -> special == BSPSLIDESIDESPECIAL)
  402.                 return MAXINT;           /* NEVER split this line, because it slides */
  403. #endif
  404.  
  405.             frontcount++;
  406.             backcount++;
  407.             break;
  408.             }
  409.  
  410.         max = MAX(frontcount, backcount);
  411.         new = (frontcount + backcount) - c;
  412.         grade = max + new * 8;
  413.         if (grade > bestgrade)
  414.             return grade;               /* might as well stop now */
  415.         }
  416.  
  417.     if (frontcount == 0 || backcount == 0)
  418.         return INT_MAX;                   /* line does not partition at all */
  419.  
  420.     return grade;
  421. }
  422.  
  423.  
  424. /*
  425.    ================
  426.    =
  427.    = ExecuteSplit
  428.    =
  429.    = Actually splits the line list as EvaluateLines predicted
  430.    ================
  431.  */
  432. /*
  433.    void ExecuteSplit (id lines_i, line_t *spliton
  434.    , id frontlist_i, id backlist_i)
  435.  */
  436. void                ExecuteSplit(STORAGE * lines_i, line_t * spliton,
  437.     STORAGE * frontlist_i, STORAGE * backlist_i)
  438. {
  439.     int                 i,
  440.                         c,
  441.                         side;
  442.     line_t             *line_p,
  443.                        *newline_p;
  444.     divline_t           divline;
  445.  
  446.     DivlineFromWorldline(&divline, spliton);
  447.     DrawDivLine(&divline);
  448.  
  449. /*      c = [lines_i count];
  450.  */
  451.     c = lines_i -> count;
  452.  
  453.     for (i = 0; i < c; i++)
  454.         {
  455. /*              line_p = [lines_i elementAt:i];
  456.  */
  457.         line_p = (line_t *) lines_i -> data + i;
  458.         if (line_p == spliton)
  459.             side = 0;
  460.         else
  461.             side = LineOnSide(line_p, &divline);
  462.         switch (side)
  463.             {
  464.             case 0:
  465. /*                      [frontlist_i addElement: line_p];
  466.  */
  467.             memcpy((line_t *) frontlist_i -> data + frontlist_i -> count, line_p, sizeof(line_t));
  468.             frontlist_i -> count += 1;
  469.             frontlist_i -> data = (line_t *) realloc(frontlist_i -> data,
  470.                 sizeof(line_t) * (frontlist_i -> count + 1));
  471.             break;
  472.             case 1:
  473. /*                      [backlist_i addElement: line_p];
  474.  */
  475.             memcpy((line_t *) backlist_i -> data + backlist_i -> count, line_p, sizeof(line_t));
  476.             backlist_i -> count += 1;
  477.             backlist_i -> data = (line_t *) realloc(backlist_i -> data,
  478.                 sizeof(line_t) * (backlist_i -> count + 1));
  479.             break;
  480.             case -2:
  481.             newline_p = CutLine(line_p, &divline);
  482. /*                      [frontlist_i addElement: line_p];
  483.    [backlist_i addElement: newline_p];
  484.  */
  485.             memcpy((line_t *) frontlist_i -> data + frontlist_i -> count, line_p, sizeof(line_t));
  486.             frontlist_i -> count += 1;
  487.             frontlist_i -> data = (line_t *) realloc(frontlist_i -> data,
  488.                 sizeof(line_t) * (frontlist_i -> count + 1));
  489.  
  490.             memcpy((line_t *) backlist_i -> data + backlist_i -> count, newline_p, sizeof(line_t));
  491.             backlist_i -> count += 1;
  492.             backlist_i -> data = (line_t *) realloc(backlist_i -> data,
  493.                 sizeof(line_t) * (backlist_i -> count + 1));
  494.  
  495.             break;
  496.             default:
  497.             Error("ExecuteSplit: bad side");
  498.             }
  499.         }
  500. }
  501.  
  502.  
  503. /*
  504.    ================
  505.    =
  506.    = BSPList
  507.    =
  508.    = Takes a storage of lines and recursively partitions the list
  509.    = Returns a bspnode_t
  510.    ================
  511.  */
  512.  
  513. /* float        gray = NX_WHITE; */
  514. float               gray = 0;
  515.  
  516. /* bspnode_t *BSPList (id lines_i)
  517.  */
  518. bspnode_t          *BSPList(STORAGE * lines_i)
  519. {
  520. /*      id                              frontlist_i, backlist_i;
  521.  */
  522.     STORAGE            *frontlist_i,
  523.                        *backlist_i;
  524.     int                 i,
  525.                         c,
  526.                         step;
  527.     line_t             *line_p,
  528.                        *bestline_p;
  529.     int                 v,
  530.                         bestv;
  531.     bspnode_t          *node_p;
  532.  
  533. /*
  534.    if (draw)
  535.    PSsetgray (gray);
  536.    gray = 1.0 - gray;
  537.  */
  538.     DrawLineStore(lines_i);
  539.  
  540.     node_p = (bspnode_t *) malloc(sizeof(*node_p));
  541.     memset(node_p, 0, sizeof(*node_p));
  542.  
  543. /*
  544.    find the best line to partition on
  545.  */
  546.  
  547. /*      c = [lines_i count];
  548.  */
  549.  
  550.     c = lines_i -> count;
  551.     bestv = INT_MAX;
  552.     bestline_p = NULL;
  553.     step = (c / 40) + 1;               /* set this to 1 for an exhaustive search */
  554.   research:
  555.     for (i = 0; i < c; i += step)
  556.         {
  557. /*              line_p = [lines_i elementAt:i];
  558.  */
  559.         line_p = (line_t *) lines_i -> data + i;
  560.         v = EvaluateSplit(lines_i, line_p, bestv);
  561.         if (v < bestv)
  562.             {
  563.             bestv = v;
  564.             bestline_p = line_p;
  565.             }
  566.         }
  567.  
  568. /*
  569.    if none of the lines should be split, the remaining lines
  570.    are convex, and form a terminal node
  571.  */
  572. /*
  573.    printf ("bestv:%i\n",bestv);
  574.  */
  575.     if (bestv == INT_MAX)
  576.         {
  577.         if (step > 1)
  578.             {                           /* possible to get here with non convex area if BSPSLIDE specials
  579.                                           caused rejections */
  580.             step = 1;
  581.             goto research;
  582.             }
  583.         node_p -> lines_i = lines_i;
  584.         return node_p;
  585.         }
  586.  
  587. /*
  588.    divide the line list into two nodes along the best split line
  589.  */
  590.     DivlineFromWorldline(&node_p -> divline, bestline_p);
  591. /*
  592.    frontlist_i =
  593.    [[Storage alloc]
  594.    initCount:              0
  595.    elementSize:    sizeof(line_t)
  596.    description:    NULL];
  597.    backlist_i =
  598.    [[Storage alloc]
  599.    initCount:              0
  600.    elementSize:    sizeof(line_t)
  601.    description:    NULL];
  602.  */
  603.     frontlist_i = (STORAGE *) SafeMalloc(sizeof(STORAGE));
  604.     frontlist_i -> count = 0;
  605.     frontlist_i -> size = sizeof(line_t);
  606.     frontlist_i -> data = (line_t *) SafeMalloc(sizeof(line_t));
  607.  
  608.     backlist_i = (STORAGE *) SafeMalloc(sizeof(STORAGE));
  609.     backlist_i -> count = 0;
  610.     backlist_i -> size = sizeof(line_t);
  611.     backlist_i -> data = (line_t *) SafeMalloc(sizeof(line_t));
  612.  
  613.     ExecuteSplit(lines_i, bestline_p, frontlist_i, backlist_i);
  614.  
  615. /*
  616.    recursively divide the lists
  617.  */
  618.     node_p -> side[0] = BSPList(frontlist_i);
  619.     node_p -> side[1] = BSPList(backlist_i);
  620.  
  621.     return node_p;
  622. }
  623.  
  624.  
  625.  
  626. /*
  627.    =====================
  628.    =
  629.    = MakeSegs
  630.    =
  631.    =====================
  632.  */
  633.  
  634. /* id segstore_i;
  635.  */
  636. STORAGE            *segstore_i;
  637.  
  638. void                MakeSegs(void)
  639. {
  640.     int                 i,
  641.                         count;
  642.     worldline_t        *wl;
  643.  
  644. /* line_t   li;
  645.  */
  646.     line_t             *li;
  647.  
  648. /*
  649.    segstore_i =
  650.    [[Storage alloc]
  651.    initCount:              0
  652.    elementSize:    sizeof(line_t)
  653.    description:    NULL];
  654.  */
  655.     segstore_i = (STORAGE *) SafeMalloc(sizeof(STORAGE));
  656.     segstore_i -> data = (line_t *) SafeMalloc(sizeof(line_t));
  657.     segstore_i -> count = 0;
  658.     segstore_i -> size = sizeof(line_t);
  659.  
  660. /*
  661.    count = [linestore_i count];
  662.    wl = [linestore_i elementAt:0];
  663.  */
  664.     count = linestore_i -> count;
  665.     wl = linestore_i -> data;
  666.  
  667.     li = segstore_i -> data;
  668.  
  669.     for (i = 0; i < count; i++, wl++)
  670.         {
  671.         li -> p1 = wl -> p1;
  672.         li -> p2 = wl -> p2;
  673.         li -> linedef = i;
  674.         li -> side = 0;
  675.         li -> offset = 0;
  676.         li -> grouped = false;
  677.  
  678. /*              [segstore_i addElement: &li];
  679.  */
  680.         segstore_i -> count += 1;
  681.         segstore_i -> data = (line_t *) realloc(segstore_i -> data,
  682.             sizeof(line_t) * (segstore_i -> count + 1));
  683.         li = (line_t *) segstore_i -> data + segstore_i -> count;
  684.  
  685.         if (wl -> flags & ML_TWOSIDED)
  686.             {
  687.             li -> p1 = wl -> p2;
  688.             li -> p2 = wl -> p1;
  689.             li -> linedef = i;
  690.             li -> side = 1;
  691.             li -> offset = 0;
  692.             li -> grouped = false;
  693. /*                      [segstore_i addElement: &li];
  694.  */
  695.             segstore_i -> count += 1;
  696.             segstore_i -> data = (line_t *) realloc(segstore_i -> data,
  697.                 sizeof(line_t) * (segstore_i -> count + 1));
  698.             li = (line_t *) segstore_i -> data + segstore_i -> count;
  699.             }
  700.         }
  701. }
  702.  
  703.  
  704. /*
  705.    =====================
  706.    =
  707.    = BuildBSP
  708.    =
  709.    =====================
  710.  */
  711.  
  712. bspnode_t          *startnode;
  713.  
  714. void                BuildBSP(void)
  715. {
  716.     MakeSegs();
  717.     cuts = 0;
  718.     startnode = BSPList(segstore_i);
  719. }
  720.