X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fcode.git;a=blobdiff_plain;f=src%2Fbezier.h;h=2b0c1e1ab3d8afae823168da1299965cd6f60e5a;hp=a7124afd8f250a03460968ff355e70282a4d1961;hb=138ee74c900c6f485cdd959d55c01099d6043661;hpb=8b3424a48d2d2e20de1a0e60ff6e1d84b9b5e226 diff --git a/src/bezier.h b/src/bezier.h index a7124af..2b0c1e1 100644 --- a/src/bezier.h +++ b/src/bezier.h @@ -15,7 +15,7 @@ namespace IPDF extern std::vector SolveQuadratic(const Real & a, const Real & b, const Real & c, const Real & min = 0, const Real & max = 1); - extern std::vector SolveCubic(const Real & a, const Real & b, const Real & c, const Real & d, const Real & min = 0, const Real & max = 1, const Real & delta = 1e-4); + extern std::vector SolveCubic(const Real & a, const Real & b, const Real & c, const Real & d, const Real & min = 0, const Real & max = 1, const Real & delta = 1e-9); /** A _cubic_ bezier. **/ struct Bezier @@ -34,7 +34,7 @@ namespace IPDF } - const Type & GetType() + Type GetType() { if (type != Bezier::UNKNOWN) return type; @@ -53,17 +53,17 @@ namespace IPDF Real d2 = a3*b1 - a1*b3; Real d3 = a1*b2 - a2*b1; - if (d1 == d2 && d2 == d3 && d3 == 0) + if (Abs(d1+d2+d3) < 1e-6) { type = LINE; //Debug("LINE %s", Str().c_str()); return type; } - Real delta1 = -d1*d1; + Real delta1 = -(d1*d1); Real delta2 = d1*d2; - Real delta3 = d1*d3 -d2*d2; - if (delta1 == delta2 && delta2 == delta3 && delta3 == 0) + Real delta3 = d1*d3 -(d2*d2); + if (Abs(delta1+delta2+delta3) < 1e-6) { type = QUADRATIC; @@ -72,7 +72,7 @@ namespace IPDF } Real discriminant = d1*d3*4 -d2*d2; - if (discriminant == 0) + if (Abs(discriminant) < 1e-6) { type = CUSP; //Debug("CUSP %s", Str().c_str()); @@ -87,6 +87,7 @@ namespace IPDF type = LOOP; //Debug("LOOP %s", Str().c_str()); } + //Debug("disc %.30f", discriminant); return type; } @@ -102,7 +103,7 @@ namespace IPDF * Construct absolute control points using relative control points to a bounding rectangle * ie: If cpy is relative to bounds rectangle, this will be absolute */ - Bezier(const Bezier & cpy, const Rect & t = Rect(0,0,1,1)) : x0(cpy.x0), y0(cpy.y0), x1(cpy.x1), y1(cpy.y1), x2(cpy.x2),y2(cpy.y2), x3(cpy.x3), y3(cpy.y3), type(UNKNOWN) + Bezier(const Bezier & cpy, const Rect & t = Rect(0,0,1,1)) : x0(cpy.x0), y0(cpy.y0), x1(cpy.x1), y1(cpy.y1), x2(cpy.x2),y2(cpy.y2), x3(cpy.x3), y3(cpy.y3), type(cpy.type) { x0 *= t.w; y0 *= t.h; @@ -178,69 +179,69 @@ namespace IPDF } // Performs one round of De Casteljau subdivision and returns the [t,1] part. - Bezier DeCasteljauSubdivideRight(const Real& t) + Bezier DeCasteljauSubdivideLeft(const Real& t) { Real one_minus_t = Real(1) - t; // X Coordinates - Real x01 = x0*t + x1*one_minus_t; - Real x12 = x1*t + x2*one_minus_t; - Real x23 = x2*t + x3*one_minus_t; + Real x01 = x1*t + x0*one_minus_t; + Real x12 = x2*t + x1*one_minus_t; + Real x23 = x3*t + x2*one_minus_t; - Real x012 = x01*t + x12*one_minus_t; - Real x123 = x12*t + x23*one_minus_t; + Real x012 = x12*t + x01*one_minus_t; + Real x123 = x23*t + x12*one_minus_t; - Real x0123 = x012*t + x123*one_minus_t; + Real x0123 = x123*t + x012*one_minus_t; // Y Coordinates - Real y01 = y0*t + y1*one_minus_t; - Real y12 = y1*t + y2*one_minus_t; - Real y23 = y2*t + y3*one_minus_t; + Real y01 = y1*t + y0*one_minus_t; + Real y12 = y2*t + y1*one_minus_t; + Real y23 = y3*t + y2*one_minus_t; - Real y012 = y01*t + y12*one_minus_t; - Real y123 = y12*t + y23*one_minus_t; + Real y012 = y12*t + y01*one_minus_t; + Real y123 = y23*t + y12*one_minus_t; - Real y0123 = y012*t + y123*one_minus_t; + Real y0123 = y123*t + y012*one_minus_t; return Bezier(x0, y0, x01, y01, x012, y012, x0123, y0123); } - // Performs one round of De Casteljau subdivision and returns the [0,t] part. - Bezier DeCasteljauSubdivideLeft(const Real& t) + // Performs one round of De Casteljau subdivision and returns the [t,1] part. + Bezier DeCasteljauSubdivideRight(const Real& t) { Real one_minus_t = Real(1) - t; // X Coordinates - Real x01 = x0*t + x1*one_minus_t; - Real x12 = x1*t + x2*one_minus_t; - Real x23 = x2*t + x3*one_minus_t; + Real x01 = x1*t + x0*one_minus_t; + Real x12 = x2*t + x1*one_minus_t; + Real x23 = x3*t + x2*one_minus_t; - Real x012 = x01*t + x12*one_minus_t; - Real x123 = x12*t + x23*one_minus_t; + Real x012 = x12*t + x01*one_minus_t; + Real x123 = x23*t + x12*one_minus_t; - Real x0123 = x012*t + x123*one_minus_t; + Real x0123 = x123*t + x012*one_minus_t; // Y Coordinates - Real y01 = y0*t + y1*one_minus_t; - Real y12 = y1*t + y2*one_minus_t; - Real y23 = y2*t + y3*one_minus_t; + Real y01 = y1*t + y0*one_minus_t; + Real y12 = y2*t + y1*one_minus_t; + Real y23 = y3*t + y2*one_minus_t; - Real y012 = y01*t + y12*one_minus_t; - Real y123 = y12*t + y23*one_minus_t; + Real y012 = y12*t + y01*one_minus_t; + Real y123 = y23*t + y12*one_minus_t; - Real y0123 = y012*t + y123*one_minus_t; + Real y0123 = y123*t + y012*one_minus_t; return Bezier(x0123, y0123, x123, y123, x23, y23, x3, y3); } Bezier ReParametrise(const Real& t0, const Real& t1) { - Debug("Reparametrise: %f -> %f",t0,t1); + Debug("Reparametrise: %f -> %f",Double(t0),Double(t1)); Bezier new_bezier; // Subdivide to get from [0,t1] new_bezier = DeCasteljauSubdivideLeft(t1); // Convert t0 from [0,1] range to [0, t1] Real new_t0 = t0 / t1; - Debug("New t0 = %f", new_t0); + Debug("New t0 = %f", Double(new_t0)); new_bezier = new_bezier.DeCasteljauSubdivideRight(new_t0); Debug("%s becomes %s", this->Str().c_str(), new_bezier.Str().c_str()); @@ -252,35 +253,19 @@ namespace IPDF // Find points of intersection with the rectangle. Debug("Clipping Bezier to Rect %s", r.Str().c_str()); - // Convert bezier coefficients -> cubic coefficients - Real xd = x0 - r.x; - Real xc = Real(3)*(x1 - x0); - Real xb = Real(3)*(x2 - x1) - xc; - Real xa = x3 - x0 - xc - xb; // Find its roots. - std::vector x_intersection = SolveCubic(xa, xb, xc, xd); + std::vector x_intersection = SolveXParam(r.x); // And for the other side. - xd = x0 - r.x - r.w; - std::vector x_intersection_pt2 = SolveCubic(xa, xb, xc, xd); + std::vector x_intersection_pt2 = SolveXParam(r.x + r.w); x_intersection.insert(x_intersection.end(), x_intersection_pt2.begin(), x_intersection_pt2.end()); - // Similarly for y-coordinates. - // Convert bezier coefficients -> cubic coefficients - Real yd = y0 - r.y; - Real yc = Real(3)*(y1 - y0); - Real yb = Real(3)*(y2 - y1) - yc; - Real ya = y3 - y0 - yc - yb; - // Find its roots. - std::vector y_intersection = SolveCubic(ya, yb, yc, yd); + std::vector y_intersection = SolveYParam(r.y); - // And for the other side. - yd = y0 - r.y - r.h; - - std::vector y_intersection_pt2 = SolveCubic(ya, yb, yc, yd); + std::vector y_intersection_pt2 = SolveYParam(r.y+r.h); y_intersection.insert(y_intersection.end(), y_intersection_pt2.begin(), y_intersection_pt2.end()); // Merge and sort. @@ -290,6 +275,12 @@ namespace IPDF std::sort(x_intersection.begin(), x_intersection.end()); Debug("Found %d intersections.\n", x_intersection.size()); + for(auto t : x_intersection) + { + Real ptx, pty; + Evaluate(ptx, pty, t); + Debug("Root: t = %f, (%f,%f)", Double(t), Double(ptx), Double(pty)); + } std::vector all_beziers; if (x_intersection.size() <= 2) @@ -302,16 +293,16 @@ namespace IPDF { Real t1 = *it; if (t1 == t0) continue; - Debug(" -- t0: %f to t1: %f", t0, t1); + Debug(" -- t0: %f to t1: %f", Double(t0), Double(t1)); Real ptx, pty; Evaluate(ptx, pty, ((t1 + t0) / Real(2))); - if (true || r.PointIn(ptx, pty)) + if (r.PointIn(ptx, pty)) { all_beziers.push_back(this->ReParametrise(t0, t1)); } else { - Debug("Segment removed (point at %f, %f)", ptx, pty); + Debug("Segment removed (point at %f, %f)", Double(ptx), Double(pty)); } t0 = t1; }