DIRECTORY IPCubic USING [Flat, Split], IPImagerBasic USING [Bezier, Pair, StrokeEnds, Transformation], IPStroke USING [], IPTransform USING [Transform], Real USING [SqRt]; IPStrokeImpl: CEDAR PROGRAM IMPORTS IPCubic, IPTransform, Real EXPORTS IPStroke = BEGIN OPEN IPImagerBasic; maxdepth: NAT = 10; Subdivide: PROC[b: Bezier, vertex: PROC[Pair], tolerance: REAL _ 1.5, depth: NAT _ 0] = { IF depth>=maxdepth OR IPCubic.Flat[b, tolerance] THEN vertex[b.b3] ELSE { b1, b2: Bezier; [b1, b2] _ IPCubic.Split[b]; Subdivide[b1, vertex, tolerance, depth+1]; -- first half Subdivide[b2, vertex, tolerance, depth+1]; -- second half }; }; 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] }; 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[ gen: PROC[move: PROC[Pair], line: PROC[Pair], curve: PROC[Pair, Pair, Pair]], T: Transformation, width: REAL, closed: BOOLEAN, ends: StrokeEnds, move: PROC[Pair], line: PROC[Pair], curve: PROC[Pair, Pair, Pair] ] = { map: PROC[p: Pair] RETURNS[Pair] = INLINE { RETURN[IPTransform.Transform[T, p]] }; h: REAL = ABS[width]/2; -- half width hsq: REAL = h*h; smallSin: REAL = 0.001*hsq; SegType: TYPE = {line, curve}; type: SegType; -- is current segment a line or curve? 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 ftype: SegType; fm3: MiterFlags; -- ditto begin, defer: BOOLEAN; 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]; move[p]; line[map[v1]]; line[map[v2]]; line[q]; }; round => { tolerance: REAL = 1.0; 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]; move[p]; Subdivide[bz, line, 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, line, tolerance]; }; 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]]] }; tolerance: REAL = 1.0; 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 line[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]; move[p0]; IF type=line THEN line[p3] ELSE DoCurve[b0, b1, b2, b3, p0, p3]; line[q3]; IF type=line THEN line[q0] ELSE DoCurve[b3, b2, b1, b0, q3, q0]; }; 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; ftype _ type; fu3 _ u3; fp3 _ p3; fq3 _ q3; fm3 _ m3; defer _ FALSE } ELSE EmitSegment[]; }; b0 _ b3; u0 _ u4; p0 _ p3; q0 _ q3; m0 _ m3; }; started: BOOL _ FALSE; Move: PROC[v: Pair] = { IF started THEN Close[] ELSE started _ TRUE; b3 _ v; begin _ TRUE; }; Line: PROC[v: Pair] = { u0: Pair; IF NOT started THEN Move[[0,0]]; EmitPreviousSegment[u0 _ HNormal[b3, v]]; b3 _ v; u3 _ u0; type _ line; }; Curve: PROC[v1, v2, v3: Pair] = { u0: Pair; IF NOT started THEN Move[[0,0]]; EmitPreviousSegment[u0 _ IF v1#b3 THEN HNormal[b3, v1] ELSE HNormal[b3, v2]]; b1 _ v1; b2 _ v2; b3 _ v3; type _ curve; u3 _ (IF b2#b3 THEN HNormal[b2, b3] ELSE HNormal[b1, b2]); }; Close: PROC = { IF begin THEN { IF closed THEN { --ignore-- } ELSE { -- just pick an arbitrary direction for end caps 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; type _ ftype; 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] }; }; gen[Move, Line, Curve]; IF started THEN Close[]; }; END. ╬IPStrokeImpl.mesa Last changed by: Doug Wyatt, April 11, 1983 2:18 pm Three point flatness test. returns a vector of length halfWidth normal to the direction from a to b trajectory is a single point Э╩ mШheadЪЬЩЪЬЩJЪЬ"Щ"ЧJШЪ╧k Ш JЪЬЭЬШJЪЬЭЬ,Ш?JЪЬ ЭЬШJЪЬЭЬ ШJЪЬЭЬШЧJШЧЪЬЭЬЭШJЪЭЬШ"JЪЭЬ ШJЪЬЭЬЭЬШJШJЪЬ ЭЬШJШЪ ╧n ЬЭЬЭЬЭЬЭЬ ШYJЪЭЬЭЬЭЬ ШBЪЭЬШJШJЪЬ+╧c Ш8JЪЬ+ЯШ9JШЧJШЧJШЪЮЬЭЬЭЬШ)JЪЬЭЬЭЬШ'ЧЪЮЬЭЬЭЬШ)JЪЬЭЬЭЬШ'ЧЪЮЬЭЬЭЬЭЬШ4JЪЬЭЬЭЬЭЬЭЬЭЬШ;ЧЪЮЬЭЬЭЬШ)JЪ ЬЭЬЭЬЭЬ ЭЬШ1ЧЪЮЬЭЬЭЬШ)JЪ ЬЭЬЭЬЭЬ ЭЬШ1ЧЪЮЬЭЬЭЬЭЬШ)JЪЬЭЬЭЬШ%ЧЪ ЮЬЭЬ ЭЬЭЬЭЬШ,JЪЭЬ#Ш)JШЧЪЮ ЬЭЬ ЭЬ ЭЬШ2JЪЬЭЬ ШJЪ ЭЬЭЬЭЬЭЬЭЬШ3JШЧЪЮЬЭЬ ЭЬ ЭЬШ3JЪЭЬШ%ЧJШЪЮЬЭЬЭЬЭЬШ+JЪЬЭЬШJЪЬШJЪЬЯШ3JЪЬЯ-ШIJЪЭЬШ JШЧJШЪ ЮЬЭЬЭЬЭЬЭЬШ@JЪЬЩJЪЬЭЬШ JШJШJЪЬШJЪЬШJЪ ЭЬЭЬЭЬЭЬЭЬШ)JЪЬШJЪЬШJЪЬЭЬЭЬШJЪЭЬ ЭЬЭЬЭЬШ!JЪ ЭЬ ЭЬ ЭЬЭЬЭЬ!ШUJЪЭЬ ЭЬЭЬЭЬ"ШKJШЧJШЪЮЬЭЬЭЬШJЪ ЬЭЬЭЬЭЬЭЬШMJЪЭЬЭЬ ЭЬШBJЪЬЭЬЭЬЭЬШAJЪЬШJЪЬЭЬ ЭЬ ЭЬЭЬЭЬШRJЪЬЭЬЭЬЯ Ш%JЪЬЭЬШJЪЬ ЭЬ ШJЪЬ ЭЬШJЪЬЯ&Ш5JЪЬЯ%Ш;JЪЬЯ&Ш4JЪЬЯ1ШGJЪЬЭЬЭЬЭЬШ)JШJЪЬ.Я$ШRJЪЬ!ЯШ)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Ъ ЮЬЭЬ ЭЬ ЭЬЭЬШVJЪ ЮЬЭЬ ЭЬ ЭЬЭЬШVJЪЬЭЬШЪЮЬЭЬ,ЭЬ ШEJШJШJШJШJШJЪЬЯ#ШBJЪЬЯШ8JЪЬЯШ4ЪЭЬ Я!Ш,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ЪЭЬЭЬ,ЭЬЭЬШJJЪЭЬ,ЭЬЭЬШBJШЧJШЧJЪЭЬЭЬЭЬШЪЭЬЭЬШJШ+JШ'JЪЬЭЬШЧJЪЭЬШJШЧJШ,JШЧJЪЬ ЭЬЭЬШЪЮЬЭЬ ШJЪЭЬ ЭЬ ЭЬЭЬШ,JЪЬЭЬШJЪЬШЧЪЮЬЭЬ ШJШ JЪЭЬЭЬ ЭЬ Ш JШ)JЪЬШJШЧЪЮЬЭЬШ!JЪЬ Ш JЪЭЬЭЬ ЭЬ Ш JЪЬЭЬЭЬЭЬШMJЪЬ(Ш(JЪЬЭЬЭЬЭЬШ:JШЧЪЮЬЭЬШЪЭЬЭЬШJЪЬЩJЪЭЬЭЬЯ ЬШЪЭЬЯ0Ш7JШJШJШJШJШJШЧJШЧЪЭЬЭЬЭЬШJЪЭЬЭЬЯ1ШKJЪЬЯ-ШGJШ+JШ'JЪЬЯ"Ш1JШЧJЪЭЬЭЬ$ШHJШЧJЪЬШJЪЭЬ ЭЬ ШJШЧJШJЪЭЬШЧЧЕЧp&л