home *** CD-ROM | disk | FTP | other *** search
/ D!Zone (Collector's Edition) / D_ZONE_CD.ISO / programs / editors / dmbsp / makenode.c < prev    next >
C/C++ Source or Header  |  1994-12-06  |  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->fl