home *** CD-ROM | disk | FTP | other *** search
/ Graphics Programming Black Book (Special Edition) / BlackBook.bin / disk1 / source / chapter60 / l60_1.cpp < prev    next >
Text File  |  1997-06-18  |  11KB  |  298 lines
  1. #define MAX_NUM_LINESEGS 1000
  2. #define MAX_INT          0x7FFFFFFF
  3. #define MATCH_TOLERANCE  0.00001
  4.  
  5. // A vertex
  6. typedef struct _VERTEX
  7. {
  8.    double x;
  9.    double y;
  10. } VERTEX;
  11.  
  12. // A potentially split piece of a line segment, as processed from the
  13. // base line in the original list
  14. typedef struct _LINESEG
  15. {
  16.    _LINESEG *pnextlineseg;
  17.     int startvertex;
  18.     int endvertex;
  19.     double walltop;
  20.     double wallbottom;
  21.     double tstart;
  22.     double tend;
  23.     int color;
  24.     _LINESEG *pfronttree;
  25.     _LINESEG *pbacktree;
  26. } LINESEG, *PLINESEG;
  27.  
  28. static VERTEX *pvertexlist;
  29. static int NumCompiledLinesegs = 0;
  30. static LINESEG *pCompiledLinesegs;
  31.  
  32.  
  33. // Builds a BSP tree from the specified line list. List must contain
  34. // at least one entry. If pCurrentTree is NULL, then this is the root
  35. // node, otherwise pCurrentTree is the tree that's been build so far.
  36. // Returns NULL for errors.
  37.  
  38. LINESEG * SelectBSPTree(LINESEG * plineseghead,
  39.     LINESEG * pCurrentTree, LINESEG ** pParentsChildPointer)
  40. {
  41.     LINESEG *pminsplit;
  42.     int minsplits;
  43.     int tempsplitcount;
  44.     LINESEG *prootline;
  45.     LINESEG *pcurrentline;
  46.     double nx, ny, numer, denom, t;
  47.  
  48.     // Pick a line as the root, and remove it from the list of lines
  49.     // to be categorized. The line we'll select is the one of those in
  50.     // the list that splits the fewest of the other lines in the list
  51.     minsplits = MAX_INT;
  52.     prootline = plineseghead;
  53.  
  54.     while (prootline != NULL) {
  55.         pcurrentline = plineseghead;
  56.         tempsplitcount = 0;
  57.  
  58.         while (pcurrentline != NULL) {
  59.  
  60.             // See how many other lines the current line splits
  61.             nx = pvertexlist[prootline->startvertex].y -
  62.                     pvertexlist[prootline->endvertex].y;
  63.             ny = -(pvertexlist[prootline->startvertex].x -
  64.                     pvertexlist[prootline->endvertex].x);
  65.  
  66.             // Calculate the dot products we'll need for line
  67.             // intersection and spatial relationship
  68.             numer = (nx * (pvertexlist[pcurrentline->startvertex].x -
  69.                     pvertexlist[prootline->startvertex].x)) +
  70.                     (ny * (pvertexlist[pcurrentline->startvertex].y -
  71.                     pvertexlist[prootline->startvertex].y));
  72.             denom = ((-nx) * (pvertexlist[pcurrentline->endvertex].x -
  73.                     pvertexlist[pcurrentline->startvertex].x)) +
  74.                     ((-ny) * (pvertexlist[pcurrentline->endvertex].y -
  75.                     pvertexlist[pcurrentline->startvertex].y));
  76.  
  77.             // Figure out if the infinite lines of the current line
  78.             // and the root intersect; if so, figure out if the
  79.             // current line segment is actually split, split if so,
  80.             // and add front/back polygons as appropriate
  81.             if (denom == 0.0) {
  82.                 // No intersection, because lines are parallel; no
  83.                 // split, so nothing to do
  84.             } else {
  85.                 // Infinite lines intersect; figure out whether the
  86.                 // actual line segment intersects the infinite line
  87.                 // of the root, and split if so
  88.                 t =  numer / denom;
  89.  
  90.                 if ((t > pcurrentline->tstart) &&
  91.                         (t < pcurrentline->tend)) {
  92.                     // The root splits the current line
  93.                     tempsplitcount++;
  94.                 } else {
  95.                     // Intersection outside segment limits, so no
  96.                     // split, nothing to do
  97.                 }
  98.             }
  99.  
  100.             pcurrentline = pcurrentline->pnextlineseg;
  101.         }
  102.  
  103.         if (tempsplitcount < minsplits) {
  104.             pminsplit = prootline;
  105.             minsplits = tempsplitcount;
  106.         }
  107.  
  108.         prootline = prootline->pnextlineseg;
  109.     }
  110.  
  111.     // For now, make this a leaf node so we can traverse the tree
  112.     // as it is at this point. BuildBSPTree() will add children as
  113.     // appropriate
  114.     pminsplit->pfronttree = NULL;
  115.     pminsplit->pbacktree = NULL;
  116.  
  117.     // Point the parent's child pointer to this node, so we can
  118.     // track the currently-build tree
  119.     *pParentsChildPointer = pminsplit;
  120.  
  121.     return BuildBSPTree(plineseghead, pminsplit, pCurrentTree);
  122. }
  123.  
  124. // Builds a BSP tree given the specified root, by creating front and
  125. // back lists from the remaining lines, and calling itself recursively
  126.  
  127. LINESEG * BuildBSPTree(LINESEG * plineseghead, LINESEG * prootline,
  128.     LINESEG * pCurrentTree)
  129. {
  130.     LINESEG *pfrontlines;
  131.     LINESEG *pbacklines;
  132.     LINESEG *pcurrentline;
  133.     LINESEG *pnextlineseg;
  134.     LINESEG *psplitline;
  135.     double nx, ny, numer, denom, t;
  136.     int Done;
  137.  
  138.     // Categorize all non-root lines as either in front of the root's
  139.     // infinite line, behind the root's infinite line, or split by the
  140.     // root's infinite line, in which case we split it into two lines
  141.     pfrontlines = NULL;
  142.     pbacklines = NULL;
  143.  
  144.     pcurrentline = plineseghead;
  145.  
  146.     while (pcurrentline != NULL)
  147.     {
  148.       // Skip the root line when encountered
  149.       if (pcurrentline == prootline) {
  150.         pcurrentline = pcurrentline->pnextlineseg;
  151.       } else  {
  152.         nx = pvertexlist[prootline->startvertex].y -
  153.                 pvertexlist[prootline->endvertex].y;
  154.         ny = -(pvertexlist[prootline->startvertex].x -
  155.                 pvertexlist[prootline->endvertex].x);
  156.  
  157.         // Calculate the dot products we'll need for line intersection
  158.         // and spatial relationship
  159.         numer = (nx * (pvertexlist[pcurrentline->startvertex].x -
  160.                  pvertexlist[prootline->startvertex].x)) +
  161.                 (ny * (pvertexlist[pcurrentline->startvertex].y -
  162.                  pvertexlist[prootline->startvertex].y));
  163.         denom = ((-nx) * (pvertexlist[pcurrentline->endvertex].x -
  164.                  pvertexlist[pcurrentline->startvertex].x)) +
  165.                 (-(ny) * (pvertexlist[pcurrentline->endvertex].y -
  166.                  pvertexlist[pcurrentline->startvertex].y));
  167.  
  168.         // Figure out if the infinite lines of the current line and
  169.         // the root intersect; if so, figure out if the current line
  170.         // segment is actually split, split if so, and add front/back
  171.         // polygons as appropriate
  172.         if (denom == 0.0) {
  173.             // No intersection, because lines are parallel; just add
  174.             // to appropriate list
  175.             pnextlineseg = pcurrentline->pnextlineseg;
  176.  
  177.             if (numer < 0.0) {
  178.                 // Current line is in front of root line; link into
  179.                 // front list
  180.                 pcurrentline->pnextlineseg = pfrontlines;
  181.                 pfrontlines = pcurrentline;
  182.             } else {
  183.                 // Current line behind root line; link into back list
  184.                 pcurrentline->pnextlineseg = pbacklines;
  185.                 pbacklines = pcurrentline;
  186.             }
  187.  
  188.             pcurrentline = pnextlineseg;
  189.         } else {
  190.             // Infinite lines intersect; figure out whether the actual
  191.             // line segment intersects the infinite line of the root,
  192.             // and split if so
  193.             t =  numer / denom;
  194.  
  195.             if ((t > pcurrentline->tstart) &&
  196.                     (t < pcurrentline->tend)) {
  197.                 // The line segment must be split; add one split
  198.                 // segment to each list
  199.                 if (NumCompiledLinesegs > (MAX_NUM_LINESEGS - 1)) {
  200.                     DisplayMessageBox("Out of space for line segs; "
  201.                                  "increase MAX_NUM_LINESEGS");
  202.                     return NULL;
  203.                 }
  204.  
  205.                 // Make a new line entry for the split part of line
  206.                 psplitline = &pCompiledLinesegs[NumCompiledLinesegs];
  207.                 NumCompiledLinesegs++;
  208.  
  209.                 *psplitline = *pcurrentline;
  210.                 psplitline->tstart = t;
  211.                 pcurrentline->tend = t;
  212.                 
  213.                 pnextlineseg = pcurrentline->pnextlineseg;
  214.  
  215.                 if (numer < 0.0) {
  216.                     // Presplit part is in front of root line; link
  217.                     // into front list and put postsplit part in back
  218.                     // list
  219.                     pcurrentline->pnextlineseg = pfrontlines;
  220.                     pfrontlines = pcurrentline;
  221.  
  222.                     psplitline->pnextlineseg = pbacklines;
  223.                     pbacklines = psplitline;
  224.                 } else {
  225.                     // Presplit part is in back of root line; link
  226.                     // into back list and put postsplit part in front
  227.                     // list
  228.                     psplitline->pnextlineseg = pfrontlines;
  229.                     pfrontlines = psplitline;
  230.  
  231.                     pcurrentline->pnextlineseg = pbacklines;
  232.                     pbacklines = pcurrentline;
  233.                 }
  234.  
  235.                 pcurrentline = pnextlineseg;
  236.             } else {
  237.                 // Intersection outside segment limits, so no need to
  238.                 // split; just add to proper list
  239.                 pnextlineseg = pcurrentline->pnextlineseg;
  240.  
  241.                 Done = 0;
  242.                 while (!Done) {
  243.                     if (numer < -MATCH_TOLERANCE) {
  244.                         // Current line is in front of root line;
  245.                         // link into front list
  246.                         pcurrentline->pnextlineseg = pfrontlines;
  247.                         pfrontlines = pcurrentline;
  248.                         Done = 1;
  249.                     } else if (numer > MATCH_TOLERANCE) {
  250.                         // Current line is behind root line; link
  251.                         // into back list
  252.                         pcurrentline->pnextlineseg = pbacklines;
  253.                         pbacklines = pcurrentline;
  254.                         Done = 1;
  255.                     } else {
  256.                         // The point on the current line we picked to
  257.                         // do front/back evaluation happens to be
  258.                         // collinear with the root, so use the other
  259.                         // end of the current line and try again
  260.                         numer =
  261.                             (nx *
  262.                              (pvertexlist[pcurrentline->endvertex].x -
  263.                               pvertexlist[prootline->startvertex].x))+
  264.                             (ny *
  265.                              (pvertexlist[pcurrentline->endvertex].y -
  266.                               pvertexlist[prootline->startvertex].y));
  267.                     }
  268.                 }
  269.  
  270.                 pcurrentline = pnextlineseg;
  271.             }
  272.         }
  273.       }
  274.     }
  275.  
  276.     // Make a node out of the root line, with the front and back trees
  277.     // attached
  278.     if (pfrontlines == NULL) {
  279.         prootline->pfronttree = NULL;
  280.     } else {
  281.         if (!SelectBSPTree(pfrontlines, pCurrentTree,
  282.                           &prootline->pfronttree)) {
  283.             return NULL;
  284.         }
  285.     }
  286.  
  287.     if (pbacklines == NULL) {
  288.         prootline->pbacktree = NULL;
  289.     } else {
  290.         if (!SelectBSPTree(pbacklines, pCurrentTree,
  291.                           &prootline->pbacktree)) {
  292.             return NULL;
  293.         }
  294.     }
  295.  
  296.     return(prootline);
  297. }
  298.