I had no idea about that. I always thought Max used Bezier for Splines.
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?
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)
)
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!
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.
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.
it takes ZERO time because it’s already stored in spline data.
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;
}
}
after 4 hours fighting and researching i’ve improved nearestPathParam function and made it ~8 times faster for 1000 steps, ~20 times faster for 10000 steps, and ~200 times faster for 100000 steps
there is what i started with http://www.cyberforum.ru/geometry/thread1425152.html
but this algorithm works for only quadratic Bezier curves, and it doesn’t work for cubic curves. But!!! any cubic curve can be approximated by several quadratic curves. there is a theory how to break cubic bezier on quadratics. it’s what i actually do.
I can’t follow the code of the link you posted. To hard for me.
But I can’t see where it is limited to second degree. In fact, I see the initial formula of third degree:
B (t) = (1-t)^3 * P1 + 3t * (1-t)^2 * P2 + 3t^2 * (1-t) * P3 + t^3 * P4
What I’ve done is simplify this formula to:
H(t) = cc[1] + cc[2]*t + cc[3]*t^2 + cc[4]*t^3 , thus derivatives are:
H’(t) = cc[2] + 2 *cc[3]t + 3cc[4]*t^2
H’’(t) = 2 cc[3] + 6cc[4]*t
The function to find its roots is the dot product F(t) = H(t).H’(t) = 0 (5th degree).
Then you use Newton-Raphson: t_n+1 = t_n – F(t_n) / F’(t_n)
We know that the derivative of a dot product is:
(F(t).G(t))’ = F(t).G’(t) + F’(t).G(t)
So
(H(t).H’(t))’ = H(t).H’’(t) + H’(t).H’(t) = H(t).H’’(t) + lengthsquared(H’(t)).
Returning to Newton-Raphson:
t_n+1 = t_n – (H(t_n).H’(t_n)) / (H(t_n).H’’(t_n) + lengthsquared(H’(t_n)))
I think that this saves a lot of calculations.
The big problem with Max is that Point3 and all its vector operations (dot product for example, or length) are float and not double. So its nearly impossible to approach to a value of ‘t’ with more than 3 exact decimals. For a spline of 1km (1000m), that means you approach to the unit (first decimal at most). That is not very much in most cases.
Using double float calculations (as I have done with Vector3D is c# from “System.Windows.Media.Media3D.Vector3D”) you win 1 decimal (not more because input data Point3 are still float and the ‘t’ param for pathInterp3D too).
to make ‘step-iteration’ faster it uses The bisection method, which is true for ‘convex’ curves (quadratics for sure)
it sounds like you want better accuracy working with splines of ‘kilometers’ long. but it doesn’t matter sometimes how accurate you calculate Length or DotProduct because input and output data is not accurate enough anyway
Not bad… and better than mine I think.
These are my results for next cases, with the two bezier splines of the image below and a sphere of 20.000 vertex in different positions:
Comparison between my code in C# with just 7 subsegments, the default MaxScript nearestPathParam and the MaxScript nearestPathParm with steps = (lengh of spline * 10) to reach the same accuracy than the C# code (not the same, but enougth).
Spline SP-2 converted to polyline – Sphere in any position:
C#: 0,048s – Default MXC: 4,662s (97 times faster) – MXC steps = lengthx10: 22,027s (460 times faster)
Spline SP-1 converted to polyline – Sphere in any position:
C#: 0,082s – Default MXC: 8,662s (105 times faster) – MXC steps = lengthx10: 42,731s (520 times faster)
Spline SP-1 (bezier) – Sphere in any position:
C#: 1,087s – Default MXC: 9.822s (9 times faster) – MXC steps = lengthx10: 48,513s (45 times faster)
Spline SP-2 (bezier) – Sphere in position 2 or 3 (near few segments):
C#: 0.717s – Default MXC: 6,742s (9,5 times faster) – MXC steps = lengthx10: 33,086s (46 times faster)
Spline SP-2 (bezier) – Sphere in position 1 (near several segments):
C#: 1,175s – Default MXC: 6,746s (6 times faster) – MXC steps = lengthx10: 33,115s (28 times faster)
In cases 3 and 4, I reach the same accuracy with only 5 segments instead of 7, obtaining of 30% more speed.
I haven’t never needed more than 11 subsegments to reach the maximum accuracy.
Edit: SP-1 length = 2341 units, SP-2 length = 1767 units
could you post a sample scene (max 2014 or less) to make a compare test of our methods (accuracy and performance)?
Yes, of course.
I’ve have sent you a pm.