home *** CD-ROM | disk | FTP | other *** search
/ PC Pro 2002 April / pcpro0402.iso / essentials / graphics / Gimp / gimp-src-20001226.exe / src / gimp / app / blob.c < prev    next >
Encoding:
C/C++ Source or Header  |  2000-12-17  |  16.6 KB  |  775 lines
  1. /* blob.c: routines for manipulating scan converted convex
  2.  *         polygons.
  3.  *  
  4.  * Copyright 1998-1999, Owen Taylor <otaylor@gtk.org>
  5.  *
  6.  * > Please contact the above author before modifying the copy <
  7.  * > of this file in the GIMP distribution. Thanks.            <
  8.  * 
  9.  * This program is free software; you can redistribute it and/or modify
  10.  * it under the terms of the GNU General Public License as published by
  11.  * the Free Software Foundation; either version 2 of the License, or
  12.  * (at your option) any later version.
  13.  *
  14.  * This program is distributed in the hope that it will be useful,
  15.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17.  * GNU General Public License for more details.
  18.  *
  19.  * You should have received a copy of the GNU General Public License
  20.  * along with this program; if not, write to the Free Software
  21.  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  22. */
  23.  
  24. #include "config.h"
  25.  
  26. #include <stdio.h>
  27. #include <stdlib.h>
  28. #include <string.h>
  29.  
  30. #include <gtk/gtk.h>
  31.  
  32. #include "apptypes.h"
  33.  
  34. #include "appenv.h"
  35. #include "blob.h"
  36.  
  37. #include "libgimp/gimpmath.h"
  38.  
  39.  
  40. static Blob *
  41. blob_new (int y, int height)
  42. {
  43.   Blob *result;
  44.  
  45.   result = g_malloc (sizeof (Blob) +  sizeof(BlobSpan) * (height-1));
  46.   result->y = y;
  47.   result->height = height;
  48.  
  49.   return result;
  50. }
  51.  
  52. typedef enum {
  53.   EDGE_NONE = 0,
  54.   EDGE_LEFT = 1 << 0,
  55.   EDGE_RIGHT = 1 << 1
  56. } EdgeType;
  57.  
  58. static void
  59. blob_fill (Blob *b, EdgeType *present)
  60. {
  61.   int start;
  62.   int x1, x2, i1, i2;
  63.   int i;
  64.  
  65.   /* Mark empty lines at top and bottom as unused */
  66.  
  67.   start = 0;
  68.   while (!(present[start])) 
  69.     {
  70.       b->data[start].left = 0;
  71.       b->data[start].right = -1;
  72.       start++;
  73.     }
  74.   if (present[start] != (EDGE_RIGHT | EDGE_LEFT))
  75.     {
  76.       if (present[start] == EDGE_RIGHT)
  77.     b->data[start].left = b->data[start].right;
  78.       else
  79.     b->data[start].right = b->data[start].left;
  80.     
  81.       present[start] = EDGE_RIGHT | EDGE_LEFT;
  82.     }
  83.  
  84.   for (i=b->height-1;!present[i];i--)
  85.     {
  86.       b->data[i].left = 0;
  87.       b->data[i].right = -1;
  88.     }
  89.   if (present[i] != (EDGE_RIGHT | EDGE_LEFT))
  90.     {
  91.       if (present[i] == EDGE_RIGHT)
  92.     b->data[i].left = b->data[i].right;
  93.       else
  94.     b->data[i].right = b->data[i].left;
  95.     
  96.       present[i] = EDGE_RIGHT | EDGE_LEFT;
  97.     }
  98.  
  99.  
  100.   /* Restore missing edges  */
  101.  
  102.   /* We fill only interior regions of convex hull, as if we were filling
  103.      polygons. But since we draw ellipses with nearest points, not interior
  104.      points, maybe it would look better if we did the same here. Probably
  105.      not a big deal either way after anti-aliasing */
  106.  
  107.   /*     left edge */
  108.   for (i1=start; i1<b->height-2; i1++)
  109.     {
  110.       /* Find empty gaps */
  111.       if (!(present[i1+1] & EDGE_LEFT))
  112.     {
  113.       int increment;    /* fractional part */
  114.       int denom;        /* denominator of fraction */
  115.       int step;        /* integral step */
  116.       int frac;        /* fractional step */
  117.       int reverse;
  118.  
  119.       /* find bottom of gap */
  120.       i2 = i1+2;
  121.       while (!(present[i2] & EDGE_LEFT) && i2 < b->height) i2++;
  122.       
  123.       if (i2 < b->height)
  124.         {
  125.           denom = i2-i1;
  126.           x1 = b->data[i1].left;
  127.           x2 = b->data[i2].left;
  128.           step = (x2-x1)/denom;
  129.           frac = x2-x1 - step*denom;
  130.           if (frac < 0)
  131.         {
  132.           frac = -frac;
  133.           reverse = 1;
  134.         }
  135.           else
  136.         reverse = 0;
  137.           
  138.           increment = 0;
  139.           for (i=i1+1; i<i2; i++)
  140.         {
  141.           x1 += step;
  142.           increment += frac;
  143.           if (increment >= denom)
  144.             {
  145.               increment -= denom;
  146.               x1 += reverse ? -1 : 1;
  147.             }
  148.           if (increment == 0 || reverse)
  149.             b->data[i].left = x1;
  150.           else
  151.             b->data[i].left = x1 + 1;
  152.         }
  153.         }
  154.       i1 = i2-1;        /* advance to next possibility */
  155.     }
  156.     }
  157.  
  158.   /*     right edge */
  159.   for (i1=start; i1<b->height-2; i1++)
  160.     {
  161.       /* Find empty gaps */
  162.       if (!(present[i1+1] & EDGE_RIGHT))
  163.     {
  164.       int increment;    /* fractional part */
  165.       int denom;        /* denominator of fraction */
  166.       int step;        /* integral step */
  167.       int frac;        /* fractional step */
  168.       int reverse;
  169.  
  170.       /* find bottom of gap */
  171.       i2 = i1+2;
  172.       while (!(present[i2] & EDGE_RIGHT) && i2 < b->height) i2++;
  173.       
  174.       if (i2 < b->height)
  175.         {
  176.           denom = i2-i1;
  177.           x1 = b->data[i1].right;
  178.           x2 = b->data[i2].right;
  179.           step = (x2-x1)/denom;
  180.           frac = x2-x1 - step*denom;
  181.           if (frac < 0)
  182.         {
  183.           frac = -frac;
  184.           reverse = 1;
  185.         }
  186.           else
  187.         reverse = 0;
  188.           
  189.           increment = 0;
  190.           for (i=i1+1; i<i2; i++)
  191.         {
  192.           x1 += step;
  193.           increment += frac;
  194.           if (increment >= denom)
  195.             {
  196.               increment -= denom;
  197.               x1 += reverse ? -1 : 1;
  198.             }
  199.           if (reverse && increment != 0)
  200.             b->data[i].right = x1 - 1;
  201.           else
  202.             b->data[i].right = x1;
  203.         }
  204.         }
  205.       i1 = i2-1;        /* advance to next possibility */
  206.     }
  207.     }
  208.  
  209. }
  210.  
  211. static void
  212. blob_make_convex (Blob *b, EdgeType *present)
  213. {
  214.   int x1, x2, y1, y2, i1, i2;
  215.   int i;
  216.   int start;
  217.  
  218.   /* Walk through edges, deleting points that aren't on convex hull */
  219.  
  220.   start = 0;
  221.   while (!(present[start])) start++;
  222.  
  223.   /*    left edge */
  224.  
  225.   i1 = start-1; 
  226.   i2 = start;
  227.   x1 = b->data[start].left - b->data[start].right;
  228.   y1 = 0;
  229.   
  230.   for (i=start+1;i<b->height;i++)
  231.     {
  232.       if (!(present[i] & EDGE_LEFT))
  233.     continue;
  234.  
  235.       x2 = b->data[i].left - b->data[i2].left;
  236.       y2 = i-i2;
  237.       
  238.       while (x2*y1 - x1*y2 < 0) /* clockwise rotation */
  239.     {
  240.       present[i2] &= ~EDGE_LEFT;
  241.       i2 = i1;
  242.       while (!(present[--i1] & EDGE_LEFT) && i1>=start);
  243.  
  244.       if (i1<start)
  245.         {
  246.           x1 = b->data[start].left - b->data[start].right;
  247.           y1 = 0;
  248.         }
  249.       else
  250.         {
  251.           x1 = b->data[i2].left - b->data[i1].left;
  252.           y1 = i2 - i1;
  253.         }
  254.       x2 = b->data[i].left - b->data[i2].left;
  255.       y2 = i - i2;
  256.     }
  257.       x1 = x2;
  258.       y1 = y2;
  259.       i1 = i2;
  260.       i2 = i;
  261.     }
  262.  
  263.   /*     Right edge */
  264.  
  265.   i1 = start -1; 
  266.   i2 = start;
  267.   x1 = b->data[start].right - b->data[start].left;
  268.   y1 = 0;
  269.   
  270.   for (i=start+1;i<b->height;i++)
  271.     {
  272.       if (!(present[i] & EDGE_RIGHT))
  273.     continue;
  274.  
  275.       x2 = b->data[i].right - b->data[i2].right;
  276.       y2 = i-i2;
  277.       
  278.       while (x2*y1 - x1*y2 > 0) /* counter-clockwise rotation */
  279.     {
  280.       present[i2] &= ~EDGE_RIGHT;
  281.       i2 = i1;
  282.       while (!(present[--i1] & EDGE_RIGHT) && i1>=start);
  283.  
  284.       if (i1<start)
  285.         {
  286.           x1 = b->data[start].right - b->data[start].left;
  287.           y1 = 0;
  288.         }
  289.       else
  290.         {
  291.           x1 = b->data[i2].right - b->data[i1].right;
  292.           y1 = i2 - i1;
  293.         }
  294.       x2 = b->data[i].right - b->data[i2].right;
  295.       y2 = i - i2;
  296.     }
  297.       x1 = x2;
  298.       y1 = y2;
  299.       i1 = i2;
  300.       i2 = i;
  301.     }
  302.  
  303.   blob_fill (b, present);
  304. }
  305.  
  306. Blob *
  307. blob_convex_union (Blob *b1, Blob *b2)
  308. {
  309.   Blob *result;
  310.   int y;
  311.   int i, j;
  312.   EdgeType *present;
  313.  
  314.   /* Create the storage for the result */
  315.  
  316.   y = MIN(b1->y,b2->y);
  317.   result = blob_new (y, MAX(b1->y+b1->height,b2->y+b2->height)-y);
  318.  
  319.   if (result->height == 0)
  320.     return result;
  321.  
  322.   present = g_new0 (EdgeType, result->height);
  323.  
  324.   /* Initialize spans from original objects */
  325.  
  326.   for (i=0, j=b1->y-y; i<b1->height; i++,j++)
  327.     {
  328.       if (b1->data[i].right >= b1->data[i].left)
  329.     {
  330.       present[j] = EDGE_LEFT | EDGE_RIGHT;
  331.       result->data[j].left = b1->data[i].left;
  332.       result->data[j].right = b1->data[i].right;
  333.     }
  334.     }
  335.  
  336.   for (i=0, j=b2->y-y; i<b2->height; i++,j++)
  337.     {
  338.       if (b2->data[i].right >= b2->data[i].left)
  339.     {
  340.       if (present[j])
  341.         {
  342.           if (result->data[j].left > b2->data[i].left)
  343.         result->data[j].left = b2->data[i].left;
  344.           if (result->data[j].right < b2->data[i].right)
  345.         result->data[j].right = b2->data[i].right;
  346.         }
  347.       else
  348.         {
  349.           present[j] = EDGE_LEFT | EDGE_RIGHT;
  350.           result->data[j].left = b2->data[i].left;
  351.           result->data[j].right = b2->data[i].right;
  352.         }
  353.     }
  354.     }
  355.   
  356.   blob_make_convex (result, present);
  357.  
  358.   g_free (present);
  359.   return result;
  360. }
  361.  
  362. static void
  363. blob_line_add_pixel (Blob *b, int x, int y)
  364. {
  365.   if (b->data[y-b->y].left > b->data[y-b->y].right)
  366.     b->data[y-b->y].left = b->data[y-b->y].right = x;
  367.   else
  368.     {
  369.       b->data[y-b->y].left = MIN (b->data[y-b->y].left, x);
  370.       b->data[y-b->y].right = MAX (b->data[y-b->y].right, x);
  371.     }
  372. }
  373.  
  374. void
  375. blob_line (Blob *b, int x0, int y0, int x1, int y1)
  376. {
  377.   int dx, dy, d;
  378.   int incrE, incrNE;
  379.   int x, y;
  380.  
  381.   int xstep = 1;
  382.   int ystep = 1;
  383.   
  384.   dx = x1 - x0;
  385.   dy = y1 - y0;
  386.   
  387.   if (dx < 0)
  388.     {
  389.       dx = -dx;
  390.       xstep = -1;
  391.     }
  392.  
  393.   if (dy < 0)
  394.     {
  395.       dy = -dy;
  396.       ystep = -1;
  397.     }
  398.  
  399.   /*  for (y = y0; y != y1 + ystep ; y += ystep)
  400.     {
  401.       b->data[y-b->y].left = 0;
  402.       b->data[y-b->y].right = -1;
  403.       }*/
  404.  
  405.   x = x0;
  406.   y = y0;
  407.  
  408.   if (dy < dx)
  409.     {
  410.       d = 2*dy - dx;        /* initial value of d */
  411.       incrE = 2 * dy;        /* increment used for move to E */
  412.       incrNE = 2 * (dy-dx);        /* increment used for move to NE */
  413.       
  414.       blob_line_add_pixel (b, x, y);
  415.       
  416.       while (x != x1)
  417.     {
  418.       if (d <= 0)
  419.         {
  420.           d += incrE;
  421.           x += xstep;
  422.         }
  423.       else
  424.         {
  425.           d += incrNE;
  426.           x += xstep;
  427.           y += ystep;
  428.         }
  429.       blob_line_add_pixel (b, x, y);
  430.     }
  431.     }
  432.   else
  433.     {
  434.       d = 2*dx - dy;        /* initial value of d */
  435.       incrE = 2 * dx;        /* increment used for move to E */
  436.       incrNE = 2 * (dx-dy);        /* increment used for move to NE */
  437.       
  438.       blob_line_add_pixel (b, x, y);
  439.       
  440.       while (y != y1)
  441.     {
  442.       if (d <= 0)
  443.         {
  444.           d += incrE;
  445.           y += ystep;
  446.         }
  447.       else
  448.         {
  449.           d += incrNE;
  450.           x += xstep;
  451.           y += ystep;
  452.         }
  453.       blob_line_add_pixel (b, x, y);
  454.     }
  455.     }
  456. }
  457.  
  458. #define TABLE_SIZE 256
  459.  
  460. #define ELLIPSE_SHIFT 2
  461. #define TABLE_SHIFT   12
  462. #define TOTAL_SHIFT   (ELLIPSE_SHIFT + TABLE_SHIFT)
  463.  
  464. /*
  465.  * The choose of this values limits the maximal image_size to 
  466.  * 16384 x 16384 pixels. The values will overflow as soon as 
  467.  * x or y > INT_MAX / (1 << (ELLIPSE_SHIFT + TABLE_SHIFT)) / SUBSAMPLE
  468.  * 
  469.  * Alternatively the code could be change the code as follows:
  470.  *
  471.  *   xc_base = floor (xc)
  472.  *   xc_shift = 0.5 + (xc - xc_base) * (1 << TOTAL_SHIFT);
  473.  * 
  474.  *    gint x = xc_base + (xc_shift + c * xp_shift + s * xq_shift +
  475.  *             (1 << (TOTAL_SHIFT - 1))) >> TOTAL_SHIFT;
  476.  *
  477.  * which would change the limit from the image to the ellipse size
  478.  */
  479.  
  480. static int trig_initialized = 0;
  481. static int trig_table[TABLE_SIZE];
  482.  
  483. /* Return blob for the given (convex) polygon
  484.  */
  485. Blob *
  486. blob_polygon (BlobPoint *points, int npoints)
  487. {
  488.   int i;
  489.   int im1;
  490.   int ip1;
  491.   int ymin, ymax;
  492.   Blob *result;
  493.   EdgeType *present;
  494.  
  495.   ymax = points[0].y;
  496.   ymin = points[0].y;
  497.  
  498.   for (i=1; i < npoints; i++)
  499.     {
  500.       if (points[i].y > ymax)
  501.     ymax = points[i].y;
  502.       if (points[i].y < ymin)
  503.     ymin = points[i].y;
  504.     }
  505.  
  506.   result = blob_new (ymin, ymax - ymin + 1);
  507.   present = g_new0 (EdgeType, result->height);
  508.  
  509.   im1 = npoints - 1;
  510.   i = 0;
  511.   ip1 = 1;
  512.  
  513.   for (; i < npoints ; i++)
  514.     {
  515.       int sides = 0;
  516.       int j = points[i].y - ymin;
  517.       
  518.       if (points[i].y < points[im1].y)
  519.     sides |= EDGE_RIGHT;
  520.       else if (points[i].y > points[im1].y)
  521.     sides |= EDGE_LEFT;
  522.  
  523.       if (points[ip1].y < points[i].y)
  524.     sides |= EDGE_RIGHT;
  525.       else if (points[ip1].y > points[i].y)
  526.     sides |= EDGE_LEFT;
  527.  
  528.       if (sides & EDGE_RIGHT)
  529.     {
  530.       if (present[j] & EDGE_RIGHT)
  531.         {
  532.           result->data[j].right = MAX (result->data[j].right, points[i].x);
  533.         }
  534.       else
  535.         {
  536.           present[j] |= EDGE_RIGHT;
  537.           result->data[j].right = points[i].x;
  538.         }
  539.     }
  540.  
  541.       if (sides & EDGE_LEFT)
  542.     {
  543.       if (present[j] & EDGE_LEFT)
  544.         {
  545.           result->data[j].left = MIN (result->data[j].left, points[i].x);
  546.         }
  547.       else
  548.         {
  549.           present[j] |= EDGE_LEFT;
  550.           result->data[j].left = points[i].x;
  551.         }
  552.     }
  553.  
  554.       im1 = i;
  555.       ip1++;
  556.       if (ip1 == npoints)
  557.     ip1 = 0;
  558.     }
  559.  
  560.   blob_fill (result, present);
  561.   g_free (present);
  562.  
  563.   return result;
  564. }
  565.  
  566. /* Scan convert a square specified by _offsets_ of major and
  567.    minor axes, and by center into a blob */
  568. Blob *
  569. blob_square (double xc, double yc, double xp, double yp, double xq, double yq)
  570. {
  571.   BlobPoint points[4];
  572.   
  573.   /* Make sure we order points ccw */
  574.  
  575.   if (xp * yq - yq * xp < 0)
  576.     {
  577.       xq = -xq;
  578.       yq = -yq;
  579.     }
  580.   
  581.   points[0].x = xc + xp + xq;
  582.   points[0].y = yc + yp + yq;
  583.   points[1].x = xc + xp - xq;
  584.   points[1].y = yc + yp - yq;
  585.   points[2].x = xc - xp - xq;
  586.   points[2].y = yc - yp - yq;
  587.   points[3].x = xc - xp + xq;
  588.   points[3].y = yc - yp + yq;
  589.  
  590.   return blob_polygon (points, 4);
  591. }
  592.  
  593. /* Scan convert a diamond specified by _offsets_ of major and
  594.    minor axes, and by center into a blob */
  595. Blob *
  596. blob_diamond (double xc, double yc, double xp, double yp, double xq, double yq)
  597. {
  598.   BlobPoint points[4];
  599.   
  600.   /* Make sure we order points ccw */
  601.  
  602.   if (xp * yq - yq * xp < 0)
  603.     {
  604.       xq = -xq;
  605.       yq = -yq;
  606.     }
  607.   
  608.   points[0].x = xc + xp;
  609.   points[0].y = yc + yp;
  610.   points[1].x = xc - xq;
  611.   points[1].y = yc - yq;
  612.   points[2].x = xc - xp;
  613.   points[2].y = yc - yp;
  614.   points[3].x = xc + xq;
  615.   points[3].y = yc + yq;
  616.  
  617.   return blob_polygon (points, 4);
  618. }
  619.  
  620. /* Scan convert an ellipse specified by _offsets_ of major and
  621.    minor axes, and by center into a blob */
  622. Blob *
  623. blob_ellipse (double xc, double yc, double xp, double yp, double xq, double yq)
  624. {
  625.   int i;
  626.   Blob *r;
  627.   gdouble r1, r2;
  628.   gint maxy, miny;
  629.   gint step;
  630.   double max_radius;
  631.  
  632.   gint xc_shift, yc_shift;
  633.   gint xp_shift, yp_shift;
  634.   gint xq_shift, yq_shift;
  635.  
  636.   EdgeType *present;
  637.   
  638.   if (!trig_initialized)
  639.     {
  640.       trig_initialized = 1;
  641.       for (i=0; i<256; i++)
  642.     trig_table[i] = 0.5 + sin(i * (G_PI / 128.)) * (1 << TABLE_SHIFT);
  643.     }
  644.  
  645.   /* Make sure we traverse ellipse in ccw direction */
  646.  
  647.   if (xp * yq - yq * xp < 0)
  648.     {
  649.       xq = -xq;
  650.       yq = -yq;
  651.  
  652.     }
  653.  
  654.   /* Compute bounds as if we were drawing a rectangle */
  655.  
  656.   maxy = ceil (yc + fabs (yp) + fabs(yq));
  657.   miny = floor (yc - fabs (yp) - fabs(yq));
  658.  
  659.   r = blob_new (miny, maxy - miny + 1);
  660.   present = g_new0 (EdgeType, r->height);
  661.  
  662.   /* Figure out a step that will draw most of the points */
  663.  
  664.   r1 = sqrt (xp * xp + yp * yp);
  665.   r2 = sqrt (xq * xq + yq * yq); 
  666.   max_radius = MAX (r1, r2);
  667.   step = TABLE_SIZE;
  668.  
  669.   while (step > 1 && (TABLE_SIZE / step < 4*max_radius))
  670.     step >>= 1;
  671.  
  672.   /* Fill in the edge points */
  673.  
  674.   xc_shift = 0.5 + xc * (1 << TOTAL_SHIFT);
  675.   yc_shift = 0.5 + yc * (1 << TOTAL_SHIFT);
  676.   xp_shift = 0.5 + xp * (1 << ELLIPSE_SHIFT);
  677.   yp_shift = 0.5 + yp * (1 << ELLIPSE_SHIFT);
  678.   xq_shift = 0.5 + xq * (1 << ELLIPSE_SHIFT);
  679.   yq_shift = 0.5 + yq * (1 << ELLIPSE_SHIFT);
  680.  
  681.   for (i = 0 ; i < TABLE_SIZE ; i += step)
  682.     {
  683.       gint s = trig_table[i];
  684.       gint c = trig_table[(TABLE_SIZE + TABLE_SIZE/4 - i) % TABLE_SIZE];
  685.       
  686.       gint x = (xc_shift + c * xp_shift + s * xq_shift +
  687.         (1 << (TOTAL_SHIFT - 1))) >> TOTAL_SHIFT;
  688.       gint y = ((yc_shift + c * yp_shift + s * yq_shift +
  689.         (1 << (TOTAL_SHIFT - 1))) >> TOTAL_SHIFT) - r->y;
  690.  
  691.       gint dydi = c * yq_shift  - s * yp_shift;
  692.  
  693.       if (dydi <= 0) /* left edge */
  694.     {
  695.       if (present[y] & EDGE_LEFT)
  696.         {
  697.           r->data[y].left = MIN (r->data[y].left, x);
  698.         }
  699.       else
  700.         {
  701.           present[y] |= EDGE_LEFT;
  702.           r->data[y].left = x;
  703.         }
  704.     }
  705.       
  706.       if (dydi >= 0) /* right edge */
  707.     {
  708.       if (present[y] & EDGE_RIGHT)
  709.         {
  710.           r->data[y].right = MAX (r->data[y].right, x);
  711.         }
  712.       else
  713.         {
  714.           present[y] |= EDGE_RIGHT;
  715.           r->data[y].right = x;
  716.         }
  717.     }
  718.     }
  719.  
  720.   /* Now fill in missing points */
  721.  
  722.   blob_fill (r, present);
  723.   g_free (present);
  724.  
  725.   return r;
  726. }
  727.  
  728. void
  729. blob_bounds(Blob *b, int *x, int *y, int *width, int *height)
  730. {
  731.   int i;
  732.   int x0, x1, y0, y1;
  733.  
  734.   i = 0;
  735.   while (i<b->height && b->data[i].left > b->data[i].right)
  736.     i++;
  737.  
  738.   if (i<b->height)
  739.     {
  740.       y0 = b->y + i;
  741.       x0 = b->data[i].left;
  742.       x1 = b->data[i].right + 1;
  743.       while (i<b->height && b->data[i].left <= b->data[i].right)
  744.     {
  745.       x0 = MIN(b->data[i].left, x0);
  746.       x1 = MAX(b->data[i].right+1, x1);
  747.       i++;
  748.     }
  749.       y1 = b->y + i;
  750.     }
  751.   else
  752.     {
  753.       x0 = y0 = 0;
  754.       x1 = y1 = 0;
  755.     }
  756.  
  757.   *x = x0;
  758.   *y = y0;
  759.   *width = x1 - x0;
  760.   *height = y1 - y0;
  761. }
  762.  
  763. void
  764. blob_dump(Blob *b) {
  765.   int i,j;
  766.   for (i=0; i<b->height; i++)
  767.     {
  768.       for (j=0;j<b->data[i].left;j++)
  769.     putchar(' ');
  770.       for (j=b->data[i].left;j<=b->data[i].right;j++)
  771.     putchar('*');
  772.       putchar('\n');
  773.     }
  774. }
  775.