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