home *** CD-ROM | disk | FTP | other *** search
/ gdead.berkeley.edu / gdead.berkeley.edu.tar / gdead.berkeley.edu / pub / cad-tools / ciftomann.tar / boxer.c < prev    next >
C/C++ Source or Header  |  1988-01-28  |  7KB  |  318 lines
  1. #include "boxer.h"
  2. #include "aeledge.h"
  3. #include "ciftomann.h"
  4. #include <stdio.h>
  5. #include "fd.h"
  6. #include "Out_Box.h"
  7.  
  8. typedef enum {     /* the different types of changes an edge can cause */
  9.     BEGIN,
  10.     LEFT_GROW,
  11.     RIGHT_GROW,
  12.     JOIN,
  13.     END,
  14.     LEFT_SHRINK,
  15.     RIGHT_SHRINK,
  16.     SPLIT,
  17.     BAD_EDGE
  18. } edge_desc;
  19.  
  20. edge_desc edge_type();
  21. AEL_EDGEPTR MakeEdge();
  22. static AEL_EDGEPTR GetEdge();
  23. char *malloc();
  24. static EmitBox();
  25.  
  26. static AEL_LIST AEList;
  27. static AEL_EDGE medge;
  28. static AEL_EDGEPTR AEdge,
  29.                    MEdge;
  30.  
  31. /*
  32.     boxer : reads edges from standard in and through a scan_line 
  33.            algorithm, breaks up the manhatten geometry into boxes,
  34.            writing them on standard output. Both input and output
  35.            are in binary, as boxer is designed to be one section
  36.            of the ciftomann pipeline, placed between the resorter
  37.            and smash
  38.  */
  39.  
  40. main()
  41. {
  42.  
  43.     int CurrentY;
  44.  
  45.     ProgName = "Boxer";
  46.  
  47.     /* Instead of checking for ends of the doubly linked active
  48.        edge list all the time, I put two dummy points in at plus
  49.        and minus infinity instead. Hopefully no real coordinate
  50.        will be be outside these two points, so I don`t have to
  51.        worry about any operations on the endpoints 
  52.      */
  53.     AEList.top = MakeEdge(-INFINITY,-INFINITY,-INFINITY,1,NIL,NIL);
  54.     AEList.bottom = MakeEdge(INFINITY,INFINITY,-INFINITY,1,NIL,NIL);
  55.     AEList.bottom->last = AEList.top;
  56.     AEList.top->next = AEList.bottom;
  57.  
  58.     MEdge = GetEdge();
  59.     AEdge = AEList.top;
  60.  
  61.     if ( MEdge == NIL ) {
  62.     exit(0);
  63.     }
  64.     
  65.     do {
  66.  
  67.     AEdge = AEList.top;
  68.     CurrentY = MEdge->y;
  69.  
  70.         /* Find the proper place in the scanline for the
  71.            new edge */
  72.  
  73.     while ( Greater_than_Equal(MEdge->x, AEdge->next->x) )  {
  74.         Inc(AEdge);
  75.     }
  76.     
  77.         /* Decide what to do on the basis of the change in
  78.            geometry caused by the new edge */
  79.  
  80.     switch ( edge_type(MEdge) ) {
  81.         
  82.         case BEGIN :
  83.         
  84.             /* Entering a new region of geometry */
  85.  
  86.         InsertAbove(AEdge->next,MEdge->x,MEdge->xend,
  87.                 MEdge->y,MEdge->sense);
  88.         break;
  89.  
  90.         case LEFT_GROW :
  91.             
  92.             /* the new edge abuts AEdge->next, so
  93.                emit a box upto AEdge->next and merge 
  94.                MEdege and AEdge->next  */
  95.  
  96.         EmitBox(AEdge->next,CurrentY);
  97.         AEdge->next->x = MEdge->x;
  98.         AEdge->next->y = CurrentY;
  99.         break;
  100.  
  101.         case RIGHT_GROW :
  102.             
  103.             /* the new edge abuts AEdge, so
  104.                emit a box upto AEdge and merge 
  105.                MEdege and AEdge  */
  106.  
  107.         EmitBox(AEdge,CurrentY);
  108.         AEdge->xend = MEdge->xend;
  109.         AEdge->y = CurrentY;
  110.         break;
  111.  
  112.         case JOIN :
  113.  
  114.             /* MEdge abuts AEdge on the left and  AEdge->next
  115.                on the right, so emit a box for both and merge
  116.                the three edges into one  */
  117.  
  118.         EmitBox(AEdge,CurrentY);
  119.         EmitBox(AEdge->next,CurrentY);
  120.         AEdge->xend = AEdge->next->xend;
  121.         AEdge->y = CurrentY;
  122.         Remove(AEList,AEdge->next);
  123.         break;
  124.  
  125.         case END :
  126.  
  127.             /* We have just closed off a piece of geometry
  128.                so emit and  remove */
  129.  
  130.         EmitBox(AEdge,CurrentY);
  131.         AEdge = AEdge->last;
  132.         Remove(AEList,AEdge->next);
  133.         break;
  134.  
  135.         case LEFT_SHRINK :
  136.  
  137.             /* Medge closed off part of AEdge, so
  138.                emit and shrink */
  139.             
  140.         EmitBox(AEdge,CurrentY);
  141.         AEdge->x = MEdge->xend;
  142.         AEdge->y = CurrentY;
  143.         AEdge = AEdge->last;
  144.         break;
  145.  
  146.         case RIGHT_SHRINK :
  147.  
  148.             /* Medge closed off part of AEdge, so
  149.                emit and shrink */
  150.             
  151.         EmitBox(AEdge,CurrentY);
  152.         AEdge->xend = MEdge->x;
  153.         AEdge->y = CurrentY;
  154.         break;
  155.  
  156.         case SPLIT :
  157.  
  158.             /* MEdge splits  AEdge into two fragements,
  159.                so emit and split */
  160.  
  161.         EmitBox(AEdge,CurrentY);
  162.         InsertAbove(AEdge->next,MEdge->xend,AEdge->xend,
  163.                 CurrentY,UP);
  164.         AEdge->xend = MEdge->x;
  165.         AEdge->y = CurrentY;
  166.         break;
  167.  
  168.         case BAD_EDGE :
  169.  
  170.             /* Something impossible has happened, blame
  171.                grow shrink and exit */
  172.  
  173.         fprintf(stderr,"Error : possible bad grow/shrink around  x = %d to %d, y = %d\n",MEdge->x,MEdge->xend,MEdge->y);
  174.         exit(1);
  175.         break;
  176.  
  177.         default :
  178.         panic("Impossible return from edge_type");
  179.  
  180.     } /* end of case */
  181.  
  182.     MEdge = GetEdge();
  183.  
  184.     } while (MEdge != NIL);
  185.  
  186.     if (AEList.top->next  != AEList.bottom) {
  187.     panic("Unterminated upperward edge at closing");
  188.     }
  189.     
  190.     exit(0);
  191. }
  192.  
  193.     /* read an edge from standard input. The  reason for
  194.        the recopying of the edge is that, for space reasons,
  195.        the output format for edges is different from the internal
  196.        one
  197.      */
  198. static AEL_EDGEPTR GetEdge()
  199. {
  200.     static EDGE redge;
  201.     int status;
  202.  
  203.     if ( fread((char *)&redge, sizeof(EDGE), 1, stdin) 
  204.         == 0 ) {
  205.     return(NIL);
  206.     }
  207.  
  208.     medge.x = redge.x;
  209.     medge.xend = redge.xend;
  210.     medge.y = redge.y;
  211.     medge.sense = redge.sense;
  212.     return(&medge);
  213. }
  214.  
  215. #ifdef DEBUG
  216. BDump() 
  217. {
  218.     AEL_EDGEPTR edge = AEList.top;
  219.  
  220.     while (edge != NIL) {
  221.     PrintEdge(edge);
  222.     edge = edge->next;
  223.     }
  224. }
  225. #endif
  226.  
  227. /*
  228.     Emit a box in left, bottom, right, top format
  229.  */
  230. static EmitBox(BottomEdge,TopY)
  231. AEL_EDGEPTR BottomEdge;
  232. int TopY;
  233. {
  234.     OUT_BOX box;
  235.  
  236.     box.xmax = BottomEdge->xend;
  237.     box.xmin = BottomEdge->x;
  238.     box.ymax = TopY;
  239.     box.ymin = BottomEdge->y;
  240.  
  241.     if (box.ymax == box.ymin) {
  242.  
  243. #ifdef DEBUG
  244.     fprintf(stderr,"Zero box , %d at %d,%d\n",box.xmax - box.xmin,
  245.             box.xmin,box.ymin);
  246. #endif
  247.  
  248.     return;
  249.     }
  250.  
  251. #ifdef DEBUG
  252.     fprintf(stderr,"Boxer : Box from %d,%d to %d,%d\n",box.xmin,
  253.         box.ymin, box.xmax, box.ymax);
  254. #endif
  255.  
  256.     if ( fwrite(&box, sizeof(box), 1, stdout) == 0 ) {
  257.     panic("Bad write in EmitBox");
  258.     }
  259. }
  260.  
  261. /*
  262.     Figure out the change in the geometry induced  by the edge.
  263.     sense == UP means the interior is on high-Y side of the edge.
  264.     x is the x coordinate of the left side of the edge, xend is
  265.     the x coordinate of the right side of the edge. (i.e x < xend)
  266.  */
  267. edge_desc edge_type(M)
  268. AEL_EDGEPTR M;
  269. {
  270.     if ( M->sense == UP ) {
  271.  
  272.     if ( M->x > AEdge->xend ) {
  273.         if (M->xend < AEdge->next->x) {
  274.         return (BEGIN);
  275.         } else if ( M->xend == AEdge->next->x ) {
  276.         return (LEFT_GROW);
  277.         } else {
  278.         return (BAD_EDGE);
  279.         }
  280.     } else if ( M->x == AEdge->xend ) {
  281.         if ( M->xend < AEdge->next->x ) {
  282.         return (RIGHT_GROW);
  283.         } else if ( M->xend == AEdge->next->x) {
  284.         return (JOIN);
  285.         } else {
  286.         return (BAD_EDGE);
  287.         }
  288.     } else {
  289.         return (BAD_EDGE);
  290.     }
  291.  
  292.     } else if (M->sense == DOWN) {
  293.  
  294.     if ( M->x == AEdge->x ) {
  295.         if ( M->xend == AEdge->xend ) {
  296.         return (END);
  297.         } else if ( M->xend < AEdge->xend ) {
  298.         return (LEFT_SHRINK);
  299.         } else {
  300.         return (BAD_EDGE);
  301.         }
  302.     } else if ( M->xend == AEdge->xend ) {
  303.         if ( M->x > AEdge->x ) {
  304.         return (RIGHT_SHRINK);
  305.         } else {
  306.         return (BAD_EDGE);
  307.         }
  308.     } else if ( M->x > AEdge->x && M->xend < AEdge->xend ) {
  309.         return (SPLIT);
  310.     } else {
  311.         return (BAD_EDGE);
  312.     }
  313.  
  314.     } else {
  315.     return (BAD_EDGE);
  316.     }
  317. }
  318.