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)
132 if (r == NULL) return;
136 NSVGmemPage* next = p->next;
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);
149 static NSVGmemPage* nsvg__nextPage(NSVGrasterizer* r, NSVGmemPage* cur)
153 // If using existing chain, return the next page in chain
154 if (cur != NULL && cur->next != NULL) {
159 newp = (NSVGmemPage*)malloc(sizeof(NSVGmemPage));
160 if (newp == NULL) return NULL;
161 memset(newp, 0, sizeof(NSVGmemPage));
163 // Add to linked list
172 static void nsvg__resetPool(NSVGrasterizer* r)
174 NSVGmemPage* p = r->pages;
179 r->curpage = r->pages;
182 static unsigned char* nsvg__alloc(NSVGrasterizer* r, int size)
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);
189 buf = &r->curpage->mem[r->curpage->size];
190 r->curpage->size += size;
194 static int nsvg__ptEquals(float x1, float y1, float x2, float y2, float tol)
198 return dx*dx + dy*dy < tol*tol;
201 static void nsvg__addPathPoint(NSVGrasterizer* r, float x, float y, int flags)
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);
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;
219 pt = &r->points[r->npoints];
222 pt->flags = (unsigned char)flags;
226 static void nsvg__appendPathPoint(NSVGrasterizer* r, NSVGpoint pt)
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;
233 r->points[r->npoints] = pt;
237 static void nsvg__duplicatePoints(NSVGrasterizer* r)
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;
245 memcpy(r->points2, r->points, sizeof(NSVGpoint) * r->npoints);
246 r->npoints2 = r->npoints;
249 static void nsvg__addEdge(NSVGrasterizer* r, float x0, float y0, float x1, float y1)
253 // Skip horizontal edges
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;
263 e = &r->edges[r->nedges];
281 static float nsvg__normalize(float *x, float* y)
283 float d = sqrtf((*x)*(*x) + (*y)*(*y));
292 static float nsvg__absf(float x) { return x < 0 ? -x : x; }
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,
299 float x12,y12,x23,y23,x34,y34,x123,y123,x234,y234,x1234,y1234;
302 if (level > 10) return;
310 x123 = (x12+x23)*0.5f;
311 y123 = (y12+y23)*0.5f;
315 d2 = nsvg__absf(((x2 - x4) * dy - (y2 - y4) * dx));
316 d3 = nsvg__absf(((x3 - x4) * dy - (y3 - y4) * dx));
318 if ((d2 + d3)*(d2 + d3) < r->tessTol * (dx*dx + dy*dy)) {
319 nsvg__addPathPoint(r, x4, y4, type);
323 x234 = (x23+x34)*0.5f;
324 y234 = (y23+y34)*0.5f;
325 x1234 = (x123+x234)*0.5f;
326 y1234 = (y123+y234)*0.5f;
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);
332 static void nsvg__flattenShape(NSVGrasterizer* r, NSVGshape* shape, float scale)
337 for (path = shape->paths; path != NULL; path = path->next) {
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);
346 nsvg__addPathPoint(r, path->pts[0]*scale, path->pts[1]*scale, 0);
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);
355 NSVG_PT_CORNER = 0x01,
356 NSVG_PT_BEVEL = 0x02,
360 static void nsvg__initClosed(NSVGpoint* left, NSVGpoint* right, NSVGpoint* p0, NSVGpoint* p1, float lineWidth)
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;
374 static void nsvg__buttCap(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p, float dx, float dy, float lineWidth, int connect)
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;
382 nsvg__addEdge(r, lx, ly, rx, ry);
385 nsvg__addEdge(r, left->x, left->y, lx, ly);
386 nsvg__addEdge(r, rx, ry, right->x, right->y);
388 left->x = lx; left->y = ly;
389 right->x = rx; right->y = ry;
392 static void nsvg__squareCap(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p, float dx, float dy, float lineWidth, int connect)
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;
400 nsvg__addEdge(r, lx, ly, rx, ry);
403 nsvg__addEdge(r, left->x, left->y, lx, ly);
404 nsvg__addEdge(r, rx, ry, right->x, right->y);
406 left->x = lx; left->y = ly;
407 right->x = rx; right->y = ry;
411 #define NSVG_PI (3.14159265358979323846264338327f)
414 static void nsvg__roundCap(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p, float dx, float dy, float lineWidth, int ncap, int connect)
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;
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;
429 nsvg__addEdge(r, prevx, prevy, x, y);
436 } else if (i == ncap-1) {
442 nsvg__addEdge(r, left->x, left->y, lx, ly);
443 nsvg__addEdge(r, rx, ry, right->x, right->y);
446 left->x = lx; left->y = ly;
447 right->x = rx; right->y = ry;
450 static void nsvg__bevelJoin(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p0, NSVGpoint* p1, float lineWidth)
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);
460 nsvg__addEdge(r, lx0, ly0, left->x, left->y);
461 nsvg__addEdge(r, lx1, ly1, lx0, ly0);
463 nsvg__addEdge(r, right->x, right->y, rx0, ry0);
464 nsvg__addEdge(r, rx0, ry0, rx1, ry1);
466 left->x = lx1; left->y = ly1;
467 right->x = rx1; right->y = ry1;
470 static void nsvg__miterJoin(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p0, NSVGpoint* p1, float lineWidth)
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;
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);
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);
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);
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);
502 left->x = lx1; left->y = ly1;
503 right->x = rx1; right->y = ry1;
506 static void nsvg__roundJoin(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p0, NSVGpoint* p1, float lineWidth, int ncap)
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);
515 float lx, ly, rx, ry;
517 if (da < NSVG_PI) da += NSVG_PI*2;
518 if (da > NSVG_PI) da -= NSVG_PI*2;
520 n = (int)ceilf((nsvg__absf(da) / NSVG_PI) * (float)ncap);
522 if (n > ncap) n = ncap;
529 for (i = 0; i < n; i++) {
530 float u = (float)i/(float)(n-1);
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;
536 nsvg__addEdge(r, lx1, ly1, lx, ly);
537 nsvg__addEdge(r, rx, ry, rx1, ry1);
543 left->x = lx; left->y = ly;
544 right->x = rx; right->y = ry;
547 static void nsvg__straightJoin(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p1, float lineWidth)
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);
553 nsvg__addEdge(r, lx, ly, left->x, left->y);
554 nsvg__addEdge(r, right->x, right->y, rx, ry);
556 left->x = lx; left->y = ly;
557 right->x = rx; right->y = ry;
560 static int nsvg__curveDivs(float r, float arc, float tol)
562 float da = acosf(r / (r + tol)) * 2.0f;
563 int divs = (int)ceilf(arc / da);
564 if (divs < 2) divs = 2;
568 static void nsvg__expandStroke(NSVGrasterizer* r, NSVGpoint* points, int npoints, int closed, int lineJoin, int lineCap, float lineWidth)
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};
575 // Build stroke edges
578 p0 = &points[npoints-1];
591 nsvg__initClosed(&left, &right, p0, p1, lineWidth);
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);
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);
614 nsvg__miterJoin(r, &left, &right, p0, p1, lineWidth);
616 nsvg__straightJoin(r, &left, &right, p1, lineWidth);
623 nsvg__addEdge(r, firstLeft.x, firstLeft.y, left.x, left.y);
624 nsvg__addEdge(r, right.x, right.y, firstRight.x, firstRight.y);
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);
639 static void nsvg__prepareStroke(NSVGrasterizer* r, float miterLimit, int lineJoin)
644 p0 = &r->points[r->npoints-1];
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);
656 p0 = &r->points[r->npoints-1];
658 for (j = 0; j < r->npoints; j++) {
659 float dlx0, dly0, dlx1, dly1, dmr2, cross;
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;
677 // Clear flags, but keep the corner.
678 p1->flags = (p1->flags & NSVG_PT_CORNER) ? NSVG_PT_CORNER : 0;
680 // Keep track of left turns.
681 cross = p1->dx * p0->dy - p0->dx * p1->dy;
683 p1->flags |= NSVG_PT_LEFT;
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;
696 static void nsvg__flattenShapeStroke(NSVGrasterizer* r, NSVGshape* shape, float scale)
701 float miterLimit = shape->miterLimit;
702 int lineJoin = shape->strokeLineJoin;
703 int lineCap = shape->strokeLineCap;
704 float lineWidth = shape->strokeWidth * scale;
706 for (path = shape->paths; path != NULL; path = path->next) {
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);
717 closed = path->closed;
719 // If the first and last points are the same, remove the last, mark as closed path.
720 p0 = &r->points[r->npoints-1];
722 if (nsvg__ptEquals(p0->x,p0->y, p1->x,p1->y, r->distTol)) {
724 p0 = &r->points[r->npoints-1];
728 if (shape->strokeDashCount > 0) {
729 int idash = 0, dashState = 1;
730 float totalDist = 0, dashLen, allDashLen, dashOffset;
734 nsvg__appendPathPoint(r, r->points[0]);
736 // Duplicate points -> points2.
737 nsvg__duplicatePoints(r);
741 nsvg__appendPathPoint(r, cur);
743 // Figure out dash offset.
745 for (j = 0; j < shape->strokeDashCount; j++)
746 allDashLen += shape->strokeDashArray[j];
747 if (shape->strokeDashCount & 1)
749 // Find location inside pattern
750 dashOffset = fmodf(shape->strokeDashOffset, allDashLen);
751 if (dashOffset < 0.0f)
752 dashOffset += allDashLen;
754 while (dashOffset > shape->strokeDashArray[idash]) {
755 dashOffset -= shape->strokeDashArray[idash];
756 idash = (idash + 1) % shape->strokeDashCount;
758 dashLen = (shape->strokeDashArray[idash] - dashOffset) * scale;
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);
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);
773 if (r->npoints > 1 && dashState) {
774 nsvg__prepareStroke(r, miterLimit, lineJoin);
775 nsvg__expandStroke(r, r->points, r->npoints, 0, lineJoin, lineCap, lineWidth);
777 // Advance dash pattern
778 dashState = !dashState;
779 idash = (idash+1) % shape->strokeDashCount;
780 dashLen = shape->strokeDashArray[idash] * scale;
784 cur.flags = NSVG_PT_CORNER;
787 nsvg__appendPathPoint(r, cur);
791 nsvg__appendPathPoint(r, cur);
795 // Stroke any leftover path
796 if (r->npoints > 1 && dashState)
797 nsvg__expandStroke(r, r->points, r->npoints, 0, lineJoin, lineCap, lineWidth);
799 nsvg__prepareStroke(r, miterLimit, lineJoin);
800 nsvg__expandStroke(r, r->points, r->npoints, closed, lineJoin, lineCap, lineWidth);
805 static int nsvg__cmpEdge(const void *p, const void *q)
807 const NSVGedge* a = (const NSVGedge*)p;
808 const NSVGedge* b = (const NSVGedge*)q;
810 if (a->y0 < b->y0) return -1;
811 if (a->y0 > b->y0) return 1;
816 static NSVGactiveEdge* nsvg__addActive(NSVGrasterizer* r, NSVGedge* e, float startPoint)
820 if (r->freelist != NULL) {
821 // Restore from freelist.
823 r->freelist = z->next;
826 z = (NSVGactiveEdge*)nsvg__alloc(r, sizeof(NSVGactiveEdge));
827 if (z == NULL) return NULL;
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
834 z->dx = (int)(-floorf(NSVG__FIX * -dxdy));
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;
846 static void nsvg__freeActive(NSVGrasterizer* r, NSVGactiveEdge* z)
848 z->next = r->freelist;
852 static void nsvg__fillScanline(unsigned char* scanline, int len, int x0, int x1, int maxWeight, int* xmin, int* xmax)
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) {
860 // x0,x1 are the same pixel, so compute combined coverage
861 scanline[i] = (unsigned char)(scanline[i] + ((x1 - x0) * maxWeight >> NSVG__FIXSHIFT));
863 if (i >= 0) // add antialiasing for x0
864 scanline[i] = (unsigned char)(scanline[i] + (((NSVG__FIX - (x0 & NSVG__FIXMASK)) * maxWeight) >> NSVG__FIXSHIFT));
868 if (j < len) // add antialiasing for x1
869 scanline[j] = (unsigned char)(scanline[j] + (((x1 & NSVG__FIXMASK) * maxWeight) >> NSVG__FIXSHIFT));
873 for (++i; i < j; ++i) // fill pixels between x0 and x1
874 scanline[i] = (unsigned char)(scanline[i] + maxWeight);
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
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.
888 static void nsvg__fillActiveEdges(unsigned char* scanline, int len, NSVGactiveEdge* e, int maxWeight, int* xmin, int* xmax, signed char fillRule)
890 // non-zero winding fill
893 if (fillRule == NSVG_FILLRULE_NONZERO) {
897 // if we're currently at zero, we need to record the edge start point
898 x0 = e->x; w += e->dir;
900 int x1 = e->x; w += e->dir;
901 // if we went to zero, we need to draw
903 nsvg__fillScanline(scanline, len, x0, x1, maxWeight, xmin, xmax);
907 } else if (fillRule == NSVG_FILLRULE_EVENODD) {
911 // if we're currently at zero, we need to record the edge start point
914 int x1 = e->x; w = 0;
915 nsvg__fillScanline(scanline, len, x0, x1, maxWeight, xmin, xmax);
922 static float nsvg__clampf(float a, float mn, float mx) { return a < mn ? mn : (a > mx ? mx : a); }
924 static unsigned int nsvg__RGBA(unsigned char r, unsigned char g, unsigned char b, unsigned char a)
926 return (r) | (g << 8) | (b << 16) | (a << 24);
929 static unsigned int nsvg__lerpRGBA(unsigned int c0, unsigned int c1, float u)
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);
939 static unsigned int nsvg__applyOpacity(unsigned int c, float u)
941 int iu = (int)(nsvg__clampf(u, 0.0f, 1.0f) * 256.0f);
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);
949 static inline int nsvg__div255(int x)
951 return ((x+1) * 257) >> 16;
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)
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;
965 for (i = 0; i < count; i++) {
967 int a = nsvg__div255((int)cover[0] * ca);
970 r = nsvg__div255(cr * a);
971 g = nsvg__div255(cg * a);
972 b = nsvg__div255(cb * a);
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]);
980 dst[0] = (unsigned char)r;
981 dst[1] = (unsigned char)g;
982 dst[2] = (unsigned char)b;
983 dst[3] = (unsigned char)a;
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;
996 fx = ((float)x - tx) / scale;
997 fy = ((float)y - ty) / scale;
1000 for (i = 0; i < count; i++) {
1002 gy = fx*t[1] + fy*t[3] + t[5];
1003 c = cache->colors[(int)nsvg__clampf(gy*255.0f, 0, 255.0f)];
1005 cg = (c >> 8) & 0xff;
1006 cb = (c >> 16) & 0xff;
1007 ca = (c >> 24) & 0xff;
1009 a = nsvg__div255((int)cover[0] * ca);
1013 r = nsvg__div255(cr * a);
1014 g = nsvg__div255(cg * a);
1015 b = nsvg__div255(cb * a);
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]);
1023 dst[0] = (unsigned char)r;
1024 dst[1] = (unsigned char)g;
1025 dst[2] = (unsigned char)b;
1026 dst[3] = (unsigned char)a;
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;
1041 fx = ((float)x - tx) / scale;
1042 fy = ((float)y - ty) / scale;
1045 for (i = 0; i < count; i++) {
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)];
1052 cg = (c >> 8) & 0xff;
1053 cb = (c >> 16) & 0xff;
1054 ca = (c >> 24) & 0xff;
1056 a = nsvg__div255((int)cover[0] * ca);
1060 r = nsvg__div255(cr * a);
1061 g = nsvg__div255(cg * a);
1062 b = nsvg__div255(cb * a);
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]);
1070 dst[0] = (unsigned char)r;
1071 dst[1] = (unsigned char)g;
1072 dst[2] = (unsigned char)b;
1073 dst[3] = (unsigned char)a;
1082 static void nsvg__rasterizeSortedEdges(NSVGrasterizer *r, float tx, float ty, float scale, NSVGcachedPaint* cache, char fillRule)
1084 NSVGactiveEdge *active = NULL;
1087 int maxWeight = (255 / NSVG__SUBSAMPLES); // weight per vertical scanline
1090 for (y = 0; y < r->height; y++) {
1091 memset(r->scanline, 0, r->width);
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;
1099 // update all active edges;
1100 // remove all active edges that terminate before the center of this scanline
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);
1108 z->x += z->dx; // advance to position for current scanline
1109 step = &((*step)->next); // advance through list
1113 // resort the list if needed
1117 while (*step && (*step)->next) {
1118 if ((*step)->x > (*step)->next->x) {
1119 NSVGactiveEdge* t = *step;
1120 NSVGactiveEdge* q = t->next;
1126 step = &(*step)->next;
1128 if (!changed) break;
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) {
1139 } else if (z->x < active->x) {
1144 // find thing to insert AFTER
1145 NSVGactiveEdge* p = active;
1146 while (p->next && p->next->x < z->x)
1148 // at this point, p->next->x is NOT < z->x
1156 // now process all active edges in non-zero fashion
1158 nsvg__fillActiveEdges(r->scanline, r->width, active, maxWeight, &xmin, &xmax, fillRule);
1161 if (xmin < 0) xmin = 0;
1162 if (xmax > r->width-1) xmax = r->width-1;
1164 nsvg__scanlineSolid(&r->bitmap[y * r->stride] + xmin*4, xmax-xmin+1, &r->scanline[xmin], xmin, y, tx,ty, scale, cache);
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.
1176 static void nsvg__initPaint(NSVGcachedPaint* cache, NSVGpaint* paint, float opacity)
1181 cache->type = paint->type;
1183 if (paint->type == NSVG_PAINT_COLOR) {
1184 cache->colors[0] = nsvg__applyOpacity(paint->color, opacity);
1188 grad = paint->gradient;
1190 cache->spread = grad->spread;
1191 memcpy(cache->xform, grad->xform, sizeof(float)*6);
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);
1200 unsigned int ca, cb = 0;
1201 float ua, ub, du, u;
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;
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);
1221 if (count <= 0) continue;
1223 du = 1.0f / (float)count;
1224 for (j = 0; j < count; j++) {
1225 cache->colors[ia+j] = nsvg__lerpRGBA(ca,cb,u);
1230 for (i = ib; i < 256; i++)
1231 cache->colors[i] = cb;
1236 void nsvgRasterize(NSVGrasterizer* r,
1237 NSVGimage* image, float tx, float ty, float scale,
1238 unsigned char* dst, int w, int h, int stride)
1240 NSVGshape *shape = NULL;
1242 NSVGcachedPaint cache;
1250 if (w > r->cscanline) {
1252 r->scanline = (unsigned char*)realloc(r->scanline, w);
1253 if (r->scanline == NULL) return;
1256 for (i = 0; i < h; i++)
1257 memset(&dst[i*stride], 0, w*4);
1259 for (shape = image->shapes; shape != NULL; shape = shape->next) {
1260 if (!(shape->flags & NSVG_FLAGS_VISIBLE))
1263 if (shape->fill.type != NSVG_PAINT_NONE) {
1268 nsvg__flattenShape(r, shape, scale);
1270 // Scale and translate edges
1271 for (i = 0; i < r->nedges; i++) {
1274 e->y0 = (ty + e->y0) * NSVG__SUBSAMPLES;
1276 e->y1 = (ty + e->y1) * NSVG__SUBSAMPLES;
1280 qsort(r->edges, r->nedges, sizeof(NSVGedge), nsvg__cmpEdge);
1282 // now, traverse the scanlines and find the intersections on each scanline, use non-zero rule
1283 nsvg__initPaint(&cache, &shape->fill, shape->opacity);
1285 nsvg__rasterizeSortedEdges(r, tx,ty,scale, &cache, shape->fillRule);
1287 if (shape->stroke.type != NSVG_PAINT_NONE && (shape->strokeWidth * scale) > 0.01f) {
1292 nsvg__flattenShapeStroke(r, shape, scale);
1294 // dumpEdges(r, "edge.svg");
1296 // Scale and translate edges
1297 for (i = 0; i < r->nedges; i++) {
1300 e->y0 = (ty + e->y0) * NSVG__SUBSAMPLES;
1302 e->y1 = (ty + e->y1) * NSVG__SUBSAMPLES;
1306 qsort(r->edges, r->nedges, sizeof(NSVGedge), nsvg__cmpEdge);
1308 // now, traverse the scanlines and find the intersections on each scanline, use non-zero rule
1309 nsvg__initPaint(&cache, &shape->stroke, shape->opacity);
1311 nsvg__rasterizeSortedEdges(r, tx,ty,scale, &cache, NSVG_FILLRULE_NONZERO);
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.