path.c revision 534c13302291c07a44afd528f4c758ced4296db5
1/**************************************************************************
2 *
3 * Copyright 2009 VMware, Inc.  All Rights Reserved.
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the
7 * "Software"), to deal in the Software without restriction, including
8 * without limitation the rights to use, copy, modify, merge, publish,
9 * distribute, sub license, and/or sell copies of the Software, and to
10 * permit persons to whom the Software is furnished to do so, subject to
11 * the following conditions:
12 *
13 * The above copyright notice and this permission notice (including the
14 * next paragraph) shall be included in all copies or substantial portions
15 * of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
18 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
20 * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
21 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
22 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
23 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24 *
25 **************************************************************************/
26
27#include "path.h"
28
29#include "stroker.h"
30#include "polygon.h"
31#include "bezier.h"
32#include "matrix.h"
33#include "vg_context.h"
34#include "util_array.h"
35#include "arc.h"
36#include "path_utils.h"
37#include "paint.h"
38#include "shader.h"
39
40#include "util/u_memory.h"
41
42#include <assert.h>
43
44#define DEBUG_PATH 0
45
46struct path {
47   struct vg_object base;
48   VGbitfield caps;
49   VGboolean dirty;
50   VGboolean dirty_stroke;
51
52   VGPathDatatype datatype;
53
54   VGfloat scale;
55   VGfloat bias;
56
57   VGint num_segments;
58
59   struct array * segments;
60   struct array * control_points;
61
62   struct {
63      struct polygon_array polygon_array;
64      struct matrix matrix;
65   } fill_polys;
66
67   struct {
68      struct path *path;
69      struct matrix matrix;
70      VGfloat stroke_width;
71      VGfloat miter_limit;
72      VGCapStyle cap_style;
73      VGJoinStyle join_style;
74   } stroked;
75};
76
77
78static INLINE void data_at(void **data,
79                           struct path *p,
80                           VGint start, VGint count,
81                           VGfloat *out)
82{
83   VGPathDatatype dt = p->datatype;
84   VGint i;
85   VGint end = start + count;
86   VGfloat *itr = out;
87
88   switch(dt) {
89   case VG_PATH_DATATYPE_S_8: {
90      VGbyte **bdata = (VGbyte **)data;
91      for (i = start; i < end; ++i) {
92         *itr = (*bdata)[i];
93         ++itr;
94      }
95      *bdata += count;
96   }
97      break;
98   case VG_PATH_DATATYPE_S_16: {
99      VGshort **bdata = (VGshort **)data;
100      for (i = start; i < end; ++i) {
101         *itr = (*bdata)[i];
102         ++itr;
103      }
104      *bdata += count;
105   }
106      break;
107   case VG_PATH_DATATYPE_S_32: {
108      VGint **bdata = (VGint **)data;
109      for (i = start; i < end; ++i) {
110         *itr = (*bdata)[i];
111         ++itr;
112      }
113      *bdata += count;
114   }
115      break;
116   case VG_PATH_DATATYPE_F: {
117      VGfloat **fdata = (VGfloat **)data;
118      for (i = start; i < end; ++i) {
119         *itr = (*fdata)[i];
120         ++itr;
121      }
122      *fdata += count;
123   }
124      break;
125   default:
126      debug_assert(!"Unknown path datatype!");
127   }
128}
129
130
131void vg_float_to_datatype(VGPathDatatype datatype,
132                          VGubyte *common_data,
133                          const VGfloat *data,
134                          VGint num_coords)
135{
136   VGint i;
137   switch(datatype) {
138   case VG_PATH_DATATYPE_S_8: {
139      for (i = 0; i < num_coords; ++i) {
140         common_data[i] = (VGubyte)data[i];
141      }
142   }
143      break;
144   case VG_PATH_DATATYPE_S_16: {
145      VGshort *buf = (VGshort*)common_data;
146      for (i = 0; i < num_coords; ++i) {
147         buf[i] = (VGshort)data[i];
148      }
149   }
150      break;
151   case VG_PATH_DATATYPE_S_32: {
152      VGint *buf = (VGint*)common_data;
153      for (i = 0; i < num_coords; ++i) {
154         buf[i] = (VGint)data[i];
155      }
156   }
157      break;
158   case VG_PATH_DATATYPE_F: {
159      memcpy(common_data, data, sizeof(VGfloat) * num_coords);
160   }
161      break;
162   default:
163      debug_assert(!"Unknown path datatype!");
164   }
165}
166
167static void coords_adjust_by_scale_bias(struct path *p,
168                                        void *pdata, VGint num_coords,
169                                        VGfloat scale, VGfloat bias,
170                                        VGPathDatatype datatype)
171{
172   VGfloat data[8];
173   void *coords = (VGfloat *)pdata;
174   VGubyte *common_data = (VGubyte *)pdata;
175   VGint size_dst = size_for_datatype(datatype);
176   VGint i;
177
178   for (i = 0; i < num_coords; ++i) {
179      data_at(&coords, p, 0, 1, data);
180      data[0] = data[0] * scale + bias;
181      vg_float_to_datatype(datatype, common_data, data, 1);
182      common_data += size_dst;
183   }
184}
185
186struct path * path_create(VGPathDatatype dt, VGfloat scale, VGfloat bias,
187                          VGint segmentCapacityHint,
188                          VGint coordCapacityHint,
189                          VGbitfield capabilities)
190{
191   struct path *path = CALLOC_STRUCT(path);
192
193   vg_init_object(&path->base, vg_current_context(), VG_OBJECT_PATH);
194   path->caps = capabilities & VG_PATH_CAPABILITY_ALL;
195   vg_context_add_object(vg_current_context(), VG_OBJECT_PATH, path);
196
197   path->datatype = dt;
198   path->scale = scale;
199   path->bias = bias;
200
201   path->segments = array_create(size_for_datatype(VG_PATH_DATATYPE_S_8));
202   path->control_points = array_create(size_for_datatype(dt));
203
204   path->dirty = VG_TRUE;
205   path->dirty_stroke = VG_TRUE;
206
207   return path;
208}
209
210void path_destroy(struct path *p)
211{
212   vg_context_remove_object(vg_current_context(), VG_OBJECT_PATH, p);
213
214   array_destroy(p->segments);
215   array_destroy(p->control_points);
216   array_destroy(p->fill_polys.polygon_array.array);
217
218   if (p->stroked.path)
219      path_destroy(p->stroked.path);
220
221   free(p);
222}
223
224VGbitfield path_capabilities(struct path *p)
225{
226   return p->caps;
227}
228
229void path_set_capabilities(struct path *p, VGbitfield bf)
230{
231   p->caps = (bf & VG_PATH_CAPABILITY_ALL);
232}
233
234void path_append_data(struct path *p,
235                      VGint numSegments,
236                      const VGubyte * pathSegments,
237                      const void * pathData)
238{
239   VGint old_segments = p->num_segments;
240   VGint num_new_coords = num_elements_for_segments(pathSegments, numSegments);
241   array_append_data(p->segments, pathSegments, numSegments);
242   array_append_data(p->control_points, pathData, num_new_coords);
243
244   p->num_segments += numSegments;
245   if (!floatsEqual(p->scale, 1.f) || !floatsEqual(p->bias, 0.f)) {
246      VGubyte *coords = (VGubyte*)p->control_points->data;
247      coords_adjust_by_scale_bias(p,
248                                  coords + old_segments * p->control_points->datatype_size,
249                                  num_new_coords,
250                                  p->scale, p->bias, p->datatype);
251   }
252   p->dirty = VG_TRUE;
253   p->dirty_stroke = VG_TRUE;
254}
255
256VGint path_num_segments(struct path *p)
257{
258   return p->num_segments;
259}
260
261static INLINE void map_if_relative(VGfloat ox, VGfloat oy,
262                                   VGboolean relative,
263                                   VGfloat *x, VGfloat *y)
264{
265   if (relative) {
266      if (x)
267         *x += ox;
268      if (y)
269         *y += oy;
270   }
271}
272
273static INLINE void close_polygon(struct polygon *current,
274                                 VGfloat sx, VGfloat sy,
275                                 VGfloat ox, VGfloat oy,
276                                 struct  matrix *matrix)
277{
278   if (!floatsEqual(sx, ox) ||
279       !floatsEqual(sy, oy)) {
280      VGfloat x0 = sx;
281      VGfloat y0 = sy;
282      matrix_map_point(matrix, x0, y0, &x0, &y0);
283      polygon_vertex_append(current, x0, y0);
284   }
285}
286
287static void convert_path(struct path *p,
288                          VGPathDatatype to,
289                          void *dst,
290                          VGint num_coords)
291{
292   VGfloat data[8];
293   void *coords = (VGfloat *)p->control_points->data;
294   VGubyte *common_data = (VGubyte *)dst;
295   VGint size_dst = size_for_datatype(to);
296   VGint i;
297
298   for (i = 0; i < num_coords; ++i) {
299      data_at(&coords, p, 0, 1, data);
300      vg_float_to_datatype(to, common_data, data, 1);
301      common_data += size_dst;
302   }
303}
304
305
306static void polygon_array_calculate_bounds( struct polygon_array *polyarray )
307{
308   struct array *polys = polyarray->array;
309   VGfloat min_x, max_x;
310   VGfloat min_y, max_y;
311   VGfloat bounds[4];
312   unsigned i;
313
314   assert(polys);
315   assert(polys->num_elements);
316   polygon_bounding_rect((((struct polygon**)polys->data)[0]), bounds);
317   min_x = bounds[0];
318   min_y = bounds[1];
319   max_x = bounds[0] + bounds[2];
320   max_y = bounds[1] + bounds[3];
321   for (i = 1; i < polys->num_elements; ++i) {
322      struct polygon *p = (((struct polygon**)polys->data)[i]);
323      polygon_bounding_rect(p, bounds);
324      min_x = MIN2(min_x, bounds[0]);
325      min_y = MIN2(min_y, bounds[1]);
326      max_x = MAX2(max_x, bounds[0] + bounds[2]);
327      max_y = MAX2(max_y, bounds[1] + bounds[3]);
328   }
329
330   polyarray->min_x = min_x;
331   polyarray->min_y = min_y;
332   polyarray->max_x = max_x;
333   polyarray->max_y = max_y;
334}
335
336
337static struct polygon_array * path_get_fill_polygons(struct path *p, struct matrix *matrix)
338{
339   VGint i;
340   struct polygon *current = 0;
341   VGfloat sx, sy, px, py, ox, oy;
342   VGfloat x0, y0, x1, y1, x2, y2, x3, y3;
343   VGfloat data[8];
344   void *coords = (VGfloat *)p->control_points->data;
345   struct array *array;
346
347   if (p->fill_polys.polygon_array.array)
348   {
349      if (memcmp( &p->fill_polys.matrix,
350                  matrix,
351                  sizeof *matrix ) == 0 && p->dirty == VG_FALSE)
352      {
353         return &p->fill_polys.polygon_array;
354      }
355      else {
356         array_destroy( p->fill_polys.polygon_array.array );
357         p->fill_polys.polygon_array.array = NULL;
358      }
359   }
360
361   array = array_create(sizeof(struct array*));
362
363   sx = sy = px = py = ox = oy = 0.f;
364
365   current = polygon_create(32);
366
367   for (i = 0; i < p->num_segments; ++i) {
368      VGubyte segment = ((VGubyte*)(p->segments->data))[i];
369      VGint command = SEGMENT_COMMAND(segment);
370      VGboolean relative = SEGMENT_ABS_REL(segment);
371
372      switch(command) {
373      case VG_CLOSE_PATH:
374         close_polygon(current, sx, sy, ox, oy, matrix);
375         ox = sx;
376         oy = sy;
377         break;
378      case VG_MOVE_TO:
379         if (current && polygon_vertex_count(current) > 0) {
380            /* add polygon */
381            close_polygon(current, sx, sy, ox, oy, matrix);
382            array_append_data(array, &current, 1);
383            current = polygon_create(32);
384         }
385         data_at(&coords, p, 0, 2, data);
386         x0 = data[0];
387         y0 = data[1];
388         map_if_relative(ox, oy, relative, &x0, &y0);
389         sx = x0;
390         sy = y0;
391         ox = x0;
392         oy = y0;
393         px = x0;
394         py = y0;
395         matrix_map_point(matrix, x0, y0, &x0, &y0);
396         polygon_vertex_append(current, x0, y0);
397         break;
398      case VG_LINE_TO:
399         data_at(&coords, p, 0, 2, data);
400         x0 = data[0];
401         y0 = data[1];
402         map_if_relative(ox, oy, relative, &x0, &y0);
403         ox = x0;
404         oy = y0;
405         px = x0;
406         py = y0;
407         matrix_map_point(matrix, x0, y0, &x0, &y0);
408         polygon_vertex_append(current, x0, y0);
409         break;
410      case VG_HLINE_TO:
411         data_at(&coords, p, 0, 1, data);
412         x0 = data[0];
413         y0 = oy;
414         map_if_relative(ox, oy, relative, &x0, 0);
415         ox = x0;
416         px = x0;
417         py = y0;
418         matrix_map_point(matrix, x0, y0, &x0, &y0);
419         polygon_vertex_append(current, x0, y0);
420         break;
421      case VG_VLINE_TO:
422         data_at(&coords, p, 0, 1, data);
423         x0 = ox;
424         y0 = data[0];
425         map_if_relative(ox, oy, relative, 0, &y0);
426         oy = y0;
427         px = x0;
428         py = y0;
429         matrix_map_point(matrix, x0, y0, &x0, &y0);
430         polygon_vertex_append(current, x0, y0);
431         break;
432      case VG_CUBIC_TO: {
433         struct bezier bezier;
434         data_at(&coords, p, 0, 6, data);
435         x0 = ox;
436         y0 = oy;
437         x1 = data[0];
438         y1 = data[1];
439         x2 = data[2];
440         y2 = data[3];
441         x3 = data[4];
442         y3 = data[5];
443         map_if_relative(ox, oy, relative, &x1, &y1);
444         map_if_relative(ox, oy, relative, &x2, &y2);
445         map_if_relative(ox, oy, relative, &x3, &y3);
446         ox = x3;
447         oy = y3;
448         px = x2;
449         py = y2;
450         assert(matrix_is_affine(matrix));
451         matrix_map_point(matrix, x0, y0, &x0, &y0);
452         matrix_map_point(matrix, x1, y1, &x1, &y1);
453         matrix_map_point(matrix, x2, y2, &x2, &y2);
454         matrix_map_point(matrix, x3, y3, &x3, &y3);
455         bezier_init(&bezier, x0, y0, x1, y1,
456                       x2, y2, x3, y3);
457         bezier_add_to_polygon(&bezier, current);
458      }
459         break;
460      case VG_QUAD_TO: {
461         struct bezier bezier;
462         data_at(&coords, p, 0, 4, data);
463         x0 = ox;
464         y0 = oy;
465         x1 = data[0];
466         y1 = data[1];
467         x3 = data[2];
468         y3 = data[3];
469         map_if_relative(ox, oy, relative, &x1, &y1);
470         map_if_relative(ox, oy, relative, &x3, &y3);
471         px = x1;
472         py = y1;
473         { /* form a cubic out of it */
474            x2 = (x3 + 2*x1) / 3.f;
475            y2 = (y3 + 2*y1) / 3.f;
476            x1 = (x0 + 2*x1) / 3.f;
477            y1 = (y0 + 2*y1) / 3.f;
478         }
479         ox = x3;
480         oy = y3;
481         assert(matrix_is_affine(matrix));
482         matrix_map_point(matrix, x0, y0, &x0, &y0);
483         matrix_map_point(matrix, x1, y1, &x1, &y1);
484         matrix_map_point(matrix, x2, y2, &x2, &y2);
485         matrix_map_point(matrix, x3, y3, &x3, &y3);
486         bezier_init(&bezier, x0, y0, x1, y1,
487                       x2, y2, x3, y3);
488         bezier_add_to_polygon(&bezier, current);
489      }
490         break;
491      case VG_SQUAD_TO: {
492         struct bezier bezier;
493         data_at(&coords, p, 0, 2, data);
494         x0 = ox;
495         y0 = oy;
496         x1 = 2*ox-px;
497         y1 = 2*oy-py;
498         x3 = data[0];
499         y3 = data[1];
500         map_if_relative(ox, oy, relative, &x3, &y3);
501         px = x1;
502         py = y1;
503         { /* form a cubic out of it */
504            x2 = (x3 + 2*x1) / 3.f;
505            y2 = (y3 + 2*y1) / 3.f;
506            x1 = (x0 + 2*x1) / 3.f;
507            y1 = (y0 + 2*y1) / 3.f;
508         }
509         ox = x3;
510         oy = y3;
511         assert(matrix_is_affine(matrix));
512         matrix_map_point(matrix, x0, y0, &x0, &y0);
513         matrix_map_point(matrix, x1, y1, &x1, &y1);
514         matrix_map_point(matrix, x2, y2, &x2, &y2);
515         matrix_map_point(matrix, x3, y3, &x3, &y3);
516         bezier_init(&bezier, x0, y0, x1, y1,
517                     x2, y2, x3, y3);
518         bezier_add_to_polygon(&bezier, current);
519      }
520         break;
521      case VG_SCUBIC_TO: {
522         struct bezier bezier;
523         data_at(&coords, p, 0, 4, data);
524         x0 = ox;
525         y0 = oy;
526         x1 = 2*ox-px;
527         y1 = 2*oy-py;
528         x2 = data[0];
529         y2 = data[1];
530         x3 = data[2];
531         y3 = data[3];
532         map_if_relative(ox, oy, relative, &x2, &y2);
533         map_if_relative(ox, oy, relative, &x3, &y3);
534         ox = x3;
535         oy = y3;
536         px = x2;
537         py = y2;
538         assert(matrix_is_affine(matrix));
539         matrix_map_point(matrix, x0, y0, &x0, &y0);
540         matrix_map_point(matrix, x1, y1, &x1, &y1);
541         matrix_map_point(matrix, x2, y2, &x2, &y2);
542         matrix_map_point(matrix, x3, y3, &x3, &y3);
543         bezier_init(&bezier, x0, y0, x1, y1,
544                              x2, y2, x3, y3);
545         bezier_add_to_polygon(&bezier, current);
546      }
547         break;
548      case VG_SCCWARC_TO:
549      case VG_SCWARC_TO:
550      case VG_LCCWARC_TO:
551      case VG_LCWARC_TO: {
552         VGfloat rh, rv, rot;
553         struct arc arc;
554
555         data_at(&coords, p, 0, 5, data);
556         x0  = ox;
557         y0  = oy;
558         rh  = data[0];
559         rv  = data[1];
560         rot = data[2];
561         x1  = data[3];
562         y1  = data[4];
563         map_if_relative(ox, oy, relative, &x1, &y1);
564#if 0
565         debug_printf("------- ARC (%f, %f), (%f, %f) %f, %f, %f\n",
566                      x0, y0, x1, y1, rh, rv, rot);
567#endif
568         arc_init(&arc, command, x0, y0, x1, y1,
569                  rh, rv, rot);
570         arc_add_to_polygon(&arc, current,
571                            matrix);
572         ox = x1;
573         oy = y1;
574         px = x1;
575         py = y1;
576      }
577         break;
578      default:
579         abort();
580         assert(!"Unknown segment!");
581      }
582   }
583   if (current) {
584      if (polygon_vertex_count(current) > 0) {
585         close_polygon(current, sx, sy, ox, oy, matrix);
586         array_append_data(array, &current, 1);
587      } else
588         polygon_destroy(current);
589   }
590
591   p->fill_polys.polygon_array.array = array;
592   p->fill_polys.matrix = *matrix;
593
594   polygon_array_calculate_bounds( &p->fill_polys.polygon_array );
595
596   p->dirty = VG_FALSE;
597
598   return &p->fill_polys.polygon_array;
599}
600
601VGbyte path_datatype_size(struct path *p)
602{
603   return size_for_datatype(p->datatype);
604}
605
606VGPathDatatype path_datatype(struct path *p)
607{
608   return p->datatype;
609}
610
611VGfloat path_scale(struct path *p)
612{
613   return p->scale;
614}
615
616VGfloat path_bias(struct path *p)
617{
618   return p->bias;
619}
620
621VGint path_num_coords(struct path *p)
622{
623   return num_elements_for_segments((VGubyte*)p->segments->data,
624                                    p->num_segments);
625}
626
627void path_modify_coords(struct path *p,
628                        VGint startIndex,
629                        VGint numSegments,
630                        const void * pathData)
631{
632   VGubyte *segments = (VGubyte*)(p->segments->data);
633   VGint count = num_elements_for_segments(&segments[startIndex], numSegments);
634   VGint start_cp = num_elements_for_segments(segments, startIndex);
635
636   array_change_data(p->control_points, pathData, start_cp, count);
637   coords_adjust_by_scale_bias(p,
638                               ((VGubyte*)p->control_points->data) +
639                               (startIndex * p->control_points->datatype_size),
640                               path_num_coords(p),
641                               p->scale, p->bias, p->datatype);
642   p->dirty = VG_TRUE;
643   p->dirty_stroke = VG_TRUE;
644}
645
646void path_for_each_segment(struct path *path,
647                           path_for_each_cb cb,
648                           void *user_data)
649{
650   VGint i;
651   struct path_for_each_data p;
652   VGfloat data[8];
653   void *coords = (VGfloat *)path->control_points->data;
654
655   p.coords = data;
656   p.sx = p.sy = p.px = p.py = p.ox = p.oy = 0.f;
657   p.user_data = user_data;
658
659   for (i = 0; i < path->num_segments; ++i) {
660      VGint command;
661      VGboolean relative;
662
663      p.segment = ((VGubyte*)(path->segments->data))[i];
664      command = SEGMENT_COMMAND(p.segment);
665      relative = SEGMENT_ABS_REL(p.segment);
666
667      switch(command) {
668      case VG_CLOSE_PATH:
669         cb(path, &p);
670         break;
671      case VG_MOVE_TO:
672         data_at(&coords, path, 0, 2, data);
673         map_if_relative(p.ox, p.oy, relative, &data[0], &data[1]);
674         cb(path, &p);
675         p.sx = data[0];
676         p.sy = data[1];
677         p.ox = data[0];
678         p.oy = data[1];
679         p.px = data[0];
680         p.py = data[1];
681         break;
682      case VG_LINE_TO:
683         data_at(&coords, path, 0, 2, data);
684         map_if_relative(p.ox, p.oy, relative, &data[0], &data[1]);
685         cb(path, &p);
686         p.ox = data[0];
687         p.oy = data[1];
688         p.px = data[0];
689         p.py = data[1];
690         break;
691      case VG_HLINE_TO:
692         data_at(&coords, path, 0, 1, data);
693         map_if_relative(p.ox, p.oy, relative, &data[0], 0);
694         p.segment = VG_LINE_TO;
695         data[1] = p.oy;
696         cb(path, &p);
697         p.ox = data[0];
698         p.oy = data[1];
699         p.px = data[0];
700         p.py = data[1];
701         break;
702      case VG_VLINE_TO:
703         data_at(&coords, path, 0, 1, data);
704         map_if_relative(p.ox, p.oy, relative, 0, &data[0]);
705         p.segment = VG_LINE_TO;
706         data[1] = data[0];
707         data[0] = p.ox;
708         cb(path, &p);
709         p.ox = data[0];
710         p.oy = data[1];
711         p.px = data[0];
712         p.py = data[1];
713         break;
714      case VG_CUBIC_TO: {
715         data_at(&coords, path, 0, 6, data);
716         map_if_relative(p.ox, p.oy, relative, &data[0], &data[1]);
717         map_if_relative(p.ox, p.oy, relative, &data[2], &data[3]);
718         map_if_relative(p.ox, p.oy, relative, &data[4], &data[5]);
719         cb(path, &p);
720         p.px = data[2];
721         p.py = data[3];
722         p.ox = data[4];
723         p.oy = data[5];
724      }
725         break;
726      case VG_QUAD_TO: {
727         data_at(&coords, path, 0, 4, data);
728         map_if_relative(p.ox, p.oy, relative, &data[0], &data[1]);
729         map_if_relative(p.ox, p.oy, relative, &data[2], &data[3]);
730         cb(path, &p);
731         p.px = data[0];
732         p.py = data[1];
733         p.ox = data[2];
734         p.oy = data[3];
735      }
736         break;
737      case VG_SQUAD_TO: {
738         data_at(&coords, path, 0, 2, data);
739         map_if_relative(p.ox, p.oy, relative, &data[0], &data[1]);
740         cb(path, &p);
741         p.px = 2*p.ox-p.px;
742         p.py = 2*p.oy-p.py;
743         p.ox = data[2];
744         p.oy = data[3];
745      }
746         break;
747      case VG_SCUBIC_TO: {
748         data_at(&coords, path, 0, 4, data);
749         map_if_relative(p.ox, p.oy, relative, &data[0], &data[1]);
750         map_if_relative(p.ox, p.oy, relative, &data[2], &data[3]);
751         cb(path, &p);
752         p.px = data[0];
753         p.py = data[1];
754         p.ox = data[2];
755         p.oy = data[3];
756      }
757         break;
758      case VG_SCCWARC_TO:
759      case VG_SCWARC_TO:
760      case VG_LCCWARC_TO:
761      case VG_LCWARC_TO: {
762         data_at(&coords, path, 0, 5, data);
763         map_if_relative(p.ox, p.oy, relative, &data[3], &data[4]);
764#if 0
765         debug_printf("------- ARC (%f, %f), (%f, %f) %f, %f, %f\n",
766                      p.ox, p.oy, data[3], data[4], data[0], data[1], data[2]);
767#endif
768         cb(path, &p);
769         p.ox = data[3];
770         p.oy = data[4];
771         p.px = data[3];
772         p.py = data[4];
773      }
774         break;
775      default:
776         abort();
777         assert(!"Unknown segment!");
778      }
779   }
780}
781
782struct transform_data {
783   struct array *segments;
784   struct array *coords;
785
786   struct matrix *matrix;
787
788   VGPathDatatype datatype;
789};
790
791static VGboolean transform_cb(struct path *p,
792                              struct path_for_each_data *pd)
793{
794   struct transform_data *td = (struct transform_data *)pd->user_data;
795   VGint num_coords = num_elements_for_segments(&pd->segment, 1);
796   VGubyte segment = SEGMENT_COMMAND(pd->segment);/* abs bit is 0 */
797   VGfloat data[8];
798   VGubyte common_data[sizeof(VGfloat)*8];
799
800   memcpy(data, pd->coords, sizeof(VGfloat) * num_coords);
801
802   switch(segment) {
803   case VG_CLOSE_PATH:
804      break;
805   case VG_MOVE_TO:
806      matrix_map_point(td->matrix,
807                       data[0], data[1], &data[0], &data[1]);
808      break;
809   case VG_LINE_TO:
810      matrix_map_point(td->matrix,
811                       data[0], data[1], &data[0], &data[1]);
812      break;
813   case VG_HLINE_TO:
814   case VG_VLINE_TO:
815      assert(0);
816      break;
817   case VG_QUAD_TO:
818      matrix_map_point(td->matrix,
819                       data[0], data[1], &data[0], &data[1]);
820      matrix_map_point(td->matrix,
821                       data[2], data[3], &data[2], &data[3]);
822      break;
823   case VG_CUBIC_TO:
824      matrix_map_point(td->matrix,
825                       data[0], data[1], &data[0], &data[1]);
826      matrix_map_point(td->matrix,
827                       data[2], data[3], &data[2], &data[3]);
828      matrix_map_point(td->matrix,
829                       data[4], data[5], &data[4], &data[5]);
830      break;
831   case VG_SQUAD_TO:
832      matrix_map_point(td->matrix,
833                       data[0], data[1], &data[0], &data[1]);
834      break;
835   case VG_SCUBIC_TO:
836      matrix_map_point(td->matrix,
837                       data[0], data[1], &data[0], &data[1]);
838      matrix_map_point(td->matrix,
839                       data[2], data[3], &data[2], &data[3]);
840      break;
841   case VG_SCCWARC_TO:
842   case VG_SCWARC_TO:
843   case VG_LCCWARC_TO:
844   case VG_LCWARC_TO: {
845      struct arc arc;
846      struct path *path = path_create(td->datatype,
847                                      1, 0, 0, 0, VG_PATH_CAPABILITY_ALL);
848      arc_init(&arc, segment,
849               pd->ox, pd->oy, data[3], data[4],
850               data[0], data[1], data[2]);
851
852      arc_to_path(&arc, path, td->matrix);
853
854      num_coords = path_num_coords(path);
855
856      array_append_data(td->segments, path->segments->data,
857                        path->num_segments);
858      array_append_data(td->coords, path->control_points->data,
859                        num_coords);
860      path_destroy(path);
861
862      return VG_TRUE;
863   }
864      break;
865   default:
866      break;
867   }
868
869   vg_float_to_datatype(td->datatype, common_data, data, num_coords);
870
871   array_append_data(td->segments, &pd->segment, 1);
872   array_append_data(td->coords, common_data, num_coords);
873   return VG_TRUE;
874}
875
876void path_transform(struct path *dst, struct path *src)
877{
878   struct transform_data data;
879   struct vg_context *ctx = dst->base.ctx;
880
881   data.segments =  dst->segments;
882   data.coords   =  dst->control_points;
883   data.matrix   = &ctx->state.vg.path_user_to_surface_matrix;
884   data.datatype = dst->datatype;
885
886   path_for_each_segment(src, transform_cb, (void*)&data);
887
888   dst->num_segments = dst->segments->num_elements;
889   dst->dirty = VG_TRUE;
890   dst->dirty_stroke = VG_TRUE;
891}
892
893void path_append_path(struct path *dst,
894                      struct path *src)
895{
896   VGint num_coords = path_num_coords(src);
897   void *dst_data = malloc(size_for_datatype(dst->datatype) * num_coords);
898   array_append_data(dst->segments,
899                     src->segments->data,
900                     src->num_segments);
901   convert_path(src, dst->datatype,
902                dst_data, num_coords);
903   array_append_data(dst->control_points,
904                     dst_data,
905                     num_coords);
906   free(dst_data);
907
908   dst->num_segments += src->num_segments;
909   dst->dirty = VG_TRUE;
910   dst->dirty_stroke = VG_TRUE;
911}
912
913static INLINE VGboolean is_segment_arc(VGubyte segment)
914{
915   VGubyte scommand = SEGMENT_COMMAND(segment);
916   return (scommand == VG_SCCWARC_TO ||
917           scommand == VG_SCWARC_TO ||
918           scommand == VG_LCCWARC_TO ||
919           scommand == VG_LCWARC_TO);
920}
921
922struct path_iter_data {
923   struct path *path;
924   VGubyte segment;
925   void *coords;
926   VGfloat px, py, ox, oy, sx, sy;
927};
928static INLINE VGubyte normalize_coords(struct path_iter_data *pd,
929                                       VGint *num_coords,
930                                       VGfloat *data)
931{
932   VGint command = SEGMENT_COMMAND(pd->segment);
933   VGboolean relative = SEGMENT_ABS_REL(pd->segment);
934
935   switch(command) {
936   case VG_CLOSE_PATH:
937      *num_coords = 0;
938      pd->ox = pd->sx;
939      pd->oy = pd->sy;
940      return VG_CLOSE_PATH;
941      break;
942   case VG_MOVE_TO:
943      data_at(&pd->coords, pd->path, 0, 2, data);
944      map_if_relative(pd->ox, pd->oy, relative, &data[0], &data[1]);
945      pd->sx = data[0];
946      pd->sy = data[1];
947      pd->ox = data[0];
948      pd->oy = data[1];
949      pd->px = data[0];
950      pd->py = data[1];
951      *num_coords = 2;
952      return VG_MOVE_TO_ABS;
953      break;
954   case VG_LINE_TO:
955      data_at(&pd->coords, pd->path, 0, 2, data);
956      map_if_relative(pd->ox, pd->oy, relative, &data[0], &data[1]);
957      pd->ox = data[0];
958      pd->oy = data[1];
959      pd->px = data[0];
960      pd->py = data[1];
961      *num_coords = 2;
962      return VG_LINE_TO_ABS;
963      break;
964   case VG_HLINE_TO:
965      data_at(&pd->coords, pd->path, 0, 1, data);
966      map_if_relative(pd->ox, pd->oy, relative, &data[0], 0);
967      data[1] = pd->oy;
968      pd->ox = data[0];
969      pd->oy = data[1];
970      pd->px = data[0];
971      pd->py = data[1];
972      *num_coords = 2;
973      return VG_LINE_TO_ABS;
974      break;
975   case VG_VLINE_TO:
976      data_at(&pd->coords, pd->path, 0, 1, data);
977      map_if_relative(pd->ox, pd->oy, relative, 0, &data[0]);
978      data[1] = data[0];
979      data[0] = pd->ox;
980      pd->ox = data[0];
981      pd->oy = data[1];
982      pd->px = data[0];
983      pd->py = data[1];
984      *num_coords = 2;
985      return VG_LINE_TO_ABS;
986      break;
987   case VG_CUBIC_TO: {
988      data_at(&pd->coords, pd->path, 0, 6, data);
989      map_if_relative(pd->ox, pd->oy, relative, &data[0], &data[1]);
990      map_if_relative(pd->ox, pd->oy, relative, &data[2], &data[3]);
991      map_if_relative(pd->ox, pd->oy, relative, &data[4], &data[5]);
992      pd->px = data[2];
993      pd->py = data[3];
994      pd->ox = data[4];
995      pd->oy = data[5];
996      *num_coords = 6;
997      return VG_CUBIC_TO_ABS;
998   }
999      break;
1000   case VG_QUAD_TO: {
1001      VGfloat x0, y0, x1, y1, x2, y2, x3, y3;
1002      data_at(&pd->coords, pd->path, 0, 4, data);
1003      x0 = pd->ox;
1004      y0 = pd->oy;
1005      x1 = data[0];
1006      y1 = data[1];
1007      x3 = data[2];
1008      y3 = data[3];
1009      map_if_relative(pd->ox, pd->oy, relative, &x1, &y1);
1010      map_if_relative(pd->ox, pd->oy, relative, &x3, &y3);
1011      pd->px = x1;
1012      pd->py = y1;
1013      { /* form a cubic out of it */
1014         x2 = (x3 + 2*x1) / 3.f;
1015         y2 = (y3 + 2*y1) / 3.f;
1016         x1 = (x0 + 2*x1) / 3.f;
1017         y1 = (y0 + 2*y1) / 3.f;
1018      }
1019      pd->ox = x3;
1020      pd->oy = y3;
1021      data[0] = x1;
1022      data[1] = y1;
1023      data[2] = x2;
1024      data[3] = y2;
1025      data[4] = x3;
1026      data[5] = y3;
1027      *num_coords = 6;
1028      return VG_CUBIC_TO_ABS;
1029   }
1030      break;
1031   case VG_SQUAD_TO: {
1032      VGfloat x0, y0, x1, y1, x2, y2, x3, y3;
1033      data_at(&pd->coords, pd->path, 0, 2, data);
1034      x0 = pd->ox;
1035      y0 = pd->oy;
1036      x1 = 2 * pd->ox - pd->px;
1037      y1 = 2 * pd->oy - pd->py;
1038      x3 = data[0];
1039      y3 = data[1];
1040      map_if_relative(pd->ox, pd->oy, relative, &x3, &y3);
1041      pd->px = x1;
1042      pd->py = y1;
1043      { /* form a cubic out of it */
1044         x2 = (x3 + 2*x1) / 3.f;
1045         y2 = (y3 + 2*y1) / 3.f;
1046         x1 = (x0 + 2*x1) / 3.f;
1047         y1 = (y0 + 2*y1) / 3.f;
1048      }
1049      pd->ox = x3;
1050      pd->oy = y3;
1051      data[0] = x1;
1052      data[1] = y1;
1053      data[2] = x2;
1054      data[3] = y2;
1055      data[4] = x3;
1056      data[5] = y3;
1057      *num_coords = 6;
1058      return VG_CUBIC_TO_ABS;
1059   }
1060      break;
1061   case VG_SCUBIC_TO: {
1062      VGfloat x0, y0, x1, y1, x2, y2, x3, y3;
1063      data_at(&pd->coords, pd->path, 0, 4, data);
1064      x0 = pd->ox;
1065      y0 = pd->oy;
1066      x1 = 2*pd->ox-pd->px;
1067      y1 = 2*pd->oy-pd->py;
1068      x2 = data[0];
1069      y2 = data[1];
1070      x3 = data[2];
1071      y3 = data[3];
1072      map_if_relative(pd->ox, pd->oy, relative, &x2, &y2);
1073      map_if_relative(pd->ox, pd->oy, relative, &x3, &y3);
1074      pd->ox = x3;
1075      pd->oy = y3;
1076      pd->px = x2;
1077      pd->py = y2;
1078      data[0] = x1;
1079      data[1] = y1;
1080      data[2] = x2;
1081      data[3] = y2;
1082      data[4] = x3;
1083      data[5] = y3;
1084      *num_coords = 6;
1085      return VG_CUBIC_TO_ABS;
1086   }
1087      break;
1088   case VG_SCCWARC_TO:
1089   case VG_SCWARC_TO:
1090   case VG_LCCWARC_TO:
1091   case VG_LCWARC_TO: {
1092      data_at(&pd->coords, pd->path, 0, 5, data);
1093      map_if_relative(pd->ox, pd->oy, relative, &data[3], &data[4]);
1094      pd->ox = data[3];
1095      pd->oy = data[4];
1096      pd->px = data[3];
1097      pd->py = data[4];
1098      *num_coords = 5;
1099      return command | VG_ABSOLUTE;
1100   }
1101      break;
1102   default:
1103      abort();
1104      assert(!"Unknown segment!");
1105   }
1106}
1107
1108static void linearly_interpolate(VGfloat *result,
1109                                 const VGfloat *start,
1110                                 const VGfloat *end,
1111                                 VGfloat amount,
1112                                 VGint number)
1113{
1114   VGint i;
1115   for (i = 0; i < number; ++i) {
1116      result[i] = start[i] + (end[i] - start[i]) * amount;
1117   }
1118}
1119
1120VGboolean path_interpolate(struct path *dst,
1121                           struct path *start, struct path *end,
1122                           VGfloat amount)
1123{
1124   /* temporary path that we can discard if it will turn
1125    * out that start is not compatible with end */
1126   struct path *res_path = path_create(dst->datatype,
1127                                       1.0, 0.0,
1128                                       0, 0, dst->caps);
1129   VGint i;
1130   VGfloat start_coords[8];
1131   VGfloat end_coords[8];
1132   VGfloat results[8];
1133   VGubyte common_data[sizeof(VGfloat)*8];
1134   struct path_iter_data start_iter, end_iter;
1135
1136   memset(&start_iter, 0, sizeof(struct path_iter_data));
1137   memset(&end_iter, 0, sizeof(struct path_iter_data));
1138
1139   start_iter.path = start;
1140   start_iter.coords = start->control_points->data;
1141   end_iter.path = end;
1142   end_iter.coords = end->control_points->data;
1143
1144   for (i = 0; i < start->num_segments; ++i) {
1145      VGubyte segment;
1146      VGubyte ssegment, esegment;
1147      VGint snum_coords, enum_coords;
1148      start_iter.segment = ((VGubyte*)(start->segments->data))[i];
1149      end_iter.segment = ((VGubyte*)(end->segments->data))[i];
1150
1151      ssegment = normalize_coords(&start_iter, &snum_coords,
1152                                  start_coords);
1153      esegment = normalize_coords(&end_iter, &enum_coords,
1154                                  end_coords);
1155
1156      if (is_segment_arc(ssegment)) {
1157         if (!is_segment_arc(esegment)) {
1158            path_destroy(res_path);
1159            return VG_FALSE;
1160         }
1161         if (amount > 0.5)
1162            segment = esegment;
1163         else
1164            segment = ssegment;
1165      } else if (is_segment_arc(esegment)) {
1166         path_destroy(res_path);
1167         return VG_FALSE;
1168      }
1169      else if (ssegment != esegment) {
1170         path_destroy(res_path);
1171         return VG_FALSE;
1172      }
1173      else
1174         segment = ssegment;
1175
1176      linearly_interpolate(results, start_coords, end_coords,
1177                           amount, snum_coords);
1178      vg_float_to_datatype(dst->datatype, common_data, results, snum_coords);
1179      path_append_data(res_path, 1, &segment, common_data);
1180   }
1181
1182   path_append_path(dst, res_path);
1183   path_destroy(res_path);
1184
1185   dst->dirty = VG_TRUE;
1186   dst->dirty_stroke = VG_TRUE;
1187
1188   return VG_TRUE;
1189}
1190
1191void path_clear(struct path *p, VGbitfield capabilities)
1192{
1193   path_set_capabilities(p, capabilities);
1194   array_destroy(p->segments);
1195   array_destroy(p->control_points);
1196   p->segments = array_create(size_for_datatype(VG_PATH_DATATYPE_S_8));
1197   p->control_points = array_create(size_for_datatype(p->datatype));
1198   p->num_segments = 0;
1199   p->dirty = VG_TRUE;
1200   p->dirty_stroke = VG_TRUE;
1201}
1202
1203struct path * path_create_stroke(struct path *p,
1204                                 struct matrix *matrix)
1205{
1206   VGint i;
1207   VGfloat sx, sy, px, py, ox, oy;
1208   VGfloat x0, y0, x1, y1, x2, y2, x3, y3;
1209   VGfloat data[8];
1210   void *coords = (VGfloat *)p->control_points->data;
1211   int dashed = (p->base.ctx->state.vg.stroke.dash_pattern_num ? 1 : 0);
1212   struct dash_stroker stroker;
1213   struct vg_state *vg_state = &p->base.ctx->state.vg;
1214
1215   if (p->stroked.path)
1216   {
1217      /* ### compare the dash patterns to see if we can cache them.
1218       *     for now we simply always bail out if the path is dashed.
1219       */
1220      if (memcmp( &p->stroked.matrix,
1221                  matrix,
1222                  sizeof *matrix ) == 0 &&
1223          !dashed && !p->dirty_stroke &&
1224          floatsEqual(p->stroked.stroke_width, vg_state->stroke.line_width.f) &&
1225          floatsEqual(p->stroked.miter_limit, vg_state->stroke.miter_limit.f) &&
1226          p->stroked.cap_style == vg_state->stroke.cap_style &&
1227          p->stroked.join_style == vg_state->stroke.join_style)
1228      {
1229         return p->stroked.path;
1230      }
1231      else {
1232         path_destroy( p->stroked.path );
1233         p->stroked.path = NULL;
1234      }
1235   }
1236
1237
1238   sx = sy = px = py = ox = oy = 0.f;
1239
1240   if (dashed)
1241      dash_stroker_init((struct stroker *)&stroker, vg_state);
1242   else
1243      stroker_init((struct stroker *)&stroker, vg_state);
1244
1245   stroker_begin((struct stroker *)&stroker);
1246
1247   for (i = 0; i < p->num_segments; ++i) {
1248      VGubyte segment = ((VGubyte*)(p->segments->data))[i];
1249      VGint command = SEGMENT_COMMAND(segment);
1250      VGboolean relative = SEGMENT_ABS_REL(segment);
1251
1252      switch(command) {
1253      case VG_CLOSE_PATH: {
1254            VGfloat x0 = sx;
1255            VGfloat y0 = sy;
1256            matrix_map_point(matrix, x0, y0, &x0, &y0);
1257            stroker_line_to((struct stroker *)&stroker, x0, y0);
1258      }
1259         break;
1260      case VG_MOVE_TO:
1261         data_at(&coords, p, 0, 2, data);
1262         x0 = data[0];
1263         y0 = data[1];
1264         map_if_relative(ox, oy, relative, &x0, &y0);
1265         sx = x0;
1266         sy = y0;
1267         ox = x0;
1268         oy = y0;
1269         px = x0;
1270         py = y0;
1271         matrix_map_point(matrix, x0, y0, &x0, &y0);
1272         stroker_move_to((struct stroker *)&stroker, x0, y0);
1273         break;
1274      case VG_LINE_TO:
1275         data_at(&coords, p, 0, 2, data);
1276         x0 = data[0];
1277         y0 = data[1];
1278         map_if_relative(ox, oy, relative, &x0, &y0);
1279         ox = x0;
1280         oy = y0;
1281         px = x0;
1282         py = y0;
1283         matrix_map_point(matrix, x0, y0, &x0, &y0);
1284         stroker_line_to((struct stroker *)&stroker, x0, y0);
1285         break;
1286      case VG_HLINE_TO:
1287         data_at(&coords, p, 0, 1, data);
1288         x0 = data[0];
1289         y0 = oy;
1290         map_if_relative(ox, oy, relative, &x0, 0);
1291         ox = x0;
1292         px = x0;
1293         py = y0;
1294         matrix_map_point(matrix, x0, y0, &x0, &y0);
1295         stroker_line_to((struct stroker *)&stroker, x0, y0);
1296         break;
1297      case VG_VLINE_TO:
1298         data_at(&coords, p, 0, 1, data);
1299         x0 = ox;
1300         y0 = data[0];
1301         map_if_relative(ox, oy, relative, 0, &y0);
1302         oy = y0;
1303         px = x0;
1304         py = y0;
1305         matrix_map_point(matrix, x0, y0, &x0, &y0);
1306         stroker_line_to((struct stroker *)&stroker, x0, y0);
1307         break;
1308      case VG_CUBIC_TO: {
1309         data_at(&coords, p, 0, 6, data);
1310         x0 = ox;
1311         y0 = oy;
1312         x1 = data[0];
1313         y1 = data[1];
1314         x2 = data[2];
1315         y2 = data[3];
1316         x3 = data[4];
1317         y3 = data[5];
1318         map_if_relative(ox, oy, relative, &x1, &y1);
1319         map_if_relative(ox, oy, relative, &x2, &y2);
1320         map_if_relative(ox, oy, relative, &x3, &y3);
1321         if (floatsEqual(x1, ox) && floatsEqual(y1, oy) &&
1322             floatsEqual(x1, x2) && floatsEqual(y1, y2) &&
1323             floatsEqual(x2, x3) && floatsEqual(y2, y3)) {
1324            /*ignore the empty segment */
1325            continue;
1326         } else if (floatsEqual(x3, ox) && floatsEqual(y3, oy)) {
1327            /* if dup vertex, emit a line */
1328            ox = x3;
1329            oy = y3;
1330            matrix_map_point(matrix, x3, y3, &x3, &y3);
1331            stroker_line_to((struct stroker *)&stroker, x3, y3);
1332            continue;
1333         }
1334         ox = x3;
1335         oy = y3;
1336         px = x2;
1337         py = y2;
1338         assert(matrix_is_affine(matrix));
1339         matrix_map_point(matrix, x0, y0, &x0, &y0);
1340         matrix_map_point(matrix, x1, y1, &x1, &y1);
1341         matrix_map_point(matrix, x2, y2, &x2, &y2);
1342         matrix_map_point(matrix, x3, y3, &x3, &y3);
1343         stroker_curve_to((struct stroker *)&stroker, x1, y1, x2, y2, x3, y3);
1344      }
1345         break;
1346      case VG_QUAD_TO: {
1347         data_at(&coords, p, 0, 4, data);
1348         x0 = ox;
1349         y0 = oy;
1350         x1 = data[0];
1351         y1 = data[1];
1352         x3 = data[2];
1353         y3 = data[3];
1354         map_if_relative(ox, oy, relative, &x1, &y1);
1355         map_if_relative(ox, oy, relative, &x3, &y3);
1356         px = x1;
1357         py = y1;
1358         { /* form a cubic out of it */
1359            x2 = (x3 + 2*x1) / 3.f;
1360            y2 = (y3 + 2*y1) / 3.f;
1361            x1 = (x0 + 2*x1) / 3.f;
1362            y1 = (y0 + 2*y1) / 3.f;
1363         }
1364         if (floatsEqual(x1, ox) && floatsEqual(y1, oy) &&
1365             floatsEqual(x1, x2) && floatsEqual(y1, y2) &&
1366             floatsEqual(x2, x3) && floatsEqual(y2, y3)) {
1367            /*ignore the empty segment */
1368            continue;
1369         } else if (floatsEqual(x3, ox) && floatsEqual(y3, oy)) {
1370            /* if dup vertex, emit a line */
1371            ox = x3;
1372            oy = y3;
1373            matrix_map_point(matrix, x3, y3, &x3, &y3);
1374            stroker_line_to((struct stroker *)&stroker, x3, y3);
1375            continue;
1376         }
1377         ox = x3;
1378         oy = y3;
1379         assert(matrix_is_affine(matrix));
1380         matrix_map_point(matrix, x0, y0, &x0, &y0);
1381         matrix_map_point(matrix, x1, y1, &x1, &y1);
1382         matrix_map_point(matrix, x2, y2, &x2, &y2);
1383         matrix_map_point(matrix, x3, y3, &x3, &y3);
1384         stroker_curve_to((struct stroker *)&stroker, x1, y1, x2, y2, x3, y3);
1385      }
1386         break;
1387      case VG_SQUAD_TO: {
1388         data_at(&coords, p, 0, 2, data);
1389         x0 = ox;
1390         y0 = oy;
1391         x1 = 2*ox-px;
1392         y1 = 2*oy-py;
1393         x3 = data[0];
1394         y3 = data[1];
1395         map_if_relative(ox, oy, relative, &x3, &y3);
1396         px = x1;
1397         py = y1;
1398         { /* form a cubic out of it */
1399            x2 = (x3 + 2*x1) / 3.f;
1400            y2 = (y3 + 2*y1) / 3.f;
1401            x1 = (x0 + 2*x1) / 3.f;
1402            y1 = (y0 + 2*y1) / 3.f;
1403         }
1404         if (floatsEqual(x1, ox) && floatsEqual(y1, oy) &&
1405             floatsEqual(x1, x2) && floatsEqual(y1, y2) &&
1406             floatsEqual(x2, x3) && floatsEqual(y2, y3)) {
1407            /*ignore the empty segment */
1408            continue;
1409         } else if (floatsEqual(x3, ox) && floatsEqual(y3, oy)) {
1410            /* if dup vertex, emit a line */
1411            ox = x3;
1412            oy = y3;
1413            matrix_map_point(matrix, x3, y3, &x3, &y3);
1414            stroker_line_to((struct stroker *)&stroker, x3, y3);
1415            continue;
1416         }
1417         ox = x3;
1418         oy = y3;
1419         assert(matrix_is_affine(matrix));
1420         matrix_map_point(matrix, x0, y0, &x0, &y0);
1421         matrix_map_point(matrix, x1, y1, &x1, &y1);
1422         matrix_map_point(matrix, x2, y2, &x2, &y2);
1423         matrix_map_point(matrix, x3, y3, &x3, &y3);
1424         stroker_curve_to((struct stroker *)&stroker, x1, y1, x2, y2, x3, y3);
1425      }
1426         break;
1427      case VG_SCUBIC_TO: {
1428         data_at(&coords, p, 0, 4, data);
1429         x0 = ox;
1430         y0 = oy;
1431         x1 = 2*ox-px;
1432         y1 = 2*oy-py;
1433         x2 = data[0];
1434         y2 = data[1];
1435         x3 = data[2];
1436         y3 = data[3];
1437         map_if_relative(ox, oy, relative, &x2, &y2);
1438         map_if_relative(ox, oy, relative, &x3, &y3);
1439         if (floatsEqual(x1, ox) && floatsEqual(y1, oy) &&
1440             floatsEqual(x1, x2) && floatsEqual(y1, y2) &&
1441             floatsEqual(x2, x3) && floatsEqual(y2, y3)) {
1442            /*ignore the empty segment */
1443            continue;
1444         } else if (floatsEqual(x3, ox) && floatsEqual(y3, oy)) {
1445            /* if dup vertex, emit a line */
1446            ox = x3;
1447            oy = y3;
1448            matrix_map_point(matrix, x3, y3, &x3, &y3);
1449            stroker_line_to((struct stroker *)&stroker, x3, y3);
1450            continue;
1451         }
1452         ox = x3;
1453         oy = y3;
1454         px = x2;
1455         py = y2;
1456         assert(matrix_is_affine(matrix));
1457         matrix_map_point(matrix, x0, y0, &x0, &y0);
1458         matrix_map_point(matrix, x1, y1, &x1, &y1);
1459         matrix_map_point(matrix, x2, y2, &x2, &y2);
1460         matrix_map_point(matrix, x3, y3, &x3, &y3);
1461         stroker_curve_to((struct stroker *)&stroker, x1, y1, x2, y2, x3, y3);
1462      }
1463         break;
1464      case VG_SCCWARC_TO:
1465      case VG_SCWARC_TO:
1466      case VG_LCCWARC_TO:
1467      case VG_LCWARC_TO: {
1468         VGfloat rh, rv, rot;
1469         struct arc arc;
1470
1471         data_at(&coords, p, 0, 5, data);
1472         x0  = ox;
1473         y0  = oy;
1474         rh  = data[0];
1475         rv  = data[1];
1476         rot = data[2];
1477         x1  = data[3];
1478         y1  = data[4];
1479         map_if_relative(ox, oy, relative, &x1, &y1);
1480         if (floatsEqual(x1, ox) && floatsEqual(y1, oy)) {
1481            /* if dup vertex, emit a line */
1482            ox = x1;
1483            oy = y1;
1484            matrix_map_point(matrix, x1, y1, &x1, &y1);
1485            stroker_line_to((struct stroker *)&stroker, x1, y1);
1486            continue;
1487         }
1488         arc_init(&arc, command, x0, y0, x1, y1,
1489                  rh, rv, rot);
1490         arc_stroke_cb(&arc, (struct stroker *)&stroker,
1491                       matrix);
1492         ox = x1;
1493         oy = y1;
1494         px = x1;
1495         py = y1;
1496      }
1497         break;
1498      default:
1499         abort();
1500         assert(!"Unknown segment!");
1501      }
1502   }
1503
1504   stroker_end((struct stroker *)&stroker);
1505
1506   if (dashed)
1507      dash_stroker_cleanup((struct dash_stroker *)&stroker);
1508   else
1509      stroker_cleanup((struct stroker *)&stroker);
1510
1511   p->stroked.path = stroker.base.path;
1512   p->stroked.matrix = *matrix;
1513   p->dirty_stroke = VG_FALSE;
1514   p->stroked.stroke_width = vg_state->stroke.line_width.f;
1515   p->stroked.miter_limit = vg_state->stroke.miter_limit.f;
1516   p->stroked.cap_style = vg_state->stroke.cap_style;
1517   p->stroked.join_style = vg_state->stroke.join_style;
1518
1519   return stroker.base.path;
1520}
1521
1522void path_render(struct path *p, VGbitfield paintModes)
1523{
1524   struct vg_context *ctx = vg_current_context();
1525   struct matrix *mat = &ctx->state.vg.path_user_to_surface_matrix;
1526
1527   vg_validate_state(ctx);
1528
1529   shader_set_drawing_image(ctx->shader, VG_FALSE);
1530   shader_set_image(ctx->shader, 0);
1531#if 0
1532   fprintf(stderr, "Matrix(11=%f 12=%f 13=%f 21=%f 22=%f 23=%f 31=%f 32=%f 33=%f)\n",
1533           mat->m[0], mat->m[1], mat->m[2],
1534           mat->m[3], mat->m[4], mat->m[5],
1535           mat->m[6], mat->m[7], mat->m[8]);
1536#endif
1537   if (paintModes & VG_FILL_PATH) {
1538      /* First the fill */
1539      shader_set_paint(ctx->shader, ctx->state.vg.fill_paint);
1540      shader_bind(ctx->shader);
1541      path_fill(p, mat);
1542   }
1543
1544   if (paintModes & VG_STROKE_PATH){
1545      /* 8.7.5: "line width less than or equal to 0 prevents stroking from
1546       *  taking place."*/
1547      if (ctx->state.vg.stroke.line_width.f <= 0)
1548         return;
1549      shader_set_paint(ctx->shader, ctx->state.vg.stroke_paint);
1550      shader_bind(ctx->shader);
1551      path_stroke(p);
1552   }
1553}
1554
1555void path_fill(struct path *p, struct matrix *mat)
1556{
1557   struct vg_context *ctx = vg_current_context();
1558   {
1559      struct polygon_array *polygon_array = path_get_fill_polygons(p, mat);
1560      struct array *polys = polygon_array->array;
1561
1562      if (!polygon_array || !polys || !polys->num_elements) {
1563         return;
1564      }
1565      polygon_array_fill(polygon_array, ctx);
1566   }
1567}
1568
1569void path_stroke(struct path *p)
1570{
1571   struct vg_context *ctx = vg_current_context();
1572   struct matrix *mat = &ctx->state.vg.path_user_to_surface_matrix;
1573   VGFillRule old_fill = ctx->state.vg.fill_rule;
1574   struct matrix identity;
1575   struct path *stroke;
1576
1577   matrix_load_identity(&identity);
1578   stroke = path_create_stroke(p, &identity);
1579   if (stroke && !path_is_empty(stroke)) {
1580      ctx->state.vg.fill_rule = VG_NON_ZERO;
1581
1582      path_fill(stroke, mat);
1583
1584      ctx->state.vg.fill_rule = old_fill;
1585   }
1586}
1587
1588void path_move_to(struct path *p, float x, float y)
1589{
1590   VGubyte segment = VG_MOVE_TO_ABS;
1591   VGubyte common_data[sizeof(VGfloat) * 2];
1592   VGfloat data[2] = {x, y};
1593
1594   vg_float_to_datatype(p->datatype, common_data, data, 2);
1595   path_append_data(p, 1, &segment, common_data);
1596}
1597
1598void path_line_to(struct path *p, float x, float y)
1599{
1600   VGubyte segment = VG_LINE_TO_ABS;
1601   VGubyte common_data[sizeof(VGfloat) * 2];
1602   VGfloat data[2] = {x, y};
1603
1604   vg_float_to_datatype(p->datatype, common_data, data, 2);
1605
1606   path_append_data(p, 1, &segment, common_data);
1607}
1608
1609void path_cubic_to(struct path *p, float px1, float py1,
1610                   float px2, float py2,
1611                   float x, float y)
1612{
1613   VGubyte segment = VG_CUBIC_TO_ABS;
1614   VGubyte common_data[sizeof(VGfloat) * 6];
1615   VGfloat data[6];
1616
1617   data[0] = px1; data[1] = py1;
1618   data[2] = px2; data[3] = py2;
1619   data[4] = x;   data[5] = y;
1620
1621   vg_float_to_datatype(p->datatype, common_data, data, 6);
1622
1623   path_append_data(p, 1, &segment, common_data);
1624}
1625
1626static INLINE void line_bounds(VGfloat *line /*x1,y1,x2,y2*/,
1627                               VGfloat *bounds)
1628{
1629   bounds[0] = MIN2(line[0], line[2]);
1630   bounds[1] = MIN2(line[1], line[3]);
1631   bounds[2] = MAX2(line[0], line[2]) - bounds[0];
1632   bounds[3] = MAX2(line[1], line[3]) - bounds[1];
1633}
1634
1635static INLINE void unite_bounds(VGfloat *bounds,
1636                                VGfloat *el)
1637{
1638   VGfloat cx1, cy1, cx2, cy2;
1639   VGfloat nx1, ny1, nx2, ny2;
1640
1641   cx1 = bounds[0];
1642   cy1 = bounds[1];
1643   cx2 = bounds[0] + bounds[2];
1644   cy2 = bounds[1] + bounds[3];
1645
1646   nx1 = el[0];
1647   ny1 = el[1];
1648   nx2 = el[0] + el[2];
1649   ny2 = el[1] + el[3];
1650
1651   bounds[0] = MIN2(cx1, nx1);
1652   bounds[1] = MIN2(cy1, ny1);
1653   bounds[2] = MAX2(cx2, nx2) - bounds[0];
1654   bounds[3] = MAX2(cy2, ny2) - bounds[1];
1655}
1656
1657static INLINE void set_bounds(VGfloat *bounds,
1658                              VGfloat *element_bounds,
1659                              VGboolean *initialized)
1660{
1661   if (!(*initialized)) {
1662      memcpy(bounds, element_bounds, 4 * sizeof(VGfloat));
1663      *initialized = VG_TRUE;
1664   } else
1665      unite_bounds(bounds, element_bounds);
1666}
1667
1668void path_bounding_rect(struct path *p, float *x, float *y,
1669                        float *w, float *h)
1670{
1671   VGint i;
1672   VGfloat coords[8];
1673   struct path_iter_data iter;
1674   VGint num_coords;
1675   VGfloat bounds[4];
1676   VGfloat element_bounds[4];
1677   VGfloat ox, oy;
1678   VGboolean bounds_inited = VG_FALSE;
1679
1680   memset(&iter, 0, sizeof(struct path_iter_data));
1681   memset(&bounds, 0, sizeof(bounds));
1682
1683   if (!p->num_segments) {
1684      bounds[2] = -1;
1685      bounds[3] = -1;
1686   }
1687
1688
1689   iter.path = p;
1690   iter.coords = p->control_points->data;
1691
1692   for (i = 0; i < p->num_segments; ++i) {
1693      VGubyte segment;
1694      iter.segment = ((VGubyte*)(p->segments->data))[i];
1695
1696      ox = iter.ox;
1697      oy = iter.oy;
1698
1699      segment = normalize_coords(&iter, &num_coords, coords);
1700
1701      switch(segment) {
1702      case VG_CLOSE_PATH:
1703      case VG_MOVE_TO_ABS:
1704         break;
1705      case VG_LINE_TO_ABS: {
1706         VGfloat line[4] = {ox, oy, coords[0], coords[1]};
1707         line_bounds(line, element_bounds);
1708         set_bounds(bounds, element_bounds, &bounds_inited);
1709      }
1710         break;
1711      case VG_CUBIC_TO_ABS: {
1712         struct bezier bezier;
1713         bezier_init(&bezier, ox, oy,
1714                     coords[0], coords[1],
1715                     coords[2], coords[3],
1716                     coords[4], coords[5]);
1717         bezier_exact_bounds(&bezier, element_bounds);
1718         set_bounds(bounds, element_bounds, &bounds_inited);
1719      }
1720         break;
1721      case VG_SCCWARC_TO:
1722      case VG_SCWARC_TO:
1723      case VG_LCCWARC_TO:
1724      case VG_LCWARC_TO: {
1725         struct arc arc;
1726         struct matrix identity;
1727         struct path *path = path_create(VG_PATH_DATATYPE_F,
1728                                         1, 0, 0, 0, VG_PATH_CAPABILITY_ALL);
1729
1730         matrix_load_identity(&identity);
1731         arc_init(&arc, segment,
1732                  ox, oy, coords[3], coords[4],
1733                  coords[0], coords[1], coords[2]);
1734
1735         arc_to_path(&arc, path, &identity);
1736
1737         path_bounding_rect(path, element_bounds + 0, element_bounds + 1,
1738                            element_bounds + 2, element_bounds + 3);
1739         set_bounds(bounds, element_bounds, &bounds_inited);
1740      }
1741         break;
1742      default:
1743         assert(0);
1744      }
1745   }
1746
1747   *x = bounds[0];
1748   *y = bounds[1];
1749   *w = bounds[2];
1750   *h = bounds[3];
1751}
1752
1753float path_length(struct path *p, int start_segment, int num_segments)
1754{
1755   VGint i;
1756   VGfloat coords[8];
1757   struct path_iter_data iter;
1758   VGint num_coords;
1759   VGfloat length = 0;
1760   VGfloat ox, oy;
1761   VGboolean in_range = VG_FALSE;
1762
1763   memset(&iter, 0, sizeof(struct path_iter_data));
1764
1765   iter.path = p;
1766   iter.coords = p->control_points->data;
1767
1768   for (i = 0; i < (start_segment + num_segments); ++i) {
1769      VGubyte segment;
1770
1771      iter.segment = ((VGubyte*)(p->segments->data))[i];
1772
1773      ox = iter.ox;
1774      oy = iter.oy;
1775
1776      segment = normalize_coords(&iter, &num_coords, coords);
1777
1778      in_range = (i >= start_segment) && i <= (start_segment + num_segments);
1779      if (!in_range)
1780         continue;
1781
1782      switch(segment) {
1783      case VG_MOVE_TO_ABS:
1784         break;
1785      case VG_CLOSE_PATH: {
1786         VGfloat line[4] = {ox, oy, iter.sx, iter.sy};
1787         length += line_lengthv(line);
1788      }
1789         break;
1790      case VG_LINE_TO_ABS: {
1791         VGfloat line[4] = {ox, oy, coords[0], coords[1]};
1792         length += line_lengthv(line);
1793      }
1794         break;
1795      case VG_CUBIC_TO_ABS: {
1796         struct bezier bezier;
1797         bezier_init(&bezier, ox, oy,
1798                     coords[0], coords[1],
1799                     coords[2], coords[3],
1800                     coords[4], coords[5]);
1801         length += bezier_length(&bezier, BEZIER_DEFAULT_ERROR);
1802      }
1803         break;
1804      case VG_SCCWARC_TO:
1805      case VG_SCWARC_TO:
1806      case VG_LCCWARC_TO:
1807      case VG_LCWARC_TO: {
1808         struct arc arc;
1809         struct matrix identity;
1810         struct path *path = path_create(VG_PATH_DATATYPE_F,
1811                                         1, 0, 0, 0, VG_PATH_CAPABILITY_ALL);
1812
1813         matrix_load_identity(&identity);
1814         arc_init(&arc, segment,
1815                  ox, oy, coords[3], coords[4],
1816                  coords[0], coords[1], coords[2]);
1817
1818         arc_to_path(&arc, path, &identity);
1819
1820         length += path_length(path, 0, path_num_segments(path));
1821      }
1822         break;
1823      default:
1824         assert(0);
1825      }
1826   }
1827
1828   return length;
1829}
1830
1831static INLINE VGboolean point_on_current_segment(VGfloat distance,
1832                                                 VGfloat length,
1833                                                 VGfloat segment_length)
1834{
1835   return
1836      (((floatIsZero(distance) || distance < 0) && floatIsZero(length)) ||
1837       ((distance > length || floatsEqual(distance, length)) &&
1838        (floatsEqual(distance, length + segment_length) ||
1839         distance < (length + segment_length))));
1840}
1841
1842static VGboolean path_point_segment(struct path_iter_data iter,
1843                                    struct path_iter_data prev_iter,
1844                                    VGfloat coords[8],
1845                                    VGfloat distance,
1846                                    VGfloat length, VGfloat *current_length,
1847                                    VGfloat *point, VGfloat *normal)
1848{
1849   switch (iter.segment) {
1850   case VG_MOVE_TO_ABS:
1851      break;
1852   case VG_CLOSE_PATH: {
1853      VGfloat line[4] = {prev_iter.ox, prev_iter.oy, iter.sx, iter.sy};
1854      VGboolean on_current_segment = VG_FALSE;
1855      *current_length = line_lengthv(line);
1856      on_current_segment = point_on_current_segment(distance,
1857                                                    length,
1858                                                    *current_length);
1859      if (on_current_segment) {
1860         VGfloat at = (distance - length) / line_lengthv(line);
1861         line_normal_vector(line, normal);
1862         line_point_at(line, at, point);
1863         return VG_TRUE;
1864      }
1865   }
1866      break;
1867   case VG_LINE_TO_ABS: {
1868      VGfloat line[4] = {prev_iter.ox, prev_iter.oy, coords[0], coords[1]};
1869      VGboolean on_current_segment = VG_FALSE;
1870      *current_length = line_lengthv(line);
1871      on_current_segment = point_on_current_segment(distance,
1872                                                    length,
1873                                                    *current_length);
1874      if (on_current_segment) {
1875         VGfloat at = (distance - length) / line_lengthv(line);
1876         line_normal_vector(line, normal);
1877         line_point_at(line, at, point);
1878         return VG_TRUE;
1879      }
1880   }
1881      break;
1882   case VG_CUBIC_TO_ABS: {
1883      struct bezier bezier;
1884      bezier_init(&bezier, prev_iter.ox, prev_iter.oy,
1885                  coords[0], coords[1],
1886                  coords[2], coords[3],
1887                  coords[4], coords[5]);
1888      *current_length = bezier_length(&bezier, BEZIER_DEFAULT_ERROR);
1889      if (point_on_current_segment(distance, length, *current_length)) {
1890         bezier_point_at_length(&bezier, distance - length,
1891                                point, normal);
1892         return VG_TRUE;
1893      }
1894   }
1895      break;
1896   case VG_SCCWARC_TO:
1897   case VG_SCWARC_TO:
1898   case VG_LCCWARC_TO:
1899   case VG_LCWARC_TO: {
1900      struct arc arc;
1901      struct matrix identity;
1902      struct path *path = path_create(VG_PATH_DATATYPE_F,
1903                                      1, 0, 0, 0, VG_PATH_CAPABILITY_ALL);
1904
1905      matrix_load_identity(&identity);
1906      arc_init(&arc, iter.segment,
1907               prev_iter.ox, prev_iter.oy, coords[3], coords[4],
1908               coords[0], coords[1], coords[2]);
1909
1910      arc_to_path(&arc, path, &identity);
1911
1912      *current_length = path_length(path, 0, path_num_segments(path));
1913      if (point_on_current_segment(distance, length, *current_length)) {
1914         path_point(path, 0, path_num_segments(path),
1915                    distance - length, point, normal);
1916         return VG_TRUE;
1917      }
1918   }
1919      break;
1920   default:
1921      assert(0);
1922   }
1923   return VG_FALSE;
1924}
1925
1926void path_point(struct path *p, VGint start_segment, VGint num_segments,
1927                VGfloat distance, VGfloat *point, VGfloat *normal)
1928{
1929   VGint i;
1930   VGfloat coords[8];
1931   struct path_iter_data iter, prev_iter;
1932   VGint num_coords;
1933   VGfloat length = 0;
1934   VGfloat current_length = 0;
1935
1936   memset(&iter, 0, sizeof(struct path_iter_data));
1937   memset(&prev_iter, 0, sizeof(struct path_iter_data));
1938
1939   point[0] = 0;
1940   point[1] = 0;
1941
1942   normal[0] = 0;
1943   normal[1] = -1;
1944
1945   iter.path = p;
1946   iter.coords = p->control_points->data;
1947   if (distance < 0)
1948      distance = 0;
1949
1950   for (i = 0; i < (start_segment + num_segments); ++i) {
1951      VGboolean outside_range = (i < start_segment ||
1952                                 i >= (start_segment + num_segments));
1953
1954      prev_iter = iter;
1955
1956      iter.segment = ((VGubyte*)(p->segments->data))[i];
1957      iter.segment = normalize_coords(&iter, &num_coords, coords);
1958
1959      if (outside_range)
1960         continue;
1961
1962      if (path_point_segment(iter, prev_iter, coords,
1963                             distance, length, &current_length,
1964                             point, normal))
1965         return;
1966
1967      length += current_length;
1968   }
1969
1970   /*
1971    *OpenVG 1.0 - 8.6.11 vgPointAlongPath
1972    *
1973    * If distance is greater than or equal to the path length
1974    *(i.e., the value returned by vgPathLength when called with the same
1975    *startSegment and numSegments parameters), the visual ending point of
1976    *the path is used.
1977    */
1978   {
1979      switch (iter.segment) {
1980      case VG_MOVE_TO_ABS:
1981         break;
1982      case VG_CLOSE_PATH: {
1983         VGfloat line[4] = {prev_iter.ox, prev_iter.oy, iter.sx, iter.sy};
1984         line_normal_vector(line, normal);
1985         line_point_at(line, 1.f, point);
1986      }
1987         break;
1988      case VG_LINE_TO_ABS: {
1989         VGfloat line[4] = {prev_iter.ox, prev_iter.oy, coords[0], coords[1]};
1990         line_normal_vector(line, normal);
1991         line_point_at(line, 1.f, point);
1992      }
1993         break;
1994      case VG_CUBIC_TO_ABS: {
1995         struct bezier bezier;
1996         bezier_init(&bezier, prev_iter.ox, prev_iter.oy,
1997                     coords[0], coords[1],
1998                     coords[2], coords[3],
1999                     coords[4], coords[5]);
2000         bezier_point_at_t(&bezier, 1.f, point, normal);
2001      }
2002         break;
2003      case VG_SCCWARC_TO:
2004      case VG_SCWARC_TO:
2005      case VG_LCCWARC_TO:
2006      case VG_LCWARC_TO: {
2007         struct arc arc;
2008         struct matrix identity;
2009         struct path *path = path_create(VG_PATH_DATATYPE_F,
2010                                         1, 0, 0, 0, VG_PATH_CAPABILITY_ALL);
2011
2012         matrix_load_identity(&identity);
2013         arc_init(&arc, iter.segment,
2014                  prev_iter.ox, prev_iter.oy, coords[3], coords[4],
2015                  coords[0], coords[1], coords[2]);
2016
2017         arc_to_path(&arc, path, &identity);
2018
2019         path_point(path, 0, path_num_segments(path),
2020                    /* to make sure we're bigger than len * 2 it */
2021                    2 * path_length(path, 0, path_num_segments(path)),
2022                    point, normal);
2023      }
2024         break;
2025      default:
2026         assert(0);
2027      }
2028   }
2029}
2030
2031VGboolean path_is_empty(struct path *p)
2032{
2033   return p->segments->num_elements == 0;
2034}
2035