New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

5-axis simulation #17

Open
jcoffland opened this Issue Mar 10, 2014 · 51 comments

Comments

Projects
None yet
6 participants
@jcoffland
Copy link
Member

jcoffland commented Mar 10, 2014

This is difficult

@jcoffland jcoffland self-assigned this Mar 10, 2014

@stustev

This comment has been minimized.

Copy link

stustev commented Mar 25, 2014

What is the difficult part to this?

@jcoffland

This comment has been minimized.

Copy link
Member

jcoffland commented Mar 25, 2014

That's hard to explain. I believe I've got it worked out in my head but there is a significant amount of programming to do. First of all we need to be able to define the mechanics of the axes. I.e. how long are the extra to joints. Do some research and you will find that this topic has been studied for the last 30 years and it's still being perfected. There are methods but most of them are inefficient. I had to come up with a new algorithm for the efficient 3-axis system CAMotics uses.

@NateTG

This comment has been minimized.

Copy link

NateTG commented Jan 12, 2015

It seems like if you want to do this in a generic fashion, you could try specifying the axes as kinetic pairs. Still seems nasty.

@jcoffland

This comment has been minimized.

Copy link
Member

jcoffland commented Jan 12, 2015

Do you mean http://en.wikipedia.org/wiki/Kinematic_pair? You'd have to understand my algorithm in order to solve this problem.

If I could find a solution to the question, "is point P inside the sweep of tool path segment S given tool T?" for the case where S is a movement in 5-axis not just 3, then my current algorithm would work for 5-axis with minor changes. I've figured out solutions to this problem for various tool shapes for 3-axis moves but not for the general case with 5-axis moves.

Note that the key advantage to my algorithm for 3-axis simulation is that it asks the question, "is there a point in the tool sweep that passes through point P." Rather than, "where in the tool sweep is point P?" Questions of existence are generally much cheaper to answer. This is the key to CAMotics's simulation speed.

To formalize this say we have a tool path segment S which moves linearly from point (Xa,Ya,Za) to point (Xb,Yb,Zb) with a linear rotation about two axes start at angles (Aa,Ba) and ending with angles (Ab,Bb). So we have:

S = (Xa,Ya,Za,Aa,Ba) -> (Xb,Yb,Zb,Ab,Bb)

Let point P be (x,y,z) and we define tool T as a conical section who's tip is on the segment S with tool length l and a radius of Rt at the top (i.e. distance l from segment S) and Rb at the bottom (i.e. the point on segment S). Then we have:

P = (x,y,z)
T = (l,Rt,Rb)

Then the question is, does the sweep of T along S contain P.

P ∋ sweep(S, T)

The more obvious method is to find the closest point on the surface of sweep(S, T) to P or similarly the closest point on the segment S and then by measuring distances determine if P ∋ sweep(S, T). However, such solutions have poor performance. All we need to know is, is there such a point in sweep(S, T) that passes through P not precisely when or where on the sweep it exists.

I've figured this out for the case where (Aa,Ba) = (Ab,Bb). If someone could help me find a solution for the general case I could implement 5-axis simulation in a matter of days. At least for the case where the axis moves are linear. In other words, where all axis moves occur at a constant rate throughout the path segment. Note, that G-Code moves fit this bill.

In CAMotics arcs are simulated as many small straight line segments. One option would be to simply treat 5-axis rotations in the same way as arcs in 3-axis by break them up in to straight line segments with fixed rotations. This would leave tiny jagged edges where adjustments in rotation were made, just like arcs have tiny corners if you zoom in close enough. It is a valid solution and it's possible that it would be good enough. Plus you can vary the accuracy at the cost of speed. I'm afraid that the performance penalties would be significant. It really depends a lot on the type of 5-axis moves. I haven't tried this yet.

Certainly there are other ways to solve this but I would like to retain the elegance, speed and scalability of my current algorithm. Many of the algorithms I found in the available literature (this has been an active area of research for over 30 years) are very complicated to implement in code and less efficient than my solution. The guys publishing papers on this topic like to use heavy duty mathematical tools that are cheap to use on paper but very expensive to implement in code, even if the algorithmic complexity of their solutions are sufficiently low in theory.

@jcoffland

This comment has been minimized.

@NateTG

This comment has been minimized.

Copy link

NateTG commented Jan 13, 2015

Certainly there are other ways to solve this but I would like to retain the elegance, speed and scalability of my current algorithm. ...

There are many ways to attack this sort of problem, can you briefly describe the approach you're currently using?

To formalize this say we have a tool path segment S which moves linearly from point (Xa,Ya,Za) to > point (Xb,Yb,Zb) with a linear rotation about two axes start at angles (Aa,Ba) and ending with
angles (Ab,Bb)

Maybe I'm not understanding, but it seems like we need information about the axes of rotation, and whether they move with the table or not. (Consider, for example, the difference between machines with tilting heads and trunion tables.) Obviously the motion can be coordinate transformed, but I'm not sure that that transformation would be 'linear'.

@jcoffland

This comment has been minimized.

Copy link
Member

jcoffland commented Jan 13, 2015

Well, the above was sort of an outline of the core of the algorithm. I need to document the full algorithm more throughly.

With regards to simulation it does not really matter how the machine moves. The movement of the tool relative to the part is what that matters. You can always choose to view the part as stationary and represent relative tool positions as (X,Y,Z,A,B). You can even view a 4-axis machine this way. You may need to do some preprocessing to translate from axis moves (i.e. GCode) to tool positions. That part is not too difficult.

@NateTG

This comment has been minimized.

Copy link

NateTG commented Jan 13, 2015

You can always choose to view the part as stationary and represent relative tool positions as (X,Y,Z,A,B). You can even view a 4-axis machine this way.

Ok, let's assume the part is stationary. Now, let' say the angles are in degrees and I move from (0,0,0,0,0) to (0,0,0,45,45). Let's say that the cirlces on the concial frustrum of the tool are initially horizontal, and that the center of the top is initially at (0,0,0). What are the x y and z coordinates of the center of the top after the the move?

You may need to do some preprocessing to translate from axis moves (i.e. GCode) to tool positions. That part is not too difficult.

Right, but the translation is not linear. Let's imagine that I'm cutting the outside of a cylinder with a square nose end mill using the 4th axis. On a machine with a trunion table, I can simply cut the cylinder by using the turntable so the parametrized path is, say (0,0,0,-45+t,0), but with a tilting head, it's got to be something like (l_cos(-45+t),0,l_sin(-45+t),-45+t,0). So, unless the controller handles the interpolation for you, you'll need to something a little clever there.

@jcoffland

This comment has been minimized.

Copy link
Member

jcoffland commented Jan 13, 2015

You have to translate from axis moves to tool positions. This is machine specific though.

@NateTG

This comment has been minimized.

Copy link

NateTG commented Jan 13, 2015

Well, the above was sort of an outline of the core of the algorithm. I need to document the full algorithm more throughly.

I think I understand now.

For a three axis machine the path that a conical frustrum tool traces out is covered by five (possibly degenerate) volumes:

  1. The skewed cylinder traced out by the top of the conical frustrum.
  2. The skewed cylinder traced out by the bottom of the conical frustrum.
  3. The tool's intital position.
  4. The tool's final position.
  5. A skewed trapezoidal prism traced out by some vertical section of the tool profile.

And it's very easy and fast to check whether S is in any of those regions. This readily generalizes to any piecewise convex cylindrically symmetric cutting tool.

So what you're looking for to handle 4-5 axis movement is a similarly elegant cover that incorporates changes in the tool angle.

@NateTG

This comment has been minimized.

Copy link

NateTG commented Jan 15, 2015

Have you considered the special case of a simple rotary movement where the axis of rotation is perpendicular to and crosses the axis of the tool and the axis of rotation is outside the tool?

It's pretty easy to work out computationally tests that are computationally reasonable per point to see whether a point is in the volume swept out by the move.

@Breefield

This comment has been minimized.

Copy link

Breefield commented Jan 15, 2015

I just followed a suggestion on r/cnc for CAMotics to here, holy shit this is some complicated stuff. I don't use this software yet (may be soon) and wanted to say thank you in advance for putting so much hard work in on this 👍

@jcoffland

This comment has been minimized.

Copy link
Member

jcoffland commented Jan 15, 2015

@NateTG Are you talking about Lathe like simulation? This is actually not too difficult and is on my list.
@Breefield Welcome.

@NateTG

This comment has been minimized.

Copy link

NateTG commented Jan 15, 2015

I'm not sure what you mean by lathe like simulation. It's like a centered trunion table or tilting head.

Let's say that I've got a cylindrical cutting tool with radius 1.5 that's and axis from (0,0,1) to (0,0,2) and I rotate it 90 degrees counterclockwise about the x axis so that the tool axis ends up at (0,-1,0) to (0,-2,0).

Then for some arbitrary point S=(x,y,z) it's pretty easy to test whether S is in the region that's swept through by the tool:

If x^2+y^2+z^2 > 1.5^2 + 2^2 then S is not in the path.
If x>1.5 then S is not in the path.
If x<1.5 then S is not in the path.
If y^2+z^2<1 then S is not in the path.
If z>2 and y<-2 then S is not in the path.
S is not in the path unless
   z>1 and x^2+y^2<1.5^2 or
   z>0 and y<0 or
   y<-1 and x^2+z^2<1.5^2

It shold be possible to generalize that to conical frustrum tools, and two dimensional angle changes.

@jcoffland

This comment has been minimized.

Copy link
Member

jcoffland commented Jan 15, 2015

What if the tool is also moving in the x and y axis at the same time. The you have some sort of crazy squished spiral shape. The basic single axis moves for 3-axis simulation are also pretty easy to reason about. Multi axis moves are the hard part.

@NateTG

This comment has been minimized.

Copy link

NateTG commented Jan 15, 2015

What if the tool is also moving in the x and y axis at the same time? ...

I may be misreading things, but that sort of question didn't seem to bother you when it came to accounting for x and y motion that was coincident with angular movement in a particular machining set-up.

There's a conceptually simple way to interpolate a generic path as alternating 'circular' and linear moves, but it wouldn't be satisfactory for paths with high helicity, and if you have a good way to do helical segments (like a lathe with a lead screw) then there's a realtively clean interpolation. Off the cuff, I'm not sure how computationally heavy the interpolation proper is.

@jcoffland

This comment has been minimized.

Copy link
Member

jcoffland commented Jan 15, 2015

@NateTG I side step the issue of handing arcs by breaking them up into straight line segments, which as I mentioned before, could be used to solve the 5-axis problem as well. However, I do handle movements in multiple axes, i.e. moving in X, Y & Z all at once. I solved this using a fairly simple formula, much like you suggested with your formula for a simple 5-axis rotation. I haven't yet figured out a general algorithm/formula for sweeps of conical sections like this which works when adding in the A and B rotational axes unless these axes remain stationary through the move segment.

If A & B rotations remain constant through a segment of the move we could handle their rotations simply by first rotating space using a 4x4 matrix and then solving the 3-axis problem as usual. This method could be used to approximate 5-axis by breaking up the rotational moves into short line segments where we pretend the A & B axis are constant, just like we pretend arcs are made up of tiny straight line segments. The smaller the segments the closer we are to the real move which allows for an adjustable accuracy vs. speed tradeoff.

I have not yet tried this method. My concerns are:

  1. If rotations while moving in other axes is common then the the number of line segments will grow rapidly causing the simulation to slow or accuracy to suffer.
  2. Each line segment will also need a 4x4 rotation matrix, greatly increasing the memory cost. This could be mitigated by sharing rotation matrices with the same value or by computing the rotations on the fly.

I've now realized that I missed something important in the discussion above. In addition to the angles of rotation, we also need to know the distance from the tip of the tool to the axis of rotation for both the A and B axes. We can add these to the tool specification as La and Lb. Note, such rotations can still be represented by 4x4 matrices.

Ideally, I'd like to have a formula which solves the 5-axis problem directly, for a single point at a time. Such a formula would eliminate the two problems mentioned above. Basically I have a function that looks like this:

Constant3AxisSweepContains(S, T, P) -> true or false

where:

S = (Xa,Ya,Za) -> (Xb,Yb,Zb)
P = (Xp,Yp,Zp)
T = (L,Rt,Rb)

As above, (X,Y,Z) denotes a point in 3D space and T is a tool represented as a conic section with length L and radii Rt and Rb.

But I need this:

Constant5AxisSweepContains(S, T, P) -> true or false

where:

S = (Xa,Ya,Za,Aa,Ba) -> (Xb,Yb,Zb,Ab,Bb)
T = (L,Rt,Rb,La,Lb)

As above, the As and Bs are angles. Again I'm calling these moves constant because all three axes and the two angles move from their starting a position to their ending b position at a constant rate.

As a side note, the constant restriction could be relaxed as long as the axes move constantly relative to one another. In other words, ramping the speed up and down would be ok as long as all 5-axes ramp up and down at the same rate. In this case, the sweep is the same. Small deviations are likely in real machines and would mean proportionately less accurate simulations. Large deviations, such as the X, Y & Z axes ramping up in 2 seconds but the A & B axes ramping up in 10 milliseconds, would be a problem.

I think we are getting closer to a clear formulation of the problem. Of course we are still zoomed down at a very low-level in the larger algorithm. I have yet to describe how this formula is used to solve the larger problem but with regards to extending the existing algorithm to 5-axes while keeping the current benefits, this is the important part.

@NateTG

This comment has been minimized.

Copy link

NateTG commented Jan 16, 2015

Yeah, I think we're mostly on the same page. I should note that the center of rotation can be off-axis from the cutting tool, but we can certainly call that a 'machine thing'.

It would call it 'linear parametrization'. The ramping issue is definitely a per-machine thing.

I'm thinking there may be something better than a straight matrix to describe the translation for use in processing. I'll think about it more.

@jcoffland

This comment has been minimized.

Copy link
Member

jcoffland commented Jan 16, 2015

I'm not 100% sure about off axis rotations. If you look at the tool position relative to the part at any give point in time it can be described by (X,Y,Z,A,B) regardless of the mechanics of the machine. So that's not a problem for the solution were we reduce each move to a series of small straight line segments. However, machine mechanics might be a problem for the implementation of a Constant5AxisSweepContains(S, T, P) function.

One possible improvement would be to pretend the tool actually had a smaller size in both diameter and length. Then check if it collides with the point in question. Iff the point collides with the full sized tool but not with the slightly smaller tool then you know it's near the edge and you can do a more accurate computation using smaller line segments. If it collides with both small and full sized tools then more accuracy is unnecessary.

@NateTG

This comment has been minimized.

Copy link

NateTG commented Jan 16, 2015

I'm not 100% sure about off axis rotations. If you look at the tool position relative to the part at any give point in time it can be described by (X,Y,Z,A,B) regardless of the mechanics of the machine.

Yes, although it's a little ambiguous how those coordinates indicate the position of the tool.

One possible improvement would be to pretend the tool actually had a smaller size in both diameter and length...

Or you could pick a set of spheres that contain the entire tool, and a set of spheres that are contained in it...

@NateTG

This comment has been minimized.

Copy link

NateTG commented Jan 20, 2015

Hmm... I've been thinking on this. Is there a "treat every move with rotation as a rotation about a fixed point" one of the approaches in your survey of the litterature?

@jcoffland

This comment has been minimized.

Copy link
Member

jcoffland commented Jan 20, 2015

@NateTG I think this is common. I don't remember. It's not that difficult to translate from axis coordinates to tool coordinates. By doing so you avoid making the algorithm dependent on the mechanics of the machine. Although I suppose you could also create an algorithm with an idea of general multi axis mechanics. One of it's inputs would then have to be some sort of machine specification.

Are you interested in this because you would like to have an Open-Source 5-axis simulator?

@NateTG

This comment has been minimized.

Copy link

NateTG commented Jan 20, 2015

... One of it's inputs would then have to be some sort of machine specification.

My experience with multi-axis machines is very limited, but because there is some variety in set-ups, I get the impression that would be necessary regardless of how the simulation works.

Are you interested in this because you would like to have an Open-Source 5-axis simulator?]

Somewhat - I did some serious thinking about computer assisted machining on a 4 axis machine, and, although I was too lazy to do any real implementation, a simulator would have been handy. Mostly I'm intrigued by the question as an exercise in math and computer science.

@jcoffland

This comment has been minimized.

Copy link
Member

jcoffland commented Jan 21, 2015

It should be easy to factor out the machine configuration from the algorithm by preprocessing the data. For example, if we know that the A an B axes rotate about the same point and both are length L from the point of rotation to the tip of the tool. Then we can apply the following transformations to the X, Y & Z axis positions to get the tool actual position:

  1. Translate -L on the Z axis.
  2. Apply A rotation.
  3. Apply B rotation.
  4. Translate L on the Z axis.

Of course more complicated machines would require more complicated transformations.

@NateTG

This comment has been minimized.

Copy link

NateTG commented Jan 21, 2015

It should be easy to factor out the machine configuration from the algorithm by preprocessing the data.

Yes. That's the sort of thing that might be described in terms of kinematic pairs.

Regarding the motion proper, I've worked something out that looks like it has potential: Every move with rotation has an equivalent 'lathe like' move (with arbitrary tool orientation) about an axis. That means that the volume swept out by the tool should be composed from conic sections revolved about that axis and some bounds.

Can we discuss what kinds of computational cost is acceptable per move (i.e. once per X Y Z A B -> X Y Z A B) and what kinds of computational cost is acceptable per test point?

@jcoffland

This comment has been minimized.

Copy link
Member

jcoffland commented Jan 21, 2015

Such operations should be constant time or at least constant amortized time. However, that's not always possible. The current algorithm does a look up in to a AABB (Axis-Aligned Bounding Box) tree in order to reduce the number of paths it needs to compare to the current target point. This is on the order of O(ln(|P|)) where P is the set of paths. This lookup returns a set of paths who's tool sweep might intersect the point including all of those which do. There are better algorithms which could improve on this slightly. One of the key features of my current algorithm is that you can trade simulation speed for accuracy.

A problem with looking at a sweep in one axis at a time is that it doesn't account for the interaction of movements of multiple axes at the same time, which is the hard part. However, if you think you are on to something and you can explain it, don't let me derail you.

If you want I can send you a stack of PDFs on the topic of CNC simulation that you wont have easy access to unless you are associated with a university. Most of them are on 3-axis simulation but some discuss 5 as well. One paper contains a method using calculus to compute the surface of the tool sweep. However, that method isn't great because it's not cheap to compute boolean operations on very complex polyhedra.

As I said before ideally I'd like to expand upon my existing method. If we could describe all moves as something reasonable like helices (or straight line segments) and then come up with a relative simple formula for checking if a helical sweep of a conic section intersects a given point then we would have the makings of a highly efficient algorithm. Really, I already know how to do it by reducing all moves to short straight line segments I'm just not totally convinced that's efficient enough at reasonable accuracy in 5-axes but I haven't tried it out in code either.

As a side note, one important step is gathering some real 5-axis tool paths. Preferably in GCode format.

@NateTG

This comment has been minimized.

Copy link

NateTG commented Jan 21, 2015

A problem with looking at a sweep in one axis at a time is that it doesn't account for the interaction > of movements of multiple axes at the same time, which is the hard part. ...
If we could describe all moves as something reasonable like helices (or straight line segments)
and then come up with a relative simple formula for checking if a helical sweep of a conic section
intersects a given point then we would have the makings of a highly efficient algorithm.

Turning everything into a helical move isn't that hard, conceptually speaking:

I don't like specifying a position as (X,Y,Z,A,B) because the center of rotation isn't clear. So I'm going to specify it as (X,Y,Z,x,y,z) where X,Y,Z is the position of the center of the base of the tool, and x,y,z is the position of the tip of the tool. It should be easy to see that this completely specifies the position of the tool. (Technically one of those coordinates is unnecessary because (X-x)^2+(Y-y)^2+(Z-z)^2 is fixed by the tool length.)

With that notation, and a limit on the amount of rotation per move we can think of a simple move as taking the tool from (X0,Y0,Z0,x0,y0,z0) to (X1,Y1,Z1,x1,y1,z1).

If (X1-x1,Y1-y1,Z1-z1) is equal to (X0-x0,Y0-y0,Z0-z0) then it's a linear move (a degenerate helix), and you've already dealt with that case.

Otherise, if the move follows a rigid helical path then the axis of rotation must be parallel to the cross product (X1-x1,Y1-y1,Z1-z1) X (X0-x0,Y0-y0,Z0-z0), and if we normalize the tool length, then the magnitude of the cross product is equal to the sine of the angle that is rotated through.

Now normalize the axis vector and call it (Ax,Ay,Az). Then the axial travel along the helix is Ax(X1-X0)+Ay(Y1-Y0)+Az(Z1-Z0).

From there it's a simple system of linear equations to find the position of the axis of rotation.

Of course there are some less than ideal aspects to this:

  1. The path of travel is not the same as linearly interpolating from the start coordinates to the end coordinates. This is a consequence of ambiguities in how the movements are specified, and can be addressed by limiting the angle change in each segment.
  2. The orientation of the tool relative to the helical movement is arbitrary. That means sophistication will be needed to handle the geometry of the volume that is swept out.
  3. As written, the calculations involve normalizing a vector which can be computationally expensive because it involves square roots and division.
@jcoffland

This comment has been minimized.

Copy link
Member

jcoffland commented Jan 21, 2015

You could simplify this slightly by representing a tool position as a unit vector. This removes the tool length component.

So one part of the problem is to convert axis moves (e.g. GCode) into the unit vector representation. We could just convert to paths consisting of unit vectors with the assumption that the transformation from one unit vector to the next involves only linear transformations in each axis.

A high-level outline of the algorithm is as follows:

  1. Preprocess axis moves into unit vector segments.
  2. Build an AABB or other 3D look up structure from the unit vector segments (paths) and tool parameters using an approximation of the bounds of the sweep.
  3. Run the marching cubes algorithm where each point is considered as follows:
    3.1 Look up potentially colliding unit vector segments in the AABB.
    3.2 Test the point against each potential segment sweep with it's tool definition.
    3.3 If at least one segment sweep collides then the point is in the sweep.

The hardest part is 3.2. It can be formulated as follows:

  • Given:
    • A start vector. S
    • An end vector. E
    • Tool length. L
    • Tool radii Rt & Rb
    • A point P
  • Assume that the transition from S to E is linear in all axes, i.e. they all transition from start to end at constant rates.
  • Decide whether P is in the sweep of T(L,Rt,Rb) from S to E.

Note, that each vector consists of two 3D coordinates and the tool definition describes a conic section.

If we could find a way to evaluate P ∈ sweep(T(L,Rt,Rb),S,E) then it's just a matter of writing up the code.

@NateTG

This comment has been minimized.

Copy link

NateTG commented Feb 3, 2015

OK, I described how any move can be treated as a helical move above. Now, let's supose that we can decompose the surface of the tool into pieces, each of which is convex with respect to the movement - that is to say that trajectory parralel to the tool path can intersect the surface section at most once.

If you model the tool as a bunch of flat surfaces, then the convexity requirement will - at worst - split those surfaces in two, and I think the collision test per point and surface segment pair should be tractable. I'm still chewing on the possibilities of eliptic sections.

@jcoffland

This comment has been minimized.

Copy link
Member

jcoffland commented Feb 3, 2015

@NateTG, I don't think that's a viable solution. It's very similar to boolean operations using polygons which is known to be inefficient. Several of the papers I've read discuss this.

Currently I'm modeling the tool as a conical frustum. Multiple conical frustums can be combined to create a good estimate of nearly any reasonable tool shape.

@NateTG

This comment has been minimized.

Copy link

NateTG commented Feb 3, 2015

I don't think that's a viable solution. It's very similar to boolean operations using polygons which is known to be inefficient.

Can you provide a citation or reference for that? I don't really understand what "boolean operations using polygons" means.

With the understanding that it's an undesirable approach for you, let's suppose, for a moment, that for any tool that's modelled as a polygon mesh with F faces, that there's some algorithm with time complexity O(F) and small constants for testing whether any particular point is in the sweep of the tool.

It's very easy to make interior and exterior approximations of a conical frustrum by simulating the cone as a regular n-sided pyramid, and it's relatively easy to calculate the max error on those approximations. (Off the cuff, the linear error is on the order of 1/n and the volume error 1/n^2.)

It seems like that could be useful, even if it's just acting to handle the easy cases so that some slower approach can deal with the harder ones.

Edit:
After writing this out, it occurred to me that there are meshes which are much more attractive for the sweep calculation.

@jcoffland

This comment has been minimized.

Copy link
Member

jcoffland commented Feb 3, 2015

Boolean operations on polyhedra refers to computing differences, unions & subtractions on collections of polyhedra.

From Complete swept volume generation, Part I Seok Won Lee, et. al.

whereas cutting simulation is conducted by Boolean subtraction between SV and raw stock, the execution time is too expensive to realize the machining simulation under a proper cycle time

There are others.

Also, why decompose the conical frustums in to a polyhedral approximation when it's easier to test for point inclusion as it is? I suppose your aim is to construct a polygon describing the sweep of the tool. This is an approach that has been used successful but there are pitfalls. The biggest being that boolean operations on complex polyhedra are expensive. See The sweep-envelope differential equation algorithm and its application to NC machining verification for a rather complicated approach to constructing the polyhedral sweep of a tool.

Also, such approaches are very different from my current approach which for me is a big negative. However, I'm open to implementing whatever works. I just really believe it's possible to extend my existing algorithm to yield an efficient implementation for 5-axes.

@NateTG

This comment has been minimized.

Copy link

NateTG commented Feb 4, 2015

Looks like I've got some reading to do.

... I suppose your aim is to construct a polygon describing the sweep of the tool. This is an approach that has been used successful but there are pitfalls. The biggest being that boolean operations on complex polyhedra are expensive.

Pretty much. If the tool is 'convex' with respect to the move (that is to say if the trajectory of any given point will cross the tool at most once) then it should be possible to generate a 'sweep polygon' with just a union.

I've been chewing on the question on and off for a while, but the last approach I'm musing on is a coordinate transform into a space where the rotating move is linear, but in that transformed space the concical frustrum becomes a more complicated shape. Since notiong easy fell out, I've been thinking about numerical methods,

@NateTG

This comment has been minimized.

Copy link

NateTG commented Feb 6, 2015

In CAMotics arcs are simulated as many small straight line segments. One option would be to
simply treat 5-axis rotations in the same way as arcs in 3-axis by break them up in to straight line
segments with fixed rotations. This would leave tiny jagged edges where adjustments in rotation
were made, just like arcs have tiny corners if you zoom in close enough. It is a valid solution and
it's possible that it would be good enough.

You might already have had this in mind, but what if these moves are 'plastic', that is to say, the effective sweep path can be slightly different for every point in the part? That means some challenges for the 3D search structure, but should allow for better simulation of rotary movements.

You might be able to get a marginal improvement by replacing linear moves with parabolic ones, although I'd expect that to translate to a lot of work for little return.

@jcoffland

This comment has been minimized.

Copy link
Member

jcoffland commented Feb 6, 2015

That's a good idea. Instead of splitting up the moves we could consider a simplification of the move when evaluating a particular point.

I've been considering some ways to improve the 3D search structure. One option would be to first do a very rough voxel simulation. We could compute a tube of successive spheres which completely surrounds each move in a tool path. Then cut these tubes through the voxel space, adding tool paths to each voxel which is cut by the path. Then searching for potentially colliding tool paths is just a matter of looking up the voxel, with some care for points that land on voxel boundaries. The voxel lookup is constant time.

Tubes can be represented as line segments, arcs or even helices plus a radius. Computing collision is a matter of computing the minimum distance to the segment, arc or helix to the voxel cube.

Once you have the voxel containing the point in question you can compare each tool path in the voxel by first checking if the point is in the tool path's tube and if so doing a more refined comparison. You might also consider a smaller tube which is guaranteed to be 100% inside the tool sweep. This would be a matter of computing the largest possible sphere which is completely contained with in the tool. Only if the point is between the inner and outer tubes do you compute the more complicated collision detection. In this later case, it should be sufficient to compare the point against a set of short line segments which represent the tool path with in the bounds of the portion of the larger tube which contains the point in question.

@NateTG

This comment has been minimized.

Copy link

NateTG commented Feb 7, 2015

... I've been considering some ways to improve the 3D search structure. ...

My initial (naive) thought was to convert the tool moves into 4x4 transform matrixes. (For rotary movements, there would probably have to be some interpolation). Then for a any point, we can generate the trajectory in straight segments by applying the transform matrixes to the coordinates of the point.

That gives a bunch of line segments which can individually be tested against the tool profile(s).

Since the volume that is swept out is connected, it should be possible to cover all of it by using a 'flood fill' approach that tests the neighbors of points that have been swept out.

As an optimization, when a point is swept out by the n th segment of it's trajectory, you can start checking its neighbors at the n th segment of their trajectories since those are likely to hit the tool as well.

@jcoffland

This comment has been minimized.

Copy link
Member

jcoffland commented Feb 15, 2015

I was just contacted by a French developer who created a 5-axis simulator in VB some years ago. His Webpage can be found here: http://5axes.free.fr/devel_NCVisu_en.htm

I don't know much about the performance, correctness or accuracy of this system but it looks interesting. It appears to use some sort of z-map method combined with a method for computing the silhouette (aka envelope) of a swept toroidal tool as described in this paper.

This method is very different from that used by CAMotics.

@cnciheart

This comment has been minimized.

Copy link

cnciheart commented Jul 14, 2015

Hi jcoffland, I was just searching out for an open source cam s/w and your CAMotics looked like a good choice. I am a hobbyist, and I too am interested in being able to do 4/5 axis.

Reason I was looking for open source is to try to modify it to 4/5 axis, but simpler and not looking for a universal approach. Personally, I believe the universal approach is the wrong way to go. 4/5 axis cam s/w is so dependent on hardware setup. Axes 1-3 are always standard...x,y,z. the fourth axis on up is pitch/yaw/roll, and not in any particular order. So you COULD look for a universal solution, but that is cost prohibitive at this stage in development, I think.

The quick solution I was imagining is to keep all the original functionality and method that you already implement in CAMotics for axes 1-3. But now introduce an automatic feature that updates after all the desired passes when the 4th axis initially at 0. The update would re-orient the tool angle in space to change the 4th axis and then calculate all complete passes relying on simple existing 3 axis method, taking into account the new shape of the object.

I am no expert in this area, and appreciate your generosity to the community by making open source, but just thought i would share my idea maybe it could help. If I ever get around to setting up my machine and experiment a little, i'll let you know how it turns out.

@jcoffland

This comment has been minimized.

Copy link
Member

jcoffland commented Jul 14, 2015

@cnciheart I think what you are talking about is uncoordinated 4/5 axis movements. I.e. the 4th and 5th axes do not move during cutting operations. This would be fairly easy to implement in CAMotics. Rather than do the operations one at a time the simulator would just consider the 4th and 5th axis orientation when comparing a point in space to a tool move. With the assumption that the 4th and 5th axes do not change during a cutting move then it is just a matter of applying the rotation.

@cnciheart

This comment has been minimized.

Copy link

cnciheart commented Jul 14, 2015

Yes, you see exactly. From a cost perspective (time/coding) it does get the job done and simple to implement. I would consider 4th-6th axis coordinated movements in realtime a luxury. even most of the 5th/6th axis movements can be achieved by 4th axis alone with some planning.

I plan to implement the 4th axis as a rotating table. Axes 1-3 are only tool movement. the tool head has not tilt...yet.

@KASUYASU

This comment has been minimized.

Copy link

KASUYASU commented Dec 17, 2015

Hi, Mr. jcoffland and all

Please give me your frank opinion and feedback for my 5-axis simulation.

https://github.com/KASUYASU/cutsim

@jcoffland

This comment has been minimized.

Copy link
Member

jcoffland commented Dec 17, 2015

Looks interesting. If I understand the code correctly you use implicit volumes with depth functions to describe tool shapes, these implicit tool volumes are then iterated through a series of poses which are used to cut the stock octree, the cut octree is then rendered using marching cubes. This is an oversimplification but do I have it essentially right?

Is it fast? How long does it take to simulate something we can compare in CAMotics like the stretching cat or Aztec calendar examples?

@KASUYASU

This comment has been minimized.

Copy link

KASUYASU commented Dec 17, 2015

Hi, Mr. jcoffland

Thank you for your reply.

This is an oversimplification but do I have it essentially right?

Yes, you are right.

Is it fast?

It's not so slow. I made my KJ66 difuser, by using the g-codes /build/bin/Diffuser#1_Top_Rough_Circle_to_Top_Hole_Rough_Circle.ngc etc., and my CNC machine. It takes about 20 hours only to process the top surface. But the cutsim excecute it in 40 minutes with my Core i7 processor. So it's 30~40 times faster than real time world, but you need a fast PC which has large amount of memories.

Kazu

@jcoffland

This comment has been minimized.

Copy link
Member

jcoffland commented Dec 17, 2015

Compared to CAMotics 40 mins is very slow. CAMotics takes about 45s with a 0.25mm grid on a quad i7-3770S (3.1GHz). The reason it is slow is that doing this sort of boolean operation on an octree is known to be O(n^3) where n is related to tool path length. CAMotics uses a more efficient method which is also O(n^3) but with n being a dimension of the simulation area. So with a simulation like the Aztec calender CAMotics will always be way faster. I've been progressing (slowly) towards 5-axis simulation in CAMotics. I've recently made some breakthroughs with the math for this but the 5-axis implementation is still a ways off.

It would be great to collaborate with you on this. One area I could use some help with is in converting 4 and 5 axis GCode moves into tool paths. Or in cutsim terms cannon lines. It seems you've already solved this.

@KASUYASU

This comment has been minimized.

Copy link

KASUYASU commented Dec 18, 2015

Hi, Mr. jcoffland

Compared to CAMotics 40 mins is very slow.

Of course, I know this octree method is essensially slow than your method. But I'm a resercher of Computer Science and want to make a breakthrough by some brute force methods, for example using FPGAs.

http://www.alterawiki.com/wiki/Nios2_SMP_System

CAMotics takes about 45s with a 0.25mm grid on a quad i7-3770S (3.1GHz).

Sorry, it takes about 40 mins when the cutsim executes the 367961 g-code lines that are saved in the build/bin folder as
Diffuser#1_Top_.ngc, Diffuser#2_Top_.ngc, Diffuser#3_Top_.ngc and Diffuser#4_Top_.ngc, under the condition 150x150x20.3mm stock size, with a 0.5859mm grid and 0.3mm tool step size on my Core i7-4790 CPU @ 3.60GHz. But your CAMotics takes only 45 seconds?

I've been progressing (slowly) towards 5-axis simulation in CAMotics.

My first intention of this post is to boost your motivation to 5-axis machines. I'm now making my home-made AC-table for 5-axis millings, but I noticed that there are no free or open-source 5-axis CAMs, even if 5-axis simulators. Once I attempted to analyze and improve your 'CAMotics', but it's little bit difficult for me. So I changed my attention to 'Cutsim', but it has many broken codes :-). It took about 3 months for this improvement, but my real aim is only to use 5-axis simulators, not to make those.

It would be great to collaborate with you on this.

I'm glad if I can have good cooperative relationship with you.

Kazu

@jcoffland

This comment has been minimized.

Copy link
Member

jcoffland commented Dec 18, 2015

Kazu,

This sounds great. I really want to encourage others to get involved with this project and will be happy to accommodate any contributions you would be willing to make. I could dig more into the cutsim code myself but would you be willing to provide a brief explanation of:

  1. The process you use to transform 4 and 5-axis GCode in to cannon lines.
  2. What form these cannon lines take. (linear, helical, arcs, splines, etc. + matrix transform?)
  3. How the geometry of the machine axes are taken in to account.

Joseph

@KASUYASU

This comment has been minimized.

Copy link

KASUYASU commented Dec 21, 2015

Hi, Mr. jcoffland,

  1. The process you use to transform 4 and 5-axis GCode in to cannon lines.

These transforms are done inside the interpriter 'rs274' and processed mainly in the file 'g2m/linearMotion.cpp' and 'g2m/helicalMotion.cpp'. (The code included in #ifdef MULTI_AXIS~ #endif concerns with the Multi-Axis calculation.) These codes only store the start and end point of tool's travel. The data are sent to 'g2m/gplayer.hpp' and devided by tool step size. Please see the code of 'gplayer.hpp' line 68~136.

  1. What form these cannon lines take. (linear, helical, arcs, splines, etc. + matrix transform?)

So the form are 'linear' and 'helical' only now. The rotational transformation is done for each octree nodes, not for tools. Almost all key-codes are located in the files 'cutsim/octnode.cpp' and 'cutsim/volume.cpp', The normal bounding box & collision detection techniques are used to reduce the calculations, but for the axis-aligned problem, each nodes are wrapped by over-size bounding boxes like

'cutsim/octnode.cpp'
113 #ifdef MULTI_AXIS
114 // Multi Axis
115 bb.addPoint(_center + GLVertex(-2.0,-2.0,-2.0) * scale); // caluclate the minimum x,y,z coordinates
116 bb.addPoint(_center + GLVertex( 2.0, 2.0, 2.0) * scale); // caluclate the maximum x,y,z coordinates
117 #else
118 bb.addPoint( *vertex[2] ); // vertex[2] has the minimum x,y,z coordinates
119 bb.addPoint( *vertex[4] ); // vertex[4] has the max x,y,z
120 #endif

(2.0 is over-estimated. square root 3 is enough.)

  1. How the geometry of the machine axes are taken in to account.

Now, X+Y+Z axes for the spindle motions, A+C axes for A and C rotary tables. Unfortunately, 'rs274' interprets C axis as its B axis under the AC configuration, so I use the B axis value for C axis's rotations.

'app/cutsim_window.cpp'
146 //slotRequestMove >> slotSetToolPosition -> slot_diff_volume_mt >> slotDiffDone -> update_gl_mt >> slotGLDone >> slotRequestMove
147 // called by gplayer
148 #ifdef MULTI_AXIS
149 void CutsimWindow::slotSetToolPosition(double x, double y, double z, double a, double b, double c, int line, int mstatus, double feedrate) {
...
168 myTools[currentTool]->setAngle( cutsim::GLVertex(a,0.0,b) );
169 myGLWidget->setToolPosition(x,y,z,a,0.0,b);
170 #else

The machines origin is set to X=Y=Z=0, and the rotation axes of A and C tables go through this origin. But you can set your user origin and stock positions by *.csim files like

OCTREE_CUBE_SIZE 110
OCTREE_MAX_DEPTH 9
OCTREE_CENTER 0.0, 0.0, 0.0
USER_ORIGIN -10.0, 0.0, 53.7, 0.0, 0.0, 0.0 <--- // user origin X, Y, Z, A, B, C
INITIAL_POSITION -10.0, 0.0, 53.7, 0.0, 0.0, 0.0
STEP_SIZE VARIABLE 0.05

STOCK
CYLINDER
RADIUS 53.7
LENGTH 14.0
CENTER 0.0, 0.0, -10.0 <-- // stock position
ROTATION 90.0, 0.0, 90.0
RCENTER 0.0, 0.0, 0.0
OPERATION SUM
END STOCK

, so you can change your machine's geometry in some ways.

Kazu

@jcoffland

This comment has been minimized.

Copy link
Member

jcoffland commented Dec 21, 2015

Ok, so that's very helpful. If I understand correctly, not only are you simulating A,B,C rotations as rotations of the Octree but the machine being modeled is actually rotating the sock about the origin in these axes.

What about machines that rotate the tool head? Any idea how these would be modeled? Does the GCode always handle the A,B,C axes as you describe and the machine is then responsible for translating these rotations to it's own mechanics? This is something that has confused me about 5 axis machines for some time but this explanation, if correct, would make a lot of sense.

@KASUYASU

This comment has been minimized.

Copy link

KASUYASU commented Dec 22, 2015

Hi, Mr. jcoffland,

If I understand correctly, not only are you simulating A,B,C rotations as rotations of the Octree but the machine being modeled is actually rotating the sock about the origin in these axes.

Yes, it is, though B axis is not implemented.

What about machines that rotate the tool head? Any idea how these would be modeled?

From the view point of simulators, you only need to translate the g-codes of head rotating machines to that of table-table machines.

Does the GCode always handle the A,B,C axes as you describe and the machine is then responsible for translating these rotations to it's own mechanics? This is something that has confused me about 5 axis machines for some time but this explanation, if correct, would make a lot of sense.

In the GCode, we have X, Y, Z, A, B and C characters as machine's axes, but these are not mathematical axes. Indeed, if we write a g-code 'G1 A10C20', this means the commands of rotations for the motor A and motor C, not rotating angles around A and C axes. So, in usual, we must inform our machine's spec. to CAMs, and generate g-codes that involve the machine's geometry implicitly. If you want to use the g-code that is generated for a table-table machine in your head-rotating machine, you need some converter to translate the codes.

Kazu

@NateTG

This comment has been minimized.

Copy link

NateTG commented Aug 20, 2018

A little issue necromancy here, but lately I've been wondering whether it would work to describe the distance squared between a point and the surface of the moving tool in a parametric fashion, and then set the gradient to zero and solving in order to find local minima that can then be checked to see whether they're where the tool hits the point.

@jcoffland

This comment has been minimized.

Copy link
Member

jcoffland commented Aug 20, 2018

Note, that we are generally dealing with a bunch of straight line segments. In the 5-axis case, there are also two additional rotational axes. The main problem I've found with a pure analytical solution is that the equations are not smooth and differentiable at all points in space. This makes solving one big equation for the whole thing impractical. But if you can work out the equations for a solution using vector calculus, I'm all ears.

I have a pretty good idea of how to implement 5-axis simulation. I just haven't had the time. Or rather there have been other higher priorities. I'm not making any money on CAMotics so it's harder to dedicate large chunks of time to it. If someone (or a lot of someones) were to sponsor this feature, then I could make it happen in fairly short order.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment