libraries/libart_lgpl-2.3.7/art_svp_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 /* Sort vector paths into sorted vector paths */
  21
  22 #include <stdlib.h>
  23 #include <math.h>
  24
  25 #include "art_misc.h"
  26
  27 #include "art_vpath.h"
  28 #include "art_svp.h"
  29 #include "art_svp_vpath.h"
  30
  31
  32 /* reverse a list of points in place */
  33 static void
  34 reverse_points (ArtPoint *points, int n_points)
  35 {
  36   int i;
  37   ArtPoint tmp_p;
  38
  39   for (i = 0; i < (n_points >> 1); i++)
  40     {
  41       tmp_p = points[i];
  42       points[i] = points[n_points - (i + 1)];
  43       points[n_points - (i + 1)] = tmp_p;
  44     }
  45 }
  46
  47 /**
  48  * art_svp_from_vpath: Convert a vpath to a sorted vector path.
  49  * @vpath: #ArtVPath to convert.
  50  *
  51  * Converts a vector path into sorted vector path form. The svp form is
  52  * more efficient for rendering and other vector operations.
  53  *
  54  * Basically, the implementation is to traverse the vector path,
  55  * generating a new segment for each "run" of points in the vector
  56  * path with monotonically increasing Y values. All the resulting
  57  * values are then sorted.
  58  *
  59  * Note: I'm not sure that the sorting rule is correct with respect
  60  * to numerical stability issues.
  61  *
  62  * Return value: Resulting sorted vector path.
  63  **/
  64 ArtSVP *
  65 art_svp_from_vpath (ArtVpath *vpath)
  66 {
  67   int n_segs, n_segs_max;
  68   ArtSVP *svp;
  69   int dir;
  70   int new_dir;
  71   int i;
  72   ArtPoint *points;
  73   int n_points, n_points_max;
  74   double x, y;
  75   double x_min, x_max;
  76
  77   n_segs = 0;
  78   n_segs_max = 16;
  79   svp = (ArtSVP *)art_alloc (sizeof(ArtSVP) +
  80                              (n_segs_max - 1) * sizeof(ArtSVPSeg));
  81
  82   dir = 0;
  83   n_points = 0;
  84   n_points_max = 0;
  85   points = NULL;
  86   i = 0;
  87
  88   x = y = 0; /* unnecessary, given "first code must not be LINETO" invariant,
  89                 but it makes gcc -Wall -ansi -pedantic happier */
  90   x_min = x_max = 0; /* same */
  91
  92   while (vpath[i].code != ART_END) {
  93     if (vpath[i].code == ART_MOVETO || vpath[i].code == ART_MOVETO_OPEN)
  94       {
  95         if (points != NULL && n_points >= 2)
  96           {
  97             if (n_segs == n_segs_max)
  98               {
  99                 n_segs_max <<= 1;
 100                 svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) +
 101                                              (n_segs_max - 1) *
 102                                              sizeof(ArtSVPSeg));
 103               }
 104             svp->segs[n_segs].n_points = n_points;
 105             svp->segs[n_segs].dir = (dir > 0);
 106             if (dir < 0)
 107               reverse_points (points, n_points);
 108             svp->segs[n_segs].points = points;
 109             svp->segs[n_segs].bbox.x0 = x_min;
 110             svp->segs[n_segs].bbox.x1 = x_max;
 111             svp->segs[n_segs].bbox.y0 = points[0].y;
 112             svp->segs[n_segs].bbox.y1 = points[n_points - 1].y;
 113             n_segs++;
 114             points = NULL;
 115           }
 116
 117         if (points == NULL)
 118           {
 119             n_points_max = 4;
 120             points = art_new (ArtPoint, n_points_max);
 121           }
 122
 123         n_points = 1;
 124         points[0].x = x = vpath[i].x;
 125         points[0].y = y = vpath[i].y;
 126         x_min = x;
 127         x_max = x;
 128         dir = 0;
 129       }
 130     else /* must be LINETO */
 131       {
 132         new_dir = (vpath[i].y > y ||
 133                    (vpath[i].y == y && vpath[i].x > x)) ? 1 : -1;
 134         if (dir && dir != new_dir)
 135           {
 136             /* new segment */
 137             x = points[n_points - 1].x;
 138             y = points[n_points - 1].y;
 139             if (n_segs == n_segs_max)
 140               {
 141                 n_segs_max <<= 1;
 142                 svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) +
 143                                              (n_segs_max - 1) *
 144                                              sizeof(ArtSVPSeg));
 145               }
 146             svp->segs[n_segs].n_points = n_points;
 147             svp->segs[n_segs].dir = (dir > 0);
 148             if (dir < 0)
 149               reverse_points (points, n_points);
 150             svp->segs[n_segs].points = points;
 151             svp->segs[n_segs].bbox.x0 = x_min;
 152             svp->segs[n_segs].bbox.x1 = x_max;
 153             svp->segs[n_segs].bbox.y0 = points[0].y;
 154             svp->segs[n_segs].bbox.y1 = points[n_points - 1].y;
 155             n_segs++;
 156
 157             n_points = 1;
 158             n_points_max = 4;
 159             points = art_new (ArtPoint, n_points_max);
 160             points[0].x = x;
 161             points[0].y = y;
 162             x_min = x;
 163             x_max = x;
 164           }
 165
 166         if (points != NULL)
 167           {
 168             if (n_points == n_points_max)
 169               art_expand (points, ArtPoint, n_points_max);
 170             points[n_points].x = x = vpath[i].x;
 171             points[n_points].y = y = vpath[i].y;
 172             if (x < x_min) x_min = x;
 173             else if (x > x_max) x_max = x;
 174             n_points++;
 175           }
 176         dir = new_dir;
 177       }
 178     i++;
 179   }
 180
 181   if (points != NULL)
 182     {
 183       if (n_points >= 2)
 184         {
 185           if (n_segs == n_segs_max)
 186             {
 187               n_segs_max <<= 1;
 188               svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) +
 189                                            (n_segs_max - 1) *
 190                                            sizeof(ArtSVPSeg));
 191             }
 192           svp->segs[n_segs].n_points = n_points;
 193           svp->segs[n_segs].dir = (dir > 0);
 194           if (dir < 0)
 195             reverse_points (points, n_points);
 196           svp->segs[n_segs].points = points;
 197           svp->segs[n_segs].bbox.x0 = x_min;
 198           svp->segs[n_segs].bbox.x1 = x_max;
 199           svp->segs[n_segs].bbox.y0 = points[0].y;
 200           svp->segs[n_segs].bbox.y1 = points[n_points - 1].y;
 201           n_segs++;
 202         }
 203       else
 204         art_free (points);
 205     }
 206
 207   svp->n_segs = n_segs;
 208
 209   qsort (&svp->segs, n_segs, sizeof (ArtSVPSeg), art_svp_seg_compare);
 210
 211   return svp;
 212 }
 213