splines are not rendering all the control points

[renato-grottesi]

Hi,

I just noticed that when I make a drawing in LibreCAD and read it in CAMotics, only the first bit of the spline is rendered, so I started digging into dxf.tpl and found that it's not running the Catmull-Rom 2D on all the control points.
The quick hack below makes the shapes appear more or less in the right place, but there are some gaps.
I'll try to find some time to fix the spline rendering and submit a change :-)

--- dxf.tpl     2022-05-23 20:44:54.000000000 +0200
+++ dxf_orig.tpl        2022-05-23 19:43:01.000000000 +0200
@@ -382,31 +382,16 @@ module.exports = extend({
   },
 
 
-  spline_cut: function(s, zSafe, zCut, res) {
+  spline_cut: function(s, res) {
     if (typeof res == 'undefined') res = units() == METRIC ? 1 : 1 / 25.4;
 
     if (s.degree == 2) {
-      for(var seg=0; seg<s.ctrlPts.length; seg++)
-      {
-        var segment = [];
-        segment.push(s.ctrlPts[(s.ctrlPts.length+seg-1)%s.ctrlPts.length]);
-        segment.push(s.ctrlPts[(s.ctrlPts.length+seg+0)%s.ctrlPts.length]);
-        segment.push(s.ctrlPts[(s.ctrlPts.length+seg+1)%s.ctrlPts.length]);
-
-        var steps = Math.ceil(quad_bezier_length(segment) / res);
-        var delta = 1 / steps;
-
-        rapid({z: zSafe});
-        for (var i = 0; i < steps; i++) {
-          v = quad_bezier(segment, delta * (i + 1));
-          if(i<=0) {
-            rapid (v.x/2.0+segment[1].x/2.0, v.y/2.0+segment[1].y/2.0);
-            cut({z: zCut}); 
-          }
-          cut(v.x/2.0+segment[1].x/2.0, v.y/2.0+segment[1].y/2.0);
-        }
-        rapid({z: zSafe});
+      var steps = Math.ceil(quad_bezier_length(s.ctrlPts) / res);
+      var delta = 1 / steps;
 
+      for (var i = 0; i < steps; i++) {
+        v = quad_bezier(s.ctrlPts, delta * (i + 1));
+        cut(v.x, v.y);
       }
 
 
@@ -425,13 +410,13 @@ module.exports = extend({
   },
 
 
-  element_cut: function(e, zSafe, zCut, res) {
+  element_cut: function(e, res) {
     switch (e.type) {
     case _dxf.POINT:    return;
     case _dxf.LINE:     return this.line_cut(e);
     case _dxf.ARC:      return this.arc_cut(e);
     case _dxf.POLYLINE: return this.polyline_cut(e);
-    case _dxf.SPLINE:   return this.spline_cut(e, zSafe, zCut, res);
+    case _dxf.SPLINE:   return this.spline_cut(e, res);
     default: throw 'Unsupported DXF element type ' + e.type;
     }
   },
@@ -459,7 +444,7 @@ module.exports = extend({
       cut({z: zCut});
       cut(v.x, v.y);
 
-      this.element_cut(e, zSafe, zCut, res);
+      this.element_cut(e, res);
 
       layer.splice(match.i, 1);
     }

[jcoffland]

Can you attach or link to an example DXF file that shows the problem?

[renato-grottesi]

Hi,

Thanks for following up the case and many thanks for making CAMotics! I already used it to carve a pirate dagger for my son with his name on it and he was very happy! :-D
I attached a zip file with the dxf, the tpl, the diff above and 3 screenshots showing the LibreCAD rendering, the wrong CAMotics rendering and the almost correct CAMotics rendering: test_dxf.zip
The current spline_cut in dxf.tpl handles only quadratic splines with 3 control points and cubic splines with 4 point, but it doesn't cope with cubic or quadratic splines that have five or more control points (it does deal with long linear splines though).

[renato-grottesi]

I finally managed to get the rendering right in dxf_tpl.zip
I still don't understand why I need to divide the results of quad_bezier by 2 and add half of the second control point, but maybe there is some magic offsetting below the scene...
I'll try to create a merge request.

[renato-grottesi]

#367

[renato-grottesi]

Two things that I should fix are:

• I don't need to pass the zSafe to the spline_cut function
• The spline_cut function assumes closed splines, so I need to implement open splines and find a way to read an is_closed boolean from the dxf file

[renato-grottesi]

I removes the zSafe and identified what I need to do to access the spline flags that contain the closed flag, but I'll have to move development from iMac to Ubuntu since I don't want to go through the pain of installing XCode in my recreational computer 😄
Maybe I'll push the last change later today.

[jcoffland]

I started implementing some similar changes when you first opened this issue. I'll have to merge your changes with mine at some point.

[renato-grottesi]

In theory my change just misses adding the same point twice at the beginning and end of the segments split to create the open splines and understanding why that division by two is necessary, but if you want to implement it yourself, feel free to go for it!
I'm not in any position to code at a reliable pace with kids and all other kinds of distractions 🙂

[jcoffland]

I believe the rendering is wrong in the first place. The code treats the data as if it work a series of Bezier curves. But it's actually a B-spline which is something else. I think this is why the adjustment is needed. I've done some tests with the "stretching cat" demo and this new code does not work at all. "stretching cat" is made of of 3-degree B-splines. Previously it just connected the control points, which is pretty dumb but it worked in this case. I think we need to implement De Boor's algorithm to render the B-splines correctly.

There are many improvements that could be made to the DXF library. It was something I just whipped up to get a job done. I've been studying your changes. The help is much appreciated.

[renato-grottesi]

Ah! Thanks for the clarification! I implement a https://en.m.wikipedia.org/wiki/Cubic_Hermite_spline#Catmull%E2%80%93Rom_spline because I saw that it had to pass through the control points and because the bezier evaluators were already in place.
I can try the algorithm you suggested when I get some time.

[jcoffland]

Where did you get the idea to average the point computation result with the second control point. It seems to work but I don't understand why.

[renato-grottesi]

I started with a 3 points spline, rendering the p0-p1 and p1-p2 lines together with the spline and I noticed that it kind of looked twice as big compared to the LibreCAD rendering, so I halved the coordinates. Then it looked offsetted from p1 so I added p1, but then it went too much the other way, so I added half p1 instead and it looked exactly like in LibreCAD. So it was a dirty hack based on observation. It would indeed be good to understand why it's needed...
Maybe those knots are involved somehow? I tried to google what they are used for, but I haven't had time to dig further into it.

[renato-grottesi]

I read the Autodesk specs and the splines in dxf are NURBS: https://en.m.wikipedia.org/wiki/Non-uniform_rational_B-spline
That means that the current evaluation (and my way of choosing which control point to add to the segment array that is not using the knots vector) is wrong and should be reimplemented accordingly.
I can try to give it a try if you are busy with other parts of the development, but my spare time is very erratic :-)

[renato-grottesi]

I found something that should work: https://github.com/caadxyz/DeBoorAlgorithmNurbs/blob/master/src/DeBoorAlgorithmNurbs.py

It's the deBorr you mentioned above, but adapted to work with NURBS.

Porting it to the spline_cut function (removing the bezier functions and the special cases for cubic/quadratic) should be the right way to go 👍

And we indeed need to export the spline flags into the JavaScript code since it needs a couple of them.

[jcoffland]

Most of the DXF splines are uniform and non-rational. Uniform splines have equal spacing between knots and non-rational splines have no weights. All the examples, I have looked at are like this. However, it would be great to also implement rational and non-uniform splines. In order to do this, we need to also load the weights from the DXF, if there are any, and look at the other flags. As you noted before, there are closed and unclosed splines. In addition, there are periodic and non-periodic splines. I don't know if closed non-periodic splines are likely to occur in a DXF. I didn't understand most of this when I first wrote the code. I've been doing some reading.

Here's an possible implementation in Javascript: https://github.com/thibauts/b-spline/blob/master/index.js

[renato-grottesi]

I ported the javascript implementation that you pointed at in #367 and it works well (only assumes open nurbs for now).
I'll try to integrate the rest of functionality from that full python implementation above at some point.

[renato-grottesi]

Thanks for the code review!
I refactored the code to fix the bug you spotted, to make it more readable and I tried to implement a closed spline rendering, but the derivative around the initial point is not continue, so I'm missing some more changes. But I run out of time, so that's all for today :-)
About the flags: do you prefer to export them all as a single bitmask, or should the C++ interface create a separate boolean for each flag? I'm more keen on the second option...

[jcoffland]

About the flags: do you prefer to export them all as a single bitmask, or should the C++ interface create a separate boolean for each flag? I'm more keen on the second option...

Either way is fine by me.

[renato-grottesi]

After my last change to #367 it looks like closed nurbs can be rendered correctly. (sorry for hardcoding is_closed, but I still haven't had a chance to sit on my development linux workstation to try the C++ changes...)
I modified the code from yesterday according to https://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/B-spline/bspline-curve-closed.html to obtain the closed nurbs, however I am still not 100% convinced about discarding the knots vector and rewriting it from scratch only to obtain a closed nurbs. Probably there is a better way to reuse the data already in the knots vector...
Also, it looks like there is a small carved hole appearing before the rendering of the first spline in a layer that I'll have to figure out! :-D

[renato-grottesi]

Finally I managed to use my ubuntu machine :-)
I upload the C++ changes and tested that they work correctly.
I also verified that the strange hole that I experienced in my iMac is gone (I think it was fluke of that macOS build).
tplang can now render correctly both open and close 2D NURBs :-)
Next thing on my list is to optimize the code to prepare the knots and v array once before invoking the evaluation function to speed up execution.
Then I would like to understand if there is more work to do for the periodical nurbs and for the knots vector of the closed nurbs.

[jcoffland]

Awesome. Thanks for doing all that.

[renato-grottesi]

No problem! This was fun to implement :-)
I'm almost happy with the change, but I want to make sure that it can correctly render all the spline types from LibreCAD to the mm before calling it done (I'll try tonight with my ubuntu machine).
Do you have a coding_convention/linter/code_formatter that I should follow before committing the code?
I'm mostly a C/C++ programmer and I'm sure that I've done some cringy JavaScript errors here and there :-)

[jcoffland]

I have my own coding style which I should document. All of the C++ and Javascript code should already be in my style. So you can try to copy the other code. Otherwise, I'll just make a pass over it when your done to bring it in to compliance. So fix the style if you want to. I'll do a through code review when you're done. Awesome work!

One of the next big things I'd like to implemented, related to this DXF work, is to add an UI interface for opening DXF files and configuring the layers to be cut using different operations such as offsetting and pocketing. You would open a DXF file and get a list of its layers and/or it's polygons. Then for each one you could select the CAM operation and parameters such as which tool, the depth, offset amount, etc. This UI would just produce a bit of JSON data that a TPL program would read and execute the correct CAM operations. There would be a function like dxf.cam(json, dxf) that would do the grunt work. Any thoughts on this?

[renato-grottesi]

I committed the final optimization for splines rendering and I added the Z interpolation because, why not?

Then I created an unruly mess of shapes in LibreCAD and checked if they matched the CAMotics rendering. Splines worked well, opened or closed. Ellipses gave a warning about not being implemented (I can do that in another GitHub issues). However, when I added even a single polyline, the polyline was always rendered closed and it was messing the closed splines data. I then added one more commit to pass the isClosed flag of the polylines down to the json, but it looks like the flags won't appear in the json. It does appear with the correct value if I move it in the vertices list, inside the x,y,z dictionary :-|
I think there is something wrong with the sink usage, but I can't figure it out now because I need to sleep. Maybe you can spot the problem?

About opening the dxf files with a dialog, I think it's a great idea. I indeed almost discarded CAMotics as broken the first time I tried it because it didn't show me the dxf rendered when I tried to open it directly :-D Good thing that I later found out about the tpl files in another tutorial. I also like the idea of configuring each layer independently. My workflow is to have a layer with the figure's details and a layer with the figure's silhouette to cut it off of the plywood. I woul configure the tpl to do the details layer first in a single pass and then to cut the silhouette with multiple passes, depending on how deep the drillbit can cut and on how thick is the plywood.

[renato-grottesi]

I figured out the last bug after looking at a simpler example where I noticed that the control points are inverted when the bug happens: I forgot to modify the element_flips for splines and polylines :-)
I'll update a fix shortly.

[renato-grottesi]

Great, the last bug is fixed (it was actually 2 or 3 of them) and #367 is ready to merge after your code review!
Thanks for all the support in this issue :-)
I'll check with my employer if I can keep helping you with this project, so that all DXF primitives are rendered correctly.

[renato-grottesi]

Hi @jcoffland
I haven't got any feedback from the change. Is that something more you want me to do with it before merging?

[jcoffland]

I'll do this soon.

[jcoffland]

I haven't forgotten about this but I'm still trying to find time to review it.

[jcoffland]

I made a branch from your PR, added some of my own changes and then made a new PR. See #370. I reviewed my own PR. Please take a look at my review comments when you have a chance. I'm mostly happy with this code but I'm not convinced it's 100% yet. Regardless, it's way better than what we had.

[renato-grottesi]

Thanks for reviewing!
I'll try to find some time to address the comments and review your new PR :-)

[renato-grottesi]

I left some comments.
I am a bit busy with some personal matters these days, but maybe I can try to find some time to try those changes myself and let you know.