public class BezierControlPoint { BezierControlPoint (pt point) { p = point; dir = new pt(1,1,1); dir.unit(); sleft = 20.0; sright = 20.0; } BezierControlPoint make () { BezierControlPoint bcp = new BezierControlPoint (p.make()); bcp.dir = dir.make(); bcp.sleft = sleft; bcp.sright = sright; bcp.dist = dist; return bcp; } pt getLeftAnchor () { pt ret = dir.make (); ret.mul(1 * sleft); ret.addPt (p); return ret; } pt getRightAnchor () { pt ret = dir.make (); ret.mul(-1 * sright); ret.addPt (p); return ret; } pt getLeftTangent () { pt ret = dir.make (); ret.mul(sleft); ret.addPt (p); return ret; } pt getRightTangent () { pt ret = dir.make (); ret.mul(-sright); ret.addPt (p); return ret; } void setLeftTangentFromMouse (boolean updateDir) { pt cur = new pt(0,0,0); cur.setFromMouse (); cur.subPt(p); sleft = cur.norm(); if (updateDir) { cur.unit (); dir = cur; } } void setRightTangentFromMouse (boolean updateDir) { pt cur = new pt(0,0,0); cur.setFromMouse (); cur.subPt(p); sright = cur.norm(); if (updateDir) { cur.unit (); cur.mul(-1.0); dir = cur; } } void saveTo (ArrayList a) { p.saveTo(a); dir.saveTo(a); a.add( "" + sleft ); a.add( "" + sright); } void readFrom (ArrayList a) { p = new pt(0,0,0); p.readFrom(a); dir = new pt(0,0,0); dir.readFrom(a); sleft = Float.parseFloat ( (String) a.remove(0) ); sright = Float.parseFloat ( (String) a.remove(0) ); } pt p; pt dir; float sleft; float sright; float dist=0; } public class BezierCurve implements ScalarFunction, NewtonFunction { ArrayList pts = new ArrayList (); float travelDist =0; float velocity = 1.0 / 300.0; int curControlPoint = -1; int curAdjustCurve = -1; int curAnchorPoint = -1; boolean leftAnchor = true; BezierCurve() {} void saveTo (ArrayList a) { a.add ( "" + pts.size() ); for ( int i =0; i < pts.size(); ++i ) { ((BezierControlPoint) pts.get(i)).saveTo(a); } } void readFrom (ArrayList a ) { pts.clear(); int n = Integer.parseInt ( (String) a.remove(0) ); for ( int i =0; i < n; ++i) { BezierControlPoint p = new BezierControlPoint (new pt(0,0,0)); p.readFrom(a); pts.add(p); } calcLength(true); } void addPoint (BezierControlPoint p) { pts.add(p); } BezierControlPoint getLastPoint () { return (BezierControlPoint) pts.get(pts.size()-1); } BezierControlPoint getPoint(int i) { return (BezierControlPoint) pts.get(i); } int incidentControlPoint (pt p, float rad) { for ( int i =0, n = pts.size(); i < n; ++i ) { pt cur = p.make(); cur.subPt (getPoint(i).p); if ( cur.norm() < rad ) return i; } return -1; } int incidentLeftAnchorPoint (pt p, float rad) { for ( int i =0, n = pts.size(); i < n; ++i ) { pt cur = p.make(); cur.subPt (getPoint(i).getLeftTangent ()); if ( cur.norm() < rad ) return i; } return -1; } int incidentRightAnchorPoint (pt p, float rad) { for ( int i =0, n = pts.size(); i < n; ++i ) { pt cur = p.make(); cur.subPt (getPoint(i).getRightTangent ()); if ( cur.norm() < rad ) return i; } return -1; } void drawCurve (boolean midPoints, int index) { pt val = new pt(0,0,0); pt tangent = new pt(0,0,0); for ( int j =0, m = pts.size(); j < m; ++j ) { BezierControlPoint bcp = (BezierControlPoint) pts.get(j); stroke(255,0,0); fill (255,0,0); ellipseMode(CENTER); ellipse(bcp.p.x, bcp.p.y,4,4); if ( j == 0 ) { // draw index textFont(curveFont,14); stroke(0,255,0); fill(0,255,0); textAlign(CENTER); textLeading(10); text ("" + index , bcp.p.x, bcp.p.y-5); } noFill(); if (j+1 < m) { stroke(255,0,0); strokeWeight(1); BezierControlPoint bcp2 = (BezierControlPoint) pts.get(j+1); bezier ( bcp.p.x, bcp.p.y, bcp.getLeftAnchor().x, bcp.getLeftAnchor().y, bcp2.getRightAnchor().x, bcp2.getRightAnchor().y, bcp2.p.x, bcp2.p.y ); if (midPoints) { float t = sampleAt( (bcp.dist +bcp2.dist)*0.5,false); eval(t,val,tangent); stroke(255,0,0); noFill(); ellipse (val.x, val.y, 3, 3); } strokeWeight(2); stroke(0,0,255,128); fill (0,0,255,128); line ( bcp.p.x, bcp.p.y, bcp.getLeftTangent().x, bcp.getLeftTangent().y); ellipse (bcp.getLeftTangent().x, bcp.getLeftTangent().y,3,3); stroke(0,255,0,128); fill (0,255,0,128); line ( bcp2.p.x, bcp2.p.y, bcp2.getRightTangent().x, bcp2.getRightTangent().y); ellipse (bcp2.getRightTangent().x, bcp2.getRightTangent().y,3,3); strokeWeight(1); } } } void adjustLastDir () { if (pts.size() > 1) { BezierControlPoint bcp = (BezierControlPoint) pts.get(pts.size()-2); BezierControlPoint bcp2 = (BezierControlPoint) pts.get(pts.size()-1); bcp2.dir = bcp2.p.make(); bcp2.dir.subPt (bcp.p); bcp2.dir.unit(); } } BezierControlPoint curLeft = null; BezierControlPoint curRight = null; int curSegment; ArrayList knotvals = new ArrayList(); float fullLength; float curTmpDist; float curTmpOffset; float curScale; GaussQuad gauss = new GaussQuad(); NewtonIter newton = new NewtonIter(); float calcLength(boolean normalize) { knotvals.clear (); fullLength =0; for( int i =0, sz = pts.size(); i < sz-1;++i) { curSegment = i; curLeft = (BezierControlPoint) pts.get(i); curRight = (BezierControlPoint) pts.get(i+1); curLeft.dist = fullLength; fullLength = gauss.adaptiveIntegrate (this, i, i+1, fullLength); knotvals.addAll( gauss.getKnotVals()); // remove last point, cause we don't want to have double points if (i pts.size()-1) t = pts.size()-1; curSegment = floor(t); if ( t == pts.size()-1) { t = 1; curSegment--; } else t -= curSegment; curLeft = (BezierControlPoint) pts.get(curSegment); curRight = (BezierControlPoint) pts.get(curSegment+1); pt[] P = { curLeft.p.make(), curLeft.getLeftAnchor(), curRight.getRightAnchor(), curRight.p.make() }; P[0].s(t,P[1]); P[1].s(t,P[2]); P[2].s(t,P[3]); P[0].s(t,P[1]); P[1].s(t,P[2]); tangent.setTo( P[1].add ( P[0].sca(-1.0) )); P[0].s(t,P[1]); value.setTo(P[0]); } void sampleAt (float d, pt value, pt tangent) { eval(sampleAt(d,false),value,tangent); } float sampleAt(float d, boolean justInterpolate) { if (d>=1) return pts.size()-1; if (d <= 0) return 0; Knot tmp = new Knot(0,d); int index = Arrays.binarySearch (knotvals.toArray(),tmp, new KnotCompare()); if ( index < 0 ) { ++index; index *= -1; Knot a = (Knot)knotvals.get(index-1); Knot b = (Knot)knotvals.get(index); float fraction =(d-a.val) / (b.val-a.val); float interp = (1-fraction)*a.t + fraction * b.t; if (justInterpolate) { return interp; } else { // search for minimum via Ralph-Newton iteration // initialize with interp if ( (b.val - a.val ) < 1e-5 ) return interp; else { curTmpOffset = a.t; curSegment = floor(curTmpOffset); curLeft = (BezierControlPoint) pts.get(curSegment); curRight = (BezierControlPoint) pts.get(curSegment+1); curTmpDist = (d - a.val)*fullLength; float res = newton.findRoot(this,interp); return res; } } } else return ((Knot)knotvals.get(index+1)).t; } void updateVelocityFromCurvature() { float d = travelDist; if (d == 0 || d == 1) return; float t = sampleAt(d, true); curSegment = floor(t); t -= curSegment; curLeft = (BezierControlPoint) pts.get(curSegment); curRight = (BezierControlPoint) pts.get(curSegment+1); pt[] P = { curLeft.p, curLeft.getLeftAnchor(), curRight.getRightAnchor(), curRight.p }; pt a = P[0].sca(-1.0).add ( P[1].sca(3.0) ).add ( P[2].sca(-3.0)).add ( P[3] ); pt b = P[0].sca(3.0).add ( P[1].sca(-6.0) ).add ( P[2].sca(3.0)); pt c = P[0].sca(-3.0).add ( P[1].sca(3.0) ); pt df = a.sca(3*t*t).add ( b.sca(2.0*t) ).add(c); pt ddf = a.sca(6*t).add ( b.sca(2.0) ); float n = df.norm(); float curvature = abs(df.x * ddf.y - ddf.x * df.y) / (n*n*n); velocity = 1.0 / 500.0 + curvature/10; } boolean handlePressEvent () { pt val = new pt(0,0,0); pt tangent = new pt(0,0,0); pt p = new pt(0,0,0); p.setFromMouse(); float rad = 5; int j = incidentControlPoint(p, rad); if ( j >= 0 ) { curControlPoint = j; return true; } j = incidentLeftAnchorPoint (p, rad); if ( j >= 0 ) { curAnchorPoint = j; leftAnchor = true; return true; } j = incidentRightAnchorPoint (p,rad); if ( j >= 0 ) { curAnchorPoint = j; leftAnchor = false; return true; } for ( j=0; j < pts.size()-1;++j) { BezierControlPoint bcp = (BezierControlPoint) pts.get(j); BezierControlPoint bcp2 = (BezierControlPoint) pts.get(j+1); float t = sampleAt((bcp.dist+bcp2.dist)*0.5,false); eval(t,val,tangent); p.setFromMouse(); p.subPt(val); if ( p.norm() < rad ) { BezierControlPoint bcpt = new BezierControlPoint(val.make()); bcpt.dir = tangent.make(); bcpt.dir.unit(); pts.add (j+1,bcpt); curControlPoint = j+1; return true; } } return false; } boolean handleReleaseEvent () { calcLength(true); if ( curControlPoint >= 0 ) { pt mouse = new pt(mouseX,mouseY,0); if ( mouse.x < 0 || mouse.y < 0 || mouse.x >= myImage.width || mouse.y > myImage.height ) pts.remove(curControlPoint); if ( pts.size() == 0 ) { return true; } calcLength(true); } curControlPoint = -1; curAnchorPoint = -1; return false; } void handleDragEvent () { if (curControlPoint >= 0 ) { getPoint(curControlPoint).p.setFromMouse (); calcLength(true); return; } if (curAnchorPoint >= 0 ) { if ( leftAnchor ) getPoint (curAnchorPoint).setLeftTangentFromMouse (mouseButton == LEFT && ( key == CODED ? (keyCode != CONTROL) : true)); else getPoint (curAnchorPoint).setRightTangentFromMouse (mouseButton == LEFT && ( key == CODED ? (keyCode != CONTROL) : true)); calcLength(true); } } }