// This file is distributed under a BSD license. See LICENSE.txt for details. #include "genvector.hpp" #include "genbitmap.hpp" #include "_start.hpp" #include <stdlib.h> static const sInt OVERSAMPLE_YF = 4; // more is probably overkill static const sInt OVERSAMPLE_Y = 1<<OVERSAMPLE_YF; /****************************************************************************/ struct Vec2 { sF32 x,y; Vec2() { } Vec2(sF32 _x,sF32 _y) : x(_x), y(_y) { } void mid(const Vec2 &a,const Vec2 &b) { x = 0.5f * (a.x + b.x); y = 0.5f * (a.y + b.y); } }; __forceinline sInt sMulShift12(sInt var_a,sInt var_b) { __asm { mov eax, var_a imul var_b shrd eax, edx, 12 } } __forceinline sInt sDivShift12(sInt var_a,sInt var_b) { __asm { mov eax, var_a mov edx, eax shl eax, 12 sar edx, 20 idiv var_b } } /****************************************************************************/ enum PathCommand { PATH_CUBIC=0, // most common one PATH_LINE, PATH_MOVE, PATH_END }; static const sU8 pathCommandSize[] = { // match commands in PathCommand 3, 1, 1, 0 }; struct Path { sArray2<sU8> cmds; sArray2<Vec2> points; const sChar* parseError; sInt parseErrorPos; sBool parse(const sChar *str); sU8 *exportData(sInt &size) const; void importData(const sU8 *data); private: const sChar* text; const sChar* cp; void skipWhitespace(); sBool expect(sChar ch); sBool floatv(sF32& v); sBool vec2d(Vec2& v); sBool command(sInt cmd, sInt params); sBool error(sInt backtrack, const sChar* msg); }; /****************************************************************************/ sBool Path::parse(const sChar *str) { Vec2 first; text = cp = str; parseError = 0; parseErrorPos = 0; points.Clear(); cmds.Clear(); skipWhitespace(); while(*cp) { sChar cmd = *cp++; skipWhitespace(); sInt pcmd = -1, pparm; switch(cmd) { case 'M': pcmd = PATH_MOVE; pparm = 1; break; // moveto case 'L': pcmd = PATH_LINE; pparm = 1; break; // lineto case 'C': pcmd = PATH_CUBIC; pparm = 3; break; // cubic case 'z': case 'Z': pcmd = PATH_LINE; pparm = 0; break; // closepath default: return error(1, "unknown command"); } if(pcmd != -1 && !command(pcmd, pparm)) return false; if(cmd == 'M') first = points[points.Count-1]; else if(cmd == 'z' || cmd == 'Z') // close *points.Add() = first; skipWhitespace(); } return true; } static sU32 deltaCode(sInt val, sInt& last) { sInt delta = val-last; last = val; return sAbs(delta) * 2 - (delta < 0); } static sInt deltaDecode(sU32 val, sInt& last) { sInt v = (val >> 1) ^ -sInt(val & 1); return last += v; } static void scatterStore(sU8* dst, sInt stride, sU32 v) { dst[0*stride] = (v >> 0) & 0xff; dst[1*stride] = (v >> 8) & 0xff; dst[2*stride] = (v >> 16) & 0xff; dst[3*stride] = (v >> 24) & 0xff; } static sU32 gatherRead(const sU8* src, sInt stride) { return src[0*stride] + (src[1*stride] << 8) + (src[2*stride] << 16) + (src[3*stride] << 24); } sU8 *Path::exportData(sInt &size) const { // commands sArray2<sU8> data = cmds; *data.Add() = PATH_END; // points sInt pts = points.Count; data.Resize(data.Count + 4 * 2 * pts); sU8* ptd = data.Array + cmds.Count + 1; sInt lx = 0, ly = 0; for(sInt i=0;i<pts;i++) { scatterStore(ptd++, 2*pts, deltaCode(points[i].x*8, lx)); scatterStore(ptd++, 2*pts, deltaCode(points[i].y*8, ly)); } // detach data from array sU8* ptr = data.Array; size = data.Count; data.Count = data.Alloc = 0; data.Array = 0; return ptr; } void Path::importData(const sU8 *data) { // commands sInt pts = 0; const sU8* ptr = data; while(*ptr != PATH_END) pts += pathCommandSize[*ptr++]; cmds.Resize(ptr-data); sCopyMem(cmds.Array, data, ptr-data); ptr++; // points points.Resize(pts); sInt lx = 0, ly = 0; sF32 scalef = sFPow(2.0f, GenBitmapTextureSizeOffset - 3.0f); for(sInt i=0;i<pts;i++) { points[i].x = deltaDecode(gatherRead(ptr++, 2*pts), lx) * scalef; points[i].y = deltaDecode(gatherRead(ptr++, 2*pts), ly) * scalef; } } void Path::skipWhitespace() { const sChar* rcp = cp; while(*rcp == ' ' || *rcp == '\t' || *rcp == '\r' || *rcp == '\n') rcp++; cp = rcp; } sBool Path::expect(sChar ch) { return (*cp++ != ch) ? error(1, "unexpected character") : sTRUE; } sBool Path::floatv(sF32 &v) { const sChar* oldcp = cp; v = strtod(cp, (char**) &cp); return (cp == oldcp) ? error(0, "float expected") : sTRUE; } sBool Path::vec2d(Vec2& v) { if(!floatv(v.x) || !expect(',') || !floatv(v.y)) return sFALSE; skipWhitespace(); return sTRUE; } sBool Path::command(sInt cmd, sInt params) { *cmds.Add() = cmd; while(params--) { Vec2 v; if(!vec2d(v)) return sFALSE; else *points.Add() = v; } return sTRUE; } sBool Path::error(sInt backtrack, const sChar *msg) { points.Clear(); cmds.Clear(); parseError = msg; parseErrorPos = cp - text - backtrack; return sFALSE; } /****************************************************************************/ class VectorRasterizer { public: VectorRasterizer(GenBitmap *target); void renderPath(const Path& path, sU32 color, sBool evenOddRule); private: struct Edge { Edge *prev, *next; // linked list sInt x,dx; // 16.16 fixed point sInt y1,y2; // actual pixels (y1<y2) sInt dir; bool operator < (const Edge& b) const { return y1 < b.y1 || y1 == b.y1 && x < b.x; } }; Edge ehead, *head; sArray2<Edge> edges; sInt minY, maxY; GenBitmap *target; void line(const Vec2& a, const Vec2& b); void cubic(const Vec2& a, const Vec2& b, const Vec2& c, const Vec2& d); void submitPath(const Path& path); void edgeSiftDown(sInt n,sInt k); void sortEdges(); void rasterizeAll(sU32 color, sBool evenOddRule); }; /****************************************************************************/ VectorRasterizer::VectorRasterizer(GenBitmap *target_) : target(target_) { head = &ehead; head->x = -0x7fffffff - 1; // VC warns for literal -0x80000000 head->dx = 0; } void VectorRasterizer::renderPath(const Path& path, sU32 color, sBool evenOddRule) { minY = target->YSize * OVERSAMPLE_Y; maxY = 0; submitPath(path); rasterizeAll(color, evenOddRule); edges.Clear(); } void VectorRasterizer::line(const Vec2& a, const Vec2& b) { int x1 = int(a.x * 4096), y1 = int(a.y * 4096 * OVERSAMPLE_Y); int x2 = int(b.x * 4096), y2 = int(b.y * 4096 * OVERSAMPLE_Y); int dir = 1; int dx; if(y1 > y2) { sSwap(x1, x2); sSwap(y1, y2); dir = -1; } int iy1 = (y1 + 0xfff) >> 12, iy2 = (y2 + 0xfff) >> 12; if(iy1 == iy2) // horizontal edge, skip return; if(y2 - y1 >= 4096) dx = sDivShift12(x2-x1, y2-y1); else dx = sMulShift(x2-x1, (1<<28)/(y2-y1)); // y clip if(y1 < 0) { x1 += sMulShift12(dx, 0 - y1); y1 = iy1 = 0; } if(y2 > OVERSAMPLE_Y * (target->YSize << 12)) { x2 += sMulShift12(dx, OVERSAMPLE_Y * (target->YSize << 12) - y2); y2 = OVERSAMPLE_Y * (target->YSize << 12); iy2 = OVERSAMPLE_Y * target->YSize; } if(iy1 >= iy2) // if degenerate after clip, just skip return; // build edge Edge *e = edges.Add(); e->prev = e->next = 0; e->x = x1 + sMulShift12(dx, (iy1 << 12) - y1); // subpixel correction? of course. e->dx = dx; e->y1 = iy1; e->y2 = iy2; e->dir = dir; minY = sMin(minY, iy1); maxY = sMax(maxY, iy2); } void VectorRasterizer::cubic(const Vec2& a, const Vec2& b, const Vec2& c, const Vec2& d) { if(sFAbs(a.x + c.x - 2.0f * b.x) + sFAbs(a.y + c.y - 2.0f * b.y) + sFAbs(b.x + d.x - 2.0f * c.x) + sFAbs(b.y + d.y - 2.0f * c.y) <= 1.0f) line(a, d); else { Vec2 ab,bc,cd,abc,bcd,abcd; ab.mid(a,b); bc.mid(b,c); cd.mid(c,d); abc.mid(ab,bc); bcd.mid(bc,cd); abcd.mid(abc,bcd); cubic(a, ab, abc, abcd); cubic(abcd, bcd, cd, d); } } void VectorRasterizer::submitPath(const Path& path) { Vec2 cur(0, 0); int cmdi = 0, pti = 0; while(cmdi < path.cmds.Count) { sInt cmd = path.cmds[cmdi++]; switch(cmd) { case PATH_LINE: line(cur, path.points[pti]); break; case PATH_CUBIC: cubic(cur, path.points[pti+0], path.points[pti+1], path.points[pti+2]); break; } pti += pathCommandSize[cmd]; cur = path.points[pti-1]; } } void VectorRasterizer::edgeSiftDown(sInt n,sInt k) { Edge v = edges[k]; while(k < (n>>1)) { sInt j = k*2+1; if(j+1 < n && edges[j] < edges[j+1]) j++; if(!(v < edges[j])) break; edges[k] = edges[j]; k = j; } edges[k] = v; } void VectorRasterizer::sortEdges() { // heapsort. sInt n = edges.Count; for(sInt k=n/2-1;k>=0;k--) edgeSiftDown(n,k); while(--n > 0) { sSwap(edges[0],edges[n]); edgeSiftDown(n,0); } } void VectorRasterizer::rasterizeAll(sU32 color, sBool evenOddRule) { head->prev = head->next = head; sortEdges(); Edge *ei = &edges[0], *ee = &edges[edges.Count]; sInt windingMask = evenOddRule ? 1 : -1; sInt endY = (maxY + OVERSAMPLE_Y - 1) & -OVERSAMPLE_Y; sInt width = target->XSize; sU8* cover = new sU8[width * OVERSAMPLE_Y]; sU8* cp = cover + (minY & (OVERSAMPLE_Y - 1)) * width; sU64* ip = target->Data + (minY / OVERSAMPLE_Y) * width; sU64 col64 = GetColor64(color); sSetMem(cover, 0, width * OVERSAMPLE_Y); for(sInt y=minY;y<endY;y++) { Edge *e, *en; // advance all x coordinates, remove "expired" edges, re-sort active edge list on the way for(e = head->next; e != head; e = en) { en = e->next; if(y < e->y2) // edge is still active { e->x += e->dx; while(e->x < e->prev->x) // keep everything sorted { // move one step towards the beginning Edge* ep = e->prev; ep->prev->next = e; e->next->prev = ep; e->prev = ep->prev; ep->next = e->next; e->next = ep; ep->prev = e; } } else // deactivate edge { e->prev->next = e->next; e->next->prev = e->prev; } } // insert new edges if there are any e = head; while(ei != ee && ei->y1 == y) { // search insert position while(e != head->prev && e->next->x <= ei->x) e = e->next; // insert new edge behind e ei->prev = e; ei->next = e->next; e->next->prev = ei; e->next = ei; ++ei; } // go through new active edge list and generate spans on the way sInt winding = 0, lx; for(e = head->next; e != head; e = e->next) { if(winding & windingMask) { // clip sInt x0 = sMax(lx, 0); sInt x1 = sMin(e->x, width << 12); if(x1 > x0) { // generate span sInt ix0 = (x0 + 0xfff) >> 12; sInt ix1 = (x1 + 0xfff) >> 12; if(ix0 == ix1) // very thin part cp[ix0-1] = sMin(cp[ix0-1] + ((x1 - x0) >> 4), 255); else // at least one pixel thick { if(x0 & 0xfff) cp[ix0-1] = sMin(cp[ix0-1] + ((~x0 & 0xfff) >> 4), 255); if(x1 & 0xfff) { ix1--; cp[ix1] = sMin(cp[ix1] + ((x1 & 0xfff) >> 4), 255); } while(ix0 < ix1) cp[ix0++] = 255; } } } winding += e->dir; lx = e->x; } // advance and resolve cp += width; if((y & (OVERSAMPLE_Y - 1)) == OVERSAMPLE_Y - 1) // row complete { for(sInt x=0;x<width;x++) { sU32 sum = 0; for(sInt s=0;s<OVERSAMPLE_Y;s++) sum += cover[x+s*width]; sum <<= 8 - OVERSAMPLE_YF; sum += (sum >> (8 + OVERSAMPLE_YF)); Fade64(ip[x], ip[x], col64, sum); } sSetMem(cover, 0, width * OVERSAMPLE_Y); cp = cover; ip += width; } } delete[] cover; } /****************************************************************************/ static sBool CheckBitmap(GenBitmap *&bm) { GenBitmap *oldbm = bm; if(bm==0) return 1; if(bm->ClassId!=KC_BITMAP) return 1; if(bm->Data==0) return 1; if(bm->RefCount>1) { bm = (GenBitmap *)oldbm->Copy(); oldbm->Release(); } return 0; } GenBitmap * __stdcall Bitmap_VectorPath(KOp *op,GenBitmap *bm,sU32 color,sInt flags,sChar *filename) { const sU8* data; data = op->GetBlobData(); #if !sPLAYER if(!data) { sChar* pathText = sSystem->LoadText(filename); if(!pathText) { sDPrintF("couldn't open input file!\n"); return 0; } Path path; sBool result = path.parse(pathText); delete[] pathText; if(!result) { sDPrintF("error while processing '%s': %s at byte %d.\n", filename, path.parseError, path.parseErrorPos); return 0; } // export sInt size; data = path.exportData(size); op->SetBlob(data, size); } #endif if(!data || CheckBitmap(bm)) return 0; // read path Path path; path.importData(data); // render! VectorRasterizer raster(bm); raster.renderPath(path, color, flags & 1); return bm; }