Shape Check, or finding self intersections of a spline


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.


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.


see sdk -> editspl.cpp -> SplineSelfIntersects


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


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


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



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


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


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.


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.


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

				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.


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.


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


So right now i’m using this,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.


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


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.