DIRECTORY ImagerBasic USING [Bezier, Pair, PathMapType, Transformation], ImagerConic USING [ToCurves], ImagerScanConverter USING [CreatePath, DevicePath, DeviceRectangle], ImagerTransform USING [Contents, SingularValues, TransformationRec], ImagerStroke USING [StrokeEnd], Real USING [SqRt]; ImagerStrokeImpl: CEDAR PROGRAM IMPORTS ImagerConic, ImagerScanConverter, ImagerTransform, Real EXPORTS ImagerStroke = BEGIN StrokeEnd: TYPE = ImagerStroke.StrokeEnd; Pair: TYPE = ImagerBasic.Pair; Bezier: TYPE = ImagerBasic.Bezier; DevicePath: TYPE ~ ImagerScanConverter.DevicePath; DeviceRectangle: TYPE ~ ImagerScanConverter.DeviceRectangle; maxdepth: NAT _ 10; -- Used in Subdivide tolerance: REAL _ 0.5; -- Used in GenerateStroke, GenerateThinStroke Split: PUBLIC PROC [bezier: Bezier] RETURNS [firstHalf, secondHalf: Bezier] ~ { a,b,c,ab,bc,p: Pair; Mid: PROC[u,v: Pair] RETURNS[Pair] = 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: Pair, b: Pair] RETURNS[Pair] = INLINE { RETURN[[a.x+b.x,a.y+b.y]] }; Sub: PROC[a: Pair, b: Pair] RETURNS[Pair] = INLINE { RETURN[[a.x-b.x,a.y-b.y]] }; In: PROC[a: Pair, b: Pair, c: Pair] RETURNS[BOOLEAN] = INLINE { RETURN[a.x IN[b.x..c.x] AND a.y IN[b.y..c.y]] }; Min: PROC[a: Pair, b: Pair] RETURNS[Pair] = INLINE { RETURN[[MIN[a.x,b.x],MIN[a.y,b.y]]] }; Max: PROC[a: Pair, b: Pair] RETURNS[Pair] = INLINE { RETURN[[MAX[a.x,b.x],MAX[a.y,b.y]]] }; Dot: PROC[a: Pair, b: Pair] 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: Pair; oh: Pair=[0.5,0.5]; bh _ Add[Max[bezier.b0,bezier.b3],oh]; bl _ Sub[Min[bezier.b0,bezier.b3],oh]; IF NOT In[bezier.b1,bl,bh] OR NOT 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]; depth _ depth + 1; Subdiv[b1]; -- first half Subdiv[b2]; -- second half depth _ depth - 1; }; }; Subdiv[bezier]; }; DevicePathFromStroke: PUBLIC PROC [pathMap: ImagerBasic.PathMapType, pathData: REF, clientToDevice: ImagerBasic.Transformation, width: REAL, strokeEnd: StrokeEnd, closed: BOOLEAN, clipBox: DeviceRectangle, scratch: DevicePath] RETURNS [devicePath: DevicePath] = { cToD: ImagerTransform.TransformationRec _ ImagerTransform.Contents[clientToDevice]; FilterPath: ImagerBasic.PathMapType ~ { lp: Pair; FilterMove: PROC[p: Pair] ~ { move[lp _ p]; }; FilterLine: PROC[p: Pair] ~ { IF p#lp THEN line[lp _ p]; }; FilterCurve: PROC[p1, p2, p3: Pair] ~ { n: NAT _ 3; -- count position changes IF lp=p1 THEN n _ n-1; IF p1=p2 THEN n _ n-1; IF p2=p3 THEN n _ n-1; SELECT n FROM 0 => NULL; 1 => line[lp _ p3]; ENDCASE => curve[p1, p2, lp _ p3]; }; FilterConic: PROC[p1, p2: Pair, r: REAL] ~ { n: NAT _ 2; -- count position changes IF lp=p1 THEN n _ n-1; IF p1=p2 THEN n _ n-1; SELECT n FROM 0 => NULL; 1 => line[lp _ p2]; ENDCASE => conic[p1, lp _ p2, r]; }; pathMap[pathData, FilterMove, FilterLine, FilterCurve, FilterConic]; }; Xform: PROC [p: Pair] RETURNS [Pair] ~ {RETURN[[ cToD.a * p.x + cToD.b * p.y + cToD.c, cToD.d * p.x + cToD.e * p.y + cToD.f ]]}; GenPath: PROC [move: PROC[s, f: REAL], line: PROC[s, f: REAL], curve: PROC[s1, f1, s2, f2, s3, f3: REAL]] = { sv: Pair ~ ImagerTransform.SingularValues[clientToDevice]; AlmostCircular: PROC[p: Pair] RETURNS[BOOL] ~ { min: REAL ~ MIN[p.x, p.y]; max: REAL ~ MAX[p.x, p.y]; epsilon: REAL ~ 0.1; RETURN[ABS[min/max-1] yMax THEN RETURN; IF MIN[p0.x, p1.x] > xMax THEN RETURN; IF p1.x < p0.x THEN {t: Pair _ p0; p0 _ p1; p1 _ t}; IF p1.x-p0.x >= ABS[p1.y-p0.y] THEN { move[p0.x-0.5, p0.y]; line[p0.x, p0.y+0.5]; line[p1.x, p1.y+0.5]; line[p1.x+0.5, p1.y]; line[p1.x, p1.y-0.5]; line[p0.x, p0.y-0.5]; } ELSE { IF p1.y < p0.y THEN {t: Pair _ p0; p0 _ p1; p1 _ t}; move[p0.x, p0.y-0.5]; line[p0.x-0.5, p0.y]; line[p1.x-0.5, p1.y]; line[p1.x, p1.y+0.5]; line[p1.x+0.5, p1.y]; line[p0.x+0.5, p0.y]; }; }; MappedCurve: PROC[p1, p2, p3: Pair] = { IF MAX[mp.x, p1.x, p2.x, p3.x] < xMin THEN {mp _ p3; RETURN}; IF MAX[mp.y, p1.y, p2.y, p3.y] < yMin THEN {mp _ p3; RETURN}; IF MIN[mp.y, p1.y, p2.y, p3.y] > yMax THEN {mp _ p3; RETURN}; IF MIN[mp.x, p1.x, p2.x, p3.x] > xMax THEN {mp _ p3; RETURN}; Subdivide[bezier: [mp, p1, p2, p3], vertex: MappedLine, tolerance: tolerance]; }; Close: PROC = { IF closed THEN MappedLine[sp]; }; pathMap[pathData, Move, Line, Curve, Conic]; IF NOT first THEN Close[]; }; Mag: PROC[v: Pair] RETURNS [REAL] = INLINE { RETURN [Real.SqRt[v.x * v.x + v.y * v.y]] }; Normalize: PROC[v: Pair] RETURNS [Pair] = INLINE { m: REAL _ Mag[v]; IF m = 0 THEN RETURN[v] ELSE RETURN[[v.x/m, v.y/m]] }; Midpoint: PROC[a, b: Pair] RETURNS[Pair] = INLINE { RETURN[[(a.x+b.x)/2, (a.y+b.y)/2]] }; Miter: PROC[v1, v2: Pair] RETURNS[REAL] = { s, a: REAL; v3: Pair; 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: Pair, epsilon: REAL] RETURNS[b: BOOL] = { dx, dy: REAL; d1, d, bl, bh: Pair; oh: Pair = [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[pathMap: ImagerBasic.PathMapType, pathData: REF, width: REAL, closed: BOOLEAN, ends: StrokeEnd, map: PROC[Pair] RETURNS[Pair], moveTo, lineTo: PROC[s, f: REAL]] = { 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: Pair; -- control points for current segment u0, u3: Pair; -- half width normal vectors at b0, b3 p0, q0, p3, q3: Pair; -- corners of stroke boundary for current segment MiterFlags: TYPE = RECORD[p, q: BOOLEAN]; m0, m3: MiterFlags; fb0, fb1, fb2, fb3, fu0, fu3, fp3, fq3: Pair; -- saved values for deferred segment fline: BOOLEAN; fm3: MiterFlags; -- ditto begin: BOOLEAN; defer: BOOLEAN; firstVertex: BOOLEAN _ TRUE; vertex: PROC[p: Pair] ~ {IF firstVertex THEN {firstVertex _ FALSE; moveTo[p.x, p.y]} ELSE lineTo[p.x, p.y]}; close: PROC ~ INLINE {firstVertex _ TRUE}; Cap: PROC[b, d, p, q: Pair] = { SELECT ends FROM butt => { }; square => { v0: Pair _ [b.x-d.y, b.y+d.x]; v3: Pair _ [b.x+d.y, b.y-d.x]; v1: Pair _ [v0.x+d.x, v0.y+d.y]; v2: Pair _ [v3.x+d.x, v3.y+d.y]; vertex[p]; vertex[map[v1]]; vertex[map[v2]]; vertex[q]; close[]; }; round => { bz: Bezier; v0, v1, v2, v3: Pair; f: REAL = 0.5522848; -- 4*(sqrt2-1)/3 a: Pair _ [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: Pair] RETURNS[Pair] = { d: Pair _ Sub[b, a]; u: Pair _ Normalize[d]; RETURN[[-u.y*h, u.x*h]]; }; ComputeP: PROC[b, u: Pair] RETURNS[Pair] = INLINE { RETURN[map[[b.x+u.x, b.y+u.y]]] }; ComputeQ: PROC[b, u: Pair] RETURNS[Pair] = INLINE { RETURN[map[[b.x-u.x, b.y-u.y]]] }; DoCurve: PROC[b0, b1, b2, b3: Pair, p0, p3: Pair, depth: NAT _ 0] = { b01: Pair _ Midpoint[b0, b1]; b12: Pair _ Midpoint[b1, b2]; b23: Pair _ Midpoint[b2, b3]; b11: Pair _ Midpoint[b01, b12]; b22: Pair _ Midpoint[b12, b23]; bm: Pair _ Midpoint[b11, b22]; -- middle point on curve (at t=1/2) um: Pair _ HNormal[b11, b22]; -- half width normal at bm pm: Pair _ 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: Pair, 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: Pair _ [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[p: Pair] = {IF first THEN first _ FALSE ELSE Close[]; b3 _ p; begin _ TRUE }; Line: PROC[p: Pair] = { u0: Pair _ HNormal[b3, p]; EmitPreviousSegment[u0]; b3 _ p; u3 _ u0; line _ TRUE; }; Curve: PROC[p1, p2, p3: Pair] = { u0: Pair _ (IF p1#b3 THEN HNormal[b3, p1] ELSE HNormal[b3, p2]); EmitPreviousSegment[u0]; b1 _ p1; b2 _ p2; b3 _ p3; line _ FALSE; u3 _ (IF b2#b3 THEN HNormal[b2, b3] ELSE HNormal[b1, b2]); }; Conic: PROC[p1, p2: Pair, r: REAL] = { ImagerConic.ToCurves[b3, p1, p2, r, Curve]; }; 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] }; }; pathMap[pathData, Move, Line, Curve, Conic]; IF NOT first THEN Close[]; }; END. ÊImagerStrokeImpl.mesa Last changed by: Michael Plass, February 16, 1984 10:34:32 am PST Doug Wyatt, July 3, 1984 1:12:03 pm PDT data: REF, move: PROC[p: Pair], line: PROC[p: Pair], curve: PROC[p1, p2, p3: Pair], conic: PROC[p1, p2: Pair, r: REAL] Transforms (x, y) to (s, f) Three point flatness test: returns a vector of length halfWidth normal to the direction from a to b trajectory is a single point just pick an arbitrary direction for end caps ʘJšœ™J™šœ™J™0Jšœ'™'—J˜šÏk ˜ Jšœ œ-˜>Jšœ œ ˜Jšœœ+˜DJšœœ/˜DJšœ œ ˜Jšœœ˜J˜—Jšœœ˜Jšœ8˜?Jšœ ˜Jšœ˜J˜Jšœ œ˜)Jšœœ˜Jšœœ˜"Jšœ œ"˜2Jšœœ'˜šœœ˜šœœ˜J˜Jšœœ˜—šœ˜J˜J˜-Jšœœœ˜J˜Jšœœ˜—Jšœœ˜—šœ˜šœœ˜Jšœœ˜ šœœœ˜Jšœœ˜ šœœ˜J˜-Jšœœœ˜—Jšœœœ˜J˜—šœ˜Jšœœ ˜J˜)Jšœœ,œœ˜JJšœ,œœ˜BJ˜—J˜—Jšœœœ˜šœœ˜J˜+J˜'Jšœœ˜—Jšœ˜J˜—J˜,J˜—Jšœœœ˜JšŸœœ œœ œœœ˜XšŸœœ ˜J˜J˜Jšœœ˜J˜—šŸœœ˜!Jšœ œœœ˜@J˜Jšœ"œ˜(Jšœœœœ˜:J˜—šŸœœœ˜&Jšœ+˜+J˜—šŸœœ˜šœœ˜Jšœ™Jšœœž œ˜šœ˜Jšœ-™-J˜ J˜J˜J˜J˜J˜—J˜—šœœœ˜Jšœœ ž1˜KJšœž-˜GJ˜+J˜'Jšœž"˜1J˜—Jšœœ$˜HJ˜—Jšœ,˜,Jšœœœ ˜J˜J˜—Jšœ˜J˜—…—12C