home *** CD-ROM | disk | FTP | other *** search
/ Microsoft Programmer's Library 1.3 / Microsoft-Programers-Library-v1.3.iso / sampcode / video / 8 / 8_4.c < prev    next >
Encoding:
C/C++ Source or Header  |  1988-08-11  |  6.8 KB  |  348 lines
  1. /* Listing 8-3 */
  2.  
  3. #define    BLOCKED        1
  4. #define    UNBLOCKED    2
  5. #define    TRUE        1
  6. #define    FALSE        0
  7.  
  8. struct    BPstruct            /* table of border pixels */
  9. {
  10.     int    x,y;
  11.     int    flag;
  12. }
  13.     BP[3000];            /* (increase if necessary) */
  14.  
  15. int    BPstart;            /* start of table */
  16. int    BPend = 0;            /* first empty cell in table */
  17. int    FillValue;            /* value of pixels in filled region */
  18. int    BorderValue;            /* value of pixels in border */
  19.  
  20.  
  21. BorderFill( x, y )
  22. int    x,y;
  23. {
  24.     do                /* do until entire table has been scanned */
  25.     {
  26.       TraceBorder( x, y );        /* trace border starting at x,y */
  27.       SortBP( BP );            /* sort the border pixel table */
  28.       ScanRegion( &x, &y );        /* look for holes in the interior */
  29.     }
  30.     while (BPstart < BPend);
  31.  
  32.     FillRegion();            /* use the table to fill the interior */
  33. }
  34.  
  35.  
  36. ScanRegion( x, y )
  37. int    *x,*y;
  38. {
  39.     int    i = BPstart;
  40.     int    xr;
  41.  
  42.     while (i<BPend)
  43.     {
  44.       if (BP[i].flag == BLOCKED)        /* skip pixel if blocked */
  45.         ++i;
  46.  
  47.       else
  48.       if (BP[i].y != BP[i+1].y)        /* skip pixel if last in line */
  49.         ++i;
  50.  
  51.       else
  52.       {                    /* if at least one pixel to fill .. */
  53.         if (BP[i].x < BP[i+1].x-1)        /* .. scan the line */
  54.         {
  55.           xr = ScanRight( BP[i].x+1, BP[i].y );
  56.  
  57.           if (xr<BP[i+1].x)            /* if a border pixel is found .. */
  58.           {
  59.         *x = xr;            /* .. return its x,y coordinates */
  60.         *y = BP[i].y;
  61.         break;
  62.           }
  63.         }
  64.  
  65.         i += 2;                /* advance past this pair of pixels */
  66.       }
  67.     }
  68.  
  69.     BPstart = i;
  70. }
  71.  
  72.  
  73. SortBP()            /* uses Microsoft C library quicksort routine */
  74. {
  75.     int    CompareBP();
  76.  
  77.     qsort( BP+BPstart, BPend-BPstart, sizeof(struct BPstruct), CompareBP );
  78. }
  79.  
  80.  
  81. CompareBP( arg1, arg2 )        /* returns -1 if arg1 < arg2 */
  82. struct    BPstruct  *arg1,*arg2;
  83. {
  84.     int    i;
  85.  
  86.     i = arg1->y - arg2->y;        /* sort by y-coordinate */
  87.     if (i!=0)
  88.       return( (i<0) ? -1 : 1 );    /* (return -1 if i<0, 1 if i>0) */
  89.  
  90.     i = arg1->x - arg2->x;        /* sort by x-coordinate */
  91.     if (i!=0)
  92.       return( (i<0) ? -1 : 1 );
  93.  
  94.     i = arg1->flag - arg2->flag;    /* sort by flag */
  95.       return( (i<0) ? -1 : 1 );
  96. }
  97.  
  98.  
  99. FillRegion()
  100. {
  101.     int    i;
  102.  
  103.  
  104.     for(i=0; i<BPend;)
  105.     {
  106.       if (BP[i].flag == BLOCKED)        /* skip pixel if blocked */
  107.         ++i;
  108.  
  109.       else
  110.       if (BP[i].y != BP[i+1].y)        /* skip pixel if last in line */
  111.         ++i;
  112.  
  113.       else
  114.       {                    /* if at least one pixel to fill .. */
  115.         if (BP[i].x < BP[i+1].x-1)        /* .. draw a line */
  116.           Line( BP[i].x+1, BP[i].y, BP[i+1].x-1, BP[i+1].y, FillValue );
  117.  
  118.         i += 2;
  119.       }
  120.     }
  121. }
  122.  
  123.  
  124. /* border tracing routine */
  125.  
  126. struct    BPstruct CurrentPixel;
  127. int    D;                /* current search direction */
  128. int    PrevD;                /* previous search direction */
  129. int    PrevV;                /* previous vertical direction */
  130.  
  131.  
  132. TraceBorder( StartX, StartY )
  133. int    StartX,StartY;
  134. {
  135.     int    NextFound;        /* flags */
  136.     int    Done;
  137.  
  138. /* initialize */
  139.  
  140.     CurrentPixel.x = StartX;
  141.     CurrentPixel.y = StartY;
  142.  
  143.     D = 6;                /* current search direction */
  144.     PrevD = 8;            /* previous search direction */
  145.     PrevV = 2;            /* most recent vertical direction */
  146.  
  147. /* loop around the border until returned to the starting pixel */
  148.  
  149.     do
  150.     {
  151.       NextFound = FindNextPixel();
  152.       Done =
  153.        (CurrentPixel.x == StartX) && (CurrentPixel.y == StartY);
  154.     }
  155.     while (NextFound && !Done);
  156.  
  157. /* if only one pixel in border, add it twice to the table */
  158.  
  159.     if (!NextFound)                /* pixel has no neighbors */
  160.     {
  161.       AppendBPList( StartX, StartY, UNBLOCKED );
  162.       AppendBPList( StartX, StartY, UNBLOCKED );
  163.     }
  164.  
  165. /* if last search direction was upward, add the starting pixel to the table */
  166.  
  167.     else
  168.     if ( (PrevD <= 3) && (PrevD >= 1) )
  169.       AppendBPList( StartX, StartY, UNBLOCKED );
  170. }    
  171.  
  172.  
  173. FindNextPixel( )
  174. {
  175.     int    i;
  176.     int    flag;
  177.  
  178.  
  179.     for (i=-1; i<=5; i++)
  180.     {
  181.       flag = FindBP( (D+i) & 7 );        /* search for next border pixel */
  182.       if (flag)                /* flag is TRUE if found */
  183.       {
  184.         D = (D+i) & 6;            /* (D+i) MOD 2 */
  185.         break;                /* exit from loop */
  186.       }
  187.     }
  188.  
  189.     return(flag);
  190. }
  191.  
  192.  
  193. FindBP( d )
  194. int    d;            /* direction to search for next border pixel */
  195. {
  196.     int    x,y;
  197.  
  198.     x = CurrentPixel.x;
  199.     y = CurrentPixel.y;
  200.  
  201.  
  202.     NextXY( &x, &y, d );        /* get x,y of pixel in direction d */
  203.  
  204.     if ( BorderValue == ReadPixel( x, y ) )
  205.     {
  206.       AddBPList( d );        /* add pixel at x,y to table */
  207.       CurrentPixel.x = x;        /* pixel at x,y becomes current pixel */
  208.       CurrentPixel.y = y;
  209.       return( TRUE );
  210.     }
  211.  
  212.     else
  213.       return( FALSE );
  214. }
  215.  
  216.  
  217. NextXY( x, y, Direction )
  218. int    *x,*y;
  219. int    Direction;
  220. {
  221.     switch( Direction )        /*   3 2 1   */
  222.     {                /*   4   0   */
  223.       case 1:            /*   5 6 7   */
  224.       case 2:
  225.       case 3:
  226.  
  227.         *y -= 1;        /* up */
  228.         break;
  229.       case 5:
  230.       case 6:
  231.       case 7:
  232.         *y += 1;        /* down */
  233.         break;
  234.     }
  235.  
  236.     switch(Direction)
  237.     {
  238.       case 3:
  239.       case 4:
  240.       case 5:
  241.         *x -= 1;        /* left */
  242.         break;
  243.       case 1:
  244.       case 0:
  245.       case 7:
  246.         *x += 1;        /* right */
  247.         break;
  248.     }
  249. }
  250.  
  251.  
  252. AddBPList( d )
  253. int    d;
  254. {
  255.     if (d == PrevD)
  256.       SameDirection();
  257.  
  258.     else
  259.     {
  260.       DifferentDirection( d );
  261.       PrevV = PrevD;            /* new previous vertical direction */ 
  262.     }
  263.     
  264.     PrevD = d;                /* new previous search direction */
  265. }
  266.  
  267. SameDirection()
  268. {
  269.     if (PrevD == 0)                /* moving right ... */
  270.       BP[BPend-1].flag = BLOCKED;        /* .. block previous pixel */
  271.  
  272.     else
  273.     if (PrevD != 4)                /* if not moving horizontally */
  274.       AppendBPList( CurrentPixel.x, CurrentPixel.y, UNBLOCKED );
  275. }
  276.  
  277.  
  278. DifferentDirection( d )
  279. int    d;
  280. {
  281.  
  282. /* previously moving left */
  283.  
  284.     if (PrevD == 4)
  285.     {
  286.       if (PrevV == 5)            /* if from above .. */
  287.         BP[BPend-1].flag = BLOCKED;        /* .. block rightmost in line */
  288.  
  289.       AppendBPList( CurrentPixel.x, CurrentPixel.y, BLOCKED );
  290.     }
  291.  
  292. /* previously moving right */
  293.  
  294.     else
  295.     if (PrevD == 0)                /* previously moving right .. */
  296.     {
  297.       BP[BPend-1].flag = BLOCKED;        /* .. block rightmost in line */
  298.  
  299.       if (d == 7)                /* if line started from above */
  300.         AppendBPList( CurrentPixel.x, CurrentPixel.y, BLOCKED );
  301.       else
  302.         AppendBPList( CurrentPixel.x, CurrentPixel.y, UNBLOCKED );
  303.     }
  304.  
  305. /* previously moving in some vertical direction */
  306.  
  307.     else
  308.     {
  309.       AppendBPList( CurrentPixel.x, CurrentPixel.y, UNBLOCKED );
  310.  
  311. /* add pixel twice if local vertical maximum or minimum */
  312.  
  313.       if ( ( (d>=1) && (d<=3) ) && ( (PrevD >= 5) && (PrevD <= 7) ) ||
  314.            ( (d>=5) && (d<=7) ) && ( (PrevD >= 1) && (PrevD <= 3) ) )
  315.         AppendBPList( CurrentPixel.x, CurrentPixel.y, UNBLOCKED );
  316.     }
  317. }
  318.  
  319.  
  320. AppendBPList( p, q, f )
  321. int    p,q;            /* pixel x,y coordinates */
  322. int    f;            /* flag */
  323. {
  324.     BP[BPend].x = p;
  325.     BP[BPend].y = q;
  326.     BP[BPend].flag = f;
  327.  
  328.     ++BPend;        /* increment past last entry in table */
  329. }
  330.  
  331.  
  332. /* routine to scan a line for a border pixel */
  333.  
  334. int    Xmax;            /* largest valid pixel x-coordinate */
  335.  
  336. ScanRight( x, y )
  337. int    x,y;
  338. {
  339.     while ( ReadPixel( x, y ) != BorderValue )
  340.     {
  341.       ++x;                /* increment x */
  342.       if (x==Xmax)            /* if end of line in buffer .. */
  343.         break;            /* .. exit from the loop */
  344.     }
  345.  
  346.     return( x );
  347. }
  348.