Drop-Cutter toroid edge test

The basic CAM-algorithm called axial tool projection, or drop-cutter, works by dropping down a cutter along the z-axis, at a chosen (x,y) location, until we make contact with the CAD model. Since the CAD model consists of triangles, drop-cutter reduces to testing cutters against the triangle vertices, edges, and facets. The most advanced of the basic cutter shapes is the BullCutter, a.k.a. Toroidal cutter, a.k.a. Filleted endmill. On the other hand the most involved of the triangle-tests is the edge test. We thus conclude that the most complex code by far in drop-cutter is the torus edge test.

The opencamlib code that implements this is spread among a few files:

  • millingcutter.cpp translates/rotates the geometry into a "canonical" configuration with CL=(0,0), and the P1-P2 edge along the X-axis.
  • bullcutter.cpp creates the correct ellipse, calls the ellipse-solver, returns the result
  • ellipse.cpp ellipse geometry
  • ellipseposition.cpp represents a point along the perimeter of the ellipse
  • brent_zero.hpp has a general purpose root-finding algorithm

The special cases where we contact the flat bottom of the cutter, or the cylindrical shaft, are easy to deal with. So in the general case where we make contact with the toroid the geometry looks like this:


Here we've fixed the XY coordinates of the cutter location (CL) point, and we're using a filleted endmill of radius R1 with a corner radius of R2. In other words R1-R2 is the major radius and R2 is the minor radius of the Torus. The edge we are testing against is defined by two points P1 and P2 (not shown). The location of these points doesn't really matter, as we do the test against an infinite line through the points (at the end we check if CC is inside the P1-P2 edge). The z-coordinate of CL is the unknown we are after, and we also want the cutter contact point (CC).

There are many ways to solve this problem, but one is based on the offset ellipse. We first realize that dropping down an R2-minor-radius Torus against a zero-radius thin line is actually equivalent to dropping down a zero-minor-radius Torus (a circle or 'ring' or CylCutter) against a R2-radius edge (the edge expanded to an R2-radius cylinder). If we now move into the 2D XY plane of this circle and slice the R2-radius cylinder we get an ellipse:


The circle and ellipse share a common virtual cutter contact point (VCC). At this point the tangents of both curves match, and since the point lies on the R1-R2 circle its distance to CL is exactly R1-R2. In order to find VCC we choose a point along the perimeter of the ellipse (an ellipse-point or ePoint), find out the normal direction, and go a distance R1-R2 along the normal. We arrive at an offset-ellipse point (oePoint), and if we slide the ePoint around the ellipse, the oePoint traces out an offset ellipse.


Now for the shocking news: an offset-ellipse doesn't have any mathematically convenient representation that helps us solve this!
Instead we must numerically find the best ePoint such that the oePoint coincides with CL. Like so:


Once we've found the correct ePoint, this locates the ellipse along the edge and the Z-axis - and thus CL and the cutter . If we go back to looking at the Torus it is obvious that the real CC point is now the point on the P1-P2 line that is closest to VCC.

In order to run Brent's root finding algorithm we must first bracket the root. The error we are minimizing is the difference in Y-coordinate between the oePoint and the CL point. It turns out that oePoints calculated for diangles of 0 and 3 bracket the root. Diangle 0 corresponds to the offset normal aligned with the X-axis, and diangle 3 to the offset normal  aligned with the Y-axis:



Finally a clarifying drawing in 2D. The ellipse center is constrained to lie on the edge, which is aligned with the X-axis, and thus we know the Y-coordinate of the ellipse center. What we get out of the 2D computation is actually the X-coordinate of the ellipse center. In fact we get two solutions, because there are two ePoints that match our requirement that the oePoint should coincide with CL:



Once the ellipse center is known in the XY plane, we can project onto the Edge and find the Z-coordinate. In drop-cutter we obviously approach everything from above, so between the two potential solutions we choose the one with a higher z-coordinate.

The two ePoint solutions have a geometric meaning. One corresponds to a contact between the Torus and the Edge on the underside of the Torus, while the other solution corresponds to a contact point on the topside of the Torus:

I wonder how this is done in the recently released pycam++?

OpenCAMlib and OpenVoronoi toolpath examples

There might be renewed hope for a FreeCAD CAM module. Here are some examples of what opencamlib and openvoronoi can do currently.

The drop-cutter algorithm is the oldest and most stable. This shows a parallel finish toolpath but many variations are possible.


The waterline algorithm has some bugs that show up now and then, but mostly it works. This is useful for finish milling of steep areas for the model. A smart algorithm would use paralllel finish on flat areas and waterline finish on steep areas. Another use for the waterline algorithm is "terrace roughing" where the waterline defines a pocket at a certain z-height of the model, and we run a pocketing path to rough mill the stock at this z-height. Not implemented yet but doable.


This shows offsets calculated with openvoronoi. The VD algorithm is fairly stable for input geometries with line-segments, but some corner cases still cause problems. It would be nice to have arc-segments as input also, but this requires additional work.


The VD is easily filtered down to a medial-axis, more well-known as a V-carving toolpath. I've demonstrated this for a 90-degree V-cutter, but toolpath is easy to adapt for other angles. Input geometry comes from truetype-tracer (which in turn uses FreeType).


Finally there is an experimental advanced pocketing algorithm which I call medial-axis-pocketing. This is just a demonstration for now, but could be developed into an "adaptive" pocketing algorithm. These are the norm now in modern CAM packages and the idea is not to overload the cutter in corners or elsewhere - take multiple light passes instead.


The real fun starts when we start composing new toolpath strategies consisting of many of these simple/basic ones. One can imagine first terrace-roughing a part using the medial-axis-pocketing strategy, then a semi-finish path using a smart shallow/steep waterline/parallel-finish algorithm, and finally a finish operation or even pencil-milling.

Octree simplification by QEFs


Dual contouring uses a quadratic-error-function (QEF) to position a vertex inside each octree-node (cube) where the implicit distance-field that defines our geometry changes sign. The vertex is positioned so that the QEF is minimized. This allows for an octree simplification strategy where we combine all the QEFs of the eight child-nodes, and see if we can replace the eight vertices they define with with a single vertex one level up in the octree.

This image shows the dual contouring code run on the same input data with various levels of simplification. Even a small threshold value of 0.001 reduces the number of triangles more than ten-fold. Too large a threshold produces jagged edges. Note that dual contouring of the original dataset where each leaf-node is at the same (maximal) depth of the tree produces only quad polygon output. When we simplify and collapse some nodes to non-maximal depth the algorithm also produces triangles - where a collapsed node is adjacent to nodes deeper in the tree.

Dual Contouring

Here's an image from the CNC-milling simulator I am working on. It stores a signed distance field in an adaptively subdivided octree. To render a surface of the stock we then run an isosurface extraction algorithm. The most well-known of these is the Marching Cubes (MC) algorithm, used here also. One problem with MC is that it doesn't preserve fine detail (like sharp edges) very well, and many times there are also gaps or cracks in the surface. Both of these problems are visible below.


From about 2000 onward there are a number of papers that try to improve on MC. The most promising seems to be Dual Contouring, by Tao Ju. There is both c++ and Java LGPL code for DC on sourceforge, and I made some slight changes to make it compile with cmake on Ubuntu: https://github.com/aewallin/dualcontouring

The output PLY file can be viewed with meshlab:

So far so good. Now the task is to either rewrite my octree + boolean CSG operations code to use the data structure used in the DC code, or vice versa, change the DC code to use my datastructure.

Crimp Clamp Tool

I've been cranking out parts for this Crimp-Clamp-Tool over the past few days:
(design inspired by Lindsay Wilson's site, which has more information on the seal-off technique)


It's used to permanently seal vacuum-systems that are pumped through a ~10 mm diameter copper tube. The jaws of the tool compress the tube and "cold-weld" the tube walls together which seals the tube.


The top and bottom clamps are milled from 20x40 mm steel bar. The bottom clamp has slots that secure two M12x100 bolts in place, and 6mm holes for M6 screws that hold half inch Thorlabs rods that guide the top and bottom clamps. The top clamp has 12mm holes for the bolts, and half inch holes that I opened up with a boring head so the Thorlabs rods (about 12.66 mm diameter) fit accurately.

The jaws are 3.125 mm diameter carbide rods (the shaft from old used PCB milling bits). They are held in a V-groove on a rod-holder part that bolts to the top/bottom clamps with M5 screws. I glued the rods to the V-groove with Loctite Hysol.


Here's how the crimped tubes look like. The first test resulted in a jagged edge, while the second test produced a nice straight cut. We will test how vacuum-tight these are with a Helium sniffer later.


PDF drawings:

Dual-needle pyVCP meter


By popular demand, a quick hack that modifies the pyVCP meter widget to have two independent needles. It's used inside the <meter> tag by specifying <halpin2>"my2ndpin"</halpin2> and hooking up something to that pin. If <halpin2> is not used meter works as before, showing only one needle.

There's an XML file for this test-panel, a short HAL-file that hooks up the pins, and a shell script to run it all here: pyvcp_dual-needle-test

The modifications to linuxcnc source required are in lib/python/pyvcp_widgets.py: 0002-dual-needle-meter-use-with-halpin2-meter2-halpin2.patch
NOTE: This is a quick hack to make it work - don't take my code/patch too seriously...

Real-Time Tuning

I tried a number of things that are supposed to improve real-time performance, as described in this forum post.

But not much changed. This series of jitter-histograms shows little or no changes:

0 1 2 3 4

The things I tried are roughly

  1. measure first latency histogram 0.png
  2. uninstall the package irqbalance using synaptic. reboot.
  3. measure 1.png
  4. in /etc/default/grub modify GRUB_CMDLINE_LINUX_DEFAULT="isolcpus=1 acpi_irq_nobalance noirqbalance"  (Aside: why are the files in /etc/grub.d/ made so incredibly hard to read? Someone should re-write them in Python!). Run sudo update-grub. reboot.
  5. measure 2.png
  6. Add irq-affinity.conf to /etc/init/
  7. Add set-irq-affinity and watchirqs to /usr/local/sbin. reboot
  8. measure 3.png
  9. Try to tweak BIOS settings. Turn off power-saving features, etc.
  10. measure 4.png

The output of watchirqs looks like this:

watchirqs_before_boot watchirqs_last

The scripts mentioned above: irqstuff

Temperature PID control - Part Deux

Update: this version of the component may compile on 10.04LTS without errors/warnings: frequency2temperature.comp (thanks to jepler!)

There's been some interest in my 2-wire temperature PID control from 2010. It uses one parallel port pin for a PWM-heater, and another connected to a 555-timer for temperature measurement. I didn't document the circuits very well, but they should be simple to reproduce for someone with an electronics background.

Here's the HAL setup once again:

The idea is to count the 555 output-frequency with an encoder, compare this to a set-point value from the user, and use a pid component to drive a pwm-generator that drives the heater.

Now it might be nicer to set the temperature in degrees C instead of a frequency. I've hacked together a new component called frequency2temperature that can be inserted after the encoder. This obviously required the thermistor B-parameters as well as the 555-astable circuit component values as input (these are hard-coded constants in frequency2temperature.comp) . Like this:

I didn't have the actual circuits and extruder at hand when coding this. So instead I made a simulated extruder (sim_extruder) component and generated simulated 555-output. Like this:

This also requires a conversion in the reverse direction called temperature2frequency. A stepgen is then used to generate a pulse-train (simulating the 555-output).

  • The INI and HAL files for the simulated extruder, based on the default axis_mm config: simextruder
  • frequency2temperature component:  frequency2temperature.comp (install with: "comp --install frequency2temperature.comp")
  • temperature2frequency component: temperature2frequency.comp (only for simulated setup, not required if you have actual hardware)
  • sim_extruder component: sim_extruder.comp (only for simulated setup, not required if you have actual hardware)

"heartyGFX" has made some progress on this. He has a proper circuit diagram for the PWM-heater and 555-astable. His circuits look much nicer than mine!

The diagrams above were drawn with Inkscape in SVG format: temp_pid_control_svg_diagrams

Why Real-Time?

Why bother with these real-time kernels and APIs at all? Isn't timing on a modern PC good enough? Look at this:

This histogram shows latency-numbers from the same 1ms thread test run compiled without (red) and with (green) real-time enabled. All the green real-time data clusters around zero +/- 20us. Without real-time enabled the event we are expecting to happen every 1 ms might happen almost 1 ms too early, or up to 3 ms late. With real-time the timing is mostly consistent to better than 1% (10 us) with a worst-case jitter of 2% (20 us).