home *** CD-ROM | disk | FTP | other *** search
/ Doom I/II Collection / DM12.ISO / edit / bsp12 / makenode.c < prev    next >
C/C++ Source or Header  |  1994-04-13  |  14KB  |  447 lines
  1. /*- MAKENODE.C --------------------------------------------------------------*
  2.  Recursively create nodes and return the pointers.
  3. *---------------------------------------------------------------------------*/
  4.  
  5. struct Node *CreateNode(struct Seg *ts)
  6. {
  7.     struct Node *tn;
  8.     struct Seg *rights = NULL;
  9.     struct Seg *lefts = NULL;
  10.  
  11.     tn = GetMemory( sizeof( struct Node));                /* Create a node*/
  12.  
  13.     DivideSegs(ts,&rights,&lefts);                        /* Divide node in two*/
  14.  
  15.     num_nodes++;
  16.  
  17.     tn->x = node_x;                                            /* store node line info*/
  18.     tn->y = node_y;
  19.     tn->dx = node_dx;
  20.     tn->dy = node_dy;
  21.  
  22.     FindLimits(lefts);                                        /* Find limits of vertices    */
  23.  
  24.     tn->maxy2 = lmaxy;
  25.     tn->miny2 = lminy;
  26.     tn->minx2 = lminx;
  27.     tn->maxx2 = lmaxx;
  28.  
  29.     if(IsItConvex(lefts))                                      /* Check lefthand side*/
  30.         {
  31.         tn->nextl = CreateNode(lefts);                    /* still segs remaining*/
  32.         tn->chleft = 0;
  33.         }
  34.     else
  35.         {
  36.         tn->nextl = NULL;
  37.         tn->chleft = CreateSSector(lefts) | 0x8000;
  38.         }
  39.  
  40.     FindLimits(rights);                                        /* Find limits of vertices*/
  41.     
  42.     tn->maxy1 = lmaxy;
  43.     tn->miny1 = lminy;
  44.     tn->minx1 = lminx;
  45.     tn->maxx1 = lmaxx;
  46.  
  47.     if(IsItConvex(rights))                                    /* Check righthand side*/
  48.         {
  49.         tn->nextr = CreateNode(rights);                    /* still segs remaining*/
  50.         tn->chright = 0;
  51.         }
  52.     else
  53.         {
  54.         tn->nextr = NULL;
  55.         tn->chright =  CreateSSector(rights) | 0x8000;
  56.         }
  57.  
  58.     return tn;
  59. }
  60.  
  61. /*---------------------------------------------------------------------------*
  62.  Split a list of segs (ts) into two using the method described at bottom of
  63.  file, this was taken from OBJECTS.C in the DEU5beta source.
  64.  
  65.  This is done by scanning all of the segs and finding the one that does
  66.  the least splitting and has the least difference in numbers of segs on either
  67.  side.
  68.  If the ones on the left side make a SSector, then create another SSector
  69.  else put the segs into lefts list.
  70.  If the ones on the right side make a SSector, then create another SSector
  71.  else put the segs into rights list.
  72. *---------------------------------------------------------------------------*/
  73.  
  74. void DivideSegs(struct Seg *ts,struct Seg **rs,struct Seg **ls)
  75. {
  76.     struct Seg *rights,*lefts;
  77.     struct Seg *tmps,*best,*news,*prev;
  78.     struct Seg *add_to_rs,*add_to_ls;
  79.       struct Seg *new_best,*new_rs,*new_ls;
  80.     
  81.     struct Seg *strights,*stlefts;
  82.  
  83.     int num_secs_r,num_secs_l,last_sec_r,last_sec_l;
  84.  
  85.     int num,least_splits,least;
  86.     int fv,tv,num_new = 0;
  87.     int bangle,cangle,cangle2,cfv,ctv,dx,dy;
  88.     short int x,y,val;
  89.  
  90.     FindLimits(ts);                            /* Find limits of this set of Segs*/
  91.     
  92.     sp.halfsx = (lmaxx - lminx) / 2;        /* Find half width of Node*/
  93.     sp.halfsy = (lmaxy - lminy) / 2;
  94.     sp.halfx = lminx + sp.halfsx;            /* Find middle of Node*/
  95.     sp.halfy = lminy + sp.halfsy;
  96.     
  97.     best = PickNode(ts);                        /* Pick best node to use.*/
  98.  
  99.     if(best == NULL) ProgError("Couldn't pick nodeline!");
  100.  
  101.     node_x = vertices[best->start].x;
  102.     node_y = vertices[best->start].y;
  103.     node_dx = vertices[best->end].x-vertices[best->start].x;
  104.     node_dy = vertices[best->end].y-vertices[best->start].y;
  105.  
  106. /* When we get to here, best is a pointer to the partition seg.
  107.     Using this partition line, we must split any lines that are intersected
  108.     into a left and right half, flagging them to be put their respective sides
  109.     Ok, now we have the best line to use as a partitioning line, we must
  110.    split all of the segs into two lists (rightside & leftside).                 */
  111.  
  112.     rights = NULL;                                    /* Start off with empty*/
  113.     lefts = NULL;                                    /* lists.*/
  114.     strights = NULL;                                /* Start off with empty*/
  115.     stlefts = NULL;                                /* lists.*/
  116.  
  117.     psx = vertices[best->start].x;            /* Partition line coords*/
  118.     psy = vertices[best->start].y;
  119.     pex = vertices[best->end].x;
  120.     pey = vertices[best->end].y;
  121.     pdx = psx - pex;                                /* Partition line DX,DY*/
  122.     pdy = psy - pey;
  123.     
  124.     for(tmps=ts;tmps;tmps=tmps->next)
  125.         {
  126.         progress();                                    /* Something for the user to look at.*/
  127.         add_to_rs = NULL;
  128.         add_to_ls = NULL;
  129.         if(tmps != best)
  130.             {
  131.             lsx = vertices[tmps->start].x;    /* Calculate this here, cos it doesn't*/
  132.             lsy = vertices[tmps->start].y;    /* change for all the interations of*/
  133.             lex = vertices[tmps->end].x;        /* the inner loop!*/
  134.             ley = vertices[tmps->end].y;
  135.             val = DoLinesIntersect();
  136.             if((val&2 && val&64) || (val&4 && val&32))    /* If intersecting !!*/
  137.                 {
  138.                 ComputeIntersection(&x,&y);
  139. /*                printf("Splitting Linedef %d at %d,%d\n",tmps->linedef,x,y);*/
  140.                 
  141.                 vertices = ResizeMemory(vertices, sizeof(struct Vertex) * (num_verts+1));
  142.                 vertices[num_verts].x = x;
  143.                 vertices[num_verts].y = y;
  144.     
  145.                 news = GetMemory(sizeof( struct Seg));
  146.     
  147.                 news->next = tmps->next;
  148.                 tmps->next = news;
  149.                 news->start = num_verts;
  150.                 news->end = tmps->end;
  151.                 tmps->end = num_verts;
  152.                 news->linedef = tmps->linedef;
  153.                 news->angle = tmps->angle;
  154.                 news->flip = tmps->flip;
  155.                 news->dist = SplitDist(news);
  156. /*                printf("splitting dist = %d\n",news->dist);*/
  157. /*                printf("splitting vertices = %d,%d,%d,%d\n",tmps->start,tmps->end,news->start,news->end);*/
  158.                 if(val&32) add_to_ls = tmps;
  159.                 if(val&64) add_to_rs = tmps;
  160.                 if(val&2) add_to_ls = news;
  161.                 if(val&4) add_to_rs = news;
  162.                 tmps = news;
  163.                 num_verts++;
  164.                 num_new++;
  165.                 }
  166.             else
  167.                 {                                            /* Not split, which side ?*/
  168.                 if(val&34) add_to_ls = tmps;
  169.                 if(val&68) add_to_rs = tmps;
  170.                 if(val&1 && val&16)                    /* On same line*/
  171.                     {
  172.                     if(tmps->flip == best->flip) add_to_rs = tmps;
  173.                     if(tmps->flip != best->flip) add_to_ls = tmps;
  174.                     }
  175.                 }
  176.             }
  177.         else add_to_rs = tmps;                        /* This is the partition line*/
  178.         
  179. /*        printf("Val = %X\n",val);*/
  180.  
  181.         if(add_to_rs)                            /* CHECK IF SHOULD ADD RIGHT ONE */
  182.             {
  183.             new_rs = GetMemory(sizeof(struct Seg));
  184.             if(add_to_rs == best) new_best = new_rs;
  185.             new_rs->start = add_to_rs->start;
  186.             new_rs->end = add_to_rs->end;
  187.             new_rs->linedef = add_to_rs->linedef;
  188.             new_rs->angle = add_to_rs->angle;
  189.             new_rs->flip = add_to_rs->flip;
  190.             new_rs->dist = add_to_rs->dist;
  191.             new_rs->next = NULL;
  192.             if(!rights) strights = rights = new_rs;
  193.             else
  194.                 {
  195.                 rights->next = new_rs;
  196.                 rights = new_rs;
  197.                 }
  198.             }
  199.                 
  200.         if(add_to_ls)                            /* CHECK IF SHOULD ADD LEFT ONE */
  201.             {
  202.             new_ls = GetMemory(sizeof(struct Seg));
  203.             if(add_to_ls == best) new_best = new_ls;
  204.             new_ls->start = add_to_ls->start;
  205.             new_ls->end = add_to_ls->end;
  206.             new_ls->linedef = add_to_ls->linedef;
  207.             new_ls->angle = add_to_ls->angle;
  208.             new_ls->flip = add_to_ls->flip;
  209.             new_ls->dist = add_to_ls->dist;
  210.             new_ls->next = NULL;
  211.             if(!lefts) stlefts = lefts = new_ls;
  212.             else
  213.                 {
  214.                 lefts->next = new_ls;
  215.                 lefts = new_ls;
  216.                 }
  217.             }
  218.         }
  219.  
  220.     if(strights == NULL)
  221.         {
  222. /*        printf("No right side, moving partition into right side\n");*/
  223.         strights = rights = new_best;
  224.         prev = NULL;
  225.         for(tmps=stlefts;tmps;tmps=tmps->next)
  226.             {
  227.             if(tmps == new_best)
  228.                 {
  229.                 if(prev != NULL) prev->next=tmps->next;
  230.                 else stlefts=tmps->next;
  231.                 }
  232.             prev=tmps;
  233.             }
  234.         prev->next = NULL;
  235.         }
  236.     
  237.     if(stlefts == NULL)
  238.         {
  239. /*        printf("No left side, moving partition into left side\n");*/
  240.         stlefts = lefts = new_best;
  241.         prev = NULL;
  242.         for(tmps=strights;tmps;tmps=tmps->next)
  243.             {
  244.             if(tmps == new_best)
  245.                 {
  246.                 if(prev != NULL) prev->next=tmps->next;
  247.                 else strights=tmps->next;
  248.                 }
  249.             prev=tmps;
  250.             }
  251.         stlefts->next = NULL;
  252.         prev->next = NULL;                                /* Make sure end of list = NULL*/
  253.         }
  254.  
  255.     if(rights->next != NULL) rights->next = NULL;
  256.     if(lefts->next != NULL) lefts->next = NULL;
  257.  
  258.     for(tmps=ts;tmps;tmps=best)
  259.         {
  260.         best=tmps->next;
  261.         free(tmps);
  262.         }
  263.  
  264. /*    printf("Made %d new Vertices and Segs\n",num_new);*/
  265.  
  266.     *rs = strights ; *ls = stlefts;
  267. }
  268.  
  269. /*--------------------------------------------------------------------------*/
  270.  
  271. int IsItConvex( struct Seg *ts)
  272. {
  273.    struct Seg *line,*check;
  274.    int   sector,val;
  275.  
  276.     if (ts->flip) sector = sidedefs[linedefs[ ts->linedef].sidedef2].sector;
  277.    else sector = sidedefs[linedefs[ts->linedef].sidedef1].sector;
  278.    
  279.     for (line = ts->next; line; line = line->next)
  280.        {
  281.       if (line->flip)
  282.           {
  283.             if (sidedefs[ linedefs[ line->linedef].sidedef2].sector != sector)
  284.                 return TRUE;
  285.           }
  286.       else
  287.           {
  288.             if (sidedefs[ linedefs[ line->linedef].sidedef1].sector != sector)
  289.                 return TRUE;
  290.             }
  291.        }
  292.    
  293.     /* all of the segs must be on the same side all the other segs */
  294.  
  295.     for(line=ts;line;line=line->next)
  296.         {
  297.         psx = vertices[line->start].x;
  298.         psy = vertices[line->start].y;
  299.         pex = vertices[line->end].x;
  300.         pey = vertices[line->end].y;
  301.         pdx = (psx - pex);                                    /* Partition line DX,DY*/
  302.         pdy = (psy - pey);
  303.         for(check=ts;check;check=check->next)
  304.             {
  305.             if(line!=check)
  306.                 {
  307.                 lsx = vertices[check->start].x;    /* Calculate this here, cos it doesn't*/
  308.                 lsy = vertices[check->start].y;    /* change for all the interations of*/
  309.                 lex = vertices[check->end].x;        /* the inner loop!*/
  310.                 ley = vertices[check->end].y;
  311.                 val = DoLinesIntersect();
  312.                 if(val&34) return TRUE;
  313.                 }
  314.             }
  315.         }
  316.  
  317.     /* no need to split the list: these Segs can be put in a SSector */
  318.    return FALSE;
  319. }
  320.  
  321. /*--------------------------------------------------------------------------*/
  322.  
  323. int CreateSSector(struct Seg *tmps)
  324. {
  325.     int n;
  326.     
  327.     if(num_ssectors == 0)
  328.         {
  329.         ssectors = GetMemory(sizeof(struct SSector));
  330.         }
  331.     else
  332.         {
  333.         ssectors = ResizeMemory(ssectors,sizeof(struct SSector)*(num_ssectors+1));
  334.         }
  335.     
  336.     ssectors[num_ssectors].first = num_psegs;
  337.  
  338.     n = num_psegs;
  339.     
  340. /*    printf("\n");*/
  341.  
  342.     for(;tmps;tmps=tmps->next)
  343.         {
  344.         if(num_psegs == 0)
  345.             {
  346.             psegs = GetMemory(sizeof(struct Pseg));
  347.             }
  348.         else
  349.             {
  350.             psegs = ResizeMemory(psegs,sizeof(struct Pseg)*(num_psegs+1));
  351.             }
  352.  
  353.         psegs[num_psegs].start = tmps->start;
  354.         psegs[num_psegs].end = tmps->end;
  355.         psegs[num_psegs].angle = tmps->angle;
  356.         psegs[num_psegs].linedef = tmps->linedef;
  357.         psegs[num_psegs].flip = tmps->flip;
  358.         psegs[num_psegs].dist = tmps->dist;
  359. /*
  360.         printf("%d,%d,%u,%d,%d,%u\n",
  361.             psegs[num_psegs].start,
  362.             psegs[num_psegs].end,
  363.             psegs[num_psegs].angle,
  364.             psegs[num_psegs].linedef,
  365.             psegs[num_psegs].flip,
  366.             psegs[num_psegs].dist);
  367. */
  368.         num_psegs++;
  369.         }
  370.     
  371.     ssectors[num_ssectors].num = num_psegs-n;
  372.     
  373.     num_ssectors++;
  374.     
  375.     return num_ssectors-1;
  376. }
  377.  
  378. /*- translate (dx, dy) into an integer angle value (0-65535) ---------------*/
  379.  
  380. unsigned ComputeAngle( int dx, int dy)
  381. {
  382.    double w;
  383.  
  384.     w = (atan2( (double) dy , (double) dx) * (double)(65536/(M_PI*2)));
  385.  
  386.     if(w<0) w = (double)65536+w;
  387.     
  388.     return (unsigned) w;
  389. }
  390.  
  391. /*---------------------------------------------------------------------------*
  392.    
  393.     This message has been taken, complete, from OBJECTS.C in DEU5beta source.
  394.     It outlines the method used here to pick the nodelines.
  395.  
  396.     IF YOU ARE WRITING A DOOM EDITOR, PLEASE READ THIS:
  397.  
  398.    I spent a lot of time writing the Nodes builder.  There are some bugs in
  399.    it, but most of the code is OK.  If you steal any ideas from this program,
  400.    put a prominent message in your own editor to make it CLEAR that some
  401.    original ideas were taken from DEU.  Thanks.
  402.  
  403.    While everyone was talking about LineDefs, I had the idea of taking only
  404.    the Segs into account, and creating the Segs directly from the SideDefs.
  405.    Also, dividing the list of Segs in two after each call to CreateNodes makes
  406.    the algorithm faster.  I use several other tricks, such as looking at the
  407.    two ends of a Seg to see on which side of the nodeline it lies or if it
  408.    should be split in two.  I took me a lot of time and efforts to do this.
  409.  
  410.    I give this algorithm to whoever wants to use it, but with this condition:
  411.    if your program uses some of the ideas from DEU or the whole algorithm, you
  412.    MUST tell it to the user.  And if you post a message with all or parts of
  413.    this algorithm in it, please post this notice also.  I don't want to speak
  414.    legalese; I hope that you understand me...  I kindly give the sources of my
  415.    program to you: please be kind with me...
  416.  
  417.    If you need more information about this, here is my E-mail address:
  418.    quinet@montefiore.ulg.ac.be (Raphaël Quinet).
  419.  
  420.    Short description of the algorithm:
  421.      1 - Create one Seg for each SideDef: pick each LineDef in turn.  If it
  422.      has a "first" SideDef, then create a normal Seg.  If it has a
  423.      "second" SideDef, then create a flipped Seg.
  424.      2 - Call CreateNodes with the current list of Segs.  The list of Segs is
  425.      the only argument to CreateNodes.
  426.      3 - Save the Nodes, Segs and SSectors to disk.  Start with the leaves of
  427.      the Nodes tree and continue up to the root (last Node).
  428.  
  429.    CreateNodes does the following:
  430.      1 - Pick a nodeline amongst the Segs (minimize the number of splits and
  431.      keep the tree as balanced as possible).
  432.      2 - Move all Segs on the right of the nodeline in a list (segs1) and do
  433.      the same for all Segs on the left of the nodeline (in segs2).
  434.      3 - If the first list (segs1) contains references to more than one
  435.      Sector or if the angle between two adjacent Segs is greater than
  436.      180°, then call CreateNodes with this (smaller) list.  Else, create
  437.      a SubSector with all these Segs.
  438.      4 - Do the same for the second list (segs2).
  439.      5 - Return the new node (its two children are already OK).
  440.  
  441.    Each time CreateSSector is called, the Segs are put in a global list.
  442.    When there is no more Seg in CreateNodes' list, then they are all in the
  443.    global list and ready to be saved to disk.
  444.  
  445. *---------------------------------------------------------------------------*/
  446.  
  447.