Previous | Table of Contents | Next

Listing 60.1 L60_1.CPP

    #define MAX_NUM_LINESEGS 1000
    #define MAX_INT          0x7FFFFFFF
    #define MATCH_TOLERANCE  0.00001
    // A vertex
    typedef struct _VERTEX
    {
       double x;
       double y;
    } VERTEX;
    // A potentially split piece of a line segment, as processed from the
    // base line in the original list
    typedef struct _LINESEG
    {
       _LINESEG *pnextlineseg;
        int startvertex;
        int endvertex;
        double walltop;
        double wallbottom;
        double tstart;
        double tend;
        int color;
        _LINESEG *pfronttree;
        _LINESEG *pbacktree;
    } LINESEG, *PLINESEG;
    static VERTEX *pvertexlist;
    static int NumCompiledLinesegs = 0;
    static LINESEG *pCompiledLinesegs;
    // Builds a BSP tree from the specified line list. List must contain
    // at least one entry. If pCurrentTree is NULL, then this is the root
    // node, otherwise pCurrentTree is the tree that’s been build so far.
    // Returns NULL for errors.
    LINESEG * SelectBSPTree(LINESEG * plineseghead,
        LINESEG * pCurrentTree, LINESEG ** pParentsChildPointer)
    {
        LINESEG *pminsplit;
        int minsplits;
        int tempsplitcount;
        LINESEG *prootline;
        LINESEG *pcurrentline;
        double nx, ny, numer, denom, t;
        // Pick a line as the root, and remove it from the list of lines
        // to be categorized. The line we’ll select is the one of those in
        // the list that splits the fewest of the other lines in the list
        minsplits = MAX_INT;
        prootline = plineseghead;
        while (prootline != NULL) {
            pcurrentline = plineseghead;
            tempsplitcount = 0;
            while (pcurrentline != NULL) {
                // See how many other lines the current line splits
                nx = pvertexlist[prootline->startvertex].y -
                        pvertexlist[prootline->endvertex].y;
                ny = -(pvertexlist[prootline->startvertex].x -
                        pvertexlist[prootline->endvertex].x);
                // Calculate the dot products we’ll need for line
                // intersection and spatial relationship
                numer = (nx * (pvertexlist[pcurrentline->startvertex].x -
                        pvertexlist[prootline->startvertex].x)) +
                        (ny * (pvertexlist[pcurrentline->startvertex].y -
                        pvertexlist[prootline->startvertex].y));
                denom = ((-nx) * (pvertexlist[pcurrentline->endvertex].x -
                        pvertexlist[pcurrentline->startvertex].x)) +
                        ((-ny) * (pvertexlist[pcurrentline->endvertex].y -
                        pvertexlist[pcurrentline->startvertex].y));
                // Figure out if the infinite lines of the current line
                // and the root intersect; if so, figure out if the
                // current line segment is actually split, split if so,
                // and add front/back polygons as appropriate
                if (denom == 0.0) {
                    // No intersection, because lines are parallel; no
                    // split, so nothing to do
                } else {
                    // Infinite lines intersect; figure out whether the
                    // actual line segment intersects the infinite line
                    // of the root, and split if so
                    t =  numer / denom;
                    if ((t > pcurrentline->tstart) &&
                            (t < pcurrentline->tend)) {
                        // The root splits the current line
                        tempsplitcount++;
                    } else {
                        // Intersection outside segment limits, so no
                        // split, nothing to do
                    }
                }
                pcurrentline = pcurrentline->pnextlineseg;
            }
            if (tempsplitcount < minsplits) {
                pminsplit = prootline;
                minsplits = tempsplitcount;
            }
            prootline = prootline->pnextlineseg;
        }
        // For now, make this a leaf node so we can traverse the tree
        // as it is at this point. BuildBSPTree() will add children as
        // appropriate
        pminsplit->pfronttree = NULL;
        pminsplit->pbacktree = NULL;
        // Point the parent’s child pointer to this node, so we can
        // track the currently-build tree
        *pParentsChildPointer = pminsplit;
        return BuildBSPTree(plineseghead, pminsplit, pCurrentTree);
    }
    // Builds a BSP tree given the specified root, by creating front and
    // back lists from the remaining lines, and calling itself recursively
    LINESEG * BuildBSPTree(LINESEG * plineseghead, LINESEG * prootline,
        LINESEG * pCurrentTree)
    {
        LINESEG *pfrontlines;
        LINESEG *pbacklines;
        LINESEG *pcurrentline;
        LINESEG *pnextlineseg;
        LINESEG *psplitline;
        double nx, ny, numer, denom, t;
        int Done;
        // Categorize all non-root lines as either in front of the root’s
        // infinite line, behind the root’s infinite line, or split by the
        // root’s infinite line, in which case we split it into two lines
        pfrontlines = NULL;
        pbacklines = NULL;
        pcurrentline = plineseghead;
        while (pcurrentline != NULL)
        {
          // Skip the root line when encountered
          if (pcurrentline == prootline) {
            pcurrentline = pcurrentline->pnextlineseg;
          } else  {
            nx = pvertexlist[prootline->startvertex].y -
                    pvertexlist[prootline->endvertex].y;
            ny = -(pvertexlist[prootline->startvertex].x -
                    pvertexlist[prootline->endvertex].x);
            // Calculate the dot products we’ll need for line intersection
            // and spatial relationship
            numer = (nx * (pvertexlist[pcurrentline->startvertex].x -
                     pvertexlist[prootline->startvertex].x)) +
                    (ny * (pvertexlist[pcurrentline->startvertex].y -
                     pvertexlist[prootline->startvertex].y));
            denom = ((-nx) * (pvertexlist[pcurrentline->endvertex].x -
                     pvertexlist[pcurrentline->startvertex].x)) +
                    (-(ny) * (pvertexlist[pcurrentline->endvertex].y -
                     pvertexlist[pcurrentline->startvertex].y));
            // Figure out if the infinite lines of the current line and
            // the root intersect; if so, figure out if the current line
            // segment is actually split, split if so, and add front/back
            // polygons as appropriate
            if (denom == 0.0) {
                // No intersection, because lines are parallel; just add
                // to appropriate list
                pnextlineseg = pcurrentline->pnextlineseg;
                if (numer < 0.0) {
                    // Current line is in front of root line; link into
                    // front list
                    pcurrentline->pnextlineseg = pfrontlines;
                    pfrontlines = pcurrentline;
                } else {
                    // Current line behind root line; link into back list
                    pcurrentline->pnextlineseg = pbacklines;
                    pbacklines = pcurrentline;
                }
                pcurrentline = pnextlineseg;
            } else {
                // Infinite lines intersect; figure out whether the actual
                // line segment intersects the infinite line of the root,
                // and split if so
                t =  numer / denom;
                if ((t > pcurrentline->tstart) &&
                        (t < pcurrentline->tend)) {
                    // The line segment must be split; add one split
                    // segment to each list
                    if (NumCompiledLinesegs > (MAX_NUM_LINESEGS - 1)) {
                        DisplayMessageBox(“Out of space for line segs;”
                                     “increase MAX_NUM_LINESEGS”);
                        return NULL;
                    }
                    // Make a new line entry for the split part of line
                    psplitline = &pCompiledLinesegs[NumCompiledLinesegs];
                    NumCompiledLinesegs++;
                    *psplitline = *pcurrentline;
                    psplitline->tstart = t;
                    pcurrentline->tend = t;

                    pnextlineseg = pcurrentline->pnextlineseg;
                    if (numer < 0.0) {
                        // Presplit part is in front of root line; link
                        // into front list and put postsplit part in back
                        // list
                        pcurrentline->pnextlineseg = pfrontlines;
                        pfrontlines = pcurrentline;
                        psplitline->pnextlineseg = pbacklines;
                        pbacklines = psplitline;
                    } else {
                        // Presplit part is in back of root line; link
                        // into back list and put postsplit part in front
                        // list
                        psplitline->pnextlineseg = pfrontlines;
                        pfrontlines = psplitline;
                        pcurrentline->pnextlineseg = pbacklines;
                        pbacklines = pcurrentline;
                    }
                    pcurrentline = pnextlineseg;
                } else {
                    // Intersection outside segment limits, so no need to
                    // split; just add to proper list
                    pnextlineseg = pcurrentline->pnextlineseg;
                    Done = 0;
                    while (!Done) {
                        if (numer < -MATCH_TOLERANCE) {
                            // Current line is in front of root line;
                            // link into front list
                            pcurrentline->pnextlineseg = pfrontlines;
                            pfrontlines = pcurrentline;
                            Done = 1;
                        } else if (numer > MATCH_TOLERANCE) {
                            // Current line is behind root line; link
                            // into back list
                            pcurrentline->pnextlineseg = pbacklines;
                            pbacklines = pcurrentline;
                            Done = 1;
                        } else {
                            // The point on the current line we picked to
                            // do front/back evaluation happens to be
                            // collinear with the root, so use the other
                            // end of the current line and try again
                            numer =
                                (nx *
                                 (pvertexlist[pcurrentline->endvertex].x -
                                  pvertexlist[prootline->startvertex].x))+
                                (ny *
                                 (pvertexlist[pcurrentline->endvertex].y -
                                  pvertexlist[prootline->startvertex].y));
                        }
                    }
                    pcurrentline = pnextlineseg;
                }
            }
          }
        }
        // Make a node out of the root line, with the front and back trees
        // attached
        if (pfrontlines == NULL) {
            prootline->pfronttree = NULL;
        } else {
            if (!SelectBSPTree(pfrontlines, pCurrentTree,
                              &prootline->pfronttree)) {
                return NULL;
            }
        }
        if (pbacklines == NULL) {
            prootline->pbacktree = NULL;
        } else {
            if (!SelectBSPTree(pbacklines, pCurrentTree,
                              &prootline->pbacktree)) {
                return NULL;
            }
        }
        return(prootline);
    }

Previous | Table of Contents | Next

Graphics Programming Black Book © 2001 Michael Abrash