home *** CD-ROM | disk | FTP | other *** search
/ gdead.berkeley.edu / gdead.berkeley.edu.tar / gdead.berkeley.edu / pub / cad-tools / ciftomann.tar / edger_dir / edge_polygon.c < prev    next >
C/C++ Source or Header  |  1988-01-28  |  7KB  |  321 lines
  1. #include "ciftomann.h"
  2. #include "intersection.h"
  3. #include "aeledge.h"
  4. #include <stdio.h>
  5. #include "fd.h"
  6.  
  7. static AEL_LIST AEList;
  8. static AEL_EDGE medge;
  9. static AEL_EDGEPTR AEdge;
  10. static int CurrentY;
  11.  
  12. extern FILE *out_desc;
  13.  
  14. AEL_EDGEPTR MakeEdge();
  15. static AEL_EDGEPTR GetEdge();
  16.  
  17.     /*
  18.      *    Convert an arbitrary Manhatten polygon into edges. 
  19.      *    A scan_line algorithm is used in a process almost
  20.      *    identical to the merging process. See the code for
  21.      *    merge for further comments.
  22.      *        Self-intersecting polygons are handled 
  23.      * properly through comparison of the relative sense
  24.      * of any edge and the first edge encountered (which
  25.      * must be an exterior edge) and keeping a running total
  26.      * of the depth of overlap on the scan-line at all times.
  27.      */    
  28.  
  29. edge_polygon()
  30. {
  31.  
  32.  
  33.     AEL_EDGEPTR MEdge,
  34.             Position;
  35.     
  36.     AEList.bottom = MakeEdge(INFINITY,INFINITY,-INFINITY,1,NIL,NIL);
  37.     AEList.top = MakeEdge(-INFINITY,-INFINITY,-INFINITY,1,NIL,NIL);
  38.  
  39.     AEList.top->next = AEList.bottom;
  40.     AEList.bottom->last = AEList.top;
  41.  
  42.     MEdge = GetEdge();
  43.  
  44.     ProgName = "FixPolygon";
  45.  
  46.     do {
  47.  
  48.     CurrentY = MEdge->y;
  49.     AEdge = AEList.top;
  50.  
  51.     do {
  52.         
  53.         /* find the proper location on the scanline */
  54.  
  55.         while ( Greater_than_Equal(MEdge->x, AEdge->next->x) )
  56.         AEdge = AEdge->next;
  57.  
  58.         Position = AEdge->last;
  59.  
  60.         do {
  61.         Update(MEdge);
  62.         AEdge = AEdge->next;
  63.         } while (MEdge->sense != 0);
  64.  
  65.         MEdge = GetEdge();
  66.  
  67.         if (Position != NIL)
  68.         AEdge = Position;
  69.         else
  70.         AEdge = AEList.top;
  71.  
  72.     } while (MEdge != NIL && MEdge->y == CurrentY);
  73.  
  74.     ClearEmit();
  75.  
  76.     } while (MEdge != NIL);
  77.  
  78.     if (AEList.top->next != AEList.bottom) 
  79.     panic("Unterminated upward edges at end of merge");
  80. }
  81.  
  82. static Update(M)
  83. AEL_EDGEPTR M;
  84. {
  85.  
  86.     switch (Intersection(AEdge,M)) {
  87.  
  88.     case COINCIDENT :    /*     M---------M
  89.                     C---------C         */
  90.  
  91.         AEdge->sense += M->sense;
  92.         M->sense = 0;
  93.  
  94.         if (AEdge->sense == 0) {
  95.         AEdge = AEdge->last;
  96.         EmitEdge(AEdge->next,DOWN);
  97.         Remove(AEList,AEdge->next);
  98.         }
  99.         break;
  100.  
  101.     case A_LCOVERS_M :    /*    M---------M
  102.                     C------------C        */
  103.  
  104.         AEdge->x = M->xend;
  105.         InsertAbove(AEdge,M->x,M->xend,CurrentY,AEdge->sense + M->sense);
  106.         M->sense = 0;
  107.  
  108.         if (AEdge->last->sense == 0) {
  109.         EmitEdge(AEdge->last,DOWN);
  110.         Remove(AEList,AEdge->last);
  111.         }
  112.         break;
  113.  
  114.     case M_LCOVERS_A :    /*    M------------M
  115.                     C---------C        */
  116.  
  117.         M->x = AEdge->xend;
  118.         AEdge->sense += M->sense;
  119.  
  120.         if (AEdge->sense == 0) {
  121.         AEdge = AEdge->last;
  122.         EmitEdge(AEdge->next,DOWN);
  123.         Remove(AEList,AEdge->next);
  124.         }
  125.         break;
  126.  
  127.     case LDISJOINT :    /*    M------M
  128.                          C----C        */
  129.  
  130.     case LPOINT :        /*    M------M
  131.                            C-----C        */
  132.         
  133.         InsertAbove(AEdge,M->x,M->xend,CurrentY,M->sense);
  134.         EmitEdge(AEdge->last,UP);
  135.         M->sense = 0;
  136.         break;
  137.  
  138.  
  139.     case M_RCOVERS_A :    /*    M------------M
  140.                          C-------C        */
  141.  
  142.         InsertAbove(AEdge,M->x,AEdge->x,CurrentY,M->sense);
  143.         EmitEdge(AEdge->last,UP);
  144.         AEdge->sense += M->sense;
  145.         M->sense = 0;
  146.  
  147.         if (AEdge->sense == 0) {
  148.         AEdge = AEdge->last;
  149.         EmitEdge(AEdge->next,DOWN);
  150.         Remove(AEList,AEdge->next);
  151.         }
  152.         break;
  153.  
  154.     case LOVERLAP :        /*    M-------M
  155.                           C------C        */
  156.  
  157.         InsertAbove(AEdge,M->x,AEdge->x,CurrentY,M->sense);
  158.         EmitEdge(AEdge->last,UP);
  159.         InsertAbove(AEdge,AEdge->x,M->xend,CurrentY,AEdge->sense + M->sense);
  160.         M->sense = 0;
  161.  
  162.         AEdge->x = M->xend;
  163.         if (AEdge->last->sense == 0) {
  164.         EmitEdge(AEdge->last,DOWN);
  165.         Remove(AEList,AEdge->last);
  166.         }
  167.         break;
  168.  
  169.     case M_COVERS_A :    /*    M------------M
  170.                       C--------C        */
  171.  
  172.         InsertAbove(AEdge,M->x,AEdge->x,CurrentY,M->sense);
  173.         EmitEdge(AEdge->last,UP);
  174.         AEdge->sense += M->sense;
  175.         M->x = AEdge->xend;
  176.  
  177.         if (AEdge->sense == 0) {
  178.         AEdge = AEdge->last;
  179.         EmitEdge(AEdge->next,DOWN);
  180.         Remove(AEList,AEdge->next);
  181.         }
  182.         break;
  183.  
  184.     case RDISJOINT :    /*            M-----M
  185.                     C-----C            */
  186.         
  187.     case RPOINT :        /*           M-----M
  188.                     C------C        */
  189.         
  190.         break;
  191.  
  192.     case A_RCOVERS_M :    /*           M-----M
  193.                     C------------C        */
  194.  
  195.         InsertAbove(AEdge,AEdge->x,M->x,CurrentY,AEdge->sense);
  196.         AEdge->x = M->x;
  197.         AEdge->sense += M->sense;
  198.         M->sense = 0;
  199.  
  200.         if (AEdge->sense == 0) {
  201.         AEdge = AEdge->last;
  202.         EmitEdge(AEdge->next,DOWN);
  203.         Remove(AEList,AEdge->next);
  204.         }
  205.         break;
  206.  
  207.     case A_COVERS_M :    /*      M--------M
  208.                     C------------C        */
  209.  
  210.         InsertAbove(AEdge,AEdge->x,M->x,CurrentY,AEdge->sense);
  211.         InsertAbove(AEdge,M->x,M->xend,CurrentY,AEdge->sense + M->sense);
  212.         AEdge->x = M->xend;
  213.         M->sense = 0;
  214.  
  215.         if (AEdge->last->sense == 0) {
  216.         EmitEdge(AEdge->last,DOWN);
  217.         Remove(AEList,AEdge->last);
  218.         }
  219.         break;
  220.  
  221.     case ROVERLAP :        /*          M------M
  222.                     C-------C        */
  223.  
  224.         InsertAbove(AEdge,AEdge->x,M->x,CurrentY,AEdge->sense);
  225.         AEdge->x = M->x;
  226.         AEdge->sense += M->sense;
  227.         M->x = AEdge->xend;
  228.  
  229.         if (AEdge->sense == 0) {
  230.         AEdge = AEdge->last;
  231.         EmitEdge(AEdge->next,DOWN);
  232.         Remove(AEList,AEdge->next);
  233.         }
  234.         break;
  235.     }
  236. }
  237.  
  238. extern EDGE EdgeArray[];
  239. extern int NumEdges;
  240. extern int ArrayIndex;
  241.  
  242. static AEL_EDGEPTR GetEdge()
  243. {
  244.  
  245.     if (ArrayIndex < NumEdges) {
  246.     medge.x = EdgeArray[ArrayIndex].x;
  247.     medge.xend = EdgeArray[ArrayIndex].xend;
  248.     medge.sense = EdgeArray[ArrayIndex].sense;
  249.     medge.y = EdgeArray[ArrayIndex].y;
  250.     ArrayIndex++;
  251.     return(&medge);
  252.     } else
  253.     return(NIL);
  254. }
  255.  
  256. #define SAVE(edge) { redge.x = edge->x;\
  257.              redge.xend = edge->xend;\
  258.                      redge.sense = sense;\
  259.                      redge.y = CurrentY;\
  260.              Empty = 0; }
  261.  
  262. static int Empty = 1;
  263. static EDGE redge;
  264.  
  265. static EmitEdge(edge,sense) 
  266. AEL_EDGEPTR edge;
  267. int sense;
  268. {
  269.  
  270.     if (Empty) 
  271.     SAVE(edge)
  272.     else {
  273.     if (redge.sense == sense && redge.xend == edge->x) 
  274.         redge.xend = edge->xend;
  275.     else if (redge.sense == -sense && redge.xend == edge->xend)
  276.         if (redge.x == edge->x)
  277.         Empty = 1;
  278.         else 
  279.         redge.xend = edge->x;
  280.     else {
  281. #ifdef DEBUG
  282.         fprintf(stderr,"Fix Emits %d->%d at %d : sense = %d\n",redge.x,
  283.             redge.xend,redge.y,redge.sense);
  284. #endif
  285.  
  286.         if ( fwrite((char *)&redge, sizeof(EDGE), 1, out_desc) == 0 )
  287.         panic("Bad write in EmitEdge");
  288.  
  289.         SAVE(edge);
  290.     }
  291.     }
  292. }
  293.  
  294. static ClearEmit() 
  295. {
  296.     if (!Empty) {
  297.     
  298. #ifdef DEBUG
  299.     fprintf(stderr,"Fix Emits %d->%d at %d : sense = %d\n",redge.x,
  300.         redge.xend,redge.y,redge.sense);
  301. #endif
  302.  
  303.     if ( fwrite((char *)&redge, sizeof(EDGE), 1, out_desc) == 0 )
  304.         panic("Bad write in EmitEdge");
  305.     
  306.     Empty = 1;
  307.     }
  308. }
  309.  
  310. #ifdef DEBUG
  311. FDump() 
  312. {
  313.     AEL_EDGEPTR edge = AEList.top;
  314.  
  315.     while (edge != NIL) {
  316.     PrintEdge(edge);
  317.     edge = edge->next;
  318.     }
  319. }
  320. #endif 
  321.