Placing points along spline at even distance between them

#9

Here’s the solution with subSegments for splines with very closed segments. I don’t think you’ll need more than 10 subsegments for really extrange splines.
This solution is coded with a struct, so more memory and time than with arrays, but more clear. If you want the array solution, I have it.
I get 2ms for your spline (memory 28680L) with 5 subsegments (they could be just 1 for this case) and an accuracy of 0.0001.

(	
	gc()
	t1 = timeStamp()
	m1 = heapfree
	
	-- Catched functions
	local interpCurve = interpCurve3D
	local interpBezier = interpBezier3D

	-- Input Data
	curSpline = selection[1]
	fixedDist = 33
	numSubSeg = 5	--	Caution!!! Minimum 1
	accuracy = 0.0001
	
	-- Basic spline data for calculation
	numK0 = numknots curSpline 1
	closed = isClosed curSpline 1
	if closed do numK0 +=1
	numK = (numK0 - 1) * numSubSeg + 1
	numSeg = numSegments curSpline 1
	invNumSeg = 1.0 / numSeg
	invNumSubSeg = 1.0 / numSubSeg
	relStep = invNumSubSeg * invNumSeg
	
	---------------------------------------
	-- Data for each knot
	struct Knot (coord, segment, relParam)
	local knots = #()
	local coord
	local segment
	local absParam
	local relParam
		
	ptsCounter = 0
	for i = 1 to numK0 - 1 do
	(
		ptsCounter += 1

		coord = getKnotPoint curSpline 1 i
		segment = i - 1
		absParam = invNumSeg * (i-1)
		relParam = 0.0
		knots[ptsCounter] = Knot coord segment relParam
		
		for j = 1 to numSubSeg - 1 do
		(
			ptsCounter += 1

			segment = i
			absParam += relStep
			relParam += invNumSubSeg
			coord = (in coordsys world (interpCurve curSpline 1 absParam pathParam:true))
			knots[ptsCounter] = Knot coord segment relParam
		)
	)
	ptsCounter += 1

	if closed then
	(
		coord = getKnotPoint curSpline 1 1
	)
	else
	(
		coord = getKnotPoint curSpline 1 numK0
	)
	knots[ptsCounter] = Knot coord numSeg 1.0
	--------------------------------------
	
	-- Calculation
	pointsPosArr = #(knots[1].coord)	
	stopLoop = false
	currentKnotIdx = 2
		
	while stopLoop == false do
	(
		-- Get index of knot farthest than fixedDist from previous one
		lastPoint = pointsPosArr[pointsPosArr.count]
		morePoints = false
		for i = currentKnotIdx to numK while not morePoints do
		(
			dist = distance lastPoint  knots[i].coord
			currentKnotIdx = i

			if dist >= fixedDist do
			(
				morePoints = true
			)
		)
		
		-- Calculation of the point by bisection (max 1000 iterations)
		if morePoints then
		(
			segmentID = knots[currentKnotIdx].segment
			
			pt
			error = 1e6
			a = knots[currentKnotIdx - 1].relParam
			b = knots[currentKnotIdx].relParam
			if b == 0.0 do b = 1.0
			iterations = 0
			while error > accuracy and iterations < 1000 do
			(
				iterations += 1
				param = (a+b) * 0.5
				pt = interpBezier curSpline 1 segmentID param pathParam:true
				dist = distance lastPoint pt
				if dist > fixedDist then b = param else a = param
				error = abs(dist - fixedDist)
			)
			append pointsPosArr pt
		)
		else
		(
			stopLoop = true
		)
	)
	
	t2 = timeStamp()
	m2 = heapfree
	format "Time: %ms; Mem: %\n" (t2-t1) (m1-m2)
	
	-- Print and Plot results
	for p in pointsPosArr do
	(
		point pos:p wirecolor:yellow
	)
	for i = 2 to pointsPosArr.count do
	(
		format "dist[%:%]= %\n" (i-1) i (distance pointsPosArr[i] pointsPosArr[i-1])
	)
)

Hope it helps.

#10

As a picture is worth a thousand words, here you have an image of the kind of spline you can have problems if you don’t use subdivisions:

#11

@Serejah, I have the same problem with your code as Andres have - the cursor goes mad. :slight_smile:

Andres, thank you. While I was at work i think that I can use this:
1- divide the spline to 100 “segments”, not 1 000 000
2- find the “segment” where the next point have to be paced
3- divide this segment to 1 000 poitns and find the right point

Your solution works better than my idea. :slight_smile: But there is one problem - try it on my scene with fixedDist = 0.3 - the max freezes. My ugly code in my first post works with 0.3 only if I increase the accuracy to 1.0. The time is the same 4+ secs, the used memory is much, much, much more than your code uses.

EDIT: increasing the numSubSeg = 100 to 100 solved the problem. :slight_smile:

I have tried the Shape Check utility - it works only when the circle is part of the same spline.

#12

If 0.3 is very small with respect to the segments length, the behaviour you tell is quite logical.
Perhaps you can make a previous check, comparing the maximum segment length (you know it’s a cached value) with the fixedDist and then set subdivisions to the double of their relation.

#13

I have added this to the code, and for now it works without any issues:

numSubSeg = (curveLength selection[1] / fixedDist) as integer

It not gives the best result, because sometimes the code above calcualtes that 300 subSegments have to be used while using only 100 segments is faster and more memory friendly.

#14

But it makes it five times slower than the original Aaandres code
Try moving numSubSeg inside the for loop

...
slen = getSegLengths selection[1] 1
ptsCounter = 0
for i = 1 to numK0 - 1 do
(
	ptsCounter += 1

	numSubSeg = (slen[ numSeg + i ] / fixedDist) as integer
	invNumSubSeg = 1.0 / numSubSeg
	relStep = invNumSubSeg * invNumSeg
				
		
	coord = getKnotPoint curSpline 1 i
	segment = i - 1
...
#15

It’s curious…
In your spline example, with fixedDist=0.3 and 100 subsegments, you get for each point a maximum of 12 iterations and you reach for all of them the 0.0001 accuracy.
With 300 subsegments, the maximum is 10 iterations, but there are 9 points that reach the 1000 iterations, thus their accuracy is lower.
These points, still with 10.000 iterations, give the same result. There must be a problem somewhere in the code, possibly when the point matchs the end of the segment. Have not time today to search for it, but shouldn’t be difficult to check if the value ‘b’ gives the right accuracy, so no need to do bisection.

EDIT: no, that’s not the problem. Must be something related with float precision when calculating distances.

#16

Yes, in this particular situation it makes it slower. But I have tested it with a spline with length 553 295 units. FixedDist = 300, numSubSeg= 100 - Max freezes. When the numSubSeg is calcualted using the numSubSeg = (curveLength selection[1] / fixedDist) as integer the values are:
fixedDist = 300, numSubSeg= 1844 and the results are:
Time: 34566ms; Mem: 3164832L

I will do more tests later this day.

#17

Seems really strange to me.
Can you send me the spline, please?

#18

I’ve just checked my suggestion on your spline and sometimes it is indeed doesn’t make almost any difference.
And seems that very few points actually reach target accuracy level even after 1000 iterations.

fixedDist 30
Total points 1224 valid: 2.78005% – added before 1000th iteration
Time: 8.206sec. Mem: 6623134L

fixedDist 100
Total points 367 valid:2.73224%
Time: 2.372sec. Mem: 7041406L

fixedDist 300
Total points 123 valid:4.09836%
Time: 0.743sec. Mem: 8915950L

fixedDist 666
Total points 55 valid:1.85185%
Time: 0.323sec. Mem: 7896406L

#19

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

Accuracy of 0,01 is enough for me.

#20

OK, I see…
The problem is the float mantissa. Your spline is too long! :slight_smile:
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

#21

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.

#22

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.

#23

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
)
#24

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)

#25

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

#26

The “one step closer” solution! :slight_smile:
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)
	)
#27

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)
	)
#28

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)
)