Instability in Lib2geom's D2<SBasis> construction
Hi,
I have noticed a few parts in lib2geom that give unstable output. I am trying to figure out what causes this and possible how to fix it:
In lib2geom’s toy example curvature-test.cpp, we fit osculating circle at a point of a given curve. We can slide along time parameter to fit osculating circle at different point on the curve. I modify the code a little to output the curvature plot of the curve in two ways:
1) Using D2<SBasis> to build curvature graph. Each segment in D2<SBasis> is a copy of SBasis from curvature curve K, offset by a constant. (as seen in RED). Piecewise<SBasis> K = curvature(B); 2) Draw the graph directly by cairo_move_to(), cairo_line_to(). (as seen in GREEN).
The normal result would look like this:
However, when I hover my mouse around randomly (no input has been changed), the curve being fitted using D2<SBasis> will go wild randomly too:
Notice that the green curve that plots curvature with cairo methods is stable. Does anyone know if we have a fix for this? Here is the source file:
The part that seems to give problems is when we define D2<> segment with linear interpolation:
for(unsigned ix = 0; ix < K.segs.size(); ix++) { D2<SBasis> Kxy; Kxy[1] = Linear(450) - K.segs[ix]*400; Kxy[0] = Linear(300*K.cuts[ix] + 150, 300*K.cuts[ix+1] + 150); cairo_d2_sb(cr, Kxy); cairo_set_source_rgba (cr, 1., 0., 0., 0.8); cairo_stroke(cr); }
I did something similar to this in other toy example and got the same instability. I believe that the instability comes from using K.segs[] to define new SBasis (K is a Piecewise<SBasis> that contains curvature of the curve). If I create D2<SBasis> by purely linear segments, my output is very stable:
dd = 0.1; for (double tt = 0; tt < 1.0; tt += dd) { D2<SBasis> Kxy; Kxy[1] = SBasis(450 - K(tt)*400, 450 - K(tt+dd)*400); Kxy[0] = SBasis(150 + 300*(tt), 150 + 300*(tt+dd)); cairo_d2_sb(cr, Kxy); cairo_set_source_rgba (cr, 1., 0., 0., 0.8); cairo_stroke(cr); }
Would appreciate some helps to fix the issue here.
Regards, _______________________ Papoj "Hua" Thamjaroenporn pt2277@...3110...
On Sun, Apr 27, 2014 at 09:03:32PM -0400, Papoj Thamjaroenporn wrote:
Hi,
I have noticed a few parts in lib2geom that give unstable output. I am trying to figure out what causes this and possible how to fix it:
In lib2geom?s toy example curvature-test.cpp, we fit osculating circle at a point of a given curve. We can slide along time parameter to fit osculating circle at different point on the curve. I modify the code a little to output the curvature plot of the curve in two ways:
- Using D2<SBasis> to build curvature graph. Each segment in D2<SBasis> is a copy of SBasis from curvature curve K, offset by a constant. (as seen in RED). Piecewise<SBasis> K = curvature(B);
- Draw the graph directly by cairo_move_to(), cairo_line_to(). (as seen in GREEN).
The normal result would look like this:
However, when I hover my mouse around randomly (no input has been changed), the curve being fitted using D2<SBasis> will go wild randomly too:
Hi Papoj, I wonder if there is a bug in the code which up degrees quads to cubics, it looks like a sign error to me.
njh
Hi Nathan,
Note that the original code of curvature-test.cpp already has this instability, in case you are wondering if it is my own bug.
I’m just wondering: how do you know it is a sign error? In fact, am not sure what’s happening under the hood when we say expression like
Kxy[1] = Linear(450) - K.segs[ix]*400;
where K.segs[ix] is an SBasis object. I looked around in the code and there didn’t seem to have operator-() defined between Linear and SBasis object (but the expression worked, and Linear object is not an SBasis object). So I don’t know where to look further to see if there is a degree increase going on anywhere.
Regards, _______________________ Papoj "Hua" Thamjaroenporn pt2277@...3110...
On Apr 28, 2014, at 2:22 AM, Nathan Hurst <njh@...1927...> wrote:
On Sun, Apr 27, 2014 at 09:03:32PM -0400, Papoj Thamjaroenporn wrote:
Hi,
I have noticed a few parts in lib2geom that give unstable output. I am trying to figure out what causes this and possible how to fix it:
In lib2geom?s toy example curvature-test.cpp, we fit osculating circle at a point of a given curve. We can slide along time parameter to fit osculating circle at different point on the curve. I modify the code a little to output the curvature plot of the curve in two ways:
- Using D2<SBasis> to build curvature graph. Each segment in D2<SBasis> is a copy of SBasis from curvature curve K, offset by a constant. (as seen in RED). Piecewise<SBasis> K = curvature(B);
- Draw the graph directly by cairo_move_to(), cairo_line_to(). (as seen in GREEN).
The normal result would look like this:
However, when I hover my mouse around randomly (no input has been changed), the curve being fitted using D2<SBasis> will go wild randomly too:
Hi Papoj, I wonder if there is a bug in the code which up degrees quads to cubics, it looks like a sign error to me.
njh
On Mon, Apr 28, 2014 at 02:36:50AM -0400, Papoj Thamjaroenporn wrote:
Hi Nathan,
Note that the original code of curvature-test.cpp already has this instability, in case you are wondering if it is my own bug.
No, I recall seeing something like that before.
I?m just wondering: how do you know it is a sign error?
It's a hunch. It reminds me of other similar bugs I've seen. Another similar problem is that it might be being overzealous in truncating the sbasis form. When I worked on this code I tended to use the cout << sbasisInstance << std::endl; form a lot, perhaps with modern IDEs this is no longer needed, but in any case you should try and get some actual numbers out, ideally comparing the correct and wigglified instability values.
In fact, am not sure what?s happening under the hood when we say expression like
Kxy[1] = Linear(450) - K.segs[ix]*400;
It returns a function (sbasis) which represents the pointwise difference between the constant 450 and 400* whatever is in segs. Under the hood it is doing calculations in sbasis space.
where K.segs[ix] is an SBasis object. I looked around in the code and there didn?t seem to have operator-() defined between Linear and SBasis object (but the expression worked, and Linear object is not an SBasis object).
I think it is automatically casting using SBasis(Linear)?
So I don?t know where to look further to see if there is a degree increase going on anywhere.
Let's get some numbers. I remember that there was also a bug in curvature toy where it would introduce a cusp as that was the easier way to satisfy the constraints. I think with some thought we could do better.\ (it might suffice to make the algorithm only consider the two straight through cases, or it might require some backtrack/DP). It would be brilliant if you could add the curvature based editing to inkscape. I tried to do it a long time ago but the canvas code was too much for my puny brain.
njh
Hi Nathan,
Thank you for the email. I am currently booked right now but I will get back to you some time this week to investigate more on this issue. Just one question: what exactly should I print out? I printed a segment of the curvature path (the 4th segment to be exact) in terms of Kxy, and this segment definitely wiggled, but the output was always the same when I hovered my mouse around:
ix: 4 Kxy[0]: {281.25, 290.625}s^0 + ix: 4 Kxy[1]: {372.08, 346.521}s^0 + {-28.7083, -45.4316}s^1 + {-8.2712, -12.9363}s^2 + {1.31768, -0.797948}s^3 + {0.739784, 0.184223}s^4 +
If Kxy is indeed stable, the problem might lie in the method cairo_d2_sb()somewhere.
Regards, _______________________ Papoj "Hua" Thamjaroenporn pt2277@...3110...
On Apr 28, 2014, at 8:49 AM, Nathan Hurst <njh@...1927...> wrote:
On Mon, Apr 28, 2014 at 02:36:50AM -0400, Papoj Thamjaroenporn wrote:
Hi Nathan,
Note that the original code of curvature-test.cpp already has this instability, in case you are wondering if it is my own bug.
No, I recall seeing something like that before.
I?m just wondering: how do you know it is a sign error?
It's a hunch. It reminds me of other similar bugs I've seen. Another similar problem is that it might be being overzealous in truncating the sbasis form. When I worked on this code I tended to use the cout << sbasisInstance << std::endl; form a lot, perhaps with modern IDEs this is no longer needed, but in any case you should try and get some actual numbers out, ideally comparing the correct and wigglified instability values.
In fact, am not sure what?s happening under the hood when we say expression like
Kxy[1] = Linear(450) - K.segs[ix]*400;
It returns a function (sbasis) which represents the pointwise difference between the constant 450 and 400* whatever is in segs. Under the hood it is doing calculations in sbasis space.
where K.segs[ix] is an SBasis object. I looked around in the code and there didn?t seem to have operator-() defined between Linear and SBasis object (but the expression worked, and Linear object is not an SBasis object).
I think it is automatically casting using SBasis(Linear)?
So I don?t know where to look further to see if there is a degree increase going on anywhere.
Let's get some numbers. I remember that there was also a bug in curvature toy where it would introduce a cusp as that was the easier way to satisfy the constraints. I think with some thought we could do better.\ (it might suffice to make the algorithm only consider the two straight through cases, or it might require some backtrack/DP). It would be brilliant if you could add the curvature based editing to inkscape. I tried to do it a long time ago but the canvas code was too much for my puny brain.
njh
On Tue, Apr 29, 2014 at 01:46:05AM -0400, Papoj Thamjaroenporn wrote:
Hi Nathan,
Thank you for the email. I am currently booked right now but I will get back to you some time this week to investigate more on this issue.
No hurry.
Just one question: what exactly should I print out? I printed a segment of the curvature path (the 4th segment to be exact) in terms of Kxy, and this segment definitely wiggled, but the output was always the same when I hovered my mouse around:
ix: 4 Kxy[0]: {281.25, 290.625}s^0 + ix: 4 Kxy[1]: {372.08, 346.521}s^0 + {-28.7083, -45.4316}s^1 + {-8.2712, -12.9363}s^2 + {1.31768, -0.797948}s^3 + {0.739784, 0.184223}s^4 +
If Kxy is indeed stable, the problem might lie in the method cairo_d2_sb()somewhere.
Ok, given this I agree with your assessment. The bit that is most suspicious is in sbasis-to-bezier starting from:
// calculate Bezier control arms
if (std::abs(xprime[1]*yprime[0] - yprime[1]*xprime[0]) > 1.e-5) { // general case : fit mid fxn value
that if statement in particular could explain the strange switching behaviour. So what you might do is either put a breakpoint in that cost, or stick a cout << ... in there.
The other likely candidate is the adaptive subdivider code: if(tail_error(B, 3) < tol || sbasis_size(B) == 2) { // nearly cubic enough
but that's been pretty well tested I think.
njh
participants (2)
-
Nathan Hurst -
Papoj Thamjaroenporn