topic Re: tracing the edge of a cutting tool (toolpath) in Mathcad

tracing the edge of a cutting tool (toolpath)

RogerYeh — Thu, 03 May 2018 16:22:32 GMT

I imagine there must be a proper way to do this, but I wasn't able to look up a good (or any) algorithm.Imagine you're cutting something on a mill. You specify a trajectory for the cutting tool. You're interested in the edges of the tool as it goes along the trajectory.

Re: tracing the edge of a cutting tool (toolpath)

RichardJ — Tue, 25 Mar 2014 20:06:16 GMT

For each line segment, check if it intersects with any previous line segment. If it does, insert a new point at the intersection, and remove all the points between (but not including) the start of the earlier segment and the end of the later segment.

Re: tracing the edge of a cutting tool (toolpath)

Werner_E — Tue, 25 Mar 2014 21:32:40 GMT

If the trajectory itself is allowed to loop, this algorithm may remove to many points of the path.

How should this case be handled?

Re: tracing the edge of a cutting tool (toolpath)

RogerYeh — Tue, 25 Mar 2014 21:46:43 GMT

Haha, that's a good point! Let's assume the trajectory doesn't loop. I think that's safe to say for typical machining practices. But this brings up another point. Often times the cutting tool will go in a trajectory where the path will overlap itself. Let's also assume that doesn't happen.

I'm looking into the equations for intersecting line segments:

http://en.wikipedia.org/wiki/Line-line_intersection

Re: tracing the edge of a cutting tool (toolpath)

Werner_E — Tue, 25 Mar 2014 21:58:58 GMT

Maybe I am misunderstanding what you just wrote, but if you assume the the path will not overlap itself, then you won't have the problem you are trying to solve here anyway!? Don't those summits and loops in those parallel curves of the trajectory arise exactly from an overlapping path?

Another algorithm just comes to my mind, but it sure is not very efficient and probably very slow. First build you green and red paths. Then go along your trajectory and for every point in the trajectory set the coordinates for all points in both paths, which are within a distance of R from the point on trajectory, to NaN. Later use filterNaN() to delete those array elements. Its sort of letting Mathcad play milling machine.

To increase accuracy of the result you may additionally add points on the circumfence of the circle for those line segments where one point is inside and the other outside of the circle.

Re: tracing the edge of a cutting tool (toolpath)

RichardJ — Tue, 25 Mar 2014 22:25:53 GMT

Good point. Tricky problem

Re: tracing the edge of a cutting tool (toolpath)

RogerYeh — Tue, 25 Mar 2014 22:29:20 GMT

Yeah, I realized that I wasn't being very clear. I was trying to say we can rule out these types of cases:

I actually like your algorithm. It'll be slower than Richard's method (I think), but it'd be easier to code up. For the number of points that I'll be working with, it probably won't be too bad. And I like your milling analogy. Very appropriate!

Re: tracing the edge of a cutting tool (toolpath)

Werner_E — Tue, 25 Mar 2014 22:39:27 GMT

I guess my algo would deal with all those cases, too. You just have to takle care of numerical inaccuracies - just use a slightly smaller radius when you delete the points just to be sure that points ON the circle (and every path point would be on at least one circle) will survive.

Re: tracing the edge of a cutting tool (toolpath)

RichardJ — Tue, 25 Mar 2014 22:42:05 GMT

A slight modification to what you suggest:

First go along both the red and green lines and check for any intersection with either another segment in the green line, or another segment in the red line. Add points at all those intersections. Any such points that are within the circles will get deleted at the next step anyway, but those that are not will accurately define sharp corners.

Re: tracing the edge of a cutting tool (toolpath)

Werner_E — Tue, 25 Mar 2014 22:45:54 GMT

Good idea. I guess every point of intersection will be added twice to the list and at the end both will have survived. So the last phase of the algorithm would be the deletion of those duplicates.

Re: tracing the edge of a cutting tool (toolpath)

RichardJ — Tue, 25 Mar 2014 23:04:43 GMT

There is another modification that would improve the accuracy of the final shape a lot. As the paths are built, instead of just adding two points on each side of the path, divide the circle circumference into N equal segments, and add a point for each segment (with the new points of course oriented relative to the path direction just as the current two points are). All thre points on one half of the circle belong to the green line, all the points on the other side belong to the red line. The line will look really ugly before point deletion, and this will slow down the step of deleting points, but the start and end of the tool path, and the tool path for any sharp turns (such as the 90 degree turns in the example above) will be much more accurately represented. The higher N, the more accurate the path, but the slower the algorithm. This could cause weird artefacts if successive circles are too far apart, but if that happens either more circles could be added, or N could be reduced.

Also, instead of marking the points to be deleted as a NaN, it might be faster to delete them on the fly. That way, they don't get checked a second time. The relative speed of the two approaches probably depends on the shape of the path though.

Re: tracing the edge of a cutting tool (toolpath)

Werner_E — Wed, 26 Mar 2014 21:51:27 GMT

Is the problem still vacant?

Attached is just another way to get the paths - no cleaned path yet and no intermediate point for better precison added. I guess this approach using complex numbers might be a bit speedier than calculating and using the angles between the segments. As complex numbers give us in a more natural way an oriented angle between segments it might also be easier to add intermediate point where necessary (on the "outside") - not yet(?) implemented.

Concerning the algorithm to eliminate the "inner" path segments, I begin more and more to dislike "my" brute force approach. Apart from speed I guess it also will remove to much, as the way we construct the path will result just at an approximation of the convex hull and so many points may lie inside the hull and would be errenaously eliminated.

In case its still of concern - I have another approach in mind but I am absolutely not sure if it works for all cases: First I would add half circles at both ends and make one continuous, closed, oriented graph. Then we begin at one arbitrary point and go along the graph until we get a a point where the graph crosses itself. We add that point to the graph (twice) and then we change the branch, that is we ar now going (again in the given direction) at the second part of the crosing branches, coming back later to deal with the other branch (a recursive approach seems adequate here). This we do until we arrive at the starting point. That way we have created a subpath which is closed and lies either completely inside (as will be removed later) or outside. As we always come back to the points of crossing, at the end we will have splitted our path in a couple of closed loops which should either survive completely or ar eto be deleted as a whole. All wee would need now is a reliable way to decide whether a specific partial is to be deleted or not.

Its a pity we don't have pointers and the necessary data structures in Mathcad to create those various chained lists, but it should be doable using various vectors containing just the indices into the data vectors. Unfortunately inserting data points in a matrix is rather time consuming if we use submatrix and stack - we had some threads here that have shown that even self written routines using for-loops are speedier.

Any comments?

BTW, what is the final aim? What would that "cleaned up" path would be used for?

Re: tracing the edge of a cutting tool (toolpath)

RichardJ — Wed, 26 Mar 2014 22:31:00 GMT

Then we begin at one arbitrary point and go along the graph until we get a a point where the graph crosses itself. We add that point to the graph (twice) and then we change the branch, that is we ar now going (again in the given direction)

I thought about that yesterday, but I couldn't figure out how to decide which way to go at an intersection. I think I've got it figured out now though. Using your "loop" as an example, at the start of the path, when facing in the direction of travel, the green line is on the "right", and the red line is on the "left" (not exactly a mathematical way of putting it, but I'm after the concept at this point). If we start on the green line then when we get to an intersection we always make a "right turn". This forces the path to be on the outer perimeter, and we will eventually get back to the start. If we start on the red line, we always make a "left turn' at an intersection. So to summarize, if we start on the left we always make make left turns, and if we start on the right we always make right turns.

Re: tracing the edge of a cutting tool (toolpath)

Werner_E — Wed, 26 Mar 2014 22:54:36 GMT

My approach would be that the whole path (green and red) is a closed loop - the half circles at the ends close it and that loop has an orientation (= the order in the vector, so one of the two halves has to be reversed before we combine them) . When we come to an intersection, I simply change the path, but I still go in the direction of this orientation. So if I start at point number 0 and arrive at an intersection segment 50-51 crosses segment 200-201, Then the point of intersection is calculated and inserted as point 51 AND as point 202 (old point number 51 is now 52, old 200 therefore gets 201, second new point will be 202). I remember (recursion started) point 51 as the start of a new subpath and continue the current subpath with 202 (the newly added), 203, etc. Eventually we will arrive at the last point of our list (after all we have a vector, not a closed chained list) and should add the starting point as endpoint. The points used should be removed or set to NaN as soon as they are processed, in every case as soon as we arrive at a cross point and start a new recursive call. At least I think so, or better, I feel its more safe to do so.

At the moment I am missing the time to implement it and to be honest I am not fully convinced that it covers all possible paths.

Re: tracing the edge of a cutting tool (toolpath)

RichardJ — Wed, 26 Mar 2014 23:19:20 GMT

At the moment I am missing the time to implement it and to be honest I am not fully convinced that it covers all possible paths.

Ditto (for my approach), on both counts. It's an interesting problem, but the main reason it's interesting is that a robust solution is not obvious.

Re: tracing the edge of a cutting tool (toolpath)

ptc-4954463 — Thu, 27 Mar 2014 18:03:14 GMT

Hi Gentlemen,

Could somebody help me on solving this? I only need the envelop of the left boundary. I used above methods (see attached), but could not get a correct curve around y=0 when cuting circles were large. I calculated manually like the following picture, and got a reasonable curve. Thanks.

Regards,

Jun

Re: tracing the edge of a cutting tool (toolpath)

Werner_E — Thu, 27 Mar 2014 18:40:20 GMT

So why don't you implement your algorithm here and see what you get?

Re: tracing the edge of a cutting tool (toolpath)

ptc-4954463 — Thu, 27 Mar 2014 18:48:08 GMT

Because I am a Mathcad beginner. I can not finish it by myself now. I calculated 40 points to get a rough curve. I want to calculate it using Mathcad.

Re: tracing the edge of a cutting tool (toolpath)

Werner_E — Thu, 27 Mar 2014 20:04:42 GMT

I see. But the algorithm you propose seems to be not generally applicable for the problem in this thread and it looks like its a very time consuming one. Furthermore you would need a rather dense net of circles to get good results as you algorithm would follow slavishly the segments of the circles and not the milling path itself.

May I ask in which application this problem cam up for you and what you intend to do with the created outline path? In which way you would use it?

Re: tracing the edge of a cutting tool (toolpath)

ptc-4954463 — Fri, 28 Mar 2014 12:39:41 GMT

Thanks for your comment, yes, it may be time consuming. It is part of a special joint.