home *** CD-ROM | disk | FTP | other *** search
/ MegaDoom Add-On 3 / MEGADOOM3.iso / editor / bsp12x / bsp.c < prev    next >
C/C++ Source or Header  |  1994-10-26  |  20KB  |  766 lines
  1. /*- BSP.C -------------------------------------------------------------------*
  2.  
  3.  Node builder for DOOM levels (c) 1994 Colin Reed, version 1.2 (dos extended)
  4.  
  5.  Many thanks to Mark Harrison for finding a bug in 1.1 which caused some
  6.  texture align problems when a flipped SEG was split.
  7.  
  8.  Credit to:-
  9.  
  10.  Raphael Quinet (A very small amount of code has been borrowed from DEU).
  11.  Matt Fell for the doom specs.
  12.  
  13.  Also, the original idea for some of the techniques where also taken from the
  14.  comment at the bottom of OBJECTS.C in DEU, and the doc by Matt Fell about
  15.  the nodes.
  16.  
  17.  Use this code for your own editors, but please credit me.
  18.  
  19. *---------------------------------------------------------------------------*/
  20.  
  21. #include "bsp.h"
  22. #include "structs.h"
  23.  
  24. /*- Global Vars ------------------------------------------------------------*/
  25.  
  26. FILE *infile,*outfile;
  27. char *testwad;
  28. char *outwad;
  29.  
  30. struct wad_header *wad = NULL;
  31. struct directory *direc = NULL;
  32. char rname[]="\0\0\0\0\0\0\0\0";
  33.  
  34. struct Thing *things;
  35. long num_things = 0;
  36. long things_start = 0;
  37.  
  38. struct Vertex *vertices;
  39. long num_verts = 0;
  40. long vertices_start = 0;
  41.  
  42. struct LineDef *linedefs;
  43. long num_lines = 0;
  44. long linedefs_start = 0;
  45.  
  46. struct SideDef *sidedefs;
  47. long num_sides = 0;
  48. long sidedefs_start = 0;
  49.  
  50. struct Sector *sectors;
  51. long num_sects = 0;
  52. long sectors_start = 0;
  53.  
  54. struct SSector *ssectors;
  55. long num_ssectors = 0;
  56. long ssectors_start = 0;
  57.  
  58. struct Pseg *psegs = NULL;
  59. long num_psegs = 0;
  60. long segs_start = 0;
  61.  
  62. struct Pnode *pnodes = NULL;
  63. long num_pnodes = 0;
  64. long pnode_indx = 0;
  65. long pnodes_start = 0;
  66.  
  67. struct Seg *tsegs = NULL;
  68. long num_tsegs = 0;
  69.  
  70. struct Node *nodelist = NULL;
  71. long num_nodes = 0;
  72.  
  73. long reject_start;
  74. long reject_size;
  75.  
  76. struct Block blockhead;
  77. short int *blockptrs;
  78. short int *blocklists=NULL;
  79. long blockptrs_size;
  80. long blockmap_size;
  81. long blockmap_start;
  82.  
  83. struct splitter sp;
  84.  
  85. short node_x;
  86. short node_y;
  87. short node_dx;
  88. short node_dy;
  89.  
  90. short lminx;
  91. short lmaxx;
  92. short lminy;
  93. short lmaxy;
  94.  
  95. short mapminx;
  96. short mapmaxx;
  97. short mapminy;
  98. short mapmaxy;
  99.  
  100. long psx,psy,pex,pey,pdx,pdy;
  101. long lsx,lsy,lex,ley;
  102.  
  103. unsigned char pcnt;
  104.  
  105. long fagcount = 0;
  106.  
  107. /*- Prototypes -------------------------------------------------------------*/
  108.  
  109. void OpenWadFile(char *);
  110. void Printname(struct directory *);
  111. int  FindDir(char *);
  112. void GetThings(void);
  113. void GetVertexes(void);
  114. void GetLinedefs(void);
  115. void GetSidedefs(void);
  116. void GetSectors(void);
  117. void FindLimits(struct Seg *);
  118.  
  119. struct Seg *CreateSegs();
  120.  
  121. struct Node *CreateNode(struct Seg *);
  122. void DivideSegs(struct Seg *,struct Seg **,struct Seg **);
  123. int IsItConvex(struct Seg *);
  124.  
  125. struct Seg *PickNode(struct Seg *);
  126. void ComputeIntersection(short int *,short int *);
  127. int DoLinesIntersect();
  128. int SplitDist(struct Seg *);
  129.  
  130. void ReverseNodes(struct Node *);
  131. long CreateBlockmap(void);
  132.  
  133. inline void progress(void);
  134.  
  135. /*--------------------------------------------------------------------------*/
  136.  
  137. #include "makenode.c"
  138. #include "picknode.c"
  139. #include "funcs.c"
  140.  
  141. /*- Main Program -----------------------------------------------------------*/
  142.  
  143. int main(int argc,char *argv[])
  144. {
  145.     long dir_start = 12;                                    /* Skip Pwad header*/
  146.     long dir_entries = 0;
  147.     
  148.     int n;
  149.     unsigned char *data;
  150.     
  151.     printf("** Doom BSP node builder ver 1.2x (c) 1994 Colin Reed **\n");
  152.  
  153.     if(argc<2 || argc>3)
  154.         {
  155.         printf("\nThis Node builder was created from the basic theory stated in DEU5 (OBJECTS.C)\n");
  156.         printf("\nCredits should go to :-\n");
  157.         printf("Matt Fell      (matt.burnett@acebbs.com) for the Doom Specs.\n");
  158.         printf("Raphael Quinet (quinet@montefiore.ulg.ac.be) for DEU and the original idea.\n");
  159.         printf("Mark Harrison  (harrison@lclark.edu) for finding a bug in 1.1x\n");
  160.         printf("\nUsage: BSP name.wad {output.wad}\n");
  161.         printf("     : (If no output.wad is specified, TMP.WAD is written)\n");
  162.         exit(0);
  163.         }
  164.  
  165.     testwad = argv[1];                                    /* Get input name*/
  166.     if(argc == 3) outwad = argv[2];                    /* Get output name*/
  167.     else outwad = "tmp.wad";
  168.  
  169.     OpenWadFile(testwad);                                /* Opens and reads directory*/
  170.     GetThings();                                            /* of wad file*/
  171.     GetLinedefs();                                            /* Get linedefs and vertices*/
  172.     GetVertexes();                                            /* and delete redundant.*/
  173.     GetSidedefs();
  174.      GetSectors();
  175.  
  176.     num_tsegs = 0;
  177.     tsegs = CreateSegs();                                  /* Initially create segs*/
  178.  
  179.     FindLimits(tsegs);                                    /* Find limits of vertices*/
  180.     
  181.     mapminx = lminx;                                        /* store as map limits*/
  182.     mapmaxx = lmaxx;
  183.     mapminy = lminy;
  184.     mapmaxy = lmaxy;
  185.     
  186.     printf("Map goes from X (%d,%d) Y (%d,%d)\n",lminx,lmaxx,lminy,lmaxy);
  187.     
  188.     num_nodes = 0;
  189.     nodelist = CreateNode(tsegs);                        /* recursively create nodes*/
  190.     printf("%lu NODES created, with %lu SSECTORS.\n",num_nodes,num_ssectors);
  191.  
  192.     pnodes = GetMemory(sizeof(struct Pnode)*num_nodes);
  193.     num_pnodes = 0;
  194.     pnode_indx = 0;
  195.     ReverseNodes(nodelist);
  196.  
  197.     dir_entries++;                                            /* Skip level number*/
  198.  
  199.     things_start = dir_start;
  200.     dir_start = dir_start + (sizeof(struct Thing)*num_things);
  201.     direc[dir_entries].start = things_start;
  202.     direc[dir_entries].length = (sizeof(struct Thing)*num_things);
  203.     dir_entries++;
  204.     
  205.     linedefs_start = dir_start;
  206.     dir_start = dir_start + (sizeof(struct LineDef)*num_lines);
  207.     direc[dir_entries].start = linedefs_start;
  208.     direc[dir_entries].length = (sizeof(struct LineDef)*num_lines);
  209.     dir_entries++;
  210.     
  211.     sidedefs_start = dir_start;
  212.     dir_start = dir_start + (sizeof(struct SideDef)*num_sides);
  213.     direc[dir_entries].start = sidedefs_start;
  214.     direc[dir_entries].length = (sizeof(struct SideDef)*num_sides);
  215.     dir_entries++;
  216.     
  217.     printf("Found %lu used vertices\n",num_verts);
  218.     
  219.     vertices_start = dir_start;
  220.     dir_start = dir_start + (sizeof(struct Vertex)*num_verts);
  221.     direc[dir_entries].start = vertices_start;
  222.     direc[dir_entries].length = (sizeof(struct Vertex)*num_verts);
  223.     dir_entries++;
  224.     
  225.     segs_start = dir_start;
  226.     dir_start = dir_start + (sizeof(struct Pseg)*num_psegs);
  227.     direc[dir_entries].start = segs_start;
  228.     direc[dir_entries].length = (sizeof(struct Pseg)*num_psegs);
  229.     dir_entries++;
  230.     
  231.     ssectors_start = dir_start;
  232.     dir_start = dir_start + (sizeof(struct SSector)*num_ssectors);
  233.     direc[dir_entries].start = ssectors_start;
  234.     direc[dir_entries].length = (sizeof(struct SSector)*num_ssectors);
  235.     dir_entries++;
  236.     
  237.     pnodes_start = dir_start;
  238.     dir_start = dir_start + (sizeof(struct Pnode)*num_pnodes);
  239.     direc[dir_entries].start = pnodes_start;
  240.     direc[dir_entries].length = (sizeof(struct Pnode)*num_pnodes);
  241.     dir_entries++;
  242.     
  243.     sectors_start = dir_start;
  244.     dir_start = dir_start + (sizeof(struct Sector)*num_sects);
  245.     direc[dir_entries].start = sectors_start;
  246.     direc[dir_entries].length = (sizeof(struct Sector)*num_sects);
  247.     dir_entries++;
  248.  
  249.     reject_size = (num_sects*num_sects+7)/8;
  250.     data = calloc(reject_size,1);
  251.     reject_start = dir_start;
  252.     dir_start+=reject_size;
  253.     direc[dir_entries].start = reject_start;            /* Skip reject map*/
  254.     direc[dir_entries].length = reject_size;
  255.     dir_entries++;
  256.  
  257.     blockmap_size = CreateBlockmap();
  258.  
  259.     blockmap_start = dir_start;
  260.     dir_start = dir_start + (blockmap_size+blockptrs_size+8);
  261.     direc[dir_entries].start = blockmap_start;
  262.     direc[dir_entries].length = (blockmap_size+blockptrs_size+8);
  263.     dir_entries++;
  264.  
  265.     printf("Completed blockmap building and saved PWAD as %s\n",outwad);
  266.     
  267.     if((outfile = fopen(outwad,"wb")) == NULL)
  268.         {
  269.       printf("Error: Could not open output PWAD file %s", outwad);
  270.         exit(0);
  271.         }
  272.     fwrite(wad,4,1,outfile);
  273.     fwrite(&dir_entries,sizeof(long),1,outfile);
  274.     fwrite(&dir_start,sizeof(long),1,outfile);
  275.     fwrite(things,(sizeof(struct Thing)*num_things),1,outfile);
  276.     fwrite(linedefs,(sizeof(struct LineDef)*num_lines),1,outfile);
  277.     fwrite(sidedefs,(sizeof(struct SideDef)*num_sides),1,outfile);
  278.     fwrite(vertices,(sizeof(struct Vertex)*num_verts),1,outfile);
  279.     fwrite(psegs,(sizeof(struct Pseg)*num_psegs),1,outfile);
  280.     fwrite(ssectors,(sizeof(struct SSector)*num_ssectors),1,outfile);
  281.     fwrite(pnodes,(sizeof(struct Pnode)*num_pnodes),1,outfile);
  282.     fwrite(sectors,(sizeof(struct Sector)*num_sects),1,outfile);
  283.     fwrite(data,reject_size,1,outfile);
  284.     fwrite(&blockhead,(sizeof(struct Block)),1,outfile);
  285.     fwrite(blockptrs,blockptrs_size,1,outfile);
  286.     fwrite(blocklists,blockmap_size,1,outfile);
  287.     fwrite(direc,(sizeof(struct directory)*wad->num_entries),1,outfile);
  288.     fclose(outfile);
  289.  
  290.     return 0;
  291. }
  292.  
  293. /*- initially creates all segs, one for each line def ----------------------*/
  294.  
  295. struct Seg *CreateSegs()
  296. {
  297.     struct Seg *cs = NULL;                    /* current and temporary Segs*/
  298.     struct Seg *ts = NULL;
  299.     struct Seg *fs = NULL;                    /* first Seg in list*/
  300.     
  301.     short    n,fv,tv;
  302.     int    dx,dy;
  303.  
  304.     printf("Creating Segs ..........\n");
  305.  
  306.     for(n=0; n < num_lines; n++)            /* step through linedefs and get side*/
  307.         {                                            /* numbers*/
  308.         fv = linedefs[n].start;
  309.         tv = linedefs[n].end;
  310.  
  311.         if(linedefs[n].sidedef1 != -1)
  312.             {                                                        /* create normal seg*/
  313.             ts = GetMemory( sizeof( struct Seg));        /* get mem for Seg*/
  314.             if(cs)
  315.                 {
  316.                 cs->next = ts;
  317.                 cs = ts;
  318.                 cs->next = NULL;
  319.                 }
  320.             else
  321.                 {
  322.                 fs = cs = ts;
  323.                 cs->next = NULL;
  324.                 }
  325.             cs->start = fv;
  326.             cs->end = tv;
  327. /*            printf("%d,%d\n",fv,tv);*/
  328.             dx = (vertices[tv].x-vertices[fv].x);
  329.             dy = (vertices[tv].y-vertices[fv].y);
  330.             cs->angle = ComputeAngle(dx,dy);
  331.             cs->linedef = n;
  332.             cs->dist = 0;
  333.             cs->flip = 0;
  334.             num_tsegs++;
  335.             }
  336.         if(linedefs[n].sidedef2 != -1)
  337.             {                                                        /* create flipped seg*/
  338.             ts = GetMemory( sizeof( struct Seg));        /* get mem for Seg*/
  339.             if(cs)
  340.                 {
  341.                 cs->next = ts;
  342.                 cs = ts;
  343.                 cs->next = NULL;
  344.                 }
  345.             else
  346.                 {
  347.                 fs = cs = ts;
  348.                 cs->next = NULL;
  349.                 }
  350.             cs->start = tv;
  351.             cs->end = fv;
  352.             dx = (vertices[fv].x-vertices[tv].x);
  353.             dy = (vertices[fv].y-vertices[tv].y);
  354.             cs->angle = ComputeAngle(dx,dy);
  355.             cs->linedef = n;
  356.             cs->dist = 0;
  357.             cs->flip = 1;
  358.             num_tsegs++;
  359.             }
  360.         }
  361.  
  362.     return fs;
  363. }
  364.  
  365. /*--------------------------------------------------------------------------*/
  366. /* Find limits from a list of segs, does this by stepping through the segs*/
  367. /* and comparing the vertices at both ends.*/
  368. /*--------------------------------------------------------------------------*/
  369.  
  370. void FindLimits(struct Seg *ts)
  371. {
  372.     int n,minx,miny,maxx,maxy;
  373.     int fv,tv;
  374.  
  375.     minx = 32767;
  376.     maxx = -32767;
  377.     miny = 32767;
  378.     maxy = -32767;
  379.  
  380.     while(1)
  381.         {
  382.         fv = ts->start;
  383.         tv = ts->end;
  384. /*        printf("%d : %d,%d\n",n,vertices[n].x,vertices[n].y);*/
  385.         if(vertices[fv].x < minx) minx = vertices[fv].x;
  386.         if(vertices[fv].x > maxx) maxx = vertices[fv].x;
  387.         if(vertices[fv].y < miny) miny = vertices[fv].y;
  388.         if(vertices[fv].y > maxy) maxy = vertices[fv].y;
  389.         if(vertices[tv].x < minx) minx = vertices[tv].x;
  390.         if(vertices[tv].x > maxx) maxx = vertices[tv].x;
  391.         if(vertices[tv].y < miny) miny = vertices[tv].y;
  392.         if(vertices[tv].y > maxy) maxy = vertices[tv].y;
  393.         if(ts->next == NULL) break;
  394.         ts = ts->next;
  395.         }
  396.     lminx = minx;
  397.     lmaxx = maxx;
  398.     lminy = miny;
  399.     lmaxy = maxy;
  400. }
  401.  
  402. /*--------------------------------------------------------------------------*/
  403.  
  404. int SplitDist(struct Seg *ts)
  405. {
  406.     double t,dx,dy;
  407.     
  408.     if(ts->flip==0)
  409.         {
  410.         dx = (double)(vertices[linedefs[ts->linedef].start].x)-(vertices[ts->start].x);
  411.         dy = (double)(vertices[linedefs[ts->linedef].start].y)-(vertices[ts->start].y);
  412.  
  413.         if(dx == 0 && dy == 0) printf("Trouble in SplitDist %f,%f\n",dx,dy);
  414.         t = sqrt((dx*dx) + (dy*dy));
  415.         return (int)t;
  416.         }
  417.     else
  418.         {
  419.         dx = (double)(vertices[linedefs[ts->linedef].end].x)-(vertices[ts->start].x);
  420.         dy = (double)(vertices[linedefs[ts->linedef].end].y)-(vertices[ts->start].y);
  421.  
  422.         if(dx == 0 && dy == 0) printf("Trouble in SplitDist %f,%f\n",dx,dy);
  423.         t = sqrt((dx*dx) + (dy*dy));
  424.         return (int)t;
  425.         }
  426. }
  427.  
  428. /*- get the directory from a wad file --------------------------------------*/
  429.  
  430. void OpenWadFile(char *filename)
  431. {
  432.     struct directory *dir;
  433.  
  434.     long n;
  435.  
  436.     if((infile = fopen(filename,"rb")) == NULL)
  437.         {
  438.       printf("Error: Cannot find WAD file %s", filename);
  439.         exit(0);
  440.         }
  441.  
  442.     wad = GetMemory( sizeof( struct wad_header));
  443.     
  444.     fread(wad,sizeof( struct wad_header),1,infile);
  445.  
  446.     printf("Opened %c%c%c%c file : %s. %lu dir entries at %lu.\n",
  447.         wad->type[0],wad->type[1],wad->type[2],wad->type[3],filename,
  448.         wad->num_entries,wad->dir_start);
  449.  
  450.     direc = dir = GetMemory( sizeof( struct directory) * wad->num_entries);
  451.     
  452.     fseek(infile,wad->dir_start,0);
  453.  
  454.     for(n = 0; n < wad->num_entries; n++)
  455.         {
  456.         fread(dir,sizeof( struct directory),1,infile);
  457. /*        Printname(dir);
  458.         printf(" of size %lu at %lu.\n",dir->length,dir->start);    */
  459.         dir++;
  460.         }
  461. }
  462.  
  463. /*- read the things from the wad file and place in 'things' ----------------*/
  464.  
  465. void GetThings(void)
  466. {
  467.     int n;
  468.  
  469.     n = FindDir("THINGS");
  470.     if(direc[n].length == 0) ProgError("Must have at least 1 thing");
  471.     num_things = (direc[n].length) / (sizeof( struct Thing));
  472. /*    printf("Allocating %lu bytes for %d things\n",direc[n].length,num_things);*/
  473.     things = GetMemory( direc[n].length);
  474.     fseek(infile,direc[n].start,0);
  475.     fread(things,direc[n].length,1,infile);
  476. }
  477.  
  478. /*- read the vertices from the wad file and place in 'vertices' ------------*/
  479.  
  480. void GetVertexes(void)
  481. {
  482.     struct Vertex *tmpv;
  483.     int n,i,t;
  484.     long used_verts;
  485.  
  486.     n = FindDir("VERTEXES");
  487.     if(direc[n].length == 0) ProgError("Couldn't find any Vertices");
  488.     fseek(infile,direc[n].start,0);
  489.     num_verts = (direc[n].length) / (sizeof( struct Vertex));
  490.     tmpv = GetMemory(sizeof(struct Vertex)*num_verts);
  491.     vertices = GetMemory(sizeof(struct Vertex)*num_verts);
  492.     fread(tmpv,direc[n].length,1,infile);
  493.  
  494.     used_verts = 0;
  495.     for(i=0;i<num_verts;i++)
  496.         {
  497.         if(Reference(i))
  498.             {
  499.             vertices[used_verts].x = tmpv[i].x;
  500.             vertices[used_verts].y = tmpv[i].y;
  501.             
  502.             for(t=0; t<num_lines; t++)
  503.                 {
  504.                 if(linedefs[t].start == i) linedefs[t].start = used_verts;
  505.                 if(linedefs[t].end == i) linedefs[t].end = used_verts;
  506.                 }
  507.             used_verts++;
  508.             }
  509.         else
  510.             {
  511. /*            printf("Vertex [%d] not used.\n",i);            */
  512.             }
  513.         }
  514.     printf("Loaded %lu vertices, but %lu were unused.\n",num_verts,num_verts-used_verts);
  515.     num_verts = used_verts;
  516.     free(tmpv);
  517. }
  518.  
  519. /*--------------------------------------------------------------------------*/
  520.  
  521. int Reference(int vert_num)
  522. {
  523.     int n;
  524.  
  525.     for(n=0; n<num_lines; n++)
  526.         {
  527.         if(linedefs[n].start == vert_num || linedefs[n].end == vert_num) return 1;
  528.         }
  529.     return 0;
  530. }
  531.  
  532. /*- read the linedefs from the wad file and place in 'linedefs' ------------*/
  533.  
  534. void GetLinedefs(void)
  535. {
  536.     int n;
  537.  
  538.     n = FindDir("LINEDEFS");
  539.     if(direc[n].length == 0) ProgError("Couldn't find any Linedefs");
  540.     num_lines = (direc[n].length) / (sizeof( struct LineDef));
  541. /*    printf("Allocating %lu bytes for %d Linedefs\n",direc[n].length,num_lines);*/
  542.     linedefs = GetMemory( direc[n].length);
  543.     fseek(infile,direc[n].start,0);
  544.     fread(linedefs,direc[n].length,1,infile);
  545. }
  546.  
  547. /*- read the sidedefs from the wad file and place in 'sidedefs' ------------*/
  548.  
  549. void GetSidedefs(void)
  550. {
  551.     int n;
  552.  
  553.     n = FindDir("SIDEDEFS");
  554.     if(direc[n].length == 0) ProgError("Couldn't find any Sidedefs");
  555.     num_sides = (direc[n].length) / (sizeof( struct SideDef));
  556. /*    printf("Allocating %lu bytes for %d Sidedefs\n",direc[n].length,num_sides);*/
  557.     sidedefs = GetMemory( direc[n].length);
  558.     fseek(infile,direc[n].start,0);
  559.     fread(sidedefs,direc[n].length,1,infile);
  560. }
  561.  
  562. /*- read the sectors from the wad file and place in 'sectors' ------------*/
  563.  
  564. void GetSectors(void)
  565. {
  566.     int n;
  567.  
  568.     n = FindDir("SECTORS");
  569.     num_sects = (direc[n].length) / (sizeof( struct Sector));
  570. /*    printf("Allocating %lu bytes for %d Sectors\n",direc[n].length,num_sects);*/
  571.     sectors = GetMemory( direc[n].length);
  572.     fseek(infile,direc[n].start,0);
  573.     fread(sectors,direc[n].length,1,infile);
  574. }
  575.  
  576. /*- find the offset into the directory of a resource -----------------------*/
  577.  
  578. int FindDir(char *name)
  579. {
  580.     struct directory *dir;
  581.     int n;
  582.  
  583.     dir = direc;
  584.  
  585.     for(n=0; n< wad->num_entries; n++)
  586.         {
  587.         strncpy(rname,dir->name,8);
  588.         if(strcmp(rname,name) == 0) return n;
  589.         dir++;
  590.         }
  591.     ProgError( "Cannot find %s", name);
  592.     return 0;
  593. }
  594.  
  595. /*- print a resource name by copying 8 chars into rname and printing this --*/
  596.  
  597. void Printname(struct directory *dir)
  598. {
  599.     strncpy(rname,dir->name,8);
  600.     printf("%-8s",rname);
  601. }
  602.  
  603. /*- Create blockmap --------------------------------------------------------*/
  604.  
  605. long CreateBlockmap()
  606. {
  607.     long blockoffs = 0;
  608.     int x,y,n;
  609.     int blocknum = 0;
  610.  
  611.     blockhead.minx = mapminx&-8;
  612.     blockhead.miny = mapminy&-8;
  613.     blockhead.xblocks = ((mapmaxx - (mapminx&-8)) / 128) + 1; 
  614.     blockhead.yblocks = ((mapmaxy - (mapminy&-8)) / 128) + 1; 
  615.     
  616.     blockptrs_size = (blockhead.xblocks*blockhead.yblocks)*2;
  617.     blockptrs = GetMemory(blockptrs_size);
  618.  
  619.     for(y=0;y<blockhead.yblocks;y++)
  620.         {
  621.         for(x=0;x<blockhead.xblocks;x++)
  622.             {
  623.             progress();
  624.  
  625.             blockptrs[blocknum]=(blockoffs+4+(blockptrs_size/2));
  626.             
  627.             blocklists = ResizeMemory(blocklists,((blockoffs+1)*2));
  628.             blocklists[blockoffs]=0;
  629.             blockoffs++;
  630.             for(n=0;n<num_lines;n++)
  631.                 {
  632.                 if(IsLineDefInside(n,(blockhead.minx+(x*128)),(blockhead.miny+(y*128)),(blockhead.minx+(x*128))+127,(blockhead.miny+(y*128))+127))
  633.                     {
  634. /*                    printf("found line %d in block %d\n",n,blocknum);*/
  635.                     blocklists = ResizeMemory(blocklists,((blockoffs+1)*2));
  636.                     blocklists[blockoffs]=n;
  637.                     blockoffs++;
  638.                     }
  639.                 }
  640.             blocklists = ResizeMemory(blocklists,((blockoffs+1)*2));
  641.             blocklists[blockoffs]=-1;
  642.             blockoffs++;
  643.             
  644.             blocknum++;
  645.             }
  646.         }
  647.     return blockoffs*2;
  648. }
  649.  
  650. /*--------------------------------------------------------------------------*/
  651.  
  652. int IsLineDefInside(int ldnum, int xmin, int ymin, int xmax, int ymax )
  653. {
  654.    int x1 = vertices[ linedefs[ ldnum].start].x;
  655.    int y1 = vertices[ linedefs[ ldnum].start].y;
  656.    int x2 = vertices[ linedefs[ ldnum].end].x;
  657.    int y2 = vertices[ linedefs[ ldnum].end].y;
  658.     
  659.     int outcode1,outcode2,t;
  660.  
  661.     while(1)
  662.         {
  663.         outcode1=0;
  664.         if(y1>ymax) outcode1|=1;
  665.         if(y1<ymin) outcode1|=2;
  666.         if(x1>xmax) outcode1|=4;
  667.         if(x1<xmin) outcode1|=8;
  668.         outcode2=0;
  669.         if(y2>ymax) outcode2|=1;
  670.         if(y2<ymin) outcode2|=2;
  671.         if(x2>xmax) outcode2|=4;
  672.         if(x2<xmin) outcode2|=8;
  673.         if((outcode1&outcode2)!=0) return FALSE;
  674.         if(((outcode1==0)&&(outcode2==0))) return TRUE;
  675.  
  676.         if(!(outcode1&15))
  677.             {
  678.             t=outcode1;
  679.             outcode1=outcode2;
  680.             outcode2=t;
  681.             t=x1;x1=x2;x2=t;
  682.             t=y1;y1=y2;y2=t;
  683.             }
  684.         if(outcode1&1)
  685.             {
  686.             x1=x1+(x2-x1)*(ymax-y1)/(y2-y1);
  687.             y1=ymax;
  688.             }
  689.         else
  690.             {
  691.             if(outcode1&2)
  692.                 {
  693.                 x1=x1+(x2-x1)*(ymin-y1)/(y2-y1);
  694.                 y1=ymin;
  695.                 }
  696.             else
  697.                 {
  698.                 if(outcode1&4)
  699.                     {
  700.                     y1=y1+(y2-y1)*(xmax-x1)/(x2-x1);
  701.                     x1=xmax;
  702.                     }
  703.                 else
  704.                     {
  705.                     if(outcode1&8)
  706.                         {
  707.                         y1=y1+(y2-y1)*(xmin-x1)/(x2-x1);
  708.                         x1=xmin;
  709.                         }
  710.                     }
  711.                 }
  712.             }
  713.         }
  714. }
  715.  
  716. /*--------------------------------------------------------------------------*/
  717.  
  718. void ReverseNodes(struct Node *tn)
  719. {
  720.     if((tn->chright & 0x8000) == 0)
  721.         {
  722.         ReverseNodes(tn->nextr);
  723.         tn->chright = tn->nextr->node_num;
  724.         }
  725.     if((tn->chleft & 0x8000) == 0)
  726.         {
  727.         ReverseNodes(tn->nextl);
  728.         tn->chleft = tn->nextl->node_num;
  729.         }
  730.     pnodes[pnode_indx].x = tn->x;
  731.     pnodes[pnode_indx].y = tn->y;
  732.     pnodes[pnode_indx].dx = tn->dx;
  733.     pnodes[pnode_indx].dy = tn->dy;
  734.     pnodes[pnode_indx].maxy1 = tn->maxy1;
  735.     pnodes[pnode_indx].miny1 = tn->miny1;
  736.     pnodes[pnode_indx].minx1 = tn->minx1;
  737.     pnodes[pnode_indx].maxx1 = tn->maxx1;
  738.     pnodes[pnode_indx].maxy2 = tn->maxy2;
  739.     pnodes[pnode_indx].miny2 = tn->miny2;
  740.     pnodes[pnode_indx].minx2 = tn->minx2;
  741.     pnodes[pnode_indx].maxx2 = tn->maxx2;
  742.     pnodes[pnode_indx].chright = tn->chright;
  743.     pnodes[pnode_indx].chleft = tn->chleft;
  744.     pnode_indx++;
  745.     tn->node_num = num_pnodes++;
  746. }
  747.  
  748. /*--------------------------------------------------------------------------*/
  749.  
  750. inline void progress()
  751. {
  752.     char *s="/-\\|/-\\|";
  753.  
  754.     if((pcnt&15) == 0)
  755.         {
  756.  
  757.         printf("%c\b",s[((pcnt)/16)&7]);
  758.         fflush(stdout);
  759.  
  760.         }
  761.     pcnt++;
  762.  
  763. }
  764.  
  765. /*- end of file ------------------------------------------------------------*/
  766.