<> <> <> <> DIRECTORY ImagerBasic, Real USING [SqRt], ScanConverter, ImagerMasks, ImagerStroke, Scaled; ImagerCGStrokeImpl: CEDAR PROGRAM IMPORTS Real, ScanConverter, ImagerMasks, Scaled EXPORTS ImagerStroke = { <> MaskThinSegment: PUBLIC PROC [dest, clipper: ImagerMasks.Mask, sFrom, fFrom, sTo, fTo: Scaled.Value, function: PACKED ARRAY [0..1] OF [0..1]] ~ { sInt, fInt: INTEGER _ 0; sDelta, fDelta: INT _ 0; signDelta: INTEGER _ 0; e: INT _ 0; ForwardS: PROC ~ INLINE { IF sDelta < fDelta THEN ERROR; sInt _ sInt + 1; IF (e _ e - fDelta) < 0 THEN {fInt _ fInt + signDelta; e _ e + sDelta}; }; ReverseS: PROC ~ INLINE { IF sDelta < fDelta THEN ERROR; sInt _ sInt - 1; IF (e _ e + fDelta) >= sDelta THEN {fInt _ fInt - signDelta; e _ e - sDelta}; }; ForwardF: PROC ~ INLINE { IF sDelta > fDelta THEN ERROR; fInt _ fInt + 1; IF (e _ e - sDelta) < 0 THEN {sInt _ sInt + signDelta; e _ e + fDelta}; }; ReverseF: PROC ~ INLINE { IF sDelta > fDelta THEN ERROR; fInt _ fInt - 1; IF (e _ e + sDelta) >= fDelta THEN {sInt _ sInt - signDelta; e _ e - fDelta}; }; IF sFrom.GREATER[sTo] THEN {t: Scaled.Value _ sFrom; sFrom _ sTo; sTo _ t; t _ fFrom; fFrom _ fTo; fTo _ t}; }; <> Path: TYPE = ImagerBasic.Path; StrokeEnds: TYPE = ImagerBasic.StrokeEnds; Vec, Pair: TYPE = ImagerBasic.Pair; Bezier: TYPE = ImagerBasic.Bezier; maxdepth: NAT = 10; Split: PUBLIC PROC[bezier: Bezier] RETURNS[Bezier, Bezier] = { a,b,c,ab,bc,p: Vec; Mid: PROC[u,v: Vec] RETURNS[Vec] = INLINE { RETURN[[(u.x+v.x)/2,(u.y+v.y)/2]] }; a _ Mid[bezier.b0,bezier.b1]; b _ Mid[bezier.b1,bezier.b2]; c _ Mid[bezier.b2,bezier.b3]; ab _ Mid[a,b]; bc _ Mid[b,c]; p _ Mid[ab,bc]; RETURN[[bezier.b0, a, ab, p],[p, bc, c, bezier.b3]]; }; Add: PROC[a: Vec, b: Vec] RETURNS[Vec] = INLINE { RETURN[[a.x+b.x,a.y+b.y]] }; Sub: PROC[a: Vec, b: Vec] RETURNS[Vec] = INLINE { RETURN[[a.x-b.x,a.y-b.y]] }; In: PROC[a: Vec, b: Vec, c: Vec] RETURNS[BOOLEAN] = INLINE { RETURN[a.x IN[b.x..c.x] AND a.y IN[b.y..c.y]] }; Min: PROC[a: Vec, b: Vec] RETURNS[Vec] = INLINE { RETURN[[MIN[a.x,b.x],MIN[a.y,b.y]]] }; Max: PROC[a: Vec, b: Vec] RETURNS[Vec] = INLINE { RETURN[[MAX[a.x,b.x],MAX[a.y,b.y]]] }; Dot: PROC[a: Vec, b: Vec] RETURNS[REAL] = INLINE { RETURN[a.x*b.x+a.y*b.y] }; FlatBezier: PUBLIC PROC[bezier: Bezier, epsilon: REAL] RETURNS[BOOLEAN] = { dx,dy: REAL; d1,d2,d,bl,bh: Vec; oh: Vec=[0.5,0.5]; bh _ Add[Max[bezier.b0,bezier.b3],oh]; bl _ Sub[Min[bezier.b0,bezier.b3],oh]; IF ~In[bezier.b1,bl,bh] OR ~In[bezier.b2,bl,bh] THEN RETURN[FALSE]; d1 _ Sub[bezier.b1,bezier.b0]; d2 _ Sub[bezier.b2,bezier.b0]; d _ Sub[bezier.b3,bezier.b0]; dx _ ABS[d.x]; dy _ ABS[d.y]; IF dx+dy < 1 THEN RETURN[TRUE]; IF dy < dx THEN { dydx: REAL _ d.y/d.x; RETURN[ABS[d2.y-d2.x*dydx]=maxdepth OR FlatBezier[b, tolerance] THEN vertex[b.b3] ELSE { b1, b2: Bezier; [b1, b2] _ Split[b]; Subdivide[b1, vertex, tolerance, depth+1]; -- first half Subdivide[b2, vertex, tolerance, depth+1]; -- second half }; }; MaskFromStroke: PUBLIC PROC [path: Path, clientToDevice: ImagerBasic.Transformation, width: REAL, strokeEnds: StrokeEnds, closed: BOOLEAN, sMin, sMax: INTEGER] RETURNS [mask: ImagerMasks.Mask] = { devicePath: ScanConverter.DevicePath _ ScanConverter.Allocate[]; firstVertex: BOOLEAN _ TRUE; Xform: PROC [p: Pair] RETURNS [Pair] ~ {RETURN[[ <> clientToDevice.d * p.x + clientToDevice.e * p.y + clientToDevice.f, clientToDevice.a * p.x + clientToDevice.b * p.y + clientToDevice.c ]]}; GenPath: PROC [move: PROC[Pair], line: PROC[Pair], curve: PROC[Pair, Pair, Pair]] = { GenerateStroke[path, width, closed, strokeEnds, Xform, move, line]; }; Runs: PROC[run: PROC[s, fMin: INTEGER, fSize: NAT], repeat: PROC[timesToRepeatScanline: NAT]] ~ { BoxFromScanConverter: PROC [x, y, w, h: INTEGER] = { IF h # 1 THEN ERROR; run[s: y, fMin: x, fSize: w]; }; devicePath.ScanConvert[BoxFromScanConverter, sMin, sMax]; }; devicePath.PushPath[GenPath]; mask _ ImagerMasks.Create[Runs]; devicePath.Release[]; }; Mag: PROC[v: Vec] RETURNS [REAL] = INLINE { RETURN [Real.SqRt[v.x * v.x + v.y * v.y]] }; Normalize: PROC[v: Vec] RETURNS [Vec] = INLINE { m: REAL _ Mag[v]; IF m = 0 THEN RETURN[v] ELSE RETURN[[v.x/m, v.y/m]] }; Midpoint: PROC[a, b: Vec] RETURNS[Vec] = INLINE { RETURN[[(a.x+b.x)/2, (a.y+b.y)/2]] }; Miter: PROC[v1, v2: Vec] RETURNS[REAL] = { s, a: REAL; v3: Vec; v3 _ Normalize[Add[v1, v2]]; s _ Dot[[v1.y, -v1.x], v3]; -- compute sin of angle a _ s / Real.SqRt[1 - s*s]; -- compute horz vec for angle between v1 & v3 RETURN[a]; }; <> Flat: PROC[v1, v2, v3: Vec, epsilon: REAL] RETURNS[b: BOOL] = { dx, dy: REAL; d1, d, bl, bh: Vec; oh: Vec = [0.5, 0.5]; bh _ Add[Max[v1, v3], oh]; bl _ Sub[Min[v1, v3], oh]; IF NOT In[v2, bl, bh] THEN RETURN[FALSE]; d1 _ Sub[v2, v1]; d _ Sub[v3, v1]; dx _ ABS[d.x]; dy _ ABS[d.y]; IF dx + dy < 1 THEN RETURN[TRUE]; IF dy < dx THEN { dydx: REAL _ d.y / d.x; RETURN[ABS[d1.y - d1.x * dydx] < epsilon] } ELSE { dxdy: REAL _ d.x / d.y; RETURN[ABS[d1.x - d1.y * dxdy] < epsilon] }; }; GenerateStroke: PUBLIC PROC[path: Path, width: REAL, closed: BOOLEAN, ends: StrokeEnds, map: PROC[Vec] RETURNS[Vec], moveTo, lineTo: PROC[Vec]] = { h: REAL _ ABS[width]/2; -- half width hsq: REAL _ h*h; smallSin: REAL _ 0.001*hsq; line: BOOLEAN; -- is current segment a line? b0, b1, b2, b3: Vec; -- control points for current segment u0, u3: Vec; -- half width normal vectors at b0, b3 p0, q0, p3, q3: Vec; -- corners of stroke boundary for current segment MiterFlags: TYPE = RECORD[p, q: BOOLEAN]; m0, m3: MiterFlags; fb0, fb1, fb2, fb3, fu0, fu3, fp3, fq3: Vec; -- saved values for deferred segment fline: BOOLEAN; fm3: MiterFlags; -- ditto begin, defer: BOOLEAN; firstVertex: BOOLEAN _ TRUE; vertex: PROC[p: Vec] ~ {IF firstVertex THEN {firstVertex _ FALSE; moveTo[p]} ELSE lineTo[p]}; close: PROC ~ INLINE {firstVertex _ TRUE}; Cap: PROC[b, d, p, q: Vec] = { SELECT ends FROM butt => { }; square => { v0: Vec _ [b.x-d.y, b.y+d.x]; v3: Vec _ [b.x+d.y, b.y-d.x]; v1: Vec _ [v0.x+d.x, v0.y+d.y]; v2: Vec _ [v3.x+d.x, v3.y+d.y]; vertex[p]; vertex[map[v1]]; vertex[map[v2]]; vertex[q]; close[]; }; round => { tolerance: REAL = 1.0; bz: Bezier; v0, v1, v2, v3: Vec; f: REAL = 0.5522848; -- 4*(sqrt2-1)/3 a: Vec _ [f*d.x, f*d.y]; v0 _ [b.x-d.y, b.y+d.x]; v3 _ [b.x+d.x, b.y+d.y]; v1 _ [v0.x+a.x, v0.y+a.y]; v2 _ [v3.x-a.y, v3.y+a.x]; bz.b0 _ p; bz.b1 _ map[v1]; bz.b2 _ map[v2]; bz.b3 _ map[v3]; vertex[p]; Subdivide[bz, vertex, tolerance]; v0 _ v3; v3 _ [b.x+d.y, b.y-d.x]; v1 _ [v0.x+a.y, v0.y-a.x]; v2 _ [v3.x+a.x, v3.y+a.y]; bz.b0 _ bz.b3; bz.b1 _ map[v1]; bz.b2 _ map[v2]; bz.b3 _ q; Subdivide[bz, vertex, tolerance]; close[]; }; ENDCASE => ERROR; }; HNormal: PROC[a, b: Vec] RETURNS[Vec] = { <> d: Vec _ Sub[b, a]; u: Vec _ Normalize[d]; RETURN[[-u.y*h, u.x*h]]; }; ComputeP: PROC[b, u: Vec] RETURNS[Vec] = INLINE { RETURN[map[[b.x+u.x, b.y+u.y]]] }; ComputeQ: PROC[b, u: Vec] RETURNS[Vec] = INLINE { RETURN[map[[b.x-u.x, b.y-u.y]]] }; tolerance: REAL = 1.0; DoCurve: PROC[b0, b1, b2, b3: Vec, p0, p3: Vec, depth: NAT _ 0] = { b01: Vec _ Midpoint[b0, b1]; b12: Vec _ Midpoint[b1, b2]; b23: Vec _ Midpoint[b2, b3]; b11: Vec _ Midpoint[b01, b12]; b22: Vec _ Midpoint[b12, b23]; bm: Vec _ Midpoint[b11, b22]; -- middle point on curve (at t=1/2) um: Vec _ HNormal[b11, b22]; -- half width normal at bm pm: Vec _ map[Add[bm, um]]; -- point on stroke edge IF depth>0 -- always divide at least once -- AND Flat[p0, pm, p3, tolerance] THEN vertex[p3] ELSE { DoCurve[b0, b01, b11, bm, p0, pm, depth+1]; -- first half DoCurve[bm, b22, b23, b3, pm, p3, depth+1]; -- second half }; }; EmitSegment: PROC = { IF NOT m0.p THEN p0 _ ComputeP[b0, u0]; IF NOT m0.q THEN q0 _ ComputeQ[b0, u0]; IF NOT m3.p THEN p3 _ ComputeP[b3, u3]; IF NOT m3.q THEN q3 _ ComputeQ[b3, u3]; vertex[p0]; IF line THEN vertex[p3] ELSE DoCurve[b0, b1, b2, b3, p0, p3]; vertex[q3]; IF line THEN vertex[q0] ELSE DoCurve[b3, b2, b1, b0, q3, q0]; close[]; }; EmitPreviousSegment: PROC[u4: Vec, miter: BOOLEAN _ TRUE] = { IF begin THEN { IF closed THEN { fb0 _ b3; fu0 _ u4; defer _ TRUE } ELSE { u3 _ u4; p3 _ ComputeP[b3, u3]; q3 _ ComputeQ[b3, u3]; m3 _ [TRUE,TRUE]; Cap[b3, [-u3.y, u3.x], q3, p3]; defer _ FALSE }; begin _ FALSE } ELSE { IF miter THEN { sin: REAL _ u3.x*u4.y-u3.y*u4.x; IF ABS[sin]0 THEN { p3 _ ComputeP[b3, u3]; q3 _ ComputeQ[b3, u3]; m3 _ [TRUE,TRUE] } ELSE m3 _ [FALSE,FALSE]; } ELSE { f: REAL _ hsq/sin; r: Vec _ [f*(u4.y-u3.y), f*(u3.x-u4.x)]; IF sin<0 THEN { p3 _ map[[b3.x+r.x, b3.y+r.y]]; m3 _ [p: TRUE, q: FALSE] } ELSE { q3 _ map[[b3.x-r.x, b3.y-r.y]]; m3 _ [p: FALSE, q: TRUE] }; }; } ELSE m3 _ [FALSE,FALSE]; IF defer THEN { fb1 _ b1; fb2 _ b2; fb3 _ b3; fline _ line; fu3 _ u3; fp3 _ p3; fq3 _ q3; fm3 _ m3; defer _ FALSE } ELSE EmitSegment[]; }; b0 _ b3; u0 _ u4; p0 _ p3; q0 _ q3; m0 _ m3; }; first: BOOLEAN _ TRUE; Move: PROC[v: Vec] = {IF first THEN first _ FALSE ELSE Close[]; b3 _ v; begin _ TRUE }; Line: PROC[v: Vec] = { u0: Vec _ HNormal[b3, v]; EmitPreviousSegment[u0]; b3 _ v; u3 _ u0; line _ TRUE; }; Curve: PROC[v1, v2, v3: Vec] = { u0: Vec _ (IF v1#b3 THEN HNormal[b3, v1] ELSE HNormal[b3, v2]); EmitPreviousSegment[u0]; b1 _ v1; b2 _ v2; b3 _ v3; line _ FALSE; u3 _ (IF b2#b3 THEN HNormal[b2, b3] ELSE HNormal[b1, b2]); }; Close: PROC = { IF begin THEN { <> IF closed THEN { --ignore-- } ELSE { <> u3 _ [0, h]; p3 _ ComputeP[b3, u3]; q3 _ ComputeQ[b3, u3]; Cap[b3, [-h, 0], q3, p3]; Cap[b3, [h, 0], p3, q3]; }; } ELSE IF closed THEN { IF b3#fb0 THEN Line[fb0]; -- if necessary, extend a line to the first point EmitPreviousSegment[fu0]; -- emit the segment ending at the first point b1 _ fb1; b2 _ fb2; b3 _ fb3; line _ fline; u3 _ fu3; p3 _ fp3; q3 _ fq3; m3 _ fm3; EmitSegment[]; -- emit the deferred first segment } ELSE { EmitPreviousSegment[u3, FALSE]; Cap[b3, [u3.y, -u3.x], p3, q3] }; }; path.generateProc[path, Move, Line, Curve]; IF NOT first THEN Close[]; }; }.