← Back to branch summary

~ml-launchpad/ubuntu/natty/gcompris/fix-for-777349

« back to all changes in this revision

Viewing changes to src/libart_lgpl/art_vpath_bpath.c

  • Committer: Bazaar Package Importer
  • Author(s): Marc Gariepy, Marc Gariepy, Stephane Graber
  • Date: 2010-01-04 17:42:49 UTC
  • mfrom: (1.1.14 upstream)
  • Revision ID: james.westby@ubuntu.com-20100104174249-7bupatd9dtxyhvs4
Tags: 9.0-0ubuntu1
[Marc Gariepy]
* New upstream release (9.0).
* Remove cache.c from POTFILES to avoid FTBFS
* Remove unneeded rm in debian/rules (file no longer exists upstream)

[Stephane Graber]
* Bump Debian standards to 3.8.3
* Add patch system (dpatch)

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/libart_lgpl/art_vpath_bpath.c
1
 
/* Libart_LGPL - library of basic graphic primitives
2
 
 * Copyright (C) 1998 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 3 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, see <http://www.gnu.org/licenses/>.
16
 
 * Boston, MA 02111-1307, USA.
17
 
 */
18
 
 
19
 
/* Basic constructors and operations for bezier paths */
20
 
 
21
 
#include "config.h"
22
 
#include "art_vpath_bpath.h"
23
 
 
24
 
#include <math.h>
25
 
 
26
 
#include "art_misc.h"
27
 
 
28
 
#include "art_bpath.h"
29
 
#include "art_vpath.h"
30
 
 
31
 
/* p must be allocated 2^level points. */
32
 
 
33
 
/* level must be >= 1 */
34
 
ArtPoint *
35
 
art_bezier_to_vec (double x0, double y0,
36
 
                   double x1, double y1,
37
 
                   double x2, double y2,
38
 
                   double x3, double y3,
39
 
                   ArtPoint *p,
40
 
                   int level)
41
 
{
42
 
  double x_m, y_m;
43
 
 
44
 
#ifdef VERBOSE
45
 
  printf ("bezier_to_vec: %g,%g %g,%g %g,%g %g,%g %d\n",
46
 
          x0, y0, x1, y1, x2, y2, x3, y3, level);
47
 
#endif
48
 
  if (level == 1) {
49
 
    x_m = (x0 + 3 * (x1 + x2) + x3) * 0.125;
50
 
    y_m = (y0 + 3 * (y1 + y2) + y3) * 0.125;
51
 
    p->x = x_m;
52
 
    p->y = y_m;
53
 
    p++;
54
 
    p->x = x3;
55
 
    p->y = y3;
56
 
    p++;
57
 
#ifdef VERBOSE
58
 
    printf ("-> (%g, %g) -> (%g, %g)\n", x_m, y_m, x3, y3);
59
 
#endif
60
 
  } else {
61
 
    double xa1, ya1;
62
 
    double xa2, ya2;
63
 
    double xb1, yb1;
64
 
    double xb2, yb2;
65
 
 
66
 
    xa1 = (x0 + x1) * 0.5;
67
 
    ya1 = (y0 + y1) * 0.5;
68
 
    xa2 = (x0 + 2 * x1 + x2) * 0.25;
69
 
    ya2 = (y0 + 2 * y1 + y2) * 0.25;
70
 
    xb1 = (x1 + 2 * x2 + x3) * 0.25;
71
 
    yb1 = (y1 + 2 * y2 + y3) * 0.25;
72
 
    xb2 = (x2 + x3) * 0.5;
73
 
    yb2 = (y2 + y3) * 0.5;
74
 
    x_m = (xa2 + xb1) * 0.5;
75
 
    y_m = (ya2 + yb1) * 0.5;
76
 
#ifdef VERBOSE
77
 
    printf ("%g,%g %g,%g %g,%g %g,%g\n", xa1, ya1, xa2, ya2,
78
 
            xb1, yb1, xb2, yb2);
79
 
#endif
80
 
    p = art_bezier_to_vec (x0, y0, xa1, ya1, xa2, ya2, x_m, y_m, p, level - 1);
81
 
    p = art_bezier_to_vec (x_m, y_m, xb1, yb1, xb2, yb2, x3, y3, p, level - 1);
82
 
  }
83
 
  return p;
84
 
}
85
 
 
86
 
#define RENDER_LEVEL 4
87
 
#define RENDER_SIZE (1 << (RENDER_LEVEL))
88
 
 
89
 
/**
90
 
 * art_vpath_render_bez: Render a bezier segment into the vpath.
91
 
 * @p_vpath: Where the pointer to the #ArtVpath structure is stored.
92
 
 * @pn_points: Pointer to the number of points in *@p_vpath.
93
 
 * @pn_points_max: Pointer to the number of points allocated.
94
 
 * @x0: X coordinate of starting bezier point.
95
 
 * @y0: Y coordinate of starting bezier point.
96
 
 * @x1: X coordinate of first bezier control point.
97
 
 * @y1: Y coordinate of first bezier control point.
98
 
 * @x2: X coordinate of second bezier control point.
99
 
 * @y2: Y coordinate of second bezier control point.
100
 
 * @x3: X coordinate of ending bezier point.
101
 
 * @y3: Y coordinate of ending bezier point.
102
 
 * @flatness: Flatness control.
103
 
 *
104
 
 * Renders a bezier segment into the vector path, reallocating and
105
 
 * updating *@p_vpath and *@pn_vpath_max as necessary. *@pn_vpath is
106
 
 * incremented by the number of vector points added.
107
 
 *
108
 
 * This step includes (@x0, @y0) but not (@x3, @y3).
109
 
 *
110
 
 * The @flatness argument guides the amount of subdivision. The Adobe
111
 
 * PostScript reference manual defines flatness as the maximum
112
 
 * deviation between the any point on the vpath approximation and the
113
 
 * corresponding point on the "true" curve, and we follow this
114
 
 * definition here. A value of 0.25 should ensure high quality for aa
115
 
 * rendering.
116
 
**/
117
 
static void
118
 
art_vpath_render_bez (ArtVpath **p_vpath, int *pn, int *pn_max,
119
 
                      double x0, double y0,
120
 
                      double x1, double y1,
121
 
                      double x2, double y2,
122
 
                      double x3, double y3,
123
 
                      double flatness)
124
 
{
125
 
  double x3_0, y3_0;
126
 
  double z3_0_dot;
127
 
  double z1_dot, z2_dot;
128
 
  double z1_perp, z2_perp;
129
 
  double max_perp_sq;
130
 
 
131
 
  double x_m, y_m;
132
 
  double xa1, ya1;
133
 
  double xa2, ya2;
134
 
  double xb1, yb1;
135
 
  double xb2, yb2;
136
 
 
137
 
  /* It's possible to optimize this routine a fair amount.
138
 
 
139
 
     First, once the _dot conditions are met, they will also be met in
140
 
     all further subdivisions. So we might recurse to a different
141
 
     routine that only checks the _perp conditions.
142
 
 
143
 
     Second, the distance _should_ decrease according to fairly
144
 
     predictable rules (a factor of 4 with each subdivision). So it might
145
 
     be possible to note that the distance is within a factor of 4 of
146
 
     acceptable, and subdivide once. But proving this might be hard.
147
 
 
148
 
     Third, at the last subdivision, x_m and y_m can be computed more
149
 
     expeditiously (as in the routine above).
150
 
 
151
 
     Finally, if we were able to subdivide by, say 2 or 3, this would
152
 
     allow considerably finer-grain control, i.e. fewer points for the
153
 
     same flatness tolerance. This would speed things up downstream.
154
 
 
155
 
     In any case, this routine is unlikely to be the bottleneck. It's
156
 
     just that I have this undying quest for more speed...
157
 
 
158
 
  */
159
 
 
160
 
  x3_0 = x3 - x0;
161
 
  y3_0 = y3 - y0;
162
 
 
163
 
  /* z3_0_dot is dist z0-z3 squared */
164
 
  z3_0_dot = x3_0 * x3_0 + y3_0 * y3_0;
165
 
 
166
 
  if (z3_0_dot < 0.001)
167
 
    {
168
 
      /* if start and end point are almost identical, the flatness tests
169
 
       * don't work properly, so fall back on testing whether both of
170
 
       * the other two control points are the same as the start point,
171
 
       * too.
172
 
       */
173
 
      if (hypot(x1 - x0, y1 - y0) < 0.001
174
 
          && hypot(x2 - x0, y2 - y0) < 0.001)
175
 
          goto nosubdivide;
176
 
      else
177
 
          goto subdivide;
178
 
    }
179
 
 
180
 
  /* we can avoid subdivision if:
181
 
 
182
 
     z1 has distance no more than flatness from the z0-z3 line
183
 
 
184
 
     z1 is no more z0'ward than flatness past z0-z3
185
 
 
186
 
     z1 is more z0'ward than z3'ward on the line traversing z0-z3
187
 
 
188
 
     and correspondingly for z2 */
189
 
 
190
 
  /* perp is distance from line, multiplied by dist z0-z3 */
191
 
  max_perp_sq = flatness * flatness * z3_0_dot;
192
 
 
193
 
  z1_perp = (y1 - y0) * x3_0 - (x1 - x0) * y3_0;
194
 
  if (z1_perp * z1_perp > max_perp_sq)
195
 
    goto subdivide;
196
 
 
197
 
  z2_perp = (y3 - y2) * x3_0 - (x3 - x2) * y3_0;
198
 
  if (z2_perp * z2_perp > max_perp_sq)
199
 
    goto subdivide;
200
 
 
201
 
  z1_dot = (x1 - x0) * x3_0 + (y1 - y0) * y3_0;
202
 
  if (z1_dot < 0 && z1_dot * z1_dot > max_perp_sq)
203
 
    goto subdivide;
204
 
 
205
 
  z2_dot = (x3 - x2) * x3_0 + (y3 - y2) * y3_0;
206
 
  if (z2_dot < 0 && z2_dot * z2_dot > max_perp_sq)
207
 
    goto subdivide;
208
 
 
209
 
  if (z1_dot + z1_dot > z3_0_dot)
210
 
    goto subdivide;
211
 
 
212
 
  if (z2_dot + z2_dot > z3_0_dot)
213
 
    goto subdivide;
214
 
 
215
 
 
216
 
 nosubdivide:
217
 
  /* don't subdivide */
218
 
  art_vpath_add_point (p_vpath, pn, pn_max,
219
 
                       ART_LINETO, x3, y3);
220
 
  return;
221
 
 
222
 
 subdivide:
223
 
 
224
 
  xa1 = (x0 + x1) * 0.5;
225
 
  ya1 = (y0 + y1) * 0.5;
226
 
  xa2 = (x0 + 2 * x1 + x2) * 0.25;
227
 
  ya2 = (y0 + 2 * y1 + y2) * 0.25;
228
 
  xb1 = (x1 + 2 * x2 + x3) * 0.25;
229
 
  yb1 = (y1 + 2 * y2 + y3) * 0.25;
230
 
  xb2 = (x2 + x3) * 0.5;
231
 
  yb2 = (y2 + y3) * 0.5;
232
 
  x_m = (xa2 + xb1) * 0.5;
233
 
  y_m = (ya2 + yb1) * 0.5;
234
 
#ifdef VERBOSE
235
 
  printf ("%g,%g %g,%g %g,%g %g,%g\n", xa1, ya1, xa2, ya2,
236
 
          xb1, yb1, xb2, yb2);
237
 
#endif
238
 
  art_vpath_render_bez (p_vpath, pn, pn_max,
239
 
                        x0, y0, xa1, ya1, xa2, ya2, x_m, y_m, flatness);
240
 
  art_vpath_render_bez (p_vpath, pn, pn_max,
241
 
                        x_m, y_m, xb1, yb1, xb2, yb2, x3, y3, flatness);
242
 
}
243
 
 
244
 
/**
245
 
 * art_bez_path_to_vec: Create vpath from bezier path.
246
 
 * @bez: Bezier path.
247
 
 * @flatness: Flatness control.
248
 
 *
249
 
 * Creates a vector path closely approximating the bezier path defined by
250
 
 * @bez. The @flatness argument controls the amount of subdivision. In
251
 
 * general, the resulting vpath deviates by at most @flatness pixels
252
 
 * from the "ideal" path described by @bez.
253
 
 *
254
 
 * Return value: Newly allocated vpath.
255
 
 **/
256
 
ArtVpath *
257
 
art_bez_path_to_vec (const ArtBpath *bez, double flatness)
258
 
{
259
 
  ArtVpath *vec;
260
 
  int vec_n, vec_n_max;
261
 
  int bez_index;
262
 
  double x, y;
263
 
 
264
 
  vec_n = 0;
265
 
  vec_n_max = RENDER_SIZE;
266
 
  vec = art_new (ArtVpath, vec_n_max);
267
 
 
268
 
  /* Initialization is unnecessary because of the precondition that the
269
 
     bezier path does not begin with LINETO or CURVETO, but is here
270
 
     to make the code warning-free. */
271
 
  x = 0;
272
 
  y = 0;
273
 
 
274
 
  bez_index = 0;
275
 
  do
276
 
    {
277
 
#ifdef VERBOSE
278
 
      printf ("%s %g %g\n",
279
 
              bez[bez_index].code == ART_CURVETO ? "curveto" :
280
 
              bez[bez_index].code == ART_LINETO ? "lineto" :
281
 
              bez[bez_index].code == ART_MOVETO ? "moveto" :
282
 
              bez[bez_index].code == ART_MOVETO_OPEN ? "moveto-open" :
283
 
              "end", bez[bez_index].x3, bez[bez_index].y3);
284
 
#endif
285
 
      /* make sure space for at least one more code */
286
 
      if (vec_n >= vec_n_max)
287
 
        art_expand (vec, ArtVpath, vec_n_max);
288
 
      switch (bez[bez_index].code)
289
 
        {
290
 
        case ART_MOVETO_OPEN:
291
 
        case ART_MOVETO:
292
 
        case ART_LINETO:
293
 
          x = bez[bez_index].x3;
294
 
          y = bez[bez_index].y3;
295
 
          vec[vec_n].code = bez[bez_index].code;
296
 
          vec[vec_n].x = x;
297
 
          vec[vec_n].y = y;
298
 
          vec_n++;
299
 
          break;
300
 
        case ART_END:
301
 
          vec[vec_n].code = bez[bez_index].code;
302
 
          vec[vec_n].x = 0;
303
 
          vec[vec_n].y = 0;
304
 
          vec_n++;
305
 
          break;
306
 
        case ART_CURVETO:
307
 
#ifdef VERBOSE
308
 
          printf ("%g,%g %g,%g %g,%g %g,%g\n", x, y,
309
 
                         bez[bez_index].x1, bez[bez_index].y1,
310
 
                         bez[bez_index].x2, bez[bez_index].y2,
311
 
                         bez[bez_index].x3, bez[bez_index].y3);
312
 
#endif
313
 
          art_vpath_render_bez (&vec, &vec_n, &vec_n_max,
314
 
                                x, y,
315
 
                                bez[bez_index].x1, bez[bez_index].y1,
316
 
                                bez[bez_index].x2, bez[bez_index].y2,
317
 
                                bez[bez_index].x3, bez[bez_index].y3,
318
 
                                flatness);
319
 
          x = bez[bez_index].x3;
320
 
          y = bez[bez_index].y3;
321
 
          break;
322
 
        }
323
 
    }
324
 
  while (bez[bez_index++].code != ART_END);
325
 
  return vec;
326
 
}
327