NURBs Curve Evaluation in Excel

Rhino Developer
, , , ,
1

I need a y = f(x) formula in Excel to estimate a value. The only way I could think of to accurately find the estimate is with a NURBs curve:

image
image1025×564 18 KB

There’s a lot of acceleration from 0 to 1, it’s flat out to 10, and slopes up gradually out to 100.

Degree 3 Curve
Knot Vector ( 7 knots )
  index                     value  mult       delta
      0                        0     3
      3                        1     1           1
      4                        2     3           1
  Control Points  5 non-rational points
    index               value
    CV[ 0] (0, 5, 0)
    CV[ 1] (0, 3, 0)
    CV[ 2] (1, 2, 0)
    CV[ 3] (10, 2, 0)
    CV[ 4] (100, 5, 0)
  1. Does anyone know of a native Excel function that can do something like this?
  2. If not, does anyone know how I can evaluate a NURBs curve to get the y at a given x?

I found a macro that will evaluate a curve, but it only works on the domain. I need to evaluate it in physical space to get the y for a specific x.

Option Explicit

Function BSpline(u, degree, CVs)
    ' computes the coordinate of a point on a B-spline
    ' u = indpendent parametric variable of the spline
    ' degree of the spline
    ' CVs = an array of the coordinates of the control vertices (x, or y, or z)
    ' L. Minardi  3/21/2019
    ' Reference https://en.wikipedia.org/wiki/B-spline
    Dim cPoints(20) As Double, numCPoints As Integer
    Dim i As Integer, j As Integer, k As Integer
    Dim c As Double
    Dim numKnots As Integer, knotMax As Integer
    Dim knots(20) As Double  ' array of knot values
    numCPoints = CVs.Count
    k = degree
    For j = 1 To numCPoints
        cPoints(j) = CVs(j)
    Next j
    numKnots = degree + numCPoints + 1
    Call KnotValues(degree, numKnots, knots, knotMax)
    If u > knotMax Or u < 0# Then
        BSpline = "Error, u is outside range of 0 to " & knotMax
    Else
        If u = knots(numKnots) Then
            c = cPoints(numCPoints)
        Else
            '  compute i based on index of u
            For j = 1 To numKnots
                If u < knots(j) Then
                    i = j - 1
                    j = numKnots + 1
                End If
            Next j
            c = deBoor(k, degree, i, u, knots, cPoints)
        End If
        BSpline = c
    End If
End Function

Function deBoor(k, degree, i, u, knots, cPoints) As Double
    'deBoor recursive algorithm
    ' k = index. initial value = degree
    ' i = index indicating maximum knot number where u < knot value
    ' u = indpendent parametric variable
    ' knots = array of knot values
    ' cPoints = one dimensional array of control point coordinates
    ' reference https://en.wikipedia.org/wiki/De_Boor%27s_algorithm
    Dim alpha As Double
    If k = 0 Then
         deBoor = cPoints(i)
    Else
         alpha = (u - knots(i)) / (knots(i + degree + 1 - k) - knots(i))
         deBoor = deBoor(k - 1, degree, i - 1, u, knots, cPoints) * (1 - alpha) + _
         deBoor(k - 1, degree, i, u, knots, cPoints) * alpha
    End If
End Function

Sub KnotValues(degree, numKnots, knots, knotMax)
    ' set knot values for uniform B-spline
    Dim j As Integer, KnotValue As Integer
    KnotValue = 0
    ' set to 0 for initial (degree + 1) knots
    For j = 1 To degree + 1
        knots(j) = KnotValue
    Next j
    KnotValue = KnotValue + 1
    ' increment knot value for successive knots
    ' up to (degree -1)
    For j = degree + 2 To (numKnots - degree - 1)
        knots(j) = KnotValue
        KnotValue = KnotValue + 1
    Next j
    ' set to last value for last (degree + 1) knots
    For j = numKnots - degree To numKnots
        knots(j) = KnotValue
    Next j
    knotMax = KnotValue
End Sub
2

You should be able to use Rhino3dm inside of Excel to access functions like this.

3

I’m helping someone with this. Their users aren’t going to have Rhino. The only way I could see to fit their data is with NURBs.

Right now, they’ve got it chopped into a series of linear curves. I manually fit their data by tracing it in Rhino.

4

Rhino3dm is free and doesn’t require Rhino

5

Ok, yeah, then it’s just a deployment problem.

I’m just surprised that Excel doesn’t have a way to do this. I keep finding things that almost work. Like this Lambda library has a function to evaluate a spline at x, but the only way I can see to create a spline is via interpolation.

6

Binary search for the curve parameter that produces the target x.

1 Like
7

I detest VBA, but I got something working with @spb 's recommendation.

I’ve got a much better understanding of how deBoors works now, but I’m not clear on a couple of things. The knot vector needed an extra multiple on the endpoints. That threw me for a couple of days. Also, I think the knot vector is supposed to scale with the spline length? The only time I see Rhino create a [0,0,0,1,2,2,2] knot vector is with curve through poly.

Here’s the relevant code snippet in case anyone else wants to manually fit a curve in Rhino and use the CVs in Excel.


Private Function CalcKnots(Degree As Integer, cvX() As Double, cvY() As Double) As Double()
    
    Dim cvLen As Integer, spans As Integer, knotLen As Integer, i As Integer
    Dim xyDistance As Double, knotDelta As Double, acc As Double
    
    cvLen = UBound(cvX) + 1
    spans = cvLen - Degree
    
    ' not sure why ends have to be terminated with degree + 1 knot multiples instead of just degree multiples
    knotLen = Degree + cvLen + 1
    Dim knots() As Double
    ReDim knots(knotLen - 1)

    ' I think it's best practice to scale the knot vector with the spline length instead of using
    ' something like 0,0,0,1,2,2,2.  I'm going with a rough approximation: the distance between endpoints.
    ' As such, it's not worth adding a sqrt to get the hypotenuse. This is the x distance plus the y distance.
    xyDistance = Abs((cvX(cvLen - 1) - cvX(0))) + Abs((cvY(cvLen - 1) - cvY(0)))
    knotDelta = xyDistance / (spans)
    acc = knotDelta
    
    For i = 0 To Degree
        knots(i) = 0
    Next i
    
    For i = Degree + 1 To Degree + spans - 1
        knots(i) = acc
        acc = acc + knotDelta
    Next i
    
    For i = Degree + spans To knotLen - 1
        knots(i) = acc
    Next i
    
    CalcKnots = knots
    
End Function

Private Function findKnotSpan(t As Double, knots() As Double) As Integer
    ' find knot span index Tk, where Tk < t < Tk+1
    Dim k As Integer
    For k = 0 To UBound(knots)
        If t < knots(k) Then
            findKnotSpan = k - 1
            Exit Function
        End If
    Next k
End Function

Public Function deBoor(idx As Integer, Degree As Integer, Tk As Integer, t As Double, knots() As Double, cvX() As Double) As Double
    ' idx = recursion index, initially the degree
    ' Tk = knot span index, where Tk < t < Tk+1
    ' t = domain parameter
    ' knots = array of knot values
    ' cvX = array of 1d control points
    
    Dim alpha As Double, left As Double, right As Double
    If idx = 0 Then
        deBoor = cvX(Tk)
    Else
        alpha = (t - knots(Tk)) / (knots(Tk + Degree + 1 - idx) - knots(Tk))
        left = deBoor(idx - 1, Degree, Tk - 1, t, knots, cvX) * (1 - alpha)
        right = deBoor(idx - 1, Degree, Tk, t, knots, cvX) * alpha
        deBoor = left + right
    End If
End Function

Private Function binSearchDeBoor(Degree As Integer, TargetValue As Double, Tolerance As Double, knots() As Double, cvX() As Double) As Double
    Dim knotsLen As Integer, Tk As Integer
    knotsLen = UBound(knots) + 1
    
    Dim delta As Double, dMin As Double, dMax As Double, t As Double, tMin As Double, tMax As Double
    dMin = 0 - Tolerance
    dMax = 0 + Tolerance
    tMin = 0
    tMax = knots(knotsLen - 1)
    t = tMax / 2
    
    Do
        Tk = findKnotSpan(t, knots)
        delta = deBoor(Degree, Degree, Tk, t, knots, cvX) - TargetValue
        Select Case delta
            Case Is < dMin
                tMin = t
                t = tMin + ((tMax - tMin) / 2)
            Case Is > dMax
                tMax = t
                t = tMin + ((tMax - tMin) / 2)
            Case Else
                binSearchDeBoor = t
                Exit Function
        End Select
    Loop
End Function

Public Function EvalSpline(TargetValue As Double, Tolerance As Double, SearchRange, ResultRange, Degree As Integer) As Double
    If SearchRange.Count <> ResultRange.Count Then
        Err.Raise vbObjectError + 1000, "EvalSpline", "Both ranges must be the same length"
    End If
    Dim rangeLen As Integer
    rangeLen = SearchRange.Count
    Dim cvS() As Double
    Dim cvR() As Double
    ReDim cvS(rangeLen - 1)
    ReDim cvR(rangeLen - 1)
    For i = 0 To rangeLen - 1
        cvS(i) = SearchRange(i + 1)
        cvR(i) = ResultRange(i + 1)
    Next i
    
    Dim knots() As Double
    knots = CalcKnots(Degree, cvS, cvR)
    
    Dim t As Double, Tk As Integer
    t = binSearchDeBoor(Degree, TargetValue, Tolerance, knots, cvS)
    Tk = findKnotSpan(t, knots)
    EvalSpline = deBoor(Degree, Degree, Tk, t, knots, cvR)
    
End Function
8

The extra points at the end points are a method for simplifying the algorith to eliminate the need for special treatment near the ends. Note that the deBoor algorithm is a method for calculating the value of a NURBS curve. It is not a general defintion of a NURBS curve.

If the finite precision of digital math is not relevant then scaling the knot vector does not change the result of calculating a point on a NURBS curve, as long as the parameter value used as input to the calculations is also scaled. Same for the applying an offset to the knot vector.

The “rule” about scaling the knot vector with the spline length is sometimes considered a good practise to minimize problems due to the finite precision of digital math, but is not a requirement.

1 Like