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