Shape Check, or finding self intersections of a spline


#1

Does anyone know where the shape check source code is, or anyway to find self intersections of a spline. I basically want to automate the removal of knots where a self intersection is created so I can convert the spline to Editable poly.


#2

Basically right now i’m using the bounding box of each segment and doing an intersection test that way, but its not the most elegant. I didn’t know if people had a better solution.


#3

see sdk -> editspl.cpp -> SplineSelfIntersects


#4

that’s not the most elegant either being like most max code brute force stylee :slight_smile:


#5

Hehe…true, after looking at, but it will work. Thanks Denis!


#6

didn’t test it in max, but it should work

(
	g = (dotNetClass "Autodesk.Max.GlobalInterface").Instance
	inode = g.coreinterface7.getinodebyhandle $.inode.handle
	shp = ((inode.EvalWorldState (int currenttime) true).obj).shape_
	splines = for i=0 to shp.SplineCount-1 collect shp.GetSpline i
	
	for i=1 to splines.count do
	(
		format "Spline % is self-intersecting: %\n" i (splines[i].SelfIntersects)
		
		for j=i+1 to splines.count where splines[i].IntersectsSpline splines[j] do
		(
			format "Spline % intersects spline %\n" i j
		)
		
	)

)

#7

I was always interested to know not the fact of intersection, but to get all intersection points.


#8

Sure, but I guess it’s better to know which splines are actually intersecting before attempting to find an exact point.
I remember here was a thread where you and @aandres discussed how to calc the intersection points between bezier splines. But forum search is too advanced to find it


#9

the issue is too advanced for this forum’s search :stuck_out_tongue_winking_eye:

just today i wrote the ‘two splines intersection’ function for my mxs extension. I found that using linear interpolation gives the best result by performance. the accuracy is OK for most cases.


#10

No, I haven’t faught here with splines intersections. Perhaps you are talking about the nearestPathParameter thread.
The better source for beziers I know (and from where I have developped my C# double precission one) is this one:


I haven’t seen the sdk -> editspl.cpp -> SplineSelfIntersects, but I suppose by your comments that is a sort of aproximation through bisection or something similar.
In the link above, the intersection is done by aproximation too, playing with bounding boxes (Caution: all this document is about spline segments, not whole splines). For Line-Spline intersection, you can get the analitic solution.


#11

the one in the .cpp, if i’m reading right, just does 2 dimensional collision. For that one i already found a relatively easy one on line, though won’t work for bezier. So i’ll have to read this bezier curves paper. Thanks!

				fn FindSlope=
				(
					A = pt1.Y - pt0.Y
					B = pt0.X - pt1.X
					C = A * pt0.X + B * pt0.Y
				),

				
				--https://pastebin.com/iQDhQTFN
				fn Intersect2D otherLine =
				(
					out = #()
					local determinant = A * otherLine.B - otherLine.A * B;

					if  EqualValues(determinant)(0) == false do -- true they are parallel
					(
						--Cramer's Rule
						local x = (otherLine.B * C - B * otherLine.C) / determinant;
						local y = (A * otherLine.C - otherLine.A * C) / determinant;

						append out [x,y];
					)
					/*return*/ out
				),

the 3 dimensional one has been a little trickier. This one works for simple linear 2d lines.


#12

3D intersections have limited chance to be. I mean, the only way you’ll have to do it is with a minimal error value as you are working with float precission. So, you will never know if it’s a real intersection or an almost one.


#13

Yea i was planning on implementing a “delta” of sorts.


#14

So right now i’m using this http://inis.jinr.ru/sl/vol1/CMC/Graphics_Gems_1,ed_A.Glassner.pdf , page 304. thats paper page 304, not pdf page. I had some string case at the knots that i had to cull out, but other than that seems to get me in the ball park.


#15

That’s the maths behind… but for infinite straight lines.
Can’t see how you are going to get it.


#16

the one in the .cpp, if i’m reading right, just does 2 dimensional collision.

the 3 dimensional one has been a little trickier. This one works for simple linear 2d lines.

the chance of a “true” 3d bezier spline self intersecting (or being able to find it to 1 or 2 mil) is neigh on impossible hence the 2d “plane projection” approach. probably best to find the “closest points” not adjacent.