2 * Copyright (c) 2013-14 Mikko Mononen memon@inside.org
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.
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:
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.
20 * The polygon rasterization is heavily based on stb_truetype rasterizer
21 * by Sean Barrett - http://nothings.org/
25 #include "nanosvgrast.h"
28 * In the original software, The nanosvgrast implementation was included in the header file.
29 * We have separated the implementation to source file here.
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
43 typedef struct NSVGedge {
46 struct NSVGedge* next;
49 typedef struct NSVGpoint {
57 typedef struct NSVGactiveEdge {
61 struct NSVGactiveEdge *next;
64 typedef struct NSVGmemPage {
65 unsigned char mem[NSVG__MEMPAGE_SIZE];
67 struct NSVGmemPage* next;
70 typedef struct NSVGcachedPaint {
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.
79 unsigned int colors[256];
101 NSVGactiveEdge* freelist;
103 NSVGmemPage* curpage;
105 unsigned char* scanline;
108 unsigned char* bitmap;
109 int width, height, stride;
112 NSVGrasterizer* nsvgCreateRasterizer()
114 NSVGrasterizer* r = (NSVGrasterizer*)malloc(sizeof(NSVGrasterizer));
115 if (r == NULL) goto error;
116 memset(r, 0, sizeof(NSVGrasterizer));
124 nsvgDeleteRasterizer(r);
128 void nsvgDeleteRasterizer(NSVGrasterizer* r)
130 if (r == NULL) return;
135 NSVGmemPage* next = p->next;
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);
148 static NSVGmemPage* nsvg__nextPage(NSVGrasterizer* r, NSVGmemPage* cur)
152 // If using existing chain, return the next page in chain
153 if (cur != NULL && cur->next != NULL) {
158 newp = (NSVGmemPage*)malloc(sizeof(NSVGmemPage));
159 if (newp == NULL) return NULL;
160 memset(newp, 0, sizeof(NSVGmemPage));
162 // Add to linked list
171 static void nsvg__resetPool(NSVGrasterizer* r)
173 NSVGmemPage* p = r->pages;
178 r->curpage = r->pages;
181 static unsigned char* nsvg__alloc(NSVGrasterizer* r, int size)
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);
188 buf = &r->curpage->mem[r->curpage->size];
189 r->curpage->size += size;
193 static int nsvg__ptEquals(float x1, float y1, float x2, float y2, float tol)
197 return dx*dx + dy*dy < tol*tol;
200 static void nsvg__addPathPoint(NSVGrasterizer* r, float x, float y, int flags)
204 if (r->npoints > 0) {
205 pt = &r->points[r->npoints-1];
206 if (nsvg__ptEquals(pt->x,pt->y, x,y, r->distTol)) {
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;
218 pt = &r->points[r->npoints];
221 pt->flags = (unsigned char)flags;
225 static void nsvg__appendPathPoint(NSVGrasterizer* r, NSVGpoint pt)
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;
232 r->points[r->npoints] = pt;
236 static void nsvg__duplicatePoints(NSVGrasterizer* r)
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;
244 memcpy(r->points2, r->points, sizeof(NSVGpoint) * r->npoints);
245 r->npoints2 = r->npoints;
248 static void nsvg__addEdge(NSVGrasterizer* r, float x0, float y0, float x1, float y1)
252 // Skip horizontal edges
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;
262 e = &r->edges[r->nedges];
280 static float nsvg__normalize(float *x, float* y)
282 float d = sqrtf((*x)*(*x) + (*y)*(*y));
291 static float nsvg__absf(float x) { return x < 0 ? -x : x; }
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,
298 float x12,y12,x23,y23,x34,y34,x123,y123,x234,y234,x1234,y1234;
301 if (level > 10) return;
309 x123 = (x12+x23)*0.5f;
310 y123 = (y12+y23)*0.5f;
314 d2 = nsvg__absf(((x2 - x4) * dy - (y2 - y4) * dx));
315 d3 = nsvg__absf(((x3 - x4) * dy - (y3 - y4) * dx));
317 if ((d2 + d3)*(d2 + d3) < r->tessTol * (dx*dx + dy*dy)) {
318 nsvg__addPathPoint(r, x4, y4, type);
322 x234 = (x23+x34)*0.5f;
323 y234 = (y23+y34)*0.5f;
324 x1234 = (x123+x234)*0.5f;
325 y1234 = (y123+y234)*0.5f;
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);
331 static void nsvg__flattenShape(NSVGrasterizer* r, NSVGshape* shape, float scale)
336 for (path = shape->paths; path != NULL; path = path->next) {
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);
345 nsvg__addPathPoint(r, path->pts[0]*scale, path->pts[1]*scale, 0);
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);
354 NSVG_PT_CORNER = 0x01,
355 NSVG_PT_BEVEL = 0x02,
359 static void nsvg__initClosed(NSVGpoint* left, NSVGpoint* right, NSVGpoint* p0, NSVGpoint* p1, float lineWidth)
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;
373 static void nsvg__buttCap(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p, float dx, float dy, float lineWidth, int connect)
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;
381 nsvg__addEdge(r, lx, ly, rx, ry);
384 nsvg__addEdge(r, left->x, left->y, lx, ly);
385 nsvg__addEdge(r, rx, ry, right->x, right->y);
387 left->x = lx; left->y = ly;
388 right->x = rx; right->y = ry;
391 static void nsvg__squareCap(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p, float dx, float dy, float lineWidth, int connect)
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;
399 nsvg__addEdge(r, lx, ly, rx, ry);
402 nsvg__addEdge(r, left->x, left->y, lx, ly);
403 nsvg__addEdge(r, rx, ry, right->x, right->y);
405 left->x = lx; left->y = ly;
406 right->x = rx; right->y = ry;
410 #define NSVG_PI (3.14159265358979323846264338327f)
413 static void nsvg__roundCap(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p, float dx, float dy, float lineWidth, int ncap, int connect)
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;
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;
428 nsvg__addEdge(r, prevx, prevy, x, y);
435 } else if (i == ncap-1) {
441 nsvg__addEdge(r, left->x, left->y, lx, ly);
442 nsvg__addEdge(r, rx, ry, right->x, right->y);
445 left->x = lx; left->y = ly;
446 right->x = rx; right->y = ry;
449 static void nsvg__bevelJoin(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p0, NSVGpoint* p1, float lineWidth)
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);
459 nsvg__addEdge(r, lx0, ly0, left->x, left->y);
460 nsvg__addEdge(r, lx1, ly1, lx0, ly0);
462 nsvg__addEdge(r, right->x, right->y, rx0, ry0);
463 nsvg__addEdge(r, rx0, ry0, rx1, ry1);
465 left->x = lx1; left->y = ly1;
466 right->x = rx1; right->y = ry1;
469 static void nsvg__miterJoin(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p0, NSVGpoint* p1, float lineWidth)
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;
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);
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);
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);
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);
501 left->x = lx1; left->y = ly1;
502 right->x = rx1; right->y = ry1;
505 static void nsvg__roundJoin(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p0, NSVGpoint* p1, float lineWidth, int ncap)
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);
514 float lx, ly, rx, ry;
516 if (da < NSVG_PI) da += NSVG_PI*2;
517 if (da > NSVG_PI) da -= NSVG_PI*2;
519 n = (int)ceilf((nsvg__absf(da) / NSVG_PI) * ncap);
521 if (n > ncap) n = ncap;
528 for (i = 0; i < n; i++) {
529 float u = i/(float)(n-1);
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;
535 nsvg__addEdge(r, lx1, ly1, lx, ly);
536 nsvg__addEdge(r, rx, ry, rx1, ry1);
542 left->x = lx; left->y = ly;
543 right->x = rx; right->y = ry;
546 static void nsvg__straightJoin(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p1, float lineWidth)
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);
552 nsvg__addEdge(r, lx, ly, left->x, left->y);
553 nsvg__addEdge(r, right->x, right->y, rx, ry);
555 left->x = lx; left->y = ly;
556 right->x = rx; right->y = ry;
559 static int nsvg__curveDivs(float r, float arc, float tol)
561 float da = acosf(r / (r + tol)) * 2.0f;
562 int divs = (int)ceilf(arc / da);
563 if (divs < 2) divs = 2;
567 static void nsvg__expandStroke(NSVGrasterizer* r, NSVGpoint* points, int npoints, int closed, int lineJoin, int lineCap, float lineWidth)
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};
574 // Build stroke edges
577 p0 = &points[npoints-1];
590 nsvg__initClosed(&left, &right, p0, p1, lineWidth);
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);
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);
613 nsvg__miterJoin(r, &left, &right, p0, p1, lineWidth);
615 nsvg__straightJoin(r, &left, &right, p1, lineWidth);
622 nsvg__addEdge(r, firstLeft.x, firstLeft.y, left.x, left.y);
623 nsvg__addEdge(r, right.x, right.y, firstRight.x, firstRight.y);
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);
638 static void nsvg__prepareStroke(NSVGrasterizer* r, float miterLimit, int lineJoin)
643 p0 = &r->points[r->npoints-1];
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);
655 p0 = &r->points[r->npoints-1];
657 for (j = 0; j < r->npoints; j++) {
658 float dlx0, dly0, dlx1, dly1, dmr2, cross;
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;
676 // Clear flags, but keep the corner.
677 p1->flags = (p1->flags & NSVG_PT_CORNER) ? NSVG_PT_CORNER : 0;
679 // Keep track of left turns.
680 cross = p1->dx * p0->dy - p0->dx * p1->dy;
682 p1->flags |= NSVG_PT_LEFT;
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;
695 static void nsvg__flattenShapeStroke(NSVGrasterizer* r, NSVGshape* shape, float scale)
700 float miterLimit = 4;
701 int lineJoin = shape->strokeLineJoin;
702 int lineCap = shape->strokeLineCap;
703 float lineWidth = shape->strokeWidth * scale;
705 for (path = shape->paths; path != NULL; path = path->next) {
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);
716 closed = path->closed;
718 // If the first and last points are the same, remove the last, mark as closed path.
719 p0 = &r->points[r->npoints-1];
721 if (nsvg__ptEquals(p0->x,p0->y, p1->x,p1->y, r->distTol)) {
723 p0 = &r->points[r->npoints-1];
727 if (shape->strokeDashCount > 0) {
728 int idash = 0, dashState = 1;
729 float totalDist = 0, dashLen, allDashLen, dashOffset;
733 nsvg__appendPathPoint(r, r->points[0]);
735 // Duplicate points -> points2.
736 nsvg__duplicatePoints(r);
740 nsvg__appendPathPoint(r, cur);
742 // Figure out dash offset.
744 for (j = 0; j < shape->strokeDashCount; j++)
745 allDashLen += shape->strokeDashArray[j];
746 if (shape->strokeDashCount & 1)
748 // Find location inside pattern
749 dashOffset = fmodf(shape->strokeDashOffset, allDashLen);
750 if (dashOffset < 0.0f)
751 dashOffset += allDashLen;
753 while (dashOffset > shape->strokeDashArray[idash]) {
754 dashOffset -= shape->strokeDashArray[idash];
755 idash = (idash + 1) % shape->strokeDashCount;
757 dashLen = (shape->strokeDashArray[idash] - dashOffset) * scale;
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);
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);
772 if (r->npoints > 1 && dashState) {
773 nsvg__prepareStroke(r, miterLimit, lineJoin);
774 nsvg__expandStroke(r, r->points, r->npoints, 0, lineJoin, lineCap, lineWidth);
776 // Advance dash pattern
777 dashState = !dashState;
778 idash = (idash+1) % shape->strokeDashCount;
779 dashLen = shape->strokeDashArray[idash] * scale;
783 cur.flags = NSVG_PT_CORNER;
786 nsvg__appendPathPoint(r, cur);
790 nsvg__appendPathPoint(r, cur);
794 // Stroke any leftover path
795 if (r->npoints > 1 && dashState)
796 nsvg__expandStroke(r, r->points, r->npoints, 0, lineJoin, lineCap, lineWidth);
798 nsvg__prepareStroke(r, miterLimit, lineJoin);
799 nsvg__expandStroke(r, r->points, r->npoints, closed, lineJoin, lineCap, lineWidth);
804 static int nsvg__cmpEdge(const void *p, const void *q)
806 NSVGedge* a = (NSVGedge*)p;
807 NSVGedge* b = (NSVGedge*)q;
809 if (a->y0 < b->y0) return -1;
810 if (a->y0 > b->y0) return 1;
815 static NSVGactiveEdge* nsvg__addActive(NSVGrasterizer* r, NSVGedge* e, float startPoint)
819 if (r->freelist != NULL) {
820 // Restore from freelist.
822 r->freelist = z->next;
825 z = (NSVGactiveEdge*)nsvg__alloc(r, sizeof(NSVGactiveEdge));
826 if (z == NULL) return NULL;
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
833 z->dx = (int)(-floorf(NSVG__FIX * -dxdy));
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;
845 static void nsvg__freeActive(NSVGrasterizer* r, NSVGactiveEdge* z)
847 z->next = r->freelist;
851 static void nsvg__fillScanline(unsigned char* scanline, int len, int x0, int x1, int maxWeight, int* xmin, int* xmax)
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) {
859 // x0,x1 are the same pixel, so compute combined coverage
860 scanline[i] += (unsigned char)((x1 - x0) * maxWeight >> NSVG__FIXSHIFT);
862 if (i >= 0) // add antialiasing for x0
863 scanline[i] += (unsigned char)(((NSVG__FIX - (x0 & NSVG__FIXMASK)) * maxWeight) >> NSVG__FIXSHIFT);
867 if (j < len) // add antialiasing for x1
868 scanline[j] += (unsigned char)(((x1 & NSVG__FIXMASK) * maxWeight) >> NSVG__FIXSHIFT);
872 for (++i; i < j; ++i) // fill pixels between x0 and x1
873 scanline[i] += (unsigned char)maxWeight;
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
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.
887 static void nsvg__fillActiveEdges(unsigned char* scanline, int len, NSVGactiveEdge* e, int maxWeight, int* xmin, int* xmax, signed char fillRule)
889 // non-zero winding fill
892 if (fillRule == NSVG_FILLRULE_NONZERO) {
896 // if we're currently at zero, we need to record the edge start point
897 x0 = e->x; w += e->dir;
899 int x1 = e->x; w += e->dir;
900 // if we went to zero, we need to draw
902 nsvg__fillScanline(scanline, len, x0, x1, maxWeight, xmin, xmax);
906 } else if (fillRule == NSVG_FILLRULE_EVENODD) {
910 // if we're currently at zero, we need to record the edge start point
913 int x1 = e->x; w = 0;
914 nsvg__fillScanline(scanline, len, x0, x1, maxWeight, xmin, xmax);
921 static float nsvg__clampf(float a, float mn, float mx) { return a < mn ? mn : (a > mx ? mx : a); }
923 static unsigned int nsvg__RGBA(unsigned char r, unsigned char g, unsigned char b, unsigned char a)
925 return (r) | (g << 8) | (b << 16) | (a << 24);
928 static unsigned int nsvg__lerpRGBA(unsigned int c0, unsigned int c1, float u)
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);
938 static unsigned int nsvg__applyOpacity(unsigned int c, float u)
940 int iu = (int)(nsvg__clampf(u, 0.0f, 1.0f) * 256.0f);
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);
948 static inline int nsvg__div255(int x)
950 return ((x+1) * 257) >> 16;
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)
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;
964 for (i = 0; i < count; i++) {
966 int a = nsvg__div255((int)cover[0] * ca);
969 r = nsvg__div255(cr * a);
970 g = nsvg__div255(cg * a);
971 b = nsvg__div255(cb * a);
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]);
979 dst[0] = (unsigned char)r;
980 dst[1] = (unsigned char)g;
981 dst[2] = (unsigned char)b;
982 dst[3] = (unsigned char)a;
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;
995 fx = (x - tx) / scale;
996 fy = (y - ty) / scale;
999 for (i = 0; i < count; i++) {
1001 gy = fx*t[1] + fy*t[3] + t[5];
1002 c = cache->colors[(int)nsvg__clampf(gy*255.0f, 0, 255.0f)];
1004 cg = (c >> 8) & 0xff;
1005 cb = (c >> 16) & 0xff;
1006 ca = (c >> 24) & 0xff;
1008 a = nsvg__div255((int)cover[0] * ca);
1012 r = nsvg__div255(cr * a);
1013 g = nsvg__div255(cg * a);
1014 b = nsvg__div255(cb * a);
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]);
1022 dst[0] = (unsigned char)r;
1023 dst[1] = (unsigned char)g;
1024 dst[2] = (unsigned char)b;
1025 dst[3] = (unsigned char)a;
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;
1040 fx = (x - tx) / scale;
1041 fy = (y - ty) / scale;
1044 for (i = 0; i < count; i++) {
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)];
1051 cg = (c >> 8) & 0xff;
1052 cb = (c >> 16) & 0xff;
1053 ca = (c >> 24) & 0xff;
1055 a = nsvg__div255((int)cover[0] * ca);
1059 r = nsvg__div255(cr * a);
1060 g = nsvg__div255(cg * a);
1061 b = nsvg__div255(cb * a);
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]);
1069 dst[0] = (unsigned char)r;
1070 dst[1] = (unsigned char)g;
1071 dst[2] = (unsigned char)b;
1072 dst[3] = (unsigned char)a;
1081 static void nsvg__rasterizeSortedEdges(NSVGrasterizer *r, float tx, float ty, float scale, NSVGcachedPaint* cache, char fillRule)
1083 NSVGactiveEdge *active = NULL;
1086 int maxWeight = (255 / NSVG__SUBSAMPLES); // weight per vertical scanline
1089 for (y = 0; y < r->height; y++) {
1090 memset(r->scanline, 0, r->width);
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;
1098 // update all active edges;
1099 // remove all active edges that terminate before the center of this scanline
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);
1107 z->x += z->dx; // advance to position for current scanline
1108 step = &((*step)->next); // advance through list
1112 // resort the list if needed
1116 while (*step && (*step)->next) {
1117 if ((*step)->x > (*step)->next->x) {
1118 NSVGactiveEdge* t = *step;
1119 NSVGactiveEdge* q = t->next;
1125 step = &(*step)->next;
1127 if (!changed) break;
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) {
1138 } else if (z->x < active->x) {
1143 // find thing to insert AFTER
1144 NSVGactiveEdge* p = active;
1145 while (p->next && p->next->x < z->x)
1147 // at this point, p->next->x is NOT < z->x
1155 // now process all active edges in non-zero fashion
1157 nsvg__fillActiveEdges(r->scanline, r->width, active, maxWeight, &xmin, &xmax, fillRule);
1160 if (xmin < 0) xmin = 0;
1161 if (xmax > r->width-1) xmax = r->width-1;
1163 nsvg__scanlineSolid(&r->bitmap[y * r->stride] + xmin*4, xmax-xmin+1, &r->scanline[xmin], xmin, y, tx,ty, scale, cache);
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.
1175 static void nsvg__initPaint(NSVGcachedPaint* cache, NSVGpaint* paint, float opacity)
1180 cache->type = paint->type;
1182 if (paint->type == NSVG_PAINT_COLOR) {
1183 cache->colors[0] = nsvg__applyOpacity(paint->color, opacity);
1187 grad = paint->gradient;
1189 cache->spread = grad->spread;
1190 memcpy(cache->xform, grad->xform, sizeof(float)*6);
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);
1199 unsigned int ca, cb = 0;
1200 float ua, ub, du, u;
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;
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);
1220 if (count <= 0) continue;
1222 du = 1.0f / (float)count;
1223 for (j = 0; j < count; j++) {
1224 cache->colors[ia+j] = nsvg__lerpRGBA(ca,cb,u);
1229 for (i = ib; i < 256; i++)
1230 cache->colors[i] = cb;
1235 void nsvgRasterize(NSVGrasterizer* r,
1236 NSVGimage* image, float tx, float ty, float scale,
1237 unsigned char* dst, int w, int h, int stride)
1239 NSVGshape *shape = NULL;
1241 NSVGcachedPaint cache;
1249 if (w > r->cscanline) {
1251 r->scanline = (unsigned char*)realloc(r->scanline, w);
1252 if (r->scanline == NULL) return;
1255 for (i = 0; i < h; i++)
1256 memset(&dst[i*stride], 0, w*4);
1258 for (shape = image->shapes; shape != NULL; shape = shape->next) {
1259 if (!(shape->flags & NSVG_FLAGS_VISIBLE))
1262 if (shape->fill.type != NSVG_PAINT_NONE) {
1267 nsvg__flattenShape(r, shape, scale);
1269 // Scale and translate edges
1270 for (i = 0; i < r->nedges; i++) {
1273 e->y0 = (ty + e->y0) * NSVG__SUBSAMPLES;
1275 e->y1 = (ty + e->y1) * NSVG__SUBSAMPLES;
1279 qsort(r->edges, r->nedges, sizeof(NSVGedge), nsvg__cmpEdge);
1281 // now, traverse the scanlines and find the intersections on each scanline, use non-zero rule
1282 nsvg__initPaint(&cache, &shape->fill, shape->opacity);
1284 nsvg__rasterizeSortedEdges(r, tx,ty,scale, &cache, shape->fillRule);
1286 if (shape->stroke.type != NSVG_PAINT_NONE && (shape->strokeWidth * scale) > 0.01f) {
1291 nsvg__flattenShapeStroke(r, shape, scale);
1293 // dumpEdges(r, "edge.svg");
1295 // Scale and translate edges
1296 for (i = 0; i < r->nedges; i++) {
1299 e->y0 = (ty + e->y0) * NSVG__SUBSAMPLES;
1301 e->y1 = (ty + e->y1) * NSVG__SUBSAMPLES;
1305 qsort(r->edges, r->nedges, sizeof(NSVGedge), nsvg__cmpEdge);
1307 // now, traverse the scanlines and find the intersections on each scanline, use non-zero rule
1308 nsvg__initPaint(&cache, &shape->stroke, shape->opacity);
1310 nsvg__rasterizeSortedEdges(r, tx,ty,scale, &cache, NSVG_FILLRULE_NONZERO);
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.