Placing points along spline at even distance between them

miauu · 2018-12-24 17:12:02 UTC

Here is the link for the new spline: https://drive.google.com/open?id=166UMWuDjtOIT90VSx0EmPB5tJRN8PLKG

Accuracy of 0,01 is enough for me.

aaandres · 2018-12-24 17:47:45 UTC

OK, I see…
The problem is the float mantissa. Your spline is too long!
Type in the listener for example 127356.5632: you’ll get 127357.0
You should scale your model to get fine results. As it is, you just can get accuracy to the unit (1 ).
There’s nothing other to do, either working with double values as Point3 has float values.
Edit:
Float numbers: -1S × M × 2E

Bit No	Size	Field Name
31	1 bit	Sign (S)
23-30	8 bits	Exponent (E)
0-22	23 bits	Mantissa (M)

You have 23 bits for the mantissa (significant numbers): 2^23=8388608

miauu · 2018-12-24 19:43:18 UTC

Thank you.
So the script will check the length of the spline and if it is too long(too many numbers before the decimal point) it will use smaller value of accuracy.
But even with this long spline the script works when the numSubSeg is calculated and not predefined.

aaandres · 2018-12-24 19:59:47 UTC

No, taking 34sec is not to work. It shouldn’t take more than 0,1sec (in a slow computer for a spline like this one). I wouldn’t trust in the results you get. Scaling it gives the result in 60ms.
But there’s still a problem in some isolated verts that I can’t solve. I think it’s a ‘bug’ of interpBezier3D or interpCurve3D, but I’m not sure.

denisT · 2018-12-25 04:26:28 UTC

let’s bring the test to a unified form of solution…

it has to be a function with at least two parameters - the spline and the fixed distance between points on the spline.
The function has to return all found points in the world space. The function can have any extra optional arguments to make calculation more accurate.

fn scatterPointsOnSpline sp dist tolerance:0.001 = 
(
	-- ...
	points
)

denisT · 2018-12-25 05:11:06 UTC

here is my solution:

fn scatterPointsOnSpline sp dist tolerance:0.001 = 
(
	len = curveLength sp
	t = 0.0
	d = 0.0
	current = interpCurve3D sp 1 t pathParam:off
	points = #(current)
	
	while t < 1.0 do
	(
		t += (dist - d)/len  
		t = amin t 1.0
		p = interpCurve3D sp 1 t pathParam:off
		d = distance current p
		if d >= dist - tolerance do
		(
			current = p
			append points current
			d = 0.0
		)
	)
	points
)


/***************** TEST *****************/
(
	delete helpers 
	
	t0 = timestamp()
	h0 = heapfree

	points = scatterPointsOnSpline $ 33.0 tolerance:0.001

	format "time:% heap:%" (timestamp() - t0) (h0 - heapfree) 
	
	dd = for k=1 to points.count collect 
	(
		point pos:points[k] wirecolor:orange
		if k > 1 then distance points[k-1] points[k] else dontcollect
	)
	format " >> %\n" #(dd.count, amin dd, amax dd)
)

PS. spline index set to 1 (of course we can pass the index to the function)

Serejah · 2018-12-25 07:18:38 UTC

It is fast.
Guess t should be double in order not to freeze max on large splines.

aaandres · 2018-12-25 10:50:49 UTC

The “one step closer” solution!
Really clever. Fast and few memory. As always, you win.
I just see two problems… well, two and a half.

For some combinations of length-dist-tolerance it freeze as Serejah’s said. It can be solved with double values to avoid freezing, but as it’s again a problem of mantissa, the upper maximum value won’t reach the tolerance. But it’s good enough in most cases (probably in all real cases).
The “half” problem is, due to the first one, you can get a different number of points (+1 or 2) if you change the tolerance to more accurate once reached the mantissa limit. Again, I don’t think it should be a problem for real cases
The second problem, with worse solution, is that if the spline is scaled to bigger, the given result is not the good solution, as for 3dsMax the spline length remains the same (and scaling splines is not perfect). If it’s scaled to lower it works because the script can’t find more points (takes more time but gives the good result).

Yes, that’s the solution to avoid freezing


	fn scatterPointsOnSpline sp dist tolerance:0.001 = 
	(
		tolerance = tolerance  as double
		len = (curveLength sp) as double
		t = 0.0 as double
		d = 0.0 as double
		current = interpCurve3D sp 1 t pathParam:off
		points = #(current)
		
		while t < 1.0 do
		(
			t += (dist - d)/len  
			t = amin t 1.0
			p = interpCurve3D sp 1 t pathParam:off
			d = (distance current p) as double
			if d >= dist - tolerance do
			(
				current = p
				append points current
				d = 0.0	
			)
		)
		points
	)


	/***************** TEST *****************/
	(
		delete helpers 
		
		t0 = timestamp()
		h0 = heapfree

		points = scatterPointsOnSpline $ 33 tolerance:0.000001

		format "time:% heap:%" (timestamp() - t0) (h0 - heapfree) 
		
		dd = for k=1 to points.count collect 
		(
			point pos:points[k] wirecolor:orange
			if k > 1 then distance points[k-1] points[k] else dontcollect
		)
		format " >> %\n" #(dd.count, amin dd, amax dd)
	)

aaandres · 2018-12-25 12:21:32 UTC

Here’s a mixing of the DenisT’s “one step closer” and my bisection way.
Seems not to freeze and supports scaled splines:


	fn scatterPointsOnSpline sp dist tolerance:0.001 = 
	(
		tolerance = tolerance  as double
		len = (curveLength sp) as double
		sc = sp.scale[1]
		x = len / (numSegments sp 1) / dist * 10 / sc;
		step0 = (1.0/ (numSegments sp 1) / x) as double
		t = 0.0 as double
		d = 0.0 as double
		current = interpCurve3D sp 1 t pathParam:on
		points = #(current)
		step = step0 as double
		counter = 0
		
		while t < 1.0 do
		(
			counter += 1 
			t += step  
			t = amin t 1.0
			p = interpCurve3D sp 1 t pathParam:on
			d = (distance current p) as double
			error = (dist - d) as double
			if abs error <= tolerance then
			(
				current = p
				append points current
				step = step0
				counter = 0		
			)
			else
			(
				if error < 0 do
				(
					t -= step
					step *= 0.5 as double
				)
				if counter > 1000 do
				(
					current = p
					append points current
					step = step0
					counter = 0		
				)
			)
		)
		points
	)


	/***************** TEST *****************/
	(
		delete helpers 
		
		t0 = timestamp()
		h0 = heapfree

		points = scatterPointsOnSpline $ 33 tolerance:0.000001

		format "time:% heap:%" (timestamp() - t0) (h0 - heapfree) 
		
		dd = for k=1 to points.count collect 
		(
			point pos:points[k] wirecolor:orange
			if k > 1 then distance points[k-1] points[k] else dontcollect
		)
		format " >> %\n" #(dd.count, amin dd, amax dd)
	)

Serejah · 2018-12-25 13:53:06 UTC

if scale is uniform it’s probably enough to make it work as expected

local isUniformScale = sp.scale[1] == sp.scale[2] and sp.scale[2] == sp.scale[3]	
local factor = if isUniformScale then abs sp.scale[1] else 1	
local len = curveLength sp * factor

and the test

for i=1 to 4 do
(
	c = circle radius:20
	convertToSplineShape c
	c.scale = [0.5 * i, 0.5 * i, 0.5 * i]
		
	gc();t1=timestamp();hf = heapfree
		
		pts = scatterPointsOnSpline c 3.0
		for p in pts do point pos:p centermarker:on cross:off wirecolor:yellow
		format "count %\n" pts.count
			
	format "Time: %sec. Mem: %\n\n" ((timestamp()-t1)/1000 as float) (hf-heapfree)
)

denisT · 2018-12-25 14:24:18 UTC

could you post settings when my algorithm hangs please?

aaandres · 2018-12-25 14:26:28 UTC

I can’t test it until tomorrow, but have you tried scaling Kostadin’s spline? Functions based on length doesn’t work fine generally when there’s a scale (check result distances).

denisT · 2018-12-25 14:30:13 UTC

scaling is not the issue. when can always use a reset-Xform copy

aaandres · 2018-12-25 15:58:17 UTC

If I remember well (I’m not in my desktop), take the second example spline and run the script with dist=300 & tolerance=0.01 (or lesser). Or the first example spline with dist=33 & tolerance=0.000001. Other combinations too.
With double precision it seems to work.

denisT · 2018-12-25 17:35:07 UTC

this version doesn’t hang for me… at least i couldn’t find settings to hang:

fn scatterPointsOnSpline sp dist tolerance:0.001 = 
(
	dist = dist as double	
	len = (curveLength sp) as double
	
	tolerance = amax tolerance (len * 0.000001d0)
	
	t = 0.0
	d = 0.0
	
	current = interpCurve3D sp 1 t pathParam:off
	points = #(current)
		
	while t < 1.0 and not esc_ do
	(
		t += (dist - d)/len  
		t = amin t 1.0
		p = interpCurve3D sp 1 t pathParam:off
		d = distance current p
		if d >= dist - tolerance do
		(
			current = p
			append points current
			d = 0.0
		)
	)
	points
)


/***************** TEST *****************/
(
	delete helpers 
	c = random red green
	
	t0 = timestamp()
	h0 = heapfree

	points = scatterPointsOnSpline $ 30.0 tolerance:0.0001

	format "time:% heap:%" (timestamp() - t0) (h0 - heapfree) 
	
	dd = for k=1 to points.count collect 
	(
		--point pos:points[k] wirecolor:c
		if k > 1 then distance points[k-1] points[k] else dontcollect
	)
	--format " >> %\n" dd
	format " >> %\n" #(dd.count, amin dd, amax dd)
)

we have to understand that most of MAX SDK functions are made in Float precision.
so there is no sense to ask tolerance to be smaller than ‘allowable error’
because of that i’ve added tolerance correction in case of very long splines. which limits tolerance by minimum as 0.000001 of spline length

now couple words about using fixed step in the algorithm.
i wanted to avoid it because there is no absolutely accurate way to define the step. Anyway it might be a situation that making a step we pass a ‘on distance’ point or might be more than one point inside a step.
in the second case we can’t use bi-search because you can find the second point instead of the first.

denisT · 2018-12-25 20:00:09 UTC

as i told many times i always find something interesting and useful in every thread on this forum.
here is very interesting founding… the maxscript doesn’t provide current length for scaled splineshapes.
also it gives the right 3d points for scaled splineshapes in methods: interpCurve3D, interpBezier3D, etc.
but only for pathParam

thanks for this founding! I’ve added to my MXS extension several methods and options to take shape node scale into account. Also I’ve added snapshotAsSplineShape method

denisT · 2018-12-25 21:35:17 UTC

here is advanced spline IK implemented with using the algorithm showen above

aaandres · 2018-12-25 23:07:30 UTC

I would like to see some of these…

miauu · 2018-12-26 18:13:32 UTC

Denis, thank you for the code. Now I have two working codes with two different solutions.
Merry Christmas to all of you and all the best to you and your families.

aaandres · 2018-12-26 19:10:10 UTC

Merry Christmas to you and everyone in this forum!

Note: if you don’t expect scaled splines, DenisT’s solution is far better than mine.