libraries/libart_lgpl-2.3.7/art_uta_vpath.c

   1 /* Libart_LGPL - library of basic graphic primitives
   2  * Copyright (C) 1998-2000 Raph Levien
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Library General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library General Public
  15  * License along with this library; if not, write to the
  16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17  * Boston, MA 02111-1307, USA.
  18  */
  19
  20 /* LGPL Copyright 1998 Raph Levien <raph@acm.org> */
  21
  22 #include <math.h>
  23
  24 #include "art_misc.h"
  25 #include "art_vpath.h"
  26 #include "art_uta.h"
  27 #include "art_uta_vpath.h"
  28
  29 #ifndef MAX
  30 #define MAX(a, b)  (((a) > (b)) ? (a) : (b))
  31 #endif /* MAX */
  32
  33 #ifndef MIN
  34 #define MIN(a, b)  (((a) < (b)) ? (a) : (b))
  35 #endif /* MIN */
  36
  37 /**
  38  * art_uta_add_line: Add a line to the uta.
  39  * @uta: The uta to modify.
  40  * @x0: X coordinate of line start point.
  41  * @y0: Y coordinate of line start point.
  42  * @x1: X coordinate of line end point.
  43  * @y1: Y coordinate of line end point.
  44  * @rbuf: Buffer containing first difference of winding number.
  45  * @rbuf_rowstride: Rowstride of @rbuf.
  46  *
  47  * Add the line (@x0, @y0) - (@x1, @y1) to @uta, and also update the
  48  * winding number buffer used for rendering the interior. @rbuf
  49  * contains the first partial difference (in the X direction) of the
  50  * winding number, measured in grid cells. Thus, each time that a line
  51  * crosses a horizontal uta grid line, an entry of @rbuf is
  52  * incremented if @y1 > @y0, decremented otherwise.
  53  *
  54  * Note that edge handling is fairly delicate. Please rtfs for
  55  * details.
  56  **/
  57 void
  58 art_uta_add_line (ArtUta *uta, double x0, double y0, double x1, double y1,
  59                   int *rbuf, int rbuf_rowstride)
  60 {
  61   int xmin, ymin;
  62   double xmax, ymax;
  63   int xmaxf, ymaxf;
  64   int xmaxc, ymaxc;
  65   int xt0, yt0;
  66   int xt1, yt1;
  67   int xf0, yf0;
  68   int xf1, yf1;
  69   int ix, ix1;
  70   ArtUtaBbox bb;
  71
  72   xmin = floor (MIN(x0, x1));
  73   xmax = MAX(x0, x1);
  74   xmaxf = floor (xmax);
  75   xmaxc = ceil (xmax);
  76   ymin = floor (MIN(y0, y1));
  77   ymax = MAX(y0, y1);
  78   ymaxf = floor (ymax);
  79   ymaxc = ceil (ymax);
  80   xt0 = (xmin >> ART_UTILE_SHIFT) - uta->x0;
  81   yt0 = (ymin >> ART_UTILE_SHIFT) - uta->y0;
  82   xt1 = (xmaxf >> ART_UTILE_SHIFT) - uta->x0;
  83   yt1 = (ymaxf >> ART_UTILE_SHIFT) - uta->y0;
  84   if (xt0 == xt1 && yt0 == yt1)
  85     {
  86       /* entirely inside a microtile, this is easy! */
  87       xf0 = xmin & (ART_UTILE_SIZE - 1);
  88       yf0 = ymin & (ART_UTILE_SIZE - 1);
  89       xf1 = (xmaxf & (ART_UTILE_SIZE - 1)) + xmaxc - xmaxf;
  90       yf1 = (ymaxf & (ART_UTILE_SIZE - 1)) + ymaxc - ymaxf;
  91
  92       ix = yt0 * uta->width + xt0;
  93       bb = uta->utiles[ix];
  94       if (bb == 0)
  95         bb = ART_UTA_BBOX_CONS(xf0, yf0, xf1, yf1);
  96       else
  97         bb = ART_UTA_BBOX_CONS(MIN(ART_UTA_BBOX_X0(bb), xf0),
  98                            MIN(ART_UTA_BBOX_Y0(bb), yf0),
  99                            MAX(ART_UTA_BBOX_X1(bb), xf1),
 100                            MAX(ART_UTA_BBOX_Y1(bb), yf1));
 101       uta->utiles[ix] = bb;
 102     }
 103   else
 104     {
 105       double dx, dy;
 106       int sx, sy;
 107
 108       dx = x1 - x0;
 109       dy = y1 - y0;
 110       sx = dx > 0 ? 1 : dx < 0 ? -1 : 0;
 111       sy = dy > 0 ? 1 : dy < 0 ? -1 : 0;
 112       if (ymin == ymaxf)
 113         {
 114           /* special case horizontal (dx/dy slope would be infinite) */
 115           xf0 = xmin & (ART_UTILE_SIZE - 1);
 116           yf0 = ymin & (ART_UTILE_SIZE - 1);
 117           xf1 = (xmaxf & (ART_UTILE_SIZE - 1)) + xmaxc - xmaxf;
 118           yf1 = (ymaxf & (ART_UTILE_SIZE - 1)) + ymaxc - ymaxf;
 119
 120           ix = yt0 * uta->width + xt0;
 121           ix1 = yt0 * uta->width + xt1;
 122           while (ix != ix1)
 123             {
 124               bb = uta->utiles[ix];
 125               if (bb == 0)
 126                 bb = ART_UTA_BBOX_CONS(xf0, yf0, ART_UTILE_SIZE, yf1);
 127               else
 128                 bb = ART_UTA_BBOX_CONS(MIN(ART_UTA_BBOX_X0(bb), xf0),
 129                                    MIN(ART_UTA_BBOX_Y0(bb), yf0),
 130                                    ART_UTILE_SIZE,
 131                                    MAX(ART_UTA_BBOX_Y1(bb), yf1));
 132               uta->utiles[ix] = bb;
 133               xf0 = 0;
 134               ix++;
 135             }
 136           bb = uta->utiles[ix];
 137           if (bb == 0)
 138             bb = ART_UTA_BBOX_CONS(0, yf0, xf1, yf1);
 139           else
 140             bb = ART_UTA_BBOX_CONS(0,
 141                                MIN(ART_UTA_BBOX_Y0(bb), yf0),
 142                                MAX(ART_UTA_BBOX_X1(bb), xf1),
 143                                MAX(ART_UTA_BBOX_Y1(bb), yf1));
 144           uta->utiles[ix] = bb;
 145         }
 146       else
 147         {
 148           /* Do a Bresenham-style traversal of the line */
 149           double dx_dy;
 150           double x, y;
 151           double xn, yn;
 152
 153           /* normalize coordinates to uta origin */
 154           x0 -= uta->x0 << ART_UTILE_SHIFT;
 155           y0 -= uta->y0 << ART_UTILE_SHIFT;
 156           x1 -= uta->x0 << ART_UTILE_SHIFT;
 157           y1 -= uta->y0 << ART_UTILE_SHIFT;
 158           if (dy < 0)
 159             {
 160               double tmp;
 161
 162               tmp = x0;
 163               x0 = x1;
 164               x1 = tmp;
 165
 166               tmp = y0;
 167               y0 = y1;
 168               y1 = tmp;
 169
 170               dx = -dx;
 171               sx = -sx;
 172               dy = -dy;
 173               /* we leave sy alone, because it would always be 1,
 174                  and we need it for the rbuf stuff. */
 175             }
 176           xt0 = ((int)floor (x0) >> ART_UTILE_SHIFT);
 177           xt1 = ((int)floor (x1) >> ART_UTILE_SHIFT);
 178           /* now [xy]0 is above [xy]1 */
 179
 180           ix = yt0 * uta->width + xt0;
 181           ix1 = yt1 * uta->width + xt1;
 182 #ifdef VERBOSE
 183           printf ("%% ix = %d,%d; ix1 = %d,%d\n", xt0, yt0, xt1, yt1);
 184 #endif
 185
 186           dx_dy = dx / dy;
 187           x = x0;
 188           y = y0;
 189           while (ix != ix1)
 190             {
 191               int dix;
 192
 193               /* figure out whether next crossing is horizontal or vertical */
 194 #ifdef VERBOSE
 195               printf ("%% %d,%d\n", xt0, yt0);
 196 #endif
 197               yn = (yt0 + 1) << ART_UTILE_SHIFT;
 198               xn = x0 + dx_dy * (yn - y0);
 199               if (xt0 != (int)floor (xn) >> ART_UTILE_SHIFT)
 200                 {
 201                   /* horizontal crossing */
 202                   xt0 += sx;
 203                   dix = sx;
 204                   if (dx > 0)
 205                     {
 206                       xn = xt0 << ART_UTILE_SHIFT;
 207                       yn = y0 + (xn - x0) / dx_dy;
 208
 209                       xf0 = (int)floor (x) & (ART_UTILE_SIZE - 1);
 210                       xf1 = ART_UTILE_SIZE;
 211                     }
 212                   else
 213                     {
 214                       xn = (xt0 + 1) << ART_UTILE_SHIFT;
 215                       yn = y0 + (xn - x0) / dx_dy;
 216
 217                       xf0 = 0;
 218                       xmaxc = (int)ceil (x);
 219                       xf1 = xmaxc - ((xt0 + 1) << ART_UTILE_SHIFT);
 220                     }
 221                   ymaxf = (int)floor (yn);
 222                   ymaxc = (int)ceil (yn);
 223                   yf1 = (ymaxf & (ART_UTILE_SIZE - 1)) + ymaxc - ymaxf;
 224                 }
 225               else
 226                 {
 227                   /* vertical crossing */
 228                   dix = uta->width;
 229                   xf0 = (int)floor (MIN(x, xn)) & (ART_UTILE_SIZE - 1);
 230                   xmax = MAX(x, xn);
 231                   xmaxc = (int)ceil (xmax);
 232                   xf1 = xmaxc - (xt0 << ART_UTILE_SHIFT);
 233                   yf1 = ART_UTILE_SIZE;
 234
 235                   if (rbuf != NULL)
 236                     rbuf[yt0 * rbuf_rowstride + xt0] += sy;
 237
 238                   yt0++;
 239                 }
 240               yf0 = (int)floor (y) & (ART_UTILE_SIZE - 1);
 241               bb = uta->utiles[ix];
 242               if (bb == 0)
 243                 bb = ART_UTA_BBOX_CONS(xf0, yf0, xf1, yf1);
 244               else
 245                 bb = ART_UTA_BBOX_CONS(MIN(ART_UTA_BBOX_X0(bb), xf0),
 246                                        MIN(ART_UTA_BBOX_Y0(bb), yf0),
 247                                        MAX(ART_UTA_BBOX_X1(bb), xf1),
 248                                        MAX(ART_UTA_BBOX_Y1(bb), yf1));
 249               uta->utiles[ix] = bb;
 250
 251               x = xn;
 252               y = yn;
 253               ix += dix;
 254             }
 255           xmax = MAX(x, x1);
 256           xmaxc = ceil (xmax);
 257           ymaxc = ceil (y1);
 258           xf0 = (int)floor (MIN(x1, x)) & (ART_UTILE_SIZE - 1);
 259           yf0 = (int)floor (y) & (ART_UTILE_SIZE - 1);
 260           xf1 = xmaxc - (xt0 << ART_UTILE_SHIFT);
 261           yf1 = ymaxc - (yt0 << ART_UTILE_SHIFT);
 262           bb = uta->utiles[ix];
 263           if (bb == 0)
 264             bb = ART_UTA_BBOX_CONS(xf0, yf0, xf1, yf1);
 265           else
 266             bb = ART_UTA_BBOX_CONS(MIN(ART_UTA_BBOX_X0(bb), xf0),
 267                                    MIN(ART_UTA_BBOX_Y0(bb), yf0),
 268                                    MAX(ART_UTA_BBOX_X1(bb), xf1),
 269                                    MAX(ART_UTA_BBOX_Y1(bb), yf1));
 270           uta->utiles[ix] = bb;
 271         }
 272     }
 273 }
 274
 275 /**
 276  * art_uta_from_vpath: Generate uta covering a vpath.
 277  * @vec: The source vpath.
 278  *
 279  * Generates a uta covering @vec. The resulting uta is of course
 280  * approximate, ie it may cover more pixels than covered by @vec.
 281  *
 282  * Return value: the new uta.
 283  **/
 284 ArtUta *
 285 art_uta_from_vpath (const ArtVpath *vec)
 286 {
 287   ArtUta *uta;
 288   ArtIRect bbox;
 289   int *rbuf;
 290   int i;
 291   double x, y;
 292   int sum;
 293   int xt, yt;
 294   ArtUtaBbox *utiles;
 295   ArtUtaBbox bb;
 296   int width;
 297   int height;
 298   int ix;
 299
 300   art_vpath_bbox_irect (vec, &bbox);
 301
 302   uta = art_uta_new_coords (bbox.x0, bbox.y0, bbox.x1, bbox.y1);
 303
 304   width = uta->width;
 305   height = uta->height;
 306   utiles = uta->utiles;
 307
 308   rbuf = art_new (int, width * height);
 309   for (i = 0; i < width * height; i++)
 310     rbuf[i] = 0;
 311
 312   x = 0;
 313   y = 0;
 314   for (i = 0; vec[i].code != ART_END; i++)
 315     {
 316       switch (vec[i].code)
 317         {
 318         case ART_MOVETO:
 319           x = vec[i].x;
 320           y = vec[i].y;
 321           break;
 322         case ART_LINETO:
 323           art_uta_add_line (uta, vec[i].x, vec[i].y, x, y, rbuf, width);
 324           x = vec[i].x;
 325           y = vec[i].y;
 326           break;
 327         default:
 328           /* this shouldn't happen */
 329           break;
 330         }
 331     }
 332
 333   /* now add in the filling from rbuf */
 334   ix = 0;
 335   for (yt = 0; yt < height; yt++)
 336     {
 337       sum = 0;
 338       for (xt = 0; xt < width; xt++)
 339         {
 340           sum += rbuf[ix];
 341           /* Nonzero winding rule - others are possible, but hardly
 342              worth it. */
 343           if (sum != 0)
 344             {
 345               bb = utiles[ix];
 346               bb &= 0xffff0000;
 347               bb |= (ART_UTILE_SIZE << 8) | ART_UTILE_SIZE;
 348               utiles[ix] = bb;
 349               if (xt != width - 1)
 350                 {
 351                   bb = utiles[ix + 1];
 352                   bb &= 0xffff00;
 353                   bb |= ART_UTILE_SIZE;
 354                   utiles[ix + 1] = bb;
 355                 }
 356               if (yt != height - 1)
 357                 {
 358                   bb = utiles[ix + width];
 359                   bb &= 0xff0000ff;
 360                   bb |= ART_UTILE_SIZE << 8;
 361                   utiles[ix + width] = bb;
 362                   if (xt != width - 1)
 363                     {
 364                       utiles[ix + width + 1] &= 0xffff;
 365                     }
 366                 }
 367             }
 368           ix++;
 369         }
 370     }
 371
 372   art_free (rbuf);
 373
 374   return uta;
 375 }