source: trunk/third/libart_lgpl/art_svp_vpath.c @ 18256

Revision 18256, 5.4 KB checked in by ghudson, 22 years ago (diff)
This commit was generated by cvs2svn to compensate for changes in r18255, which included commits to RCS files with non-trunk default branches.
Line 
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 */
35static void
36reverse_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 **/
66ArtSVP *
67art_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
Note: See TracBrowser for help on using the repository browser.