Who has an algorithm for tool-collision detection?
I think you need to be more specific. 2D/3D? What shape of tool? What format CAD model? And what exactly do you mean by tool-collision?
List of triangles with an arbitrary CNC cutting tool of user defined shaped (ball end, flat, contour,…) and size.
It’s for a special purpose 4 axis CAM software I’m currently writing.
I can reduce it to a hit - test between a triangle polygon and a cylinder or sphere in 3D space.
I can reduce it to a hit - test between a triangle polygon and a cylinder, cone or sphere in 3D space.
I’ve worked on the axial tool projection (“hit”) problem in opencamlib. There a cylinder/sphere/torus/cone is dropped down along the cutter rotation-axis until it hits a vertex/edge/face of a triangle. You run this against all relevant triangles and take the maximum (highest) z-value for the cutter as the correct one.
By far the toughest to code is the edge-test. Vertices and faces of triangles are fairly easy by comparison.
For real 4/5-axis you would need a collision algorithm where the tool is projected(“dropped” or “pushed”) along an arbitrary axis (not necessarily the axial or radial direction). I haven’t seen open-source code for this.
The figure over here shows the basic cutter shapes, as well as some composite ones, which exist in opencamlib. As mentioned before there is only axial and radial tool projection implemented currently:
http://www.anderswallin.net/2011/08/opencamlib-cutter-shapes/
The difference to non axial work is just to rotate and translate the part, so it is axial again.
I already got the inverse kinematic for the translation figured out (untested, I may be wrong).
Takes a lot of trigonometric function calls to do this for all relevant triangles and thus computing power.
Of cause you may also have the case of not cutting with the tip of the cutter if you cannot rotate far enough to have the tool normal to the surface. (the condition I’m trying to create a often as possible)
opencamlib models the cutter as ‘perfect’ cylinder/sphere/torus/cone and tests against each element of a triangle: vertex/edge/facet.
To speed up the algorithm we first figure out which triangles lie under the “shadow” of the cutter (we can potentially make contact only with these triangles) - for this the cutter can be approximated by its bounding-box, and all triangles also by their XY bounding-boxes.
Non-axial tool projection can only be done by first rotating+translating the triangle and second an axial tool-projection when we are cutting with the tip of the tool. Even in this case I don’t know how to easily+quickly figure out which triangles of the model to test against. This is vital since the algorithm is very slow if we test against all triangles.
You should post some diagrams, math, and code somewhere if you get an example of non-axial tool projection working!
Currently you compare all vertices against the bounding box in X, Y space?
That would still work in a nonaxial case, you just have to project the bounding box for the given Z of the vertex first. (simple linear equation)
I figure out which triangles are under the cutter as a pre-processing step. This pre-processing uses 2D XY bounding-boxes (because it is easy to figure out if two bounding-boxes overlap). For speed, it’s done by storing all triangles of an STL-model in a kd-tree, which makes searching for overlap with a given cutter bounding-box fast.
The actual tool-projection is then run on the found triangles, and uses the exact shape of the cutter.
Having thought about 4/5D a little more, I think the idea of “rotate+translate triangle, then tool-project axially” may actually work, when the cutter-contact point is on the convex tool tip. It will not work if we want to machine with the cylindrical shaft of the tool since this part of the tool will never make contact with a triangle when an axial tool-projection is performed.
Once you have a non-axial tool projection algorithm in place the next question ofcourse becomes how do you figure out how to tilt the tool axis as you move along e.g. some pre-defined cutting pattern in the XY-plane?
From the tool-projection algorithm you get out also the cutter-contact point and from that the slope(tangent) of the cutter-contact point - so you may try to keep this slope constant?
I’m using the surface normal as the tilt angle.
What I want to achieve are perfectly curved, convex, organic surfaces without visible steps.
https://code.google.com/p/simplemultiaxiscam/source/browse/
Super slow but it produces G-Code that looks legit.
It’s just a proof of concept now and I’m currently installing a 5 axis simulator to see if the g-code makes sense.
No collision check at all yet.
Added a very first GUI.
We have 3 parallel projections now that show the model.
next step: showing the toolpathes and single-stepping through the g-code showing the tool’s position and orientation .
Then I can verify the algorithm.
It does have a problem if there is no geometry surrounding the rotational axis but left or right of it. Not all sides of it will be milled in that case.
ok, removed the old main class, gui can now generate and show g-code. looks fine. Just very, very slow.
@Anders_Wallin do you know a faster way to check if a hit point of plane and ray is inside a triangle then the conversion to Bayer coordinates?
Especially as I already have the intermediate calculations of the plane+ray test.
Here’s what I’m using
and here’s a reference:
http://www.blackpawn.com/texts/pointinpoly/default.html
Thanks 
As for optimizing it, I’m thinking about grouping the triangles in equidistant voxels (no balancing needed, some shortcuts in math)