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