Let's talk about splines!

Jul 2, 2014 at 3:41 PM
So to the best of my knowledge, Net DXF currently does not have a spline elevator. I am a mathematician and I know a thing or two about splines and I am interested in writing an elevator to enhance my software. I would be happy to share the code!

I scanned the forum for info about splines but only found one answered thread about it.

Do we know what type of splines are used? Are all the parameters and information for the spline being read into the Net DXF spline object?
Coordinator
Jul 3, 2014 at 5:27 PM
I don't really know what you mean by a spline elevator. Bear in mind that, netDxf is only a library to read and write dxf files, so the Spline class is just a container to hold the essential information needed to read and write the dxf Spline entity. It is not intended to be a library for geometric operations, but I always wanted to write a library with them to calculate intersections, distances, interpolations,... I do not know how many times I wrote the code to calculate the intersection between two lines. It would be something similar to the Mathematics library of the WildMagic engine, even a direct translation to C# would be great. If you can read C++ take a look at the code, it is open source and easy to follow; you might even find what you are looking for.

About your questions, the Spline entity represents a nurbs curve, and the library only reads the essential information needed to build the curve. The dxf also includes information about what is called fit points, inside AutoCad there are two methods to create Splines through the classical Nurbs definition with control points, and by points through which the curve passes called fit points. In any case, AutoCad is not a good representation of a good program to work with nurbs, or any other kind of curves besides circunferences.

If you have a more complete implementation of a class to handle nurbs curves, I would love to take a look at it, I might borrow some code. It would be great to include both Splines representations: control and fit points that the dxf includes.

Daniel
Jul 24, 2014 at 5:21 PM
Edited Jul 24, 2014 at 7:55 PM
Hello Haplokuon, and thank you for your response! Sorry for my delay in responding, I have been quite busy with my own software development.

Your library features functions to convert most primitives into a set of points. I can't remember the names off the top of my head but it takes a parameter indicating how many points you want to decompose the arc/polyline/ellipse into. But this function is missing for splines. What I would like to do (If I can pull it off) is add this function to your library (or at least give you the code so you can put it where you want it). So by 'evaluator' I mean a function to take the spline description and produce actual points on the curve.

NURBS huh.. so you say " inside AutoCad there are two methods to create Splines through the classical Nurbs definition with control points, and by points through which the curve passes called fit points. In any case, AutoCad is not a good representation of a good program to work with nurbs, or any other kind of curves besides circunferences."

So (Just to confirm) AutoDesk 100% follows classical Nurbs theory as far as you know? I did a massive investigation into one of AutoDesks other file formats (FBX) and one thing I know about them is they like to make up a lot of their own stuff and not bother to document it.

You also say there are 2 functions. You mentioned "It would be great to include both Splines representations: control and fit points that the DXF includes. ". I believe the classic NURBS formulas are based on control points, but I don't know what applies when using fit points. Can you point me towards any literature on this? The classic formula looks like it would be fairly straight forward to implement.

Thanks! :)

-Michael
Coordinator
Jul 27, 2014 at 5:59 PM
Edited Jul 27, 2014 at 7:12 PM
My two main sources of information is the dxf documentation, and the actual AutoCad user's guide, since the dxf is a representation of the actual drawing database you will find more information in how the AutoCad works than the dxf documentation, that just describes the code-value pairs, but not much on what does values represents. This documentation is online at: AutoCad 2015 help.

This is what the AutoCad documentation says about splines: "These curves are technically called nonuniform rational B-splines (NURBS), but are referred to as splines for simplicity." So, the should follow the classical Nurbs theory. Working with curves has never been AutoCad strongest point, something that is getting better with newer versions, so limitations might appear with older ones. For example this is a note that appears in the AutoCad 2013 user's guide when talking about "Trim, Extend, and Fillet Splines": "Because periodic curves and surfaces are not currently supported, the objects may kink if they are reshaped." However, I haven't found this same note in the AutoCad 2015 user's guide.

There is no problem in decomposing a spline in a set of points, I already have one but I didn't have the time to clean it up to include it in the project, and since there is plenty of literature for anyone interested about it I didn't bother to finish it. My problem is the other way around, I have a set of points (fit points) and I want to create a spline that passes through them. When AutoCad generate this kind of curves, it limits them to cubic splines and gives you three choices to parametrize the knot vector: Chord (chord-length method), Square root (centripetal method), and Uniform (equidistant method). There are lots of information about curves in the Wildmagic engine but didn't have much time to study them and my knowledge on nurbs is limited.

Daniel
Jul 27, 2014 at 10:24 PM
"There is no problem in decomposing a spline in a set of points, I already have one but I didn't have the time to clean it up to include it in the project, and since there is plenty of literature for anyone interested about it I didn't bother to finish it. My problem is the other way around, I have a set of points (fit points) and I want to create a spline that passes through them."

So if I'm understanding you correctly - if I just want to read a spline in an existing DXF document then there is only one way to go about it - the standard NURBS theory can be used to evaluate it just fine. But you are looking for some sort of solution to create a spline using a set of points it should pass through. Correct?

I wonder if I could help you with this. I am going to do a little research on the matter.

Btw, as for the previous matter, would you be willing to share with me the (un-cleaned up) code you use to evaluate splines?

-Michael
Jul 28, 2014 at 5:18 PM
Edited Jul 28, 2014 at 6:36 PM
Here is a brief analysis...

Referring to Wikipedia's formula:
http://en.wikipedia.org/wiki/Non-uniform_rational_B-spline

The general nurbs evaluation function is as follows:

C(u) = sum (from i = 1 to k) R_iN(u) P_i

where k is the number of control points and N is the degree of the nurb.(R is defined in the wikipedia article in terms of B-spline basis functions). We can ignore N for the purpose of this discussion.

Suppose we are given k values of u: (u1, u2, ..., u_k) and we have k fit points (F1,F2, ..., Fk).

We want to find control points (P1,P2, ...,Pk) such that C(u_j) = F_j.


Define A_i,j = R_iN(u_j). Then it follows from our nurbs formula that:

C(u_j) = sum(i = 1 to k) (A_i,j) P_i


So A is now a k x k matrix.


We want

sum(i = 1 to k) (A_i,j) P_i = F_j

This is really a set of k equations. One for each value of j. We can describe these k equations in one with the matrix equation:

A * P = F

where A is the matrix described above, P is matrix who's rows are your control points, and F is a matrix who's rows are your fit points.

Solving gives:

P = MatrixInverse(A)*F.

There is the question of if the matrix will be invertable. It is very very rare that real valued matrices are not invertible and if one of them was, you could provide user feedback that they need to change one of the knot values.

I don't know if you have any matrix inversion routines but since its a square matrix you could use something like Cramer's Rule for example.

So here's a summary of how you could go about it.
  1. Choose your k fit points
  2. Choose your knot vector (this must have at least k plus 1 knot values).
  3. Determine the degree N of your NURB using N = (Number of Knots) - (Number of Control Points) - 1.
  4. Choose your k values of u that fall within your knot vector values.
  5. Construct your F matrix where the i'th row is the i'th fit point.
  6. Compute your A matrix using A_i,j = R_iN(u_j)
  7. Compute A_Inverse
  8. Compute the matrix product A_inverse*F
  9. The i'th row in the resulting matrix in (6) is the i'th control point
This was just a preliminary analysis so if you find any flaws in it let me know but I'm pretty sure this is an accurate analysis. If this is what you are looking for I may be able to write some code for this. But it would be useful for me to know what Matrix libraries or routines you have available.

-Michael
Coordinator
Jul 28, 2014 at 6:50 PM
Thank you for the info, I will try to find time to take a look at it. If you want to try to build a method for that, I am all open, basically the only information the user needs to provide is a set of points, if the spline is closed, and the knot parametrization method. I am raising this question because the dxf includes all this information: the control points, the knot vector, the fit points, several tolerances, and a few other things. Although all that information is included it is enough with the degree, the control points and the knot vector.

About the nurbs evaluator, if you go back to commit, number 79902, of the project you will find the last change of a file called "NurbsCurve.cs", this file does not exists in the current version. Inside that class, there is a method called PolygonalVertexes() to convert a nurbs to a set of points. This code is very old, might or might not work, and perhaps I was too optimistic when I said it was unclean, it is kind of unfinished. It was limited to 2d splines and looking at the code I am worried that it didn't work for periodic splines.

Daniel
Aug 4, 2014 at 4:49 PM
"It was limited to 2d splines and looking at the code I am worried that it didn't work for periodic splines. "

Can you explain more what you mean by periodic splines? I know what periodic means I just don't know what you mean in this context.

Is there a different evaluation formula needed for closed splines or the 'periodic' splines you mentioned?

-Michael
Coordinator
Aug 5, 2014 at 2:02 AM
Edited Aug 5, 2014 at 2:20 AM
Perhaps I am not being too precise when talking about the mathematics behind the nurbs curves. When I say a spline is periodic I am also implying that it is also closed.

Let's imagine we have a 3rd degree nurbs curve made of n control vertexes, if we just close the curve making V0=Vn, we will get a closed non periodic curve with C0 continuity; but to make a truly continuous curve we need to achieve C2 continuity at the end points, this is what I am referring to as a closed periodic curve. In this case, for this 3rd degree curve, we need to add three additional control points, for a total of n control points + spline degree, making V0=Vn+3, V1=Vn+2, and V2=Vn+1.

If you take a look at the netDxf Spline constructor, you will see that I am duplicating control points if you want to make the spline periodic. In those cases, I am also implying that you want to make the curve closed and continuous; if you want to make it closed but not continuous at the end points just duplicate the last control point and pass false to the "periodic" parameter.

When evaluating the curve to convert it to a set of points, and in the case of closed periodic splines, we only need to compute, in the example shown earlier, n control points and not the full n+3 list.

When in doubt the library code might clarify how I am using those terms, but do not hesitate to correct me if I am misusing them.

I have been messing again with the dxf splines. The full spline description includes both control points plus knots, and fit points with start and end tangents representations, but we can choose to write one or the other, or both, to make it work. At the moment the netDxf spline entity is only writing the control points and the knot vector representation.

I got my hands in the book, probably you hear about it, "The NURBS Book" by Les Piegl and Wayne Tiller, really good stuff in there, even it shows the solution for the problem in hand, cubic spline curve interpolation, since AutoCad limits the degree of the splines generated by fit points to three.

Daniel

At the moment, and in the next few weeks I will not have time to dedicate to the library, and neither to this nurbs mumbo jumbo, so things will go pretty slow for a while.
Aug 12, 2014 at 5:39 PM
No worries! I am stoked just from the fact that we're having this discussion. Being able to open and read splines will increase the value of my software tremendously! :D

I intend to write my own NURBS evaluator at some point in the next couple weeks, so I'll post about it here for others to see and for the sake of discussion.

-Michael
Aug 17, 2014 at 3:24 AM
Edited Aug 17, 2014 at 3:32 AM
Very excited to have my first NURBS evaluator up and running! :) And in less than 100 lines of code! I have a question or two for you, Daniel. The root function is SplineToPolyLine.

Results! A comparison between the original curve created in DraftSight, and loading it into my application using NetDXF and the function above.

Image

Works like a charm! :)

Daniel, I am still slightly confused about your earlier advice. To be clear, I am (at the moment) trying to write a complete and robust function that converts a DXF Spline to a list of vertices on the curve (in other words, plot the curve, not talking about control points). In my code above I am going about this by producing a LwPolyLine. Your description for handling periodic splines seems to describe the constraints that are necessary for CHOOSING the control points, rather than reading a curve with given control points. Therefore I am confused that you are bringing this up in the context of evaluation (by 'evaluation' I again mean plotting the resulting curve).

Are you saying that, if the curve is periodic, NetDXF will (As a memory optimization) leave off several duplicated control points from the spline object, and I would need to restore them (by copying appropriate vertices) before evaluating the curve? Your earlier post seems to suggest that your spline constructor handles the duplication of vertices. So I am really confused that you said you were concerned your spline evaluator does not "handle" periodic splines.
Coordinator
Aug 18, 2014 at 5:58 PM
Edited Aug 18, 2014 at 6:09 PM
Great, keep me updated. I will add your evaluator to the project once it is finish.

And now about your questions.
  1. I am duplicating the control points and creating the knot vector when building a closed periodic spline. The duplicated control points are saved together with the rest of them, it would be just silly not doing so just to save that little bit of memory, when the spline might contains hundreds or even thousands.
  2. When I was saying that my old evaluator might not work with closed periodic splines, I was just worried about that, since duplicating the control points is like overlapping the spline at the end points, the evaluator might also duplicate the points at those overlapped ends.
Keep in mind that it was a long time ago, and now I barely remember what I was doing. So, take my words about nurbs curves with a grain of salt I might be imprecise, confused or just plainly wrong. Do what you think is right and we will see how it works.

Daniel
Feb 16, 2015 at 1:35 PM
Hi,

I try to use your code for drawing a DXF Spline and I noticed, that there should be an easy optimization:
        private static Vector3 C(double u)
        {
            Vector3 vectorSum = new Vector3(0,0,0);
            double denominatorSum = 0;

            for (int j = 0; j < numControlPoints; j++)
                denominatorSum += __N(j, Degree, u)__ * Weights[j];
            
            for (int i =0; i < numControlPoints; i++)
                vectorSum += (Weights[i]*__N(i,Degree,u))__ * ControlPoints[i];

            return (1.0/denominatorSum) * vectorSum;
        }
can be simplified to:
        private Vector3 C(double u)
        {
            Vector3 vectorSum = new Vector3(0, 0, 0);
            double denominatorSum = 0;

            for (int j = 0; j < numControlPoints; j++)
            {
                double n = N(j, Degree, u);
                denominatorSum +=                         n * Weights[j];
                vectorSum += (Weights[j] * n) * ControlPoints[j];
            }
           
            return (1.0 / denominatorSum) * vectorSum;
        }
By doing this you can even avoid the usage of the dictionary (N_cache) as the lookup of values is also cost intensive.

This should cut down the CPU time by more than 50%.

Cheers Thomas
Coordinator
Feb 17, 2015 at 5:50 PM
Yes, nice suggestion. I add the modification for the next code update to avoid the use of the cache dictionary, it is a lot faster now. The method "N" also needs to be updated to delete the use of the cache.

Looking back at the code, the cache seems unnecessary, not only because what you suggest, but also because of the original purpose of the method "private double N(int i, int p, double u)". The cache stores the values calculated by that method, but the parameter "i" is the control point counter, and the recursive call of N modifies the parameter "p". When calculating "leftCoefficientthis.N(i, p - 1, u) + rightCoefficientthis.N(i + 1, p - 1, u)" is where the cache might be useful, but it seems that the use of it does not overcome the cost of looking up the table, nullifying its original purpose.

Daniel