home *** CD-ROM | disk | FTP | other *** search
/ Most Wanted 2 / MostWantedII.iso / doomutil / dooms / deu / source / nodes.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-04-26  |  20.0 KB  |  597 lines
  1. /*
  2.    Nodes builder by Raphaël Quinet <quinet@montefiore.ulg.ac.be>
  3.  
  4.    You are allowed to use any parts of this code in another program, as
  5.    long as you give credits to the authors in the documentation and in
  6.    the program itself.  Read the file README.1ST for more information.
  7.  
  8.    This program comes with absolutely no warranty.
  9.  
  10.    *------- PLEASE READ THE COMMENT AT THE END OF THIS FILE. -------*
  11.    | If you use the algorithm or even some of the ideas taken from  |
  12.    | this file, you must put a message in your program, so that the |
  13.    | user knows that all or part of the algorithm comes from DEU.   |
  14.    *------- PLEASE READ THE COMMENT AT THE END OF THIS FILE. -------*
  15.  
  16.    NODES.C - automatic builder for Nodes, Segs and SSectors.
  17. */
  18.  
  19. /* the includes */
  20. #include "deu.h"
  21. #include "levels.h"
  22.  
  23.  
  24.  
  25. /*
  26.    display some informations while the user is waiting
  27. */
  28.  
  29. void ShowProgress( int objtype)
  30. {
  31.    static int SavedNumVertexes = 0;
  32.    static int NumErrors = 0;
  33.  
  34.    if (UseMouse)
  35.       HideMousePointer();
  36.    switch (objtype)
  37.    {
  38.    case OBJ_VERTEXES:
  39.       DrawScreenBox3D( 0, 0, 203, 22);
  40.       DrawScreenText( 10, 8, "Number of Vertices: %d", NumVertexes);
  41.       break;
  42.    case OBJ_SIDEDEFS:
  43.       DrawScreenBox3D( 0, 30, 203, 52);
  44.       DrawScreenText( 10, 38, "Number of SideDefs: %d", NumSideDefs);
  45.       SavedNumVertexes = NumVertexes;
  46.       NumErrors = 0;
  47.       break;
  48.    case OBJ_SSECTORS:
  49.       DrawScreenBox3D( 0, 60, 203, 92);
  50.       DrawScreenText( 10, 68, "Number of Segs:     %d", NumSegs);
  51.       DrawScreenText( 10, 78, "Number of SSectors: %d", NumSSectors);
  52.       DrawScreenMeter( 225, 28, ScrMaxX - 10, 48, (float) NumSegs / (float) (NumSideDefs + NumVertexes - SavedNumVertexes));
  53.       break;
  54.    default:
  55.       NumErrors++;
  56.       DrawScreenBox3D( 0, 100, 203, 122);
  57.       SetColor( RED);
  58.       DrawScreenText( 10, 108, "Number of warnings: %d", NumErrors);
  59.       Beep();
  60.       break;
  61.    }
  62.    if (UseMouse)
  63.       ShowMousePointer();
  64. }
  65.  
  66.  
  67.  
  68. /*
  69.    find the point of intersection for two lines
  70. */
  71.  
  72. Bool ComputeIntersection( int *x, int *y, SEPtr seg1, SEPtr seg2) /* SWAP - needs Vertexes */
  73. {
  74.    /* floating-point required because long integers cause errors */
  75.    double x1  = Vertexes[ seg1->start].x;
  76.    double y1  = Vertexes[ seg1->start].y;
  77.    double dx1 = Vertexes[ seg1->end].x - Vertexes[ seg1->start].x;
  78.    double dy1 = Vertexes[ seg1->end].y - Vertexes[ seg1->start].y;
  79.    double x2  = Vertexes[ seg2->start].x;
  80.    double y2  = Vertexes[ seg2->start].y;
  81.    double dx2 = Vertexes[ seg2->end].x - Vertexes[ seg2->start].x;
  82.    double dy2 = Vertexes[ seg2->end].y - Vertexes[ seg2->start].y;
  83.    double d;
  84.  
  85.    d = dy1 * dx2 - dx1 * dy2;
  86.    if (d != 0.0)
  87.    {
  88.       x1 = y1 * dx1 - x1 * dy1;
  89.       x2 = y2 * dx2 - x2 * dy2;
  90.       /* (*x, *y) = intersection */
  91.       *x = (int) ((dx1 * x2 - dx2 * x1) / d);
  92.       *y = (int) ((dy1 * x2 - dy2 * x1) / d);
  93.       /* check if the intersection is not at one end of a Seg (vertex grid = 8*8) */
  94.       if ((*x < Vertexes[ seg1->start].x - 7 || *x > Vertexes[ seg1->start].x + 7 || *y < Vertexes[ seg1->start].y - 7 || *y > Vertexes[ seg1->start].y + 7)
  95.        && (*x < Vertexes[ seg1->end].x - 7   || *x > Vertexes[ seg1->end].x + 7   || *y < Vertexes[ seg1->end].y - 7   || *y > Vertexes[ seg1->end].y + 7  )
  96.        && (*x < Vertexes[ seg2->start].x - 7 || *x > Vertexes[ seg2->start].x + 7 || *y < Vertexes[ seg2->start].y - 7 || *y > Vertexes[ seg2->start].y + 7)
  97.        && (*x < Vertexes[ seg2->end].x - 7   || *x > Vertexes[ seg2->end].x + 7   || *y < Vertexes[ seg2->end].y - 7   || *y > Vertexes[ seg2->end].y + 7  ))
  98.      return TRUE; /* intersection OK */
  99.       else
  100.      return FALSE; /* not a real intersection point (round-off error in a previous operation) */
  101.    }
  102.    else
  103.       return FALSE; /* parallel lines */
  104. }
  105.  
  106.  
  107.  
  108. /*
  109.    choose a nodeline amongst the list of Segs
  110. */
  111.  
  112. SEPtr FindNodeLine( SEPtr seglist) /* SWAP - needs Vertexes */
  113. {
  114.    int   splits;
  115. #ifdef OLD_ALGORITHM
  116.    int   minsplits = 32767;
  117. #endif /* OLD_ALGORITHM */
  118.    int   mindiff = 32767;
  119.    int   num1, num2;
  120.    SEPtr nodeline, bestnodeline;
  121.    SEPtr curseg;
  122.    long  x, y;
  123.    long  dx, dy;
  124.    long  a, b, c, d;
  125.    /* ***DEBUG*** */
  126.    static SEPtr lastnodeline = NULL;
  127.  
  128.    /* find nodeline - brute force: try with all Segs */
  129.    bestnodeline = NULL;
  130.    for (nodeline = seglist; nodeline; nodeline = nodeline->next)
  131.    {
  132.       /* compute x, y, dx, dy */
  133.       x = Vertexes[ nodeline->start].x;
  134.       y = Vertexes[ nodeline->start].y;
  135.       dx = Vertexes[ nodeline->end].x - Vertexes[ nodeline->start].x;
  136.       dy = Vertexes[ nodeline->end].y - Vertexes[ nodeline->start].y;
  137.       /* compute number of splits */
  138.       if (dx == 0 || dy == 0)
  139.      splits = 0;
  140.       else
  141.      splits = 1; /* small penalty for oblique lines */
  142.       num1 = 0;
  143.       num2 = 0;
  144.       for (curseg = seglist; curseg; curseg = curseg->next)
  145.       {
  146.      if (curseg == nodeline)
  147.      {
  148.         num1++;
  149.         continue;
  150.      }
  151.      /* you love maths, don't you? */
  152.      a = ((long) Vertexes[ curseg->start].x - x) * dy;
  153.      b = ((long) Vertexes[ curseg->start].y - y) * dx;
  154.      c = ((long) Vertexes[ curseg->end].x - x) * dy;
  155.      d = ((long) Vertexes[ curseg->end].y - y) * dx;
  156.      if ((a != b) && (c != d) && ((a > b) != (c > d)))
  157.      {
  158.         int dummyx, dummyy;
  159.         /* we should have an intersection, but... */
  160.         /* check for round-off errors (intersection of long diagonal lines) */
  161.         if (ComputeIntersection( &dummyx, &dummyy, nodeline, curseg))
  162.         {
  163.            splits++; /* one more split */
  164.            num1++;
  165.            num2++;
  166.         }
  167.      }
  168.      else if ((a > b) || ((a == b) && (c > d))
  169.           || ((a == b) && (c == d) && ((dx > 0) == ((Vertexes[ curseg->end].x - Vertexes[ curseg->start].x) > 0)) && ((dy > 0) == ((Vertexes[ curseg->end].y - Vertexes[ curseg->start].y) > 0))))
  170.         num1++; /* one more Seg on the first (right) side */
  171.      else
  172.         num2++; /* one more Seg on the second (left) side */
  173. #ifdef OLD_ALGORITHM
  174.      if (splits > minsplits)
  175.         break;  /* don't waste time */
  176. #else
  177.      if (max( num1, num2) + 8 * splits > mindiff)
  178.         break;  /* don't waste time */
  179. #endif /* OLD_ALGORITHM */
  180.       }
  181.  
  182.       /* there must be at least one Seg on each side */
  183.       if (num1 > 0 && num2 > 0)
  184.       {
  185. #ifdef OLD_ALGORITHM
  186.      /* now, num1 = difference in number of Segs between two sides */
  187.      if (num1 > num2)
  188.         num1 = num1 - num2;
  189.      else
  190.         num1 = num2 - num1;
  191.      /* minimal number of splits = candidate for nodeline */
  192.      if (splits < minsplits || (splits == minsplits && num1 < mindiff))
  193.      {
  194.         minsplits = splits; /* minimal number of splits */
  195.         mindiff = num1; /* minimal difference between the two sides */
  196.         bestnodeline = nodeline; /* save the nodeline */
  197.      }
  198. #else
  199.      /* now, num1 = rating for this nodeline */
  200.      num1 = max( num1, num2) + 8 * splits;
  201.      /* this nodeline is better than the previous one */
  202.      if (num1 < mindiff)
  203.      {
  204.         mindiff = num1; /* save the rating */
  205.         bestnodeline = nodeline; /* save the nodeline */
  206.      }
  207. #endif /* OLD_ALGORITHM */
  208.       }
  209.    }
  210.  
  211.    /* ***DEBUG*** */
  212.    if (bestnodeline && bestnodeline == lastnodeline)
  213.       ProgError( "nodeline picked twice (this is a BUG!)");
  214.    lastnodeline = nodeline;
  215.  
  216.    return bestnodeline;
  217. }
  218.  
  219.  
  220.  
  221. /*
  222.    Move a Seg into a list and update the bounding box
  223. */
  224.  
  225. void StoreInSegList( SEPtr seg, SEPtr *seglist, SEPtr *slistend, NPtr node, int listnum, Bool updatebbox) /* SWAP - needs Vertexes */
  226. {
  227.    if (*seglist)
  228.    {
  229.       (*slistend)->next = seg;
  230.       *slistend = (*slistend)->next;
  231.    }
  232.    else
  233.    {
  234.       *seglist = seg;
  235.       *slistend = *seglist;
  236.    }
  237.    (*slistend)->next = NULL;
  238.  
  239.    if (updatebbox)
  240.    {
  241.       if (listnum == 1)
  242.       {
  243.      /* update minx1, miny1, maxx1, maxy1 */
  244.      if (Vertexes[ seg->start].x < node->minx1)
  245.         node->minx1 = Vertexes[ seg->start].x;
  246.      if (Vertexes[ seg->start].x > node->maxx1)
  247.         node->maxx1 = Vertexes[ seg->start].x;
  248.      if (Vertexes[ seg->start].y < node->miny1)
  249.         node->miny1 = Vertexes[ seg->start].y;
  250.      if (Vertexes[ seg->start].y > node->maxy1)
  251.         node->maxy1 = Vertexes[ seg->start].y;
  252.  
  253.      if (Vertexes[ seg->end].x < node->minx1)
  254.         node->minx1 = Vertexes[ seg->end].x;
  255.      if (Vertexes[ seg->end].x > node->maxx1)
  256.         node->maxx1 = Vertexes[ seg->end].x;
  257.      if (Vertexes[ seg->end].y < node->miny1)
  258.         node->miny1 = Vertexes[ seg->end].y;
  259.      if (Vertexes[ seg->end].y > node->maxy1)
  260.         node->maxy1 = Vertexes[ seg->end].y;
  261.       }
  262.       else
  263.       {
  264.      /* update minx2, miny2, maxx2, maxy2 */
  265.      if (Vertexes[ seg->start].x < node->minx2)
  266.         node->minx2 = Vertexes[ seg->start].x;
  267.      if (Vertexes[ seg->start].x > node->maxx2)
  268.         node->maxx2 = Vertexes[ seg->start].x;
  269.      if (Vertexes[ seg->start].y < node->miny2)
  270.         node->miny2 = Vertexes[ seg->start].y;
  271.      if (Vertexes[ seg->start].y > node->maxy2)
  272.         node->maxy2 = Vertexes[ seg->start].y;
  273.  
  274.      if (Vertexes[ seg->end].x < node->minx2)
  275.         node->minx2 = Vertexes[ seg->end].x;
  276.      if (Vertexes[ seg->end].x > node->maxx2)
  277.         node->maxx2 = Vertexes[ seg->end].x;
  278.      if (Vertexes[ seg->end].y < node->miny2)
  279.         node->miny2 = Vertexes[ seg->end].y;
  280.      if (Vertexes[ seg->end].y > node->maxy2)
  281.         node->maxy2 = Vertexes[ seg->end].y;
  282.       }
  283.    }
  284. }
  285.  
  286.  
  287.  
  288. /*
  289.    check if a list of Segs should be divided in smaller parts (by a nodeline)
  290. */
  291.  
  292. Bool NeedFurtherDivision( SEPtr seglist) /* SWAP! */
  293. {
  294.    SEPtr curseg, refseg;
  295.    int   refsector;
  296.  
  297.    ObjectsNeeded( OBJ_LINEDEFS, OBJ_SIDEDEFS, 0);
  298.    /* the sector number must be the same for all Segs */
  299.    refseg = seglist;
  300.    if (refseg->flip)
  301.       refsector = SideDefs[ LineDefs[ refseg->linedef].sidedef2].sector;
  302.    else
  303.       refsector = SideDefs[ LineDefs[ refseg->linedef].sidedef1].sector;
  304.    for (curseg = seglist->next; curseg; curseg = curseg->next)
  305.    {
  306.       if (curseg->flip)
  307.       {
  308.      if (SideDefs[ LineDefs[ curseg->linedef].sidedef2].sector != refsector)
  309.      {
  310.         ObjectsNeeded( OBJ_VERTEXES, 0);
  311.         return TRUE;
  312.      }
  313.       }
  314.       else
  315.       {
  316.      if (SideDefs[ LineDefs[ curseg->linedef].sidedef1].sector != refsector)
  317.      {
  318.         ObjectsNeeded( OBJ_VERTEXES, 0);
  319.         return TRUE;
  320.      }
  321.       }
  322.    }
  323.  
  324.    /* the angle between two successive Segs must be <= 32767 */
  325.    /* check also for two-sided walls (start1 = end2 and end1 = start2) */
  326.    for (refseg = seglist; refseg; refseg = refseg->next)
  327.       for (curseg = seglist; curseg; curseg = curseg->next)
  328.      if (curseg->start == refseg->end && ((unsigned int) (refseg->angle - curseg->angle) > (unsigned int) 32767 || curseg->end == refseg->start))
  329.      {
  330.         ObjectsNeeded( OBJ_VERTEXES, 0);
  331.         return TRUE;
  332.      }
  333.  
  334.    /* no need to split the list: these Segs can be put in a SSector */
  335.    ObjectsNeeded( OBJ_VERTEXES, 0);
  336.    return FALSE;
  337. }
  338.  
  339.  
  340.  
  341. /*
  342.    create a SSector from a list of Segs
  343. */
  344.  
  345. int CreateSSector( SEPtr seglist)
  346. {
  347.    /* update the SSectors list */
  348.    NumSSectors++;
  349.    if (SSectors)
  350.    {
  351.       LastSSector->next = GetMemory( sizeof( struct SSector));
  352.       LastSSector = LastSSector->next;
  353.    }
  354.    else
  355.    {
  356.       SSectors = GetMemory( sizeof( struct SSector));
  357.       LastSSector = SSectors;
  358.    }
  359.    LastSSector->next = NULL;
  360.    /* number of first Segment in this SubSector */
  361.    LastSSector->first = NumSegs;
  362.    /* update the Segs list */
  363.    if (Segs == NULL)
  364.       Segs = seglist;
  365.    else
  366.       LastSeg->next = seglist;
  367.    NumSegs++;
  368.    for (LastSeg = seglist; LastSeg->next; LastSeg = LastSeg->next)
  369.       NumSegs++;
  370.    /* total number of Segments in this SubSector */
  371.    LastSSector->num = NumSegs - LastSSector->first;
  372.    /* while the user is waiting... */
  373.    ShowProgress( OBJ_SSECTORS);
  374.  
  375.    /* return the number of this SubSector */
  376.    return NumSSectors - 1;
  377. }
  378.  
  379.  
  380.  
  381. /*
  382.    create all Nodes from a list of Segs
  383. */
  384.  
  385. NPtr CreateNodes( SEPtr seglist) /* SWAP - needs Vertexes */
  386. {
  387.    NPtr         node;
  388.    SEPtr        segs1, segs2;
  389.    static SEPtr nodeline, curseg;
  390.    static long  a, b, c, d;
  391.    static SEPtr lastseg1, lastseg2;
  392.  
  393.    /* new Node */
  394.    node = GetMemory( sizeof( struct Node));
  395.  
  396.    /* reset bounding box limits */
  397.    node->maxx1 = -32768;
  398.    node->maxy1 = -32768;
  399.    node->minx1 = 32767;
  400.    node->miny1 = 32767;
  401.    node->maxx2 = -32768;
  402.    node->maxy2 = -32768;
  403.    node->minx2 = 32767;
  404.    node->miny2 = 32767;
  405.  
  406.    segs1 = NULL;
  407.    segs2 = NULL;
  408.  
  409.    /* find the best nodeline */
  410.    nodeline = FindNodeLine( seglist);
  411.  
  412.    /* special case: nodeline could not be found */
  413.    if (nodeline == NULL)
  414.    {
  415.       LogMessage( "\tNodeline could not be found.\n\t\tLineDefs in seglist:\n");
  416.       /* this only occurs when a Sector is not closed, */
  417.       /* or if there is only one Sector in the level.  */
  418.       nodeline = seglist;
  419.       curseg = seglist;
  420.       LogMessage( "\t\t%6d\n", curseg->linedef);
  421.       if (! IsSelected( errld, curseg->linedef))
  422.      SelectObject( &errld, curseg->linedef);
  423.       seglist = seglist->next;
  424.       StoreInSegList( curseg, &segs2, &lastseg2, node, 2, TRUE);
  425.       while (seglist)
  426.       {
  427.      curseg = seglist;
  428.      LogMessage( "\t\t%6d\n", curseg->linedef);
  429.      if (! IsSelected( errld, curseg->linedef))
  430.         SelectObject( &errld, curseg->linedef);
  431.      seglist = seglist->next;
  432.      StoreInSegList( curseg, &segs1, &lastseg1, node, 1, TRUE);
  433.       }
  434.       /* warn the user */
  435.       ShowProgress( -1);
  436.       LogMessage( "\n");
  437.    }
  438.  
  439.    /* compute x, y, dx, dy */
  440.    node->x = Vertexes[ nodeline->start].x;
  441.    node->y = Vertexes[ nodeline->start].y;
  442.    node->dx = Vertexes[ nodeline->end].x - Vertexes[ nodeline->start].x;
  443.    node->dy = Vertexes[ nodeline->end].y - Vertexes[ nodeline->start].y;
  444.  
  445.    /* split seglist in segs1 and segs2 */
  446.    while (seglist)
  447.    {
  448.       curseg = seglist;
  449.       seglist = seglist->next;
  450.       /* now, where is that old book about analytic geometry? */
  451.       a = (long) (Vertexes[ curseg->start].x - node->x) * (long) (node->dy);
  452.       b = (long) (Vertexes[ curseg->start].y - node->y) * (long) (node->dx);
  453.       c = (long) (Vertexes[ curseg->end].x - node->x) * (long) (node->dy);
  454.       d = (long) (Vertexes[ curseg->end].y - node->y) * (long) (node->dx);
  455.       /* check if starting vertex is on the right side of the nodeline, */
  456.       /* or if starting vertex is on the nodeline and ending vertex on the right side, */
  457.       /* or if both are on the nodeline and the Seg has the same orientation as the nodeline. */
  458.       if ((a > b) || ((a == b) && (c > d))
  459.       || ((a == b) && (c == d) && ((node->dx > 0) == ((Vertexes[ curseg->end].x - Vertexes[ curseg->start].x) > 0)) && ((node->dy > 0) == ((Vertexes[ curseg->end].y - Vertexes[ curseg->start].y) > 0))))
  460.       {
  461.      /* the starting Vertex is on the first side (right) of the nodeline */
  462.      StoreInSegList( curseg, &segs1, &lastseg1, node, 1, TRUE);
  463.      if (c < d)
  464.      {
  465.         int newx, newy;
  466.  
  467.         /* the ending Vertex is on the other side: split the Seg in two */
  468.         if (ComputeIntersection( &newx, &newy, nodeline, curseg))
  469.         {
  470.            InsertObject( OBJ_VERTEXES, -1, newx, newy);
  471.            StoreInSegList( GetFarMemory( sizeof( struct Seg)), &segs2, &lastseg2, node, 2, FALSE);
  472.            lastseg2->start = NumVertexes - 1;
  473.            lastseg2->end = lastseg1->end;
  474.            lastseg2->angle = lastseg1->angle;
  475.            lastseg2->linedef = lastseg1->linedef;
  476.            lastseg2->flip = lastseg1->flip;
  477.            lastseg2->dist = lastseg1->dist + ComputeDist( newx - Vertexes[ lastseg1->start].x, newy - Vertexes[ lastseg1->start].y);
  478.            lastseg1->end = NumVertexes - 1;
  479.            ShowProgress( OBJ_VERTEXES);
  480.         }
  481.      }
  482.       }
  483.       else
  484.       {
  485.      /* the starting Vertex is on the second side (left) of the nodeline */
  486.      StoreInSegList( curseg, &segs2, &lastseg2, node, 2, TRUE);
  487.      if (c > d)
  488.      {
  489.         int newx, newy;
  490.  
  491.         /* the ending Vertex is on the other side: split the Seg in two */
  492.         if (ComputeIntersection( &newx, &newy, nodeline, curseg))
  493.         {
  494.            InsertObject( OBJ_VERTEXES, -1, newx, newy);
  495.            StoreInSegList( GetFarMemory( sizeof( struct Seg)), &segs1, &lastseg1, node, 1, FALSE);
  496.            lastseg1->start = NumVertexes - 1;
  497.            lastseg1->end = lastseg2->end;
  498.            lastseg1->angle = lastseg2->angle;
  499.            lastseg1->linedef = lastseg2->linedef;
  500.            lastseg1->flip = lastseg2->flip;
  501.            lastseg1->dist = lastseg2->dist + ComputeDist( newx - Vertexes[ lastseg2->start].x, newy - Vertexes[ lastseg2->start].y);
  502.            lastseg2->end = NumVertexes - 1;
  503.            ShowProgress( OBJ_VERTEXES);
  504.         }
  505.      }
  506.       }
  507.    }
  508.  
  509.    /* now, we should have all the Segs in segs1 and segs2 (seglist is empty) */
  510.    if (segs1 == NULL || segs2 == NULL)
  511.       ProgError("could not split the Segs list (this is a BUG!)");
  512.  
  513.    /* create Nodes or SSectors from segs1 */
  514.    if (NeedFurtherDivision( segs1))
  515.    {
  516.       node->node1 = CreateNodes( segs1);
  517.       node->child1 = 0;
  518.    }
  519.    else
  520.    {
  521.       node->node1 = NULL;
  522.       node->child1 = CreateSSector( segs1) | 0x8000;
  523.    }
  524.  
  525.    /* create Nodes or SSectors from segs2 */
  526.    if (NeedFurtherDivision( segs2))
  527.    {
  528.       node->node2 = CreateNodes( segs2);
  529.       node->child2 = 0;
  530.    }
  531.    else
  532.    {
  533.       node->node2 = NULL;
  534.       node->child2 = CreateSSector( segs2) | 0x8000;
  535.    }
  536.  
  537.    /* this Node is OK */
  538.    return node;
  539. }
  540.  
  541.  
  542. /*
  543.    IF YOU ARE WRITING A DOOM EDITOR OR ANOTHER ADD-ON, PLEASE READ THIS:
  544.  
  545.    I spent a lot of time writing the Nodes builder.  There may be some bugs in
  546.    it, but most of the code is OK.  If you steal any ideas from this program,
  547.    put a prominent message in your own editor (i.e. it must be displayed when
  548.    the program starts or in an "about" box) to make it CLEAR that some
  549.    original ideas were taken from DEU.  You need not credit me.  Just credit
  550.    DEU and its contributors.  Thanks.
  551.  
  552.    While everyone was talking about LineDefs, I had the idea of taking only
  553.    the Segs into account, and creating the Segs directly from the SideDefs.
  554.    Also, dividing the list of Segs in two after each call to CreateNodes makes
  555.    the algorithm faster.  I use several other tricks, such as looking at the
  556.    two ends of a Seg to see on which side of the nodeline it lies or if it
  557.    should be split in two.  I took me a lot of time and efforts to do this.
  558.  
  559.    I give this algorithm to whoever wants to use it, but with this condition:
  560.    if your program uses SOME of the IDEAS from DEU or the whole ALGORITHM, you
  561.    MUST tell it to the user.  And if you post a message with all or parts of
  562.    this algorithm in it, please post THIS NOTICE also.  I don't want to speak
  563.    legalese; I hope that you understand me...  I kindly give the sources of my
  564.    program to you: please be kind with me...
  565.  
  566.    If you need more information about this, here is my E-mail address:
  567.    quinet@montefiore.ulg.ac.be (Raphaël Quinet).
  568.  
  569.    Short description of the algorithm:
  570.      1 - Create one Seg for each SideDef: pick each LineDef in turn.  If it
  571.      has a "first" SideDef, then create a normal Seg.  If it has a
  572.      "second" SideDef, then create a flipped Seg.
  573.      2 - Call CreateNodes with the current list of Segs.  The list of Segs is
  574.      the only argument to CreateNodes.
  575.      3 - Save the Nodes, Segs and SSectors to disk.  Start with the leaves of
  576.      the Nodes tree and continue up to the root (last Node).
  577.  
  578.    CreateNodes does the following:
  579.      1 - Pick a nodeline amongst the Segs (minimize the number of splits and
  580.      keep the tree as balanced as possible).
  581.      2 - Move all Segs on the right of the nodeline in a list (segs1) and
  582.      move all Segs on the left of the nodeline in another list (segs2).
  583.      3 - If the first list (segs1) contains references to more than one
  584.      Sector or if the angle between two adjacent Segs is greater than
  585.      180°, then call CreateNodes with this (smaller) list.  Else, create
  586.      a SubSector with all these Segs.
  587.      4 - Do the same for the second list (segs2).
  588.      5 - Return the new node (its two children are already OK).
  589.  
  590.    Each time CreateSSector is called, the Segs are put in a global list.
  591.    When there is no more Seg in CreateNodes' list, then they are all in the
  592.    global list and ready to be saved to disk.
  593. */
  594.  
  595.  
  596. /* end of file */
  597.