GGMultiGravityImpl.mesa
Copyright © 1986 by Xerox Corporation. All rights reserved.
Last edited by Bier on June 3, 1986 2:42:42 pm PDT
Contents: Performs hit testing similar to GGGravity. Instead of returning a single nearest feature, we return the N (or fewer) nearest features which are within a given tolerance distance from the test point. The algorithm used is described in [Cyan]<Gargoyle>Documentation>MultiGravity.tioga.
DIRECTORY
GGBasicTypes, GGButtons, GGCaret, GGCircles, GGLines, GGInterfaceTypes, GGModelTypes, GGMultiGravity, GGSegmentTypes, GGStatistics, GGUtility, GGVector, RealFns, Rope;
GGMultiGravityImpl: CEDAR PROGRAM
IMPORTS GGButtons, GGCaret, GGCircles, GGLines, GGStatistics, GGVector, RealFns
EXPORTS GGMultiGravity = BEGIN
Arc: TYPE = GGBasicTypes.Arc;
AlignmentCircle: TYPE = GGInterfaceTypes.AlignmentCircle;
AlignmentLine: TYPE = GGInterfaceTypes.AlignmentLine;
AlignmentPoint: TYPE = REF AlignmentPointObj;
AlignmentPointObj: TYPE = GGInterfaceTypes.AlignmentPointObj;
Caret: TYPE = GGInterfaceTypes.Caret;
Circle: TYPE = GGBasicTypes.Circle;
Edge: TYPE = GGBasicTypes.Edge;
FeatureData: TYPE = REF FeatureDataObj;
FeatureDataObj: TYPE = GGModelTypes.FeatureDataObj;
GargoyleData: TYPE = GGInterfaceTypes.GargoyleData;
GoodCurve: TYPE = REF GoodCurveObj;
GoodCurveObj: TYPE = GGMultiGravity.GoodCurveObj;
GoodPoint: TYPE = REF GoodPointObj;
GoodPointObj: TYPE = GGMultiGravity.GoodPointObj;
GoodPointType: TYPE = GGMultiGravity.GoodPointType;
JointGenerator: TYPE = GGModelTypes.JointGenerator;
Line: TYPE = GGBasicTypes.Line;
NearDistances: TYPE = REF NearDistancesObj;
NearDistancesObj: TYPE = GGMultiGravity.NearDistancesObj;
NearFeatures: TYPE = REF NearFeaturesObj;
NearFeaturesObj: TYPE = GGMultiGravity.NearFeaturesObj;
NearPoints: TYPE = REF NearPointsObj;
NearPointsAndCurves: TYPE = REF NearPointsAndCurvesObj;
NearPointsAndCurvesObj: TYPE = GGMultiGravity.NearPointsAndCurvesObj;
NearPointsObj: TYPE = GGMultiGravity.NearPointsObj;
ObjectBag: TYPE = REF ObjectBagObj;
ObjectBagObj: TYPE = GGInterfaceTypes.ObjectBagObj;
Outline: TYPE = GGModelTypes.Outline;
OutlineDescriptor: TYPE = REF OutlineDescriptorObj;
OutlineDescriptorObj: TYPE = GGModelTypes.OutlineDescriptorObj;
Point: TYPE = GGBasicTypes.Point;
Segment: TYPE = GGSegmentTypes.Segment;
SegmentGenerator: TYPE = GGModelTypes.SegmentGenerator;
Sequence: TYPE = GGModelTypes.Sequence;
Slice: TYPE = GGModelTypes.Slice;
SliceDescriptor: TYPE = GGModelTypes.SliceDescriptor;
TriggerBag: TYPE = REF TriggerBagObj;
TriggerBagObj: TYPE = GGInterfaceTypes.TriggerBagObj;
MultiGravityPool: TYPE = REF MultiGravityPoolObj;
MultiGravityPoolObj: TYPE = RECORD [
distances: NearDistances,
features: NearFeatures,
bestpoints: BestPoints,
bestcurves: BestCurves
];
BestCurves: TYPE = REF BestCurvesObj;
BestCurvesObj: TYPE = RECORD [
size: NAT,
max, min: REAL,
overflow: BOOL,
curves: SEQUENCE len: NAT OF GoodCurve];
BestPoints: TYPE = REF BestPointsObj;
BestPointsObj: TYPE = RECORD [
size: NAT,
max, min: REAL,
overflow: BOOL,
points: SEQUENCE len: NAT OF GoodPoint];
Shared with GGGravityImpl
EmptyBag: PROC [objectBag: ObjectBag] RETURNS [BOOL] = {
RETURN[
objectBag.slopeLines = NIL AND
objectBag.angleLines = NIL AND
objectBag.radiiCircles = NIL AND
objectBag.distanceLines = NIL AND
objectBag.midpoints = NIL AND
objectBag.intersectionPoints = NIL];
};
EmptyTriggers: PROC [triggerBag: TriggerBag] RETURNS [BOOL] = {
RETURN[
triggerBag.outlines = NIL AND
triggerBag.slices = NIL AND
triggerBag.intersectionPoints = NIL AND
triggerBag.anchor = NIL
];
};
Problem: PUBLIC SIGNAL [msg: Rope.ROPE] = CODE;
Arbitration
[Artwork node; type 'ArtworkInterpress on' to command tool]
We arbitrate between those points which are within an epsilon-width ring of the nearest point.
Map: PUBLIC PROC [testPoint: Point, criticalR: REAL, currentObjects: ObjectBag, activeObjects: TriggerBag, gargoyleData: GargoyleData, intersections: BOOL] RETURNS [resultPoint: Point, feature: FeatureData] = {
Dispatches to StrictDistance, InnerCircle, or does nothing depending on the currently selected gravity type. If intersections is TRUE, compute the intersections of the objects that are in the bags.
ENABLE UNWIND => gargoyleData.multiGravityPool ← NewMultiGravityPool[]; -- in case an ABORT happened while pool was in use
GGStatistics.StartInterval[$MultiMap, GGStatistics.GlobalTable[]];
SELECT GGButtons.GetButtonState[gargoyleData.hitTest.gravButton] FROM
on => SELECT gargoyleData.hitTest.gravityType FROM
strictDistance =>
[resultPoint, feature] ← StrictDistance[testPoint, criticalR, currentObjects, activeObjects, gargoyleData];
innerCircle =>
[resultPoint, feature] ← InnerCircle[testPoint, criticalR, gargoyleData.hitTest.innerR, currentObjects, activeObjects, gargoyleData, intersections];
ENDCASE => ERROR;
off => {
resultPoint ← testPoint;
feature ← NIL;
};
ENDCASE => ERROR;
GGStatistics.StopInterval[$MultiMap, GGStatistics.GlobalTable[]];
};
PrepareWinner: PROC [nearPointsAndCurves: NearPointsAndCurves, index: NAT] RETURNS [resultPoint: Point, feature: FeatureData] = {
WITH nearPointsAndCurves[index] SELECT FROM
goodPoint: GoodPoint => {
resultPoint ← goodPoint.point;
ExtractResultFromPoint[goodPoint, goodPoint.featureData]; -- stuffs hit info into featureData
feature ← goodPoint.featureData;
};
goodCurve: GoodCurve => {
resultPoint ← goodCurve.point;
ExtractResultFromCurve[goodCurve, goodCurve.featureData]; -- stuffs hit info into featureData
feature ← goodCurve.featureData;
};
ENDCASE => ERROR;
};
StrictDistance: PUBLIC PROC [testPoint: Point, criticalR: REAL, objectBag: ObjectBag, sceneBag: TriggerBag, gargoyleData: GargoyleData] RETURNS [resultPoint: Point, feature: FeatureData] = {
Someday, GoodPoint and GoodCurve should become a single variant record and distances will be unnecessary.
nearPointsAndCurves: NearPointsAndCurves;
count: NAT;
[nearPointsAndCurves, count] ← MultiStrictDistance[testPoint, criticalR, objectBag, sceneBag, gargoyleData];
IF count = 0 THEN RETURN [testPoint, NIL];
IF count = 1 THEN RETURN PrepareWinner[nearPointsAndCurves, 0]
ELSE {
Otherwise, let's do arbitration.
distances: NearDistances ← NARROW[gargoyleData.multiGravityPool, MultiGravityPool].distances;
features: NearFeatures ← NARROW[gargoyleData.multiGravityPool, MultiGravityPool].features;
nearestDist: REAL;
bestSceneObject: INT;
neighborCount: NAT ← 1;
s: REAL = 0.072; -- 1/1000 inches
FOR i: NAT IN [0..count) DO
WITH nearPointsAndCurves[i] SELECT FROM
goodPoint: GoodPoint => {
distances[i] ← goodPoint.dist;
features[i] ← goodPoint.featureData};
goodCurve: GoodCurve => {
distances[i] ← goodCurve.dist;
features[i] ← goodCurve.featureData;};
ENDCASE => ERROR;
ENDLOOP;
nearestDist ← distances[0];
FOR i: NAT IN [1..count) DO
IF distances[i] - nearestDist < s THEN neighborCount ← neighborCount + 1;
ENDLOOP;
IF neighborCount = 1 THEN RETURN PrepareWinner[nearPointsAndCurves, 0];
We have more than one "equally close" features. Now we choose on the following basis:
1) Prefer scene objects to alignment lines.
2) Prefer points to lines.
Later, we will prefer objects that say the testpoint is "inside" them to those that don't.
bestSceneObject ← -1;
FOR i: NAT IN [0..neighborCount) DO
IF features[i].type = outline OR features[i].type = slice THEN {
SELECT features[i].resultType FROM
joint, controlPoint, intersectionPoint =>
RETURN PrepareWinner[nearPointsAndCurves, i];
ENDCASE => IF bestSceneObject = -1 THEN bestSceneObject ← i;
};
REPEAT
FINISHED => {
IF bestSceneObject >= 0 THEN
RETURN PrepareWinner[nearPointsAndCurves, bestSceneObject]
ELSE RETURN PrepareWinner[nearPointsAndCurves, 0];
};
ENDLOOP;
RETURN PrepareWinner[nearPointsAndCurves, 0];
};
};
ResultFeatureType: TYPE = {joint, segment, controlPoint, slice, distanceLine, slopeLine, angleLine, symmetryLine, radiiCircle, intersectionPoint, midpoint, anchor};
InnerCircle: PUBLIC PROC [testPoint: Point, criticalR: REAL, innerR: REAL, currentObjects: ObjectBag, activeObjects: TriggerBag, gargoyleData: GargoyleData, intersections: BOOL] RETURNS [resultPoint: Point, feature: FeatureData] = {
count: NAT;
nearPointsAndCurves: NearPointsAndCurves;
[nearPointsAndCurves, count] ← MultiInnerCircle[testPoint, criticalR, innerR, currentObjects, activeObjects, gargoyleData, intersections];
IF count = 0 THEN RETURN [testPoint, NIL];
IF count = 1 THEN RETURN PrepareWinner[nearPointsAndCurves, 0]
ELSE {
Otherwise, let's do arbitration.
distances: NearDistances ← NARROW[gargoyleData.multiGravityPool, MultiGravityPool].distances;
features: NearFeatures ← NARROW[gargoyleData.multiGravityPool, MultiGravityPool].features;
neighborCount: NAT ← 1;
s: REAL = 0.072; -- 1/1000 inches
nearestDist: REAL;
FOR i: NAT IN [0..count) DO
WITH nearPointsAndCurves[i] SELECT FROM
goodPoint: GoodPoint => {
distances[i] ← goodPoint.dist;
features[i] ← goodPoint.featureData};
goodCurve: GoodCurve => {
distances[i] ← goodCurve.dist;
features[i] ← goodCurve.featureData;};
ENDCASE => ERROR;
ENDLOOP;
nearestDist ← distances[0];
FOR i: NAT IN [1..count) DO
IF distances[i] - nearestDist < s THEN neighborCount ← neighborCount + 1;
ENDLOOP;
IF neighborCount = 1 THEN RETURN PrepareWinner[nearPointsAndCurves, 0];
Now we choose on the following basis:
1) Prefer scene objects to alignment lines.
Later, we will prefer objects that say the testpoint is "inside" them to those that don't.
FOR i: NAT IN [0..neighborCount) DO
IF features[i].type = outline OR features[i].type = slice THEN {
RETURN PrepareWinner[nearPointsAndCurves, i];
};
REPEAT
FINISHED => RETURN PrepareWinner[nearPointsAndCurves, 0];
ENDLOOP;
};
};
NearestNeighborsPlusSome: PROC [q: Point, initialD: REAL, currentObjects: ObjectBag, activeObjects: TriggerBag, anchor: Caret, gargoyleData: GargoyleData, distinguishedPointsOnly: BOOL ← FALSE] RETURNS [g: NearPointsAndCurves, count: NAT] = {
};
Multi-Gravity Routines
MultiMap: PUBLIC PROC [testPoint: Point, criticalR: REAL, currentObjects: ObjectBag, activeObjects: TriggerBag, gargoyleData: GargoyleData, intersections: BOOL] RETURNS [nearPointsAndCurves: NearPointsAndCurves, count: NAT] = {
Dispatches to MultiStrictDistance or MultiInnerCircle as appropriate.
ENABLE UNWIND => gargoyleData.multiGravityPool ← NewMultiGravityPool[]; -- in case an ABORT happened while pool was in use
GGStatistics.StartInterval[$MultiMap, GGStatistics.GlobalTable[]];
SELECT GGButtons.GetButtonState[gargoyleData.hitTest.gravButton] FROM
on => SELECT gargoyleData.hitTest.gravityType FROM
strictDistance =>
[nearPointsAndCurves, count] ← MultiStrictDistance[testPoint, criticalR, currentObjects, activeObjects, gargoyleData];
innerCircle =>
[nearPointsAndCurves, count] ← MultiInnerCircle[testPoint, criticalR, gargoyleData.hitTest.innerR, currentObjects, activeObjects, gargoyleData, intersections];
ENDCASE => ERROR;
off => {
nearPointsAndCurves ← NIL;
count ← 0;
};
ENDCASE => ERROR;
GGStatistics.StopInterval[$MultiMap, GGStatistics.GlobalTable[]];
};
MultiStrictDistance: PUBLIC PROC [testPoint: Point, criticalR: REAL, currentObjects: ObjectBag, activeObjects: TriggerBag, gargoyleData: GargoyleData] RETURNS [nearPointsAndCurves: NearPointsAndCurves, count: NAT] = {
Returns up to MaxFeatures closest features, their closest points, and their distances from the testpoint. Features outside of the critical radius, criticalR, will not be included. The results will be located in nearPointsAndCurves[0] .. nearPointsAndCurves[count-1].
bestCurves: BestCurves;
bestPoints: BestPoints;
pointCount, curveCount: NAT;
IF EmptyBag[currentObjects] AND EmptyTriggers[activeObjects] THEN
RETURN[NIL, 0];
[bestCurves, curveCount] ← CurvesInTolerance[currentObjects, activeObjects, testPoint, gargoyleData, criticalR];
SortCurves[bestCurves, curveCount];
[bestPoints, pointCount] ← PointsInTolerance[bestCurves, curveCount, currentObjects, activeObjects, testPoint, criticalR, gargoyleData, FALSE];
SortPoints[bestPoints, pointCount];
count ← MIN[pointCount + curveCount, MaxFeatures];
nearPointsAndCurves ← NEW[NearPointsAndCurvesObj[count]];
MergePointsAndCurves[bestPoints, pointCount, bestCurves, curveCount, nearPointsAndCurves, count];
};
MultiInnerCircle: PUBLIC PROC [testPoint: Point, criticalR: REAL, innerR: REAL, currentObjects: ObjectBag, activeObjects: TriggerBag, gargoyleData: GargoyleData, intersections: BOOL] RETURNS [nearPointsAndCurves: NearPointsAndCurves, count: NAT] = {
Returns up to MaxFeatures closest features, their closest points, and their distances from the testpoint. Features outside of the critical radius, criticalR, will not be included. The results will be located in nearPointsAndCurves[0] .. nearPointsAndCurves[count-1]. If any points are within the inner radius innerR, then only points (e.g. vertices, control points, and intersection points) will be mentioned. Otherwise, nearPointsAndCurves will consist of a mixture of points and curves. However, if criticalR = innerR THEN only points or only curves will be returned.
bestCurves: BestCurves;
bestPoints: BestPoints;
pointCount, curveCount: NAT;
IF EmptyBag[currentObjects] AND EmptyTriggers[activeObjects] THEN RETURN[NIL, 0];
[bestCurves, curveCount] ← CurvesInTolerance[currentObjects, activeObjects, testPoint, gargoyleData, criticalR];
SortCurves[bestCurves, curveCount];
[bestPoints, pointCount] ← PointsInTolerance[bestCurves, curveCount, currentObjects, activeObjects, testPoint, criticalR, gargoyleData, intersections];
SortPoints[bestPoints, pointCount];
IF pointCount > 0 AND bestPoints[0].dist < innerR THEN {
count ← pointCount;
nearPointsAndCurves ← NEW[NearPointsAndCurvesObj[count]];
NearPointsFromPoints[bestPoints, pointCount, nearPointsAndCurves];
}
ELSE {
count ← MIN[pointCount + curveCount, MaxFeatures];
nearPointsAndCurves ← NEW[NearPointsAndCurvesObj[count]];
MergePointsAndCurves[bestPoints, pointCount, bestCurves, curveCount, nearPointsAndCurves, count];
};
};
ExtractResultFromCurve: PROC [curve: GoodCurve, feature: FeatureData] = {
SELECT feature.type FROM
outline => {
feature.hitPart ← curve.hitData;
feature.resultType ← outline;
};
slice => {
feature.hitPart ← curve.hitData;
feature.resultType ← slice;
};
slopeLine => feature.resultType ← slopeLine;
angleLine => feature.resultType ← angleLine;
radiiCircle => feature.resultType ← radiiCircle;
distanceLine => feature.resultType ← distanceLine;
ENDCASE => SIGNAL Problem[msg: "Unimplemented result type."];
};
ExtractResultFromPoint: PROC [goodPoint: GoodPoint, feature: FeatureData] = {
SELECT goodPoint.type FROM
outline => {
feature.hitPart ← goodPoint.hitData;
feature.resultType ← outline;
};
slice => {
feature.hitPart ← goodPoint.hitData;
feature.resultType ← slice;
};
intersectionPoint => {
feature.hitPart ← NIL;
feature.resultType ← intersectionPoint;
};
midpoint => {
midPoint features contain a reasonable segNum in their hitPart
feature.resultType ← midpoint;
};
anchor => {
anchors contain the anchor point in their hitPart
feature.resultType ← anchor;
};
ENDCASE => SIGNAL Problem [msg: "Unimplemented result type."];
};
FindIntersections: PROC [bestCurves: BestCurves, curveCount: NAT, thisPoint: GoodPoint, q: Point, tolerance: REAL, h: BestPoints] = {
curveI, curveJ: GoodCurve;
theseIPoints: LIST OF Point;
success: BOOL;
FOR i: NAT IN [0..curveCount) DO
curveI ← bestCurves[i];
FOR j: NAT IN [i+1..curveCount) DO
curveJ ← bestCurves[j];
theseIPoints ← CurveMeetsCurve[curveI, curveJ];
FOR list: LIST OF Point ← theseIPoints, list.rest UNTIL list = NIL DO
thisPoint.point ← list.first;
thisPoint.type ← intersectionPoint;
thisPoint.dist ← GGVector.Distance[thisPoint.point, q];
success ← thisPoint.dist <= tolerance;
IF success THEN {
featureData: FeatureData ← NEW[FeatureDataObj];
alignmentPoint: AlignmentPoint ← NEW[AlignmentPointObj ← [point: thisPoint.point, curve1: curveI.featureData, curve2: curveJ.featureData]];
featureData.type ← intersectionPoint;
featureData.shape ← alignmentPoint;
thisPoint.featureData ← featureData;
MergePoint[thisPoint, h];
};
ENDLOOP;
ENDLOOP;
ENDLOOP;
};
PointsInTolerance: PROC [bestCurves: BestCurves, curveCount: NAT, objectBag: ObjectBag, sceneObjects: TriggerBag, q: Point, t: REAL, gargoyleData: GargoyleData, intersections: BOOL] RETURNS [h: BestPoints, pointCount: NAT] = {
thisPoint: GoodPoint;
For each gravity active point, find its distance from the testpoint. Package this information up into the thisPoint record. Then call MergePoint, which will add this point to the list of best points, if appropriate.
ProcessPoint: PROC [thisPoint: GoodPoint, featureData: FeatureData] = {
dSquared: REAL;
dSquared ← GGVector.DistanceSquared[thisPoint.point, q];
thisPoint.hitData ← NIL;
IF dSquared < tSquared THEN {
thisPoint.dist ← RealFns.SqRt[dSquared];
thisPoint.featureData ← featureData;
MergePoint[thisPoint, h];
};
};
ProcessSlice: PROC [sliceD: SliceDescriptor, thisPoint: GoodPoint, featureData: FeatureData] = {
[thisPoint.point, thisPoint.dist, thisPoint.hitData, success] ← sliceD.slice.class.closestPoint[sliceD, q, t];
IF success THEN {
IF thisPoint.dist < t THEN {
thisPoint.featureData ← featureData;
MergePoint[thisPoint, h];
};
};
};
ProcessOutline: PROC [outlineD: OutlineDescriptor, thisPoint: GoodPoint, featureData: FeatureData] = {
[thisPoint.point, thisPoint.dist, thisPoint.hitData, success] ← outlineD.slice.class.closestPoint[outlineD, q, t];
IF success THEN {
IF thisPoint.dist < t THEN {
thisPoint.featureData ← featureData;
MergePoint[thisPoint, h];
};
};
};
sliceD: SliceDescriptor;
outlineD: OutlineDescriptor;
featureData: FeatureData;
success: BOOL;
tSquared: REAL ← t*t;
thisPoint ← NEW[GoodPointObj];
h ← BestPointsFromPool[gargoyleData];
IF intersections THEN FindIntersections[bestCurves, curveCount, thisPoint, q, t, h];
FOR iPoints: LIST OF FeatureData ← objectBag.intersectionPoints, iPoints.rest UNTIL iPoints = NIL DO
featureData ← iPoints.first;
thisPoint.type ← intersectionPoint;
thisPoint.point ← NARROW[featureData.shape, AlignmentPoint].point;
ProcessPoint[thisPoint, featureData];
ENDLOOP;
FOR midpoints: LIST OF FeatureData ← objectBag.midpoints, midpoints.rest UNTIL midpoints = NIL DO
featureData ← midpoints.first;
thisPoint.type ← midpoint;
thisPoint.point ← NARROW[featureData.shape, AlignmentPoint].point;
ProcessPoint[thisPoint, featureData];
ENDLOOP;
FOR slices: LIST OF FeatureData ← sceneObjects.slices, slices.rest UNTIL slices = NIL DO
featureData ← slices.first;
thisPoint.type ← slice;
sliceD ← NARROW[featureData.shape, SliceDescriptor];
ProcessSlice[sliceD, thisPoint, featureData];
ENDLOOP;
FOR outlines: LIST OF FeatureData ← sceneObjects.outlines, outlines.rest UNTIL outlines = NIL DO
featureData ← outlines.first;
thisPoint.type ← outline;
outlineD ← NARROW[featureData.shape];
ProcessOutline[outlineD, thisPoint, featureData];
ENDLOOP;
Handle the anchor.
featureData ← sceneObjects.anchor;
IF featureData # NIL THEN {
anchor: Caret;
anchor ← NARROW[featureData.shape];
IF NOT GGCaret.Exists[anchor] THEN ERROR;
thisPoint.type ← anchor;
thisPoint.point ← GGCaret.GetPoint[anchor];
ProcessPoint[thisPoint, featureData];
};
pointCount ← h.size;
};
CurvesInTolerance: PROC [objectBag: ObjectBag, sceneObjects: TriggerBag, q: Point, gargoyleData: GargoyleData, t: REAL] RETURNS [h: BestCurves, curveCount: NAT] = {
For each slopeLine, find the distance of the slopeLine from the testpoint. Package this information up into the thisCurve record. Then call MergeCurve, which will add this curve to the list of best curves, if appropriate. Do not merge any curves that are farther away than tolerance.
ProcessLine: PROC [line: Line, thisCurve: GoodCurve, featureData: FeatureData] = {
thisCurve.dist ← GGLines.LineDistance[q, line];
IF thisCurve.dist < t THEN {
thisCurve.featureData ← featureData;
thisCurve.point ← GGLines.PointProjectedOntoLine[q, line];
thisCurve.hitData ← NIL;
added ← MergeCurve[thisCurve, h];
}
};
ProcessCircle: PROC [circle: Circle, thisCurve: GoodCurve, featureData: FeatureData] = {
thisCurve.dist ← GGCircles.CircleDistance[q, circle];
IF thisCurve.dist < t THEN {
thisCurve.featureData ← featureData;
thisCurve.point ← GGCircles.PointProjectedOntoCircle[q, circle];
thisCurve.hitData ← NIL;
added ← MergeCurve[thisCurve, h];
};
};
ProcessSlice: PROC [sliceD: SliceDescriptor, thisCurve: GoodCurve, featureData: FeatureData] = {
success: BOOL;
[thisCurve.point, thisCurve.dist, thisCurve.hitData, success] ← sliceD.slice.class.closestSegment[sliceD, q, t];
IF success THEN {
IF thisCurve.dist < t THEN {
thisCurve.featureData ← featureData;
added ← MergeCurve[thisCurve, h];
};
};
};
ProcessOutline: PROC [outlineD: OutlineDescriptor, thisCurve: GoodCurve, featureData: FeatureData] = {
success: BOOL;
[thisCurve.point, thisCurve.dist, thisCurve.hitData, success] ← outlineD.slice.class.closestSegment[outlineD, q, t];
IF success THEN {
IF thisCurve.dist < t THEN {
thisCurve.featureData ← featureData;
added ← MergeCurve[thisCurve, h];
};
};
};
line: Line;
circle: Circle;
sliceD: SliceDescriptor;
outlineD: OutlineDescriptor;
featureData: FeatureData;
added: BOOL;
thisCurve: GoodCurve ← NEW[GoodCurveObj];
h ← BestCurvesFromPool[gargoyleData];
FOR slopeLines: LIST OF FeatureData ← objectBag.slopeLines, slopeLines.rest UNTIL slopeLines = NIL DO
featureData ← slopeLines.first;
line ← NARROW[featureData.shape, AlignmentLine].line;
ProcessLine[line, thisCurve, featureData];
ENDLOOP;
FOR angleLines: LIST OF FeatureData ← objectBag.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 ← objectBag.distanceLines, dLines.rest UNTIL dLines = NIL DO
featureData ← dLines.first;
line ← NARROW[featureData.shape];
ProcessLine[line, thisCurve, featureData];
ENDLOOP;
FOR circles: LIST OF FeatureData ← objectBag.radiiCircles, circles.rest UNTIL circles = NIL DO
featureData ← circles.first;
circle ← NARROW[featureData.shape, AlignmentCircle].circle;
ProcessCircle[circle, thisCurve, featureData];
ENDLOOP;
Sensitive Scene Objects.
FOR slices: LIST OF FeatureData ← sceneObjects.slices, slices.rest UNTIL slices = NIL DO
featureData ← slices.first;
sliceD ← NARROW[featureData.shape, SliceDescriptor];
ProcessSlice[sliceD, thisCurve, featureData];
ENDLOOP;
FOR outlines: LIST OF FeatureData ← sceneObjects.outlines, outlines.rest UNTIL outlines = NIL DO
featureData ← outlines.first;
outlineD ← NARROW[featureData.shape, OutlineDescriptor];
ProcessOutline[outlineD, thisCurve, featureData];
ENDLOOP;
curveCount ← h.size;
}; -- end CurvesInTolerance
MergePoint: PROC [thisPoint: GoodPoint, h: BestPoints] = {
d: REAL ← thisPoint.dist;
n: NAT = MaxFeatures;
SELECT TRUE FROM
d > h.max AND h.size < n => {h.max ← d; GOTO Add};
d <= h.max AND h.size < n => GOTO Add;
d < h.max AND h.size = n => GOTO AddAndComputeNewMax;
d > h.max AND h.size = n => GOTO NoChange; -- we already have n and this is no better
d = h.max AND h.size = n => {h.overflow ← TRUE; GOTO NoChange};
ENDCASE => SIGNAL Problem[msg: "Impossible case."];
EXITS
Add => {
d: REAL ← thisPoint.dist;
h[h.size]^ ← thisPoint^;
h.size ← h.size + 1;
h.min ← IF d < h.min THEN d ELSE h.min;
};
AddAndComputeNewMax => {
d: REAL ← thisPoint.dist;
newMax: REAL;
iMax: NAT; bestDist: REAL;
iMax ← 0; bestDist ← 0.0;
FOR i: NAT IN [0..MaxFeatures-1] DO
IF h[i].dist > bestDist THEN {iMax ← i; bestDist ← h[i].dist};
ENDLOOP;
h[iMax].dist ← d;
h[iMax]^ ← thisPoint^;
iMax ← 0; bestDist ← 0.0;
FOR i: NAT IN [0..MaxFeatures-1] DO
IF h[i].dist > bestDist THEN {iMax ← i; bestDist ← h[i].dist};
ENDLOOP;
newMax ← h[iMax].dist;
h.overflow ← IF newMax # h.max THEN TRUE ELSE FALSE;
h.max ← newMax;
};
NoChange => {
};
};
MergeCurve: PROC [thisCurve: GoodCurve, h: BestCurves] RETURNS [added: BOOL] = {
d: REAL ← thisCurve.dist;
n: NAT ← MaxFeatures;
SELECT TRUE FROM
d > h.max AND h.size < n => {h.max ← d; GOTO Add};
d <= h.max AND h.size < n => GOTO Add;
d < h.max AND h.size = n => GOTO AddAndComputeNewMax;
d > h.max AND h.size = n => GOTO NoChange; -- we already have n and this is no better
d = h.max AND h.size = n => {h.overflow ← TRUE; GOTO NoChange};
ENDCASE => SIGNAL Problem[msg: "Impossible case."];
EXITS
Add => {
d: REAL ← thisCurve.dist;
h[h.size]^ ← thisCurve^;
h.size ← h.size + 1;
h.min ← IF d < h.min THEN d ELSE h.min;
added ← TRUE;
};
AddAndComputeNewMax => {
d: REAL ← thisCurve.dist;
newMax: REAL;
iMax: NAT; bestDist: REAL;
iMax ← 0; bestDist ← 0.0;
FOR i: NAT IN [0..MaxFeatures-1] DO
IF h[i].dist > bestDist THEN {iMax ← i; bestDist ← h[i].dist};
ENDLOOP;
h[iMax].dist ← d;
h[iMax]^ ← thisCurve^;
iMax ← 0; bestDist ← 0.0;
FOR i: NAT IN [0..MaxFeatures-1] DO
IF h[i].dist > bestDist THEN {iMax ← i; bestDist ← h[i].dist};
ENDLOOP;
newMax ← h[iMax].dist;
h.overflow ← IF newMax # h.max THEN TRUE ELSE FALSE;
h.max ← newMax;
added ← TRUE;
};
NoChange => {
added ← FALSE;
};
};
NearPointsFromPoints: PROC [bestPoints: BestPoints, pointCount: NAT, nearPointsAndCurves: NearPointsAndCurves] = {
FOR i: NAT IN [0..pointCount-1] DO
nearPointsAndCurves[i] ← bestPoints[i];
ENDLOOP;
};
MergePointsAndCurves: PROC [bestPoints: BestPoints, pointCount: NAT, bestCurves: BestCurves, curveCount: NAT, nearPointsAndCurves: NearPointsAndCurves, count: NAT] = {
Merge the bestPoints and the bestCurves. There will be count elements in the result.
pointIndex, curveIndex: NAT;
pointDist, curveDist: REAL;
pointIndex ← 0;
curveIndex ← 0;
FOR i: NAT IN [0..count-1] 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 {
nearPointsAndCurves[i] ← bestPoints[pointIndex];
pointIndex ← pointIndex + 1;
}
ELSE {
nearPointsAndCurves[i] ← bestCurves[curveIndex];
curveIndex ← curveIndex + 1;
};
REPEAT
NoMorePoints => { -- finish up with Curves data
FOR k: NAT ← i, k+1 UNTIL k >= count DO
nearPointsAndCurves[k] ← bestCurves[curveIndex];
curveIndex ← curveIndex + 1;
ENDLOOP};
NoMoreCurves => { -- finish up with points data
FOR k: NAT ← i, k+1 UNTIL k >= count DO
nearPointsAndCurves[k] ← bestPoints[pointIndex];
pointIndex ← pointIndex + 1;
ENDLOOP};
ENDLOOP;
};
SortPoints: PROC [bestPoints: BestPoints, pointCount: NAT] = {
Sort the points in order of increasing distance. Since n is likely to be small, bubble sort is sensible:
temp: GoodPointObj;
FOR i: NAT IN [0..pointCount-2] DO
FOR j: NAT IN [1..pointCount-i-1] 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: BestCurves, curveCount: NAT] = {
Sort the curves in order of increasing distance. Since n is likely to be small, bubble sort is sensible:
temp: GoodCurveObj;
FOR i: NAT IN [0..curveCount-2] DO
FOR j: NAT IN [1..curveCount-i-1] DO
IF bestCurves[j-1].dist > bestCurves[j].dist THEN {
temp ← bestCurves[j]^;
bestCurves[j]^ ← bestCurves[j-1]^;
bestCurves[j-1]^ ← temp;
};
ENDLOOP;
ENDLOOP;
};
Computing Intersections
FeatureType: TYPE = {sequence, slice, distanceLine, slopeLine, angleLine, symmetryLine, radiiCircle, intersectionPoint, midpoint, anchor};
ClassifyCurve: PROC [curve: GoodCurve] 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 ← sliceD.slice.class.hitDataAsSimpleCurve[sliceD.slice, hitData];
IF simpleCurve = NIL THEN {
simpleCurve ← sliceD;
class ← 5;
RETURN;
};
};
outline => {
The asymmetry here is OK.
sliceD: OutlineDescriptor ← NARROW[feature.shape];
hitData: REF ANY ← curve.hitData;
simpleCurve ← sliceD.slice.class.hitDataAsSimpleCurve[sliceD.slice, hitData];
IF simpleCurve = NIL THEN {
class ← 0;
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;
ENDCASE => ERROR;
};
CurveMeetsCurve: PROC [c1, c2: GoodCurve] RETURNS [iPoints: LIST OF Point] = {
typeOfCurve1, typeOfCurve2: NAT;
simpleCurve1, simpleCurve2: REF ANY;
[typeOfCurve1, simpleCurve1] ← ClassifyCurve[c1];
[typeOfCurve2, simpleCurve2] ← ClassifyCurve[c2];
IF typeOfCurve1 >= typeOfCurve2 THEN
iPoints ← ComputeIntersection[typeOfCurve1][typeOfCurve2][simpleCurve1, simpleCurve2]
ELSE
iPoints ← ComputeIntersection[typeOfCurve2][typeOfCurve1][simpleCurve2, simpleCurve1]
};
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point];
ComputeIntersection: ARRAY [0..5] OF ARRAY [0..5] OF IntersectionProc = [
0) NoOp 1) Line 2) Circle 3) Edge 4) Arc 5) Slice
[NoOpI, NIL,  NIL,  NIL, NIL, NIL], -- 0) NoOp
[NoOpI, LinLinI,  NIL, NIL, NIL, NIL], -- 1) Line
[NoOpI, CirLinI, CirCirI, NIL, NIL, NIL], -- 2) Circle
[NoOpI,  EdgLinI,  EdgCirI, EdgEdgI, NIL, NIL], -- 3) Edge
[NoOpI, ArcLinI, ArcCirI, ArcEdgI, ArcArcI, NIL], -- 4) Arc
[NoOpI, SlcLinI, SlcCirI, NoOpI, NoOpI, NoOpI] -- 5) Slice
]; 
NoOpI: IntersectionProc = {
iPoints ← NIL;
};
LinLinI: IntersectionProc = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point];
l1: Line ← NARROW[c1];
l2: Line ← NARROW[c2];
point: Point;
parallel: BOOL;
[point, parallel] ← GGLines.LineMeetsLine[l1, l2];
IF NOT parallel THEN iPoints ← LIST[point] ELSE iPoints ← NIL;
};
CirLinI: IntersectionProc = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point];
circle: Circle ← NARROW[c1];
line: Line ← NARROW[c2];
points: ARRAY [1..2] OF Point;
hitCount: [0..2];
[points, hitCount] ← GGCircles.CircleMeetsLine[circle, line];
iPoints ← NIL;
FOR i: NAT IN [1..hitCount] DO
iPoints ← CONS[points[i], iPoints];
ENDLOOP;
};
CirCirI: IntersectionProc = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point];
circle1: Circle ← NARROW[c1];
circle2: Circle ← NARROW[c2];
points: ARRAY [1..2] OF Point;
hitCount: [0..2];
[points, hitCount] ← GGCircles.CircleMeetsCircle[circle1, circle2];
iPoints ← NIL;
FOR i: NAT IN [1..hitCount] DO
iPoints ← CONS[points[i], iPoints];
ENDLOOP;
};
EdgLinI: IntersectionProc = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point];
edge: Edge ← NARROW[c1];
line: Line ← NARROW[c2];
point: Point;
noHit: BOOL;
[point, noHit] ← GGLines.LineMeetsEdge[line, edge];
IF NOT noHit THEN iPoints ← LIST[point] ELSE iPoints ← NIL;
};
EdgCirI: IntersectionProc = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point];
edge: Edge ← NARROW[c1];
circle: Circle ← NARROW[c2];
points: ARRAY [1..2] OF Point;
hitCount: [0..2];
[points, hitCount] ← GGCircles.CircleMeetsEdge[circle, edge];
iPoints ← NIL;
FOR i: NAT IN [1..hitCount] DO
iPoints ← CONS[points[i], iPoints];
ENDLOOP;
};
EdgEdgI: IntersectionProc = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point];
e1: Edge ← NARROW[c1];
e2: Edge ← NARROW[c2];
point: Point;
noHit: BOOL;
[point, noHit] ← GGLines.EdgeMeetsEdge[e1, e2];
IF NOT noHit THEN iPoints ← LIST[point] ELSE iPoints ← NIL;
};
ArcLinI: IntersectionProc = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point];
arc: Arc ← NARROW[c1];
line: Line ← NARROW[c2];
points: ARRAY [1..2] OF Point;
hitCount: [0..2];
[points, hitCount] ← GGCircles.ArcMeetsLine[arc, line];
iPoints ← NIL;
FOR i: NAT IN [1..hitCount] DO
iPoints ← CONS[points[i], iPoints];
ENDLOOP;
};
ArcCirI: IntersectionProc = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point];
arc: Arc ← NARROW[c1];
circle: Circle ← NARROW[c2];
points: ARRAY [1..2] OF Point;
hitCount: [0..2];
[points, hitCount] ← GGCircles.CircleMeetsArc[circle, arc];
iPoints ← NIL;
FOR i: NAT IN [1..hitCount] DO
iPoints ← CONS[points[i], iPoints];
ENDLOOP;
};
ArcEdgI: IntersectionProc = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point];
arc: Arc ← NARROW[c1];
edge: Edge ← NARROW[c2];
points: ARRAY [1..2] OF Point;
hitCount: [0..2];
[points, hitCount] ← GGCircles.ArcMeetsEdge[arc, edge];
iPoints ← NIL;
FOR i: NAT IN [1..hitCount] DO
iPoints ← CONS[points[i], iPoints];
ENDLOOP;
};
ArcArcI: IntersectionProc = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point];
arc1: Arc ← NARROW[c1];
arc2: Arc ← NARROW[c2];
points: ARRAY [1..2] OF Point;
hitCount: [0..2];
[points, hitCount] ← GGCircles.ArcMeetsArc[arc1, arc2];
iPoints ← NIL;
FOR i: NAT IN [1..hitCount] DO
iPoints ← CONS[points[i], iPoints];
ENDLOOP;
};
SlcLinI: IntersectionProc = {
sliceD: SliceDescriptor ← NARROW[c1];
line: Line ← NARROW[c2];
[iPoints, ----] ← sliceD.slice.class.lineIntersection[sliceD, line];
};
SlcCirI: IntersectionProc = {
sliceD: SliceDescriptor ← NARROW[c1];
circle: Circle ← NARROW[c2];
[iPoints, ----] ← sliceD.slice.class.circleIntersection[sliceD, circle];
};
SeqLineI: IntersectionProc = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point];
outlineD: OutlineDescriptor ← NARROW[c1];
line: Line ← NARROW[c2];
[iPoints, ----] ← outlineD.slice.class.lineIntersection[outlineD, line];
};
SeqCircleI: IntersectionProc = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point];
outlineD: OutlineDescriptor ← NARROW[c1];
circle: Circle ← NARROW[c2];
[iPoints, ----] ← outlineD.slice.class.circleIntersection[outlineD, circle];
};
SeqSeqI: IntersectionProc = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point];
od1: OutlineDescriptor ← NARROW[c1];
od2: OutlineDescriptor ← NARROW[c2];
simpleCurve1, simpleCurve2: REF ANY;
simpleCurve1 ← od1.slice.class.hitDataAsSimpleCurve[od1.slice, hitData1];
simpleCurve2 ← od2.slice.class.hitDataAsSimpleCurve[od2.slice, hitData2];
iPoints ← NIL;
};
Utilities
MaxFeatures: NAT = 20;
BestCurvesFromPool: PROC [gargoyleData: GargoyleData] RETURNS [h: BestCurves] = {
h ← NARROW[gargoyleData.multiGravityPool, MultiGravityPool].bestcurves;
h.size ← 0;
h.max ← 0;
h.min ← GGUtility.plusInfinity;
h.overflow ← FALSE;
FOR i: NAT IN [0..MaxFeatures-1] DO
h[i].dist ← GGUtility.plusInfinity;
h[i].featureData ← NIL;
ENDLOOP;
};
BestPointsFromPool: PROC [gargoyleData: GargoyleData] RETURNS [h: BestPoints] = {
h ← NARROW[gargoyleData.multiGravityPool, MultiGravityPool].bestpoints;
h.size ← 0;
h.max ← 0;
h.min ← GGUtility.plusInfinity;
h.overflow ← FALSE;
FOR i: NAT IN [0..MaxFeatures-1] DO
h[i].dist ← GGUtility.plusInfinity;
h[i].featureData ← NIL;
ENDLOOP;
};
NewMultiGravityPool: PUBLIC PROC [] RETURNS [REF]= { -- reuseable storage for BestPointAndCurve proc to avoid NEWs
pool: MultiGravityPool ← NEW[MultiGravityPoolObj];
pool.distances ← NEW[NearDistancesObj[MaxFeatures]];
pool.features ← NEW[NearFeaturesObj[MaxFeatures]];
pool.bestpoints ← NEW[BestPointsObj[MaxFeatures]];
pool.bestcurves ← NEW[BestCurvesObj[MaxFeatures]];
FOR i: NAT IN [0..MaxFeatures) DO
pool.bestpoints[i] ← NEW[GoodPointObj];
pool.bestcurves[i] ← NEW[GoodCurveObj];
ENDLOOP;
RETURN[pool];
};
InitStats: PROC [] = {
interval: GGStatistics.Interval;
interval ← GGStatistics.CreateInterval[$MultiMap];
GGStatistics.AddInterval[interval, GGStatistics.GlobalTable[]];
};
InitStats[];
END.