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, February 20, 1987 4:46:00 pm PST
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: BOOL ← TRUE;
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: BOOL ← FALSE;
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: BOOL ← TRUE;
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 thisDist
2 < bestDist
2
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 thisDist
2 < bestDist
2
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 thisDist
2 < bestDist
2
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