lib/art/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 #include "config.h"
  21 #include "art_uta_vpath.h"
  22
  23 #include <math.h>
  24
  25 #include "art_misc.h"
  26 #include "art_vpath.h"
  27 #include "art_uta.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
 199               /* xn is the intercept with bottom edge of this tile. The
 200                  following expression is careful to result in exactly
 201                  x1 when yn = y1. */
 202               xn = x1 + dx_dy * (yn - y1);
 203
 204               if (xt0 != (int)floor (xn) >> ART_UTILE_SHIFT)
 205                 {
 206                   /* horizontal crossing */
 207                   xt0 += sx;
 208                   dix = sx;
 209                   if (dx > 0)
 210                     {
 211                       xn = xt0 << ART_UTILE_SHIFT;
 212                       yn = y0 + (xn - x0) / dx_dy;
 213
 214                       xf0 = (int)floor (x) & (ART_UTILE_SIZE - 1);
 215                       xf1 = ART_UTILE_SIZE;
 216                     }
 217                   else
 218                     {
 219                       xn = (xt0 + 1) << ART_UTILE_SHIFT;
 220                       yn = y0 + (xn - x0) / dx_dy;
 221
 222                       xf0 = 0;
 223                       xmaxc = (int)ceil (x);
 224                       xf1 = xmaxc - ((xt0 + 1) << ART_UTILE_SHIFT);
 225                     }
 226                   ymaxf = (int)floor (yn);
 227                   ymaxc = (int)ceil (yn);
 228                   yf1 = (ymaxf & (ART_UTILE_SIZE - 1)) + ymaxc - ymaxf;
 229                 }
 230               else
 231                 {
 232                   /* vertical crossing */
 233                   dix = uta->width;
 234                   xf0 = (int)floor (MIN(x, xn)) & (ART_UTILE_SIZE - 1);
 235                   xmax = MAX(x, xn);
 236                   xmaxc = (int)ceil (xmax);
 237                   xf1 = xmaxc - (xt0 << ART_UTILE_SHIFT);
 238                   yf1 = ART_UTILE_SIZE;
 239
 240                   if (rbuf != NULL)
 241                     rbuf[yt0 * rbuf_rowstride + xt0] += sy;
 242
 243                   yt0++;
 244                 }
 245               yf0 = (int)floor (y) & (ART_UTILE_SIZE - 1);
 246               bb = uta->utiles[ix];
 247               if (bb == 0)
 248                 bb = ART_UTA_BBOX_CONS(xf0, yf0, xf1, yf1);
 249               else
 250                 bb = ART_UTA_BBOX_CONS(MIN(ART_UTA_BBOX_X0(bb), xf0),
 251                                        MIN(ART_UTA_BBOX_Y0(bb), yf0),
 252                                        MAX(ART_UTA_BBOX_X1(bb), xf1),
 253                                        MAX(ART_UTA_BBOX_Y1(bb), yf1));
 254               uta->utiles[ix] = bb;
 255
 256               x = xn;
 257               y = yn;
 258               ix += dix;
 259             }
 260           xmax = MAX(x, x1);
 261           xmaxc = ceil (xmax);
 262           ymaxc = ceil (y1);
 263           xf0 = (int)floor (MIN(x1, x)) & (ART_UTILE_SIZE - 1);
 264           yf0 = (int)floor (y) & (ART_UTILE_SIZE - 1);
 265           xf1 = xmaxc - (xt0 << ART_UTILE_SHIFT);
 266           yf1 = ymaxc - (yt0 << ART_UTILE_SHIFT);
 267           bb = uta->utiles[ix];
 268           if (bb == 0)
 269             bb = ART_UTA_BBOX_CONS(xf0, yf0, xf1, yf1);
 270           else
 271             bb = ART_UTA_BBOX_CONS(MIN(ART_UTA_BBOX_X0(bb), xf0),
 272                                    MIN(ART_UTA_BBOX_Y0(bb), yf0),
 273                                    MAX(ART_UTA_BBOX_X1(bb), xf1),
 274                                    MAX(ART_UTA_BBOX_Y1(bb), yf1));
 275           uta->utiles[ix] = bb;
 276         }
 277     }
 278 }
 279
 280 /**
 281  * art_uta_from_vpath: Generate uta covering a vpath.
 282  * @vec: The source vpath.
 283  *
 284  * Generates a uta covering @vec. The resulting uta is of course
 285  * approximate, ie it may cover more pixels than covered by @vec.
 286  *
 287  * Return value: the new uta.
 288  **/
 289 ArtUta *
 290 art_uta_from_vpath (const ArtVpath *vec)
 291 {
 292   ArtUta *uta;
 293   ArtIRect bbox;
 294   int *rbuf;
 295   int i;
 296   double x, y;
 297   int sum;
 298   int xt, yt;
 299   ArtUtaBbox *utiles;
 300   ArtUtaBbox bb;
 301   int width;
 302   int height;
 303   int ix;
 304
 305   art_vpath_bbox_irect (vec, &bbox);
 306
 307   uta = art_uta_new_coords (bbox.x0, bbox.y0, bbox.x1, bbox.y1);
 308
 309   width = uta->width;
 310   height = uta->height;
 311   utiles = uta->utiles;
 312
 313   rbuf = art_new (int, width * height);
 314   for (i = 0; i < width * height; i++)
 315     rbuf[i] = 0;
 316
 317   x = 0;
 318   y = 0;
 319   for (i = 0; vec[i].code != ART_END; i++)
 320     {
 321       switch (vec[i].code)
 322         {
 323         case ART_MOVETO:
 324           x = vec[i].x;
 325           y = vec[i].y;
 326           break;
 327         case ART_LINETO:
 328           art_uta_add_line (uta, vec[i].x, vec[i].y, x, y, rbuf, width);
 329           x = vec[i].x;
 330           y = vec[i].y;
 331           break;
 332         default:
 333           /* this shouldn't happen */
 334           art_free (rbuf);
 335           art_free (uta);
 336           return NULL;
 337         }
 338     }
 339
 340   /* now add in the filling from rbuf */
 341   ix = 0;
 342   for (yt = 0; yt < height; yt++)
 343     {
 344       sum = 0;
 345       for (xt = 0; xt < width; xt++)
 346         {
 347           sum += rbuf[ix];
 348           /* Nonzero winding rule - others are possible, but hardly
 349              worth it. */
 350           if (sum != 0)
 351             {
 352               bb = utiles[ix];
 353               bb &= 0xffff0000;
 354               bb |= (ART_UTILE_SIZE << 8) | ART_UTILE_SIZE;
 355               utiles[ix] = bb;
 356               if (xt != width - 1)
 357                 {
 358                   bb = utiles[ix + 1];
 359                   bb &= 0xffff00;
 360                   bb |= ART_UTILE_SIZE;
 361                   utiles[ix + 1] = bb;
 362                 }
 363               if (yt != height - 1)
 364                 {
 365                   bb = utiles[ix + width];
 366                   bb &= 0xff0000ff;
 367                   bb |= ART_UTILE_SIZE << 8;
 368                   utiles[ix + width] = bb;
 369                   if (xt != width - 1)
 370                     {
 371                       utiles[ix + width + 1] &= 0xffff;
 372                     }
 373                 }
 374             }
 375           ix++;
 376         }
 377     }
 378
 379   art_free (rbuf);
 380
 381   return uta;
 382 }