Menu
▾
▴
|
From: Tavmjong B. <tav...@fr...> - 2016-12-01 06:52:20
|
Hi Alexander, Looks interesting. As you are proposing this as an addition to lib2geom, the proper place to discuss this is on the lib2geom-devel list (lib2geom is a semi- independent project): lib...@li... Tav > Hi, > > I added a curve fitting algorithm to 2geom which takes a std::vector > of > Geom::Point and fits a Geom::CubicBezier to the points. > > It fits (non-degenerate) cubic bezier curves to given points within > half > a millisecond up to an error of 1e-9. > > You can find it here: > https://github.com/abrock/lib2geom > > In src/test/bezier-fit-test.cpp I made three simple tests, > one "normal" curve and two (nearly) degenerate curves with (nearly) > colinear points. > I create a Cubic Bezier, select 20 points and give these to the > fitting > function (which doesn't know the original curve). > > Results: > > Normal Curve: > Speed: 2678 curves per second > Worst error: 1.31799e-10 at t=0.736842 > > Degenerate Curve: > New method: 1567.89 curves per second > Worst error: 6.84045e-09 at t=0.110945 > > Nearly degenerate curve: > New method: 534.738 curves per second > Worst error: 0.0284499 at t=0.0958247 > > in src/2geom/bezier-utils.cpp are the new functions: > > - fit_bezier sets up the nonlinear least squares problem > > Helper functions: > - bezierfit_f calculates residuals > - bezierfit_df calculates derivatives of residuals > - bezier_distance helps calculating derivatives, it mainly contains a > templated evaluation of Cubic Bezier functions. > > src/2geom/jet.h contains the implementation of dual numbers I copied > from the Ceres source code > > Best Regards, > Alexander > > ------------------------------------------------------------------- > ----------- > _______________________________________________ > Inkscape-devel mailing list > Ink...@li... > https://lists.sourceforge.net/lists/listinfo/inkscape-devel |
|
From: Nathan H. <nj...@nj...> - 2016-12-01 10:37:48
|
If we can just constrain the code licence to match the 2geom one, I think everything is fine, otherwise I guess we could include separate licencing for just this piece of code. I'm happy to do a code review if you remind me in a few weeks. njh On Thu, Dec 01, 2016 at 07:52:06AM +0100, Tavmjong Bah wrote: > > Hi Alexander, > > Looks interesting. > > As you are proposing this as an addition to lib2geom, the proper place > to discuss this is on the lib2geom-devel list (lib2geom is a semi- > independent project): > > lib...@li... > > Tav > > > > Hi, > > > > I added a curve fitting algorithm to 2geom which takes a std::vector > > of > > Geom::Point and fits a Geom::CubicBezier to the points. > > > > It fits (non-degenerate) cubic bezier curves to given points within > > half > > a millisecond up to an error of 1e-9. > > > > You can find it here: > > https://github.com/abrock/lib2geom > > > > In src/test/bezier-fit-test.cpp I made three simple tests, > > one "normal" curve and two (nearly) degenerate curves with (nearly) > > colinear points. > > I create a Cubic Bezier, select 20 points and give these to the > > fitting > > function (which doesn't know the original curve). > > > > Results: > > > > Normal Curve: > > Speed: 2678 curves per second > > Worst error: 1.31799e-10 at t=0.736842 > > > > Degenerate Curve: > > New method: 1567.89 curves per second > > Worst error: 6.84045e-09 at t=0.110945 > > > > Nearly degenerate curve: > > New method: 534.738 curves per second > > Worst error: 0.0284499 at t=0.0958247 > > > > in src/2geom/bezier-utils.cpp are the new functions: > > > > - fit_bezier sets up the nonlinear least squares problem > > > > Helper functions: > > - bezierfit_f calculates residuals > > - bezierfit_df calculates derivatives of residuals > > - bezier_distance helps calculating derivatives, it mainly contains a > > templated evaluation of Cubic Bezier functions. > > > > src/2geom/jet.h contains the implementation of dual numbers I copied > > from the Ceres source code > > > > Best Regards, > > Alexander > > > > ------------------------------------------------------------------- > > ----------- > > _______________________________________________ > > Inkscape-devel mailing list > > Ink...@li... > > https://lists.sourceforge.net/lists/listinfo/inkscape-devel > > ------------------------------------------------------------------------------ > _______________________________________________ > Inkscape-devel mailing list > Ink...@li... > https://lists.sourceforge.net/lists/listinfo/inkscape-devel |
|
From: Alexander B. <ale...@lu...> - 2016-12-04 23:08:10
|
On 12/01/2016 11:12 AM, Nathan Hurst wrote: > If we can just constrain the code licence to match the 2geom one, I > think everything is fine, otherwise I guess we could include separate > licencing for just this piece of code. The file jet.h itself contains the license: // Redistribution and use in source and binary forms, with or without // modification, are permitted provided that the following conditions are met: // // * Redistributions of source code must retain the above copyright notice, // this list of conditions and the following disclaimer. // * Redistributions in binary form must reproduce the above copyright notice, // this list of conditions and the following disclaimer in the documentation // and/or other materials provided with the distribution. // * Neither the name of Google Inc. nor the names of its contributors may be // used to endorse or promote products derived from this software without // specific prior written permission. I think it's fine to just include the modified file in lib2geom. > I'm happy to do a code review if you remind me in a few weeks. Thank you, I will. Best Regards, Alexander |
|
From: Alexander B. <ale...@lu...> - 2016-12-04 20:58:22
|
Hi, I made a little toy which shows different methods for fitting a single cubic bezier curve to a set of points. You can play with it by moving the control points of a cubic bezier, the toy then selects an adjustable number of points on the curve and attemps different methods for fitting bezier curves to them. https://github.com/abrock/lib2geom The toy is in src/toys/bezier-fit.cpp, curve fitting code is in src/tests/bezierfit.h and src/tests/bezierfit-a.h (newer version, I keep the old version for comparison to avoid regressions) Best Regards, Alexander |
