remove_knot implementation bug

[portnov]

Describe the bug remove_knot() method returns a curve, which is geometrically different from original curve. According to description of this operation (see The NURBS Book, p.5.4), the resulting curve should be geometrically and parametrically identical to original one

To Reproduce

from math import sqrt

import geomdl
from geomdl import operations, BSpline

curve = BSpline.Curve()
curve.degree = 2
curve.ctrlpts = [[0, 0, 0], [1, 1, 0], [2, 0, 0]]
curve.knotvector = [0, 0, 0, 1, 1, 1]

ts = [0, 0.1, 0.3, 0.5, 0.7, 0.9, 1.0]

inserted = BSpline.Curve()
inserted.degree = curve.degree
inserted.ctrlpts = curve.ctrlpts
inserted.knotvector = curve.knotvector
inserted.insert_knot(0.5, num=1)

removed = BSpline.Curve()
removed.degree = inserted.degree
removed.ctrlpts = inserted.ctrlpts
removed.knotvector = inserted.knotvector
removed.remove_knot(0.5, num=1)

tolerance = 1e-5

def distance(pt1, pt2):
    x1, y1, z1 = pt1
    x2, y2, z2 = pt2

    return sqrt((x1-x2)**2 + (y1-y2)**2 + (z1-z2)**2)

print("Insertion:")
for t in ts:
    orig = curve.evaluate_single(t) 
    new = inserted.evaluate_single(t)
    print(f"T = {t}, orig = {orig}, new = {new}")
    if distance(orig, new) > tolerance:
        raise Exception("Too far")

print("Removal:")
for t in ts:
    orig = curve.evaluate_single(t) 
    new = removed.evaluate_single(t)
    print(f"T = {t}, orig = {orig}, new = {new}")
    if distance(orig, new) > tolerance:
        raise Exception("Too far")

Output:

Insertion:
T = 0, orig = [0.0, 0.0, 0.0], new = [0.0, 0.0, 0.0]
T = 0.1, orig = [0.2, 0.18000000000000002, 0.0], new = [0.20000000000000004, 0.18000000000000005, 0.0]
T = 0.3, orig = [0.6, 0.42, 0.0], new = [0.6, 0.41999999999999993, 0.0]
T = 0.5, orig = [1.0, 0.5, 0.0], new = [1.0, 0.5, 0.0]
T = 0.7, orig = [1.4, 0.42000000000000004, 0.0], new = [1.4, 0.42000000000000004, 0.0]
T = 0.9, orig = [1.8, 0.17999999999999997, 0.0], new = [1.8000000000000003, 0.18, 0.0]
T = 1.0, orig = [2.0, 0.0, 0.0], new = [2.0, 0.0, 0.0]
Removal:
T = 0, orig = [0.0, 0.0, 0.0], new = [0.0, 0.0, 0.0]
T = 0.1, orig = [0.2, 0.18000000000000002, 0.0], new = [0.29000000000000004, 0.09000000000000001, 0.0]
Traceback (most recent call last):
  File "/home/portnov/src/sverchok/test.py", line 49, in <module>
    raise Exception("Too far")
Exception: Too far

[orbingol]

According to the NURBS book, it is not always possible to remove a knot as the authors assume that num-th derivative must be continuous to remove num number of knots. Some researchers say that knot removal is possible as long as the knot exists in the knot vector but it is not always possible to get the same shape, i.e. it may change parametrically and geometrically. I think it would be a good idea to stick to the NURBS book in this case.

I see that I forgot to add a check to identify if the knot is removable or not. That specific check exists in the algorithm, p.186 of the NURBS book. It looks like I added that function 3 years ago with a note "needs testing" but I am guessing I forgot to test it :)

Thanks for the report @portnov.

[portnov]

In this particular test, I explicitly insert a knot and then try to remove it. Since I inserted the knot, I think it should be possible to remove it :)

[orbingol]

In this particular test, I explicitly insert a knot and then try to remove it. Since I inserted the knot, I think it should be possible to remove it :)

Yes, absolutely.

I see that I forgot to add a check to identify if the knot is removable or not. That specific check exists in the algorithm, p.186 of the NURBS book. It looks like I added that function 3 years ago with a note "needs testing" but I am guessing I forgot to test it :)

It looks like I was wrong here. The implementation of the algorithms is always a little bit different than the algorithms in the book and it leads to unintentional mistakes. Having said that, I think I found the error. @portnov, would you change helpers.py line 733 with

ctrlpts_new[j] = ctrlpts_new[k]   # line 733 of helpers.py

and test it again? I am guessing you have multiple cases to test :)

[portnov]

Ok, will test

[portnov]

The test case I posted in the description of this ticket is working now. With other cases I have, I'm not so sure: result is changing form, but not so badly as before. But then, I'm not so sure there that knots are removable.

How current implementation is supposed to work if the knot is not removable?

[orbingol]

@portnov you are right. For your specific case, if we want to remove knot = 0 instead of knot = 0.5, it shouldn't allow it. I've implemented a fix and it seems to be working fine for curves.

Before pushing the fix, I need to complete the following:

• [ ] Implement the fix for the surfaces and volumes
• [ ] Test dependent functionality (e.g. degree reduction)