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