From: Sam Moore Date: Mon, 1 Sep 2014 12:55:55 +0000 (+0800) Subject: Classify Beziers, use DeCasteljau for CPU renderer X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fcode.git;a=commitdiff_plain;h=8b3424a48d2d2e20de1a0e60ff6e1d84b9b5e226 Classify Beziers, use DeCasteljau for CPU renderer I don't know how glDrawLines does it, but I can't get rid of the wiggles in straight lines done using CPU renderer. So I switched to DeCasteljau. Then I made it classify the lines and only use one Bresenham instead of 100 anyway. --- diff --git a/src/bezier.cpp b/src/bezier.cpp index 3fa16e3..9d24672 100644 --- a/src/bezier.cpp +++ b/src/bezier.cpp @@ -166,8 +166,8 @@ pair BezierTurningPoints(const Real & p0, const Real & p1, const Rea { return pair(0, 1); } - Real a = (3*(p1-p2) + p3 - p0); - Real b = 2*(p2 - 2*p1 + p0); + Real a = ((p1-p2)*3 + p3 - p0); + Real b = (p2 - p1*2 + p0)*2; Real c = (p1-p0); if (a == 0) { @@ -179,7 +179,7 @@ pair BezierTurningPoints(const Real & p0, const Real & p1, const Rea return pair(t, t); } //Debug("a, b, c are %f, %f, %f", Float(a), Float(b), Float(c)); - if (b*b - 4*a*c < 0) + if (b*b - a*c*4 < 0) { //Debug("No real roots"); return pair(0,1); diff --git a/src/bezier.h b/src/bezier.h index 7ff4f87..a7124af 100644 --- a/src/bezier.h +++ b/src/bezier.h @@ -25,16 +25,72 @@ namespace IPDF Real x2; Real y2; Real x3; Real y3; - typedef enum {LINE, QUADRATIC, CUSP, LOOP, SERPENTINE} Type; + typedef enum {UNKNOWN, LINE, QUADRATIC, CUSP, LOOP, SERPENTINE} Type; Type type; Bezier() = default; // Needed so we can fread/fwrite this struct... for now. - Bezier(Real _x0, Real _y0, Real _x1, Real _y1, Real _x2, Real _y2, Real _x3, Real _y3) : x0(_x0), y0(_y0), x1(_x1), y1(_y1), x2(_x2), y2(_y2), x3(_x3), y3(_y3) + Bezier(Real _x0, Real _y0, Real _x1, Real _y1, Real _x2, Real _y2, Real _x3, Real _y3) : x0(_x0), y0(_y0), x1(_x1), y1(_y1), x2(_x2), y2(_y2), x3(_x3), y3(_y3), type(UNKNOWN) { - //TODO: classify the curve - type = SERPENTINE; + } + const Type & GetType() + { + if (type != Bezier::UNKNOWN) + return type; + // From Loop-Blinn 2005, with w0 == w1 == w2 == w3 = 1 + // Transformed control points: (a0 = x0, b0 = y0) + Real a1 = (x1-x0)*3; + Real a2 = (x0- x1*2 +x2)*3; + Real a3 = (x3 - x0 + (x1 - x2)*3); + + Real b1 = (y1-y0)*3; + Real b2 = (y0- y1*2 +y2)*3; + Real b3 = (y3 - y0 + (y1 - y2)*3); + + // d vector (d0 = 0 since all w = 1) + Real d1 = a2*b3 - a3*b2; + Real d2 = a3*b1 - a1*b3; + Real d3 = a1*b2 - a2*b1; + + if (d1 == d2 && d2 == d3 && d3 == 0) + { + type = LINE; + //Debug("LINE %s", Str().c_str()); + return type; + } + + Real delta1 = -d1*d1; + Real delta2 = d1*d2; + Real delta3 = d1*d3 -d2*d2; + if (delta1 == delta2 && delta2 == delta3 && delta3 == 0) + { + type = QUADRATIC; + + //Debug("QUADRATIC %s", Str().c_str()); + return type; + } + + Real discriminant = d1*d3*4 -d2*d2; + if (discriminant == 0) + { + type = CUSP; + //Debug("CUSP %s", Str().c_str()); + } + else if (discriminant > 0) + { + type = SERPENTINE; + //Debug("SERPENTINE %s", Str().c_str()); + } + else + { + type = LOOP; + //Debug("LOOP %s", Str().c_str()); + } + return type; + } + + std::string Str() const { std::stringstream s; @@ -46,7 +102,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(cpy.type) + 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) { x0 *= t.w; y0 *= t.h; diff --git a/src/objectrenderer.cpp b/src/objectrenderer.cpp index f39bae8..4e59cd0 100644 --- a/src/objectrenderer.cpp +++ b/src/objectrenderer.cpp @@ -7,6 +7,7 @@ #include "view.h" #include #include +#include using namespace std; @@ -254,36 +255,50 @@ void BezierRenderer::RenderUsingCPU(const Objects & objects, const View & view, - Real x[2]; Real y[2]; - control.Evaluate(x[0], y[0], Real(0)); - //Debug("target is (%lu, %lu)", target.w, target.h); - int64_t blen = min(max((int64_t)2, (int64_t)(target.w/view.GetBounds().w)), (int64_t)100); + + unsigned blen = min(max(2U, (unsigned)(target.w/view.GetBounds().w)), min((unsigned)(pix_bounds.w+pix_bounds.h)/4 + 1, 100U)); - Real invblen(1); invblen /= blen; - //Debug("Using %li lines, inverse %f", blen, Double(invblen)); - for (int64_t j = 1; j <= blen; ++j) + // DeCasteljau Divide the Bezier + queue divisions; + divisions.push(control); + while(divisions.size() < blen) { - control.Evaluate(x[j % 2],y[j % 2], invblen*j); - ObjectRenderer::RenderLineOnCPU((int64_t)Double(x[0]),(int64_t)Double(y[0]), (int64_t)Double(x[1]),(int64_t)Double(y[1]), target, Colour(0,0,0,!view.PerformingShading())); + Bezier & current = divisions.front(); + if (current.GetType() == Bezier::LINE) + { + --blen; + continue; + } + divisions.push(current.DeCasteljauSubdivideRight(Real(1)/Real(2))); + divisions.push(current.DeCasteljauSubdivideLeft(Real(1)/Real(2))); + divisions.pop(); + + //Debug("divisions %u", divisions.size()); + } + while (divisions.size() > 0) + { + Bezier & current = divisions.front(); + RenderLineOnCPU(current.x0, current.y0, current.x3, current.y3, target, Colour(0,0,0,!view.PerformingShading())); + divisions.pop(); } - /* - Real u(0); - while (u < Real(1)) + /* Draw the Bezier by sampling + Real invblen(1); invblen /= blen; + Real t(invblen); + Vec2 v0; + Vec2 v1; + control.Evaluate(v0.x, v0.y, 0); + for (int64_t j = 1; j <= blen; ++j) { - u += Real(1e-6); - Real x; Real y; control.Evaluate(x,y,u); - int64_t index = ((int64_t)x + (int64_t)y*target.w)*4; - if (index >= 0 && index < 4*(target.w*target.h)) - { - target.pixels[index+0] = 0; - target.pixels[index+1] = 0; - target.pixels[index+2] = 0; - target.pixels[index+3] = 255; - } + control.Evaluate(v1.x, v1.y, t); + + ObjectRenderer::RenderLineOnCPU(v0.x, v0.y, v1.x, v1.y, target, Colour(0,0,0,!view.PerformingShading())); + //ObjectRenderer::SetColour(target, x[0], y[0], Colour(1,0,0,1)); + //ObjectRenderer::SetColour(target, x[1], y[1], Colour(0,0,1,1)); + t += invblen; + v0 = v1; } */ - } } diff --git a/src/rational.h b/src/rational.h index b019505..f9157c7 100644 --- a/src/rational.h +++ b/src/rational.h @@ -77,6 +77,8 @@ struct Rational { Simplify(); } + + Rational(const T & _P, const T & _Q) : P(_P), Q(_Q) { @@ -174,7 +176,7 @@ struct Rational double ToDouble() const { T num = P, denom = Q; - while (Tabs(num) > T(DBL_MAX)) + while (Tabs(num) > T(1e10)) { num /= T(16); denom /= T(16); @@ -206,8 +208,6 @@ struct Rational - - } #endif //_RATIONAL_H diff --git a/src/real.h b/src/real.h index b766558..322b02b 100644 --- a/src/real.h +++ b/src/real.h @@ -81,7 +81,6 @@ namespace IPDF r *= a; return r; } - struct Vec2 { Real x; @@ -89,6 +88,7 @@ namespace IPDF Vec2() : x(0), y(0) {} Vec2(Real _x, Real _y) : x(_x), y(_y) {} Vec2(const std::pair & p) : x(p.first), y(p.second) {} + Vec2(const std::pair & p) : x(p.first), y(p.second) {} bool operator==(const Vec2& other) const { return (x == other.x) && (y == other.y); } bool operator!=(const Vec2& other) const { return !(*this == other); } diff --git a/src/svg-tests/fox_simple.svg b/src/svg-tests/fox_simple.svg new file mode 100644 index 0000000..58e2b8a --- /dev/null +++ b/src/svg-tests/fox_simple.svg @@ -0,0 +1,235 @@ + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/src/svg-tests/kinematic_diagram.svg b/src/svg-tests/kinematic_diagram.svg new file mode 100644 index 0000000..ca35cc2 --- /dev/null +++ b/src/svg-tests/kinematic_diagram.svg @@ -0,0 +1,1243 @@ + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 1* + 2 + 3 + 4 + 5 + 6 + 7* + 1* + 2 + 3 + 4 + 5* + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 1* + 2 + 3 + 4 + 5* + + + + + Base + Travelling Plate + + = Pin / Revolute (f ) + 1 + + + + = Ball (f ) + 3 + + + = Universal (f ) + 2 + Joints + + 1 + 2 + 3 + Original NUWAR Armn = 17, f = 21, f = 0, f = 0Mobility = -4 + Variation #1n = 11, f = 3, f = 0, f = 12Mobility = 9 + Variation #2n = 11, f = 3, f = 6, f = 6Mobility = 3 + * The base and travelling plate are common to all 3 arms + 1 + 2 + 3 + 1 + 2 + 3 + + diff --git a/src/svg-tests/lines.svg b/src/svg-tests/lines.svg index f15c961..ff7eddb 100644 --- a/src/svg-tests/lines.svg +++ b/src/svg-tests/lines.svg @@ -5,17 +5,20 @@ - + - + - + - + - - + --> + x1="0" y1="200" x2="400" y2="0" stroke="black"/> + +