Here's an initial test of octree-based cutting simulation:
If you turn up the resolution to eleven, where it starts to be useful and not so grainy, the calculation of the tool-swept volume, which we subtract from the stock at each move, becomes too slow.
See also octree operations.
Download a short clip with a depth=10 tree: OUTPUT (it's also on youtube, but a 2s clip on youtube doesn't work very well: http://www.youtube.com/watch?v=G0RYS9FcqR0)
some screenshots:
When generating toolpaths with drop-cutter ("axial tool-projection", if you like fancy words) the path ends up being composed of lots of short linear segments. It makes sense to filter this list of points and take out any middle points that lie on a straight line between neighboring points. Here's a first attempt at such a line-filter.
The lower points is the raw output from drop cutter, while the filtered points are offset vertically for clarity. There are 6611 CL-points in the raw data, but only 401 CL-points after filtering.
The next step is to come up with an arc-filter which detects circular arcs in the list of CL-points. All CNC-machines have G2/3 circular arc motion in the principal planes (xy, xz, yz). Then the number of moves will go even further down from 401 points.
This is just something to live with, having chosen the triangulated model approach to CAM. First we have pure and exact shapes in CAD which get tessellated into zillions of tiny triangles, from these we generate a sampled toolpath consisting of lots and lots of points, and finally we filter to get back those "pure" "exact" and "nice" line-segments and arcs.
The relevant part of the code looks like this. It might be a bit prettier to use the remove_if STL algorithm? Also, there's no check that p1 actually lies between p0 and p2.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | typedef std::list<clpoint>::iterator cl_itr; cl_itr p0 = clpoints.begin(); cl_itr p1 = clpoints.begin(); p1++; cl_itr p2 = p1; p2++; for( ; p2 != clpoints.end(); ) { Point p = p1->closestPoint(*p0, *p2); if ( (p- *p1).norm() < tol ) { // p1 is to be removed p1 = clpoints.erase(p1); p2++; } else { p0++; p1++; p2++; } } |
full code here.
People who, unlike me, actually know something about programming often talk about design patterns. One common idea is to compose objects out of other objects.
I was able to add four new APT-tool like cutter classes to ocl with about 5-lines of code for each cutter (sans the bugfixing, taking much longer, that also took place simultaneously 🙂 ).
These show CL-points resulting from the vertexDrop() function, which results in a shape that looks like the cutter, but inverted.
Other combinations of the basic shapes (cylinder, sphere, torus, cone) are fairly easy to add now also if someone actually needs them.
I've experimented with using OpenMP to calculate drop-cutter toolpaths on a quad-core machine. These now run reasonably fast. There are obvious lurking bugs with BallCutter and BullCutter still...
Code is here: code.google.com/p/opencamlib/ (if you know C++, computational geometry, and cnc-machining, or are willing to learn, this project needs your help!)
See also: styrofoam spider
If you number the octants in an octree using a 1982 scheme called Gargantini-code, and store the codes for only the black nodes in the tree in a list then that's called a linear octree.
For quadtrees, there is a 1985 paper by Bauer with an algorithm for computing set-operations (intersection, union, difference) between two trees. Ten years later Jiang corrected a few mistakes and extended this algorithm to octrees. Neither paper is free of misprints, but by looking at both I seem to have arrived at set-operations which work.
Pushing lists with 10 000 or more elements back and forth between C++ and python is not very fast, and I'm now rendering each node (a cube) in a tree as a separate Cube-object in VTK, which isn't very efficient. The video shows depth 6 trees at the end, and here's a screen-capture of a depth 7 tree:
This could be useful for making a cutting-simulator used for both verifying CAM-algorithms in opencamlib, and G-code produced by other programs. It's probably possible to hook into the EMC2interpreter and have it drive the tool in the simulation.
A one-triangle test of drop-cutter for toroidal tools (a.k.a. filleted-endmills, or bull-nose).
The blue points are contacts with the facet, and the green points are contacts with the vertices. These are easy.
The edges-contacts (red-points) are a bit more involved, and are done with the offset-ellipse solver presented earlier here(the initial geometry) and here(offset-ellipse construction) and here(convergence of the solver) and here(toroid-line intesection animation).
explanation(s) to follow at some point...
Recursion and 'divide-and-conquer' must be two of the greatest ideas ever in computer science.
Threw together some code in python today for building an octree, given a function isInside() which the tree-builder evaluates to see if a node is inside or outside of the object. Nodes completely outside the interesting volume(here a sphere, for simplicity) are rendered grey. Nodes completely inside the object are coloured, green for low tree-depth, and red for high. Where the algorithm can't decide if the node is inside or outside we subdivide (until we reach a decision, or the maximum tree depth).
In the end our sphere-approximation looks something like this:
These tests were done with a maximum tree depth of 6 or 7. If we imagine we want a 100 mm long part represented with 0.01 mm precision we will need about depth 14, or a subdivision into 16384 parts. That's impractical to render right now, but seems doable. In terms of memory-use, the octree is much better than a voxel-representation where space is uniformly subdivided into tiny voxels. The graph below shows how the number of nodes grows with tree-depth in the actual octree, versus a voxel-model (i.e. a complete octree). For large tree-depths there are orders-of-magnitude differences, and the octree only uses a number of nodes roughly proportional to the surface area of the part.
Now, the next trick is to implement union (addition) and difference (subtraction) operations for octrees. Then you represent your stock material with one octree, and the tool-swept-volume of your machining operation with another octree -> lo and behold we have a cutting-simulator!
In colours and numbers, the number of iterations in the offset-ellipse solver required to reach an arbitrary 8-digit precision. A smart choice of initial value can save almost half of the computation.
More on the offset-ellipse calculation, which is related to contacting toroidal cutters against edges(lines). An ellipse aligned with the x- and y-axes, with axes a and b can be given in parametric form as (a*cos(theta) , b*sin(theta) ). The ellipse is shown as the dotted oval, in four different colours.
Now the sin() and cos() are a bit expensive the calculate every time you are running this algorithm, so we replace them with parameters (s,t) which are both in [-1,1] and constrain them so s^2 + t^2 = 1, i.e. s = cos(theta) and t=sin(theta). Points on the ellipse are calculated as (a*s, b*t).
Now we need a way of moving around our ellipse to find the one point we are seeking. At point (s,t) on the ellipse, for example the point with the red sphere in the picture, the tangent(shown as a cyan line) to the ellipse will be given by (-a*t, b*s). Instead of worrying about different quadrants in the (s,t) plane, and how the signs of s and t vary, I thought it would be simplest always to take a step in the direction of the tangent. That seems to work quite well, we update s (or t) with a new value according to the tangent, and then t (or s) is calculated from s^2+t^2=1, keeping the sign of t (or s) the same as it was before.
Now for the Newton-Rhapson search we also need a measure of the error, which in this case is the difference in the y-coordinate of the offset-ellipse point (shown as the green small sphere, and obviously calculated as the ellipse-point plus the offset-radius times a normal vector) and where we want that point. Then we just run the algorithm, always stepping either in the positive or negative direction of the tangent along the ellipse, until we reach the required precision (or max number of iterations).
Here's an animation which first shows moving around the ellipse, and then at the end a slowed-down Newton-Rhapson search which in reality converges to better than 8 decimal-places in just seven (7) iterations, but as the animation is slowed down it takes about 60-frames in the movie.
I wonder if all this should be done in Python for the general case too, where the axes of the ellipse are not parallel to the x- and y-axes, before embarking on the c++ version?
