What algorithms of polynomial interpolation drive Rhino rebuild function?


(Guziko1944) #1

Hello,

I have quite a specific question. I am wondering what mathematical rules apply to the function of ‘Rebuild’.

I mean let’s say I have a polyline with 200 vertices. Now using ‘Rebuild’ I go down to 50 control points to build a curve. Is there any specific polynomial interpolation that rules this function like Lagrange or something?

Thanks in advance,

Kuba


(Tom) #2

Usually such commands don’t fit in such simplistic mathematical functions, like ‘Lagrange-’ or ‘Newton Interpolation’. Since Rhino is based on NURBs, these algorithms are much more complex. Rebuild is not based on Interpolation, its rather based on Approximation/Fitting.

The _Rebuild command changes the control point count with the premise of equally spacing the control points. If you want to change the controlpoint count without moving the shape you rather should use _ChangeDegree which does degree reduction or degree increasing and as such its also changing amount of control points. From a mathematical standpoint degree elevation is trivial, degree reduction is not. Rhino actually lacks a good approximation algorithm in terms of explicit control on control point count, distribution and smoothing. But using the _Fit algorithm may be sufficient for most cases. Hope this helps. Further reading: “The NURBs book”

Many Approximation algorithms (also for NURBSs) are based on “Least Square” methods (regression)


#3

@dale, @dalelear: Comments?


(Guziko1944) #4

Thanks for your answer. This is really helpful. However, I am still waiting for some more specific information. Or is it classified in terms of intelectual property? Would be glad for some example equations. I need it for educational purposes as I am working on spatial data generalisation for cartographic purposes.

Looking forward to Your answers!

Kuba


(Tom) #5

Well in addition to that. I haven’t written the Rhino function so I’m not sure how its exactly made. There is a possibility that its just made of some sort of de boor in reverse algorithm, which is special case interpolation. Could be that its none of all. I mean the rebuilt shape diverges from the original one.

However the Nurbsbook contains more then 4 approaches if I remember correctly.The learning curve is quite steep. I think impossible to explain that here. Thats why I‘m pointing to that book. You can also check OpenNurbs for the Rebuild command. If its part of it, you can just use that command. What are you trying to do?


(Guziko1944) #6

As I said before I am working on spatial data generalisation for cartographic purposes. So basically with vector data representing roads and paths. In order to make them 3D-printable I have to change their appearance from polylines into curves (as polylines make the geometri for 3D printers too complicated quite surprisingly).

I would like to analyze how the ‘rebuild’ function parameters impact maximum deviations in terms of shape while transforming from polyline into curve. But to do that properly I would like to know more about mathematic aspects of this operation.


(Tom) #7

You are describing a process similar to Mesh to Nurbs conversion, just one dimension lower.
This is problematic and non-trivial, because you are missing important information. A discrete representation does not mathematically describe a shape. One reason why serious engineering is done in Nurbs, not with Meshes/Polylines.

So how would you solve that problem? Well you would rebuild that shape manually. You decide the curve layout and the properties of each curve. This requires an iterative workflow and experience. Reverse engineering a shape is difficult, and a very common job description.

You can automate such tasks to a certain degree, but its a trade-off. There is no perfect algorithm, none of them are easy to implement.

I showed you 4 mathematical tools in doing so:
* approximation -> least square
* approximation -> iterative guessing
* interpolation -> de Boor algorithm in reverse
* degree lowering (perfect for single span representations, unsuited for you)

Applying Least Square approximation is the usual mathematic approach in fitting a shape and a central part of the regression analysis. Rhino offers this with _FitCrv.
The problem, you work with Nurbs which makes it difficult to implement that for yourself. If you don’t know what Nurbs are, then learn about it first.
I showed a book where this is all explained.

The _rebuild command is unsuited because it diverges strongly, doesn’t hold the continuity between multiple curves and it has a complete different purpose. The _rebuild command is used to in-/decrease controlpoint count, equally distribute them and as such to smooth out a shape.


(David Cockey) #8

Investigate the Patch command if you need to fit a simpler surface to a complex surface, mesh, network of curves/polylines or points. (If you are starting with a NURBS surface you will need to convert it to a mesh or create a set of points on the surface before using Patch.) https://docs.mcneel.com/rhino/6/help/en-us/index.htm#commands/patch.htm?Highlight=patch Patch allows direct control of the complexity of the resulting surface, and also allows use of a user supplied “starting surface” which is deformed to fit the input data. I use Patch as a primary curve for converting point clouds of boat surfaces to NURBS surfaces. Unfortunately Patch does not work for fitting a curve to input data.