Bug 47787 - B Spline interpolation is broken
Summary: B Spline interpolation is broken
Status: NEW
Alias: None
Product: LibreOffice
Classification: Unclassified
Component: Chart (show other bugs)
Version:
(earliest affected)
Master old -3.6
Hardware: Other All
: medium normal
Assignee: Not Assigned
URL:
Whiteboard:
Keywords:
: 57234 (view as bug list)
Depends on:
Blocks: Chart
  Show dependency treegraph
 
Reported: 2012-03-23 18:03 UTC by Markus Mohrhard
Modified: 2021-02-23 09:29 UTC (History)
4 users (show)

See Also:
Crash report or crash signature:


Attachments
File for experiments (21.93 KB, application/vnd.oasis.opendocument.spreadsheet)
2012-03-31 11:28 UTC, Regina Henschel
Details
B-spline chart that loops all around (60.02 KB, application/vnd.oasis.opendocument.spreadsheet)
2021-02-23 09:26 UTC, Emily Bowman
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Markus Mohrhard 2012-03-23 18:03:21 UTC
B Spline interpolation is broken for some documents.

Open the test document attached to Bug 47632 and switch to edit mode. Somewhere in Splines.cxx must be an error implementing the algorithm mentioned in ODF 1.2.
Comment 1 Markus Mohrhard 2012-03-24 13:20:00 UTC
Algorithm is implemented in chart2/source/view/charttypes/Splines.cxx
Comment 2 Markus Mohrhard 2012-03-30 19:51:59 UTC
This one is getting really nasty. I have more or less implemented the algorithm totally new and added unit tests but the algorithm results in memory corruption.

Have to spend some time on other calc bugs.
Comment 3 Regina Henschel 2012-03-31 11:28:30 UTC
Created attachment 59314 [details]
File for experiments

Hi Markus. I think, that the problem is caused by identical y-values. When you increase the x- or y-values step by step, you can notice, that the amplitude of the curves increases too. I tend to think, that this cannot be avoided, because B-Spline interpolation curves are parametric. I guess, that it is a property of this kind of interpolation.
When you agree to that and not find an error in the algorithm, I suggest, that we implement some functional interpolation. For those of cause the x-values have to be sorted as it has been in older versions of OOo. Perhaps we can discuss this on the Hackfest?
Comment 4 Markus Mohrhard 2012-03-31 21:34:16 UTC
Hey Regina,

I don't think that the B-Spline algorithm itself has a problem with identical y values. I fear more that one of our assumptions in the implementation is wrong.

I think I remember from my Numerical Math 2 lecture that there is no such limitation for B splines but I would need to check with my script.

I have now to fix some more calc bugs before I can come back to this problem but I will finally try to run this data through MATLAB and compare the result of each individual step with the MATLAB result.

I already did that for the creation of t and u with my reworked implementation and they were the same in matlab and in my implementation. I will try to get the splitted up implementation into master before the hackfest and hopefully the test data ready until then.

Sadly we are not free to implement another algorithm because ODF1.2 explicitly mentions this algorithm. Nevertheless if there is really a problem with the ODF algorithm we may talk to Kohei/Thorsten how to proceed.
Comment 5 Markus Mohrhard 2013-02-14 16:40:02 UTC
*** Bug 57234 has been marked as a duplicate of this bug. ***
Comment 6 Thomas Lendo 2017-06-17 12:32:23 UTC
Is there any development in working on this bug or should it be unassigned? Last comment is from 2012.
Comment 7 Xisco Faulí 2017-09-16 13:48:00 UTC
Dear developer,
This bug has been in ASSIGNED status for more than 3 months without any activity. Resetting it to NEW.
Please assigned it back to yourself if you're still working on this.
Comment 8 QA Administrators 2018-09-17 02:46:41 UTC Comment hidden (obsolete)
Comment 9 QA Administrators 2020-09-17 04:07:30 UTC Comment hidden (obsolete)
Comment 10 Emily Bowman 2021-02-23 09:26:41 UTC
Created attachment 169987 [details]
B-spline chart that loops all around
Comment 11 Emily Bowman 2021-02-23 09:29:08 UTC
This feature is obviously completely abandoned, despite being broken; I propose that it be deprecated, with text in the GUI to that effect (since it can't be outright removed due to being incorporated into the ODF spec, despite being completely broken then as now).

I just tried to switch to B-splines to eliminate the hilariously long overshoots in the cubic algorithm, and instead it gave me loop-de-loops. My experience working with B-spline interpolation in image resizing tells me this is not correct, but if you've already specified an incorrect algorithm, better to just deprecate it.