View Full Version : check for curve selfintersection
pixlix2 07 July 2007, 03:00 PM Hi,
I'm having a problem, I need to write a function that checks if a curve (in 2d space) has selfintersections  like in the picture below:
http://i33.photobucket.com/albums/d60/pixlix/screen1.gif
I was thinking about creating two pointOnCurve nodes an let wander around in small increments continuously measuring the distance with a mag() function  but when I know really think about it... wouldnt really work, i guess, would have to check a million times...
has anyone any pointers for me?
Thanks!!
Greetings


GennadiyKorol
07 July 2007, 04:16 PM
Using Maya curve commands you could first separate the curve into segments, by selecting curve points around the curve edit points and calling "Detach Curves". Then you'd select all the segments and call "Intersect Curves" to get the intersections.
The ugly thing about this is that the Intersect Curves node will give you warnings in case it won't find any intersection. Also you'd have intersections on the points where 2 continuous segments meet. So might want to do some little scaling to the curve points to hack around that.
This would give you intersections in some Maya MEL, hacky way :)
If you're like me, appreciating a clean mathematical solution this might help :) :
First of all you need to check whether 2 segments intersect.
If the curve has linear interpolation as on the picture, you could reduce this to checking line segment intersections.
If the curve is cubic you'd have to separate it to segments, each of which is polynomial of 3'rd degree. You'd have to calculate the polynomial here, which would require getting 4 points on a segment (4 coefficients in 3'rd degree polynomial).
To check if there's intersection you could subtract the polynomials of first and second segments and find its roots (possible for 3'rd degree polynomial (http://en.wikipedia.org/wiki/Cubic_equation#The_nature_of_the_roots)).
Now to check if the curve has selfintersections, you subdivide it to segments (probably by edit points), and check intersection between each pair of segments.
So you check segment 1 with segment 2, then 1 with 3, 1 and 4, etc. Then 2 with 3, 2 with 4, etc. This isn't very efficient, but fairly simple to implement without any introduction of grid or BSP like optimizations.
The numerical approach you started with is also very interesting and could work. I will post when I'll get any ideas about it :)
Hope it helps,
Henry
pixlix2
07 July 2007, 08:15 PM
Hey, many thanks for your detailed answer, Henry!
This sounds all pretty interesting. For now I only need 1Degree curves (these are used to generate houses in a citybuilder script I'm working on).
While I tried you suggestion with the curve splitting I suddenly had a pretty funny idea  veryyyy unmathematical ;)
take the curve>surface planar>poly output with "count"tesslation set to 1>
select all faces> if number of faces > 1 then the curve has at least one interesection
This only works with closed curves of course, but thats what I need right now.
Maybe I've missed a problem, havent tested all condition yet:
http://i33.photobucket.com/albums/d60/pixlix/screen2.gif
of course its all a bit slow, but i need to finish the damn script..hehe
greetings
edit:::::
so, thats what I'm using now
// will return 1 if the closed curve intersects itself  else it will return 0
proc int checkIntersect(string $crv){
string $selRestore[] = `ls sl`;
string $tmp1[];
string $tmp2[];
string $shape[] = `listRelatives s $crv`;
int $v = `getAttr ($shape[0] + ".form")`;
if ($v == 0)
closeCurve ch 0 ps 1 rpo 1 bb 0.5 bki 0 p 0.1 $crv;
$tmp1 = `planarSrf ch 0 d 3 ko 0 tol 0.01 rn 0 po 0 $crv`;
$tmp2 = `nurbsToPoly f 0 pt 1 pc 1 ch 0 $tmp1[0]`;
int $f[] = `polyEvaluate f $tmp2[0]`;
delete $tmp2 $tmp1;
if ($f[0] > 1)
return 1;
else
return 0;
}
{
string $sel[] = `ls sl`;
print `checkIntersect($sel[0])`;
}
GennadiyKorol
07 July 2007, 11:06 PM
It looks like a nice hack! I can't really think of a case with a closed curve where you'd have more than one face.
I see you could as well find the points of intersection by just getting the "shared" vertex positions of the adjacent faces :)
Glad you have it done :)
Regards
CGTalk Moderation
07 July 2007, 11:06 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.