DIRECTORY ImagerPath USING [Filter, PathProc, Transform], ImagerScanConverter USING [CreatePath, DevicePath, DeviceRectangle], ImagerStroke USING [Bezier, StrokeStyle], ImagerTransformation USING [SingularValues, Transform, Transformation], Real USING [SqRt], Vector2 USING [VEC]; ImagerStrokeImpl: CEDAR PROGRAM IMPORTS ImagerPath, ImagerScanConverter, ImagerTransformation, Real EXPORTS ImagerStroke = BEGIN VEC: TYPE = Vector2.VEC; Bezier: TYPE = ImagerStroke.Bezier; StrokeStyle: TYPE = ImagerStroke.StrokeStyle; DevicePath: TYPE ~ ImagerScanConverter.DevicePath; DeviceRectangle: TYPE ~ ImagerScanConverter.DeviceRectangle; Transformation: TYPE ~ ImagerTransformation.Transformation; PathProc: TYPE ~ ImagerPath.PathProc; 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: 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 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[ pathProc: ImagerPath.PathProc, pathData: REF, width: REAL, style: StrokeStyle, closed: BOOLEAN, clientToDevice: Transformation, clipBox: DeviceRectangle, scratch: DevicePath ] RETURNS [devicePath: DevicePath] = { outerPathData: REF ~ pathData; transformedStroke: ImagerPath.PathProc ~ { sv: VEC ~ ImagerTransformation.SingularValues[clientToDevice]; AlmostCircular: PROC[p: VEC] 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: VEC _ p0; p0 _ p1; p1 _ t}; IF p1.x-p0.x >= ABS[p1.y-p0.y] THEN { moveTo[[p0.x-0.5, p0.y]]; lineTo[[p0.x, p0.y+0.5]]; lineTo[[p1.x, p1.y+0.5]]; lineTo[[p1.x+0.5, p1.y]]; lineTo[[p1.x, p1.y-0.5]]; lineTo[[p0.x, p0.y-0.5]]; } ELSE { IF p1.y < p0.y THEN {t: VEC _ p0; p0 _ p1; p1 _ t}; moveTo[[p0.x, p0.y-0.5]]; lineTo[[p0.x-0.5, p0.y]]; lineTo[[p1.x-0.5, p1.y]]; lineTo[[p1.x, p1.y+0.5]]; lineTo[[p1.x+0.5, p1.y]]; lineTo[[p0.x+0.5, p0.y]]; }; }; Curve: PROC[p1, p2, p3: VEC] = { 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: Line, tolerance: tolerance]; }; Close: PROC = { IF closed THEN Line[sp] }; ImagerPath.Transform[pathProc: pathProc, pathData: pathData, m: transformation, moveTo: Move, lineTo: Line, curveTo: Curve, close: Close]; }; 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: PROC[pathProc: PathProc, pathData: REF, width: REAL, style: StrokeStyle, closed: BOOL, transformation: Transformation, moveTo: PROC[VEC], lineTo: PROC[VEC]] = { map: PROC[p: VEC] RETURNS[VEC] ~ INLINE { RETURN[transformation.Transform[p]] }; 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: BOOLEAN; 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 style FROM 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[]; }; butt => NULL; ENDCASE => { 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[]; }; }; 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]]] }; 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; }; Move: PROC[p: VEC] = { b3 _ p; begin _ TRUE }; Line: PROC[p: VEC] = { u0: VEC _ HNormal[b3, p]; EmitPreviousSegment[u0]; b3 _ p; u3 _ u0; line _ TRUE; }; Curve: PROC[p1, p2, p3: VEC] = { u0: VEC _ (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]); }; 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] }; }; ImagerPath.Filter[pathProc: pathProc, pathData: pathData, moveTo: Move, lineTo: Line, curveTo: Curve, close: Close]; }; END. bImagerStrokeImpl.mesa Copyright c 1984 Xerox Corporation. All rights reserved. Michael Plass, February 16, 1984 10:34:32 am PST Doug Wyatt, October 9, 1984 8:54:09 am PDT 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šœ Ïmœ.™9J™0Jšœ*™*—J˜šÏk ˜ Jšœ žœ˜/Jšœžœ+˜DJšœ žœ˜)Jšœžœ-˜GJšœžœ˜Jšœžœžœ˜J˜—Jšœžœž˜Jšžœ<˜CJšžœ ˜Jšœž˜J˜Jšžœžœ žœ˜Jšœžœ˜#Jšœ žœ˜-Jšœ žœ"˜2Jšœžœ'˜š  œžœžœžœžœ˜.Jš œžœžœžœžœ ˜5Jšœ žœ˜Jšžœžœ˜J˜—šžœžœžœ˜EJšœ,˜,JšœA˜AJšœ˜—šžœ˜Jšœ,˜,JšœK˜KJšœ ˜ —Jšœ˜—šœ,˜,Jšœ'žœ˜+Jšœžœ&˜9—J˜J˜—š œžœžœ˜;Jšœžœ;˜GJš œžœžœ žœžœ˜)JšœžœŸ*˜3JšœžœŸ ˜Jšœžœ˜Jšœžœ˜(Jšœžœ˜Jšœžœ˜(Jš œžœžœ˜%š œžœžœ˜Jšœžœ˜ Jšœžœ˜ Jšœ˜Jšžœžœžœžœ˜&Jšžœžœžœžœ˜&Jšžœžœžœžœ˜&Jšžœžœžœžœ˜&Jšžœ žœžœ˜3šžœžœ žœ˜%Jšœ˜Jšœ˜Jšœ˜Jšœ˜Jšœ˜Jšœ˜Jšœ˜—šžœ˜Jšžœ žœžœ˜3Jšœ˜Jšœ˜Jšœ˜Jšœ˜Jšœ˜Jšœ˜Jšœ˜—J˜—š œžœ žœ˜ Jšžœžœ žœ žœ˜=Jšžœžœ žœ žœ˜=Jšžœžœ žœ žœ˜=Jšžœžœ žœ žœ˜=JšœH˜HJ˜—Jš œžœžœžœ ˜*šœO˜OJšœ:˜:—Jšœ˜J˜—š  œžœžœžœžœžœ˜+Jšžœ#˜)J˜J˜—š   œžœžœžœžœžœ˜0Jšœžœ ˜Jš žœžœžœžœžœ˜3J˜J˜—š  œžœžœžœžœžœ˜1Jšžœ˜%J˜—š  œžœ žœžœžœ˜*Jšœžœžœ˜Jšœ˜JšœŸ˜3JšœŸ-˜IJšžœ˜ J˜J˜—Jšœ™š  œžœ žœ žœžœžœ˜?Jšœžœ˜ Jšœžœ˜Jšœžœ˜Jšœ˜Jšœ˜Jš žœžœžœžœžœ˜)Jšœ˜Jšœ˜Jšœžœ žœ˜Jšžœ žœžœžœ˜!Jš žœ žœ žœžœžœ!˜UJšžœ žœžœžœ"˜KJ˜J˜—š œžœžœ˜7Jšœžœžœ!˜NJš œžœžœ žœžœ˜)Jš œžœžœžœžœžœžœ ˜PJšœžœžœ Ÿ ˜%Jšœžœ˜Jšœ žœ ˜JšœžœŸ˜,JšœžœŸ%˜:JšœžœŸ&˜3JšœžœŸ1˜FJšœ žœžœžœ˜)J˜Jšœ(žœŸ$˜QJšœžœŸ˜)Jšœžœ˜Jšœžœ˜Jšœ žœžœ˜Jš œžœžœžœ žœžœ žœ ˜]Jšœžœžœžœ˜*š œžœ žœ˜šžœž˜˜ Jšœžœ˜Jšœžœ˜Jšœžœ˜Jšœžœ˜J˜@J˜—Jšœžœ˜ šžœ˜ J˜ Jšœžœ˜JšœžœŸ˜%Jšœžœ˜J˜J˜J˜J˜J˜=J˜,J˜J˜J˜J˜J˜;J˜*J˜——J˜—š  œžœžœžœžœ˜)JšœH™HJšœžœ ˜Jšœžœ˜Jšžœ˜J˜—Jš œžœžœžœžœžœžœ˜TJš œžœžœžœžœžœžœ˜Tš  œžœžœ žœ žœ ˜CJšœžœ˜Jšœžœ˜Jšœžœ˜Jšœžœ˜Jšœžœ˜JšœžœŸ#˜AJšœžœŸ˜7JšœžœŸ˜3šžœ Ÿ!˜,Jšžœžœ ˜/—šžœ˜Jšœ,Ÿ ˜9Jšœ,Ÿ˜:J˜—J˜—š  œžœ˜Jšžœžœžœ˜'Jšžœžœžœ˜'Jšžœžœžœ˜'Jšžœžœžœ˜'J˜ Jšžœžœ žœ!˜=J˜ Jšžœžœ žœ!˜=J˜J˜—š  œžœžœ žœžœ˜=šžœžœ˜šžœžœ˜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šœžœ˜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˜—šœ9˜9Jšœ:˜:—J˜J˜—Jšžœ˜J˜—…—,Î>$