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