DIRECTORY PEBetaSpline, PETrajectoryOps USING [InsertSegment, InsertVertex], PETypes; PEBetaSplineImpl: CEDAR PROGRAM IMPORTS PETrajectoryOps EXPORTS PEBetaSpline = BEGIN BetaSplinePoints: PUBLIC PROCEDURE [seg: PETypes.SegmentList, handleSeg: PETypes.SegmentList, closed: BOOLEAN] RETURNS [splineSegList: PETypes.SegmentList] = { beta1, beta2: REAL; -- the shape parameters of bias and tension, respectively beta1sq, beta1cu: REAL; -- various powers of the tension value for computation purposes b0, b1, b2, b3: REAL; -- the cubic Beta-spline basis functions epsilon: REAL = .01; -- necessary factor to add to max of parameter u to adjust for -- precision errors increment: REAL = .1; -- step size through parametric space invDelta: REAL; -- common factor in the basis functions, cf. article cited above lessThanFour: BOOLEAN _ FALSE; -- don't compute Beta-spline with < 4 control points max: REAL = 1.0; -- max value of parameter u p: PETypes.Point; -- points on the Beta-spline curve splineSeg: PETypes.Segment _ NIL; -- the spline segment to be stored into the new trajectory splineSegNode: PETypes.SegmentNode _ NIL; splineVertex: PETypes.Vertex; -- the spline point to be stored into the trajectory splineVertexList: PETypes.VertexList _ NIL; splineVertexNode: PETypes.VertexNode _ NIL; usq, ucu, u4, u5: REAL; -- various powers of the parameter u for computation purposes SegmentsOnCurve: PROCEDURE = { current, preceding, next, prepreceding: PETypes.Vertex; currentNode, precedingNode, preprecedingNode, nextNode: PETypes.VertexNode; -- firstVertex is true iff current is the 1st vertex of the control polygon firstVertex: BOOLEAN _ TRUE; firstSegment, lastWorkingSeg, secondSegment: PETypes.Segment; splineSegList _ NIL; IF closed THEN seg _ seg.rest; firstSegment _ seg.preceding.first; secondSegment _ seg.preceding.preceding.first; prepreceding _ seg.preceding.first.vertices.first; preceding _ seg.preceding.preceding.first.vertices.first; current _ seg.preceding.preceding.preceding.first.vertices.first; next _ seg.preceding.preceding.preceding.preceding.first.vertices.first; WHILE handleSeg.preceding.first.vertices.first^ # prepreceding^ DO handleSeg _ handleSeg.preceding; ENDLOOP; preprecedingNode _ handleSeg.preceding.first.vertices; precedingNode _ handleSeg.preceding.preceding.first.vertices; currentNode _ handleSeg.preceding.preceding.preceding.first.vertices; nextNode _ handleSeg.preceding.preceding.preceding.preceding.first.vertices; lastWorkingSeg _ seg.preceding.preceding.preceding.preceding.first; IF (current = prepreceding) OR (current = preceding) OR (current = next) OR (prepreceding = next) THEN lessThanFour _ TRUE; WHILE (firstVertex OR (lastWorkingSeg # firstSegment AND ~closed) OR (lastWorkingSeg # secondSegment AND closed)) AND ~lessThanFour DO FOR u: REAL _ 0, u+increment UNTIL u>(max+epsilon) DO -- step thru parameter space usq _ u*u; ucu _ u*usq; u4 _ u*ucu; u5 _ u*u4; beta1 _ preceding.bias + (current.bias-preceding.bias)*(10*ucu - 15*u4 + 6*u5); beta2 _ preceding.tension + (current.tension-preceding.tension)* (10*ucu - 15*u4 + 6*u5); beta1sq _ beta1 * beta1; beta1cu _ beta1 * beta1sq; invDelta _ 1.0/(beta2 + 2*beta1cu + 4*beta1sq + 4*beta1 + 2); b0 _ invDelta*2*ucu; b1 _ invDelta*(2 + 6*beta1*u + (3*beta2 + 6*beta1sq)*usq - (2*beta2 + 2*beta1sq + 2*beta1 + 2)*ucu); b2 _ invDelta*( (beta2 + 4*beta1sq + 4*beta1) + (6*beta1cu - 6*beta1)*u - (3*beta2 + 6*beta1cu + 6*beta1sq)*usq + (2*beta2 + 2*beta1cu + 2*beta1sq + 2*beta1)*ucu ); b3 _ invDelta*( 2*beta1cu - 6*beta1cu*u + 6*beta1cu*usq - 2*beta1cu*ucu); p.x _ prepreceding.point.x*b3 + preceding.point.x*b2 + current.point.x*b1 + next.point.x*b0; p.y _ prepreceding.point.y*b3 + preceding.point.y*b2 + current.point.y*b1 + next.point.y*b0; splineVertex _ NEW[PETypes.VertexRec _ [point: p]]; splineVertexList _ NEW[PETypes.VertexNodeRec]; splineVertexList _ NIL; [splineVertexList, splineVertexNode] _ PETrajectoryOps.InsertVertex[splineVertexList, splineVertex, NIL]; splineSeg _ NEW[PETypes.SegmentRec _ [type: curveTo, fp: splineVertexList.first, vertices: splineVertexList, controlPtPP: preprecedingNode, controlPtP: precedingNode, controlPtC: currentNode, controlPtN: nextNode]]; [splineSegList, splineSegNode] _ PETrajectoryOps.InsertSegment[splineSegList, splineSeg, NIL]; IF firstVertex THEN firstVertex _ FALSE; ENDLOOP; -- finding the vertices used in calculating the next curve segment seg _ seg.preceding; handleSeg _ handleSeg.preceding; prepreceding _ seg.preceding.first.vertices.first; preceding _ seg.preceding.preceding.first.vertices.first; current _ seg.preceding.preceding.preceding.first.vertices.first; next _ seg.preceding.preceding.preceding.preceding.first.vertices.first; preprecedingNode _ handleSeg.preceding.first.vertices; precedingNode _ handleSeg.preceding.preceding.first.vertices; currentNode _ handleSeg.preceding.preceding.preceding.first.vertices; nextNode _ handleSeg.preceding.preceding.preceding.preceding.first.vertices; lastWorkingSeg _ seg.preceding.preceding.preceding.preceding.first; ENDLOOP; }; SegmentsOnCurve[]; }; END. ìPEBetaSplineImpl.mesa Copyright (C) 1984 by Xerox Corporation. All rights reserved. Written by Pauline Ts'o on June 4, 1984 2:23:24 pm PDT Last Edited by: Tso, June 27, 1984 3:14:34 pm PDT Beta Spline routines for the Path Editor. Cf. "Local Control of Bias and Tension in Beta-splines", by Barsky, Brian A. and John C. Beatty in April 1983 issue of acm Transactions on Graphics for a discussion of the mathematics. This routine computes the points of a Beta spline given a list of control points with corresponding beta values (bias and tension). seg should point to the first control point of the active trajectory. -- the vertices used in calculating the current segment The 1st clause indicates whether or not we are just starting the calculations, the 2nd clause sets the condition for exiting the loop for an open control polygon, and the 3rd clause sets the exit condition for a closed control polygon. -- building up the new trajectory whose segments consist of the points of the spline ÊÓ˜Jšœ™J™>Jšœ6™6J™1J˜J™ãJ˜JšÏk ˜ ˜Jšœœ˜4Jšœ˜J˜—šœœ˜Jšœ˜Jšœ˜—J˜Jš˜J˜š Ïnœœ œDœœ)˜ŸJ™ÊJšœœÏi9˜O—JšœœŸ?˜[šœ›@$@œŸ(˜BJšœ œ Ÿ/œŸ*˜rJšœ œŸ%˜