DIRECTORY GraphicsBasic, Graphics, CGVector, CGCubic, CGPath, UFCubicScan, Inline, Mopcodes, Real, Scaled ; UFCubicScanImpl: CEDAR MONITOR IMPORTS Graphics, CGPath, CGVector, Inline, Real, Scaled EXPORTS UFCubicScan = BEGIN OPEN UFCubicScan; BITAND: PROC[a, b: CARDINAL] RETURNS [CARDINAL] = TRUSTED MACHINE CODE {Mopcodes.zAND}; BITOR: PROC[a, b: CARDINAL] RETURNS [CARDINAL] = TRUSTED MACHINE CODE {Mopcodes.zOR}; BITXOR: PROC[a, b: CARDINAL] RETURNS [CARDINAL] = TRUSTED MACHINE CODE {Mopcodes.zXOR}; Floor8: PROC[a: CARDINAL] RETURNS [NAT] = INLINE {RETURN[Inline.BITSHIFT[a, -8]]}; Mid: PROC[a, b: CARDINAL] RETURNS [CARDINAL] = INLINE {RETURN[Inline.BITSHIFT[(a+b),-1]]}; Rec6: TYPE = RECORD[a,b,c,d,e,f: CARDINAL]; Vec: TYPE = RECORD [x, y: CARDINAL]; XValueFor: PUBLIC PROCEDURE [cubic: CubicRec, y: Scaled.Value] RETURNS [INTEGER] = { OPEN cubic; yRel: CARDINAL; IF y.Ceiling[] < ymin THEN RETURN [LAST[INTEGER]]; IF y.Floor[] > ymax THEN RETURN [FIRST[INTEGER]]; yRel _ y.MINUS[Scaled.FromInt[ymin]].Scale[8].Round[]; IF yRel <= y0 THEN IF yRel < y0 OR openAt0 THEN RETURN [LAST[INTEGER]]; IF yRel >= y3 THEN IF yRel > y3 OR openAt3 THEN RETURN [FIRST[INTEGER]]; WHILE y3 - y0 > 3 AND 0 # BITAND[ BITOR[BITXOR[x0, x1], BITOR[BITXOR[x1, x2], BITXOR[x2, x3]]], LAST[CARDINAL]-255 ] DO a: Vec _ [Mid[x0, x1], Mid[y0, y1]]; b: Vec _ [Mid[x1, x2], Mid[y1, y2]]; c: Vec _ [Mid[x2, x3], Mid[y2, y3]]; ab: Vec _ [Mid[a.x, b.x], Mid[a.y, b.y]]; bc: Vec _ [Mid[b.x, c.x], Mid[b.y, c.y]]; p: Vec _ [Mid[ab.x, bc.x], Mid[ab.y, bc.y]]; IF yRel=0 THEN { sqrt: REAL = Real.SqRt[d]; t0 _ (-b-sqrt)/2; t1 _ (-b+sqrt)/2; }; } ELSE IF d1#0.0 THEN t0 _ -d0/d1; t0 _ MIN[1.0, MAX[0.0, t0]]; t1 _ MIN[1.0, MAX[0.0, t1]]; IF t0 > t1 THEN {t: REAL _ t0; t0 _ t1; t1 _ t}; IF 0.0 < t0 AND t0 < t1 AND t1 < 1.0 THEN { low, middle, high: CGCubic.Bezier; [middle, high] _ SubDivide[bezier, t1]; [low, middle] _ SubDivide[middle, t0/t1]; Delta[low.b2.y-low.b3.y]; low.b2.y _ low.b3.y; Delta[middle.b1.y-middle.b0.y]; middle.b1.y _ middle.b0.y; Delta[middle.b2.y-middle.b3.y]; middle.b2.y _ middle.b3.y; Delta[high.b1.y-high.b0.y]; high.b1.y _ high.b0.y; AppendMonotoneBezier[devicePath, low]; AppendMonotoneBezier[devicePath, middle]; AppendMonotoneBezier[devicePath, high]; } ELSE IF t0 IN (0.0..1.0) OR t1 IN (0.0..1.0) THEN { low, high: CGCubic.Bezier; [low, high] _ SubDivide[bezier, IF t0 IN (0.0..1.0) THEN t0 ELSE t1]; Delta[low.b2.y-low.b3.y]; low.b2.y _ low.b3.y; Delta[high.b1.y-high.b0.y]; high.b1.y _ high.b0.y; AppendMonotoneBezier[devicePath, low]; AppendMonotoneBezier[devicePath, high]; } ELSE AppendMonotoneBezier[devicePath, bezier]; }; numberOfDeltas: INT _ 0; sumOfAbsDeltas: REAL _ 0.0; maxDelta: REAL _ 0.0; Delta: PROCEDURE [delta: REAL] = { numberOfDeltas _ numberOfDeltas + 1; sumOfAbsDeltas _ sumOfAbsDeltas + ABS[delta]; IF ABS[delta] > maxDelta THEN maxDelta _ ABS[delta]; }; DeltaStats: PROCEDURE RETURNS [n: INT, sum: REAL, max: REAL] = { n _ numberOfDeltas; sum _ sumOfAbsDeltas; max _ maxDelta; numberOfDeltas _ 0; sumOfAbsDeltas _ maxDelta _ 0.0; }; PushPath: PUBLIC PROCEDURE [ devicePath: DevicePath, path: GraphicsBasic.Path, map: PROC [GraphicsBasic.Vec] RETURNS [GraphicsBasic.Vec] _ NIL ] = { firstPoint, lastPoint: GraphicsBasic.Vec; started: BOOLEAN _ FALSE; outlineStart: NAT _ devicePath.length; Move: PROC [v: GraphicsBasic.Vec] = { IF started THEN Close[]; outlineStart _ devicePath.length; started _ TRUE; firstPoint _ lastPoint _ v; }; Line: PROC [v: GraphicsBasic.Vec] = { started _ TRUE; AppendBezier[devicePath, [lastPoint, Interpolate[0.3333333, lastPoint, v], Interpolate[0.6666667, lastPoint, v], v]]; lastPoint _ v; }; Curve: PROC [v1, v2, v3: GraphicsBasic.Vec] = { started _ TRUE; AppendBezier[devicePath, [lastPoint, v1, v2, v3]]; lastPoint _ v3; }; Close: PROC = { IF started AND lastPoint # firstPoint THEN Line[firstPoint]; FOR j: NAT IN [outlineStart..devicePath.length) DO i: NAT = IF j = outlineStart THEN devicePath.length-1 ELSE j-1; cubicI: Cubic = devicePath.seq[i]; cubicJ: Cubic = devicePath.seq[j]; iup: BOOLEAN = cubicI.ascending; jup: BOOLEAN = cubicJ.ascending; IF iup THEN cubicI.openAt3 _ FALSE ELSE cubicI.openAt0 _ NOT jup; IF jup THEN cubicJ.openAt0 _ iup ELSE cubicJ.openAt3 _ FALSE; ENDLOOP; started _ FALSE; }; CGPath.MapAndFilter[path, map, Move, Line, Curve, Close]; devicePath.numberOfOutlines _ devicePath.numberOfOutlines + 1; }; PopPath: PUBLIC PROCEDURE [devicePath: DevicePath] = { devicePath.numberOfOutlines _ devicePath.numberOfOutlines-1; WHILE devicePath.length > 0 AND devicePath.seq[devicePath.length-1].outlineNumber = devicePath.numberOfOutlines DO devicePath.length _ devicePath.length - 1; ENDLOOP; }; PathFromDevicePath: PROCEDURE [devicePath: DevicePath] RETURNS [path: GraphicsBasic.Path] = { started: BOOLEAN _ FALSE; lastX, lastY: REAL; path _ Graphics.NewPath[]; FOR i: NAT IN [0..devicePath.length) DO cubic: Cubic _ devicePath.seq[i]; X: PROC [xRel: CARDINAL] RETURNS [REAL] = {RETURN[cubic.xmin-0.5+(xRel/256.0)]}; Y: PROC [yRel: CARDINAL] RETURNS [REAL] = {RETURN[cubic.ymin+(yRel/256.0)]}; IF NOT started THEN { IF cubic.ascending THEN Graphics.MoveTo[path, X[cubic.x0], Y[cubic.y0]] ELSE Graphics.MoveTo[path, X[cubic.x3], Y[cubic.y3]]; started _ TRUE; }; [lastX, lastY] _ Graphics.LastPoint[path]; lastX _ lastX - X[IF cubic.ascending THEN cubic.x0 ELSE cubic.x3]; lastY _ lastY - Y[IF cubic.ascending THEN cubic.y0 ELSE cubic.y3]; IF lastX # 0.0 OR lastY # 0.0 THEN lastX _ lastY _ 0.0; -- Breakpoint here to check for broken paths IF cubic.ascending THEN Graphics.CurveTo[path, X[cubic.x1], Y[cubic.y1], X[cubic.x2], Y[cubic.y2], X[cubic.x3], Y[cubic.y3]] ELSE Graphics.CurveTo[path, X[cubic.x2], Y[cubic.y2], X[cubic.x1], Y[cubic.y1], X[cubic.x0], Y[cubic.y0]] ENDLOOP; }; ActivePieceTable: TYPE = REF ActivePieceTableRec; ActivePieceTableRec: TYPE = RECORD [ SEQUENCE maxLength: NAT OF ActivePieceRec ]; ActivePieceRec: TYPE = RECORD [ sortKey: INTEGER, pieceIndex: NAT ]; activePieceTable: ActivePieceTable _ NIL; AllocActivePieceTable: ENTRY PROC [size: NAT] RETURNS [a: ActivePieceTable] = { IF activePieceTable # NIL AND activePieceTable.maxLength >= size THEN {a _ activePieceTable; activePieceTable _ NIL} ELSE a _ NEW[ActivePieceTableRec[size]] }; FreeActivePieceTable: ENTRY PROC [a: ActivePieceTable] = { IF activePieceTable = NIL OR a.maxLength > activePieceTable.maxLength THEN activePieceTable _ a }; Sort: PROCEDURE [table: ActivePieceTable, start, startPlusLength: NAT] = { FOR i: NAT IN [start..startPlusLength) DO a: ActivePieceRec _ table[i]; b: ActivePieceRec; j: NAT _ i; WHILE j>0 AND a.sortKey < (b _ table[j-1]).sortKey DO table[j] _ b; j _ j-1 ENDLOOP; table[j] _ a; ENDLOOP; }; WrapTable: TYPE = REF WrapTableRec; WrapTableRec: TYPE = RECORD [ SEQUENCE maxLength: NAT OF INTEGER ]; wrapTable: WrapTable _ NIL; AllocWrapTable: ENTRY PROC [size: NAT] RETURNS [w: WrapTable] = { IF wrapTable # NIL AND wrapTable.maxLength >= size THEN {w _ wrapTable; wrapTable _ NIL} ELSE w _ NEW[WrapTableRec[size]] }; FreeWrapTable: ENTRY PROC [w: WrapTable] = { IF wrapTable = NIL OR w.maxLength > wrapTable.maxLength THEN wrapTable _ w }; ScanConvert: PUBLIC PROCEDURE [devicePath: DevicePath, LineProc: PROC[xmin, xmax, y: INTEGER]] = { length: NAT _ devicePath.length; outlines: NAT _ devicePath.numberOfOutlines; active: ActivePieceTable _ AllocActivePieceTable[length]; wrap: WrapTable _ AllocWrapTable[outlines]; firstActive, firstUnActivated: NAT _ 0; y: INTEGER _ FIRST[INTEGER]; FOR i: NAT IN [0..length) DO active[i] _ [sortKey: devicePath.seq[i].ymin, pieceIndex: i]; ENDLOOP; Sort[active, 0, length]; WHILE firstActive xStart THEN LineProc[xStart, a.sortKey, y]; nonZeroWrapCount _ nonZeroWrapCount - 1; }; wrap[k] _ w; ENDLOOP; ENDLOOP; FreeActivePieceTable[active]; FreeWrapTable[wrap]; }; END. ŠUFCubicScanImpl.mesa Created February 16, 1983 Edited by Michael Plass, March 2, 1983 2:00 pm Returns LAST[INTEGER] if y is below the piece, FIRST[INTEGER] if it is above, otherwise the x-intercept rounded to the nearest integer. Let garbage collector get it. Free old sequence here First find the coefficients of the y projection. Now find the coefficients of the derivative. Find where the derivative vanishes. Now break it up as needed This is used to monitor the effects of roundoff error in the computation of the monotone pieces. The globals are meant to be examined with the debugger. Useful for debugging the DevicePath building code Κ ˜Jšœ™J™J™.unitšΟk ˜ J˜J˜ J˜ J˜J˜Jšœ ˜ J˜J˜ J˜Jšœ˜J˜—šœœ˜Jšœ1˜8Jšœ ˜Jšœœœ ˜Jšœœœœœœœœ˜WJšœœœœœœœœ˜UJšœœœœœœœœ˜WJšΟnœœœœœœœœ ˜RJšžœœœœœœœœ ˜ZKšœœœœ˜+Kšœœœœ˜$š ž œœ œ$œœ˜TJš œœœœœK™‡Jšœ˜ Jšœœ˜Jš œœœœœ˜2Jš œœœœœ˜1Jšœ œ(˜6Jšœ œœ œ œœœœ˜GJšœ œœ œ œœœœ˜Hšœ ˜šœœ˜Jš œœ œœ œ ˜=Jšœœ˜Jšœ˜—Jšœ$˜$Jšœ$˜$Jšœ$˜$Jšœ)˜)Jšœ)˜)Jšœ,˜,Jšœ œ@˜PJšœœ œœ˜/Jšœ@˜DJšœ˜—Jšœ˜Jšœ˜—Kšž œœ!œuœ˜ΗKšœœœ0˜Kšžœ œœ!˜PJšœ œœ˜.Jš žœœœœœœ˜lJšœF˜FJšœF˜FJšœF˜FJšœ/˜/Jšœ/˜/Jšœ2˜2Jšœq˜wJ˜—šžœœ œœ˜?Jšœ œ˜ Jšœ˜Jšœ ˜ Jšœœ˜+J˜—šžœœ œ*œ˜HJ™—šžœœ œ˜4Jšœ˜Jšœ ˜ Jšœ˜—šžœ œ3˜VJšœ˜ Jš œœ.œ#œœ˜oJšœ œœ œ ˜*šœ-œ˜6šœœœ˜ Jšœœœœ.˜KJšœ˜—šœœœ˜'Jšœ˜Jš˜—Jšœ™Jšœ˜Jšœ˜—Jšœ*˜*Jšœ*˜*Jšœœ˜šœœœ˜JšœN˜NJšœœ˜J˜—Jšœ2˜2Jšœ œ1˜AJšœ˜Jšœ˜Jšœœœ˜SJšœœœ˜SJšœœœ˜SJšœœœ˜SJšœœ.˜AJšœœ.˜AJšœœ.˜AJšœœ.˜AJšœœ+˜FJšœ˜—šžœ œ.˜LJšœœœ9˜LJšœœœA˜TJšœœœ9˜LJšœœœA˜TJšœ˜Jšœœœœœœœ(˜kšœ˜Jšœ˜Jšœ$˜$Jšœ$˜$J˜—J˜—šžœ œ5˜Tšœ˜Jšœ<˜˜>Jšœ˜—šžœœ œ˜6Jšœ<˜<šœœQ˜rJšœ*˜*Jš˜—Jšœ˜—šžœ œœ˜]Jšœ1™1Jšœ œœ˜Jšœœ˜Jšœ˜šœœœ˜'Jšœ!˜!Jš žœœœœœœ˜PJš žœœœœœœ˜Lšœœ œ˜Jšœœ0˜GJšœ1˜5Jšœ œ˜J˜—Jšœ*˜*Jšœœœ œ ˜BJšœœœ œ ˜CJšœ œ œΟc,˜dJšœœe˜|Jšœe˜iJšœ˜—Jšœ˜—Kšœœœ˜1šœœœ˜$Jšœ œœ˜)J˜—šœœœ˜Jšœ œ˜Jšœ ˜J˜—Kšœ%œ˜)š žœœœœœ˜OJš œœœ$œ+œ˜tJšœœ˜'Jšœ˜—šžœœœ˜:šœœœ*˜JJšœ˜—Jšœ˜—šžœ œ3œ˜Jšœœœ˜)Jšœ˜Jšœ˜Jšœœ˜ Jšœœ&œœ˜TJšœ ˜ Jš˜—Jšœ˜—Kšœ œœ˜#šœœœ˜Jšœ œœ˜"J˜—Kšœœ˜š žœœœœœ˜AJš œ œœœœ˜XJšœœ˜ Jšœ˜—šž œœœ˜,šœ œœ#˜