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