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