<> <> <> <> <> 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 = { <<-- the vertices used in calculating the current segment>> 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; <<-- building up the new trajectory whose segments consist of the points of the spline>> 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.