(SDK) what is equivalent to mxs nearestpathparam?


#1

I can but i don’t really want to calculate a closest pathparam of bezier curve to a specified 3d point.
in mxs the nearestpathparam does do it for me (not very well), but i can’t find any similar method in SDK. does anyone know an answer or can show me a shorter way than do all math myself?
thanks


#2

Hi DenisT.

Did you solve this?
I’m fighting with a plugin script modifier and I have a serious time bottleneck with this function (proyecting all mesh verts against a spline).
I’m wondering if this rutine could be done in C++ and compile it ‘on the fly’.

(P.S.: stupid question. Of course you’ve solved it, as allways! :bowdown: )


#3

i couldn’t find any sdk method to make it easy. so i do distance comparison with precalculated step points. they are cached in polyline. it works good enough in my case


#4

I’ve been thinking (and working) on this subject for two months: if DenisT has a problem, it must be a real-interesting-passioning challenge! And perhaps I can help!?

How to solve this?
Let’s back to University, with all extrange functions for interpolation, solving roots, …

If we get a function that fits the spline, then it’s seems easy: let’s call Q the external point.
1- Find all spline points P whose tangent is perpendicular to the [Q ,P] vector;
2- Calc the distance of [Q,P] vector
3- Select the smallest of all

The first point reduces to calculate the function points where:
dot_product [Q,P] [Tangent in P] = 0, being [Tangent in P] the derivative of the function in P.

There are several methods to interpolate splines according to the case. Most used and simplest are third degree polynomial interpolation by segments: for each segment of the spline, you find a third degree polynomial that meets some restrictions, for example containing the extreme knots of the segment and having the same tangent at these knots.

This starts to become a problem… if we fit the spline with a third degree polynomial (the simplest one possibility), the derivative is a second degree polynomial, so the dot product is a fifth degree function… and by the Abel-Ruffini theorem, we know that there’s no a general formula to solve this.

[… to be continued]


#5

Luckely, not all is lost.

Third degree interpolation methods by segments are parametric in the variable ‘t’ which goes from 0 at start knot to 1 at the end knot.

If there’s a solution for our fifth-degre equation (dot product = 0), then it must be between 0 and 1.
Here appears the Newton–Raphson method. It is a method for finding successively better approximations to the roots (or zeroes) of a real-valued function in a known interval. The convergence is at least quadratic in a neighbourhood of the zero (that means converges very fast).


So I started with the Hermite interpolation:
Unit interval (0, 1)
On the unit interval (0,1), given a starting point P0 at t=0 and an ending point P1 at t=1 with starting tangent m0 at t=0 and ending tangent m1 at t=1, the polynomial can be defined by

P(t) = (2t^3-3t^2+1)P0 + (t^3-2t^2+t)m0 + (-2t^3+3t^2)P1 +(t^3-t^2)m1

After programming it, the function didn’t fit fine Max splines. In fact, the function depends on another parameter that gives de ‘weight’ of the curve. And this weight is not the same for all segments.

Then I found the Centripetal Catmull-Rom interpolation, that I didn’t knew before, that seems to be used in computer graphics for splines. That sounds nice!

https://en.wikipedia.org/wiki/Centripetal_Catmull–Rom_spline

The only problem is that you need 4 points to define a segment as it uses the external points to find the tangent. Thus, I had to search a start and an end imaginary knots for the spline, using tangent given by 3DSMAX at these starting/ending knots.

The general formula is:
F(t) = (-0.5t + t^2 - 0.5t^3)P0 + (1 - 2.5t^2 + 1.5t^3t)P1 + (0.5t + 2t^2 - 1.5t^3)P2 + (-0.5t^2 + 0.5t^3)*P3

Bingo!! That fits very fine the spline and the ‘t’ param is very close to the 3DSMAX ‘pathparam’ (non uniform) for splines.

Next Chapter: “how to make it faster (1)”


#6

What I used in a first round to speed up the function is:

  • Make two cycles, with a first one of at least 7 subdivisions for each spline segment to find the ‘zone’ where the nearestPoint is and a second sub-subdivision just in this zone to avoid calculate all the spline sub-subdivided.
    Why 7 subdivisions? As there can be segments like segment 3 in the image below, I think 7 is a needed minimum.

  • Reduce Newton-Raphson iterations to 10 (if accuracy is not reached before)

  • Take two accuracies: one for the first cycle and a smallest one for the second.

  • Check for straight segments (comparing its length to the distance between its extreme knots) to make the exact (and quick) calculation through vertex projection instead of Catmull-Rom interpolation.

  • Simplify Catmull-Rom coefficients to At^3+Bt^2+C*t+D, so you can reuse those coefficients in first and second derivative that you will need for the calc.

  • Create initial array for these coefficients and knots, and check allways if the elements are allready calculated to avoid recalc something.

  • Learn a little bit of C# and Max SDK to write the function in a compiled languaje!!!

P.S.: I don’t know if there is someone interested in this thread, but I’ll go on with it.

[Next… problems, how to make it faster (2) and, finally, code]


#7
I wonder why you have decided to work with Catmull-Rom spline with 4 "imaginary" control points instead of Bezier spline and getInVec() - getOutVec().

#8

No, I haven’t explained well.
The Centripetal Catmull-Rom uses the knots of the spline. But as it needs 4 knots to define 1 segment, you have a problem with the first and the last segments of the spline (S-1 & S-6 in the image above).
So you have to create an additional first vert and an additional last vert. I’ve done it with tangents at this points but you are right I could have use the inVect for the first and the outVect for the last one.

By the way, thanks for following!


#9

But, in fact, there’s a need of more subdivisions near bezier corner knots that perhaps using outVec can be reduced. You are wellcome to improve the code :keenly:


#10

It’s still unclear to me why you decided to work with Catmull-Rom curve instead of Bezier curve.

I mean, what makes you think that SplineShapes are Catmull-Rom curves (internally in 3ds Max) and not Bezier curves, as explicitly declared everywhere in Max help and SDK.


#11

The Centripetal_Catmull is a special case of a Cardinal Spline that is a solution for finding tangents for a Cubic Hermite Spline. A Cubic Hermite Spline is a Bezier curve of 3rd degree. It’s the same.

https://en.m.wikipedia.org/wiki/Cubic_Hermite_spline#Catmull.E2.80.93Rom_spline

The principal advantage of Catmull-Rom technique is that the points along the original set of points also make up the control points for the spline curve. Two additional points are required on either end of the curve. That is not the case for all bezier curves, where control points are outside the spline (don’t belong to it).
Studying its properties and uses, and the results of my code, I think 3ds Max uses something very similar to them.


#12

Further more, you need to find an analytical function to be able to derive it twice. That’s not the case with most bezier splines that aren’t. You get values iterating.
In fact, viewing the results of the maxscript function ‘nearestpathparam’ and others, 3ds Max splines mustn’t have an analitical expression. That’s why you need the parameter ‘steps’ in some functions to set the number of iterations.


#13

I had no idea about that. I always thought Max used Bezier for Splines.


#14

Here is a Bezier version. It does seem to fit the spline perfectly and also to be consistent with Max native function pathInterp().

(
    	gc()
    	delete objects
    	sp = splineshape adaptive:on wirecolor:yellow
    	addnewspline sp
    	addknot sp 1 #beziercorner #curve [0,50,100] [0,50,100] [250,0,50]
    	addknot sp 1 #beziercorner #curve [0,-50,0] [-250,0,50] [0,-50,0]
    	updateshape sp
    	
    	fn InterpolateBezier P0 P1 P2 P3 t = 
    	(
    		return (1-t)^3*P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3
    	)	
    	
    	p0 = getknotpoint sp 1 1
    	p1 = getOutVec sp 1 1
    	p2 = getInVec sp 1 2
    	p3 = getknotpoint sp 1 2
    	
    	T = random 0.0 1.0
    	
    	pt1 = InterpolateBezier p0 p1 p2 p3 T
    	pt2 = pathInterp sp 1 T
    	
    	point pos:pt1 size:10 cross:on box:on wirecolor:red
    	point pos:pt2 size:20 cross:on box:off wirecolor:green
    		
    	format "P1:%
P2:%
" pt1 pt2
    )

How is the Catmull-Rom function you are using?


#15

Here is an approach of what I think Max is doing behind the scene in the nearestPathParam() function. It is not fully tested but a proof of concept.

I don’t think it is exactly the same but close to it, and it does work with one curve only (or the first one if many), but is just an example.

It returns an array with 3 values:
The param along the spline (0.0-1.0)
The position
The distance

(
 	/*---------------------------------------------------------------------------------------------*/
 	/* TEST SCENE */
 	/*---------------------------------------------------------------------------------------------*/
 	
 	gc()
 	delete objects
 	sp = splineshape adaptive:on wirecolor:yellow
 	addnewspline sp
 	addknot sp 1 #beziercorner #curve [0,50,100] [0,50,100] [250,0,50]
 	addknot sp 1 #beziercorner #curve [0,-50,0] [-250,0,50] [0,-50,0]
 	
 	updateshape sp
 	
 	center = (random -[1,1,1] [1,1,1]) * 100
 	point pos:center size:10 cross:on box:on wirecolor:red
 	
 	/*---------------------------------------------------------------------------------------------*/
 	/* CUSTOM FUNCTION */
 	/*---------------------------------------------------------------------------------------------*/
 	
 	fn GetNearestPathParam mShape mPt steps: =
 	(
 		fn InterpolateBezier P0 P1 P2 P3 t = (1-t)^3*P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3
 		
 		/*	In the nearestPathParam() function, if steps
 			is unsupplied it seems to use a default value
 			close to twice the length of the spline.
 		*/
 		if steps == unsupplied do steps = (curvelength mShape) * 2.0
 		
 		minDist = 1E9
 		minPoint = undefined
 		minTime = undefined
 		
 		step = 1.0 / steps
 		segments = numsegments mShape 1
 
 		for j = 1 to segments do
 		(
 			p0 = getknotpoint mShape 1 j
 			p1 = getoutvec mShape 1 j
 			p2 = getinvec mShape 1 (j+1)
 			p3 = getknotpoint mShape 1 (j+1)
 			
 			for t = 0.0 to 1.0 by step do
 			(
 				pt = InterpolateBezier p0 p1 p2 p3 t
 				dist = distance mPt pt
 				
 				if dist <= minDist do
 				(
 					minDist = dist
 					minPoint = pt
 					minTime = j+t-1
 				)
 			)
 		)
 		return #(minTime/segments, minPoint, minDist)
 	)
 	
 	steps = random 200 2000
 	format "Steps:%
" steps
 	
 	p = GetNearestPathParam sp center steps:steps
 	point pos:p[2] size:10 cross:on box:off wirecolor:green
 	format "CUSTOM	%
" p
 	
 	/*---------------------------------------------------------------------------------------------*/
 	/* MAX NATIVE */
 	/*---------------------------------------------------------------------------------------------*/
 
 	nearestParam = nearestpathparam sp 1 center steps:steps
 	p = pathinterp sp 1 nearestParam
 	point pos:p size:5 cross:on box:on wirecolor:blue
 	format "3DSMAX	%
" #(nearestParam, p)
 )

#16

The bad thing for me is that you are absolutely right. :keenly:

When I tried this function I used tangents instead of inVect-outVect. That’s why I gave up the idea and searched for other functions. So a thousand lines of code will be thrown to the rubish. :banghead:

The good thing is that new code will be much fast and accurate. The one with Catmull-Rom was faster and more accurate than the maxscript native one. So the new one will be much better and without a lot of parameters (subsegments, sub-subsegments, error admited,…)

What I can’t understand is why MaxScript has a such slow and unaccurate function for nearestPathParam if there’s an analytical formula for its splines. The same for all other functions that need ‘step’ parameter.

Well, let’s start again and enjoy!


#17

it’s not slow. the accuracy depends on number of steps.
i’ve written above, that i use already precalculated step points. to get distance from point-to-line is much faster than point-to-curve. so we can find a ‘segment from step to step’ which contains the nearest point on the curve. after that all we need is to search again only this segment.


#18

If you need accuracy, it’s very very slow. With straight segments it’s very unaccurate (I can’t understand why), thus you need to increase steps to get something good.
I gave a try to polyshapes as you suggested (3DS MAX SDK says: “Used for doing a one time interpolation of a bezier shape into a form that is the same shape but doesn’t require any further interpolation”). Time needed to create the polyshape and get these verts was the same than getting the vertex one by one with ‘InterpBezier3D’ command. And it didn’t solve unnacuracy.

The new code with Jorge’s proposal is already done (draft) and it’s really-really good.

I haven’t said am looking for a function to apply to a set of vertex (node or nodes at a time). That gives a chance to get precalculated items and be much faster.
If additionnaly you skip segments ‘far from node’ and ‘far from vertex’ and use projection for straight segments… you have a fantastic tool!

Soon for all of you who want it.


#19

it takes ZERO time because it’s already stored in spline data.


#20

Surely I did something wrong. I’m just starting with SDK and with C#.

        /// <summary>
        /// Method to get an IPolyLine from a Shape (after modifiers applyed).
        /// </summary>
        /// <param name="shapeNode"></param>   The shape node
        /// <param name="numSpline"></param>   The index of the ISpline3D to get from the shape
        /// <param name="numsteps"></param>   The number of setps to apply for the conversion
        /// <returns> the 'ns' ISpline3D of the shape converted to IPolyLine (or the first one if ns>number of splines in the shape)</returns>
        /// 
        public static IPolyLine ConvertShapeToIPolyLine(IINode shapeNode, int numSpline, int numsteps)
        {

            ISplineShape newSpline1 = GetSplineShapeFromNode(shapeNode);

            if (isShape)
            {
                //MyClass("ISplineShape newSpline1", newSpline1);   //Inspects the Shape BaseObject. 

                SClass_ID mySClass1 = SClass_ID.Shape;  //shape SuperClass
                IClass_ID myClass1 = global.Class_ID.Create((uint)BuiltInClassIDA.SPLINE3D_CLASS_ID, 0);    //ISpline3D class

                IBezierShape bzs = newSpline1.Shape;    //IBezierShape got from ISplineShape newSpline1

                IClass_ID myClass2 = global.Class_ID.Create((uint)BuiltInClassIDA.LINEARSHAPE_CLASS_ID, 0); //ILinearShape class
                ILinearShape iln = ip.CreateInstance(mySClass1, myClass2) as ILinearShape;
                IPolyShape pshp = iln.Shape;    // Creates empty IPolyShape from empty ILinearShape

                bzs.MakePolyShape(pshp, numsteps, false);   //Get the IPolyShape from the IBezierShape

                if (numSpline < 0 || numSpline > (pshp.NumLines - 1))
                {
                    numSpline = 0;
                }

                IPolyLine the_Path = pshp.Lines[numSpline]; //Gets the IPolyLine from the IPolyShape

                /*
                int numPoints = the_Path.NumPts;
                List<IPoint3> thePoints = new List<IPoint3>(nsp4);

                for (int i = 0; i < numPoints; i++)
                {
                    IPoint3 p1 = the_Path.Pts[i].P;
                    thePoints.Add(p1);
                }
                */

                return (the_Path);
            }
            else
            {
                //WriteLine("The Node is not a Shape");
                return null;
            }
        }