## The non-axial projection subjection

Wednesday, October 8th, 2008 at 3:58 pm

You don’t begin a project that will take the rest of the year and more without evading it as long as you can. Finally I’ve begun to break ground on this.

Background: Almost all industrial algorithms for generating toolpaths for 3-axis machining are based on the Drop Cutter function, where the tool is lowered along its axis towards a triangulated surface until it makes contact. I have discussed this here, where I also add my usual complaint about how almost all of published academic literature on 3-axis machining is based on the contact point offset from a point in a parametric surface, and so is of no use. The problems raised by that approach are insurmountable, and you don’t need to solve them because there is a better way.

For most CAM systems, if you speed up the Drop Cutter function (which for toroidal cutters often depends on solving the quartic equation), then everything runs faster. The other determination of performance is if the implementation of the machining strategy calls this Drop Cutter function too frequently. That’s how fundamental the function is.

The only 3-axis machining algorithm that does not depend on the Drop Cutter function is the Horizontal Projection function used in the calculation of constant Z (waterline) contours. (A visualization of a bug in it is shown here.) This Horizontal Projection function finds the points of intersection when the cutter moves in the plane perpendicular to its axis. In Machining Strategist/Depocam I never solved it for the toroidal case (because I didn’t know the answer to an order six polynomial which you get instead of the quartic), and used a neat little fudge where I could get to the same answer by measuring the contours for a ball-nosed cutter and then offsetting the contour in its plane by the radius of the circular axis of the torus. In HSM Works/Adaptive Clearing I finally worked out how to do it, which is fortunate because I’m going to need it here, and there’s no way round it.

The obvious fundamental 5-axis cutter location function is shown in the diagram above. The cutter is in an arbitrary orientation (the red dotted line is its axis) and is dropped in an arbitrary direction (the thick green vector) to find the point of contact with the triangulated surface (outlined in blue).

We can transform everything into a better position and make the green vector the vertical Z-axis. Then, if the dotted red line (axis) is in line with this green vector, we’re back to the 3-axis condition. If the dotted red line is horizontal (perpendicular to the green vector), then that’s Horizontal Projection function. Otherwise we can rotate the assembly so that the dotted red line is in the X-Z plane to observe that the only new parameter we need to include is the angle between the axis of the cutter and the direction of projection. (If the red axis line is below the horizontal I’m going to reflect about the horizontal X-Y plane.)

Makes it seem simple. The interface into the big calculation engine that solves the Horizontal Projection function merely needs to take a unit 2D vector in the X-Z plane representing the tilt from the red vector to the green vector. A value of (1,0) is the Horizontal Projection, and (0,1) is the Drop Cutter function.

At least that gives it a home and a tiny tweak to the interface for the other developers to access. But there’s going to be thousands of lines of hard code coming up real soon over the next few months.

BTW this doesn’t unify the Horizontal Projection and Drop Cutter functions, because the Drop Cutter, being as fundamental as it is, is unbelievably optimized. In its case there is a rotational symmetry about the Z-axis that can be heavily exploited. Once there is a tilt from this axis, the symmetry is broken.

And so to work.

• 1. Denys Plakhotnik replies at 8th October 2008, 9:01 pm :

it is easier and faster to move a CC point over an offset surface than calculating drops. for ball-nose mill 5-axis toolpath generation is almost the same as for 3-axis. the tool orientation is added to avoid collision and reach unaccessible regions.

• 2. Julian replies at 13th October 2008, 4:40 pm :

Thanks for this comment, and the link to a paper in the last post about 5axis. I’ve added it to my library.

The conventional method for moving CC points over an offset surface fails when the model has concave corners (where the cutter positions gouge the part) and convex corners (where there are many cutter positions for one CC point).

As with autonomous robots, these obstacles are what really matter; they are not a special case to be dealt with once we have mastered locomotion along smooth undulating surfaces.

• 3. Denys Plakhotnik replies at 13th October 2008, 5:40 pm :

Bull s***, it depends on an offset algorithm only. with the good algorithm you don’t have any problems. Just first article I found

• 4. Julian replies at 13th October 2008, 9:29 pm :

I’m sure that with a “good” algorithm anything will work — by the definition of the word “good”.

However, I don’t believe there are any offsetting algorithms that are good enough. The paper you pointed to is very brief and really only discusses what to do with convex edges for completely spherical cutters.

It has nothing to say for cutters that are non-spherical where the length of the normal depends on the orientation of shaft.

And for concave edges it has only this to say:

There are two possible ways to remove the self-intersections on the offset triangular mesh. One complicated way is to remove the self-intersection in 3D spaces. The other way is to remove the self-intersection in 2D spaces after slicing by a series of planes; this way is a suitable method for 3-axis numerical control machining and a layer-based manufacturing process. The offset triangular mesh is sliced by a series of planes to get the tool path lines. Since all the gaps between the faces are joined by the blend surface, the sliced lines of the offset triangular mesh is connected a continuous loop. An invalid loop can be removed by a loop removal method of 2D milling.

In simpler terms, they are saying: “Sorry, we can’t do this part of the algorithm in 3D.”

Even the 2D method they have reduced it to is extremely hard. I wouldn’t want to code it.

It doesn’t take many issues like this, and others I haven’t mentioned, before the complexity and unreliability of the Cutter Contact point method exceeds the speed and predictability of the cutter projection method — which is the one applied in all industrial CAM kernels that I know.

• 5. Denys Plakhotnik replies at 14th October 2008, 8:25 am :

In 3-axis milling, Z plane is a ruled surface. You do drops along Z direction to surface. In 5-axis ball milling there is no exact direction, unless you use ruled surface. When you have “inverse tool-offset (ITO) surface”:

http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYR-481DWM8-FK&_user=877992&_coverDate=08%2F31%2F1989&_fmt=abstract&_orig=search&_cdi=5625&view=c&_acct=C000047079&_version=1&_urlVersion=0&_userid=877992&md5=464d38d4d40831efbab26a13e9083a15&ref=full

http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYR-3SP2NK3-G&_user=877992&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_version=1&_urlVersion=0&_userid=877992&md5=14fa546b497b62e5efdb4970c1592caf

http://dimacs.rutgers.edu/Workshops/CompAided/slides/misra1.pdf

you have the surface of feasible CL point positions. then just set collision-free inclination. Moreover, you don’t do drops while varying inclination.It seems to be enough advantage. The workflow for ball-end milling becomes “simple”:
1. offset surface
2. generate CL path on the ITO (remember each position is a gouge-free)
3. set collision-free tool orientation (visibility cone, gauss map, etc).

Unfortunately, ITO suits for 3-axis and 5-axis ball end milling only.

• 6. Julian replies at 4th November 2008, 11:51 am :

… or you conclude that the academic community has got this issue wrong and have done so for years, and go with the way it’s done in all high-end CAM software in the world — which is just as I have outlined it.

There’s a point when they will eventually be forced to take notice of this challenge to the theories — though not as dramatically as the theoretical economists have to explain the financial crisis.

Actually, it’s always surprised me how the academics don’t even seem to have the intellectual curiosity to inquire about how the commercial software works, so sure as they are of the fundamental principles, in spite of the lack of a working model.

Having written two machining kernels from the ground up that compete in the open market, I am still apparently qualified for nothing when compared to a crusty old book from the 1980s.

I don’t know of any other fields of engineering and software that are as disconnected as this.

Where is this Professor B K Choi these days? He used to publish papers about machining almost every month in CAD magazine. They were good for a laugh, because they were all of them entirely useless — for the production of practical software that worked.

• 7. Freesteel&hellip replies at 4th February 2009, 6:20 pm :

[…] Here at Freesteel Central where the fastest most parallizable CAM algorithms are being written, we’re attempting to code up valley machining which is going to rely on the not-yet-written non-axial tool projection function. […]

• 8. Live replies at 14th February 2009, 8:05 pm :

Hello Julian, thanks for your blog.
I think you are right in that the drop cutter function is the only feasible solution for the 5 axis machining. But I think that it must work not on triangulated surfaces but on parametric UV-surfaces and curves. In HSMWorks you claim the possibility to machine a part with very tight tolerances. Hou you can do this while approximating surfaces with triangles?

Sometimes things are made easier for parametric surfaces. For example, you drop the cutter on the vertices and the edges of the triangles of a triangulated surface, while a surface is smooth by definition and has sharp corners and edges only on its boundary. So you waste the time and get in result only an approximate solution.

I think in five axis environment and non axial tool projection the best solution will be to triangulate part surfaces to a very rough tolerance, not absolute but angular (The ShouldSplitTriangle returns true if n1 dot n2 < AngularTolerance), drop the cutter on this triangulation, unmap the found contact points back to the surface parameter domain and refine them by an incremental algorithm with good convergence speed.

• 9. Julian replies at 16th February 2009, 12:06 pm :

Thank you for your comments, SprutCAM. I think I can walk you through the reasoning to get to where I am from where you left off.

I agree with you that you cannot have an analytical or incrementally accurate algorithm for cutter locations against a surface without first applying an algorithm that tests against triangulations of the surfaces at a “rough” tolerance.

The reason for this is pretty obvious, but difficult to explain in a short sentence. You discover it with experience.

The argument is therefore between whether the answer given by applying the algorithm that tests against a triangulation is good enough, or if it is (as you believe) necessary to further refine it by an incremental algorithm against the original surface equations.

Do we need to apply Algorithm 1 and then Algorithm 2, or can we make Algorithm 1 strong enough that we can live without Algorithm 2?

This is something that we can prove with experience. In my experience Algorithm 1 can be made very efficient on triangles that are very small (on modern computers), with few of the instabilities that are going to happen with Algorithm 2 (in particular, when the tool passes the surface tangentially). And my code has half the complexity than one that depends on two algorithms.

You should think about the application of these calculations. The machine tools work to a tolerance of no better than, say, 0.002mm. There is no point in triangulating to a tighter tolerance than this. Modern computers have no problem with this.

Also, the machine tools make linear motions. Since that is the eventual output of the algorithms, the argument is over how far back into the algorithms to take these linear approximations.

I think the argument is exactly the same with high quality computer graphics, which are all based on triangles. If the triangles are smaller than the pixels, then you’re not going to notice anything. Computer graphics has the technique of re-triangulating to a tighter tolerance when zoomed in.

I would apply this technique first, before touching the complicated surface equations.

A lot of acceleration has been applied to triangle plotting.

Also, intuitively, the iterative technique is kind of like a local re-triangulation of the surface by the way it approximates the function locally to a straight line.

In summary: with the parameters involved (speed+capacity of computers, size of models, tolerance of machinining) the triangle only method can give indistinguishable results to the “accurate” method.

Does this make sense?

• 10. Live replies at 16th February 2009, 12:39 pm :

Hello Julian,
The non axial tool projection can not be so optimized as the 3d or 2d case. It is impossible to offset triangles first and than ray trace the offset triangles. Instead we have to check every triangle in the tool shadow. So I think that this procedure that checks every triangle in the tool shadow will spend the most time of the calculation. So, by reducing the number of checked triangles we can get a great speedup in calculation time.

There is no need to have an “exact” surface equation and even an exact tool equation to refine a cutter contact point. All we need is the 2 surface functions: function TSurface.GetPoint(const u, v: single): T3DPoint and TSurface.GetUnitNormal(const u, v: single): T3DPoint and the tool function TTool.GetCenterPoint(const ContactPoint, ContactNormal: T3DPoint): T3DPoint.

• 11. Julian replies at 16th February 2009, 2:13 pm :

You might be right. We can’t say.

I can be honest about the situation with my code. I don’t have any access to the surfaces in the CAM kernel.

The only input I have is the triangulation which is transmitted as an STL file. There are so many complexities with surfaces (I would have to implement an evaluation and unit normal of every different type, from cylinders to NURBS).

Like a lot of software development, you have to make an early bet on which way you’re going to do it, and this leaves you with no option but to make it work the way you’ve chosen.

Maybe we could arrange exchange some benchmark tests. Could this work as DLLs which we linked into each other’s code so we could run our algorithms side-by-side and compare performance, test reliability, and discover miscalculations?

• 12. Live replies at 16th February 2009, 3:24 pm :

Hello Julian,
the surfaces code is very simple, there are not so many surface types. Most of them you can find in the OpenNurbs library from Rhino.

At first I have to implement one. Today, I guess, SprutCAM is the only CAM system on the market that does not rely on the drop cutter function.

• 13. Freesteel&hellip replies at 19th February 2009, 4:32 pm :

[…] the non-axial projection function for a general cutter shape, it’s necessary to find the intersection between a line […]

• 14. anderswallin.net ›&hellip replies at 17th December 2011, 11:45 am :

[…] pockets for 2D machining/clearing of stock. The general purpose tool-location function would be a non-axial tool projection, but I'm not going there unless someone sends me a state of the art 5-axis VMC as a […]