dali-toolkit/internal/controls/renderers/svg/nanosvg/nanosvgrast.cc

   1 /*
   2  * Copyright (c) 2013-14 Mikko Mononen memon@inside.org
   3  *
   4  * This software is provided 'as-is', without any express or implied
   5  * warranty.  In no event will the authors be held liable for any damages
   6  * arising from the use of this software.
   7  *
   8  * Permission is granted to anyone to use this software for any purpose,
   9  * including commercial applications, and to alter it and redistribute it
  10  * freely, subject to the following restrictions:
  11  *
  12  * 1. The origin of this software must not be misrepresented; you must not
  13  * claim that you wrote the original software. If you use this software
  14  * in a product, an acknowledgment in the product documentation would be
  15  * appreciated but is not required.
  16  * 2. Altered source versions must be plainly marked as such, and must not be
  17  * misrepresented as being the original software.
  18  * 3. This notice may not be removed or altered from any source distribution.
  19  *
  20  * The polygon rasterization is heavily based on stb_truetype rasterizer
  21  * by Sean Barrett - http://nothings.org/
  22  *
  23  */
  24
  25 #include "nanosvgrast.h"
  26
  27 /**
  28  * In the original software, The nanosvgrast implementation was included in the header file.
  29  * We have separated the implementation to source file here.
  30  */
  31
  32 #include <stdio.h>
  33 #include <string.h>
  34 #include <stdlib.h>
  35 #include <math.h>
  36
  37 #define NSVG__SUBSAMPLES    5
  38 #define NSVG__FIXSHIFT      10
  39 #define NSVG__FIX           (1 << NSVG__FIXSHIFT)
  40 #define NSVG__FIXMASK       (NSVG__FIX-1)
  41 #define NSVG__MEMPAGE_SIZE  1024
  42
  43 typedef struct NSVGedge {
  44     float x0,y0, x1,y1;
  45     int dir;
  46     struct NSVGedge* next;
  47 } NSVGedge;
  48
  49 typedef struct NSVGpoint {
  50     float x, y;
  51     float dx, dy;
  52     float len;
  53     float dmx, dmy;
  54     unsigned char flags;
  55 } NSVGpoint;
  56
  57 typedef struct NSVGactiveEdge {
  58     int x,dx;
  59     float ey;
  60     int dir;
  61     struct NSVGactiveEdge *next;
  62 } NSVGactiveEdge;
  63
  64 typedef struct NSVGmemPage {
  65     unsigned char mem[NSVG__MEMPAGE_SIZE];
  66     int size;
  67     struct NSVGmemPage* next;
  68 } NSVGmemPage;
  69
  70 typedef struct NSVGcachedPaint {
  71     char type;
  72     char spread;
  73     float xform[6];
  74     unsigned int colors[256];
  75 } NSVGcachedPaint;
  76
  77 struct NSVGrasterizer
  78 {
  79     float px, py;
  80
  81     float tessTol;
  82     float distTol;
  83
  84     NSVGedge* edges;
  85     int nedges;
  86     int cedges;
  87
  88     NSVGpoint* points;
  89     int npoints;
  90     int cpoints;
  91
  92     NSVGpoint* points2;
  93     int npoints2;
  94     int cpoints2;
  95
  96     NSVGactiveEdge* freelist;
  97     NSVGmemPage* pages;
  98     NSVGmemPage* curpage;
  99
 100     unsigned char* scanline;
 101     int cscanline;
 102
 103     unsigned char* bitmap;
 104     int width, height, stride;
 105 };
 106
 107 NSVGrasterizer* nsvgCreateRasterizer()
 108 {
 109     NSVGrasterizer* r = (NSVGrasterizer*)malloc(sizeof(NSVGrasterizer));
 110     if (r == NULL) goto error;
 111     memset(r, 0, sizeof(NSVGrasterizer));
 112
 113     r->tessTol = 0.25f;
 114     r->distTol = 0.01f;
 115
 116     return r;
 117
 118 error:
 119     nsvgDeleteRasterizer(r);
 120     return NULL;
 121 }
 122
 123 void nsvgDeleteRasterizer(NSVGrasterizer* r)
 124 {
 125     if (r == NULL) return;
 126
 127     NSVGmemPage* p;
 128     p = r->pages;
 129     while (p != NULL) {
 130         NSVGmemPage* next = p->next;
 131         free(p);
 132         p = next;
 133     }
 134
 135     if (r->edges) free(r->edges);
 136     if (r->points) free(r->points);
 137     if (r->points2) free(r->points2);
 138     if (r->scanline) free(r->scanline);
 139
 140     free(r);
 141 }
 142
 143 static NSVGmemPage* nsvg__nextPage(NSVGrasterizer* r, NSVGmemPage* cur)
 144 {
 145     NSVGmemPage *newp;
 146
 147     // If using existing chain, return the next page in chain
 148     if (cur != NULL && cur->next != NULL) {
 149         return cur->next;
 150     }
 151
 152     // Alloc new page
 153     newp = (NSVGmemPage*)malloc(sizeof(NSVGmemPage));
 154     if (newp == NULL) return NULL;
 155     memset(newp, 0, sizeof(NSVGmemPage));
 156
 157     // Add to linked list
 158     if (cur != NULL)
 159         cur->next = newp;
 160     else
 161         r->pages = newp;
 162
 163     return newp;
 164 }
 165
 166 static void nsvg__resetPool(NSVGrasterizer* r)
 167 {
 168     NSVGmemPage* p = r->pages;
 169     while (p != NULL) {
 170         p->size = 0;
 171         p = p->next;
 172     }
 173     r->curpage = r->pages;
 174 }
 175
 176 static unsigned char* nsvg__alloc(NSVGrasterizer* r, int size)
 177 {
 178     unsigned char* buf;
 179     if (size > NSVG__MEMPAGE_SIZE) return NULL;
 180     if (r->curpage == NULL || r->curpage->size+size > NSVG__MEMPAGE_SIZE) {
 181         r->curpage = nsvg__nextPage(r, r->curpage);
 182     }
 183     buf = &r->curpage->mem[r->curpage->size];
 184     r->curpage->size += size;
 185     return buf;
 186 }
 187
 188 static int nsvg__ptEquals(float x1, float y1, float x2, float y2, float tol)
 189 {
 190     float dx = x2 - x1;
 191     float dy = y2 - y1;
 192     return dx*dx + dy*dy < tol*tol;
 193 }
 194
 195 static void nsvg__addPathPoint(NSVGrasterizer* r, float x, float y, int flags)
 196 {
 197     NSVGpoint* pt;
 198
 199     if (r->npoints > 0) {
 200         pt = &r->points[r->npoints-1];
 201         if (nsvg__ptEquals(pt->x,pt->y, x,y, r->distTol)) {
 202             pt->flags |= flags;
 203             return;
 204         }
 205     }
 206
 207     if (r->npoints+1 > r->cpoints) {
 208         r->cpoints = r->cpoints > 0 ? r->cpoints * 2 : 64;
 209         r->points = (NSVGpoint*)realloc(r->points, sizeof(NSVGpoint) * r->cpoints);
 210         if (r->points == NULL) return;
 211     }
 212
 213     pt = &r->points[r->npoints];
 214     pt->x = x;
 215     pt->y = y;
 216     pt->flags = (unsigned char)flags;
 217     r->npoints++;
 218 }
 219
 220 static void nsvg__appendPathPoint(NSVGrasterizer* r, NSVGpoint pt)
 221 {
 222     if (r->npoints+1 > r->cpoints) {
 223         r->cpoints = r->cpoints > 0 ? r->cpoints * 2 : 64;
 224         r->points = (NSVGpoint*)realloc(r->points, sizeof(NSVGpoint) * r->cpoints);
 225         if (r->points == NULL) return;
 226     }
 227     r->points[r->npoints] = pt;
 228     r->npoints++;
 229 }
 230
 231 static void nsvg__duplicatePoints(NSVGrasterizer* r)
 232 {
 233     if (r->npoints > r->cpoints2) {
 234         r->cpoints2 = r->npoints;
 235         r->points2 = (NSVGpoint*)realloc(r->points2, sizeof(NSVGpoint) * r->cpoints2);
 236         if (r->points2 == NULL) return;
 237     }
 238
 239     memcpy(r->points2, r->points, sizeof(NSVGpoint) * r->npoints);
 240     r->npoints2 = r->npoints;
 241 }
 242
 243 static void nsvg__addEdge(NSVGrasterizer* r, float x0, float y0, float x1, float y1)
 244 {
 245     NSVGedge* e;
 246
 247     // Skip horizontal edges
 248     if (y0 == y1)
 249         return;
 250
 251     if (r->nedges+1 > r->cedges) {
 252         r->cedges = r->cedges > 0 ? r->cedges * 2 : 64;
 253         r->edges = (NSVGedge*)realloc(r->edges, sizeof(NSVGedge) * r->cedges);
 254         if (r->edges == NULL) return;
 255     }
 256
 257     e = &r->edges[r->nedges];
 258     r->nedges++;
 259
 260     if (y0 < y1) {
 261         e->x0 = x0;
 262         e->y0 = y0;
 263         e->x1 = x1;
 264         e->y1 = y1;
 265         e->dir = 1;
 266     } else {
 267         e->x0 = x1;
 268         e->y0 = y1;
 269         e->x1 = x0;
 270         e->y1 = y0;
 271         e->dir = -1;
 272     }
 273 }
 274
 275 static float nsvg__normalize(float *x, float* y)
 276 {
 277     float d = sqrtf((*x)*(*x) + (*y)*(*y));
 278     if (d > 1e-6f) {
 279         float id = 1.0f / d;
 280         *x *= id;
 281         *y *= id;
 282     }
 283     return d;
 284 }
 285
 286 static float nsvg__absf(float x) { return x < 0 ? -x : x; }
 287
 288 static void nsvg__flattenCubicBez(NSVGrasterizer* r,
 289                                   float x1, float y1, float x2, float y2,
 290                                   float x3, float y3, float x4, float y4,
 291                                   int level, int type)
 292 {
 293     float x12,y12,x23,y23,x34,y34,x123,y123,x234,y234,x1234,y1234;
 294     float dx,dy,d2,d3;
 295
 296     if (level > 10) return;
 297
 298     x12 = (x1+x2)*0.5f;
 299     y12 = (y1+y2)*0.5f;
 300     x23 = (x2+x3)*0.5f;
 301     y23 = (y2+y3)*0.5f;
 302     x34 = (x3+x4)*0.5f;
 303     y34 = (y3+y4)*0.5f;
 304     x123 = (x12+x23)*0.5f;
 305     y123 = (y12+y23)*0.5f;
 306
 307     dx = x4 - x1;
 308     dy = y4 - y1;
 309     d2 = nsvg__absf(((x2 - x4) * dy - (y2 - y4) * dx));
 310     d3 = nsvg__absf(((x3 - x4) * dy - (y3 - y4) * dx));
 311
 312     if ((d2 + d3)*(d2 + d3) < r->tessTol * (dx*dx + dy*dy)) {
 313         nsvg__addPathPoint(r, x4, y4, type);
 314         return;
 315     }
 316
 317     x234 = (x23+x34)*0.5f;
 318     y234 = (y23+y34)*0.5f;
 319     x1234 = (x123+x234)*0.5f;
 320     y1234 = (y123+y234)*0.5f;
 321
 322     nsvg__flattenCubicBez(r, x1,y1, x12,y12, x123,y123, x1234,y1234, level+1, 0);
 323     nsvg__flattenCubicBez(r, x1234,y1234, x234,y234, x34,y34, x4,y4, level+1, type);
 324 }
 325
 326 static void nsvg__flattenShape(NSVGrasterizer* r, NSVGshape* shape, float scale)
 327 {
 328     int i, j;
 329     NSVGpath* path;
 330
 331     for (path = shape->paths; path != NULL; path = path->next) {
 332         r->npoints = 0;
 333         // Flatten path
 334         nsvg__addPathPoint(r, path->pts[0]*scale, path->pts[1]*scale, 0);
 335         for (i = 0; i < path->npts-1; i += 3) {
 336             float* p = &path->pts[i*2];
 337             nsvg__flattenCubicBez(r, p[0]*scale,p[1]*scale, p[2]*scale,p[3]*scale, p[4]*scale,p[5]*scale, p[6]*scale,p[7]*scale, 0, 0);
 338         }
 339         // Close path
 340         nsvg__addPathPoint(r, path->pts[0]*scale, path->pts[1]*scale, 0);
 341         // Build edges
 342         for (i = 0, j = r->npoints-1; i < r->npoints; j = i++)
 343             nsvg__addEdge(r, r->points[j].x, r->points[j].y, r->points[i].x, r->points[i].y);
 344     }
 345 }
 346
 347 enum NSVGpointFlags
 348 {
 349     NSVG_PT_CORNER = 0x01,
 350     NSVG_PT_BEVEL = 0x02,
 351     NSVG_PT_LEFT = 0x04,
 352 };
 353
 354 static void nsvg__initClosed(NSVGpoint* left, NSVGpoint* right, NSVGpoint* p0, NSVGpoint* p1, float lineWidth)
 355 {
 356     float w = lineWidth * 0.5f;
 357     float dx = p1->x - p0->x;
 358     float dy = p1->y - p0->y;
 359     float len = nsvg__normalize(&dx, &dy);
 360     float px = p0->x + dx*len*0.5f, py = p0->y + dy*len*0.5f;
 361     float dlx = dy, dly = -dx;
 362     float lx = px - dlx*w, ly = py - dly*w;
 363     float rx = px + dlx*w, ry = py + dly*w;
 364     left->x = lx; left->y = ly;
 365     right->x = rx; right->y = ry;
 366 }
 367
 368 static void nsvg__buttCap(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p, float dx, float dy, float lineWidth, int connect)
 369 {
 370     float w = lineWidth * 0.5f;
 371     float px = p->x, py = p->y;
 372     float dlx = dy, dly = -dx;
 373     float lx = px - dlx*w, ly = py - dly*w;
 374     float rx = px + dlx*w, ry = py + dly*w;
 375
 376     nsvg__addEdge(r, lx, ly, rx, ry);
 377
 378     if (connect) {
 379         nsvg__addEdge(r, left->x, left->y, lx, ly);
 380         nsvg__addEdge(r, rx, ry, right->x, right->y);
 381     }
 382     left->x = lx; left->y = ly;
 383     right->x = rx; right->y = ry;
 384 }
 385
 386 static void nsvg__squareCap(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p, float dx, float dy, float lineWidth, int connect)
 387 {
 388     float w = lineWidth * 0.5f;
 389     float px = p->x - dx*w, py = p->y - dy*w;
 390     float dlx = dy, dly = -dx;
 391     float lx = px - dlx*w, ly = py - dly*w;
 392     float rx = px + dlx*w, ry = py + dly*w;
 393
 394     nsvg__addEdge(r, lx, ly, rx, ry);
 395
 396     if (connect) {
 397         nsvg__addEdge(r, left->x, left->y, lx, ly);
 398         nsvg__addEdge(r, rx, ry, right->x, right->y);
 399     }
 400     left->x = lx; left->y = ly;
 401     right->x = rx; right->y = ry;
 402 }
 403
 404 #ifndef NSVG_PI
 405 #define NSVG_PI (3.14159265358979323846264338327f)
 406 #endif
 407
 408 static void nsvg__roundCap(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p, float dx, float dy, float lineWidth, int ncap, int connect)
 409 {
 410     int i;
 411     float w = lineWidth * 0.5f;
 412     float px = p->x, py = p->y;
 413     float dlx = dy, dly = -dx;
 414     float lx = 0, ly = 0, rx = 0, ry = 0, prevx = 0, prevy = 0;
 415
 416     for (i = 0; i < ncap; i++) {
 417         float a = i/(float)(ncap-1)*NSVG_PI;
 418         float ax = cosf(a) * w, ay = sinf(a) * w;
 419         float x = px - dlx*ax - dx*ay;
 420         float y = py - dly*ax - dy*ay;
 421
 422         if (i > 0)
 423             nsvg__addEdge(r, prevx, prevy, x, y);
 424
 425         prevx = x;
 426         prevy = y;
 427
 428         if (i == 0) {
 429             lx = x; ly = y;
 430         } else if (i == ncap-1) {
 431             rx = x; ry = y;
 432         }
 433     }
 434
 435     if (connect) {
 436         nsvg__addEdge(r, left->x, left->y, lx, ly);
 437         nsvg__addEdge(r, rx, ry, right->x, right->y);
 438     }
 439
 440     left->x = lx; left->y = ly;
 441     right->x = rx; right->y = ry;
 442 }
 443
 444 static void nsvg__bevelJoin(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p0, NSVGpoint* p1, float lineWidth)
 445 {
 446     float w = lineWidth * 0.5f;
 447     float dlx0 = p0->dy, dly0 = -p0->dx;
 448     float dlx1 = p1->dy, dly1 = -p1->dx;
 449     float lx0 = p1->x - (dlx0 * w), ly0 = p1->y - (dly0 * w);
 450     float rx0 = p1->x + (dlx0 * w), ry0 = p1->y + (dly0 * w);
 451     float lx1 = p1->x - (dlx1 * w), ly1 = p1->y - (dly1 * w);
 452     float rx1 = p1->x + (dlx1 * w), ry1 = p1->y + (dly1 * w);
 453
 454     nsvg__addEdge(r, lx0, ly0, left->x, left->y);
 455     nsvg__addEdge(r, lx1, ly1, lx0, ly0);
 456
 457     nsvg__addEdge(r, right->x, right->y, rx0, ry0);
 458     nsvg__addEdge(r, rx0, ry0, rx1, ry1);
 459
 460     left->x = lx1; left->y = ly1;
 461     right->x = rx1; right->y = ry1;
 462 }
 463
 464 static void nsvg__miterJoin(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p0, NSVGpoint* p1, float lineWidth)
 465 {
 466     float w = lineWidth * 0.5f;
 467     float dlx0 = p0->dy, dly0 = -p0->dx;
 468     float dlx1 = p1->dy, dly1 = -p1->dx;
 469     float lx0, rx0, lx1, rx1;
 470     float ly0, ry0, ly1, ry1;
 471
 472     if (p1->flags & NSVG_PT_LEFT) {
 473         lx0 = lx1 = p1->x - p1->dmx * w;
 474         ly0 = ly1 = p1->y - p1->dmy * w;
 475         nsvg__addEdge(r, lx1, ly1, left->x, left->y);
 476
 477         rx0 = p1->x + (dlx0 * w);
 478         ry0 = p1->y + (dly0 * w);
 479         rx1 = p1->x + (dlx1 * w);
 480         ry1 = p1->y + (dly1 * w);
 481         nsvg__addEdge(r, right->x, right->y, rx0, ry0);
 482         nsvg__addEdge(r, rx0, ry0, rx1, ry1);
 483     } else {
 484         lx0 = p1->x - (dlx0 * w);
 485         ly0 = p1->y - (dly0 * w);
 486         lx1 = p1->x - (dlx1 * w);
 487         ly1 = p1->y - (dly1 * w);
 488         nsvg__addEdge(r, lx0, ly0, left->x, left->y);
 489         nsvg__addEdge(r, lx1, ly1, lx0, ly0);
 490
 491         rx0 = rx1 = p1->x + p1->dmx * w;
 492         ry0 = ry1 = p1->y + p1->dmy * w;
 493         nsvg__addEdge(r, right->x, right->y, rx1, ry1);
 494     }
 495
 496     left->x = lx1; left->y = ly1;
 497     right->x = rx1; right->y = ry1;
 498 }
 499
 500 static void nsvg__roundJoin(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p0, NSVGpoint* p1, float lineWidth, int ncap)
 501 {
 502     int i, n;
 503     float w = lineWidth * 0.5f;
 504     float dlx0 = p0->dy, dly0 = -p0->dx;
 505     float dlx1 = p1->dy, dly1 = -p1->dx;
 506     float a0 = atan2f(dly0, dlx0);
 507     float a1 = atan2f(dly1, dlx1);
 508     float da = a1 - a0;
 509     float lx, ly, rx, ry;
 510
 511     if (da < NSVG_PI) da += NSVG_PI*2;
 512     if (da > NSVG_PI) da -= NSVG_PI*2;
 513
 514     n = (int)ceilf((nsvg__absf(da) / NSVG_PI) * ncap);
 515     if (n < 2) n = 2;
 516     if (n > ncap) n = ncap;
 517
 518     lx = left->x;
 519     ly = left->y;
 520     rx = right->x;
 521     ry = right->y;
 522
 523     for (i = 0; i < n; i++) {
 524         float u = i/(float)(n-1);
 525         float a = a0 + u*da;
 526         float ax = cosf(a) * w, ay = sinf(a) * w;
 527         float lx1 = p1->x - ax, ly1 = p1->y - ay;
 528         float rx1 = p1->x + ax, ry1 = p1->y + ay;
 529
 530         nsvg__addEdge(r, lx1, ly1, lx, ly);
 531         nsvg__addEdge(r, rx, ry, rx1, ry1);
 532
 533         lx = lx1; ly = ly1;
 534         rx = rx1; ry = ry1;
 535     }
 536
 537     left->x = lx; left->y = ly;
 538     right->x = rx; right->y = ry;
 539 }
 540
 541 static void nsvg__straightJoin(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p1, float lineWidth)
 542 {
 543     float w = lineWidth * 0.5f;
 544     float lx = p1->x - (p1->dmx * w), ly = p1->y - (p1->dmy * w);
 545     float rx = p1->x + (p1->dmx * w), ry = p1->y + (p1->dmy * w);
 546
 547     nsvg__addEdge(r, lx, ly, left->x, left->y);
 548     nsvg__addEdge(r, right->x, right->y, rx, ry);
 549
 550     left->x = lx; left->y = ly;
 551     right->x = rx; right->y = ry;
 552 }
 553
 554 static int nsvg__curveDivs(float r, float arc, float tol)
 555 {
 556     float da = acosf(r / (r + tol)) * 2.0f;
 557     int divs = (int)ceilf(arc / da);
 558     if (divs < 2) divs = 2;
 559     return divs;
 560 }
 561
 562 static void nsvg__expandStroke(NSVGrasterizer* r, NSVGpoint* points, int npoints, int closed, int lineJoin, int lineCap, float lineWidth)
 563 {
 564     int ncap = nsvg__curveDivs(lineWidth*0.5f, NSVG_PI, r->tessTol);    // Calculate divisions per half circle.
 565     NSVGpoint left = {0,0,0,0,0,0,0,0}, right = {0,0,0,0,0,0,0,0}, firstLeft = {0,0,0,0,0,0,0,0}, firstRight = {0,0,0,0,0,0,0,0};
 566     NSVGpoint* p0, *p1;
 567     int j, s, e;
 568
 569     // Build stroke edges
 570     if (closed) {
 571         // Looping
 572         p0 = &points[npoints-1];
 573         p1 = &points[0];
 574         s = 0;
 575         e = npoints;
 576     } else {
 577         // Add cap
 578         p0 = &points[0];
 579         p1 = &points[1];
 580         s = 1;
 581         e = npoints-1;
 582     }
 583
 584     if (closed) {
 585         nsvg__initClosed(&left, &right, p0, p1, lineWidth);
 586         firstLeft = left;
 587         firstRight = right;
 588     } else {
 589         // Add cap
 590         float dx = p1->x - p0->x;
 591         float dy = p1->y - p0->y;
 592         nsvg__normalize(&dx, &dy);
 593         if (lineCap == NSVG_CAP_BUTT)
 594             nsvg__buttCap(r, &left, &right, p0, dx, dy, lineWidth, 0);
 595         else if (lineCap == NSVG_CAP_SQUARE)
 596             nsvg__squareCap(r, &left, &right, p0, dx, dy, lineWidth, 0);
 597         else if (lineCap == NSVG_CAP_ROUND)
 598             nsvg__roundCap(r, &left, &right, p0, dx, dy, lineWidth, ncap, 0);
 599     }
 600
 601     for (j = s; j < e; ++j) {
 602         if (p1->flags & NSVG_PT_CORNER) {
 603             if (lineJoin == NSVG_JOIN_ROUND)
 604                 nsvg__roundJoin(r, &left, &right, p0, p1, lineWidth, ncap);
 605             else if (lineJoin == NSVG_JOIN_BEVEL || (p1->flags & NSVG_PT_BEVEL))
 606                 nsvg__bevelJoin(r, &left, &right, p0, p1, lineWidth);
 607             else
 608                 nsvg__miterJoin(r, &left, &right, p0, p1, lineWidth);
 609         } else {
 610             nsvg__straightJoin(r, &left, &right, p1, lineWidth);
 611         }
 612         p0 = p1++;
 613     }
 614
 615     if (closed) {
 616         // Loop it
 617         nsvg__addEdge(r, firstLeft.x, firstLeft.y, left.x, left.y);
 618         nsvg__addEdge(r, right.x, right.y, firstRight.x, firstRight.y);
 619     } else {
 620         // Add cap
 621         float dx = p1->x - p0->x;
 622         float dy = p1->y - p0->y;
 623         nsvg__normalize(&dx, &dy);
 624         if (lineCap == NSVG_CAP_BUTT)
 625             nsvg__buttCap(r, &right, &left, p1, -dx, -dy, lineWidth, 1);
 626         else if (lineCap == NSVG_CAP_SQUARE)
 627             nsvg__squareCap(r, &right, &left, p1, -dx, -dy, lineWidth, 1);
 628         else if (lineCap == NSVG_CAP_ROUND)
 629             nsvg__roundCap(r, &right, &left, p1, -dx, -dy, lineWidth, ncap, 1);
 630     }
 631 }
 632
 633 static void nsvg__prepareStroke(NSVGrasterizer* r, float miterLimit, int lineJoin)
 634 {
 635     int i, j;
 636     NSVGpoint* p0, *p1;
 637
 638     p0 = &r->points[r->npoints-1];
 639     p1 = &r->points[0];
 640     for (i = 0; i < r->npoints; i++) {
 641         // Calculate segment direction and length
 642         p0->dx = p1->x - p0->x;
 643         p0->dy = p1->y - p0->y;
 644         p0->len = nsvg__normalize(&p0->dx, &p0->dy);
 645         // Advance
 646         p0 = p1++;
 647     }
 648
 649     // calculate joins
 650     p0 = &r->points[r->npoints-1];
 651     p1 = &r->points[0];
 652     for (j = 0; j < r->npoints; j++) {
 653         float dlx0, dly0, dlx1, dly1, dmr2, cross;
 654         dlx0 = p0->dy;
 655         dly0 = -p0->dx;
 656         dlx1 = p1->dy;
 657         dly1 = -p1->dx;
 658         // Calculate extrusions
 659         p1->dmx = (dlx0 + dlx1) * 0.5f;
 660         p1->dmy = (dly0 + dly1) * 0.5f;
 661         dmr2 = p1->dmx*p1->dmx + p1->dmy*p1->dmy;
 662         if (dmr2 > 0.000001f) {
 663             float s2 = 1.0f / dmr2;
 664             if (s2 > 600.0f) {
 665                 s2 = 600.0f;
 666             }
 667             p1->dmx *= s2;
 668             p1->dmy *= s2;
 669         }
 670
 671         // Clear flags, but keep the corner.
 672         p1->flags = (p1->flags & NSVG_PT_CORNER) ? NSVG_PT_CORNER : 0;
 673
 674         // Keep track of left turns.
 675         cross = p1->dx * p0->dy - p0->dx * p1->dy;
 676         if (cross > 0.0f)
 677             p1->flags |= NSVG_PT_LEFT;
 678
 679         // Check to see if the corner needs to be beveled.
 680         if (p1->flags & NSVG_PT_CORNER) {
 681             if ((dmr2 * miterLimit*miterLimit) < 1.0f || lineJoin == NSVG_JOIN_BEVEL || lineJoin == NSVG_JOIN_ROUND) {
 682                 p1->flags |= NSVG_PT_BEVEL;
 683             }
 684         }
 685
 686         p0 = p1++;
 687     }
 688 }
 689
 690 static void nsvg__flattenShapeStroke(NSVGrasterizer* r, NSVGshape* shape, float scale)
 691 {
 692     int i, j, closed;
 693     NSVGpath* path;
 694     NSVGpoint* p0, *p1;
 695     float miterLimit = 4;
 696     int lineJoin = shape->strokeLineJoin;
 697     int lineCap = shape->strokeLineCap;
 698     float lineWidth = shape->strokeWidth * scale;
 699
 700     for (path = shape->paths; path != NULL; path = path->next) {
 701         // Flatten path
 702         r->npoints = 0;
 703         nsvg__addPathPoint(r, path->pts[0]*scale, path->pts[1]*scale, NSVG_PT_CORNER);
 704         for (i = 0; i < path->npts-1; i += 3) {
 705             float* p = &path->pts[i*2];
 706             nsvg__flattenCubicBez(r, p[0]*scale,p[1]*scale, p[2]*scale,p[3]*scale, p[4]*scale,p[5]*scale, p[6]*scale,p[7]*scale, 0, NSVG_PT_CORNER);
 707         }
 708         if (r->npoints < 2)
 709             continue;
 710
 711         closed = path->closed;
 712
 713         // If the first and last points are the same, remove the last, mark as closed path.
 714         p0 = &r->points[r->npoints-1];
 715         p1 = &r->points[0];
 716         if (nsvg__ptEquals(p0->x,p0->y, p1->x,p1->y, r->distTol)) {
 717             r->npoints--;
 718             p0 = &r->points[r->npoints-1];
 719             closed = 1;
 720         }
 721
 722         if (shape->strokeDashCount > 0) {
 723             int idash = 0, dashState = 1;
 724             float totalDist = 0, dashLen, allDashLen, dashOffset;
 725             NSVGpoint cur;
 726
 727             if (closed)
 728                 nsvg__appendPathPoint(r, r->points[0]);
 729
 730             // Duplicate points -> points2.
 731             nsvg__duplicatePoints(r);
 732
 733             r->npoints = 0;
 734             cur = r->points2[0];
 735             nsvg__appendPathPoint(r, cur);
 736
 737             // Figure out dash offset.
 738             allDashLen = 0;
 739             for (j = 0; j < shape->strokeDashCount; j++)
 740                 allDashLen += shape->strokeDashArray[j];
 741             if (shape->strokeDashCount & 1)
 742                 allDashLen *= 2.0f;
 743             // Find location inside pattern
 744             dashOffset = fmodf(shape->strokeDashOffset, allDashLen);
 745             if (dashOffset < 0.0f)
 746                 dashOffset += allDashLen;
 747
 748             while (dashOffset > shape->strokeDashArray[idash]) {
 749                 dashOffset -= shape->strokeDashArray[idash];
 750                 idash = (idash + 1) % shape->strokeDashCount;
 751             }
 752             dashLen = (shape->strokeDashArray[idash] - dashOffset) * scale;
 753
 754             for (j = 1; j < r->npoints2; ) {
 755                 float dx = r->points2[j].x - cur.x;
 756                 float dy = r->points2[j].y - cur.y;
 757                 float dist = sqrtf(dx*dx + dy*dy);
 758
 759                 if ((totalDist + dist) > dashLen) {
 760                     // Calculate intermediate point
 761                     float d = (dashLen - totalDist) / dist;
 762                     float x = cur.x + dx * d;
 763                     float y = cur.y + dy * d;
 764                     nsvg__addPathPoint(r, x, y, NSVG_PT_CORNER);
 765
 766                     // Stroke
 767                     if (r->npoints > 1 && dashState) {
 768                         nsvg__prepareStroke(r, miterLimit, lineJoin);
 769                         nsvg__expandStroke(r, r->points, r->npoints, 0, lineJoin, lineCap, lineWidth);
 770                     }
 771                     // Advance dash pattern
 772                     dashState = !dashState;
 773                     idash = (idash+1) % shape->strokeDashCount;
 774                     dashLen = shape->strokeDashArray[idash] * scale;
 775                     // Restart
 776                     cur.x = x;
 777                     cur.y = y;
 778                     cur.flags = NSVG_PT_CORNER;
 779                     totalDist = 0.0f;
 780                     r->npoints = 0;
 781                     nsvg__appendPathPoint(r, cur);
 782                 } else {
 783                     totalDist += dist;
 784                     cur = r->points2[j];
 785                     nsvg__appendPathPoint(r, cur);
 786                     j++;
 787                 }
 788             }
 789             // Stroke any leftover path
 790             if (r->npoints > 1 && dashState)
 791                 nsvg__expandStroke(r, r->points, r->npoints, 0, lineJoin, lineCap, lineWidth);
 792         } else {
 793             nsvg__prepareStroke(r, miterLimit, lineJoin);
 794             nsvg__expandStroke(r, r->points, r->npoints, closed, lineJoin, lineCap, lineWidth);
 795         }
 796     }
 797 }
 798
 799 static int nsvg__cmpEdge(const void *p, const void *q)
 800 {
 801     NSVGedge* a = (NSVGedge*)p;
 802     NSVGedge* b = (NSVGedge*)q;
 803
 804     if (a->y0 < b->y0) return -1;
 805     if (a->y0 > b->y0) return  1;
 806     return 0;
 807 }
 808
 809
 810 static NSVGactiveEdge* nsvg__addActive(NSVGrasterizer* r, NSVGedge* e, float startPoint)
 811 {
 812      NSVGactiveEdge* z;
 813
 814     if (r->freelist != NULL) {
 815         // Restore from freelist.
 816         z = r->freelist;
 817         r->freelist = z->next;
 818     } else {
 819         // Alloc new edge.
 820         z = (NSVGactiveEdge*)nsvg__alloc(r, sizeof(NSVGactiveEdge));
 821         if (z == NULL) return NULL;
 822     }
 823
 824     float dxdy = (e->x1 - e->x0) / (e->y1 - e->y0);
 825 //  STBTT_assert(e->y0 <= start_point);
 826     // round dx down to avoid going too far
 827     if (dxdy < 0)
 828         z->dx = (int)(-floorf(NSVG__FIX * -dxdy));
 829     else
 830         z->dx = (int)floorf(NSVG__FIX * dxdy);
 831     z->x = (int)floorf(NSVG__FIX * (e->x0 + dxdy * (startPoint - e->y0)));
 832 //  z->x -= off_x * FIX;
 833     z->ey = e->y1;
 834     z->next = 0;
 835     z->dir = e->dir;
 836
 837     return z;
 838 }
 839
 840 static void nsvg__freeActive(NSVGrasterizer* r, NSVGactiveEdge* z)
 841 {
 842     z->next = r->freelist;
 843     r->freelist = z;
 844 }
 845
 846 static void nsvg__fillScanline(unsigned char* scanline, int len, int x0, int x1, int maxWeight, int* xmin, int* xmax)
 847 {
 848     int i = x0 >> NSVG__FIXSHIFT;
 849     int j = x1 >> NSVG__FIXSHIFT;
 850     if (i < *xmin) *xmin = i;
 851     if (j > *xmax) *xmax = j;
 852     if (i < len && j >= 0) {
 853         if (i == j) {
 854             // x0,x1 are the same pixel, so compute combined coverage
 855             scanline[i] += (unsigned char)((x1 - x0) * maxWeight >> NSVG__FIXSHIFT);
 856         } else {
 857             if (i >= 0) // add antialiasing for x0
 858                 scanline[i] += (unsigned char)(((NSVG__FIX - (x0 & NSVG__FIXMASK)) * maxWeight) >> NSVG__FIXSHIFT);
 859             else
 860                 i = -1; // clip
 861
 862             if (j < len) // add antialiasing for x1
 863                 scanline[j] += (unsigned char)(((x1 & NSVG__FIXMASK) * maxWeight) >> NSVG__FIXSHIFT);
 864             else
 865                 j = len; // clip
 866
 867             for (++i; i < j; ++i) // fill pixels between x0 and x1
 868                 scanline[i] += (unsigned char)maxWeight;
 869         }
 870     }
 871 }
 872
 873 // note: this routine clips fills that extend off the edges... ideally this
 874 // wouldn't happen, but it could happen if the truetype glyph bounding boxes
 875 // are wrong, or if the user supplies a too-small bitmap
 876 static void nsvg__fillActiveEdges(unsigned char* scanline, int len, NSVGactiveEdge* e, int maxWeight, int* xmin, int* xmax, char fillRule)
 877 {
 878     // non-zero winding fill
 879     int x0 = 0, w = 0;
 880
 881     if (fillRule == NSVG_FILLRULE_NONZERO) {
 882         // Non-zero
 883         while (e != NULL) {
 884             if (w == 0) {
 885                 // if we're currently at zero, we need to record the edge start point
 886                 x0 = e->x; w += e->dir;
 887             } else {
 888                 int x1 = e->x; w += e->dir;
 889                 // if we went to zero, we need to draw
 890                 if (w == 0)
 891                     nsvg__fillScanline(scanline, len, x0, x1, maxWeight, xmin, xmax);
 892             }
 893             e = e->next;
 894         }
 895     } else if (fillRule == NSVG_FILLRULE_EVENODD) {
 896         // Even-odd
 897         while (e != NULL) {
 898             if (w == 0) {
 899                 // if we're currently at zero, we need to record the edge start point
 900                 x0 = e->x; w = 1;
 901             } else {
 902                 int x1 = e->x; w = 0;
 903                 nsvg__fillScanline(scanline, len, x0, x1, maxWeight, xmin, xmax);
 904             }
 905             e = e->next;
 906         }
 907     }
 908 }
 909
 910 static float nsvg__clampf(float a, float mn, float mx) { return a < mn ? mn : (a > mx ? mx : a); }
 911
 912 static unsigned int nsvg__RGBA(unsigned char r, unsigned char g, unsigned char b, unsigned char a)
 913 {
 914     return (r) | (g << 8) | (b << 16) | (a << 24);
 915 }
 916
 917 static unsigned int nsvg__lerpRGBA(unsigned int c0, unsigned int c1, float u)
 918 {
 919     int iu = (int)(nsvg__clampf(u, 0.0f, 1.0f) * 256.0f);
 920     int r = (((c0) & 0xff)*(256-iu) + (((c1) & 0xff)*iu)) >> 8;
 921     int g = (((c0>>8) & 0xff)*(256-iu) + (((c1>>8) & 0xff)*iu)) >> 8;
 922     int b = (((c0>>16) & 0xff)*(256-iu) + (((c1>>16) & 0xff)*iu)) >> 8;
 923     int a = (((c0>>24) & 0xff)*(256-iu) + (((c1>>24) & 0xff)*iu)) >> 8;
 924     return nsvg__RGBA((unsigned char)r, (unsigned char)g, (unsigned char)b, (unsigned char)a);
 925 }
 926
 927 static unsigned int nsvg__applyOpacity(unsigned int c, float u)
 928 {
 929     int iu = (int)(nsvg__clampf(u, 0.0f, 1.0f) * 256.0f);
 930     int r = (c) & 0xff;
 931     int g = (c>>8) & 0xff;
 932     int b = (c>>16) & 0xff;
 933     int a = (((c>>24) & 0xff)*iu) >> 8;
 934     return nsvg__RGBA((unsigned char)r, (unsigned char)g, (unsigned char)b, (unsigned char)a);
 935 }
 936
 937 static inline int nsvg__div255(int x)
 938 {
 939     return ((x+1) * 257) >> 16;
 940 }
 941
 942 static void nsvg__scanlineSolid(unsigned char* dst, int count, unsigned char* cover, int x, int y,
 943                                 float tx, float ty, float scale, NSVGcachedPaint* cache)
 944 {
 945
 946     if (cache->type == NSVG_PAINT_COLOR) {
 947         int i, cr, cg, cb, ca;
 948         cr = cache->colors[0] & 0xff;
 949         cg = (cache->colors[0] >> 8) & 0xff;
 950         cb = (cache->colors[0] >> 16) & 0xff;
 951         ca = (cache->colors[0] >> 24) & 0xff;
 952
 953         for (i = 0; i < count; i++) {
 954             int r,g,b;
 955             int a = nsvg__div255((int)cover[0] * ca);
 956             int ia = 255 - a;
 957             // Premultiply
 958             r = nsvg__div255(cr * a);
 959             g = nsvg__div255(cg * a);
 960             b = nsvg__div255(cb * a);
 961
 962             // Blend over
 963             r += nsvg__div255(ia * (int)dst[0]);
 964             g += nsvg__div255(ia * (int)dst[1]);
 965             b += nsvg__div255(ia * (int)dst[2]);
 966             a += nsvg__div255(ia * (int)dst[3]);
 967
 968             dst[0] = (unsigned char)r;
 969             dst[1] = (unsigned char)g;
 970             dst[2] = (unsigned char)b;
 971             dst[3] = (unsigned char)a;
 972
 973             cover++;
 974             dst += 4;
 975         }
 976     } else if (cache->type == NSVG_PAINT_LINEAR_GRADIENT) {
 977         // TODO: spread modes.
 978         // TODO: plenty of opportunities to optimize.
 979         float fx, fy, dx, gy;
 980         float* t = cache->xform;
 981         int i, cr, cg, cb, ca;
 982         unsigned int c;
 983
 984         fx = (x - tx) / scale;
 985         fy = (y - ty) / scale;
 986         dx = 1.0f / scale;
 987
 988         for (i = 0; i < count; i++) {
 989             int r,g,b,a,ia;
 990             gy = fx*t[1] + fy*t[3] + t[5];
 991             c = cache->colors[(int)nsvg__clampf(gy*255.0f, 0, 255.0f)];
 992             cr = (c) & 0xff;
 993             cg = (c >> 8) & 0xff;
 994             cb = (c >> 16) & 0xff;
 995             ca = (c >> 24) & 0xff;
 996
 997             a = nsvg__div255((int)cover[0] * ca);
 998             ia = 255 - a;
 999
1000             // Premultiply
1001             r = nsvg__div255(cr * a);
1002             g = nsvg__div255(cg * a);
1003             b = nsvg__div255(cb * a);
1004
1005             // Blend over
1006             r += nsvg__div255(ia * (int)dst[0]);
1007             g += nsvg__div255(ia * (int)dst[1]);
1008             b += nsvg__div255(ia * (int)dst[2]);
1009             a += nsvg__div255(ia * (int)dst[3]);
1010
1011             dst[0] = (unsigned char)r;
1012             dst[1] = (unsigned char)g;
1013             dst[2] = (unsigned char)b;
1014             dst[3] = (unsigned char)a;
1015
1016             cover++;
1017             dst += 4;
1018             fx += dx;
1019         }
1020     } else if (cache->type == NSVG_PAINT_RADIAL_GRADIENT) {
1021         // TODO: spread modes.
1022         // TODO: plenty of opportunities to optimize.
1023         // TODO: focus (fx,fy)
1024         float fx, fy, dx, gx, gy, gd;
1025         float* t = cache->xform;
1026         int i, cr, cg, cb, ca;
1027         unsigned int c;
1028
1029         fx = (x - tx) / scale;
1030         fy = (y - ty) / scale;
1031         dx = 1.0f / scale;
1032
1033         for (i = 0; i < count; i++) {
1034             int r,g,b,a,ia;
1035             gx = fx*t[0] + fy*t[2] + t[4];
1036             gy = fx*t[1] + fy*t[3] + t[5];
1037             gd = sqrtf(gx*gx + gy*gy);
1038             c = cache->colors[(int)nsvg__clampf(gd*255.0f, 0, 255.0f)];
1039             cr = (c) & 0xff;
1040             cg = (c >> 8) & 0xff;
1041             cb = (c >> 16) & 0xff;
1042             ca = (c >> 24) & 0xff;
1043
1044             a = nsvg__div255((int)cover[0] * ca);
1045             ia = 255 - a;
1046
1047             // Premultiply
1048             r = nsvg__div255(cr * a);
1049             g = nsvg__div255(cg * a);
1050             b = nsvg__div255(cb * a);
1051
1052             // Blend over
1053             r += nsvg__div255(ia * (int)dst[0]);
1054             g += nsvg__div255(ia * (int)dst[1]);
1055             b += nsvg__div255(ia * (int)dst[2]);
1056             a += nsvg__div255(ia * (int)dst[3]);
1057
1058             dst[0] = (unsigned char)r;
1059             dst[1] = (unsigned char)g;
1060             dst[2] = (unsigned char)b;
1061             dst[3] = (unsigned char)a;
1062
1063             cover++;
1064             dst += 4;
1065             fx += dx;
1066         }
1067     }
1068 }
1069
1070 static void nsvg__rasterizeSortedEdges(NSVGrasterizer *r, float tx, float ty, float scale, NSVGcachedPaint* cache, char fillRule)
1071 {
1072     NSVGactiveEdge *active = NULL;
1073     int y, s;
1074     int e = 0;
1075     int maxWeight = (255 / NSVG__SUBSAMPLES);  // weight per vertical scanline
1076     int xmin, xmax;
1077
1078     for (y = 0; y < r->height; y++) {
1079         memset(r->scanline, 0, r->width);
1080         xmin = r->width;
1081         xmax = 0;
1082         for (s = 0; s < NSVG__SUBSAMPLES; ++s) {
1083             // find center of pixel for this scanline
1084             float scany = y*NSVG__SUBSAMPLES + s + 0.5f;
1085             NSVGactiveEdge **step = &active;
1086
1087             // update all active edges;
1088             // remove all active edges that terminate before the center of this scanline
1089             while (*step) {
1090                 NSVGactiveEdge *z = *step;
1091                 if (z->ey <= scany) {
1092                     *step = z->next; // delete from list
1093 //                  NSVG__assert(z->valid);
1094                     nsvg__freeActive(r, z);
1095                 } else {
1096                     z->x += z->dx; // advance to position for current scanline
1097                     step = &((*step)->next); // advance through list
1098                 }
1099             }
1100
1101             // resort the list if needed
1102             for (;;) {
1103                 int changed = 0;
1104                 step = &active;
1105                 while (*step && (*step)->next) {
1106                     if ((*step)->x > (*step)->next->x) {
1107                         NSVGactiveEdge* t = *step;
1108                         NSVGactiveEdge* q = t->next;
1109                         t->next = q->next;
1110                         q->next = t;
1111                         *step = q;
1112                         changed = 1;
1113                     }
1114                     step = &(*step)->next;
1115                 }
1116                 if (!changed) break;
1117             }
1118
1119             // insert all edges that start before the center of this scanline -- omit ones that also end on this scanline
1120             while (e < r->nedges && r->edges[e].y0 <= scany) {
1121                 if (r->edges[e].y1 > scany) {
1122                     NSVGactiveEdge* z = nsvg__addActive(r, &r->edges[e], scany);
1123                     if (z == NULL) break;
1124                     // find insertion point
1125                     if (active == NULL) {
1126                         active = z;
1127                     } else if (z->x < active->x) {
1128                         // insert at front
1129                         z->next = active;
1130                         active = z;
1131                     } else {
1132                         // find thing to insert AFTER
1133                         NSVGactiveEdge* p = active;
1134                         while (p->next && p->next->x < z->x)
1135                             p = p->next;
1136                         // at this point, p->next->x is NOT < z->x
1137                         z->next = p->next;
1138                         p->next = z;
1139                     }
1140                 }
1141                 e++;
1142             }
1143
1144             // now process all active edges in non-zero fashion
1145             if (active != NULL)
1146                 nsvg__fillActiveEdges(r->scanline, r->width, active, maxWeight, &xmin, &xmax, fillRule);
1147         }
1148         // Blit
1149         if (xmin < 0) xmin = 0;
1150         if (xmax > r->width-1) xmax = r->width-1;
1151         if (xmin <= xmax) {
1152             nsvg__scanlineSolid(&r->bitmap[y * r->stride] + xmin*4, xmax-xmin+1, &r->scanline[xmin], xmin, y, tx,ty, scale, cache);
1153         }
1154     }
1155
1156 }
1157
1158 /**
1159  * In the original software, an function 'static void nsvg__unpremultiplyAlpha(unsigned char* image, int w, int h, int stride)' is implemented here.
1160  * We removed this function, as our renderer renders the pre-multiplied alpha format directly, so this process is not required.
1161  */
1162
1163
1164 static void nsvg__initPaint(NSVGcachedPaint* cache, NSVGpaint* paint, float opacity)
1165 {
1166     int i, j;
1167     NSVGgradient* grad;
1168
1169     cache->type = paint->type;
1170
1171     if (paint->type == NSVG_PAINT_COLOR) {
1172         cache->colors[0] = nsvg__applyOpacity(paint->color, opacity);
1173         return;
1174     }
1175
1176     grad = paint->gradient;
1177
1178     cache->spread = grad->spread;
1179     memcpy(cache->xform, grad->xform, sizeof(float)*6);
1180
1181     if (grad->nstops == 0) {
1182         for (i = 0; i < 256; i++)
1183             cache->colors[i] = 0;
1184     } if (grad->nstops == 1) {
1185         for (i = 0; i < 256; i++)
1186             cache->colors[i] = nsvg__applyOpacity(grad->stops[i].color, opacity);
1187     } else {
1188         unsigned int ca, cb = 0;
1189         float ua, ub, du, u;
1190         int ia, ib, count;
1191
1192         ca = nsvg__applyOpacity(grad->stops[0].color, opacity);
1193         ua = nsvg__clampf(grad->stops[0].offset, 0, 1);
1194         ub = nsvg__clampf(grad->stops[grad->nstops-1].offset, ua, 1);
1195         ia = (int)(ua * 255.0f);
1196         ib = (int)(ub * 255.0f);
1197         for (i = 0; i < ia; i++) {
1198             cache->colors[i] = ca;
1199         }
1200
1201         for (i = 0; i < grad->nstops-1; i++) {
1202             ca = nsvg__applyOpacity(grad->stops[i].color, opacity);
1203             cb = nsvg__applyOpacity(grad->stops[i+1].color, opacity);
1204             ua = nsvg__clampf(grad->stops[i].offset, 0, 1);
1205             ub = nsvg__clampf(grad->stops[i+1].offset, 0, 1);
1206             ia = (int)(ua * 255.0f);
1207             ib = (int)(ub * 255.0f);
1208             count = ib - ia;
1209             if (count <= 0) continue;
1210             u = 0;
1211             du = 1.0f / (float)count;
1212             for (j = 0; j < count; j++) {
1213                 cache->colors[ia+j] = nsvg__lerpRGBA(ca,cb,u);
1214                 u += du;
1215             }
1216         }
1217
1218         for (i = ib; i < 256; i++)
1219             cache->colors[i] = cb;
1220     }
1221
1222 }
1223
1224 void nsvgRasterize(NSVGrasterizer* r,
1225                    NSVGimage* image, float tx, float ty, float scale,
1226                    unsigned char* dst, int w, int h, int stride)
1227 {
1228     NSVGshape *shape = NULL;
1229     NSVGedge *e = NULL;
1230     NSVGcachedPaint cache;
1231     int i;
1232
1233     r->bitmap = dst;
1234     r->width = w;
1235     r->height = h;
1236     r->stride = stride;
1237
1238     if (w > r->cscanline) {
1239         r->cscanline = w;
1240         r->scanline = (unsigned char*)realloc(r->scanline, w);
1241         if (r->scanline == NULL) return;
1242     }
1243
1244     for (i = 0; i < h; i++)
1245         memset(&dst[i*stride], 0, w*4);
1246
1247     for (shape = image->shapes; shape != NULL; shape = shape->next) {
1248         if (!(shape->flags & NSVG_FLAGS_VISIBLE))
1249             continue;
1250
1251         if (shape->fill.type != NSVG_PAINT_NONE) {
1252             nsvg__resetPool(r);
1253             r->freelist = NULL;
1254             r->nedges = 0;
1255
1256             nsvg__flattenShape(r, shape, scale);
1257
1258             // Scale and translate edges
1259             for (i = 0; i < r->nedges; i++) {
1260                 e = &r->edges[i];
1261                 e->x0 = tx + e->x0;
1262                 e->y0 = (ty + e->y0) * NSVG__SUBSAMPLES;
1263                 e->x1 = tx + e->x1;
1264                 e->y1 = (ty + e->y1) * NSVG__SUBSAMPLES;
1265             }
1266
1267             // Rasterize edges
1268             qsort(r->edges, r->nedges, sizeof(NSVGedge), nsvg__cmpEdge);
1269
1270             // now, traverse the scanlines and find the intersections on each scanline, use non-zero rule
1271             nsvg__initPaint(&cache, &shape->fill, shape->opacity);
1272
1273             nsvg__rasterizeSortedEdges(r, tx,ty,scale, &cache, shape->fillRule);
1274         }
1275         if (shape->stroke.type != NSVG_PAINT_NONE && (shape->strokeWidth * scale) > 0.01f) {
1276             nsvg__resetPool(r);
1277             r->freelist = NULL;
1278             r->nedges = 0;
1279
1280             nsvg__flattenShapeStroke(r, shape, scale);
1281
1282 //          dumpEdges(r, "edge.svg");
1283
1284             // Scale and translate edges
1285             for (i = 0; i < r->nedges; i++) {
1286                 e = &r->edges[i];
1287                 e->x0 = tx + e->x0;
1288                 e->y0 = (ty + e->y0) * NSVG__SUBSAMPLES;
1289                 e->x1 = tx + e->x1;
1290                 e->y1 = (ty + e->y1) * NSVG__SUBSAMPLES;
1291             }
1292
1293             // Rasterize edges
1294             qsort(r->edges, r->nedges, sizeof(NSVGedge), nsvg__cmpEdge);
1295
1296             // now, traverse the scanlines and find the intersections on each scanline, use non-zero rule
1297             nsvg__initPaint(&cache, &shape->stroke, shape->opacity);
1298
1299             nsvg__rasterizeSortedEdges(r, tx,ty,scale, &cache, NSVG_FILLRULE_NONZERO);
1300         }
1301     }
1302
1303     /**
1304      * In the original file, the pre-multiplied alpha format is transformed to the convertional non-pre format.
1305      * We skip this process here, and render the pre-multiplied alpha format directly in our svg renderer.
1306      */
1307
1308     r->bitmap = NULL;
1309     r->width = 0;
1310     r->height = 0;
1311     r->stride = 0;
1312 }