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