simgear/canvas/ShivaVG/src/shGeometry.c

   1 /*
   2  * Copyright (c) 2007 Ivan Leben
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2.1 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library in the file COPYING;
  16  * if not, write to the Free Software Foundation, Inc.,
  17  * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  18  *
  19  */
  20
  21 #include <vg/openvg.h>
  22 #include "shContext.h"
  23 #include "shGeometry.h"
  24
  25
  26 static int shAddVertex(SHPath *p, SHVertex *v, SHint *contourStart)
  27 {
  28   /* Assert contour was open */
  29   SH_ASSERT((*contourStart) >= 0);
  30
  31   /* Check vertex limit */
  32   if (p->vertices.size >= SH_MAX_VERTICES) return 0;
  33
  34   /* Add vertex to subdivision */
  35   shVertexArrayPushBackP(&p->vertices, v);
  36
  37   /* Increment contour size. Its stored in
  38      the flags of first contour vertex */
  39   p->vertices.items[*contourStart].flags++;
  40
  41   return 1;
  42 }
  43
  44 static void shSubrecurseQuad(SHPath *p, SHQuad *quad, SHint *contourStart)
  45 {
  46   SHVertex v;
  47   SHVector2 mid, dif, c1, c2, c3;
  48   SHQuad quads[SH_MAX_RECURSE_DEPTH];
  49   SHQuad *q, *qleft, *qright;
  50   SHint qindex=0;
  51   quads[0] = *quad;
  52
  53   while (qindex >= 0) {
  54
  55     q = &quads[qindex];
  56
  57     /* Calculate distance of control point from its
  58      counterpart on the line between end points */
  59     SET2V(mid, q->p1); ADD2V(mid, q->p3); DIV2(mid, 2);
  60     SET2V(dif, q->p2); SUB2V(dif, mid); ABS2(dif);
  61
  62     /* Cancel if the curve is flat enough */
  63     if (dif.x + dif.y <= 1.0f || qindex == SH_MAX_RECURSE_DEPTH-1) {
  64
  65       /* Add subdivision point */
  66       v.point = q->p3; v.flags = 0;
  67       if (qindex == 0) return; /* Skip last point */
  68       if (!shAddVertex(p, &v, contourStart)) return;
  69       --qindex;
  70
  71     }else{
  72
  73       /* Left recursion goes on top of stack! */
  74       qright = q; qleft = &quads[++qindex];
  75
  76       /* Subdivide into 2 sub-curves */
  77       SET2V(c1, q->p1); ADD2V(c1, q->p2); DIV2(c1, 2);
  78       SET2V(c3, q->p2); ADD2V(c3, q->p3); DIV2(c3, 2);
  79       SET2V(c2, c1); ADD2V(c2, c3); DIV2(c2, 2);
  80
  81       /* Add left recursion onto stack */
  82       qleft->p1 = q->p1;
  83       qleft->p2 = c1;
  84       qleft->p3 = c2;
  85
  86       /* Add right recursion onto stack */
  87       qright->p1 = c2;
  88       qright->p2 = c3;
  89       qright->p3 = q->p3;
  90     }
  91   }
  92 }
  93
  94 static void shSubrecurseCubic(SHPath *p, SHCubic *cubic, SHint *contourStart)
  95 {
  96   SHVertex v;
  97   SHfloat dx1, dy1, dx2, dy2;
  98   SHVector2 mm, c1, c2, c3, c4, c5;
  99   SHCubic cubics[SH_MAX_RECURSE_DEPTH];
 100   SHCubic *c, *cleft, *cright;
 101   SHint cindex = 0;
 102   cubics[0] = *cubic;
 103
 104   while (cindex >= 0) {
 105
 106     c = &cubics[cindex];
 107
 108     /* Calculate distance of control points from their
 109      counterparts on the line between end points */
 110     dx1 = 3.0f*c->p2.x - 2.0f*c->p1.x - c->p4.x; dx1 *= dx1;
 111     dy1 = 3.0f*c->p2.y - 2.0f*c->p1.y - c->p4.y; dy1 *= dy1;
 112     dx2 = 3.0f*c->p3.x - 2.0f*c->p4.x - c->p1.x; dx2 *= dx2;
 113     dy2 = 3.0f*c->p3.y - 2.0f*c->p4.y - c->p1.y; dy2 *= dy2;
 114     if (dx1 < dx2) dx1 = dx2;
 115     if (dy1 < dy2) dy1 = dy2;
 116
 117     /* Cancel if the curve is flat enough */
 118     if (dx1+dy1 <= 1.0 || cindex == SH_MAX_RECURSE_DEPTH-1) {
 119
 120       /* Add subdivision point */
 121       v.point = c->p4; v.flags = 0;
 122       if (cindex == 0) return; /* Skip last point */
 123       if (!shAddVertex(p, &v, contourStart)) return;
 124       --cindex;
 125
 126     }else{
 127
 128       /* Left recursion goes on top of stack! */
 129       cright = c; cleft = &cubics[++cindex];
 130
 131       /* Subdivide into 2 sub-curves */
 132       SET2V(c1, c->p1); ADD2V(c1, c->p2); DIV2(c1, 2);
 133       SET2V(mm, c->p2); ADD2V(mm, c->p3); DIV2(mm, 2);
 134       SET2V(c5, c->p3); ADD2V(c5, c->p4); DIV2(c5, 2);
 135
 136       SET2V(c2, c1); ADD2V(c2, mm); DIV2(c2, 2);
 137       SET2V(c4, mm); ADD2V(c4, c5); DIV2(c4, 2);
 138
 139       SET2V(c3, c2); ADD2V(c3, c4); DIV2(c3, 2);
 140
 141       /* Add left recursion to stack */
 142       cleft->p1 = c->p1;
 143       cleft->p2 = c1;
 144       cleft->p3 = c2;
 145       cleft->p4 = c3;
 146
 147       /* Add right recursion to stack */
 148       cright->p1 = c3;
 149       cright->p2 = c4;
 150       cright->p3 = c5;
 151       cright->p4 = c->p4;
 152     }
 153   }
 154 }
 155
 156 static void shSubrecurseArc(SHPath *p, SHArc *arc,
 157                             SHVector2 *c,SHVector2 *ux, SHVector2 *uy,
 158                             SHint *contourStart)
 159 {
 160   SHVertex v;
 161   SHfloat am, cosa, sina, dx, dy;
 162   SHVector2 uux, uuy, c1, m;
 163   SHArc arcs[SH_MAX_RECURSE_DEPTH];
 164   SHArc *a, *aleft, *aright;
 165   SHint aindex=0;
 166   arcs[0] = *arc;
 167
 168   while (aindex >= 0) {
 169
 170     a = &arcs[aindex];
 171
 172     /* Middle angle and its cos/sin */
 173     am = (a->a1 + a->a2)/2;
 174     cosa = SH_COS(am);
 175     sina = SH_SIN(am);
 176
 177     /* New point */
 178     SET2V(uux, (*ux)); MUL2(uux, cosa);
 179     SET2V(uuy, (*uy)); MUL2(uuy, sina);
 180     SET2V(c1, (*c)); ADD2V(c1, uux); ADD2V(c1, uuy);
 181
 182     /* Check distance from linear midpoint */
 183     SET2V(m, a->p1); ADD2V(m, a->p2); DIV2(m, 2);
 184     dx = c1.x - m.x; dy = c1.y - m.y;
 185     if (dx < 0.0f) dx = -dx;
 186     if (dy < 0.0f) dy = -dy;
 187
 188     /* Stop if flat enough */
 189     if (dx+dy <= 1.0f || aindex == SH_MAX_RECURSE_DEPTH-1) {
 190
 191       /* Add middle subdivision point */
 192       v.point = c1; v.flags = 0;
 193       if (!shAddVertex(p, &v, contourStart)) return;
 194       if (aindex == 0) return; /* Skip very last point */
 195
 196       /* Add end subdivision point */
 197       v.point = a->p2; v.flags = 0;
 198       if (!shAddVertex(p, &v, contourStart)) return;
 199       --aindex;
 200
 201     }else{
 202
 203       /* Left subdivision goes on top of stack! */
 204       aright = a; aleft = &arcs[++aindex];
 205
 206       /* Add left recursion to stack */
 207       aleft->p1 = a->p1;
 208       aleft->a1 = a->a1;
 209       aleft->p2 = c1;
 210       aleft->a2 = am;
 211
 212       /* Add right recursion to stack */
 213       aright->p1 = c1;
 214       aright->a1 = am;
 215       aright->p2 = a->p2;
 216       aright->a2 = a->a2;
 217     }
 218   }
 219 }
 220
 221 static void shSubdivideSegment(SHPath *p, VGPathSegment segment,
 222                                VGPathCommand originalCommand,
 223                                SHfloat *data, void *userData)
 224 {
 225   SHVertex v;
 226   SHint *contourStart = ((SHint**)userData)[0];
 227   SHint *surfaceSpace = ((SHint**)userData)[1];
 228   SHQuad quad; SHCubic cubic; SHArc arc;
 229   SHVector2 c, ux, uy;
 230   VG_GETCONTEXT(VG_NO_RETVAL);
 231
 232   switch (segment)
 233   {
 234   case VG_MOVE_TO:
 235
 236     /* Set contour start here */
 237     (*contourStart) = p->vertices.size;
 238
 239     /* First contour vertex */
 240     v.point.x = data[2];
 241     v.point.y = data[3];
 242     v.flags = 0;
 243     if (*surfaceSpace)
 244       TRANSFORM2(v.point, context->pathTransform);
 245     break;
 246
 247   case VG_CLOSE_PATH:
 248
 249     /* Last contour vertex */
 250     v.point.x = data[2];
 251     v.point.y = data[3];
 252     v.flags = SH_VERTEX_FLAG_SEGEND | SH_VERTEX_FLAG_CLOSE;
 253     if (*surfaceSpace)
 254       TRANSFORM2(v.point, context->pathTransform);
 255     break;
 256
 257   case VG_LINE_TO:
 258
 259     /* Last segment vertex */
 260     v.point.x = data[2];
 261     v.point.y = data[3];
 262     v.flags = SH_VERTEX_FLAG_SEGEND;
 263     if (*surfaceSpace)
 264       TRANSFORM2(v.point, context->pathTransform);
 265     break;
 266
 267   case VG_QUAD_TO:
 268
 269     /* Recurse subdivision */
 270     SET2(quad.p1, data[0], data[1]);
 271     SET2(quad.p2, data[2], data[3]);
 272     SET2(quad.p3, data[4], data[5]);
 273     if (*surfaceSpace) {
 274       TRANSFORM2(quad.p1, context->pathTransform);
 275       TRANSFORM2(quad.p2, context->pathTransform);
 276       TRANSFORM2(quad.p3, context->pathTransform); }
 277     shSubrecurseQuad(p, &quad, contourStart);
 278
 279     /* Last segment vertex */
 280     v.point.x = data[4];
 281     v.point.y = data[5];
 282     v.flags = SH_VERTEX_FLAG_SEGEND;
 283     if (*surfaceSpace)
 284       TRANSFORM2(v.point, context->pathTransform);
 285     break;
 286
 287   case VG_CUBIC_TO:
 288
 289     /* Recurse subdivision */
 290     SET2(cubic.p1, data[0], data[1]);
 291     SET2(cubic.p2, data[2], data[3]);
 292     SET2(cubic.p3, data[4], data[5]);
 293     SET2(cubic.p4, data[6], data[7]);
 294     if (*surfaceSpace) {
 295       TRANSFORM2(cubic.p1, context->pathTransform);
 296       TRANSFORM2(cubic.p2, context->pathTransform);
 297       TRANSFORM2(cubic.p3, context->pathTransform);
 298       TRANSFORM2(cubic.p4, context->pathTransform); }
 299     shSubrecurseCubic(p, &cubic, contourStart);
 300
 301     /* Last segment vertex */
 302     v.point.x = data[6];
 303     v.point.y = data[7];
 304     v.flags = SH_VERTEX_FLAG_SEGEND;
 305     if (*surfaceSpace)
 306       TRANSFORM2(v.point, context->pathTransform);
 307     break;
 308
 309   default:
 310
 311     SH_ASSERT(segment==VG_SCWARC_TO || segment==VG_SCCWARC_TO ||
 312               segment==VG_LCWARC_TO || segment==VG_LCCWARC_TO);
 313
 314     /* Recurse subdivision */
 315     SET2(arc.p1, data[0], data[1]);
 316     SET2(arc.p2, data[10], data[11]);
 317     arc.a1 = data[8]; arc.a2 = data[9];
 318     SET2(c,  data[2], data[3]);
 319     SET2(ux, data[4], data[5]);
 320     SET2(uy, data[6], data[7]);
 321     if (*surfaceSpace) {
 322       TRANSFORM2(arc.p1, context->pathTransform);
 323       TRANSFORM2(arc.p2, context->pathTransform);
 324       TRANSFORM2(c, context->pathTransform);
 325       TRANSFORM2DIR(ux, context->pathTransform);
 326       TRANSFORM2DIR(uy, context->pathTransform); }
 327     shSubrecurseArc(p, &arc, &c, &ux, &uy, contourStart);
 328
 329     /* Last segment vertex */
 330     v.point.x = data[10];
 331     v.point.y = data[11];
 332     v.flags = SH_VERTEX_FLAG_SEGEND;
 333     if (*surfaceSpace) {
 334       TRANSFORM2(v.point, context->pathTransform); }
 335     break;
 336   }
 337
 338   /* Add subdivision vertex */
 339   shAddVertex(p, &v, contourStart);
 340 }
 341
 342 /*--------------------------------------------------
 343  * Processes path data by simplfying it and sending
 344  * each segment to subdivision callback function
 345  *--------------------------------------------------*/
 346
 347 void shFlattenPath(SHPath *p, SHint surfaceSpace)
 348 {
 349   SHint contourStart = -1;
 350 //  SHint surfSpace = surfaceSpace;
 351   SHint *userData[2];
 352   SHint processFlags =
 353     SH_PROCESS_SIMPLIFY_LINES |
 354     SH_PROCESS_SIMPLIFY_CURVES |
 355     SH_PROCESS_CENTRALIZE_ARCS |
 356     SH_PROCESS_REPAIR_ENDS;
 357
 358   userData[0] = &contourStart;
 359   userData[1] = &surfaceSpace;
 360
 361   shVertexArrayClear(&p->vertices);
 362   shProcessPathData(p, processFlags, shSubdivideSegment, userData);
 363 }
 364
 365 /*-------------------------------------------
 366  * Adds a rectangle to the path's stroke.
 367  *-------------------------------------------*/
 368
 369 static void shPushStrokeQuad(SHPath *p, SHVector2 *p1, SHVector2 *p2,
 370                              SHVector2 *p3, SHVector2 *p4)
 371 {
 372   shVector2ArrayPushBackP(&p->stroke, p1);
 373   shVector2ArrayPushBackP(&p->stroke, p2);
 374   shVector2ArrayPushBackP(&p->stroke, p3);
 375   shVector2ArrayPushBackP(&p->stroke, p3);
 376   shVector2ArrayPushBackP(&p->stroke, p4);
 377   shVector2ArrayPushBackP(&p->stroke, p1);
 378 }
 379
 380 /*-------------------------------------------
 381  * Adds a triangle to the path's stroke.
 382  *-------------------------------------------*/
 383
 384 static void shPushStrokeTri(SHPath *p, SHVector2 *p1,
 385                             SHVector2 *p2, SHVector2 *p3)
 386 {
 387   shVector2ArrayPushBackP(&p->stroke, p1);
 388   shVector2ArrayPushBackP(&p->stroke, p2);
 389   shVector2ArrayPushBackP(&p->stroke, p3);
 390 }
 391
 392 /*-----------------------------------------------------------
 393  * Adds a miter join to the path's stroke at the given
 394  * turn point [c], with the end of the previous segment
 395  * outset [o1] and the beginning of the next segment
 396  * outset [o2], transiting from tangent [d1] to [d2].
 397  *-----------------------------------------------------------*/
 398
 399 static void shStrokeJoinMiter(SHPath *p, SHVector2 *c,
 400                               SHVector2 *o1, SHVector2 *d1,
 401                               SHVector2 *o2, SHVector2 *d2)
 402 {
 403   /* Init miter top to first point in case lines are colinear */
 404   SHVector2 x; SET2V(x,(*o1));
 405
 406   /* Find intersection of two outer turn edges
 407      (lines defined by origin and direction) */
 408   shLineLineXsection(o1, d1, o2, d2, &x);
 409
 410   /* Add a "diamond" quad with top on intersected point
 411      and bottom on center of turn (on the line) */
 412   shPushStrokeQuad(p, &x, o1, c, o2);
 413 }
 414
 415 /*-----------------------------------------------------------
 416  * Adds a round join to the path's stroke at the given
 417  * turn point [c], with the end of the previous segment
 418  * outset [pstart] and the beginning of the next segment
 419  * outset [pend], transiting from perpendicular vector
 420  * [tstart] to [tend].
 421  *-----------------------------------------------------------*/
 422
 423 static void shStrokeJoinRound(SHPath *p, SHVector2 *c,
 424                               SHVector2 *pstart, SHVector2 *tstart,
 425                               SHVector2 *pend, SHVector2 *tend)
 426 {
 427   SHVector2 p1, p2;
 428   SHfloat a, ang, cosa, sina;
 429
 430   /* Find angle between lines */
 431   ang = ANGLE2((*tstart),(*tend));
 432
 433   /* Begin with start point */
 434   SET2V(p1,(*pstart));
 435   for (a=0.0f; a<ang; a+=PI/12) {
 436
 437     /* Rotate perpendicular vector around and
 438        find next offset point from center */
 439     cosa = SH_COS(-a);
 440     sina = SH_SIN(-a);
 441     SET2(p2, tstart->x*cosa - tstart->y*sina,
 442          tstart->x*sina + tstart->y*cosa);
 443     ADD2V(p2, (*c));
 444
 445     /* Add triangle, save previous */
 446     shPushStrokeTri(p, &p1, &p2, c);
 447     SET2V(p1, p2);
 448   }
 449
 450   /* Add last triangle */
 451   shPushStrokeTri(p, &p1, pend, c);
 452 }
 453
 454 static void shStrokeCapRound(SHPath *p, SHVector2 *c, SHVector2 *t, SHint start)
 455 {
 456   SHint a;
 457   SHfloat ang, cosa, sina;
 458   SHVector2 p1, p2;
 459   SHint steps = 12;
 460   SHVector2 tt;
 461
 462   /* Revert perpendicular vector if start cap */
 463   SET2V(tt, (*t));
 464   if (start) MUL2(tt, -1);
 465
 466   /* Find start point */
 467   SET2V(p1, (*c));
 468   ADD2V(p1, tt);
 469
 470   for (a = 1; a<=steps; ++a) {
 471
 472     /* Rotate perpendicular vector around and
 473        find next offset point from center */
 474     ang = (SHfloat)a * PI / steps;
 475     cosa = SH_COS(-ang);
 476     sina = SH_SIN(-ang);
 477     SET2(p2, tt.x*cosa - tt.y*sina,
 478          tt.x*sina + tt.y*cosa);
 479     ADD2V(p2, (*c));
 480
 481     /* Add triangle, save previous */
 482     shPushStrokeTri(p, &p1, &p2, c);
 483     SET2V(p1, p2);
 484   }
 485 }
 486
 487 static void shStrokeCapSquare(SHPath *p, SHVector2 *c, SHVector2 *t, SHint start)
 488 {
 489   SHVector2 tt, p1, p2, p3, p4;
 490
 491   /* Revert perpendicular vector if start cap */
 492   SET2V(tt, (*t));
 493   if (start) MUL2(tt, -1);
 494
 495   /* Find four corners of the quad */
 496   SET2V(p1, (*c));
 497   ADD2V(p1, tt);
 498
 499   SET2V(p2, p1);
 500   ADD2(p2, tt.y, -tt.x);
 501
 502   SET2V(p3, p2);
 503   ADD2(p3, -2*tt.x, -2*tt.y);
 504
 505   SET2V(p4, p3);
 506   ADD2(p4, -tt.y, tt.x);
 507
 508   shPushStrokeQuad(p, &p1, &p2, &p3, &p4);
 509 }
 510
 511 /*-----------------------------------------------------------
 512  * Generates stroke of a path according to VGContext state.
 513  * Produces quads for every linear subdivision segment or
 514  * dash "on" segment, handles line caps and joins.
 515  *-----------------------------------------------------------*/
 516
 517 void shStrokePath(VGContext* c, SHPath *p)
 518 {
 519   /* Line width and vertex count */
 520   SHfloat w = c->strokeLineWidth / 2;
 521   SHfloat mlimit = c->strokeMiterLimit;
 522   SHint vertsize = p->vertices.size;
 523
 524   /* Contour state */
 525   SHint contourStart = 0;
 526   SHint contourLength = 0;
 527   SHint start = 0;
 528   SHint end = 0;
 529   SHint loop = 0;
 530   SHint close = 0;
 531   SHint segend = 0;
 532
 533   /* Current vertices */
 534   SHint i1=0, i2=0;
 535   SHVertex *v1, *v2;
 536   SHVector2 *p1, *p2;
 537   SHVector2 d, t, dprev, tprev;
 538   SHfloat norm, cross, mlength;
 539
 540   /* Stroke edge points */
 541   SHVector2 l1, r1, l2, r2, lprev, rprev;
 542
 543   /* Dash state */
 544   SHint dashIndex = 0;
 545   SHfloat dashLength = 0.0f, strokeLength = 0.0f;
 546   SHint dashSize = c->strokeDashPattern.size;
 547   SHfloat *dashPattern = c->strokeDashPattern.items;
 548   SHint dashOn = 1;
 549
 550   /* Dash edge points */
 551   SHVector2 dash1, dash2;
 552   SHVector2 dashL1, dashR1;
 553   SHVector2 dashL2, dashR2;
 554   SHfloat nextDashLength, dashOffset;
 555
 556   /* Discard odd dash segment */
 557   dashSize -= dashSize % 2;
 558
 559   /* Init previous so compiler doesn't warn
 560      for uninitialized usage */
 561   SET2(tprev, 0,0); SET2(dprev, 0,0);
 562   SET2(lprev, 0,0); SET2(rprev, 0,0);
 563
 564
 565   /* Walk over subdivision vertices */
 566   for (i1=0; i1<vertsize; ++i1) {
 567
 568     if (loop) {
 569       /* Start new contour if exists */
 570       if (contourStart < vertsize)
 571         i1 = contourStart;
 572       else break;
 573     }
 574
 575     start = end = loop = close = segend = 0;
 576     i2 = i1 + 1;
 577
 578     if (i1 == contourStart) {
 579       /* Contour has started. Get length */
 580       contourLength = p->vertices.items[i1].flags;
 581       start = 1;
 582     }
 583
 584     if (contourLength <= 1) {
 585       /* Discard empty contours. */
 586       contourStart = i1 + 1;
 587       loop = 1;
 588       continue;
 589     }
 590
 591     v1 = &p->vertices.items[i1];
 592     v2 = &p->vertices.items[i2];
 593
 594     if (i2 == contourStart + contourLength-1) {
 595       /* Contour has ended. Check close */
 596       close = v2->flags & SH_VERTEX_FLAG_CLOSE;
 597       end = 1;
 598     }
 599
 600     if (i1 == contourStart + contourLength-1) {
 601       /* Loop back to first edge. Check close */
 602       close = v1->flags & SH_VERTEX_FLAG_CLOSE;
 603       i2 = contourStart+1;
 604       contourStart = i1 + 1;
 605       i1 = i2 - 1;
 606       loop = 1;
 607     }
 608
 609     if (!start && !loop) {
 610       /* We are inside a contour. Check segment end. */
 611       segend = (v1->flags & SH_VERTEX_FLAG_SEGEND);
 612     }
 613
 614     if (dashSize > 0 && start &&
 615         (contourStart == 0 || c->strokeDashPhaseReset)) {
 616
 617       /* Reset pattern phase at contour start */
 618       dashLength = -c->strokeDashPhase;
 619       strokeLength = 0.0f;
 620       dashIndex = 0;
 621       dashOn = 1;
 622
 623       if (dashLength < 0.0f) {
 624         /* Consume dash segments forward to reach stroke start */
 625         while (dashLength + dashPattern[dashIndex] <= 0.0f) {
 626           dashLength += dashPattern[dashIndex];
 627           dashIndex = (dashIndex + 1) % dashSize;
 628           dashOn = !dashOn; }
 629
 630       }else if (dashLength > 0.0f) {
 631         /* Consume dash segments backward to return to stroke start */
 632         dashIndex = dashSize;
 633         while (dashLength > 0.0f) {
 634           dashIndex = dashIndex ? (dashIndex-1) : (dashSize-1);
 635           dashLength -= dashPattern[dashIndex];
 636           dashOn = !dashOn; }
 637       }
 638     }
 639
 640     /* Subdiv segment vertices and points */
 641     v1 = &p->vertices.items[i1];
 642     v2 = &p->vertices.items[i2];
 643     p1 = &v1->point;
 644     p2 = &v2->point;
 645
 646     /* Direction vector */
 647     SET2(d, p2->x-p1->x, p2->y-p1->y);
 648     norm = NORM2(d);
 649     if (norm == 0.0f) d = dprev;
 650     else DIV2(d, norm);
 651
 652     /* Perpendicular vector */
 653     SET2(t, -d.y, d.x);
 654     MUL2(t, w);
 655     cross = CROSS2(t,tprev);
 656
 657     /* Left and right edge points */
 658     SET2V(l1, (*p1)); ADD2V(l1, t);
 659     SET2V(r1, (*p1)); SUB2V(r1, t);
 660     SET2V(l2, (*p2)); ADD2V(l2, t);
 661     SET2V(r2, (*p2)); SUB2V(r2, t);
 662
 663     /* Check if join needed */
 664     if ((segend || (loop && close)) && dashOn) {
 665
 666       switch (c->strokeJoinStyle) {
 667       case VG_JOIN_ROUND:
 668
 669         /* Add a round join to stroke */
 670         if (cross >= 0.0f)
 671           shStrokeJoinRound(p, p1, &lprev, &tprev, &l1, &t);
 672         else{
 673           SHVector2 _t, _tprev;
 674           SET2(_t, -t.x, -t.y);
 675           SET2(_tprev, -tprev.x, -tprev.y);
 676           shStrokeJoinRound(p, p1,  &r1, &_t, &rprev, &_tprev);
 677         }
 678
 679         break;
 680       case VG_JOIN_MITER:
 681
 682         /* Add a miter join to stroke */
 683         mlength = 1/SH_COS((ANGLE2(t, tprev))/2);
 684         if (mlength <= mlimit) {
 685           if (cross > 0.0f)
 686             shStrokeJoinMiter(p, p1, &lprev, &dprev, &l1, &d);
 687           else if (cross < 0.0f)
 688             shStrokeJoinMiter(p, p1, &rprev, &dprev, &r1, &d);
 689           break;
 690         }/* Else fall down to bevel */
 691
 692       case VG_JOIN_BEVEL:
 693
 694         /* Add a bevel join to stroke */
 695         if (cross > 0.0f)
 696           shPushStrokeTri(p, &l1, &lprev, p1);
 697         else if (cross < 0.0f)
 698           shPushStrokeTri(p, &r1, &rprev, p1);
 699
 700         break;
 701       }
 702     }else if (!start && !loop && dashOn) {
 703
 704       /* Fill gap with previous (= bevel join) */
 705       if (cross > 0.0f)
 706         shPushStrokeTri(p, &l1, &lprev, p1);
 707       else if (cross < 0.0f)
 708         shPushStrokeTri(p, &r1, &rprev, p1);
 709     }
 710
 711
 712     /* Apply cap to start of a non-closed contour or
 713        if we are dashing and dash segment is on */
 714     if ((dashSize == 0 && loop && !close) ||
 715         (dashSize > 0 && start && dashOn)) {
 716       switch (c->strokeCapStyle) {
 717       case VG_CAP_ROUND:
 718         shStrokeCapRound(p, p1, &t, 1); break;
 719       case VG_CAP_SQUARE:
 720         shStrokeCapSquare(p, p1, &t, 1); break;
 721       default: break;
 722       }
 723     }
 724
 725     if (loop)
 726       continue;
 727
 728     /* Handle dashing */
 729     if (dashSize > 0) {
 730
 731       /* Start with beginning of subdiv segment */
 732       SET2V(dash1, (*p1)); SET2V(dashL1, l1); SET2V(dashR1, r1);
 733
 734       do {
 735         /* Interpolate point on the current subdiv segment */
 736         nextDashLength = dashLength + dashPattern[dashIndex];
 737         dashOffset = (nextDashLength - strokeLength) / norm;
 738         if (dashOffset > 1.0f) dashOffset = 1;
 739         SET2V(dash2, (*p2)); SUB2V(dash2, (*p1));
 740         MUL2(dash2, dashOffset); ADD2V(dash2, (*p1));
 741
 742         /* Left and right edge points */
 743         SET2V(dashL2, dash2); ADD2V(dashL2, t);
 744         SET2V(dashR2, dash2); SUB2V(dashR2, t);
 745
 746         /* Add quad for this dash segment */
 747         if (dashOn) shPushStrokeQuad(p, &dashL2, &dashL1, &dashR1, &dashR2);
 748
 749         /* Move to next dash segment if inside this subdiv segment */
 750         if (nextDashLength <= strokeLength + norm) {
 751           dashIndex = (dashIndex + 1) % dashSize;
 752           dashLength = nextDashLength;
 753           dashOn = !dashOn;
 754           SET2V(dash1, dash2);
 755           SET2V(dashL1, dashL2);
 756           SET2V(dashR1, dashR2);
 757
 758           /* Apply cap to dash segment */
 759           switch (c->strokeCapStyle) {
 760           case VG_CAP_ROUND:
 761             shStrokeCapRound(p, &dash1, &t, dashOn); break;
 762           case VG_CAP_SQUARE:
 763             shStrokeCapSquare(p, &dash1, &t, dashOn); break;
 764           default: break;
 765           }
 766         }
 767
 768         /* Consume dash segments until subdiv end met */
 769       } while (nextDashLength < strokeLength + norm);
 770
 771     }else{
 772
 773       /* Add quad for this line segment */
 774       shPushStrokeQuad(p, &l2, &l1, &r1, &r2);
 775     }
 776
 777
 778     /* Apply cap to end of a non-closed contour or
 779        if we are dashing and dash segment is on */
 780     if ((dashSize == 0 && end && !close) ||
 781         (dashSize > 0 && end && dashOn)) {
 782       switch (c->strokeCapStyle) {
 783       case VG_CAP_ROUND:
 784         shStrokeCapRound(p, p2, &t, 0); break;
 785       case VG_CAP_SQUARE:
 786         shStrokeCapSquare(p, p2, &t, 0); break;
 787       default: break;
 788       }
 789     }
 790
 791     /* Save previous edge */
 792     strokeLength += norm;
 793     SET2V(lprev, l2);
 794     SET2V(rprev, r2);
 795     dprev = d;
 796     tprev = t;
 797   }
 798 }
 799
 800
 801 /*-------------------------------------------------------------
 802  * Transforms the tessellation vertices using the given matrix
 803  *-------------------------------------------------------------*/
 804
 805 void shTransformVertices(SHMatrix3x3 *m, SHPath *p)
 806 {
 807   SHVector2 *v;
 808   int i = 0;
 809
 810   for (i = p->vertices.size-1; i>=0; --i) {
 811     v = (&p->vertices.items[i].point);
 812     TRANSFORM2((*v), (*m)); }
 813 }
 814
 815 /*--------------------------------------------------------
 816  * Finds the tight bounding box of path's tesselation
 817  * vertices. Depends on whether the path had been
 818  * tesselated in user or surface space.
 819  *--------------------------------------------------------*/
 820
 821 void shFindBoundbox(SHPath *p)
 822 {
 823   int i;
 824
 825   if (p->vertices.size == 0) {
 826     SET2(p->min, 0,0);
 827     SET2(p->max, 0,0);
 828     return;
 829   }
 830
 831   p->min.x = p->max.x = p->vertices.items[0].point.x;
 832   p->min.y = p->max.y = p->vertices.items[0].point.y;
 833
 834   for (i=0; i<p->vertices.size; ++i) {
 835
 836     SHVector2 *v = &p->vertices.items[i].point;
 837     if (v->x < p->min.x) p->min.x = v->x;
 838     if (v->x > p->max.x) p->max.x = v->x;
 839     if (v->y < p->min.y) p->min.y = v->y;
 840     if (v->y > p->max.y) p->max.y = v->y;
 841   }
 842 }
 843
 844 /*--------------------------------------------------------
 845  * Outputs a tight bounding box of a path in path's own
 846  * coordinate system.
 847  *--------------------------------------------------------*/
 848
 849 VG_API_CALL void vgPathBounds(VGPath path,
 850                               VGfloat * minX, VGfloat * minY,
 851                               VGfloat * width, VGfloat * height)
 852 {
 853   SHPath *p = NULL;
 854   VG_GETCONTEXT(VG_NO_RETVAL);
 855
 856   VG_RETURN_ERR_IF(!shIsValidPath(context, path),
 857                    VG_BAD_HANDLE_ERROR, VG_NO_RETVAL);
 858
 859   VG_RETURN_ERR_IF(minX == NULL || minY == NULL ||
 860                    width == NULL || height == NULL,
 861                    VG_ILLEGAL_ARGUMENT_ERROR, VG_NO_RETVAL);
 862
 863   /* TODO: check output pointer alignment */
 864
 865   p = (SHPath*)path;
 866   VG_RETURN_ERR_IF(!(p->caps & VG_PATH_CAPABILITY_PATH_BOUNDS),
 867                    VG_PATH_CAPABILITY_ERROR, VG_NO_RETVAL);
 868
 869   /* Update path geometry */
 870   shFlattenPath(p, 0);
 871   shFindBoundbox(p);
 872
 873   /* Output bounds */
 874   *minX = p->min.x;
 875   *minY = p->min.y;
 876   *width = p->max.x - p->min.x;
 877   *height = p->max.y - p->min.y;
 878
 879   VG_RETURN(VG_NO_RETVAL);
 880 }
 881
 882 /*------------------------------------------------------------
 883  * Outputs a bounding box of a path defined by its control
 884  * points that is guaranteed to enclose the path geometry
 885  * after applying the current path-user-to-surface transform
 886  *------------------------------------------------------------*/
 887
 888 VG_API_CALL void vgPathTransformedBounds(VGPath path,
 889                                          VGfloat * minX, VGfloat * minY,
 890                                          VGfloat * width, VGfloat * height)
 891 {
 892   SHPath *p = NULL;
 893   VG_GETCONTEXT(VG_NO_RETVAL);
 894
 895   VG_RETURN_ERR_IF(!shIsValidPath(context, path),
 896                    VG_BAD_HANDLE_ERROR, VG_NO_RETVAL);
 897
 898   VG_RETURN_ERR_IF(minX == NULL || minY == NULL ||
 899                    width == NULL || height == NULL,
 900                    VG_ILLEGAL_ARGUMENT_ERROR, VG_NO_RETVAL);
 901
 902   /* TODO: check output pointer alignment */
 903
 904   p = (SHPath*)path;
 905   VG_RETURN_ERR_IF(!(p->caps & VG_PATH_CAPABILITY_PATH_BOUNDS),
 906                    VG_PATH_CAPABILITY_ERROR, VG_NO_RETVAL);
 907
 908   /* Update path geometry */
 909   shFlattenPath(p, 1);
 910   shFindBoundbox(p);
 911
 912   /* Output bounds */
 913   *minX = p->min.x;
 914   *minY = p->min.y;
 915   *width = p->max.x - p->min.x;
 916   *height = p->max.y - p->min.y;
 917
 918   /* Invalidate subdivision for rendering */
 919   p->cacheDataValid = VG_FALSE;
 920
 921   VG_RETURN(VG_NO_RETVAL);
 922 }
 923
 924 VG_API_CALL VGfloat vgPathLength(VGPath path,
 925                                  VGint startSegment, VGint numSegments)
 926 {
 927   return 0.0f;
 928 }
 929
 930 VG_API_CALL void vgPointAlongPath(VGPath path,
 931                                   VGint startSegment, VGint numSegments,
 932                                   VGfloat distance,
 933                                   VGfloat * x, VGfloat * y,
 934                                   VGfloat * tangentX, VGfloat * tangentY)
 935 {
 936 }