/***** * knot.h * Andy Hammerlindl 200/02/10 * * Describes a knot, a point and its neighbouring specifiers, used as an * intermediate structure in solving paths. *****/ #ifndef KNOT_H #define KNOT_H #include #include #include #include "mod.h" #include "pair.h" #include "path.h" namespace camp { using mem::vector; // The choice of branch cuts of atan2 disguishes between y=+0.0 and y=-0.0 in // the case where x<0. This can lead to strange looking paths being // calculated from guides of the form a..b..cycle. To avoid these degenerate // cases, the niceAngle routine moves the branch cut so that the sign of a // zero won't matter. double niceAngle(pair z); // A cyclic vector: ie. a vector where the index is taken mod the size of the // vector. template class cvector : public vector { public: cvector() {} cvector(size_t n) : vector(n) {} cvector(size_t n, const T& t) : vector(n,t) {} cvector(const vector& v) : vector(v) {} T& operator[](Int j) { return vector::operator[](imod(j,(Int) this->size())); } const T& operator[](Int j) const { return vector::operator[](imod(j,(Int) this->size())); } }; // Forward declaration. class knotlist; /* A linear equation (one of a set of equations to solve for direction through knots in a path). The i-th equation is: pre*theta[i-1] + piv*theta[i] + post*theta[i+1] = aug where indices are taken mod n. */ struct eqn { double pre,piv,post,aug; eqn(double pre, double piv, double post, double aug) : pre(pre), piv(piv), post(post), aug(aug) {} friend ostream& operator<< (ostream& out, const eqn& e) { return out << e.pre << " * pre + " << e.piv << " * piv + " << e.post << " * post = " << e.aug; } }; // A direction specifier, telling how the path behaves coming in or out of a // point. The base class represents the "open" specifier. class spec : public gc { public: virtual ~spec() {} // If the knot is open, it gives no restriction on the behavior of the // path. virtual bool open() { return true; } virtual bool controlled() { return false; } virtual pair control() {return pair(0.0,0.0);} virtual double curl() { return -1.0; } virtual pair dir() { return pair(0.0,0.0); } // When a knot has a restriction on one side but is open on the other, the // restriction implies a restriction on the other side. This is the partner // restriction defined here, where the pair argument is for the location of // the knot. virtual spec *outPartner(pair) { return this; } virtual spec *inPartner(pair) { return this; } virtual void print(ostream&) const {} }; inline ostream& operator<< (ostream& out, spec& s) { s.print(out); return out; } // Specifier used at an endpoint. class endSpec : public spec { public: bool open() { return false; } // Returns an equation used to solve for the thetas along the knot. These are // called by eqnprop in the non-cyclic case for the first and last equations. virtual eqn eqnOut(Int j, knotlist& l, cvector& d, cvector& psi) = 0; virtual eqn eqnIn (Int j, knotlist& l, cvector& d, cvector& psi) = 0; }; // A specifier with a given direction (in radians). class dirSpec : public endSpec { double given; public: // Direction should be given in the range [-PI,PI] dirSpec(double given) : given(given) {} dirSpec(pair z) : given(niceAngle(z)) {} pair dir() { return expi(given); } eqn eqnOut(Int j, knotlist& l, cvector& d, cvector& psi); eqn eqnIn (Int j, knotlist& l, cvector& d, cvector& psi); void print(ostream& out) const { out << "{dir(" << degrees(given) << ")}"; } }; // A curl specifier. The curvature at the end knot should be gamma times the // curvature at the neighbouring knot. class curlSpec : public endSpec { double gamma; public: // Gamma should be non-negative. curlSpec(double gamma=1.0) : gamma(gamma) { if(gamma < 0) reportError("curl cannot be less than 0"); } double curl() { return gamma; } eqn eqnOut(Int j, knotlist& l, cvector& d, cvector& psi); eqn eqnIn (Int j, knotlist& l, cvector& d, cvector& psi); void print(ostream& out) const { out << "{curl " << gamma << "}"; } }; // A specifier with a control point. All information for this portion of the // curve has been determined. class controlSpec : public spec { public: pair cz; bool straight; controlSpec(pair cz, bool straight=false) : cz(cz), straight(straight) {} bool open() { return false; } bool controlled() { return true; } pair control() { return cz; } // The partner spec will be a dirSpec in the same direction the specifier // takes the path, unless the velocity is zero, then it uses a curl // specifier. spec *outPartner(pair); spec *inPartner(pair); void print(ostream& out) const { // NOTE: This format cannot be read back in. out << "{control " << cz << "}"; } }; // The tension information for one side of a knot. struct tension { double val; bool atleast; tension(double val=1.0, bool atleast=false) : val(val), atleast(atleast) { if(val < 0.75) reportError("tension cannot be less than 3/4"); } }; inline ostream& operator<<(ostream& out, tension t) { return out << "tension" << (t.atleast ? " atleast " : " ") << t.val; } // A knot, a point with specifiers to double the path coming in and going out // of the knot. struct knot { pair z; spec *in; spec *out; tension tin, tout; knot() {} knot(pair z, spec *in, spec *out, tension tin=tension(), tension tout=tension()) : z(z), in(in), out(out), tin(tin), tout(tout) {} double alpha() { return 1.0/tout.val; } double beta() { return 1.0/tin.val; } }; ostream& operator<<(ostream& out, const knot& k); // Abstract base class for a section of a guide. class knotlist { public: virtual ~knotlist() {} virtual Int length() = 0; virtual bool cyclic() = 0; // Returns the number of knots. Int size() { return cyclic() ? length() : length() + 1; } bool empty() { return size()==0; } virtual knot& cell(Int) = 0; virtual knot& operator[] (Int i) { #if 0 assert(cyclic() || (0 <= i && i <= length())); // Bounds check. #endif return cell(i); } knot& front() { return (*this)[0]; } knot& back() { return (*this)[length()]; } }; // Defines a knotlist as a piece of another knotlist. class subknotlist : public knotlist { knotlist& l; Int a,b; public: subknotlist(knotlist& l, Int a, Int b) : l(l), a(a), b(b) {} Int length() { return b-a; } bool cyclic() { return false; } knot& cell(Int i) { return l[a+i]; } }; struct simpleknotlist : public knotlist { cvector nodes; bool cycles; simpleknotlist(cvector nodes, bool cycles=false) : nodes(nodes), cycles(cycles) {} Int length() { return cycles ? (Int) nodes.size() : (Int) nodes.size() - 1; } bool cyclic() { return cycles; } knot& cell(Int j) { return nodes[j]; } }; // A protopath is a path being made. struct protopath { bool cycles; Int n; mem::vector nodes; protopath(Int n, bool cycles) : cycles(cycles), n(n), nodes(n) {} solvedKnot& operator[](Int j) { return nodes[imod(j,n)]; } bool& straight(Int j) { return (*this)[j].straight; } pair& pre(Int j) { return (*this)[j].pre; } pair& point(Int j) { return (*this)[j].point; } pair& post(Int j) { return (*this)[j].post; } void controlEnds() { if (!cycles) { solvedKnot& start=(*this)[0]; solvedKnot& end=(*this)[n-1]; start.pre=start.point; end.post=end.point; } } // Once all the controls are set, return the final (constant) path. path fix() { return path(nodes,n,cycles); } }; // Represents properties that can be computed along a knotlist. // Examples include distances (d), turning angles (psi), and the linear // equations used to solve for the thetas. template class knotprop { protected: knotlist& l; // Calculate the property for the usual case in the iteration (and for a // cyclic knot, the only case), at the index given. virtual T mid(Int) = 0; // The special cases, these default to the usual case: mid. virtual T solo(Int j) // Calculates the property for a list of length 0. { return mid(j); } virtual T start(Int j) // Calculates it at the start of the list. { return mid(j); } virtual T end(Int j) // Calculate it at the end. { return mid(j); } virtual cvector linearCompute() { Int n=l.length(); cvector v; if (n==0) v.push_back(solo(0)); else { v.push_back(start(0)); for (Int j=1; j cyclicCompute() { Int n=l.length(); cvector v; for (Int j=0; j linearBackCompute() { Int n=l.length(); cvector v; if (n==0) v.push_back(solo(0)); else { v.push_back(end(n)); for (Int j=1; j cyclicBackCompute() { Int n=l.length(); cvector v; for (Int j=1; j<=n; ++j) v.push_back(mid(n-j)); return v; } public: virtual ~knotprop() {} virtual cvector compute() { return l.cyclic() ? cyclicCompute() : linearCompute(); } // Compute the values in the opposite order. This is needed for instance if // the i-th calculation needed a result computed in the i+1-th, such as in the // back substitution for solving thetas. virtual cvector backCompute() { cvector v=l.cyclic() ? cyclicBackCompute() : linearBackCompute(); // Even though they are computed in the backwards order, return them in the // standard order. reverse(v.begin(),v.end()); return v; } knotprop(knotlist& l) : l(l) {} }; // A knot transforms, it takes in one knotlist and transforms it knot for knot // into a new one. class knottrans : public knotprop { protected: virtual knot mid(Int j) { /* By default, just copy the knot. */ return l[j]; } public: virtual ~knottrans() {} knottrans(knotlist& l) : knotprop(l) {} virtual simpleknotlist trans() { return simpleknotlist(compute(),l.cyclic()); } }; // Like a knotprop, but it doesn't compute a vector of values for the knot. It // iterates over the knotlist calling method for side-effect. For instance, // this is used to plug control points into protopaths. class knoteffect { protected: knotlist& l; virtual void mid(Int) = 0; // The special cases, these default to the usual case: mid. virtual void solo(Int j) { mid(j); } virtual void start(Int j) { mid(j); } virtual void end(Int j) { mid(j); } virtual void linearExec() { Int n=l.length(); if (n==0) solo(0); else { start(0); for (Int j=1; j& z); double velocity(double theta, double phi, tension t); } // namespace camp GC_DECLARE_PTRFREE(camp::eqn); GC_DECLARE_PTRFREE(camp::tension); #endif // KNOT_H