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 {
74 unsigned int colors[256];
96 NSVGactiveEdge* freelist;
100 unsigned char* scanline;
103 unsigned char* bitmap;
104 int width, height, stride;
107 NSVGrasterizer* nsvgCreateRasterizer()
109 NSVGrasterizer* r = (NSVGrasterizer*)malloc(sizeof(NSVGrasterizer));
110 if (r == NULL) goto error;
111 memset(r, 0, sizeof(NSVGrasterizer));
119 nsvgDeleteRasterizer(r);
123 void nsvgDeleteRasterizer(NSVGrasterizer* r)
125 if (r == NULL) return;
130 NSVGmemPage* next = p->next;
135 if (r->edges) free(r->edges);
136 if (r->points) free(r->points);
137 if (r->points2) free(r->points2);
138 if (r->scanline) free(r->scanline);
143 static NSVGmemPage* nsvg__nextPage(NSVGrasterizer* r, NSVGmemPage* cur)
147 // If using existing chain, return the next page in chain
148 if (cur != NULL && cur->next != NULL) {
153 newp = (NSVGmemPage*)malloc(sizeof(NSVGmemPage));
154 if (newp == NULL) return NULL;
155 memset(newp, 0, sizeof(NSVGmemPage));
157 // Add to linked list
166 static void nsvg__resetPool(NSVGrasterizer* r)
168 NSVGmemPage* p = r->pages;
173 r->curpage = r->pages;
176 static unsigned char* nsvg__alloc(NSVGrasterizer* r, int size)
179 if (size > NSVG__MEMPAGE_SIZE) return NULL;
180 if (r->curpage == NULL || r->curpage->size+size > NSVG__MEMPAGE_SIZE) {
181 r->curpage = nsvg__nextPage(r, r->curpage);
183 buf = &r->curpage->mem[r->curpage->size];
184 r->curpage->size += size;
188 static int nsvg__ptEquals(float x1, float y1, float x2, float y2, float tol)
192 return dx*dx + dy*dy < tol*tol;
195 static void nsvg__addPathPoint(NSVGrasterizer* r, float x, float y, int flags)
199 if (r->npoints > 0) {
200 pt = &r->points[r->npoints-1];
201 if (nsvg__ptEquals(pt->x,pt->y, x,y, r->distTol)) {
207 if (r->npoints+1 > r->cpoints) {
208 r->cpoints = r->cpoints > 0 ? r->cpoints * 2 : 64;
209 r->points = (NSVGpoint*)realloc(r->points, sizeof(NSVGpoint) * r->cpoints);
210 if (r->points == NULL) return;
213 pt = &r->points[r->npoints];
216 pt->flags = (unsigned char)flags;
220 static void nsvg__appendPathPoint(NSVGrasterizer* r, NSVGpoint pt)
222 if (r->npoints+1 > r->cpoints) {
223 r->cpoints = r->cpoints > 0 ? r->cpoints * 2 : 64;
224 r->points = (NSVGpoint*)realloc(r->points, sizeof(NSVGpoint) * r->cpoints);
225 if (r->points == NULL) return;
227 r->points[r->npoints] = pt;
231 static void nsvg__duplicatePoints(NSVGrasterizer* r)
233 if (r->npoints > r->cpoints2) {
234 r->cpoints2 = r->npoints;
235 r->points2 = (NSVGpoint*)realloc(r->points2, sizeof(NSVGpoint) * r->cpoints2);
236 if (r->points2 == NULL) return;
239 memcpy(r->points2, r->points, sizeof(NSVGpoint) * r->npoints);
240 r->npoints2 = r->npoints;
243 static void nsvg__addEdge(NSVGrasterizer* r, float x0, float y0, float x1, float y1)
247 // Skip horizontal edges
251 if (r->nedges+1 > r->cedges) {
252 r->cedges = r->cedges > 0 ? r->cedges * 2 : 64;
253 r->edges = (NSVGedge*)realloc(r->edges, sizeof(NSVGedge) * r->cedges);
254 if (r->edges == NULL) return;
257 e = &r->edges[r->nedges];
275 static float nsvg__normalize(float *x, float* y)
277 float d = sqrtf((*x)*(*x) + (*y)*(*y));
286 static float nsvg__absf(float x) { return x < 0 ? -x : x; }
288 static void nsvg__flattenCubicBez(NSVGrasterizer* r,
289 float x1, float y1, float x2, float y2,
290 float x3, float y3, float x4, float y4,
293 float x12,y12,x23,y23,x34,y34,x123,y123,x234,y234,x1234,y1234;
296 if (level > 10) return;
304 x123 = (x12+x23)*0.5f;
305 y123 = (y12+y23)*0.5f;
309 d2 = nsvg__absf(((x2 - x4) * dy - (y2 - y4) * dx));
310 d3 = nsvg__absf(((x3 - x4) * dy - (y3 - y4) * dx));
312 if ((d2 + d3)*(d2 + d3) < r->tessTol * (dx*dx + dy*dy)) {
313 nsvg__addPathPoint(r, x4, y4, type);
317 x234 = (x23+x34)*0.5f;
318 y234 = (y23+y34)*0.5f;
319 x1234 = (x123+x234)*0.5f;
320 y1234 = (y123+y234)*0.5f;
322 nsvg__flattenCubicBez(r, x1,y1, x12,y12, x123,y123, x1234,y1234, level+1, 0);
323 nsvg__flattenCubicBez(r, x1234,y1234, x234,y234, x34,y34, x4,y4, level+1, type);
326 static void nsvg__flattenShape(NSVGrasterizer* r, NSVGshape* shape, float scale)
331 for (path = shape->paths; path != NULL; path = path->next) {
334 nsvg__addPathPoint(r, path->pts[0]*scale, path->pts[1]*scale, 0);
335 for (i = 0; i < path->npts-1; i += 3) {
336 float* p = &path->pts[i*2];
337 nsvg__flattenCubicBez(r, p[0]*scale,p[1]*scale, p[2]*scale,p[3]*scale, p[4]*scale,p[5]*scale, p[6]*scale,p[7]*scale, 0, 0);
340 nsvg__addPathPoint(r, path->pts[0]*scale, path->pts[1]*scale, 0);
342 for (i = 0, j = r->npoints-1; i < r->npoints; j = i++)
343 nsvg__addEdge(r, r->points[j].x, r->points[j].y, r->points[i].x, r->points[i].y);
349 NSVG_PT_CORNER = 0x01,
350 NSVG_PT_BEVEL = 0x02,
354 static void nsvg__initClosed(NSVGpoint* left, NSVGpoint* right, NSVGpoint* p0, NSVGpoint* p1, float lineWidth)
356 float w = lineWidth * 0.5f;
357 float dx = p1->x - p0->x;
358 float dy = p1->y - p0->y;
359 float len = nsvg__normalize(&dx, &dy);
360 float px = p0->x + dx*len*0.5f, py = p0->y + dy*len*0.5f;
361 float dlx = dy, dly = -dx;
362 float lx = px - dlx*w, ly = py - dly*w;
363 float rx = px + dlx*w, ry = py + dly*w;
364 left->x = lx; left->y = ly;
365 right->x = rx; right->y = ry;
368 static void nsvg__buttCap(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p, float dx, float dy, float lineWidth, int connect)
370 float w = lineWidth * 0.5f;
371 float px = p->x, py = p->y;
372 float dlx = dy, dly = -dx;
373 float lx = px - dlx*w, ly = py - dly*w;
374 float rx = px + dlx*w, ry = py + dly*w;
376 nsvg__addEdge(r, lx, ly, rx, ry);
379 nsvg__addEdge(r, left->x, left->y, lx, ly);
380 nsvg__addEdge(r, rx, ry, right->x, right->y);
382 left->x = lx; left->y = ly;
383 right->x = rx; right->y = ry;
386 static void nsvg__squareCap(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p, float dx, float dy, float lineWidth, int connect)
388 float w = lineWidth * 0.5f;
389 float px = p->x - dx*w, py = p->y - dy*w;
390 float dlx = dy, dly = -dx;
391 float lx = px - dlx*w, ly = py - dly*w;
392 float rx = px + dlx*w, ry = py + dly*w;
394 nsvg__addEdge(r, lx, ly, rx, ry);
397 nsvg__addEdge(r, left->x, left->y, lx, ly);
398 nsvg__addEdge(r, rx, ry, right->x, right->y);
400 left->x = lx; left->y = ly;
401 right->x = rx; right->y = ry;
405 #define NSVG_PI (3.14159265358979323846264338327f)
408 static void nsvg__roundCap(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p, float dx, float dy, float lineWidth, int ncap, int connect)
411 float w = lineWidth * 0.5f;
412 float px = p->x, py = p->y;
413 float dlx = dy, dly = -dx;
414 float lx = 0, ly = 0, rx = 0, ry = 0, prevx = 0, prevy = 0;
416 for (i = 0; i < ncap; i++) {
417 float a = i/(float)(ncap-1)*NSVG_PI;
418 float ax = cosf(a) * w, ay = sinf(a) * w;
419 float x = px - dlx*ax - dx*ay;
420 float y = py - dly*ax - dy*ay;
423 nsvg__addEdge(r, prevx, prevy, x, y);
430 } else if (i == ncap-1) {
436 nsvg__addEdge(r, left->x, left->y, lx, ly);
437 nsvg__addEdge(r, rx, ry, right->x, right->y);
440 left->x = lx; left->y = ly;
441 right->x = rx; right->y = ry;
444 static void nsvg__bevelJoin(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p0, NSVGpoint* p1, float lineWidth)
446 float w = lineWidth * 0.5f;
447 float dlx0 = p0->dy, dly0 = -p0->dx;
448 float dlx1 = p1->dy, dly1 = -p1->dx;
449 float lx0 = p1->x - (dlx0 * w), ly0 = p1->y - (dly0 * w);
450 float rx0 = p1->x + (dlx0 * w), ry0 = p1->y + (dly0 * w);
451 float lx1 = p1->x - (dlx1 * w), ly1 = p1->y - (dly1 * w);
452 float rx1 = p1->x + (dlx1 * w), ry1 = p1->y + (dly1 * w);
454 nsvg__addEdge(r, lx0, ly0, left->x, left->y);
455 nsvg__addEdge(r, lx1, ly1, lx0, ly0);
457 nsvg__addEdge(r, right->x, right->y, rx0, ry0);
458 nsvg__addEdge(r, rx0, ry0, rx1, ry1);
460 left->x = lx1; left->y = ly1;
461 right->x = rx1; right->y = ry1;
464 static void nsvg__miterJoin(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p0, NSVGpoint* p1, float lineWidth)
466 float w = lineWidth * 0.5f;
467 float dlx0 = p0->dy, dly0 = -p0->dx;
468 float dlx1 = p1->dy, dly1 = -p1->dx;
469 float lx0, rx0, lx1, rx1;
470 float ly0, ry0, ly1, ry1;
472 if (p1->flags & NSVG_PT_LEFT) {
473 lx0 = lx1 = p1->x - p1->dmx * w;
474 ly0 = ly1 = p1->y - p1->dmy * w;
475 nsvg__addEdge(r, lx1, ly1, left->x, left->y);
477 rx0 = p1->x + (dlx0 * w);
478 ry0 = p1->y + (dly0 * w);
479 rx1 = p1->x + (dlx1 * w);
480 ry1 = p1->y + (dly1 * w);
481 nsvg__addEdge(r, right->x, right->y, rx0, ry0);
482 nsvg__addEdge(r, rx0, ry0, rx1, ry1);
484 lx0 = p1->x - (dlx0 * w);
485 ly0 = p1->y - (dly0 * w);
486 lx1 = p1->x - (dlx1 * w);
487 ly1 = p1->y - (dly1 * w);
488 nsvg__addEdge(r, lx0, ly0, left->x, left->y);
489 nsvg__addEdge(r, lx1, ly1, lx0, ly0);
491 rx0 = rx1 = p1->x + p1->dmx * w;
492 ry0 = ry1 = p1->y + p1->dmy * w;
493 nsvg__addEdge(r, right->x, right->y, rx1, ry1);
496 left->x = lx1; left->y = ly1;
497 right->x = rx1; right->y = ry1;
500 static void nsvg__roundJoin(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p0, NSVGpoint* p1, float lineWidth, int ncap)
503 float w = lineWidth * 0.5f;
504 float dlx0 = p0->dy, dly0 = -p0->dx;
505 float dlx1 = p1->dy, dly1 = -p1->dx;
506 float a0 = atan2f(dly0, dlx0);
507 float a1 = atan2f(dly1, dlx1);
509 float lx, ly, rx, ry;
511 if (da < NSVG_PI) da += NSVG_PI*2;
512 if (da > NSVG_PI) da -= NSVG_PI*2;
514 n = (int)ceilf((nsvg__absf(da) / NSVG_PI) * ncap);
516 if (n > ncap) n = ncap;
523 for (i = 0; i < n; i++) {
524 float u = i/(float)(n-1);
526 float ax = cosf(a) * w, ay = sinf(a) * w;
527 float lx1 = p1->x - ax, ly1 = p1->y - ay;
528 float rx1 = p1->x + ax, ry1 = p1->y + ay;
530 nsvg__addEdge(r, lx1, ly1, lx, ly);
531 nsvg__addEdge(r, rx, ry, rx1, ry1);
537 left->x = lx; left->y = ly;
538 right->x = rx; right->y = ry;
541 static void nsvg__straightJoin(NSVGrasterizer* r, NSVGpoint* left, NSVGpoint* right, NSVGpoint* p1, float lineWidth)
543 float w = lineWidth * 0.5f;
544 float lx = p1->x - (p1->dmx * w), ly = p1->y - (p1->dmy * w);
545 float rx = p1->x + (p1->dmx * w), ry = p1->y + (p1->dmy * w);
547 nsvg__addEdge(r, lx, ly, left->x, left->y);
548 nsvg__addEdge(r, right->x, right->y, rx, ry);
550 left->x = lx; left->y = ly;
551 right->x = rx; right->y = ry;
554 static int nsvg__curveDivs(float r, float arc, float tol)
556 float da = acosf(r / (r + tol)) * 2.0f;
557 int divs = (int)ceilf(arc / da);
558 if (divs < 2) divs = 2;
562 static void nsvg__expandStroke(NSVGrasterizer* r, NSVGpoint* points, int npoints, int closed, int lineJoin, int lineCap, float lineWidth)
564 int ncap = nsvg__curveDivs(lineWidth*0.5f, NSVG_PI, r->tessTol); // Calculate divisions per half circle.
565 NSVGpoint left = {0,0,0,0,0,0,0,0}, right = {0,0,0,0,0,0,0,0}, firstLeft = {0,0,0,0,0,0,0,0}, firstRight = {0,0,0,0,0,0,0,0};
569 // Build stroke edges
572 p0 = &points[npoints-1];
585 nsvg__initClosed(&left, &right, p0, p1, lineWidth);
590 float dx = p1->x - p0->x;
591 float dy = p1->y - p0->y;
592 nsvg__normalize(&dx, &dy);
593 if (lineCap == NSVG_CAP_BUTT)
594 nsvg__buttCap(r, &left, &right, p0, dx, dy, lineWidth, 0);
595 else if (lineCap == NSVG_CAP_SQUARE)
596 nsvg__squareCap(r, &left, &right, p0, dx, dy, lineWidth, 0);
597 else if (lineCap == NSVG_CAP_ROUND)
598 nsvg__roundCap(r, &left, &right, p0, dx, dy, lineWidth, ncap, 0);
601 for (j = s; j < e; ++j) {
602 if (p1->flags & NSVG_PT_CORNER) {
603 if (lineJoin == NSVG_JOIN_ROUND)
604 nsvg__roundJoin(r, &left, &right, p0, p1, lineWidth, ncap);
605 else if (lineJoin == NSVG_JOIN_BEVEL || (p1->flags & NSVG_PT_BEVEL))
606 nsvg__bevelJoin(r, &left, &right, p0, p1, lineWidth);
608 nsvg__miterJoin(r, &left, &right, p0, p1, lineWidth);
610 nsvg__straightJoin(r, &left, &right, p1, lineWidth);
617 nsvg__addEdge(r, firstLeft.x, firstLeft.y, left.x, left.y);
618 nsvg__addEdge(r, right.x, right.y, firstRight.x, firstRight.y);
621 float dx = p1->x - p0->x;
622 float dy = p1->y - p0->y;
623 nsvg__normalize(&dx, &dy);
624 if (lineCap == NSVG_CAP_BUTT)
625 nsvg__buttCap(r, &right, &left, p1, -dx, -dy, lineWidth, 1);
626 else if (lineCap == NSVG_CAP_SQUARE)
627 nsvg__squareCap(r, &right, &left, p1, -dx, -dy, lineWidth, 1);
628 else if (lineCap == NSVG_CAP_ROUND)
629 nsvg__roundCap(r, &right, &left, p1, -dx, -dy, lineWidth, ncap, 1);
633 static void nsvg__prepareStroke(NSVGrasterizer* r, float miterLimit, int lineJoin)
638 p0 = &r->points[r->npoints-1];
640 for (i = 0; i < r->npoints; i++) {
641 // Calculate segment direction and length
642 p0->dx = p1->x - p0->x;
643 p0->dy = p1->y - p0->y;
644 p0->len = nsvg__normalize(&p0->dx, &p0->dy);
650 p0 = &r->points[r->npoints-1];
652 for (j = 0; j < r->npoints; j++) {
653 float dlx0, dly0, dlx1, dly1, dmr2, cross;
658 // Calculate extrusions
659 p1->dmx = (dlx0 + dlx1) * 0.5f;
660 p1->dmy = (dly0 + dly1) * 0.5f;
661 dmr2 = p1->dmx*p1->dmx + p1->dmy*p1->dmy;
662 if (dmr2 > 0.000001f) {
663 float s2 = 1.0f / dmr2;
671 // Clear flags, but keep the corner.
672 p1->flags = (p1->flags & NSVG_PT_CORNER) ? NSVG_PT_CORNER : 0;
674 // Keep track of left turns.
675 cross = p1->dx * p0->dy - p0->dx * p1->dy;
677 p1->flags |= NSVG_PT_LEFT;
679 // Check to see if the corner needs to be beveled.
680 if (p1->flags & NSVG_PT_CORNER) {
681 if ((dmr2 * miterLimit*miterLimit) < 1.0f || lineJoin == NSVG_JOIN_BEVEL || lineJoin == NSVG_JOIN_ROUND) {
682 p1->flags |= NSVG_PT_BEVEL;
690 static void nsvg__flattenShapeStroke(NSVGrasterizer* r, NSVGshape* shape, float scale)
695 float miterLimit = 4;
696 int lineJoin = shape->strokeLineJoin;
697 int lineCap = shape->strokeLineCap;
698 float lineWidth = shape->strokeWidth * scale;
700 for (path = shape->paths; path != NULL; path = path->next) {
703 nsvg__addPathPoint(r, path->pts[0]*scale, path->pts[1]*scale, NSVG_PT_CORNER);
704 for (i = 0; i < path->npts-1; i += 3) {
705 float* p = &path->pts[i*2];
706 nsvg__flattenCubicBez(r, p[0]*scale,p[1]*scale, p[2]*scale,p[3]*scale, p[4]*scale,p[5]*scale, p[6]*scale,p[7]*scale, 0, NSVG_PT_CORNER);
711 closed = path->closed;
713 // If the first and last points are the same, remove the last, mark as closed path.
714 p0 = &r->points[r->npoints-1];
716 if (nsvg__ptEquals(p0->x,p0->y, p1->x,p1->y, r->distTol)) {
718 p0 = &r->points[r->npoints-1];
722 if (shape->strokeDashCount > 0) {
723 int idash = 0, dashState = 1;
724 float totalDist = 0, dashLen, allDashLen, dashOffset;
728 nsvg__appendPathPoint(r, r->points[0]);
730 // Duplicate points -> points2.
731 nsvg__duplicatePoints(r);
735 nsvg__appendPathPoint(r, cur);
737 // Figure out dash offset.
739 for (j = 0; j < shape->strokeDashCount; j++)
740 allDashLen += shape->strokeDashArray[j];
741 if (shape->strokeDashCount & 1)
743 // Find location inside pattern
744 dashOffset = fmodf(shape->strokeDashOffset, allDashLen);
745 if (dashOffset < 0.0f)
746 dashOffset += allDashLen;
748 while (dashOffset > shape->strokeDashArray[idash]) {
749 dashOffset -= shape->strokeDashArray[idash];
750 idash = (idash + 1) % shape->strokeDashCount;
752 dashLen = (shape->strokeDashArray[idash] - dashOffset) * scale;
754 for (j = 1; j < r->npoints2; ) {
755 float dx = r->points2[j].x - cur.x;
756 float dy = r->points2[j].y - cur.y;
757 float dist = sqrtf(dx*dx + dy*dy);
759 if ((totalDist + dist) > dashLen) {
760 // Calculate intermediate point
761 float d = (dashLen - totalDist) / dist;
762 float x = cur.x + dx * d;
763 float y = cur.y + dy * d;
764 nsvg__addPathPoint(r, x, y, NSVG_PT_CORNER);
767 if (r->npoints > 1 && dashState) {
768 nsvg__prepareStroke(r, miterLimit, lineJoin);
769 nsvg__expandStroke(r, r->points, r->npoints, 0, lineJoin, lineCap, lineWidth);
771 // Advance dash pattern
772 dashState = !dashState;
773 idash = (idash+1) % shape->strokeDashCount;
774 dashLen = shape->strokeDashArray[idash] * scale;
778 cur.flags = NSVG_PT_CORNER;
781 nsvg__appendPathPoint(r, cur);
785 nsvg__appendPathPoint(r, cur);
789 // Stroke any leftover path
790 if (r->npoints > 1 && dashState)
791 nsvg__expandStroke(r, r->points, r->npoints, 0, lineJoin, lineCap, lineWidth);
793 nsvg__prepareStroke(r, miterLimit, lineJoin);
794 nsvg__expandStroke(r, r->points, r->npoints, closed, lineJoin, lineCap, lineWidth);
799 static int nsvg__cmpEdge(const void *p, const void *q)
801 NSVGedge* a = (NSVGedge*)p;
802 NSVGedge* b = (NSVGedge*)q;
804 if (a->y0 < b->y0) return -1;
805 if (a->y0 > b->y0) return 1;
810 static NSVGactiveEdge* nsvg__addActive(NSVGrasterizer* r, NSVGedge* e, float startPoint)
814 if (r->freelist != NULL) {
815 // Restore from freelist.
817 r->freelist = z->next;
820 z = (NSVGactiveEdge*)nsvg__alloc(r, sizeof(NSVGactiveEdge));
821 if (z == NULL) return NULL;
824 float dxdy = (e->x1 - e->x0) / (e->y1 - e->y0);
825 // STBTT_assert(e->y0 <= start_point);
826 // round dx down to avoid going too far
828 z->dx = (int)(-floorf(NSVG__FIX * -dxdy));
830 z->dx = (int)floorf(NSVG__FIX * dxdy);
831 z->x = (int)floorf(NSVG__FIX * (e->x0 + dxdy * (startPoint - e->y0)));
832 // z->x -= off_x * FIX;
840 static void nsvg__freeActive(NSVGrasterizer* r, NSVGactiveEdge* z)
842 z->next = r->freelist;
846 static void nsvg__fillScanline(unsigned char* scanline, int len, int x0, int x1, int maxWeight, int* xmin, int* xmax)
848 int i = x0 >> NSVG__FIXSHIFT;
849 int j = x1 >> NSVG__FIXSHIFT;
850 if (i < *xmin) *xmin = i;
851 if (j > *xmax) *xmax = j;
852 if (i < len && j >= 0) {
854 // x0,x1 are the same pixel, so compute combined coverage
855 scanline[i] += (unsigned char)((x1 - x0) * maxWeight >> NSVG__FIXSHIFT);
857 if (i >= 0) // add antialiasing for x0
858 scanline[i] += (unsigned char)(((NSVG__FIX - (x0 & NSVG__FIXMASK)) * maxWeight) >> NSVG__FIXSHIFT);
862 if (j < len) // add antialiasing for x1
863 scanline[j] += (unsigned char)(((x1 & NSVG__FIXMASK) * maxWeight) >> NSVG__FIXSHIFT);
867 for (++i; i < j; ++i) // fill pixels between x0 and x1
868 scanline[i] += (unsigned char)maxWeight;
873 // note: this routine clips fills that extend off the edges... ideally this
874 // wouldn't happen, but it could happen if the truetype glyph bounding boxes
875 // are wrong, or if the user supplies a too-small bitmap
876 static void nsvg__fillActiveEdges(unsigned char* scanline, int len, NSVGactiveEdge* e, int maxWeight, int* xmin, int* xmax, char fillRule)
878 // non-zero winding fill
881 if (fillRule == NSVG_FILLRULE_NONZERO) {
885 // if we're currently at zero, we need to record the edge start point
886 x0 = e->x; w += e->dir;
888 int x1 = e->x; w += e->dir;
889 // if we went to zero, we need to draw
891 nsvg__fillScanline(scanline, len, x0, x1, maxWeight, xmin, xmax);
895 } else if (fillRule == NSVG_FILLRULE_EVENODD) {
899 // if we're currently at zero, we need to record the edge start point
902 int x1 = e->x; w = 0;
903 nsvg__fillScanline(scanline, len, x0, x1, maxWeight, xmin, xmax);
910 static float nsvg__clampf(float a, float mn, float mx) { return a < mn ? mn : (a > mx ? mx : a); }
912 static unsigned int nsvg__RGBA(unsigned char r, unsigned char g, unsigned char b, unsigned char a)
914 return (r) | (g << 8) | (b << 16) | (a << 24);
917 static unsigned int nsvg__lerpRGBA(unsigned int c0, unsigned int c1, float u)
919 int iu = (int)(nsvg__clampf(u, 0.0f, 1.0f) * 256.0f);
920 int r = (((c0) & 0xff)*(256-iu) + (((c1) & 0xff)*iu)) >> 8;
921 int g = (((c0>>8) & 0xff)*(256-iu) + (((c1>>8) & 0xff)*iu)) >> 8;
922 int b = (((c0>>16) & 0xff)*(256-iu) + (((c1>>16) & 0xff)*iu)) >> 8;
923 int a = (((c0>>24) & 0xff)*(256-iu) + (((c1>>24) & 0xff)*iu)) >> 8;
924 return nsvg__RGBA((unsigned char)r, (unsigned char)g, (unsigned char)b, (unsigned char)a);
927 static unsigned int nsvg__applyOpacity(unsigned int c, float u)
929 int iu = (int)(nsvg__clampf(u, 0.0f, 1.0f) * 256.0f);
931 int g = (c>>8) & 0xff;
932 int b = (c>>16) & 0xff;
933 int a = (((c>>24) & 0xff)*iu) >> 8;
934 return nsvg__RGBA((unsigned char)r, (unsigned char)g, (unsigned char)b, (unsigned char)a);
937 static inline int nsvg__div255(int x)
939 return ((x+1) * 257) >> 16;
942 static void nsvg__scanlineSolid(unsigned char* dst, int count, unsigned char* cover, int x, int y,
943 float tx, float ty, float scale, NSVGcachedPaint* cache)
946 if (cache->type == NSVG_PAINT_COLOR) {
947 int i, cr, cg, cb, ca;
948 cr = cache->colors[0] & 0xff;
949 cg = (cache->colors[0] >> 8) & 0xff;
950 cb = (cache->colors[0] >> 16) & 0xff;
951 ca = (cache->colors[0] >> 24) & 0xff;
953 for (i = 0; i < count; i++) {
955 int a = nsvg__div255((int)cover[0] * ca);
958 r = nsvg__div255(cr * a);
959 g = nsvg__div255(cg * a);
960 b = nsvg__div255(cb * a);
963 r += nsvg__div255(ia * (int)dst[0]);
964 g += nsvg__div255(ia * (int)dst[1]);
965 b += nsvg__div255(ia * (int)dst[2]);
966 a += nsvg__div255(ia * (int)dst[3]);
968 dst[0] = (unsigned char)r;
969 dst[1] = (unsigned char)g;
970 dst[2] = (unsigned char)b;
971 dst[3] = (unsigned char)a;
976 } else if (cache->type == NSVG_PAINT_LINEAR_GRADIENT) {
977 // TODO: spread modes.
978 // TODO: plenty of opportunities to optimize.
979 float fx, fy, dx, gy;
980 float* t = cache->xform;
981 int i, cr, cg, cb, ca;
984 fx = (x - tx) / scale;
985 fy = (y - ty) / scale;
988 for (i = 0; i < count; i++) {
990 gy = fx*t[1] + fy*t[3] + t[5];
991 c = cache->colors[(int)nsvg__clampf(gy*255.0f, 0, 255.0f)];
993 cg = (c >> 8) & 0xff;
994 cb = (c >> 16) & 0xff;
995 ca = (c >> 24) & 0xff;
997 a = nsvg__div255((int)cover[0] * ca);
1001 r = nsvg__div255(cr * a);
1002 g = nsvg__div255(cg * a);
1003 b = nsvg__div255(cb * a);
1006 r += nsvg__div255(ia * (int)dst[0]);
1007 g += nsvg__div255(ia * (int)dst[1]);
1008 b += nsvg__div255(ia * (int)dst[2]);
1009 a += nsvg__div255(ia * (int)dst[3]);
1011 dst[0] = (unsigned char)r;
1012 dst[1] = (unsigned char)g;
1013 dst[2] = (unsigned char)b;
1014 dst[3] = (unsigned char)a;
1020 } else if (cache->type == NSVG_PAINT_RADIAL_GRADIENT) {
1021 // TODO: spread modes.
1022 // TODO: plenty of opportunities to optimize.
1023 // TODO: focus (fx,fy)
1024 float fx, fy, dx, gx, gy, gd;
1025 float* t = cache->xform;
1026 int i, cr, cg, cb, ca;
1029 fx = (x - tx) / scale;
1030 fy = (y - ty) / scale;
1033 for (i = 0; i < count; i++) {
1035 gx = fx*t[0] + fy*t[2] + t[4];
1036 gy = fx*t[1] + fy*t[3] + t[5];
1037 gd = sqrtf(gx*gx + gy*gy);
1038 c = cache->colors[(int)nsvg__clampf(gd*255.0f, 0, 255.0f)];
1040 cg = (c >> 8) & 0xff;
1041 cb = (c >> 16) & 0xff;
1042 ca = (c >> 24) & 0xff;
1044 a = nsvg__div255((int)cover[0] * ca);
1048 r = nsvg__div255(cr * a);
1049 g = nsvg__div255(cg * a);
1050 b = nsvg__div255(cb * a);
1053 r += nsvg__div255(ia * (int)dst[0]);
1054 g += nsvg__div255(ia * (int)dst[1]);
1055 b += nsvg__div255(ia * (int)dst[2]);
1056 a += nsvg__div255(ia * (int)dst[3]);
1058 dst[0] = (unsigned char)r;
1059 dst[1] = (unsigned char)g;
1060 dst[2] = (unsigned char)b;
1061 dst[3] = (unsigned char)a;
1070 static void nsvg__rasterizeSortedEdges(NSVGrasterizer *r, float tx, float ty, float scale, NSVGcachedPaint* cache, char fillRule)
1072 NSVGactiveEdge *active = NULL;
1075 int maxWeight = (255 / NSVG__SUBSAMPLES); // weight per vertical scanline
1078 for (y = 0; y < r->height; y++) {
1079 memset(r->scanline, 0, r->width);
1082 for (s = 0; s < NSVG__SUBSAMPLES; ++s) {
1083 // find center of pixel for this scanline
1084 float scany = y*NSVG__SUBSAMPLES + s + 0.5f;
1085 NSVGactiveEdge **step = &active;
1087 // update all active edges;
1088 // remove all active edges that terminate before the center of this scanline
1090 NSVGactiveEdge *z = *step;
1091 if (z->ey <= scany) {
1092 *step = z->next; // delete from list
1093 // NSVG__assert(z->valid);
1094 nsvg__freeActive(r, z);
1096 z->x += z->dx; // advance to position for current scanline
1097 step = &((*step)->next); // advance through list
1101 // resort the list if needed
1105 while (*step && (*step)->next) {
1106 if ((*step)->x > (*step)->next->x) {
1107 NSVGactiveEdge* t = *step;
1108 NSVGactiveEdge* q = t->next;
1114 step = &(*step)->next;
1116 if (!changed) break;
1119 // insert all edges that start before the center of this scanline -- omit ones that also end on this scanline
1120 while (e < r->nedges && r->edges[e].y0 <= scany) {
1121 if (r->edges[e].y1 > scany) {
1122 NSVGactiveEdge* z = nsvg__addActive(r, &r->edges[e], scany);
1123 if (z == NULL) break;
1124 // find insertion point
1125 if (active == NULL) {
1127 } else if (z->x < active->x) {
1132 // find thing to insert AFTER
1133 NSVGactiveEdge* p = active;
1134 while (p->next && p->next->x < z->x)
1136 // at this point, p->next->x is NOT < z->x
1144 // now process all active edges in non-zero fashion
1146 nsvg__fillActiveEdges(r->scanline, r->width, active, maxWeight, &xmin, &xmax, fillRule);
1149 if (xmin < 0) xmin = 0;
1150 if (xmax > r->width-1) xmax = r->width-1;
1152 nsvg__scanlineSolid(&r->bitmap[y * r->stride] + xmin*4, xmax-xmin+1, &r->scanline[xmin], xmin, y, tx,ty, scale, cache);
1159 * In the original software, an function 'static void nsvg__unpremultiplyAlpha(unsigned char* image, int w, int h, int stride)' is implemented here.
1160 * We removed this function, as our renderer renders the pre-multiplied alpha format directly, so this process is not required.
1164 static void nsvg__initPaint(NSVGcachedPaint* cache, NSVGpaint* paint, float opacity)
1169 cache->type = paint->type;
1171 if (paint->type == NSVG_PAINT_COLOR) {
1172 cache->colors[0] = nsvg__applyOpacity(paint->color, opacity);
1176 grad = paint->gradient;
1178 cache->spread = grad->spread;
1179 memcpy(cache->xform, grad->xform, sizeof(float)*6);
1181 if (grad->nstops == 0) {
1182 for (i = 0; i < 256; i++)
1183 cache->colors[i] = 0;
1184 } if (grad->nstops == 1) {
1185 for (i = 0; i < 256; i++)
1186 cache->colors[i] = nsvg__applyOpacity(grad->stops[i].color, opacity);
1188 unsigned int ca, cb = 0;
1189 float ua, ub, du, u;
1192 ca = nsvg__applyOpacity(grad->stops[0].color, opacity);
1193 ua = nsvg__clampf(grad->stops[0].offset, 0, 1);
1194 ub = nsvg__clampf(grad->stops[grad->nstops-1].offset, ua, 1);
1195 ia = (int)(ua * 255.0f);
1196 ib = (int)(ub * 255.0f);
1197 for (i = 0; i < ia; i++) {
1198 cache->colors[i] = ca;
1201 for (i = 0; i < grad->nstops-1; i++) {
1202 ca = nsvg__applyOpacity(grad->stops[i].color, opacity);
1203 cb = nsvg__applyOpacity(grad->stops[i+1].color, opacity);
1204 ua = nsvg__clampf(grad->stops[i].offset, 0, 1);
1205 ub = nsvg__clampf(grad->stops[i+1].offset, 0, 1);
1206 ia = (int)(ua * 255.0f);
1207 ib = (int)(ub * 255.0f);
1209 if (count <= 0) continue;
1211 du = 1.0f / (float)count;
1212 for (j = 0; j < count; j++) {
1213 cache->colors[ia+j] = nsvg__lerpRGBA(ca,cb,u);
1218 for (i = ib; i < 256; i++)
1219 cache->colors[i] = cb;
1224 void nsvgRasterize(NSVGrasterizer* r,
1225 NSVGimage* image, float tx, float ty, float scale,
1226 unsigned char* dst, int w, int h, int stride)
1228 NSVGshape *shape = NULL;
1230 NSVGcachedPaint cache;
1238 if (w > r->cscanline) {
1240 r->scanline = (unsigned char*)realloc(r->scanline, w);
1241 if (r->scanline == NULL) return;
1244 for (i = 0; i < h; i++)
1245 memset(&dst[i*stride], 0, w*4);
1247 for (shape = image->shapes; shape != NULL; shape = shape->next) {
1248 if (!(shape->flags & NSVG_FLAGS_VISIBLE))
1251 if (shape->fill.type != NSVG_PAINT_NONE) {
1256 nsvg__flattenShape(r, shape, scale);
1258 // Scale and translate edges
1259 for (i = 0; i < r->nedges; i++) {
1262 e->y0 = (ty + e->y0) * NSVG__SUBSAMPLES;
1264 e->y1 = (ty + e->y1) * NSVG__SUBSAMPLES;
1268 qsort(r->edges, r->nedges, sizeof(NSVGedge), nsvg__cmpEdge);
1270 // now, traverse the scanlines and find the intersections on each scanline, use non-zero rule
1271 nsvg__initPaint(&cache, &shape->fill, shape->opacity);
1273 nsvg__rasterizeSortedEdges(r, tx,ty,scale, &cache, shape->fillRule);
1275 if (shape->stroke.type != NSVG_PAINT_NONE && (shape->strokeWidth * scale) > 0.01f) {
1280 nsvg__flattenShapeStroke(r, shape, scale);
1282 // dumpEdges(r, "edge.svg");
1284 // Scale and translate edges
1285 for (i = 0; i < r->nedges; i++) {
1288 e->y0 = (ty + e->y0) * NSVG__SUBSAMPLES;
1290 e->y1 = (ty + e->y1) * NSVG__SUBSAMPLES;
1294 qsort(r->edges, r->nedges, sizeof(NSVGedge), nsvg__cmpEdge);
1296 // now, traverse the scanlines and find the intersections on each scanline, use non-zero rule
1297 nsvg__initPaint(&cache, &shape->stroke, shape->opacity);
1299 nsvg__rasterizeSortedEdges(r, tx,ty,scale, &cache, NSVG_FILLRULE_NONZERO);
1304 * In the original file, the pre-multiplied alpha format is transformed to the convertional non-pre format.
1305 * We skip this process here, and render the pre-multiplied alpha format directly in our svg renderer.