Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
tree: 70bdfcb66b
Fetching contributors…

Cannot retrieve contributors at this time

664 lines (538 sloc) 12.806 kb
// 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;
}
Jump to Line
Something went wrong with that request. Please try again.