PDA

View Full Version : check for curve self-intersection


pixlix2
07-11-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 self-intersections - 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-11-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 self-intersections, 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-11-2007, 08:15 PM
Hey, many thanks for your detailed answer, Henry!
This sounds all pretty interesting. For now I only need 1-Degree 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-11-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-11-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.