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