Here's the place for discussion related to CAM/CNC and the development of the Path module.
sliptonic
Posts: 1633
Joined: Tue Oct 25, 2011 10:46 pm

kreso-t wrote:
Sat Sep 07, 2019 8:27 pm
If someone knows a decent python implementation of arc fitting alg. that would as input take a list of points/line segments + tolerance setting and as output produce the list of arcs, it would be relatively easy to include it into adaptive if all that done in python code (no need to change the interfaces to C++, etc.)
I don't know an implementation but @JulianTodd posted earlier in this thread about working out the math
kreso-t
Posts: 115
Joined: Sat Aug 04, 2018 2:32 pm

sliptonic wrote:
Sun Sep 08, 2019 3:10 pm
I don't know an implementation but @JulianTodd posted earlier in this thread about working out the math
I did not yet have time to study the @JulianTodd math in details, so I might not understand it fully - but it looks to me that it is solving a different problem: how to connect two line segments with two tangentially connected arcs. So not sure if that can be applied as a solution to what I had in mind for reducing the size of adaptive g-code. The idea here was to approximate the series of points that (approximately) fit to an arc with an actual arc (that can be defined by three points only). So potentially larger number of points would be reduced to only three points without loosing much accuracy.
RatonLaveur
Posts: 433
Joined: Wed Mar 27, 2019 10:45 am

I'm no mathematician, barely more than a pleeb in the discipline, but:

-Assuming a contiguous series of segments of roughly the same lengths (roughly being an accuracy parameter)
-The end points of a series of two consecutive segments approximate the orientation of the tangent.
-That tangent can be placed at the apex of the two segments.
-the normal to the tangent crossing that apex is therefore a radial of the arc approximate.
-the normals of all the tangents along the contiguous series of segments cross at the "most likely" center.
-The radius is defined by the lengths of all the radials from the center to the apexes.

So basically the segments are chords of the arc.

I'm afraid I'm not being groundbreaking here, but I'd rather throw that pebble in the pond than keep it in my pocket.

A cursive google search yielded some more interesting results than my babbling:

And

On another note: have been refining a bit my usage of adaptive with the laser. Pretty cool results, can't wait for your accuracy update. I'm sure it will be a killer
dubstar-04
Posts: 414
Joined: Mon Mar 04, 2013 8:41 pm
Location: Manchester, UK
Contact:

kreso-t wrote:
Tue Sep 10, 2019 5:38 pm
sliptonic wrote:
Sun Sep 08, 2019 3:10 pm
I don't know an implementation but @JulianTodd posted earlier in this thread about working out the math
I did not yet have time to study the @JulianTodd math in details, so I might not understand it fully - but it looks to me that it is solving a different problem: how to connect two line segments with two tangentially connected arcs. So not sure if that can be applied as a solution to what I had in mind for reducing the size of adaptive g-code. The idea here was to approximate the series of points that (approximately) fit to an arc with an actual arc (that can be defined by three points only). So potentially larger number of points would be reduced to only three points without loosing much accuracy.
I had a quick look at converting the paths to arc moves. The method I chose was to pass the first (pt1), mid (pt2) and last (pt3) points of a path segment to a function. That function does the following:

1. Calculate lines pt1->pt2 and pt2->pt3
2. Determine the mid point of those lines
3. Calculate lines perpendicular to the mid point of the lines
4. Calculate the intersection of those perpendicular lines (arc centre)
5. Determine if the arc direction is clockwise or anticlockwise

This gives the centre of the arc and allows the calculation of the I and J values, arc direction determins G2 or G3.

Results below:
Std-Adaptive.png (13.81 KiB) Viewed 551 times
Arc-Adaptive.png (14.05 KiB) Viewed 551 times
Issues:

1. Many
2. Path segments contain a mixture of straight and arc segments

I think it needs a more flexible approach to determine straight segments and check that all points of an arc are equidistant from the calculated centre.
Last edited by dubstar-04 on Thu Sep 12, 2019 5:05 am, edited 1 time in total.
chrisb
Posts: 21334
Joined: Tue Mar 17, 2015 9:14 am

This is highly appreciated by me, who does not have endless memory in his CNC. Additional it makes simulation at the machine simpler, where e.g. single lines are executed one by one.
kreso-t
Posts: 115
Joined: Sat Aug 04, 2018 2:32 pm

Hi,

I think the following may work:
i.e. lets say we have array of N points pt1,pt2, ... ptN and want to find an arc that approx fits as many as possible points starting from pt1
1. we take pt1,pt2 and pt3 and find the center point of arc that fits that these points, let call it c1
2. then we take pt2, pt3, pt4 and do the same -> we get c2
3. calculate avg./midpoint of center points c1 and c2 -> c_avg
3. find the line having each point equally distant from pt1 and pt2 and on that line find the point that is closest to c_avg, use that point as the actual arc center -> ca
4. check if all pt1 ... pt4 fits within tolerance to the arc defined by pt1, pt4 and ca (center)
5. if so, repeat the same from step 2 for points pt3, pt4, pt5 (we get another center c3, and new c_avg (from c1,c2,c3) and new ca, arc spanning the pt1...pt5)
repeat that steps 2-5 until we find the that some point does not fit within defined tolerance, then we add the previous (fitting ok) arc to output, remove points that fit to it and start again with the remaining points. If only two points remain add a line segment to output (the same in case when some three subsequent points are collinear).

I'll try it in the next days to see if it actually works. Also I'll see if I can use some of the math from http://www.maths-in-industry.org/miis/6 ... 104_P7.pdf suggested by @RatonLaveur, this looks helpful, ty

BR
K.
kreso-t
Posts: 115
Joined: Sat Aug 04, 2018 2:32 pm

dubstar-04 wrote:
Tue Sep 10, 2019 9:46 pm

I had a quick look at converting the paths to arc moves. The method I chose was to pass the first (pt1), mid (pt2) and last (pt3) points of a path segment to a function. That function does the following:

1. Calculate lines pt1->pt2 and pt2->pt3
2. Determine the mid point of those lines
3. Calculate lines perpendicular to the mid point of the lines
4. Calculate the intersection of those perpendicular lines (arc centre)
5. Determine if the arc direction is clockwise or anticlockwise

This gives the centre of the arc and allows the calculation of the I and J values, arc direction determins G2 or G3.

Results below:

Issues:

1. Many
2. Path segments contain a mixture of straight and arc segments

I think it needs a more flexible approach to determine straight segments and check that all points of an arc are equidistant from the calculated centre.
Hi Dan,

Actually your implementation looks quite promissing. As you are already ahead with this, maybe to include some of these ideas into your implementation if you have time, so that we don't do the same thing in parallel?

Thx,
BR,
K.
dubstar-04
Posts: 414
Joined: Mon Mar 04, 2013 8:41 pm
Location: Manchester, UK
Contact:

kreso-t wrote:
Mon Sep 16, 2019 12:36 pm
dubstar-04 wrote:
Tue Sep 10, 2019 9:46 pm

I had a quick look at converting the paths to arc moves. The method I chose was to pass the first (pt1), mid (pt2) and last (pt3) points of a path segment to a function. That function does the following:

1. Calculate lines pt1->pt2 and pt2->pt3
2. Determine the mid point of those lines
3. Calculate lines perpendicular to the mid point of the lines
4. Calculate the intersection of those perpendicular lines (arc centre)
5. Determine if the arc direction is clockwise or anticlockwise

This gives the centre of the arc and allows the calculation of the I and J values, arc direction determins G2 or G3.

Results below:

Issues:

1. Many
2. Path segments contain a mixture of straight and arc segments

I think it needs a more flexible approach to determine straight segments and check that all points of an arc are equidistant from the calculated centre.
Hi Dan,

Actually your implementation looks quite promissing. As you are already ahead with this, maybe to include some of these ideas into your implementation if you have time, so that we don't do the same thing in parallel?

Thx,
BR,
K.
I don't have any FreeCAD time for a month or so but I can look at it then.

I did some further work on this that gave interesting results.

1. Check if the first two points are more that 1/2 tool dia apart, if so consider it a line segment and go to 5, if not go to 2
2. Check if pt2 lies on a line between pt1 and pt3 (or is +/- a tolerance from the line), if not go to 3 if it does check pt4... ...ptN until one doesn't fit and go to 5
3. Get the arc centre point from pt1, pt2 and pt3 using method from previous post.
4. Check if pt4, pt5... ...ptN are part of the arc formed by pt1 to pt3, by checking the distance from the arc centre to selected point +/- a tolerance. On finding a point that doesn't fit the arc go 5
5. Start the process again with the last point.

This method looks like it might work but it will take some time to test and refine.

Thanks,

Dan
sliptonic
Posts: 1633
Joined: Tue Oct 25, 2011 10:46 pm