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.

# Shape Check, or finding self intersections of a spline

**Hobbs**#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.

**Serejah**#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
)
)
)
```

**denisT**#7

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

**Serejah**#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

**denisT**#9

the issue is too advanced for this forum’s search

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.

**aaandres**#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.

**Hobbs**#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.

**aaandres**#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.

**Hobbs**#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.

**aaandres**#15

That’s the maths behind… but for infinite straight lines.

Can’t see how you are going to get it.

**Klvnk**#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.