GGGravityImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Last edited by Bier on April 7, 1987 0:41:17 am PDT
Contents: Procedures which take a test point and map it to a point on a nearby set of objects.
Pier, May 13, 1987 2:35:53 pm PDT
DIRECTORY
AtomButtons, BiScrollers, CodeTimer, FunctionCache, GGBasicTypes, GGCaret, GGCircleCache, GGCircles, GGGravity, GGInterfaceTypes, GGModelTypes, GGSegmentTypes, GGSequence, GGShapes, GGTraj, Imager, ImagerBackdoor, ImagerTransformation, Lines2d, Process, Real, RealFns, Rope, Vectors2d;
GGGravityImpl: CEDAR PROGRAM
IMPORTS AtomButtons, BiScrollers, CodeTimer, FunctionCache, GGCaret, GGCircleCache, GGCircles, GGSequence, GGShapes, GGTraj, Imager, ImagerBackdoor, Lines2d, Process, RealFns, Vectors2d
EXPORTS GGGravity = BEGIN
AlignmentCircle: TYPE = REF AlignmentCircleObj;
AlignmentCircleObj: TYPE = GGInterfaceTypes.AlignmentCircleObj;
AlignmentLine: TYPE = REF AlignmentLineObj;
AlignmentLineObj: TYPE = GGInterfaceTypes.AlignmentLineObj;
AlignmentPoint: TYPE = REF AlignmentPointObj;
AlignmentPointObj: TYPE = GGInterfaceTypes.AlignmentPointObj;
Angle: TYPE = GGBasicTypes.Angle;
BoundBox: TYPE = GGModelTypes.BoundBox;
Caret: TYPE = GGInterfaceTypes.Caret;
Circle: TYPE = GGBasicTypes.Circle;
Edge: TYPE = GGBasicTypes.Edge;
FeatureData: TYPE = REF FeatureDataObj;
FeatureDataObj: TYPE = GGModelTypes.FeatureDataObj;
GGData: TYPE = GGInterfaceTypes.GGData;
JointGenerator: TYPE = GGModelTypes.JointGenerator;
Line: TYPE = GGBasicTypes.Line;
AlignBag: TYPE = REF AlignBagObj;
AlignBagObj: TYPE = GGInterfaceTypes.AlignBagObj;
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 = REF SliceDescriptorObj;
SliceDescriptorObj: TYPE = GGModelTypes.SliceDescriptorObj;
SliceParts: TYPE = GGModelTypes.SliceParts;
Traj: TYPE = GGModelTypes.Traj;
TriggerBag: TYPE = GGInterfaceTypes.TriggerBag;
Vector: TYPE = GGBasicTypes.Vector;
Problem: PUBLIC SIGNAL [msg: Rope.ROPE] = CODE;
Magic Numbers for Debugging
maxDistance: REAL = 99999.0;
noPoint: Point = [0.0, 0.0];
noJoint: NAT = 9999;
noCP: NAT = 8888;
noSeg: NAT = 7777;
Building the Trigger Bag
FeatureFromOutline: PUBLIC PROC [outline: Outline, parts: SliceParts ← NIL] RETURNS [feature: FeatureData] = {
sliceParts: SliceParts ← IF parts=NIL THEN outline.class.newParts[outline, NIL, slice].parts ELSE parts;
outlineD: OutlineDescriptor ← NEW[OutlineDescriptorObj ← [slice: outline, parts: sliceParts]];
feature ← NEW[FeatureDataObj];
feature.type ← outline;
feature.shape ← outlineD;
};
FeatureFromSlice: PUBLIC PROC [slice: Slice, parts: SliceParts ← NIL] RETURNS [feature: FeatureData] = {
sliceParts: SliceParts ← IF parts=NIL THEN slice.class.newParts[slice, NIL, slice].parts ELSE parts; -- may get a descriptor of the whole slice
sliceD: SliceDescriptor ← NEW[SliceDescriptorObj ← [slice: slice, parts: sliceParts]];
feature ← NEW[FeatureDataObj];
feature.type ← slice;
feature.shape ← sliceD;
};
FeatureFromAnchor: PUBLIC PROC [anchor: Caret] RETURNS [feature: FeatureData] = {
feature ← NEW[FeatureDataObj];
feature.type ← anchor; -- that is, anchor => the member of the enumerated type
feature.shape ← anchor; -- that is, anchor => the parameter
};
Building the Object Bag
JointAddSlopeLine: PUBLIC PROC [degrees: REAL, direction: Vector, point: Point, objectBag: AlignBag] RETURNS [feature: FeatureData] = {
The angle (degrees) and direction vector are the global information. lineList is used to avoid redundant lines.
For now, each slope line only remembers one of the joints which it passes thru.
line: Line;
coincident: FeatureData ← LineThru[point, degrees, objectBag.slopeLines];
IF coincident # NIL THEN {
alignmentLine: AlignmentLine ← NARROW[coincident.shape];
alignmentLine.triggerPoints ← CONS[point, alignmentLine.triggerPoints];
feature ← NIL;
}
ELSE {
alignmentLine: AlignmentLine;
line ← Lines2d.LineFromPointAndVector[point, direction];
alignmentLine ← NEW[AlignmentLineObj ← [line: line, degrees: degrees, triggerPoints: CONS[point, NIL]]];
feature ← NEW[FeatureDataObj];
feature.type ← slopeLine;
feature.shape ← alignmentLine;
AddFeature[feature, objectBag];
};
};
JointAddCircle: PUBLIC PROC [radius: REAL, point: Point, objectBag: AlignBag] RETURNS [feature: FeatureData] = {
radius is global. [point, jointNum, traj] describes the joint.
Each circle remembers all of the joints at its center.
circle: Circle;
coincident: FeatureData;
coincident ← SameCircle[point, radius, objectBag.radiiCircles];
IF coincident # NIL THEN {
alignmentCircle: AlignmentCircle ← NARROW[coincident.shape];
alignmentCircle.triggerPoints ← CONS[point, alignmentCircle.triggerPoints];
feature ← NIL;
}
ELSE {
alignmentCircle: AlignmentCircle;
circle ← GGCircles.CircleFromPointAndRadius[point, radius];
alignmentCircle ← NEW[AlignmentCircleObj ← [circle: circle, triggerPoints: CONS[point, NIL]]];
feature ← NEW[FeatureDataObj];
feature.type ← radiiCircle;
feature.shape ← alignmentCircle;
AddFeature[feature, objectBag];
};
};
SameCircle: PRIVATE PROC [point: Point, radius: REAL, list: LIST OF FeatureData] RETURNS [coincident: FeatureData] = {
circle: Circle;
FOR l: LIST OF FeatureData ← list, l.rest UNTIL l = NIL DO
circle ← NARROW[l.first.shape, AlignmentCircle].circle;
IF circle.origin = point AND circle.radius = radius THEN RETURN[l.first];
IF RealFns.AlmostEqual[circle.origin.x, point.x, -10] AND RealFns.AlmostEqual[circle.origin.y, point.y, -10] AND RealFns.AlmostEqual[circle.radius, radius, -10] THEN RETURN[l.first];
ENDLOOP;
RETURN[NIL];
};
LineThru: PRIVATE PROC [point: Point, degrees: REAL, list: LIST OF FeatureData] RETURNS [coincident: FeatureData] = {
epsilon: REAL = 1.0e-5;
line: Line;
FOR l: LIST OF FeatureData ← list, l.rest UNTIL l = NIL DO
line ← NARROW[l.first.shape, AlignmentLine].line;
IF NARROW[l.first.shape, AlignmentLine].degrees = degrees AND
Lines2d.LineDistance[point, line] < epsilon THEN RETURN[l.first];
ENDLOOP;
RETURN[NIL];
};
SegmentAddTwoAngleLines: PUBLIC PROC [degrees: REAL, segNum: NAT, lo, hi: Point, objectBag: AlignBag] RETURNS [line1, line2: FeatureData] = {
loLine: Line ← Lines2d.LineFromPointAndAngle[pt: lo, degrees: Vectors2d.AngleFromVector[[x: hi.x-lo.x, y: hi.y-lo.y]]+degrees];
hiLine: Line ← Lines2d.LineFromPointAndAngle[pt: hi, degrees: Vectors2d.AngleFromVector[[x: lo.x-hi.x, y: lo.y-hi.y]]+degrees];
line1 ← NEW[FeatureDataObj];
line1.type ← angleLine;
line1.shape ← NEW[AlignmentLineObj ← [line: loLine, degrees: degrees, triggerPoints: NIL]];
line1.hitPart ← NEW[SequencePartObj ← [segNum, -1, -1]];
AddFeature[line1, objectBag];
line2 ← NEW[FeatureDataObj];
line2.type ← angleLine;
line2.shape ← NEW[AlignmentLineObj ← [line: hiLine, degrees: degrees, triggerPoints: NIL]];
line2.hitPart ← NEW[SequencePartObj ← [segNum, -1, -1]];
AddFeature[line2, objectBag];
};
SegmentAddDistanceLines: PUBLIC PROC [distance: REAL, segNum: NAT, lo, hi: Point, objectBag: AlignBag] RETURNS [line1, line2: FeatureData] = {
No global information is needed. [segNum, traj] describes the segment.
line, leftLine, rightLine: Line;
line ← Lines2d.LineFromPoints[lo, hi];
leftLine ← Lines2d.LineLeftOfLine[line, distance];
line1 ← NEW[FeatureDataObj];
line1.type ← distanceLine;
line1.shape ← leftLine;
line1.hitPart ← NEW[SequencePartObj ← [segNum, -1, -1]];
AddFeature[line1, objectBag];
IF ABS[distance] > 0.0 THEN {
rightLine ← Lines2d.LineRightOfLine[line, distance];
line2 ← NEW[FeatureDataObj];
line2.type ← distanceLine;
line2.shape ← rightLine;
line2.hitPart ← NEW[SequencePartObj ← [segNum, -1, -1]];
AddFeature[line2, objectBag];
}
ELSE line2 ← NIL;
};
SegmentAddMidpoint: PUBLIC PROC [segNum: NAT, lo, hi: Point, objectBag: AlignBag] RETURNS [feature: FeatureData] = {
No global information is needed. [segNum, traj] describes the segment.
midpoint: Point;
alignmentPoint: AlignmentPoint;
midpoint ← Vectors2d.Scale[Vectors2d.Add[lo, hi], 0.5];
alignmentPoint ← NEW[AlignmentPointObj ← [point: midpoint, tangent: FALSE]];
feature ← NEW[FeatureDataObj];
feature.type ← midpoint;
feature.shape ← alignmentPoint;
feature.hitPart ← NEW[GGInterfaceTypes.SequencePartObj ← [segNum, -1, -1]];
AddFeature[feature, objectBag];
};
AddFeature: PRIVATE PROC [featureData: FeatureData, objectBag: AlignBag] = {
Process.CheckForAbort[];
SELECT featureData.type FROM
midpoint => objectBag.midpoints ← CONS[featureData, objectBag.midpoints];
distanceLine => objectBag.distanceLines ← CONS[featureData, objectBag.distanceLines];
slopeLine => objectBag.slopeLines ← CONS[featureData, objectBag.slopeLines];
angleLine => objectBag.angleLines ← CONS[featureData, objectBag.angleLines];
radiiCircle => objectBag.radiiCircles ← CONS[featureData, objectBag.radiiCircles];
intersectionPoint => objectBag.intersectionPoints ← CONS[featureData, objectBag.intersectionPoints];
anchor => objectBag.anchor ← featureData;
ENDCASE => SIGNAL Problem[msg: "Unimplemented feature type"];
};
AddLineIntersections: PROC [featureData: FeatureData, objectBag: AlignBag] = {
iPoint: Point;
parallel: BOOL;
points: ARRAY[1..2] OF Point;
hitCount: NAT;
line: Line;
WITH featureData.shape SELECT FROM
l: Line => line ← l;
aL: AlignmentLine => line ← aL.line;
ENDCASE => ERROR Problem[msg: "Broken Invariant"];
FOR lineList: LIST OF FeatureData ← objectBag.slopeLines, lineList.rest UNTIL lineList = NIL DO
[iPoint, parallel] ← Lines2d.LineMeetsLine[NARROW[lineList.first.shape, AlignmentLine].line, line];
IF NOT parallel THEN {
AddIntersectionPointFeature[iPoint, featureData, lineList.first, objectBag];
};
ENDLOOP;
FOR lineList: LIST OF FeatureData ← objectBag.angleLines, lineList.rest UNTIL lineList = NIL DO
[iPoint, parallel] ← Lines2d.LineMeetsLine[NARROW[lineList.first.shape, AlignmentLine].line, line];
IF NOT parallel THEN {
AddIntersectionPointFeature[iPoint, featureData, lineList.first, objectBag];
};
ENDLOOP;
FOR dlineList: LIST OF FeatureData ← objectBag.distanceLines, dlineList.rest UNTIL dlineList = NIL DO
[iPoint, parallel] ← Lines2d.LineMeetsLine[NARROW[dlineList.first.shape], line];
IF NOT parallel THEN {
AddIntersectionPointFeature[iPoint, featureData, dlineList.first, objectBag];
};
ENDLOOP;
FOR circleList: LIST OF FeatureData ← objectBag.radiiCircles, circleList.rest UNTIL circleList = NIL DO
[points, hitCount] ← GGCircles.LineMeetsCircle[line, NARROW[circleList.first.shape, AlignmentCircle].circle];
FOR i: NAT IN [1..hitCount] DO
AddIntersectionPointFeature[points[i], featureData, circleList.first, objectBag];
ENDLOOP;
ENDLOOP;
};
AddCircleIntersections: PROC [featureData: FeatureData, objectBag: AlignBag] = {
points: ARRAY[1..2] OF Point;
hitCount: NAT;
circle: Circle ← NARROW[featureData.shape, AlignmentCircle].circle;
FOR lineList: LIST OF FeatureData ← objectBag.slopeLines, lineList.rest UNTIL lineList = NIL DO
[points, hitCount] ← GGCircles.LineMeetsCircle[NARROW[lineList.first.shape, AlignmentLine].line, circle];
FOR i: NAT IN [1..hitCount] DO
AddIntersectionPointFeature[points[i], lineList.first, featureData, objectBag];
ENDLOOP;
ENDLOOP;
FOR lineList: LIST OF FeatureData ← objectBag.angleLines, lineList.rest UNTIL lineList = NIL DO
[points, hitCount] ← GGCircles.LineMeetsCircle[NARROW[lineList.first.shape, AlignmentLine].line, circle];
FOR i: NAT IN [1..hitCount] DO
AddIntersectionPointFeature[points[i], lineList.first, featureData, objectBag];
ENDLOOP;
ENDLOOP;
FOR dlineList: LIST OF FeatureData ← objectBag.distanceLines, dlineList.rest UNTIL dlineList = NIL DO
[points, hitCount] ← GGCircles.LineMeetsCircle[NARROW[dlineList.first.shape], circle];
FOR i: NAT IN [1..hitCount] DO
AddIntersectionPointFeature[points[i], dlineList.first, featureData, objectBag];
ENDLOOP;
ENDLOOP;
FOR circleList: LIST OF FeatureData ← objectBag.radiiCircles, circleList.rest UNTIL circleList = NIL DO
[points, hitCount] ← GGCircles.CircleMeetsCircle[NARROW[circleList.first.shape, AlignmentCircle].circle, circle];
FOR i: NAT IN [1..hitCount] DO
AddIntersectionPointFeature[points[i], circleList.first, featureData, objectBag];
ENDLOOP;
ENDLOOP;
};
AddIntersectionPointFeature: PRIVATE PROC [point: Point, feature1, feature2: FeatureData, objectBag: AlignBag] = {
featureData: FeatureData;
alignmentPoint: AlignmentPoint;
featureData ← NEW[FeatureDataObj];
alignmentPoint ← NEW[AlignmentPointObj ← [point: point, curve1: feature1, curve2: feature2]];
featureData.type ← intersectionPoint;
featureData.shape ← alignmentPoint;
AddFeature[featureData, objectBag];
};
Drawing Alignment Objects
THE FOLLOWING STIPPLEs ARE VERY PRECISELY DETERMINED. DO NOT MESS WITH THEM !!
alignmentColor: Imager.Color ← ImagerBackdoor.MakeStipple[145065B];
checkerColor: Imager.Color ← ImagerBackdoor.MakeStipple[122645B];
alignmentColor: Imager.Color ← Imager.black; -- doing this buys less than 10% in performance
checkerColor: Imager.Color ← Imager.black;
useCache: BOOLTRUE;
DrawFeatureList: PUBLIC PROC [dc: Imager.Context, alignObjects: LIST OF FeatureData, ggData: GGData] = {
DrawLineAux: PROC [line: Line] = { -- uses FunctionCache to avoid duplication
LineCompare: PROC [argument: FunctionCache.Domain] RETURNS [good: BOOL] = {
thisLine: Line ← NARROW[argument];
RETURN[thisLine.d = line.d AND thisLine.theta = line.theta];
};
ok: BOOL;
[----, ok] ← FunctionCache.Lookup[ggData.refresh.lineCache, LineCompare];
IF ok THEN RETURN
ELSE {
FunctionCache.Insert[ggData.refresh.lineCache, line, NIL, 2];
};
IF ABS[line.theta] < 1.0 OR ABS[line.theta - 90.0] < 1.0 THEN {
Imager.SetColor[dc, checkerColor];
GGShapes.DrawLine[dc, line, rect, 0.0]; -- 0 width lines go fast
Imager.SetColor[dc, alignmentColor];
}
ELSE GGShapes.DrawLine[dc, line, rect, 0.0]; -- 0 width lines go fast
};
DrawCircleAux: PROC [circle: Circle] = { -- uses GGCircleCache
cachedCircle: GGCircleCache.CachedCircle;
IF (cachedCircle ← GGCircleCache.Lookup[ggData.hitTest.radiusCircleCache, circle.radius])#NIL THEN GGCircleCache.DrawCachedCircle[dc, circle.origin, cachedCircle] -- cache hit
ELSE { -- cache miss. Attempt a cache entry and retry
GGCircleCache.Insert[ggData.hitTest.radiusCircleCache, circle.radius];
IF (cachedCircle ← GGCircleCache.Lookup[ggData.hitTest.radiusCircleCache, circle.radius])#NIL THEN GGCircleCache.DrawCachedCircle[dc, circle.origin, cachedCircle]
ELSE GGShapes.DrawCircle[dc, circle];
};
};
rect: Imager.Rectangle ← BiScrollers.ViewportBox[ggData.biScroller];
Imager.SetStrokeWidth[dc, 1.0];
Imager.SetColor[dc, alignmentColor];
FOR list: LIST OF FeatureData ← alignObjects, list.rest UNTIL list = NIL DO
WITH list.first.shape SELECT FROM
slopeLine: AlignmentLine => DrawLineAux[slopeLine.line];
angleLine: AlignmentLine => DrawLineAux[angleLine.line];
circle: AlignmentCircle => IF useCache THEN DrawCircleAux[circle.circle] ELSE GGShapes.DrawCircle[dc, circle.circle];
distanceLine: GGBasicTypes.Line => GGShapes.DrawLine[dc, distanceLine, rect];
ENDCASE => ERROR;
ENDLOOP;
};
DrawAlignBagRegardless: PUBLIC PROC [dc: Imager.Context, objectBag: AlignBag, ggData: GGData] = {
Draws all objects in the object bag regardless of how they have been marked.
IF objectBag = NIL THEN RETURN;
DrawFeatureList[dc, objectBag.slopeLines, ggData];
DrawFeatureList[dc, objectBag.angleLines, ggData];
DrawFeatureList[dc, objectBag.radiiCircles, ggData];
DrawFeatureList[dc, objectBag.distanceLines, ggData];
};
Hit Testing
GoodCurve: TYPE = REF GoodCurveObj;
GoodCurveObj: TYPE = RECORD [
dist: REAL ← maxDistance, -- the distance from point to testPoint
segNum: NAT ← noSeg, -- the best segment of this curve (if it is a trajectory)
point: Point, -- the best point on this curve
featureData: FeatureData ← NIL, -- this curve
hitData: REF ANY
];
GoodPointType: TYPE = {joint, controlPoint, slice, intersectionPoint, midpoint, none};
GoodPoint: TYPE = REF GoodPointObj;
GoodPointObj: TYPE = RECORD [
type: GoodPointType ← none,
dist: REAL ← maxDistance,
point: Point ← noPoint,
joint: NAT ← noJoint, -- the joint of the trajectory mentioned in FeatureData (if this is a joint)
controlPoint: NAT ← noCP, -- the control point number (if this is a control point)
segNum: NAT ← noSeg, -- the segment to which the control point belongs
featureData: FeatureData ← NIL, -- this point
hitData: REF ANY
];
UniMap: PUBLIC PROC [testPoint: Point, criticalR: REAL, currentObjects: AlignBag, activeObjects: TriggerBag, ggData: GGData, intersections: BOOL] RETURNS [resultPoint: Point, feature: FeatureData, hitData: REF ANY] = {
ENABLE UNWIND => ggData.gravityPool ← NewGravityPool[]; -- perhaps ABORT happened while pool was in use
Calls one of the procedures below, depending on the current gravity type.
CodeTimer.StartInt[$UniMap, $Gargoyle];
SELECT AtomButtons.GetButtonState[ggData.hitTest.gravButton] FROM
on => SELECT ggData.hitTest.gravityType FROM
strictDistance =>
[resultPoint, feature, hitData] ← StrictDistance[testPoint, criticalR, currentObjects, activeObjects, ggData, intersections];
innerCircle =>
[resultPoint, feature, hitData] ← InnerCircle[testPoint, criticalR, ggData.hitTest.innerR, currentObjects, activeObjects, ggData, intersections];
ENDCASE => ERROR;
off => {
resultPoint ← testPoint;
feature ← NIL;
};
ENDCASE => ERROR;
CodeTimer.StopInt[$UniMap, $Gargoyle];
};
Map: PUBLIC PROC [testPoint: Point, criticalR: REAL, currentObjects: AlignBag, activeObjects: TriggerBag, ggData: GGData, intersections: BOOL] RETURNS [resultPoint: Point, feature: FeatureData] = {
ENABLE UNWIND => ggData.gravityPool ← NewGravityPool[]; -- in case an ABORT happened while pool was in use
[resultPoint, feature] ← GGMultiGravity.Map[testPoint, criticalR, currentObjects, activeObjects, ggData, intersections];
};
StrictDistance: PROC [testPoint: Point, criticalR: REAL, currentObjects: AlignBag, activeObjects: TriggerBag, ggData: GGData, intersections: BOOL] RETURNS [resultPoint: Point, feature: FeatureData, hitData: REF ANY] = {
Here we find both the nearest point and the nearest line. The winning object is simply the closest.
thisCurve, bestCurve: GoodCurve;
thisPoint, bestPoint: GoodPoint;
IF EmptyBag[currentObjects] AND EmptyTriggers[activeObjects] --AND NOT (intersections AND GGCaret.Exists[ggData.anchor]) -- THEN {
resultPoint ← testPoint;
feature ← NIL;
RETURN;
};
[thisPoint, bestPoint, thisCurve, bestCurve] ← BestPointAndCurve[currentObjects, activeObjects, testPoint, criticalR, ggData.anchor, intersections, ggData];
Pick the closer of the curve and the point.
IF bestPoint.type = none AND bestCurve.dist = maxDistance THEN {
feature ← NIL;
resultPoint ← testPoint;
ReturnPointsToPool[thisPoint, bestPoint, ggData];
ReturnCurvesToPool[thisCurve, bestCurve, ggData];
RETURN};
IF (NOT bestPoint.type = none) AND bestPoint.dist < criticalR AND bestPoint.dist <= bestCurve.dist THEN { -- use the best point
resultPoint ← bestPoint.point;
feature ← bestPoint.featureData;
hitData ← bestPoint.hitData;
}
ELSE IF bestCurve.dist < criticalR THEN {
resultPoint ← bestCurve.point;
feature ← bestCurve.featureData;
hitData ← bestCurve.hitData;
}
ELSE {
feature ← NIL;
resultPoint ← testPoint;
};
ReturnPointsToPool[thisPoint, bestPoint, ggData];
ReturnCurvesToPool[thisCurve, bestCurve, ggData];
}; -- StrictDistance
InnerCircle: PROC [testPoint: Point, criticalR: REAL, innerR: REAL, currentObjects: AlignBag, activeObjects: TriggerBag, ggData: GGData, intersections: BOOL] RETURNS [resultPoint: Point, feature: FeatureData, hitData: REF ANY] = {
Here we find both the nearest point and the nearest line. Within innerR, points get preference.
thisCurve, bestCurve: GoodCurve;
thisPoint, bestPoint: GoodPoint;
IF EmptyBag[currentObjects] AND EmptyTriggers[activeObjects] --AND NOT (intersections AND GGCaret.Exists[ggData.anchor])-- THEN {
resultPoint ← testPoint;
feature ← NIL;
RETURN;
};
[thisPoint, bestPoint, thisCurve, bestCurve] ← BestPointAndCurve[currentObjects, activeObjects, testPoint, criticalR, ggData.anchor, intersections, ggData];
Look at the closest point first. If it is within innerR, use it. Otherwise, pick the closer of the curve and the point.
IF bestPoint.type = none AND bestCurve.dist = maxDistance THEN {
feature ← NIL;
resultPoint ← testPoint;
ReturnPointsToPool[thisPoint, bestPoint, ggData];
ReturnCurvesToPool[thisCurve, bestCurve, ggData];
RETURN};
IF (NOT bestPoint.type = none) AND (bestPoint.dist < innerR OR (bestPoint.dist < criticalR AND bestPoint.dist <= bestCurve.dist)) THEN { -- use the best point
resultPoint ← bestPoint.point;
feature ← bestPoint.featureData;
hitData ← bestPoint.hitData;
}
ELSE IF bestCurve.dist < criticalR THEN {
resultPoint ← bestCurve.point;
feature ← bestCurve.featureData;
hitData ← bestCurve.hitData;
}
ELSE {
feature ← NIL;
resultPoint ← testPoint;
};
ReturnPointsToPool[thisPoint, bestPoint, ggData];
ReturnCurvesToPool[thisCurve, bestCurve, ggData];
}; -- InnerCircle
Auxiliary Hit Testing Routines
BestPointAndCurve: PROC [currentObjects: AlignBag, sceneObjects: TriggerBag, testPoint: Point, tolerance: REAL, anchor: Caret, intersections: BOOL, ggData: GGData] RETURNS [thisPoint, bestPoint: GoodPoint, thisCurve, bestCurve: GoodCurve] = {
The storage borrowed from the Pool is returned to the caller. The caller has the responsibility to return that storage to the Pool when it is no longer needed.
epsilon: REAL = 1.0e-3;
line: Line;
circle: Circle;
sliceD: SliceDescriptor;
outlineD: OutlineDescriptor;
success: BOOLFALSE;
featureData: FeatureData;
[thisPoint, bestPoint] ← GetPointsFromPool[ggData];
[thisCurve, bestCurve] ← GetCurvesFromPool[ggData];
bestCurve^ ← [maxDistance, noSeg, noPoint, NIL]; -- magic values for debugging
bestPoint^ ← [none, maxDistance, noPoint, noJoint, noCP, noSeg, NIL]; -- magic values for debugging
Alignment Lines.
FOR slopeLines: LIST OF FeatureData ← currentObjects.slopeLines, slopeLines.rest UNTIL slopeLines = NIL DO
featureData ← slopeLines.first;
line ← NARROW[featureData.shape, AlignmentLine].line;
thisCurve.dist ← Lines2d.LineDistance[testPoint, line];
success ← thisCurve.dist < tolerance;
IF success AND thisCurve.dist < bestCurve.dist THEN {
thisCurve.point ← Lines2d.DropPerpendicular[testPoint, line];
thisCurve.featureData ← featureData;
thisCurve.hitData ← NIL;
UpdateBestCurve[thisCurve, bestCurve];
};
ENDLOOP;
FOR angleLines: LIST OF FeatureData ← currentObjects.angleLines, angleLines.rest UNTIL angleLines = NIL DO
featureData ← angleLines.first;
line ← NARROW[featureData.shape, AlignmentLine].line;
thisCurve.dist ← Lines2d.LineDistance[testPoint, line];
success ← thisCurve.dist < tolerance;
IF success AND thisCurve.dist < bestCurve.dist THEN {
thisCurve.point ← Lines2d.DropPerpendicular[testPoint, line];
thisCurve.featureData ← featureData;
thisCurve.hitData ← NIL;
UpdateBestCurve[thisCurve, bestCurve];
};
ENDLOOP;
FOR dLines: LIST OF FeatureData ← currentObjects.distanceLines, dLines.rest UNTIL dLines = NIL DO
featureData ← dLines.first;
thisCurve.dist ← Lines2d.LineDistance[testPoint, (line ← NARROW[featureData.shape])];
success ← thisCurve.dist < tolerance;
IF success AND thisCurve.dist < bestCurve.dist THEN {
thisCurve.point ← Lines2d.DropPerpendicular[testPoint, line];
thisCurve.featureData ← featureData;
thisCurve.hitData ← NIL;
UpdateBestCurve[thisCurve, bestCurve];
};
ENDLOOP;
FOR iPoints: LIST OF FeatureData ← currentObjects.intersectionPoints, iPoints.rest UNTIL iPoints = NIL DO
featureData ← iPoints.first;
thisPoint.type ← intersectionPoint;
thisPoint.dist ← Vectors2d.Distance[NARROW[featureData.shape, AlignmentPoint].point, testPoint];
success ← thisPoint.dist < tolerance;
IF success AND thisPoint.dist < bestPoint.dist THEN {
thisPoint.point ← NARROW[featureData.shape, AlignmentPoint].point;
thisPoint.featureData ← featureData;
thisPoint.hitData ← NIL;
UpdateBestPoint[thisPoint, bestPoint];
};
ENDLOOP;
FOR midpoints: LIST OF FeatureData ← currentObjects.midpoints, midpoints.rest UNTIL midpoints = NIL DO
featureData ← midpoints.first;
thisPoint.type ← midpoint;
thisPoint.dist ← Vectors2d.Distance[NARROW[featureData.shape, AlignmentPoint].point, testPoint];
success ← thisPoint.dist < tolerance;
IF success AND thisPoint.dist < bestPoint.dist THEN {
thisPoint.point ← NARROW[featureData.shape, AlignmentPoint].point;
thisPoint.featureData ← featureData;
thisPoint.hitData ← NIL;
UpdateBestPoint[thisPoint, bestPoint];
};
ENDLOOP;
FOR circles: LIST OF FeatureData ← currentObjects.radiiCircles, circles.rest UNTIL circles = NIL DO
featureData ← circles.first;
circle ← NARROW[featureData.shape, AlignmentCircle].circle;
thisCurve.dist ← GGCircles.CircleDistance[testPoint, circle];
success ← thisCurve.dist < tolerance;
IF success AND thisCurve.dist < bestCurve.dist THEN {
thisCurve.point ← GGCircles.PointProjectedOntoCircle[testPoint, circle];
thisCurve.featureData ← featureData;
thisCurve.hitData ← NIL;
UpdateBestCurve[thisCurve, bestCurve];
};
ENDLOOP;
Active Scene Objects.
FOR slices: LIST OF FeatureData ← sceneObjects.slices, slices.rest UNTIL slices = NIL DO
featureData ← slices.first;
sliceD ← NARROW[featureData.shape, SliceDescriptor];
[thisCurve.point, thisCurve.dist, thisCurve.hitData, success] ← sliceD.slice.class.closestSegment[sliceD, testPoint, tolerance];
IF success AND (thisCurve.dist - epsilon <= bestCurve.dist) THEN { -- so segments are preferred to slopelines
bestCurve.dist ← thisCurve.dist;
bestCurve.segNum ← thisCurve.segNum;
bestCurve.point ← thisCurve.point;
bestCurve.hitData ← thisCurve.hitData;
bestCurve.featureData ← featureData;
};
[thisPoint.point, thisPoint.dist, thisPoint.hitData, success] ← sliceD.slice.class.closestPoint[sliceD, testPoint, tolerance];
IF success AND (thisPoint.dist - epsilon <= bestPoint.dist) THEN {
bestPoint.type ← slice;
bestPoint.dist ← thisPoint.dist;
bestPoint.point ← thisPoint.point;
bestPoint.hitData ← thisPoint.hitData;
bestPoint.joint ← 999;
bestPoint.featureData ← featureData;
};
ENDLOOP;
FOR outlines: LIST OF FeatureData ← sceneObjects.outlines, outlines.rest UNTIL outlines = NIL DO
featureData ← outlines.first;
outlineD ← NARROW[featureData.shape, OutlineDescriptor];
[thisCurve.point, thisCurve.dist, thisCurve.hitData, success] ← outlineD.slice.class.closestSegment[outlineD, testPoint, tolerance];
IF success AND (thisCurve.dist - epsilon <= bestCurve.dist) THEN { -- so segments are preferred to slopelines
bestCurve.dist ← thisCurve.dist;
bestCurve.segNum ← thisCurve.segNum;
bestCurve.point ← thisCurve.point;
bestCurve.hitData ← thisCurve.hitData;
bestCurve.featureData ← featureData;
};
[thisPoint.point, thisPoint.dist, thisPoint.hitData, success] ← outlineD.slice.class.closestPoint[outlineD, testPoint, tolerance];
IF success AND (thisPoint.dist - epsilon <= bestPoint.dist) THEN {
bestPoint.type ← joint;
bestPoint.dist ← thisPoint.dist;
bestPoint.point ← thisPoint.point;
bestPoint.hitData ← thisPoint.hitData;
bestPoint.joint ← 999;
bestPoint.featureData ← featureData;
};
ENDLOOP;
Handle the anchor.
IF intersections THEN {
featureData ← currentObjects.anchor;
IF featureData # NIL THEN {
anchor: Caret ← NARROW[featureData.shape];
IF NOT GGCaret.Exists[anchor] THEN ERROR;
thisPoint.type ← intersectionPoint; -- REALLY CARETPOINT
thisPoint.point ← GGCaret.GetPoint[anchor];
thisPoint.dist ← Vectors2d.Distance[thisPoint.point, testPoint];
thisPoint.hitData ← NIL;
IF thisPoint.dist < tolerance AND thisPoint.dist < bestPoint.dist THEN {
thisPoint.featureData ← featureData;
UpdateBestPoint[thisPoint, bestPoint];
};
};
};
};
UpdateBestCurve: PROC [thisCurve, bestCurve: GoodCurve] = {
bestCurve.dist ← thisCurve.dist;
bestCurve.segNum ← noSeg; -- magic number for debugging
bestCurve.point ← thisCurve.point;
bestCurve.featureData ← thisCurve.featureData;
};
UpdateBestPoint: PROC [thisPoint, bestPoint: GoodPoint] = {
bestPoint.type ← thisPoint.type;
bestPoint.dist ← thisPoint.dist;
bestPoint.point ← thisPoint.point;
bestPoint.joint ← noSeg; -- magic number for debugging
bestPoint.featureData ← thisPoint.featureData;
};
ExtractResultFromCurve: PROC [curve: GoodCurve, feature: FeatureData] = {
SELECT feature.type FROM
outline => feature.hitPart ← curve.hitData;
slice => feature.hitPart ← curve.hitData;
slopeLine, angleLine, radiiCircle, distanceLine => {};
ENDCASE => SIGNAL Problem[msg: "Unimplemented type."];
};
ExtractResultFromPoint: PROC [goodPoint: GoodPoint, feature: FeatureData] = {
SELECT goodPoint.type FROM
joint, controlPoint => feature.hitPart ← goodPoint.hitData;
slice => feature.hitPart ← goodPoint.hitData;
intersectionPoint => feature.hitPart ← NIL;
midpoint => {
midPoint features contain a reasonable segNum in their hitPart
};
ENDCASE => SIGNAL Problem [msg: "Unimplemented result type."];
};
EmptyBag: PROC [objectBag: AlignBag] 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 AND
objectBag.anchor = NIL];
};
EmptyTriggers: PROC [triggerBag: TriggerBag] RETURNS [BOOL] = {
RETURN[
triggerBag.outlines = NIL AND
triggerBag.slices = NIL AND
triggerBag.intersectionPoints = NIL AND
triggerBag.anchor = NIL
];
};
Hit Testing For Different Kinds of Objects.
useBBox: BOOLTRUE;
PointIsInBox: PROC [test: Point, box: GGBasicTypes.BoundBoxObj] RETURNS [BOOL] = {
RETURN[ NOT (test.x < box.loX OR test.x > box.hiX OR test.y < box.loY OR test.y > box.hiY) ];
};
NearestSegment: PROC [testPoint: Point, seq: Sequence, tolerance: REAL] RETURNS [bestDist: REAL, bestSeg: NAT, bestPoint: Point, success: BOOL] = {
thisDist2, bestDist2: REAL;
thisPoint: Point;
segGen: SegmentGenerator;
thisSuccess: BOOL;
next: GGSequence.SegAndIndex;
bigBox: GGBasicTypes.BoundBoxObj;
success ← FALSE;
IF useBBox THEN {
bigBox ← [seq.boundBox.loX-tolerance, seq.boundBox.loY-tolerance, seq.boundBox.hiX+tolerance, seq.boundBox.hiY+tolerance, FALSE, FALSE];
IF NOT PointIsInBox[testPoint, bigBox] THEN RETURN; -- success=FALSE
};
segGen ← GGSequence.SegmentsInSequence[seq];
next ← GGSequence.NextSegmentAndIndex[segGen];
IF next.seg = NIL THEN { -- The sequence is a single joint
bestDist ← maxDistance; -- magic number for debugging
bestSeg ← noSeg; -- magic number meaning no segment
bestPoint ← [-1.0, -1.0];
RETURN;
};
[bestPoint, thisSuccess] ← next.seg.class.closestPoint[next.seg, testPoint, tolerance];
IF NOT thisSuccess THEN {
bestDist2 ← maxDistance;
bestSeg ← noSeg;
bestPoint ← [-1.0, -1.0];
}
ELSE {
bestDist2 ← Vectors2d.DistanceSquared[bestPoint, testPoint];
bestSeg ← next.index;
success ← TRUE;
};
FOR next ← GGSequence.NextSegmentAndIndex[segGen], GGSequence.NextSegmentAndIndex[segGen] UNTIL next.seg = NIL DO
[thisPoint, thisSuccess] ← next.seg.class.closestPoint[next.seg, testPoint, tolerance];
IF NOT thisSuccess THEN {
thisDist2 ← maxDistance;
thisPoint ← [-1.0, -1.0];
}
ELSE {
thisDist2 ← Vectors2d.DistanceSquared[thisPoint, testPoint];
success ← TRUE;
};
IF success AND thisDist2 < bestDist2 THEN {
bestDist2 ← thisDist2;
bestSeg ← next.index;
bestPoint ← thisPoint;
};
ENDLOOP;
bestDist ← RealFns.SqRt[bestDist2];
};
NearestJoint: PROC [testPoint: Point, seq: Sequence, tolerance: REAL] RETURNS [bestDist: REAL, bestJoint: NAT, bestPoint: Point, success: BOOL] = {
Finds the nearest joint of traj to testPoint (and its distance from testPoint).
tolerance2: REAL ← tolerance*tolerance;
thisDist2, bestDist2: REAL;
thisPoint: Point;
jointGen: JointGenerator;
index: INT;
bigBox: GGBasicTypes.BoundBoxObj;
success ← FALSE;
IF useBBox THEN {
bigBox ← [seq.boundBox.loX-tolerance, seq.boundBox.loY-tolerance, seq.boundBox.hiX+tolerance, seq.boundBox.hiY+tolerance, FALSE, FALSE];
IF NOT PointIsInBox[testPoint, bigBox] THEN RETURN; -- success=FALSE
};
jointGen ← GGSequence.JointsInSequence[seq];
index ← GGSequence.NextJoint[jointGen];
IF index = -1 THEN {
bestDist ← maxDistance;
bestJoint ← noJoint;
bestPoint ← [-1.0, -1.0];
RETURN;
};
bestPoint ← GGTraj.FetchJointPos[seq.traj, index];
bestDist2 ← Vectors2d.DistanceSquared[bestPoint, testPoint];
bestJoint ← index;
IF bestDist2 < tolerance2 THEN success ← TRUE;
FOR index ← GGSequence.NextJoint[jointGen], GGSequence.NextJoint[jointGen] UNTIL index = -1 DO
thisPoint ← GGTraj.FetchJointPos[seq.traj, index];
thisDist2 ← Vectors2d.DistanceSquared[thisPoint, testPoint];
IF thisDist2 < tolerance2 THEN success ← TRUE;
IF success AND thisDist2 < bestDist2 THEN {
bestDist2 ← thisDist2;
bestJoint ← index;
bestPoint ← thisPoint;
};
ENDLOOP;
bestDist ← RealFns.SqRt[bestDist2];
};
NearestControlPoint: PROC [testPoint: Point, seq: Sequence, tolerance: REAL] RETURNS [bestDist: REAL, bestSeg: NAT, bestControlPoint: NAT, bestPoint: Point, success: BOOL] = {
Finds the nearest control point of seq (within tolerance) to testPoint (and its distance from testPoint).
SomeCP: PROC [i: NAT] RETURNS [BOOL] = {
cpCount: NAT ← seq.controlPoints[i].len;
FOR j: NAT IN [0..cpCount) DO
IF seq.controlPoints[i][j] THEN RETURN[TRUE];
ENDLOOP;
RETURN[FALSE];
};
tolerance2: REAL ← tolerance*tolerance;
thisDist2, bestDist2: REAL;
thisControlPoint: NAT;
thisPoint: Point;
segGen: SegmentGenerator;
thisSuccess: BOOL;
next: GGSequence.SegAndIndex;
bigBox: GGBasicTypes.BoundBoxObj;
success ← FALSE;
IF useBBox THEN {
bigBox ← [seq.boundBox.loX-tolerance, seq.boundBox.loY-tolerance, seq.boundBox.hiX+tolerance, seq.boundBox.hiY+tolerance, FALSE, FALSE];
IF NOT PointIsInBox[testPoint, bigBox] THEN RETURN; -- success=FALSE
};
segGen ← GGSequence.SegmentsInSequence[seq];
next ← GGSequence.NextSegmentAndIndex[segGen];
WHILE next.seg#NIL AND NOT SomeCP[next.index] DO
next ← GGSequence.NextSegmentAndIndex[segGen];
ENDLOOP;
IF next.seg = NIL THEN { -- The sequence has no control points
bestDist ← maxDistance; -- magic number meaning no segment
bestControlPoint ← noCP; -- magic number meaning no CP
bestPoint ← [-1.0, -1.0];
RETURN;
};
[bestPoint, thisControlPoint, thisSuccess] ← next.seg.class.closestControlPoint[next.seg, testPoint, tolerance];
IF NOT thisSuccess THEN {
bestDist2 ← maxDistance;
bestSeg ← noSeg;
bestControlPoint ← noCP;
bestPoint ← [-1.0, -1.0];
}
ELSE {
bestDist2 ← Vectors2d.DistanceSquared[bestPoint, testPoint];
bestSeg ← next.index;
bestControlPoint ← thisControlPoint;
success ← TRUE;
};
FOR next ← GGSequence.NextSegmentAndIndex[segGen], GGSequence.NextSegmentAndIndex[segGen] UNTIL next.seg = NIL DO
IF SomeCP[next.index] THEN {
[thisPoint, thisControlPoint, thisSuccess] ← next.seg.class.closestControlPoint[next.seg, testPoint, tolerance];
IF NOT thisSuccess THEN {
thisDist2 ← maxDistance;
thisPoint ← [-1.0, -1.0];
}
ELSE {
thisDist2 ← Vectors2d.DistanceSquared[thisPoint, testPoint];
success ← TRUE;
};
IF success AND thisDist2 < bestDist2 THEN {
bestDist2 ← thisDist2;
bestSeg ← next.index;
bestControlPoint ← thisControlPoint;
bestPoint ← thisPoint;
};
};
ENDLOOP;
bestDist ← RealFns.SqRt[bestDist2];
};
Storage Pools
maxPoints: NAT = 6;
maxCurves: NAT = 6;
GravityPool: TYPE = REF GravityPoolObj;
GravityPoolObj: TYPE = RECORD [
pointPoolIndex: NAT ← 0,
pointPool: ARRAY [0..maxPoints) OF GoodPoint,
curvePoolIndex: NAT ← 0,
curvePool: ARRAY [0..maxCurves) OF GoodCurve
];
GetPointsFromPool: PROC [ggData: GGData] RETURNS [p1, p2: GoodPoint] = {
To be used to reduce GoodPoint allocations.
pool: GravityPool ← NARROW[ggData.gravityPool];
IF pool.pointPoolIndex >= maxPoints THEN ERROR;
p1 ← pool.pointPool[pool.pointPoolIndex];
p2 ← pool.pointPool[pool.pointPoolIndex+1];
pool.pointPoolIndex ← pool.pointPoolIndex + 2;
};
ReturnPointsToPool: PROC [p1, p2: GoodPoint, ggData: GGData] = {
pool: GravityPool ← NARROW[ggData.gravityPool];
IF pool.pointPoolIndex<2 THEN ERROR;
pool.pointPoolIndex ← pool.pointPoolIndex - 1;
pool.pointPool[pool.pointPoolIndex] ← p1;
pool.pointPoolIndex ← pool.pointPoolIndex - 1;
pool.pointPool[pool.pointPoolIndex] ← p2;
};
GetCurvesFromPool: PROC [ggData: GGData] RETURNS [c1, c2: GoodCurve] = {
To be used to reduce GoodCurve allocations.
pool: GravityPool ← NARROW[ggData.gravityPool];
IF pool.curvePoolIndex >= maxCurves THEN ERROR;
c1 ← pool.curvePool[pool.curvePoolIndex];
c2 ← pool.curvePool[pool.curvePoolIndex+1];
pool.curvePoolIndex ← pool.curvePoolIndex + 2;
};
ReturnCurvesToPool: PROC [c1, c2: GoodCurve, ggData: GGData] = {
pool: GravityPool ← NARROW[ggData.gravityPool];
IF pool.curvePoolIndex<2 THEN ERROR;
pool.curvePoolIndex ← pool.curvePoolIndex - 1;
pool.curvePool[pool.curvePoolIndex] ← c1;
pool.curvePoolIndex ← pool.curvePoolIndex - 1;
pool.curvePool[pool.curvePoolIndex] ← c2;
};
NewGravityPool: PUBLIC PROC [] RETURNS [REF] = { -- reuseable storage for BestPointAndCurve proc to avoid NEWs
pool: GravityPool ← NEW[GravityPoolObj]; -- indices are automatically made =0
FOR i: NAT IN [0..maxPoints) DO
pool.pointPool[i] ← NEW[GoodPointObj];
ENDLOOP;
FOR i: NAT IN [0..maxCurves) DO
pool.curvePool[i] ← NEW[GoodCurveObj];
ENDLOOP;
RETURN[pool];
};
InitStats: PROC [] = {
interval: CodeTimer.Interval;
interval ← CodeTimer.CreateInterval[$UniMap];
CodeTimer.AddInt[interval, $Gargoyle];
};
InitStats[];
END.
Pier, December 5, 1985 10:06:40 am PST
changes to: removed all references to camera.
Bier, January 23, 1986 5:46:09 pm PST
An initial policy decision was that any object which was gravity active should be drawn on the alignment lines plane. This meant that all trajectories were drawn when they were gravity active, even though they are already visible (modulo overlap). This had the nice side effect that all trajectories become visible during selection. It also helped with debugging (remember the "ghosts"?) However, I am changing this policy now for performance reasons. I may change my mind later.
changes to: DrawAlignBag, DrawAlignBagRegardless, DIRECTORY, GGGravityImpl
Pier, June 11, 1986 3:15:44 pm PDT
renamed all references to activeObjects to be currentObjects
renamed all references to sensitiveObjects to be activeObjects