<> <> <Documentation>MultiGravity.tioga.>> <> <> <> <> <<>> DIRECTORY CodeTimer, Cubic2, CubicPaths, GGAlign, GGBasicTypes, GGCaret, GGCircles, GGCoreTypes, GGInterfaceTypes, GGModelTypes, GGMultiGravity, GGParent, GGScene, GGSegmentTypes, GGSliceOps, GGState, GGUtility, Lines2d, Real, RealFns, Rope, Vectors2d; GGMultiGravityImpl: CEDAR PROGRAM IMPORTS CodeTimer, CubicPaths, GGAlign, GGCaret, GGCircles, GGParent, GGScene, GGSliceOps, GGState, Lines2d, RealFns, Vectors2d EXPORTS GGMultiGravity = BEGIN AlignBag: TYPE = REF AlignBagObj; AlignBagObj: TYPE = GGInterfaceTypes.AlignBagObj; AlignmentCircle: TYPE = GGInterfaceTypes.AlignmentCircle; AlignmentLine: TYPE = GGInterfaceTypes.AlignmentLine; AlignmentPoint: TYPE = REF AlignmentPointObj; AlignmentPointObj: TYPE = GGInterfaceTypes.AlignmentPointObj; Arc: TYPE = GGBasicTypes.Arc; Bezier: TYPE = Cubic2.Bezier; BezierRef: TYPE = REF Bezier; Caret: TYPE = GGInterfaceTypes.Caret; Circle: TYPE = GGBasicTypes.Circle; Edge: TYPE = GGBasicTypes.Edge; FeatureCycler: TYPE = REF FeatureCyclerObj; FeatureCyclerObj: TYPE = GGInterfaceTypes.FeatureCyclerObj; FeatureData: TYPE = REF FeatureDataObj; FeatureDataObj: TYPE = GGModelTypes.FeatureDataObj; GGData: TYPE = GGInterfaceTypes.GGData; GoodPoint: TYPE = REF GoodPointObj; GoodPointObj: TYPE = GGInterfaceTypes.GoodPointObj; GravityType: TYPE = GGInterfaceTypes.GravityType; JointGenerator: TYPE = GGModelTypes.JointGenerator; Line: TYPE = GGCoreTypes.Line; NearVertexEdgeAndFaces: TYPE = REF NearVertexEdgeAndFacesObj; NearVertexEdgeAndFacesObj: TYPE = GGInterfaceTypes.NearVertexEdgeAndFacesObj; Point: TYPE = GGBasicTypes.Point; PointPairAndDone: TYPE = GGModelTypes.PointPairAndDone; PointPairGenerator: TYPE = GGModelTypes.PointPairGenerator; Scene: TYPE = GGModelTypes.Scene; Segment: TYPE = GGSegmentTypes.Segment; SegmentGenerator: TYPE = GGModelTypes.SegmentGenerator; Sequence: TYPE = GGModelTypes.Sequence; Slice: TYPE = GGModelTypes.Slice; SliceDescriptor: TYPE = GGModelTypes.SliceDescriptor; SliceDescriptorObj: TYPE = GGModelTypes.SliceDescriptorObj; TriggerBag: TYPE = REF TriggerBagObj; TriggerBagObj: TYPE = GGInterfaceTypes.TriggerBagObj; Vector: TYPE = GGBasicTypes.Vector; BestPoints: TYPE = REF BestPointsObj; BestPointsObj: TYPE = RECORD [ size: NAT, max, min: REAL, maxIndex: NAT, bestTossed: REAL, -- the distance of the closest object that has been thrown away dTol: REAL, -- min + s innerR: REAL, -- find all curves within this radius even if they are not neighbors of the nearest s: REAL, -- the size of neighborhoods. BestPoints should contain all objects that have been seen such that min <= dist(o, q) <= min+s, unless BestPoints overflows. overflow: BOOL, points: SEQUENCE len: NAT OF GoodPoint]; BestFaces: TYPE = REF BestFacesObj; BestFacesObj: TYPE = RECORD [ size: NAT, maxPriority, minPriority: INT, minIndex: NAT, bestPriorityTossed: INT, priorityTol: INT, -- the farthest overlap level that we are interested in overflow: BOOL, faces: SEQUENCE len: NAT OF GoodPoint]; MultiGravityPool: TYPE = REF MultiGravityPoolObj; MultiGravityPoolObj: TYPE = RECORD [ bestpoints: BestPoints, bestcurves: BestPoints, bestfaces: BestFaces ]; Problem: PUBLIC SIGNAL [msg: Rope.ROPE] = CODE; <> << [Artwork node; type 'ArtworkInterpress on' to command tool] >> <> Map: PUBLIC PROC [testPoint: Point, t: REAL, alignBag: AlignBag, sceneBag: TriggerBag, ggData: GGData, intersections: BOOL ¬ FALSE] RETURNS [resultPoint: Point, normal: Vector, feature: FeatureData, hitData: REF ANY] = { <> ENABLE UNWIND => { ggData.multiGravityPool ¬ NewMultiGravityPool[]; <> }; gravityType: GravityType ¬ GGState.GetGravityType[ggData]; CodeTimer.StartInt[$MultiMap, $Gargoyle]; IF GGState.GetGravity[ggData] THEN { SELECT gravityType FROM pointsPreferred => [resultPoint, normal, feature, hitData] ¬ PointsPreferred[testPoint, t, alignBag, sceneBag, ggData, intersections]; linesPreferred, facesPreferred => [resultPoint, normal, feature, hitData] ¬ LinesPreferred[testPoint, t, alignBag, sceneBag, ggData]; ENDCASE => ERROR; } ELSE { resultPoint ¬ testPoint; feature ¬ NIL; normal ¬ [0,-1]; }; CodeTimer.StopInt[$MultiMap, $Gargoyle]; }; <<>> PointsPreferred: PUBLIC PROC [testPoint: Point, t: REAL, alignBag: AlignBag, sceneBag: TriggerBag, ggData: GGData, intersections: BOOL ¬ FALSE] RETURNS [resultPoint: Point, normal: Vector, feature: FeatureData, hitData: REF ANY] = { <> count: NAT; nearVEF: NearVertexEdgeAndFaces; [nearVEF, count] ¬ MultiPointsPreferred[testPoint, t, alignBag, sceneBag, ggData, intersections]; IF count = 0 THEN RETURN [testPoint, [0,-1], NIL, NIL]; IF count = 1 THEN RETURN PrepareWinner[nearVEF, 0] ELSE { <> neighborCount: NAT ¬ 1; s: REAL = 0.072; -- 1/1000 inches nearestDist: REAL ¬ -1; nearestDist ¬ nearVEF[0].dist; FOR i: NAT IN [1..count) DO IF nearVEF[i].dist - nearestDist < s THEN neighborCount ¬ neighborCount + 1; ENDLOOP; IF neighborCount = 1 THEN RETURN PrepareWinner[nearVEF, 0]; <> <> FOR i: NAT IN [0..neighborCount) DO IF nearVEF[i].featureData.type = slice THEN { RETURN PrepareWinner[nearVEF, i]; }; REPEAT FINISHED => RETURN PrepareWinner[nearVEF, 0]; ENDLOOP; }; }; LinesPreferred: PUBLIC PROC [testPoint: Point, t: REAL, alignBag: AlignBag, sceneBag: TriggerBag, ggData: GGData] RETURNS [resultPoint: Point, normal: Vector, feature: FeatureData, hitData: REF ANY] = { <> nearVEF: NearVertexEdgeAndFaces; count: NAT; [nearVEF, count] ¬ MultiLinesPreferred[testPoint, t, alignBag, sceneBag, ggData]; IF count = 0 THEN RETURN [testPoint, [0,-1], NIL, NIL]; IF count = 1 THEN RETURN PrepareWinner[nearVEF, 0] ELSE { <> <> <<1) Prefer scene objects to alignment lines.>> <<2) Prefer points to lines.>> <> bestSceneObject ¬ -1;>> RETURN PrepareWinner[nearVEF, 0]; }; }; FacesPreferred: PUBLIC PROC [testPoint: Point, t: REAL, alignBag: AlignBag, sceneBag: TriggerBag, ggData: GGData] RETURNS [resultPoint: Point, normal: Vector, feature: FeatureData, hitData: REF ANY] = { <> nearVEF: NearVertexEdgeAndFaces; count: NAT; [nearVEF, count] ¬ MultiFacesPreferred[testPoint, t, alignBag, sceneBag, ggData]; IF count = 0 THEN RETURN [testPoint, [0,-1], NIL, NIL]; RETURN PrepareWinner[nearVEF, 0] }; PrepareWinner: PROC [nearVEF: NearVertexEdgeAndFaces, index: NAT] RETURNS [resultPoint: Point, normal: Vector, feature: FeatureData, hitData: REF ANY] = { goodPoint: GoodPoint ¬ nearVEF[index]; resultPoint ¬ goodPoint.point; normal ¬ goodPoint.normal; feature ¬ goodPoint.featureData; hitData ¬ goodPoint.hitData; }; <<>> <> EmptyCycler: PUBLIC PROC [testPoint: Point] RETURNS [featureCycler: FeatureCycler] = { featureCycler ¬ NEW[FeatureCyclerObj ¬ [ nearVEF: NIL, count: 0, index: -1, testPoint: testPoint ]]; }; MapCycler: PUBLIC PROC [testPoint: Point, t: REAL, alignBag: AlignBag, sceneBag: TriggerBag, ggData: GGData, intersections: BOOL ¬ FALSE] RETURNS [featureCycler: FeatureCycler] = { ENABLE UNWIND => { ggData.multiGravityPool ¬ NewMultiGravityPool[]; <> }; gravityType: GravityType ¬ GGState.GetGravityType[ggData]; IF GGState.GetGravity[ggData] THEN { SELECT gravityType FROM pointsPreferred => featureCycler ¬ PointsPreferredCycler[testPoint, t, alignBag, sceneBag, ggData, intersections]; linesPreferred, facesPreferred => featureCycler ¬ LinesPreferredCycler[testPoint, t, alignBag, sceneBag, ggData]; ENDCASE => ERROR; } ELSE { featureCycler ¬ EmptyCycler[testPoint]; }; }; CopyVEF: PROC [vef: NearVertexEdgeAndFaces, count: NAT] RETURNS [copy: NearVertexEdgeAndFaces] = { oldGoodPoint, newGoodPoint: GoodPoint; copy ¬ NEW[NearVertexEdgeAndFacesObj[count]]; FOR i: NAT IN [0..count) DO oldGoodPoint ¬ vef[i]; newGoodPoint ¬ NEW[GoodPointObj ¬ [ dist: oldGoodPoint.dist, point: oldGoodPoint.point, normal: oldGoodPoint.normal, featureData: oldGoodPoint.featureData, hitData: oldGoodPoint.hitData, dimension: oldGoodPoint.dimension]]; copy[i] ¬ newGoodPoint; ENDLOOP; }; PointsPreferredCycler: PUBLIC PROC [testPoint: Point, t: REAL, alignBag: AlignBag, sceneBag: TriggerBag, ggData: GGData, intersections: BOOL ¬ FALSE, maxDimension: [0..1] ¬ 1] RETURNS [featureCycler: FeatureCycler] = { count: NAT; nearVEF: NearVertexEdgeAndFaces; BEGIN [nearVEF, count] ¬ MultiPointsPreferred[testPoint, t, alignBag, sceneBag, ggData, intersections]; IF count = 0 THEN RETURN[EmptyCycler[testPoint]]; IF count = 1 THEN GOTO MakeSimpleCycler ELSE { <> neighborCount: NAT ¬ 1; s: REAL = 0.072; -- 1/1000 inches nearestDist: REAL ¬ -1; featureCycler ¬ NEW[FeatureCyclerObj ¬ [ nearVEF: NIL, -- will be filled in below count: count, index: -1, -- will be filled in below testPoint: testPoint ]]; nearestDist ¬ nearVEF[0].dist; FOR i: NAT IN [1..count) DO IF nearVEF[i].dist - nearestDist < s THEN neighborCount ¬ neighborCount + 1; ENDLOOP; IF neighborCount = 1 THEN GOTO MakeSimpleCycler; featureCycler.nearVEF ¬ CopyVEF[nearVEF, count]; <> FOR i: NAT IN [0..neighborCount) DO IF nearVEF[i].featureData.type = slice THEN { featureCycler.index ¬ i; RETURN; }; REPEAT FINISHED => featureCycler.index ¬ 0; ENDLOOP; }; EXITS MakeSimpleCycler => { featureCycler ¬ NEW[FeatureCyclerObj ¬ [ nearVEF: CopyVEF[nearVEF, count], count: count, index: 0, testPoint: testPoint ]]; }; END; }; LinesPreferredCycler: PUBLIC PROC [testPoint: Point, t: REAL, alignBag: AlignBag, sceneBag: TriggerBag, ggData: GGData] RETURNS [featureCycler: FeatureCycler] = { <> <> nearVEF: NearVertexEdgeAndFaces; count: NAT; BEGIN [nearVEF, count] ¬ MultiLinesPreferred[testPoint, t, alignBag, sceneBag, ggData]; IF count = 0 THEN RETURN[EmptyCycler[testPoint]]; IF count = 1 THEN GOTO MakeSimpleCycler ELSE { nearestDist: REAL ¬ -1; bestSceneObject: INT ¬ -1; neighborCount: NAT ¬ 1; s: REAL = 0.072; -- 1/1000 inches nearestDist ¬ nearVEF[0].dist; <> FOR i: NAT IN [1..count) DO IF nearVEF[i].dist - nearestDist < s THEN neighborCount ¬ neighborCount + 1; ENDLOOP; IF neighborCount = 1 THEN GOTO MakeSimpleCycler; bestSceneObject ¬ -1; featureCycler ¬ NEW[FeatureCyclerObj ¬ [ nearVEF: CopyVEF[nearVEF, count], count: count, index: 0, testPoint: testPoint ]]; }; EXITS MakeSimpleCycler => { featureCycler ¬ NEW[FeatureCyclerObj ¬ [ nearVEF: CopyVEF[nearVEF, count], count: count, index: 0, testPoint: testPoint ]]; }; END; }; FacesPreferredCycler: PUBLIC PROC [testPoint: Point, t: REAL, alignBag: AlignBag, sceneBag: TriggerBag, ggData: GGData] RETURNS [featureCycler: FeatureCycler] = { nearVEF: NearVertexEdgeAndFaces; count: NAT; BEGIN [nearVEF, count] ¬ MultiFacesPreferred[testPoint, t, alignBag, sceneBag, ggData]; IF count = 0 THEN RETURN[EmptyCycler[testPoint]]; IF count = 1 THEN GOTO MakeSimpleCycler ELSE { GOTO MakeSimpleCycler; <> <> FOR i: NAT IN [1..count) DO IF nearVEF[i].dist - nearestDist < s THEN neighborCount ¬ neighborCount + 1; ENDLOOP; IF neighborCount = 1 THEN GOTO MakeSimpleCycler; bestSceneObject ¬ -1; featureCycler ¬ NEW[FeatureCyclerObj ¬ [ nearVEF: CopyVEF[nearVEF, count], count: count, index: 0, testPoint: testPoint ]];>> }; EXITS MakeSimpleCycler => { featureCycler ¬ NEW[FeatureCyclerObj ¬ [ nearVEF: CopyVEF[nearVEF, count], count: count, index: 0, testPoint: testPoint ]]; }; END; }; <<>> FirstFeature: PUBLIC PROC [featureCycler: FeatureCycler] RETURNS [resultPoint: Point, normal: Vector, feature: FeatureData, hitData: REF ANY] = { RETURN GetFeature[featureCycler, 0]; }; NextFeature: PUBLIC PROC [featureCycler: FeatureCycler] RETURNS [resultPoint: Point, normal: Vector, feature: FeatureData, hitData: REF ANY] = { RETURN GetFeature[featureCycler, 1]; }; PreviousFeature: PUBLIC PROC [featureCycler: FeatureCycler] RETURNS [resultPoint: Point, normal: Vector, feature: FeatureData, hitData: REF ANY] = { RETURN GetFeature[featureCycler, -1]; }; GetFeature: PUBLIC PROC [featureCycler: FeatureCycler, move: [-1..1]] RETURNS [resultPoint: Point, normal: Vector, feature: FeatureData, hitData: REF ANY] = { IF featureCycler = NIL THEN { -- return a backdrop position resultPoint ¬ [0.0, 0.0]; -- bogus normal ¬ [0,-1]; feature ¬ NIL; hitData ¬ NIL; } ELSE IF featureCycler.count = 0 THEN { -- return a backdrop position resultPoint ¬ featureCycler.testPoint; normal ¬ [0,-1]; feature ¬ NIL; hitData ¬ NIL; } ELSE { featureCycler.index ¬ (featureCycler.index + move + featureCycler.count) MOD featureCycler.count; [resultPoint, normal, feature, hitData] ¬ PrepareWinner[featureCycler.nearVEF, featureCycler.index]; }; }; <<>> <> <<>> MultiMap: PUBLIC PROC [testPoint: Point, t: REAL, alignBag: AlignBag, sceneBag: TriggerBag, ggData: GGData, intersections: BOOL ¬ FALSE] RETURNS [nearVEF: NearVertexEdgeAndFaces, count: NAT] = { ENABLE UNWIND => ggData.multiGravityPool ¬ NewMultiGravityPool[]; -- in case an ABORT happened while pool was in use CodeTimer.StartInt[$MultiMap, $Gargoyle]; IF GGState.GetGravity[ggData] THEN { SELECT GGState.GetGravityType[ggData] FROM <>> <<[nearVEF, count] _ MultiFacesPreferred[testPoint, t, alignBag, sceneBag, ggData];>> linesPreferred => [nearVEF, count] ¬ MultiLinesPreferred[testPoint, t, alignBag, sceneBag, ggData]; pointsPreferred => [nearVEF, count] ¬ MultiPointsPreferred[testPoint, t, alignBag, sceneBag, ggData, intersections]; ENDCASE => ERROR; } ELSE { nearVEF ¬ NIL; count ¬ 0; }; CodeTimer.StopInt[$MultiMap, $Gargoyle]; }; MultiFacesPreferred: PUBLIC PROC [testPoint: Point, t: REAL, alignBag: AlignBag, sceneBag: TriggerBag, ggData: GGData] RETURNS [nearVEF: NearVertexEdgeAndFaces, count: NAT] = { <> bestCurves, bestPoints: BestPoints; bestFaces: BestFaces; faceCount, curveCount, pointCount: NAT; IF GGAlign.EmptyAlignBag[alignBag] AND GGAlign.EmptyTriggerBag[sceneBag] THEN RETURN[NIL, 0]; [bestFaces, faceCount] ¬ FacesInNeighborhoodPlus[alignBag, sceneBag, testPoint, ggData, t]; SortByOverlap[bestFaces, faceCount]; [bestCurves, curveCount] ¬ CurvesInNeighborhoodPlus[alignBag, sceneBag, testPoint, ggData, t, 0]; [bestPoints, pointCount] ¬ VertsInNeighborhoodPlus[bestCurves, curveCount, alignBag, sceneBag, testPoint, t, ggData, FALSE]; SortPoints[bestPoints, pointCount]; count ¬ MIN[pointCount + curveCount, MaxFeatures]; nearVEF ¬ NEW[NearVertexEdgeAndFacesObj[count]]; MergePointsAndCurves[bestPoints, pointCount, bestCurves, curveCount, nearVEF, count]; [nearVEF, count] ¬ MergeByOverlapAndDistance[bestFaces, faceCount, nearVEF, count]; }; MultiLinesPreferred: PUBLIC PROC [testPoint: Point, t: REAL, alignBag: AlignBag, sceneBag: TriggerBag, ggData: GGData] RETURNS [nearVEF: NearVertexEdgeAndFaces, count: NAT] = { <> bestCurves: BestPoints; bestPoints: BestPoints; pointCount, curveCount: NAT; IF GGAlign.EmptyAlignBag[alignBag] AND GGAlign.EmptyTriggerBag[sceneBag] THEN RETURN[NIL, 0]; <> [bestCurves, curveCount] ¬ CurvesInNeighborhoodPlus[alignBag, sceneBag, testPoint, ggData, t, 0]; [bestPoints, pointCount] ¬ VertsInNeighborhoodPlus[bestCurves, curveCount, alignBag, sceneBag, testPoint, t, ggData, FALSE]; SortPoints[bestPoints, pointCount]; count ¬ MIN[pointCount + curveCount, MaxFeatures]; nearVEF ¬ NEW[NearVertexEdgeAndFacesObj[count]]; MergePointsAndCurves[bestPoints, pointCount, bestCurves, curveCount, nearVEF, count]; }; MultiPointsPreferred: PUBLIC PROC [testPoint: Point, t: REAL, alignBag: AlignBag, sceneBag: TriggerBag, ggData: GGData, intersections: BOOL ¬ FALSE] RETURNS [nearVEF: NearVertexEdgeAndFaces, count: NAT] = { <> bestCurves: BestPoints; bestPoints: BestPoints; pointCount, curveCount: NAT; innerR: REAL ¬ t/2.0; IF GGAlign.EmptyAlignBag[alignBag] AND GGAlign.EmptyTriggerBag[sceneBag] THEN RETURN[NIL, 0]; <> [bestCurves, curveCount] ¬ CurvesInNeighborhoodPlus[alignBag, sceneBag, testPoint, ggData, t, innerR]; [bestPoints, pointCount] ¬ VertsInNeighborhoodPlus[bestCurves, curveCount, alignBag, sceneBag, testPoint, t, ggData, intersections]; SortPoints[bestPoints, pointCount]; IF pointCount > 0 AND bestPoints[0].dist < innerR THEN { count ¬ pointCount; nearVEF ¬ NEW[NearVertexEdgeAndFacesObj[count]]; NearPointsFromPoints[bestPoints, pointCount, nearVEF]; } ELSE { count ¬ MIN[pointCount + curveCount, MaxFeatures]; nearVEF ¬ NEW[NearVertexEdgeAndFacesObj[count]]; MergePointsAndCurves[bestPoints, pointCount, bestCurves, curveCount, nearVEF, count]; }; }; VertsInNeighborhoodPlus: PROC [bestCurves: BestPoints, curveCount: NAT, alignBag: AlignBag, sceneBag: TriggerBag, q: Point, t: REAL, ggData: GGData, intersections: BOOL ¬ FALSE] RETURNS [h: BestPoints, pointCount: NAT] = { thisPoint: GoodPoint; <> <> <> <> ProcessPoint: PROC [thisPoint: GoodPoint, featureData: FeatureData] = { -- used for the anchor dSquared: REAL; dTolSquared: REAL ¬ dTol*dTol; dSquared ¬ Vectors2d.DistanceSquared[thisPoint.point, q]; thisPoint.hitData ¬ NIL; IF dSquared < dTolSquared THEN { thisPoint.dist ¬ RealFns.SqRt[dSquared]; <> thisPoint.normal ¬ GGCaret.GetNormal[NARROW[featureData.shape]]; -- the anchor IF Vectors2d.MagnitudeSquared[thisPoint.normal] = 0 THEN thisPoint.normal ¬ [0, -1]; thisPoint.featureData ¬ featureData; thisPoint.priority ¬ -1; dTol ¬ AddNeighbor[thisPoint, h, FALSE]; }; }; ProcessSlice: PROC [sliceD: SliceDescriptor, thisPoint: GoodPoint, featureData: FeatureData] = { [thisPoint.point, thisPoint.dist, thisPoint.normal, thisPoint.hitData, success] ¬ sliceD.slice.class.closestPoint[sliceD, q, dTol]; IF success THEN { IF thisPoint.dist < dTol THEN { thisPoint.featureData ¬ featureData; IF Vectors2d.MagnitudeSquared[thisPoint.normal] = 0 THEN { thisPoint.normal ¬ [0, -1]; }; thisPoint.priority ¬ GGScene.GetPriority[ggData.scene, sliceD.slice]; dTol ¬ AddNeighbor[thisPoint, h, FALSE]; }; }; }; DoForSliceTrigger: GGAlign.FeatureWalkProc = { <> sliceD ¬ NARROW[feature.shape, SliceDescriptor]; ProcessSlice[sliceD, thisPoint, feature]; }; sliceD: SliceDescriptor; featureData: FeatureData; success: BOOL ¬ FALSE; dTol: REAL ¬ t; midpoints: BOOL ¬ GGState.GetMidpoints[ggData]; thisPoint ¬ NEW[GoodPointObj]; h ¬ BestPointsFromPool[ggData, t]; IF intersections THEN { dTol ¬ FindIntersections[bestCurves, curveCount, thisPoint, q, dTol, h, ggData.scene]; IF midpoints THEN dTol ¬ FindMidpoints[bestCurves, curveCount, thisPoint, q, dTol, h, ggData.scene]; }; GGAlign.WalkSliceTriggers[sceneBag, DoForSliceTrigger]; featureData ¬ alignBag.anchor; IF featureData # NIL THEN { anchor: Caret ¬ NARROW[featureData.shape]; IF NOT GGCaret.Exists[anchor] THEN ERROR; thisPoint.point ¬ GGCaret.GetPoint[anchor]; ProcessPoint[thisPoint, featureData]; }; pointCount ¬ h.size; IF h.overflow THEN { CodeTimer.StartInt[$PointOverflow, $Gargoyle]; CodeTimer.StopInt[$PointOverflow, $Gargoyle]; }; }; -- end of VertsInNeighborhoodPlus <<>> FindIntersections: PROC [bestCurves: BestPoints, curveCount: NAT, thisPoint: GoodPoint, q: Point, tolerance: REAL, h: BestPoints, scene: Scene] RETURNS [dTol: REAL] = { <> curveI, curveJ: GoodPoint; theseIPoints: LIST OF Point; thisTangency, tangentList: LIST OF BOOL; success: BOOL ¬ FALSE; dTol ¬ tolerance; FOR i: NAT IN [0..curveCount) DO curveI ¬ bestCurves[i]; IF curveI.dist > dTol THEN EXIT; -- this curve is too far away (and the rest are farther) FOR j: NAT IN [0..i] DO curveJ ¬ bestCurves[j]; IF curveJ.dist > dTol THEN LOOP; -- this curve is too far away to be worth considering [theseIPoints, thisTangency] ¬ CurveMeetsCurve[curveI, curveJ]; tangentList ¬ thisTangency; FOR list: LIST OF Point ¬ theseIPoints, list.rest UNTIL list = NIL DO thisPoint.point ¬ list.first; thisPoint.dist ¬ Vectors2d.Distance[thisPoint.point, q]; success ¬ thisPoint.dist <= dTol; IF success THEN { featureData: FeatureData ¬ NEW[FeatureDataObj]; alignmentPoint: AlignmentPoint ¬ NEW[AlignmentPointObj ¬ [ point: thisPoint.point, tangent: tangentList.first, curve1: curveI.featureData, curve2: curveJ.featureData]]; featureData.type ¬ intersectionPoint; featureData.shape ¬ alignmentPoint; thisPoint.featureData ¬ featureData; thisPoint.priority ¬ -1; IF curveI.featureData.type = slice THEN { sliceD: SliceDescriptor ¬ NARROW[curveI.featureData.shape]; slice: Slice ¬ sliceD.slice; thisPoint.priority ¬ GGScene.GetPriority[scene, slice]; thisPoint.hitData ¬ curveI.hitData; thisPoint.normal ¬ GGSliceOps.ClosestSegment[sliceD, q, dTol].bestNormal; -- find normal at nearest vertex. Works for straight edges } ELSE IF curveJ.featureData.type = slice THEN { sliceD: SliceDescriptor ¬ NARROW[curveJ.featureData.shape]; slice: Slice ¬ sliceD.slice; thisPoint.priority ¬ MIN[thisPoint.priority, GGScene.GetPriority[scene, slice]]; thisPoint.hitData ¬ curveJ.hitData; thisPoint.normal ¬ GGSliceOps.ClosestSegment[sliceD, q, dTol].bestNormal; -- find normal at nearest vertex. Works for straight edges } ELSE thisPoint.hitData ¬ NIL; IF Vectors2d.MagnitudeSquared[thisPoint.normal] = 0 THEN thisPoint.normal ¬ [0, -1]; dTol ¬ AddNeighbor[thisPoint, h, FALSE]; }; tangentList ¬ tangentList.rest; ENDLOOP; ENDLOOP; ENDLOOP; }; FindMidpoints: PROC [bestCurves: BestPoints, curveCount: NAT, thisPoint: GoodPoint, q: Point, tolerance: REAL, h: BestPoints, scene: Scene] RETURNS [dTol: REAL] = { <> curve: GoodPoint; midpoint: Point; success: BOOL ¬ FALSE; dTol ¬ tolerance; FOR i: NAT IN [0..curveCount) DO curve ¬ bestCurves[i]; IF curve.featureData.type#slice THEN LOOP; [midpoint, success] ¬ ComputeMidpoint[curve]; IF NOT success THEN LOOP; thisPoint.point ¬ midpoint; thisPoint.dist ¬ Vectors2d.Distance[thisPoint.point, q]; success ¬ thisPoint.dist <= dTol; IF success THEN { sliceD: SliceDescriptor ¬ NARROW[curve.featureData.shape]; slice: Slice ¬ sliceD.slice; featureData: FeatureData ¬ NEW[FeatureDataObj]; alignmentPoint: AlignmentPoint ¬ NEW[AlignmentPointObj ¬ [ point: thisPoint.point, tangent: FALSE, curve1: curve.featureData, curve2: NIL]]; featureData.type ¬ midpoint; featureData.shape ¬ alignmentPoint; thisPoint.featureData ¬ featureData; thisPoint.hitData ¬ curve.hitData; <> thisPoint.normal ¬ GGSliceOps.ClosestSegment[sliceD, q, dTol].bestNormal; -- find normal at nearest vertex. Works for edges IF Vectors2d.MagnitudeSquared[thisPoint.normal] = 0 THEN thisPoint.normal ¬ [0, -1]; thisPoint.priority ¬ GGScene.GetPriority[scene, slice]; dTol ¬ AddNeighbor[thisPoint, h, FALSE]; }; ENDLOOP; }; CurvesInNeighborhoodPlus: PROC [alignBag: AlignBag, sceneBag: TriggerBag, q: Point, ggData: GGData, t: REAL, innerR: REAL] RETURNS [h: BestPoints, curveCount: NAT] = { <> <> <> <> <> ProcessLine: PROC [line: Line, thisCurve: GoodPoint, featureData: FeatureData] = { thisCurve.dist ¬ Lines2d.LineDistance[q, line]; IF thisCurve.dist < dTol THEN { thisCurve.featureData ¬ featureData; thisCurve.point ¬ Lines2d.DropPerpendicular[q, line]; thisCurve.normal ¬ Vectors2d.Sub[q, thisCurve.point]; IF Vectors2d.MagnitudeSquared[thisCurve.normal] = 0 THEN { thisCurve.normal ¬ [0, -1];}; thisCurve.hitData ¬ NIL; thisCurve.priority ¬ -1; dTol ¬ AddNeighbor[thisCurve, h, TRUE]; } }; ProcessCircle: PROC [circle: Circle, thisCurve: GoodPoint, featureData: FeatureData] = { QProjectedOntoCircle: PUBLIC PROC [] RETURNS [projectedPt: Point] = { epsilon: REAL = 1.0e-5; IF distQtoCenter < epsilon THEN projectedPt ¬ [circle.origin.x + circle.radius, circle.origin.y] ELSE projectedPt ¬ Vectors2d.Add[circle.origin, Vectors2d.Scale[centerToQ, circle.radius/distQtoCenter]]; }; centerToQ: Vector ¬ Vectors2d.Sub[q, circle.origin]; distQtoCenter: REAL ¬ Vectors2d.Magnitude[centerToQ]; thisCurve.dist ¬ ABS[distQtoCenter-circle.radius]; IF thisCurve.dist < dTol THEN { thisCurve.featureData ¬ featureData; thisCurve.point ¬ QProjectedOntoCircle[]; IF thisCurve.dist = 0.0 THEN thisCurve.normal ¬ centerToQ ELSE thisCurve.normal ¬ Vectors2d.Sub[q, thisCurve.point]; thisCurve.hitData ¬ NIL; thisCurve.priority ¬ -1; dTol ¬ AddNeighbor[thisCurve, h, TRUE]; }; }; ProcessSlice: PROC [sliceD: SliceDescriptor, thisCurve: GoodPoint, featureData: FeatureData] = { success: BOOL ¬ FALSE; [thisCurve.point, thisCurve.dist, thisCurve.normal, thisCurve.hitData, success] ¬ sliceD.slice.class.closestSegment[sliceD, q, dTol]; IF success THEN { IF thisCurve.dist < dTol THEN { thisCurve.featureData ¬ featureData; IF Vectors2d.MagnitudeSquared[thisCurve.normal] = 0 THEN { thisCurve.normal ¬ [0, -1]; }; thisCurve.priority ¬ GGScene.GetPriority[ggData.scene, sliceD.slice]; dTol ¬ AddNeighbor[thisCurve, h, TRUE]; }; }; }; ProcessSlopeLine: GGAlign.FeatureWalkProc = { <> line ¬ NARROW[feature.shape, AlignmentLine].line; ProcessLine[line, thisCurve, feature]; }; DoForSceneSlice: GGAlign.FeatureWalkProc = { <> sliceD ¬ NARROW[feature.shape, SliceDescriptor]; ProcessSlice[sliceD, thisCurve, feature]; }; line: Line; circle: Circle; sliceD: SliceDescriptor; featureData: FeatureData; added: BOOL ¬ FALSE; thisCurve: GoodPoint ¬ NEW[GoodPointObj]; dTol: REAL ¬ t; h ¬ BestCurvesFromPool[ggData, t, innerR]; <> GGAlign.WalkSlopeLines[alignBag, ProcessSlopeLine]; FOR angleLines: LIST OF FeatureData ¬ alignBag.angleLines, angleLines.rest UNTIL angleLines = NIL DO featureData ¬ angleLines.first; line ¬ NARROW[featureData.shape, AlignmentLine].line; ProcessLine[line, thisCurve, featureData]; ENDLOOP; FOR dLines: LIST OF FeatureData ¬ alignBag.distanceLines, dLines.rest UNTIL dLines = NIL DO featureData ¬ dLines.first; line ¬ NARROW[featureData.shape]; ProcessLine[line, thisCurve, featureData]; ENDLOOP; FOR circles: LIST OF FeatureData ¬ alignBag.radiiCircles, circles.rest UNTIL circles = NIL DO featureData ¬ circles.first; circle ¬ NARROW[featureData.shape, AlignmentCircle].circle; ProcessCircle[circle, thisCurve, featureData]; ENDLOOP; <> GGAlign.WalkSliceTriggers[sceneBag, DoForSceneSlice]; curveCount ¬ h.size; IF h.overflow THEN { CodeTimer.StartInt[$CurveOverflow, $Gargoyle]; CodeTimer.StopInt[$CurveOverflow, $Gargoyle]; }; SortCurves[h, curveCount]; }; -- end CurvesInNeighborhoodPlus FacesInNeighborhoodPlus: PROC [alignBag: AlignBag, sceneBag: TriggerBag, q: Point, ggData: GGData, t: REAL] RETURNS [h: BestFaces, faceCount: NAT] = { sliceD: SliceDescriptor; added: BOOL ¬ FALSE; thisFace: GoodPoint ¬ NEW[GoodPointObj]; priorityTol: INT ¬ -1; ProcessSlice: PROC [sliceD: SliceDescriptor, thisFace: GoodPoint, featureData: FeatureData] = { hitData: REF ANY; moreHitDatas: LIST OF REF ANY; success: BOOL ¬ TRUE; IF GGScene.GetPriority[ggData.scene, sliceD.slice] >= priorityTol THEN { [hitData, moreHitDatas] ¬ GGSliceOps.FilledPathsUnderPoint[sliceD.slice, q, t]; IF hitData # NIL THEN { thisFace.point ¬ q; thisFace.priority ¬ GGScene.GetPriority[ggData.scene, sliceD.slice]; thisFace.normal ¬ [0, -1]; thisFace.hitData ¬ hitData; thisFace.featureData ¬ featureData; priorityTol ¬ AddFace[thisFace, h]; }; FOR list: LIST OF REF ANY ¬ moreHitDatas, list.rest UNTIL list = NIL DO thisFace.point ¬ q; thisFace.priority ¬ GGScene.GetPriority[ggData.scene, sliceD.slice]; thisFace.normal ¬ [0, -1]; thisFace.hitData ¬ list.first; thisFace.featureData ¬ featureData; priorityTol ¬ AddFace[thisFace, h]; ENDLOOP; }; }; DoForSceneSlice: GGAlign.FeatureWalkProc = { <> sliceD ¬ NARROW[feature.shape, SliceDescriptor]; ProcessSlice[sliceD, thisFace, feature]; }; h ¬ BestFacesFromPool[ggData]; <> GGAlign.WalkSliceTriggers[sceneBag, DoForSceneSlice]; faceCount ¬ h.size; IF h.overflow THEN { CodeTimer.StartInt[$FaceOverflow, $Gargoyle]; CodeTimer.StopInt[$FaceOverflow, $Gargoyle]; }; SortFaces[h, faceCount]; }; <> MaxFeatures: NAT ¬ 20; BestFacesFromPool: PROC [ggData: GGData] RETURNS [h: BestFaces] = { h ¬ NARROW[ggData.multiGravityPool, MultiGravityPool].bestfaces; h.size ¬ 0; h.maxPriority ¬ -1; h.minIndex ¬ 9999; h.minPriority ¬ LAST[INT]; h.bestPriorityTossed ¬ -1; h.overflow ¬ FALSE; FOR i: NAT IN [0..MaxFeatures) DO h[i].dist ¬ Real.LargestNumber; h[i].featureData ¬ NIL; ENDLOOP; }; BestCurvesFromPool: PROC [ggData: GGData, t: REAL, innerR: REAL] RETURNS [h: BestPoints] = { h ¬ NARROW[ggData.multiGravityPool, MultiGravityPool].bestcurves; h.size ¬ 0; h.max ¬ 0.0; h.maxIndex ¬ 9999; h.min ¬ Real.LargestNumber; h.dTol ¬ t; h.innerR ¬ innerR; h.s ¬ 0.072; -- 1/1000 inches h.bestTossed ¬ Real.LargestNumber; h.overflow ¬ FALSE; FOR i: NAT IN [0..MaxFeatures) DO h[i].dist ¬ Real.LargestNumber; h[i].featureData ¬ NIL; ENDLOOP; }; BestPointsFromPool: PROC [ggData: GGData, t: REAL] RETURNS [h: BestPoints] = { h ¬ NARROW[ggData.multiGravityPool, MultiGravityPool].bestpoints; h.size ¬ 0; h.max ¬ 0.0; h.maxIndex ¬ 9999; h.min ¬ Real.LargestNumber; h.dTol ¬ t; h.s ¬ 0.072; -- 1/1000 inches h.bestTossed ¬ Real.LargestNumber; h.overflow ¬ FALSE; FOR i: NAT IN [0..MaxFeatures) DO h[i].dist ¬ Real.LargestNumber; h[i].featureData ¬ NIL; ENDLOOP; }; <> <> <> <> <> <> <> <> <> <> <> < 0 and curve is TRUE,>> < 0 and curve is FALSE.>> <<>> AddNeighbor: PROC [thisPoint: GoodPoint, h: BestPoints, curve: BOOL ¬ FALSE] RETURNS [dTol: REAL] = { d: REAL ¬ thisPoint.dist; n: NAT = MaxFeatures; BEGIN SELECT TRUE FROM d > h.dTol => GOTO Toss; -- the caller is not taking our hints and is passing us trash h.size < n => GOTO Add; h.size = n => GOTO ReplaceOrOverflow; ENDCASE => SIGNAL Problem[msg: "Impossible case."]; EXITS Add => { h[h.size]­ ¬ thisPoint­; IF d > h.max THEN {h.max ¬ d; h.maxIndex ¬ h.size}; h.min ¬ MIN[h.min, d]; h.size ¬ h.size + 1; IF curve THEN dTol ¬ h.dTol ¬ MAX[h.min+h.s, h.innerR] ELSE dTol ¬ h.dTol ¬ h.min+h.s; }; ReplaceOrOverflow => { <> IF d < h.max THEN { -- do the replace h[h.maxIndex]­ ¬ thisPoint­; h.bestTossed ¬ MIN[h.bestTossed, h.max]; h.min ¬ MIN[h.min, d]; IF curve THEN dTol ¬ h.dTol ¬ MAX[h.min+h.s, h.innerR] ELSE dTol ¬ h.dTol ¬ h.min+h.s; h.overflow ¬ h.bestTossed <= dTol; <> BEGIN maxIndex: NAT ¬ 0; maxDist: REAL ¬ 0.0; FOR i: NAT IN [0..MaxFeatures) DO IF h[i].dist > maxDist THEN {maxIndex ¬ i; maxDist ¬ h[i].dist}; ENDLOOP; h.max ¬ maxDist; h.maxIndex ¬ maxIndex; END; } ELSE { -- toss the new item dTol ¬ h.dTol; h.bestTossed ¬ MIN[h.bestTossed, d]; h.overflow ¬ TRUE; }; }; Toss => { dTol ¬ h.dTol; h.bestTossed ¬ MIN[h.bestTossed, d]; h.overflow ¬ h.bestTossed <= dTol; }; END; }; AddFace: PROC [thisFace: GoodPoint, h: BestFaces] RETURNS [priorityTol: INT] = { d: INT ¬ thisFace.priority; n: NAT = MaxFeatures; BEGIN SELECT TRUE FROM d < h.priorityTol => GOTO Toss; -- the caller is passing us trash h.size < n => GOTO Add; h.size = n => GOTO ReplaceOrOverflow; ENDCASE => SIGNAL Problem[msg: "Impossible case."]; EXITS Add => { h[h.size]­ ¬ thisFace­; IF d < h.minPriority THEN {h.minPriority ¬ d; h.minIndex ¬ h.size}; h.maxPriority ¬ MAX[h.maxPriority, d]; h.size ¬ h.size + 1; priorityTol ¬ h.priorityTol; }; ReplaceOrOverflow => { <> IF d > h.minPriority THEN { -- do the replace h[h.minIndex]­ ¬ thisFace­; h.bestPriorityTossed ¬ MAX[h.bestPriorityTossed, h.minPriority]; h.maxPriority ¬ MAX[h.maxPriority, d]; h.overflow ¬ TRUE; <> BEGIN minIndex: NAT ¬ 0; minPriority: INT ¬ LAST[INT]; FOR i: NAT IN [0..MaxFeatures) DO IF h[i].priority < minPriority THEN {minIndex ¬ i; minPriority ¬ h[i].priority}; ENDLOOP; h.minPriority ¬ minPriority; h.minIndex ¬ minIndex; END; priorityTol ¬ h.priorityTol ¬ h.minPriority; } ELSE { -- toss the new item priorityTol ¬ h.priorityTol; h.bestPriorityTossed ¬ MAX[h.bestPriorityTossed, d]; h.overflow ¬ TRUE; }; }; Toss => { priorityTol ¬ h.priorityTol; h.bestPriorityTossed ¬ MAX[h.bestPriorityTossed, d]; h.overflow ¬ TRUE; }; END; }; NearPointsFromPoints: PROC [bestPoints: BestPoints, pointCount: NAT, nearVEF: NearVertexEdgeAndFaces] = { FOR i: NAT IN [0..pointCount) DO nearVEF[i] ¬ bestPoints[i]; ENDLOOP; }; MergePointsAndCurves: PROC [bestPoints: BestPoints, pointCount: NAT, bestCurves: BestPoints, curveCount: NAT, nearVEF: NearVertexEdgeAndFaces, count: NAT] = { <> pointIndex, curveIndex: NAT; pointDist, curveDist: REAL; pointIndex ¬ 0; curveIndex ¬ 0; FOR i: INTEGER IN [0..count) DO IF pointIndex >= pointCount THEN GOTO NoMorePoints; IF curveIndex >= curveCount THEN GOTO NoMoreCurves; pointDist ¬ bestPoints[i].dist; curveDist ¬ bestCurves[i].dist; IF pointDist <= curveDist THEN { nearVEF[i] ¬ bestPoints[pointIndex]; pointIndex ¬ pointIndex + 1; } ELSE { nearVEF[i] ¬ bestCurves[curveIndex]; curveIndex ¬ curveIndex + 1; }; REPEAT NoMorePoints => { -- finish up with Curves data FOR k: NAT ¬ i, k+1 UNTIL k >= count DO nearVEF[k] ¬ bestCurves[curveIndex]; curveIndex ¬ curveIndex + 1; ENDLOOP}; NoMoreCurves => { -- finish up with points data FOR k: NAT ¬ i, k+1 UNTIL k >= count DO nearVEF[k] ¬ bestPoints[pointIndex]; pointIndex ¬ pointIndex + 1; ENDLOOP}; ENDLOOP; }; MergeByOverlapAndDistance: PROC [faces: BestFaces, faceCount: NAT, curves: NearVertexEdgeAndFaces, curveCount: NAT] RETURNS [nearVEF: NearVertexEdgeAndFaces, total: NAT] = { <> facePtr, curvePtr: NAT; total ¬ MIN[curveCount+faceCount, MaxFeatures]; nearVEF ¬ NEW[NearVertexEdgeAndFacesObj[total]]; facePtr ¬ curvePtr ¬ 0; FOR i: NAT IN[0..total) DO IF curvePtr >= curveCount THEN GOTO CurvePtrWentOver; IF facePtr >= faceCount THEN GOTO FacePtrWentOver; BEGIN SELECT faces[facePtr].priority - curves[curvePtr].priority FROM = 0 => { -- they're part of the same slice slice: Slice ¬ NARROW[faces[facePtr].featureData.shape, SliceDescriptor].slice; IF GGParent.IsParent[slice] THEN { facePath, curvePath: Slice; faceHitData, curveHitData: REF ANY; [facePath, faceHitData] ¬ GGParent.PathOfHitData[slice, faces[facePtr].hitData]; [curvePath, curveHitData] ¬ GGParent.PathOfHitData[slice, curves[curvePtr].hitData]; IF facePath = curvePath THEN GOTO RemoveDuplicate; <> SELECT GGParent.ComparePriorities[facePath, curvePath] FROM less => GOTO CurveIsCloser; greater => GOTO FaceIsCloser; equal => GOTO RemoveDuplicate; ENDCASE => ERROR; } ELSE GOTO RemoveDuplicate; }; > 0 => GOTO FaceIsCloser; < 0 => GOTO CurveIsCloser; ENDCASE => ERROR; EXITS RemoveDuplicate => { nearVEF[i] ¬ curves[curvePtr]; curvePtr ¬ curvePtr + 1; facePtr ¬ facePtr + 1; total ¬ total - 1; -- a duplicate has been removed }; FaceIsCloser => { nearVEF[i] ¬ faces[facePtr]; facePtr ¬ facePtr + 1; }; CurveIsCloser => { nearVEF[i] ¬ curves[curvePtr]; curvePtr ¬ curvePtr + 1; }; END; REPEAT CurvePtrWentOver => { -- finish up with faces FOR k: NAT ¬ i, k+1 UNTIL k >= total DO nearVEF[k] ¬ faces[facePtr]; facePtr ¬ facePtr + 1; ENDLOOP}; FacePtrWentOver => { -- finish up with curves FOR k: NAT ¬ i, k+1 UNTIL k >= total DO nearVEF[k] ¬ curves[curvePtr]; curvePtr ¬ curvePtr + 1; ENDLOOP}; ENDLOOP; }; -- end of MergeByOverlapAndDistance SortPoints: PROC [bestPoints: BestPoints, pointCount: NAT] = { <> temp: GoodPoint; FOR i: INTEGER IN [0..pointCount-2] DO FOR j: INTEGER IN [1..pointCount-i) DO IF bestPoints[j-1].dist > bestPoints[j].dist THEN { temp ¬ bestPoints[j]; bestPoints[j] ¬ bestPoints[j-1]; bestPoints[j-1] ¬ temp; }; ENDLOOP; ENDLOOP; }; SortCurves: PROC [bestCurves: BestPoints, curveCount: NAT] = { <> temp: GoodPoint; FOR i: INTEGER IN [0..curveCount-2] DO FOR j: INTEGER IN [1..curveCount-i) DO IF bestCurves[j-1].dist > bestCurves[j].dist THEN { temp ¬ bestCurves[j]; bestCurves[j] ¬ bestCurves[j-1]; bestCurves[j-1] ¬ temp; }; ENDLOOP; ENDLOOP; }; SortFaces: PROC [bestFaces: BestFaces, faceCount: NAT] = { <> temp: GoodPoint; FOR i: INTEGER IN [0..faceCount-2] DO FOR j: INTEGER IN [1..faceCount-i) DO IF bestFaces[j-1].priority < bestFaces[j].priority THEN { temp ¬ bestFaces[j]; bestFaces[j] ¬ bestFaces[j-1]; bestFaces[j-1] ¬ temp; }; ENDLOOP; ENDLOOP; }; SortByOverlap: PROC [faces: BestFaces, count: NAT] = { <> temp: GoodPoint; FOR i: INTEGER IN [0..count-2] DO FOR j: INTEGER IN [1..count-i) DO IF faces[j-1].priority < faces[j].priority THEN { temp ¬ faces[j]; faces[j] ¬ faces[j-1]; faces[j-1] ¬ temp; }; ENDLOOP; ENDLOOP; }; <<>> <> <<>> ComputeMidpoint: PROC [curve: GoodPoint] RETURNS [midpoint: Point, success: BOOL ¬ TRUE] = { class: NAT; simpleCurve: REF ANY; [class, simpleCurve] ¬ ClassifyCurve[curve]; SELECT class FROM 3 => { -- edge edge: Edge ¬ NARROW[simpleCurve]; midpoint ¬ Vectors2d.Scale[Vectors2d.Add[edge.start, edge.end], 0.5]; success ¬ TRUE; }; 4 => { -- arc arc: Arc ¬ NARROW[simpleCurve]; midpoint ¬ Vectors2d.Scale[Vectors2d.Add[arc.p0, arc.p2], 0.5]; success ¬ TRUE; }; ENDCASE => RETURN[[0,0], FALSE]; }; ClassifyCurve: PROC [curve: GoodPoint] RETURNS [class: NAT, simpleCurve: REF ANY] = { feature: FeatureData ¬ curve.featureData; SELECT feature.type FROM slice => { sliceD: SliceDescriptor ¬ NARROW[feature.shape]; hitData: REF ANY ¬ curve.hitData; simpleCurve ¬ GGSliceOps.HitDataAsSimpleCurve[sliceD.slice, hitData]; IF simpleCurve = NIL THEN { simpleCurve ¬ sliceD; class ¬ 6; RETURN; }; }; radiiCircle => { class ¬ 2; simpleCurve ¬ NARROW[feature.shape, AlignmentCircle].circle; RETURN; }; slopeLine, angleLine => { class ¬ 1; simpleCurve ¬ NARROW[feature.shape, AlignmentLine].line; RETURN; }; distanceLine => { class ¬ 1; simpleCurve ¬ NARROW[feature.shape, Line]; RETURN; }; ENDCASE => {class ¬ 0; simpleCurve ¬ NIL; RETURN}; WITH simpleCurve SELECT FROM circle: Circle => class ¬ 2; edge: Edge => class ¬ 3; arc: Arc => class ¬ 4; cubic: BezierRef => class ¬ 5; ENDCASE => ERROR; }; CurveMeetsCurve: PROC [c1, c2: GoodPoint] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL] = { typeOfCurve1, typeOfCurve2: NAT; simpleCurve1, simpleCurve2: REF ANY; [typeOfCurve1, simpleCurve1] ¬ ClassifyCurve[c1]; [typeOfCurve2, simpleCurve2] ¬ ClassifyCurve[c2]; IF typeOfCurve1 >= typeOfCurve2 THEN [iPoints, tangency] ¬ ComputeIntersection[typeOfCurve1][typeOfCurve2][simpleCurve1, simpleCurve2] ELSE [iPoints, tangency] ¬ ComputeIntersection[typeOfCurve2][typeOfCurve1][simpleCurve2, simpleCurve1] }; IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL]; ComputeIntersection: ARRAY [0..6] OF ARRAY [0..6] OF IntersectionProc = [ <<0) NoOp 1) Line 2) Circle 3) Edge 4) Arc 5) Cubic 6) Slice>> [NoOpI, NIL, NIL, NIL, NIL, NIL, NIL], -- 0) NoOp [NoOpI, LinLinI, NIL, NIL, NIL, NIL, NIL], -- 1) Line [NoOpI, CirLinI, CirCirI, NIL, NIL, NIL, NIL], -- 2) Circle [NoOpI, EdgLinI, EdgCirI, EdgEdgI, NIL, NIL, NIL], -- 3) Edge [NoOpI, ArcLinI, ArcCirI, ArcEdgI, ArcArcI, NIL, NIL], -- 4) Arc [NoOpI, CubLinI, NoOpI, CubEdgI, NoOpI, NoOpI, NIL], -- 5) Cubic [NoOpI, SlcLinI, SlcCirI, NoOpI, NoOpI, NoOpI, NoOpI] -- 6) Slice ]; NoOpI: IntersectionProc = { iPoints ¬ NIL; tangency ¬ NIL; }; LinLinI: IntersectionProc = { <> l1: Line ¬ NARROW[c1]; l2: Line ¬ NARROW[c2]; point: Point; parallel: BOOL ¬ FALSE; [point, parallel] ¬ Lines2d.LineMeetsLine[l1, l2]; IF NOT parallel THEN {iPoints ¬ LIST[point]; tangency ¬ LIST[FALSE]} ELSE {iPoints ¬ NIL; tangency ¬ NIL}; }; CirLinI: IntersectionProc = { <> circle: Circle ¬ NARROW[c1]; line: Line ¬ NARROW[c2]; points: ARRAY [1..2] OF Point; hitCount: [0..2]; tangent: BOOL ¬ FALSE; [points, hitCount, tangent] ¬ GGCircles.CircleMeetsLine[circle, line]; FOR i: NAT IN [1..hitCount] DO iPoints ¬ CONS[points[i], iPoints]; tangency ¬ CONS[tangent, tangency]; ENDLOOP; }; CirCirI: IntersectionProc = { <> circle1: Circle ¬ NARROW[c1]; circle2: Circle ¬ NARROW[c2]; points: ARRAY [1..2] OF Point; hitCount: [0..2]; tangent: BOOL ¬ FALSE; [points, hitCount, tangent] ¬ GGCircles.CircleMeetsCircle[circle1, circle2]; FOR i: NAT IN [1..hitCount] DO iPoints ¬ CONS[points[i], iPoints]; tangency ¬ CONS[tangent, tangency]; ENDLOOP; }; EdgLinI: IntersectionProc = { <> edge: Edge ¬ NARROW[c1]; line: Line ¬ NARROW[c2]; point: Point; noHit: BOOL ¬ FALSE; [point, noHit] ¬ Lines2d.LineMeetsEdge[line, edge]; IF NOT noHit THEN {iPoints ¬ LIST[point]; tangency ¬ LIST[FALSE]} ELSE {iPoints ¬ NIL; tangency ¬ NIL}; }; EdgCirI: IntersectionProc = { <> edge: Edge ¬ NARROW[c1]; circle: Circle ¬ NARROW[c2]; points: ARRAY [1..2] OF Point; hitCount: [0..2]; tangent: BOOL ¬ FALSE; [points, hitCount, tangent] ¬ GGCircles.CircleMeetsEdge[circle, edge]; FOR i: NAT IN [1..hitCount] DO iPoints ¬ CONS[points[i], iPoints]; tangency ¬ CONS[tangent, tangency]; ENDLOOP; }; EdgEdgI: IntersectionProc = { <> e1: Edge ¬ NARROW[c1]; e2: Edge ¬ NARROW[c2]; point: Point; noHit: BOOL ¬ FALSE; [point, noHit] ¬ Lines2d.EdgeMeetsEdge[e1, e2]; IF NOT noHit THEN {iPoints ¬ LIST[point]; tangency ¬ LIST[FALSE]} ELSE {iPoints ¬ NIL; tangency ¬ NIL}; }; ArcLinI: IntersectionProc = { <> arc: Arc ¬ NARROW[c1]; line: Line ¬ NARROW[c2]; points: ARRAY [1..2] OF Point; hitCount: [0..2]; tangent: BOOL ¬ FALSE; [points, hitCount, tangent] ¬ GGCircles.ArcMeetsLine[arc, line]; FOR i: NAT IN [1..hitCount] DO iPoints ¬ CONS[points[i], iPoints]; tangency ¬ CONS[tangent, tangency]; ENDLOOP; }; ArcCirI: IntersectionProc = { <> arc: Arc ¬ NARROW[c1]; circle: Circle ¬ NARROW[c2]; points: ARRAY [1..2] OF Point; hitCount: [0..2]; tangent: BOOL ¬ FALSE; [points, hitCount, tangent] ¬ GGCircles.CircleMeetsArc[circle, arc]; FOR i: NAT IN [1..hitCount] DO iPoints ¬ CONS[points[i], iPoints]; tangency ¬ CONS[tangent, tangency]; ENDLOOP; }; ArcEdgI: IntersectionProc = { <> arc: Arc ¬ NARROW[c1]; edge: Edge ¬ NARROW[c2]; points: ARRAY [1..2] OF Point; hitCount: [0..2]; tangent: BOOL ¬ FALSE; [points, hitCount, tangent] ¬ GGCircles.ArcMeetsEdge[arc, edge]; FOR i: NAT IN [1..hitCount] DO iPoints ¬ CONS[points[i], iPoints]; tangency ¬ CONS[tangent, tangency]; ENDLOOP; }; ArcArcI: IntersectionProc = { <> arc1: Arc ¬ NARROW[c1]; arc2: Arc ¬ NARROW[c2]; points: ARRAY [1..2] OF Point; hitCount: [0..2]; tangent: BOOL ¬ FALSE; <<[points, hitCount] _ GGCircles.ArcMeetsArc[arc1, arc2];>> [points, hitCount, tangent] ¬ GGCircles.ArcMeetsArc[arc1, arc2]; FOR i: NAT IN [1..hitCount] DO iPoints ¬ CONS[points[i], iPoints]; tangency ¬ CONS[tangent, tangency]; ENDLOOP; }; CubLinI: IntersectionProc = { <> bezier: BezierRef ¬ NARROW[c1]; line: Line ¬ NARROW[c2]; points: ARRAY [0..2] OF Point; hitCount: [0..3]; tangent: ARRAY [0..2] OF BOOL ¬ ALL[FALSE]; [points, hitCount, tangent] ¬ CubicPaths.CubicMeetsLine[bezier­, -line.s, line.c, -line.d]; FOR i: NAT IN [0..hitCount) DO iPoints ¬ CONS[points[i], iPoints]; tangency ¬ CONS[tangent[i], tangency]; ENDLOOP; }; CubicMeetsEdge: PROC [bezier: BezierRef, edge: Edge] RETURNS [points: ARRAY [0..2] OF Point, hitCount: [0..3] ¬ 0, tangent: ARRAY [0..2] OF BOOL ¬ ALL[FALSE]] = { linePoints: ARRAY [0..2] OF Point; lineHitCount: [0..3]; lineTangents: ARRAY [0..2] OF BOOL ¬ ALL[FALSE]; [linePoints, lineHitCount, lineTangents] ¬ CubicPaths.CubicMeetsLine[bezier­, -edge.line.s, edge.line.c, -edge.line.d]; FOR i: NAT IN [0..lineHitCount) DO IF Lines2d.OnEdge[linePoints[i], edge] THEN { points[hitCount] ¬ linePoints[i]; tangent[hitCount] ¬ lineTangents[i]; hitCount ¬ hitCount + 1; }; ENDLOOP; }; CubEdgI: IntersectionProc = { IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL]; bezier: BezierRef ¬ NARROW[c1]; edge: Edge ¬ NARROW[c2]; points: ARRAY [0..2] OF Point; hitCount: [0..3]; tangent: ARRAY [0..2] OF BOOL ¬ ALL[FALSE]; [points, hitCount, tangent] ¬ CubicMeetsEdge[bezier, edge]; FOR i: NAT IN [0..hitCount) DO iPoints ¬ CONS[points[i], iPoints]; tangency ¬ CONS[tangent[i], tangency]; ENDLOOP; }; SlcLinI: IntersectionProc = { sliceD: SliceDescriptor ¬ NARROW[c1]; line: Line ¬ NARROW[c2]; [iPoints, ----] ¬ GGSliceOps.LineIntersection[sliceD, line]; FOR list: LIST OF Point ¬ iPoints, list.rest UNTIL list = NIL DO tangency ¬ CONS[FALSE, tangency]; ENDLOOP; }; SlcCirI: IntersectionProc = { sliceD: SliceDescriptor ¬ NARROW[c1]; circle: Circle ¬ NARROW[c2]; [iPoints, ----] ¬ GGSliceOps.CircleIntersection[sliceD, circle]; FOR list: LIST OF Point ¬ iPoints, list.rest UNTIL list = NIL DO tangency ¬ CONS[FALSE, tangency]; ENDLOOP; }; <> NewMultiGravityPool: PUBLIC PROC [] RETURNS [REF]= { -- reuseable storage for BestPointAndCurve proc to avoid NEWs pool: MultiGravityPool ¬ NEW[MultiGravityPoolObj]; pool.bestpoints ¬ NEW[BestPointsObj[MaxFeatures]]; pool.bestcurves ¬ NEW[BestPointsObj[MaxFeatures]]; pool.bestfaces ¬ NEW[BestFacesObj[MaxFeatures]]; FOR i: NAT IN [0..MaxFeatures) DO pool.bestpoints[i] ¬ NEW[GoodPointObj]; pool.bestcurves[i] ¬ NEW[GoodPointObj]; pool.bestfaces[i] ¬ NEW[GoodPointObj]; ENDLOOP; RETURN[pool]; }; END.