stroker.c revision e55cf4854d594eae9ac3f6abd24f4e616eea894f 
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 "stroker.h"
28
29#include "path.h"
30#include "vg_state.h"
31#include "util_array.h"
32#include "arc.h"
33#include "bezier.h"
34#include "matrix.h"
35#include "path_utils.h"
36#include "polygon.h"
37
38#include "util/u_math.h"
39
40#ifndef M_2PI
41#define M_2PI 6.28318530717958647692528676655900576
42#endif
43
44#define STROKE_SEGMENTS 0
45#define STROKE_DEBUG 0
46#define DEBUG_EMITS 0
47
48static const VGfloat curve_threshold = 0.25f;
49
50static const VGfloat zero_coords[] = {0.f, 0.f};
51
52enum intersection_type {
53   NoIntersections,
54   BoundedIntersection,
55   UnboundedIntersection,
56};
57
58enum line_join_mode {
59   FlatJoin,
60   SquareJoin,
61   MiterJoin,
62   RoundJoin,
63   RoundCap
64};
65
66struct stroke_iterator {
67   void (*next)(struct stroke_iterator *);
68   VGboolean (*has_next)(struct stroke_iterator *);
69
70   VGPathCommand (*current_command)(struct stroke_iterator *it);
71   void (*current_coords)(struct stroke_iterator *it, VGfloat *coords);
72
73   VGint position;
74   VGint coord_position;
75
76   const VGubyte *cmds;
77   const VGfloat *coords;
78   VGint num_commands;
79   VGint num_coords;
80
81   struct polygon *curve_poly;
82   VGint curve_index;
83};
84
85static VGPathCommand stroke_itr_command(struct stroke_iterator *itr)
86{
87   return itr->current_command(itr);
88}
89
90static void stroke_itr_coords(struct stroke_iterator *itr, VGfloat *coords)
91{
92   itr->current_coords(itr, coords);
93}
94
95static void stroke_fw_itr_coords(struct stroke_iterator *itr, VGfloat *coords)
96{
97   if (itr->position >= itr->num_commands)
98      return;
99   switch (stroke_itr_command(itr)) {
100   case VG_MOVE_TO_ABS:
101      coords[0] = itr->coords[itr->coord_position];
102      coords[1] = itr->coords[itr->coord_position + 1];
103      break;
104   case VG_LINE_TO_ABS:
105      coords[0] = itr->coords[itr->coord_position];
106      coords[1] = itr->coords[itr->coord_position + 1];
107      break;
108   case VG_CUBIC_TO_ABS:
109      coords[0] = itr->coords[itr->coord_position];
110      coords[1] = itr->coords[itr->coord_position + 1];
111      coords[2] = itr->coords[itr->coord_position + 2];
112      coords[3] = itr->coords[itr->coord_position + 3];
113      coords[4] = itr->coords[itr->coord_position + 4];
114      coords[5] = itr->coords[itr->coord_position + 5];
115      break;
116   default:
117      debug_assert(!"invalid command!\n");
118   }
119}
120
121
122static void stroke_bw_itr_coords(struct stroke_iterator *itr, VGfloat *coords)
123{
124   if (itr->position >= itr->num_commands)
125      return;
126   switch (stroke_itr_command(itr)) {
127   case VG_MOVE_TO_ABS:
128      coords[0] = itr->coords[itr->coord_position];
129      coords[1] = itr->coords[itr->coord_position + 1];
130      break;
131   case VG_LINE_TO_ABS:
132      coords[0] = itr->coords[itr->coord_position];
133      coords[1] = itr->coords[itr->coord_position + 1];
134      break;
135   case VG_CUBIC_TO_ABS:
136      coords[0] = itr->coords[itr->coord_position + 4];
137      coords[1] = itr->coords[itr->coord_position + 5];
138      coords[2] = itr->coords[itr->coord_position + 2];
139      coords[3] = itr->coords[itr->coord_position + 3];
140      coords[4] = itr->coords[itr->coord_position + 0];
141      coords[5] = itr->coords[itr->coord_position + 1];
142      break;
143   default:
144      debug_assert(!"invalid command!\n");
145   }
146}
147
148
149static VGPathCommand stroke_fw_current_command(struct stroke_iterator *it)
150{
151   return it->cmds[it->position];
152}
153
154static VGPathCommand stroke_bw_current_command(struct stroke_iterator *it)
155{
156   VGPathCommand prev_cmd;
157   if (it->position == it->num_commands  -1)
158      return VG_MOVE_TO_ABS;
159
160   prev_cmd = it->cmds[it->position + 1];
161   return prev_cmd;
162}
163
164static VGboolean stroke_fw_has_next(struct stroke_iterator *itr)
165{
166   return itr->position < (itr->num_commands - 1);
167}
168
169static VGboolean stroke_bw_has_next(struct stroke_iterator *itr)
170{
171   return itr->position > 0;
172}
173
174static void stroke_fw_next(struct stroke_iterator *itr)
175{
176   VGubyte cmd;
177   debug_assert(stroke_fw_has_next(itr));
178
179   cmd = stroke_itr_command(itr);
180
181   itr->coord_position += num_elements_for_segments(&cmd, 1);
182   ++itr->position;
183}
184
185static void stroke_bw_next(struct stroke_iterator *itr)
186{
187   VGubyte cmd;
188   debug_assert(stroke_bw_has_next(itr));
189
190   --itr->position;
191   cmd = stroke_itr_command(itr);
192
193   itr->coord_position -= num_elements_for_segments(&cmd, 1);
194}
195
196static void stroke_itr_common_init(struct stroke_iterator *itr,
197                                   struct array *cmds,
198                                   struct array *coords)
199{
200   itr->cmds = (VGubyte*)cmds->data;
201   itr->num_commands = cmds->num_elements;
202
203   itr->coords = (VGfloat*)coords->data;
204   itr->num_coords = coords->num_elements;
205}
206
207static void stroke_forward_iterator(struct stroke_iterator *itr,
208                                    struct array *cmds,
209                                    struct array *coords)
210{
211   stroke_itr_common_init(itr, cmds, coords);
212   itr->position = 0;
213   itr->coord_position = 0;
214
215   itr->next = stroke_fw_next;
216   itr->has_next = stroke_fw_has_next;
217   itr->current_command = stroke_fw_current_command;
218   itr->current_coords = stroke_fw_itr_coords;
219}
220
221static void stroke_backward_iterator(struct stroke_iterator *itr,
222                                     struct array *cmds,
223                                     struct array *coords)
224{
225   VGubyte cmd;
226   stroke_itr_common_init(itr, cmds, coords);
227   itr->position = itr->num_commands - 1;
228
229   cmd = stroke_bw_current_command(itr);
230   itr->coord_position = itr->num_coords -
231                         num_elements_for_segments(&cmd, 1);
232
233   itr->next = stroke_bw_next;
234   itr->has_next = stroke_bw_has_next;
235   itr->current_command = stroke_bw_current_command;
236   itr->current_coords = stroke_bw_itr_coords;
237}
238
239
240
241static void stroke_flat_next(struct stroke_iterator *itr)
242{
243   VGubyte cmd;
244
245   if (itr->curve_index >= 0) {
246      ++itr->curve_index;
247      if (itr->curve_index >= polygon_vertex_count(itr->curve_poly)) {
248         itr->curve_index = -1;
249         polygon_destroy(itr->curve_poly);
250         itr->curve_poly = 0;
251      } else
252         return;
253   }
254   debug_assert(stroke_fw_has_next(itr));
255
256   cmd = itr->cmds[itr->position];
257   itr->coord_position += num_elements_for_segments(&cmd, 1);
258   ++itr->position;
259
260   cmd = itr->cmds[itr->position];
261
262   if (cmd == VG_CUBIC_TO_ABS) {
263      struct bezier bezier;
264      VGfloat bez[8];
265
266      bez[0] = itr->coords[itr->coord_position - 2];
267      bez[1] = itr->coords[itr->coord_position - 1];
268      bez[2] = itr->coords[itr->coord_position];
269      bez[3] = itr->coords[itr->coord_position + 1];
270      bez[4] = itr->coords[itr->coord_position + 2];
271      bez[5] = itr->coords[itr->coord_position + 3];
272      bez[6] = itr->coords[itr->coord_position + 4];
273      bez[7] = itr->coords[itr->coord_position + 5];
274
275      bezier_init(&bezier,
276                  bez[0], bez[1],
277                  bez[2], bez[3],
278                  bez[4], bez[5],
279                  bez[6], bez[7]);
280      /* skip the first one, it's the same as the prev point */
281      itr->curve_index = 1;
282      if (itr->curve_poly) {
283         polygon_destroy(itr->curve_poly);
284         itr->curve_poly = 0;
285      }
286      itr->curve_poly = bezier_to_polygon(&bezier);
287   }
288}
289
290static VGboolean stroke_flat_has_next(struct stroke_iterator *itr)
291{
292   return  (itr->curve_index >= 0 &&
293            itr->curve_index < (polygon_vertex_count(itr->curve_poly)-1))
294            || itr->position < (itr->num_commands - 1);
295}
296
297static VGPathCommand stroke_flat_current_command(struct stroke_iterator *it)
298{
299   if (it->cmds[it->position] == VG_CUBIC_TO_ABS) {
300      return VG_LINE_TO_ABS;
301   }
302   return it->cmds[it->position];
303}
304
305static void stroke_flat_itr_coords(struct stroke_iterator *itr, VGfloat *coords)
306{
307   if (itr->curve_index <= -1 && itr->position >= itr->num_commands)
308      return;
309
310   if (itr->curve_index >= 0) {
311      polygon_vertex(itr->curve_poly, itr->curve_index,
312                     coords);
313      return;
314   }
315
316   switch (stroke_itr_command(itr)) {
317   case VG_MOVE_TO_ABS:
318      coords[0] = itr->coords[itr->coord_position];
319      coords[1] = itr->coords[itr->coord_position + 1];
320      break;
321   case VG_LINE_TO_ABS:
322      coords[0] = itr->coords[itr->coord_position];
323      coords[1] = itr->coords[itr->coord_position + 1];
324      break;
325   case VG_CUBIC_TO_ABS:
326   default:
327      debug_assert(!"invalid command!\n");
328   }
329}
330
331static void stroke_flat_iterator(struct stroke_iterator *itr,
332                                 struct array *cmds,
333                                 struct array *coords)
334{
335   stroke_itr_common_init(itr, cmds, coords);
336   itr->position = 0;
337   itr->coord_position = 0;
338
339   itr->next = stroke_flat_next;
340   itr->has_next = stroke_flat_has_next;
341   itr->current_command = stroke_flat_current_command;
342   itr->current_coords = stroke_flat_itr_coords;
343   itr->curve_index = -1;
344   itr->curve_poly = 0;
345}
346
347
348static INLINE VGboolean finite_coords4(const VGfloat *c)
349{
350   return
351      isfinite(c[0]) && isfinite(c[1]) &&
352      isfinite(c[2]) && isfinite(c[3]);
353}
354
355/* from Graphics Gems II */
356#define SAME_SIGNS(a, b) ((a) * (b) >= 0)
357static VGboolean do_lines_intersect(VGfloat x1, VGfloat y1, VGfloat x2, VGfloat y2,
358                                    VGfloat x3, VGfloat y3, VGfloat x4, VGfloat y4)
359{
360   VGfloat a1, a2, b1, b2, c1, c2; /* Coefficients of line eqns */
361   VGfloat r1, r2, r3, r4;         /* 'sign' values */
362
363   a1 = y2 - y1;
364   b1 = x1 - x2;
365   c1 = x2 * y1 - x1 * y2;
366
367   r3 = a1 * x3 + b1 * y3 + c1;
368   r4 = a1 * x4 + b1 * y4 + c1;
369
370   if (r3 != 0 && r4 != 0 && SAME_SIGNS(r3, r4))
371      return VG_FALSE;
372
373   a2 = y4 - y3;
374   b2 = x3 - x4;
375   c2 = x4 * y3 - x3 * y4;
376
377   r1 = a2 * x1 + b2 * y1 + c2;
378   r2 = a2 * x2 + b2 * y2 + c2;
379
380   if (r1 != 0 && r2 != 0 && SAME_SIGNS(r1, r2))
381      return VG_FALSE;
382
383   return VG_TRUE;
384}
385
386static INLINE VGfloat line_dx(const VGfloat *l)
387{
388   return l[2] - l[0];
389}
390
391static INLINE VGfloat line_dy(const VGfloat *l)
392{
393   return l[3] - l[1];
394}
395
396static INLINE VGfloat line_angle(const VGfloat *l)
397{
398   const VGfloat dx = line_dx(l);
399   const VGfloat dy = line_dy(l);
400
401   const VGfloat theta = atan2(-dy, dx) * 360.0 / M_2PI;
402
403   const VGfloat theta_normalized = theta < 0 ? theta + 360 : theta;
404
405   if (floatsEqual(theta_normalized, 360.f))
406      return 0;
407   else
408      return theta_normalized;
409}
410
411static INLINE void line_set_length(VGfloat *l, VGfloat len)
412{
413   VGfloat uv[] = {l[0], l[1], l[2], l[3]};
414   if (null_line(l))
415      return;
416   line_normalize(uv);
417   l[2] = l[0] + line_dx(uv) * len;
418   l[3] = l[1] + line_dy(uv) * len;
419}
420
421static INLINE void line_translate(VGfloat *l, VGfloat x, VGfloat y)
422{
423   l[0] += x;
424   l[1] += y;
425   l[2] += x;
426   l[3] += y;
427}
428
429static INLINE VGfloat line_angle_to(const VGfloat *l1,
430                                    const VGfloat *l2)
431{
432   VGfloat a1, a2, delta, delta_normalized;
433   if (null_line(l1) || null_line(l1))
434      return 0;
435
436   a1 = line_angle(l1);
437   a2 = line_angle(l2);
438
439   delta = a2 - a1;
440   delta_normalized = delta < 0 ? delta + 360 : delta;
441
442   if (floatsEqual(delta, 360.f))
443      return 0;
444   else
445      return delta_normalized;
446}
447
448static INLINE VGfloat line_angles(const VGfloat *l1,
449                                  const VGfloat *l2)
450{
451   VGfloat cos_line, rad = 0;
452
453   if (null_line(l1) || null_line(l2))
454      return 0;
455
456   cos_line = (line_dx(l1)*line_dx(l2) + line_dy(l1)*line_dy(l2)) /
457              (line_lengthv(l1)*line_lengthv(l2));
458   rad = 0;
459
460   if (cos_line >= -1.0 && cos_line <= 1.0)
461      rad = acos(cos_line);
462   return rad * 360 / M_2PI;
463}
464
465
466static INLINE VGfloat adapted_angle_on_x(const VGfloat *line)
467{
468   const VGfloat identity[] = {0, 0, 1, 0};
469   VGfloat angle = line_angles(line, identity);
470   if (line_dy(line) > 0)
471      angle = 360 - angle;
472   return angle;
473}
474
475static enum intersection_type line_intersect(const VGfloat *l1,
476                                             const VGfloat *l2,
477                                             float *intersection_point)
478{
479   VGfloat isect[2] = { 0 };
480   enum intersection_type type;
481   VGboolean dx_zero, ldx_zero;
482
483   if (null_line(l1) || null_line(l2) ||
484       !finite_coords4(l1) || !finite_coords4(l2))
485      return NoIntersections;
486
487   type = do_lines_intersect(l1[0], l1[1], l1[2], l1[3], l2[0], l2[1], l2[2], l2[3])
488          ? BoundedIntersection : UnboundedIntersection;
489
490   dx_zero  = floatsEqual(line_dx(l1) + 1, 1);
491   ldx_zero = floatsEqual(line_dx(l2) + 1, 1);
492
493   /* one of the lines is vertical */
494   if (dx_zero && ldx_zero) {
495      type = NoIntersections;
496   } else if (dx_zero) {
497      VGfloat la = line_dy(l2) / line_dx(l2);
498      isect[0] = l1[0];
499      isect[1] = la * l1[0] + l2[1] - la * l2[0];
500   } else if (ldx_zero) {
501      VGfloat ta = line_dy(l1) / line_dx(l1);
502      isect[0] = l2[0];
503      isect[1] = ta * l2[0] + l1[1] - ta*l1[0];
504   } else {
505      VGfloat x;
506      VGfloat ta = line_dy(l1) / line_dx(l1);
507      VGfloat la = line_dy(l2) / line_dx(l2);
508      if (ta == la)
509         return NoIntersections;
510
511      x = ( - l2[1] + la * l2[0] + l1[1] - ta * l1[0] ) / (la - ta);
512      isect[0] = x;
513      isect[1] = ta*(x - l1[0]) + l1[1];
514   }
515   if (intersection_point) {
516      intersection_point[0] = isect[0];
517      intersection_point[1] = isect[1];
518   }
519   return type;
520}
521
522static INLINE enum line_join_mode stroker_join_mode(struct stroker *s)
523{
524   switch(s->join_style) {
525   case VG_JOIN_MITER:
526      return MiterJoin;
527   case VG_JOIN_ROUND:
528      return RoundJoin;
529   case VG_JOIN_BEVEL:
530      return FlatJoin;
531   default:
532      return FlatJoin;
533   }
534}
535
536static INLINE enum line_join_mode stroker_cap_mode(struct stroker *s)
537{
538   switch(s->cap_style) {
539   case VG_CAP_BUTT:
540      return FlatJoin;
541   case VG_CAP_ROUND:
542      return RoundCap;
543   case VG_CAP_SQUARE:
544      return SquareJoin;
545   default:
546      return FlatJoin;
547   }
548}
549
550void stroker_emit_move_to(struct stroker *stroker, VGfloat x, VGfloat y)
551{
552   VGubyte cmds = VG_MOVE_TO_ABS;
553   VGfloat coords[2] = {x, y};
554#if DEBUG_EMITS
555   debug_printf("emit move %f, %f\n", x, y);
556#endif
557   stroker->back2_x = stroker->back1_x;
558   stroker->back2_y = stroker->back1_y;
559   stroker->back1_x = x;
560   stroker->back1_y = y;
561
562   path_append_data(stroker->path,
563                    1,
564                    &cmds, &coords);
565}
566
567void stroker_emit_line_to(struct stroker *stroker, VGfloat x, VGfloat y)
568{
569   VGubyte cmds = VG_LINE_TO_ABS;
570   VGfloat coords[2] = {x, y};
571#if DEBUG_EMITS
572   debug_printf("emit line %f, %f\n", x, y);
573#endif
574   stroker->back2_x = stroker->back1_x;
575   stroker->back2_y = stroker->back1_y;
576   stroker->back1_x = x;
577   stroker->back1_y = y;
578   path_append_data(stroker->path,
579                    1,
580                    &cmds, &coords);
581}
582
583void stroker_emit_curve_to(struct stroker *stroker, VGfloat px1, VGfloat py1,
584                                  VGfloat px2, VGfloat py2,
585                                  VGfloat x, VGfloat y)
586{
587   VGubyte cmds = VG_CUBIC_TO_ABS;
588   VGfloat coords[6] = {px1, py1, px2, py2, x, y};
589#if DEBUG_EMITS
590   debug_printf("emit curve %f, %f, %f, %f, %f, %f\n", px1, py1,
591                px2, py2, x, y);
592#endif
593
594   if (px2 == x && py2 == y) {
595      if (px1 == x && py1 == y) {
596         stroker->back2_x = stroker->back1_x;
597         stroker->back2_y = stroker->back1_y;
598      } else {
599         stroker->back2_x = px1;
600         stroker->back2_y = py1;
601      }
602   } else {
603      stroker->back2_x = px2;
604      stroker->back2_y = py2;
605   }
606   stroker->back1_x = x;
607   stroker->back1_y = y;
608
609   path_append_data(stroker->path,
610                    1,
611                    &cmds, &coords);
612}
613
614static INLINE void create_round_join(struct stroker *stroker,
615                                     VGfloat x1, VGfloat y1,
616                                     VGfloat x2, VGfloat y2,
617                                     VGfloat width, VGfloat height)
618{
619   struct arc arc;
620   struct matrix matrix;
621
622   matrix_load_identity(&matrix);
623
624   /*stroker_emit_line_to(stroker, nx, ny);*/
625
626   arc_init(&arc, VG_SCCWARC_TO,
627            x1, y1, x2, y2, width/2, height/2, 0);
628   arc_stroker_emit(&arc, stroker, &matrix);
629}
630
631
632static void create_joins(struct stroker *stroker,
633                         VGfloat focal_x, VGfloat focal_y,
634                         const VGfloat *next_line, enum line_join_mode join)
635{
636#if DEBUG_EMITS
637   debug_printf("create_joins: focal=[%f, %f], next_line=[%f, %f,%f, %f]\n",
638                focal_x, focal_y,
639                next_line[0], next_line[1], next_line[2], next_line[3]);
640#endif
641   /* if we're alredy connected do nothing */
642   if (floatsEqual(stroker->back1_x, next_line[0]) &&
643       floatsEqual(stroker->back1_y, next_line[1]))
644      return;
645
646   if (join == FlatJoin) {
647      stroker_emit_line_to(stroker, next_line[0], next_line[1]);
648   } else {
649      VGfloat prev_line[] = {stroker->back2_x, stroker->back2_y,
650                             stroker->back1_x, stroker->back1_y};
651
652      VGfloat isect[2] = { 0 };
653      enum intersection_type type = line_intersect(prev_line, next_line, isect);
654
655      if (join == SquareJoin) {
656         VGfloat offset = stroker->stroke_width / 2;
657         VGfloat l1[4] = {prev_line[0],
658                          prev_line[1],
659                          prev_line[2],
660                          prev_line[3]};
661         VGfloat l2[4] = {next_line[2],
662                          next_line[3],
663                          next_line[0],
664                          next_line[1]};
665
666         line_translate(l1, line_dx(l1), line_dy(l1));
667         line_set_length(l1, offset);
668
669         line_translate(l2, line_dx(l2), line_dy(l2));
670         line_set_length(l2, offset);
671
672         stroker_emit_line_to(stroker, l1[2], l1[3]);
673         stroker_emit_line_to(stroker, l2[2], l2[3]);
674         stroker_emit_line_to(stroker, l2[0], l2[1]);
675      } else if (join == RoundJoin) {
676         VGfloat offset = stroker->stroke_width / 2;
677         VGfloat short_cut[4] = {prev_line[2], prev_line[3],
678                                 next_line[0], next_line[1]};
679         VGfloat angle = line_angles(prev_line, short_cut);
680
681         if (type == BoundedIntersection ||
682             (angle > 90 && !floatsEqual(angle, 90.f))) {
683            stroker_emit_line_to(stroker, next_line[0], next_line[1]);
684            return;
685         }
686         create_round_join(stroker, prev_line[2], prev_line[3],
687                           next_line[0], next_line[1],
688                           offset * 2, offset * 2);
689
690         stroker_emit_line_to(stroker, next_line[0], next_line[1]);
691      } else if (join == RoundCap) {
692         VGfloat offset = stroker->stroke_width / 2;
693         VGfloat l1[4] = { prev_line[0], prev_line[1],
694                           prev_line[2], prev_line[3] };
695         VGfloat l2[4] = {focal_x, focal_y,
696                          prev_line[2], prev_line[3]};
697
698         line_translate(l1, line_dx(l1), line_dy(l1));
699         line_set_length(l1, KAPPA * offset);
700
701         /* normal between prev_line and focal */
702         line_translate(l2, -line_dy(l2), line_dx(l2));
703         line_set_length(l2, KAPPA * offset);
704
705         stroker_emit_curve_to(stroker, l1[2], l1[3],
706                               l2[2], l2[3],
707                               l2[0], l2[1]);
708
709         l2[0] = l2[0];
710         l2[1] = l2[1];
711         l2[2] = l2[0] - line_dx(l2);
712         l2[3] = l2[1] - line_dy(l2);
713
714         line_translate(l1, next_line[0] - l1[0], next_line[1] - l1[1]);
715
716         stroker_emit_curve_to(stroker,
717                               l2[2], l2[3],
718                               l1[2], l1[3],
719                               l1[0], l1[1]);
720      } else if (join == MiterJoin) {
721         VGfloat miter_line[4] = {stroker->back1_x, stroker->back1_y,
722                                  isect[0], isect[1]};
723         VGfloat sl = (stroker->stroke_width * stroker->miter_limit);
724         VGfloat inside_line[4] = {prev_line[2], prev_line[3],
725                                   next_line[0], next_line[1]};
726         VGfloat angle = line_angle_to(inside_line, prev_line);
727
728         if (type == BoundedIntersection ||
729             (angle > 90 && !floatsEqual(angle, 90.f))) {
730            /*
731            debug_printf("f = %f, nl = %f, pl = %f, is = %f\n",
732                         focal_x, next_line[0],
733                         prev_line[2], isect[0]);*/
734            stroker_emit_line_to(stroker, next_line[0], next_line[1]);
735            return;
736         }
737
738         if (type == NoIntersections || line_lengthv(miter_line) > sl) {
739            stroker_emit_line_to(stroker, next_line[0], next_line[1]);
740         } else {
741            stroker_emit_line_to(stroker, isect[0], isect[1]);
742            stroker_emit_line_to(stroker, next_line[0], next_line[1]);
743         }
744      } else {
745         debug_assert(!"create_joins bad join style");
746      }
747   }
748}
749
750static void stroker_add_segment(struct stroker *stroker,
751                                VGPathCommand cmd,
752                                const VGfloat *coords,
753                                VGint num_coords)
754{
755   /* skip duplicated points */
756   if (stroker->segments->num_elements &&
757       stroker->last_cmd == cmd) {
758      VGfloat *data = stroker->control_points->data;
759      data += stroker->control_points->num_elements;
760      data -= num_coords;
761      switch (cmd) {
762      case VG_MOVE_TO_ABS:
763         if (floatsEqual(coords[0], data[0]) &&
764             floatsEqual(coords[1], data[1]))
765            return;
766         break;
767      case VG_LINE_TO_ABS:
768         if (floatsEqual(coords[0], data[0]) &&
769             floatsEqual(coords[1], data[1]))
770            return;
771         break;
772      case VG_CUBIC_TO_ABS:
773         if (floatsEqual(coords[0], data[0]) &&
774             floatsEqual(coords[1], data[1]) &&
775             floatsEqual(coords[2], data[2]) &&
776             floatsEqual(coords[3], data[3]) &&
777             floatsEqual(coords[4], data[4]) &&
778             floatsEqual(coords[5], data[5]))
779            return;
780         break;
781      default:
782         debug_assert(!"Invalid stroke segment");
783      }
784   } else if (stroker->last_cmd == VG_CUBIC_TO_ABS &&
785              cmd == VG_LINE_TO_ABS) {
786      VGfloat *data = stroker->control_points->data;
787      data += stroker->control_points->num_elements;
788      data -= 2;
789      if (floatsEqual(coords[0], data[0]) &&
790          floatsEqual(coords[1], data[1]))
791         return;
792   }
793   stroker->last_cmd = cmd;
794   array_append_data(stroker->segments, &cmd, 1);
795   array_append_data(stroker->control_points, coords, num_coords);
796}
797
798void stroker_move_to(struct stroker *stroker, VGfloat x, VGfloat y)
799{
800   VGfloat coords[2] = {x, y};
801#if STROKE_SEGMENTS
802   debug_printf("stroker_move_to(%f, %f)\n", x, y);
803#endif
804
805   if (stroker->segments->num_elements > 0)
806      stroker->process_subpath(stroker);
807
808   array_reset(stroker->segments);
809   array_reset(stroker->control_points);
810
811   stroker_add_segment(stroker, VG_MOVE_TO_ABS, coords, 2);
812}
813
814void stroker_line_to(struct stroker *stroker, VGfloat x, VGfloat y)
815{
816   VGfloat coords[] = {x, y};
817
818#if STROKE_SEGMENTS
819   debug_printf("stroker_line_to(%f, %f)\n", x, y);
820#endif
821   if (!stroker->segments->num_elements)
822      stroker_add_segment(stroker, VG_MOVE_TO_ABS, zero_coords, 2);
823
824   stroker_add_segment(stroker, VG_LINE_TO_ABS, coords, 2);
825}
826
827void stroker_curve_to(struct stroker *stroker, VGfloat px1, VGfloat py1,
828                      VGfloat px2, VGfloat py2,
829                      VGfloat x, VGfloat y)
830{
831   VGfloat coords[] = {px1, py1,
832                       px2, py2,
833                       x, y};
834#if STROKE_SEGMENTS
835   debug_printf("stroker_curve_to(%f, %f, %f, %f, %f, %f)\n",
836                px1, py1, px2, py2, x, y);
837#endif
838   if (!stroker->segments->num_elements)
839      stroker_add_segment(stroker, VG_MOVE_TO_ABS, zero_coords, 2);
840
841   stroker_add_segment(stroker, VG_CUBIC_TO_ABS, coords, 6);
842}
843
844static INLINE VGboolean is_segment_null(VGPathCommand cmd,
845                                        VGfloat *coords,
846                                        VGfloat *res)
847{
848   switch(cmd) {
849   case VG_MOVE_TO_ABS:
850   case VG_LINE_TO_ABS:
851      return floatsEqual(coords[0], res[0]) &&
852         floatsEqual(coords[1], res[1]);
853      break;
854   case VG_CUBIC_TO_ABS:
855      return floatsEqual(coords[0], res[0]) &&
856         floatsEqual(coords[1], res[1]) &&
857         floatsEqual(coords[2], res[0]) &&
858         floatsEqual(coords[3], res[1]) &&
859         floatsEqual(coords[4], res[0]) &&
860         floatsEqual(coords[5], res[1]);
861      break;
862   default:
863      assert(0);
864   }
865   return VG_FALSE;
866}
867
868static VGboolean vg_stroke_outline(struct stroke_iterator *it,
869                                struct stroker *stroker,
870                                VGboolean cap_first,
871                                VGfloat *start_tangent)
872{
873#define MAX_OFFSET 16
874   struct bezier offset_curves[MAX_OFFSET];
875   VGPathCommand first_element;
876   VGfloat start[2], prev[2];
877   VGboolean first = VG_TRUE;
878   VGfloat offset;
879
880   first_element = stroke_itr_command(it);
881   if (first_element != VG_MOVE_TO_ABS) {
882      stroker_emit_move_to(stroker, 0.f, 0.f);
883      prev[0] = 0.f;
884      prev[1] = 0.f;
885   }
886   stroke_itr_coords(it, start);
887#if STROKE_DEBUG
888   debug_printf(" -> (side) [%.2f, %.2f]\n",
889                start[0],
890                start[1]);
891#endif
892
893   prev[0] = start[0];
894   prev[1] = start[1];
895
896   offset = stroker->stroke_width / 2;
897
898   if (!it->has_next(it)) {
899      /* single point */
900
901      return VG_TRUE;
902   }
903
904   while (it->has_next(it)) {
905      VGPathCommand cmd;
906      VGfloat coords[8];
907
908      it->next(it);
909      cmd = stroke_itr_command(it);
910      stroke_itr_coords(it, coords);
911
912      if (cmd == VG_LINE_TO_ABS) {
913         VGfloat line[4] = {prev[0], prev[1], coords[0], coords[1]};
914         VGfloat normal[4];
915         line_normal(line, normal);
916
917#if STROKE_DEBUG
918         debug_printf("\n ---> (side) lineto [%.2f, %.2f]\n", coords[0], coords[1]);
919#endif
920         line_set_length(normal, offset);
921         line_translate(line, line_dx(normal), line_dy(normal));
922
923         /* if we are starting a new subpath, move to correct starting point */
924         if (first) {
925            if (cap_first)
926               create_joins(stroker, prev[0], prev[1], line,
927                            stroker_cap_mode(stroker));
928            else
929               stroker_emit_move_to(stroker, line[0], line[1]);
930            memcpy(start_tangent, line,
931                   sizeof(VGfloat) * 4);
932            first = VG_FALSE;
933         } else {
934            create_joins(stroker, prev[0], prev[1], line,
935                         stroker_join_mode(stroker));
936         }
937
938         /* add the stroke for this line */
939         stroker_emit_line_to(stroker, line[2], line[3]);
940         prev[0] = coords[0];
941         prev[1] = coords[1];
942      } else if (cmd == VG_CUBIC_TO_ABS) {
943#if STROKE_DEBUG
944         debug_printf("\n ---> (side) cubicTo [%.2f, %.2f]\n",
945                coords[4],
946                coords[5]);
947#endif
948         struct bezier bezier;
949         int count;
950
951         bezier_init(&bezier,
952                     prev[0], prev[1], coords[0], coords[1],
953                     coords[2], coords[3], coords[4], coords[5]);
954
955         count = bezier_translate_by_normal(&bezier,
956                                            offset_curves,
957                                            MAX_OFFSET,
958                                            offset,
959                                            curve_threshold);
960
961         if (count) {
962            /* if we are starting a new subpath, move to correct starting point */
963            VGfloat tangent[4];
964            VGint i;
965
966            bezier_start_tangent(&bezier, tangent);
967            line_translate(tangent,
968                           offset_curves[0].x1 - bezier.x1,
969                           offset_curves[0].y1 - bezier.y1);
970            if (first) {
971               VGfloat pt[2] = {offset_curves[0].x1,
972                                offset_curves[0].y1};
973
974               if (cap_first) {
975                  create_joins(stroker, prev[0], prev[1], tangent,
976                               stroker_cap_mode(stroker));
977               } else {
978                  stroker_emit_move_to(stroker, pt[0], pt[1]);
979               }
980               start_tangent[0] = tangent[0];
981               start_tangent[1] = tangent[1];
982               start_tangent[2] = tangent[2];
983               start_tangent[3] = tangent[3];
984               first = VG_FALSE;
985            } else {
986               create_joins(stroker, prev[0], prev[1], tangent,
987                            stroker_join_mode(stroker));
988            }
989
990            /* add these beziers */
991            for (i = 0; i < count; ++i) {
992               struct bezier *bez = &offset_curves[i];
993               stroker_emit_curve_to(stroker,
994                                     bez->x2, bez->y2,
995                                     bez->x3, bez->y3,
996                                     bez->x4, bez->y4);
997            }
998         }
999
1000         prev[0] = coords[4];
1001         prev[1] = coords[5];
1002      }
1003   }
1004
1005   if (floatsEqual(start[0], prev[0]) &&
1006       floatsEqual(start[1], prev[1])) {
1007      /* closed subpath, join first and last point */
1008#if STROKE_DEBUG
1009      debug_printf("\n stroker: closed subpath\n");
1010#endif
1011      create_joins(stroker, prev[0], prev[1], start_tangent,
1012                   stroker_join_mode(stroker));
1013      return VG_TRUE;
1014   } else {
1015#if STROKE_DEBUG
1016      debug_printf("\n stroker: open subpath\n");
1017#endif
1018      return VG_FALSE;
1019   }
1020#undef MAX_OFFSET
1021}
1022
1023static void stroker_process_subpath(struct stroker *stroker)
1024{
1025   VGboolean fwclosed, bwclosed;
1026   VGfloat fw_start_tangent[4], bw_start_tangent[4];
1027   struct stroke_iterator fwit;
1028   struct stroke_iterator bwit;
1029   debug_assert(stroker->segments->num_elements > 0);
1030
1031   memset(fw_start_tangent, 0,
1032          sizeof(VGfloat)*4);
1033   memset(bw_start_tangent, 0,
1034          sizeof(VGfloat)*4);
1035
1036   stroke_forward_iterator(&fwit, stroker->segments,
1037                           stroker->control_points);
1038   stroke_backward_iterator(&bwit, stroker->segments,
1039                            stroker->control_points);
1040
1041   debug_assert(fwit.cmds[0] == VG_MOVE_TO_ABS);
1042
1043   fwclosed = vg_stroke_outline(&fwit, stroker, VG_FALSE, fw_start_tangent);
1044   bwclosed = vg_stroke_outline(&bwit, stroker, !fwclosed, bw_start_tangent);
1045
1046   if (!bwclosed)
1047      create_joins(stroker,
1048                   fwit.coords[0], fwit.coords[1], fw_start_tangent,
1049                   stroker_cap_mode(stroker));
1050   else {
1051      /* hack to handle the requirement of the VG spec that says that strokes
1052       * of len==0 that have butt cap or round cap still need
1053       * to be rendered. (8.7.4 Stroke Generation) */
1054      if (stroker->segments->num_elements <= 3) {
1055         VGPathCommand cmd;
1056         VGfloat data[8], coords[8];
1057         struct stroke_iterator *it = &fwit;
1058
1059         stroke_forward_iterator(it, stroker->segments,
1060                                 stroker->control_points);
1061         cmd = stroke_itr_command(it);
1062         stroke_itr_coords(it, coords);
1063         if (cmd != VG_MOVE_TO_ABS) {
1064            memset(data, 0, sizeof(VGfloat) * 8);
1065            if (!is_segment_null(cmd, coords, data))
1066               return;
1067         } else {
1068            data[0] = coords[0];
1069            data[1] = coords[1];
1070         }
1071         while (it->has_next(it)) {
1072            it->next(it);
1073            cmd = stroke_itr_command(it);
1074            stroke_itr_coords(it, coords);
1075            if (!is_segment_null(cmd, coords, data))
1076               return;
1077         }
1078         /* generate the square/round cap */
1079         if (stroker->cap_style == VG_CAP_SQUARE) {
1080            VGfloat offset = stroker->stroke_width / 2;
1081            stroker_emit_move_to(stroker, data[0] - offset,
1082                                 data[1] - offset);
1083            stroker_emit_line_to(stroker, data[0] + offset,
1084                                 data[1] - offset);
1085            stroker_emit_line_to(stroker, data[0] + offset,
1086                                 data[1] + offset);
1087            stroker_emit_line_to(stroker, data[0] - offset,
1088                                 data[1] + offset);
1089            stroker_emit_line_to(stroker, data[0] - offset,
1090                                 data[1] - offset);
1091         } else if (stroker->cap_style == VG_CAP_ROUND) {
1092            VGfloat offset = stroker->stroke_width / 2;
1093            VGfloat cx = data[0], cy = data[1];
1094            { /*circle */
1095               struct arc arc;
1096               struct matrix matrix;
1097               matrix_load_identity(&matrix);
1098
1099               stroker_emit_move_to(stroker, cx + offset, cy);
1100               arc_init(&arc, VG_SCCWARC_TO,
1101                        cx + offset, cy,
1102                        cx - offset, cy,
1103                        offset, offset, 0);
1104               arc_stroker_emit(&arc, stroker, &matrix);
1105               arc_init(&arc, VG_SCCWARC_TO,
1106                         cx - offset, cy,
1107                         cx + offset, cy,
1108                         offset, offset, 0);
1109               arc_stroker_emit(&arc, stroker, &matrix);
1110            }
1111         }
1112      }
1113   }
1114}
1115
1116static INLINE VGfloat dash_pattern(struct dash_stroker *stroker,
1117                                   VGint idx)
1118{
1119   if (stroker->dash_pattern[idx] < 0)
1120      return 0.f;
1121   return stroker->dash_pattern[idx];
1122}
1123
1124static void dash_stroker_process_subpath(struct stroker *str)
1125{
1126   struct dash_stroker *stroker = (struct dash_stroker *)str;
1127   VGfloat sum_length = 0;
1128   VGint i;
1129   VGint idash = 0;
1130   VGfloat pos = 0;
1131   VGfloat elen = 0;
1132   VGfloat doffset = stroker->dash_phase;
1133   VGfloat estart = 0;
1134   VGfloat estop = 0;
1135   VGfloat cline[4];
1136   struct stroke_iterator it;
1137   VGfloat prev[2];
1138   VGfloat move_to_pos[2];
1139   VGfloat line_to_pos[2];
1140
1141   VGboolean has_move_to = VG_FALSE;
1142
1143   stroke_flat_iterator(&it, stroker->base.segments,
1144                        stroker->base.control_points);
1145
1146   stroke_itr_coords(&it, prev);
1147   move_to_pos[0] = prev[0];
1148   move_to_pos[1] = prev[1];
1149
1150   debug_assert(stroker->dash_pattern_num > 0);
1151
1152   for (i = 0; i < stroker->dash_pattern_num; ++i) {
1153      sum_length += dash_pattern(stroker, i);
1154   }
1155
1156   if (floatIsZero(sum_length)) {
1157      return;
1158   }
1159
1160   doffset -= floorf(doffset / sum_length) * sum_length;
1161
1162   while (!floatIsZero(doffset) && doffset >= dash_pattern(stroker, idash)) {
1163      doffset -= dash_pattern(stroker, idash);
1164      idash = (idash + 1) % stroker->dash_pattern_num;
1165   }
1166
1167   while (it.has_next(&it)) {
1168      VGPathCommand cmd;
1169      VGfloat coords[8];
1170      VGboolean done;
1171
1172      it.next(&it);
1173      cmd = stroke_itr_command(&it);
1174      stroke_itr_coords(&it, coords);
1175
1176      debug_assert(cmd == VG_LINE_TO_ABS);
1177      cline[0] = prev[0];
1178      cline[1] = prev[1];
1179      cline[2] = coords[0];
1180      cline[3] = coords[1];
1181
1182      elen = line_lengthv(cline);
1183
1184      estop = estart + elen;
1185
1186      done = pos >= estop;
1187      while (!done) {
1188         VGfloat p2[2];
1189
1190         VGint idash_incr = 0;
1191         VGboolean has_offset = doffset > 0;
1192         VGfloat dpos = pos + dash_pattern(stroker, idash) - doffset - estart;
1193
1194         debug_assert(dpos >= 0);
1195
1196         if (dpos > elen) { /* dash extends this line */
1197            doffset = dash_pattern(stroker, idash) - (dpos - elen);
1198            pos = estop;
1199            done = VG_TRUE;
1200            p2[0] = cline[2];
1201            p2[1] = cline[3];
1202         } else { /* Dash is on this line */
1203            line_point_at(cline, dpos/elen, p2);
1204            pos = dpos + estart;
1205            done = pos >= estop;
1206            idash_incr = 1;
1207            doffset = 0;
1208         }
1209
1210         if (idash % 2 == 0) {
1211            line_to_pos[0] = p2[0];
1212            line_to_pos[1] = p2[1];
1213
1214            if (!has_offset || !has_move_to) {
1215               stroker_move_to(&stroker->stroker, move_to_pos[0], move_to_pos[1]);
1216               has_move_to = VG_TRUE;
1217            }
1218            stroker_line_to(&stroker->stroker, line_to_pos[0], line_to_pos[1]);
1219         } else {
1220            move_to_pos[0] = p2[0];
1221            move_to_pos[1] = p2[1];
1222         }
1223
1224         idash = (idash + idash_incr) % stroker->dash_pattern_num;
1225      }
1226
1227      estart = estop;
1228      prev[0] = coords[0];
1229      prev[1] = coords[1];
1230   }
1231
1232   if (it.curve_poly) {
1233      polygon_destroy(it.curve_poly);
1234      it.curve_poly = 0;
1235   }
1236
1237   stroker->base.path = stroker->stroker.path;
1238}
1239
1240static void default_begin(struct stroker *stroker)
1241{
1242   array_reset(stroker->segments);
1243   array_reset(stroker->control_points);
1244}
1245
1246static void default_end(struct stroker *stroker)
1247{
1248   if (stroker->segments->num_elements > 0)
1249      stroker->process_subpath(stroker);
1250}
1251
1252
1253static void dash_stroker_begin(struct stroker *stroker)
1254{
1255   struct dash_stroker *dasher =
1256      (struct dash_stroker *)stroker;
1257
1258   default_begin(&dasher->stroker);
1259   default_begin(stroker);
1260}
1261
1262static void dash_stroker_end(struct stroker *stroker)
1263{
1264   struct dash_stroker *dasher =
1265      (struct dash_stroker *)stroker;
1266
1267   default_end(stroker);
1268   default_end(&dasher->stroker);
1269}
1270
1271void stroker_init(struct stroker *stroker,
1272                  struct vg_state *state)
1273{
1274   stroker->stroke_width = state->stroke.line_width.f;
1275   stroker->miter_limit = state->stroke.miter_limit.f;
1276   stroker->cap_style = state->stroke.cap_style;
1277   stroker->join_style = state->stroke.join_style;
1278
1279   stroker->begin = default_begin;
1280   stroker->process_subpath = stroker_process_subpath;
1281   stroker->end = default_end;
1282
1283   stroker->segments = array_create(sizeof(VGubyte));
1284   stroker->control_points = array_create(sizeof(VGfloat));
1285
1286   stroker->back1_x = 0;
1287   stroker->back1_y = 0;
1288   stroker->back2_x = 0;
1289   stroker->back2_y = 0;
1290
1291   stroker->path = path_create(VG_PATH_DATATYPE_F, 1.0f, 0.0f,
1292                               0, 0, VG_PATH_CAPABILITY_ALL);
1293
1294   /* Initialize with an invalid value */
1295   stroker->last_cmd = (VGPathCommand)0;
1296}
1297
1298void dash_stroker_init(struct stroker *str,
1299                       struct vg_state *state)
1300{
1301   struct dash_stroker *stroker = (struct dash_stroker *)str;
1302   int i;
1303
1304   stroker_init(str, state);
1305   stroker_init(&stroker->stroker, state);
1306
1307   {
1308      int real_num = state->stroke.dash_pattern_num;
1309      if (real_num % 2)/* if odd, ignore the last one */
1310         --real_num;
1311      for (i = 0; i < real_num; ++i)
1312         stroker->dash_pattern[i] = state->stroke.dash_pattern[i].f;
1313      stroker->dash_pattern_num = real_num;
1314   }
1315
1316   stroker->dash_phase = state->stroke.dash_phase.f;
1317   stroker->dash_phase_reset = state->stroke.dash_phase_reset;
1318
1319   stroker->base.begin = dash_stroker_begin;
1320   stroker->base.process_subpath = dash_stroker_process_subpath;
1321   stroker->base.end = dash_stroker_end;
1322   path_destroy(stroker->base.path);
1323   stroker->base.path = NULL;
1324}
1325
1326void stroker_begin(struct stroker *stroker)
1327{
1328   stroker->begin(stroker);
1329}
1330
1331void stroker_end(struct stroker *stroker)
1332{
1333   stroker->end(stroker);
1334}
1335
1336void stroker_cleanup(struct stroker *stroker)
1337{
1338   array_destroy(stroker->segments);
1339   array_destroy(stroker->control_points);
1340}
1341
1342void dash_stroker_cleanup(struct dash_stroker *stroker)
1343{
1344   /* if stroker->base.path is null means we never
1345    * processed a valid path so delete the temp one
1346    * we already created */
1347   if (!stroker->base.path)
1348      path_destroy(stroker->stroker.path);
1349   stroker_cleanup(&stroker->stroker);
1350   stroker_cleanup((struct stroker*)stroker);
1351}
1352