lib/art/art_vpath_dash.c

   1 /* Libart_LGPL - library of basic graphic primitives
   2  * Copyright (C) 1999-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 /* Apply a dash style to a vector path. */
  21
  22 #include "config.h"
  23 #include "art_vpath_dash.h"
  24
  25 #include <math.h>
  26 #include <stdlib.h>
  27
  28 #include "art_misc.h"
  29
  30 #include "art_vpath.h"
  31
  32
  33 /* Return the length of the largest subpath within vpath */
  34 static int
  35 art_vpath_dash_max_subpath (const ArtVpath *vpath)
  36 {
  37   int max_subpath;
  38   int i;
  39   int start;
  40
  41   max_subpath = 0;
  42   start = 0;
  43   for (i = 0; vpath[i].code != ART_END; i++)
  44     {
  45       if (vpath[i].code == ART_MOVETO || vpath[i].code == ART_MOVETO_OPEN)
  46         {
  47           if (i - start > max_subpath)
  48             max_subpath = i - start;
  49           start = i;
  50         }
  51     }
  52   if (i - start > max_subpath)
  53     max_subpath = i - start;
  54
  55   return max_subpath;
  56 }
  57
  58 /**
  59  * art_vpath_dash: Add dash style to vpath.
  60  * @vpath: Original vpath.
  61  * @dash: Dash style.
  62  *
  63  * Creates a new vpath that is the result of applying dash style @dash
  64  * to @vpath.
  65  *
  66  * This implementation has two known flaws:
  67  *
  68  * First, it adds a spurious break at the beginning of the vpath. The
  69  * only way I see to resolve this flaw is to run the state forward one
  70  * dash break at the beginning, and fix up by looping back to the
  71  * first dash break at the end. This is doable but of course adds some
  72  * complexity.
  73  *
  74  * Second, it does not suppress output points that are within epsilon
  75  * of each other.
  76  *
  77  * Return value: Newly created vpath.
  78  **/
  79 ArtVpath *
  80 art_vpath_dash (const ArtVpath *vpath, const ArtVpathDash *dash)
  81 {
  82   int max_subpath;
  83   double *dists;
  84   ArtVpath *result;
  85   int n_result, n_result_max;
  86   int start, end;
  87   int i;
  88   double total_dist;
  89
  90   /* state while traversing dasharray - offset is offset of current dash
  91      value, toggle is 0 for "off" and 1 for "on", and phase is the distance
  92      in, >= 0, < dash->dash[offset]. */
  93   int offset, toggle;
  94   double phase;
  95
  96   /* initial values */
  97   int offset_init, toggle_init;
  98   double phase_init;
  99
 100   max_subpath = art_vpath_dash_max_subpath (vpath);
 101   dists = art_new (double, max_subpath);
 102
 103   n_result = 0;
 104   n_result_max = 16;
 105   result = art_new (ArtVpath, n_result_max);
 106
 107   /* determine initial values of dash state */
 108   toggle_init = 1;
 109   offset_init = 0;
 110   phase_init = dash->offset;
 111   while (phase_init >= dash->dash[offset_init])
 112     {
 113       toggle_init = !toggle_init;
 114       phase_init -= dash->dash[offset_init];
 115       offset_init++;
 116       if (offset_init == dash->n_dash)
 117         offset_init = 0;
 118     }
 119
 120   for (start = 0; vpath[start].code != ART_END; start = end)
 121     {
 122       for (end = start + 1; vpath[end].code == ART_LINETO; end++);
 123       /* subpath is [start..end) */
 124       total_dist = 0;
 125       for (i = start; i < end - 1; i++)
 126         {
 127           double dx, dy;
 128
 129           dx = vpath[i + 1].x - vpath[i].x;
 130           dy = vpath[i + 1].y - vpath[i].y;
 131           dists[i - start] = sqrt (dx * dx + dy * dy);
 132           total_dist += dists[i - start];
 133         }
 134       if (total_dist <= dash->dash[offset_init] - phase_init)
 135         {
 136           /* subpath fits entirely within first dash */
 137           if (toggle_init)
 138             {
 139               for (i = start; i < end; i++)
 140                 art_vpath_add_point (&result, &n_result, &n_result_max,
 141                                      vpath[i].code, vpath[i].x, vpath[i].y);
 142             }
 143         }
 144       else
 145         {
 146           /* subpath is composed of at least one dash - thus all
 147              generated pieces are open */
 148           double dist;
 149
 150           phase = phase_init;
 151           offset = offset_init;
 152           toggle = toggle_init;
 153           dist = 0;
 154           i = start;
 155           if (toggle)
 156             art_vpath_add_point (&result, &n_result, &n_result_max,
 157                                  ART_MOVETO_OPEN, vpath[i].x, vpath[i].y);
 158           while (i != end - 1)
 159             {
 160               if (dists[i - start] - dist > dash->dash[offset] - phase)
 161                 {
 162                   /* dash boundary is next */
 163                   double a;
 164                   double x, y;
 165
 166                   dist += dash->dash[offset] - phase;
 167                   a = dist / dists[i - start];
 168                   x = vpath[i].x + a * (vpath[i + 1].x - vpath[i].x);
 169                   y = vpath[i].y + a * (vpath[i + 1].y - vpath[i].y);
 170                   art_vpath_add_point (&result, &n_result, &n_result_max,
 171                                        toggle ? ART_LINETO : ART_MOVETO_OPEN,
 172                                        x, y);
 173                   /* advance to next dash */
 174                   toggle = !toggle;
 175                   phase = 0;
 176                   offset++;
 177                   if (offset == dash->n_dash)
 178                     offset = 0;
 179                 }
 180               else
 181                 {
 182                   /* end of line in vpath is next */
 183                   phase += dists[i - start] - dist;
 184                   i++;
 185                   dist = 0;
 186                   if (toggle)
 187                     art_vpath_add_point (&result, &n_result, &n_result_max,
 188                                          ART_LINETO, vpath[i].x, vpath[i].y);
 189                 }
 190             }
 191         }
 192     }
 193
 194   art_vpath_add_point (&result, &n_result, &n_result_max,
 195                        ART_END, 0, 0);
 196
 197   art_free (dists);
 198
 199   return result;
 200 }