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