gfxpoly: added additional save method
[swftools.git] / 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