I've looked at set-operations (union, difference, intersection) for octrees again. Previously I tried it with linear-octrees and visualization with python and VTK. Now I'm using a traditional pointer-based octree data-structure, and drawing with OpenGL VBOs. With the addition of a g-code interpreter, a user-interface, and an isosurface extraction algorithm (such as marching-cubes) this should converge towards a milling/turning/3d-printing cutting-simulation sometime soon...
Update: this figure shows the numbering of vertices(red), edges(green), and faces(blue). The arrows show the direction of the X-(red), Y-(green), and Z-axes(blue).
Here the sides of the cube are not generated with Marching-Cubes, they are just extracted directly from the octree. Nodes are subdivided whenever the signed distance-field of the cutter indicates that the surface is contained within the node, i.e. the distance-field evaluates to both positive and negative at the eight fourvertices of a node. This apparently leads to transient holes in the surface when the cutter is just about to enter a coarse node which hasn't been subdivided very far yet. It should be possible to adjust the subdivision criterion so that the octree 'anticipates' the cutter slightly and subdivides ahead of the actual cutter surface.
The speed of the new cutting-simulation code makes it possible to run it at a higher resolution than before. That makes the surfaces look smooth and nice. Alas, some problems still remain with holes in the fabric of reality mystically appearing and disappearing .
This is my second attempt at a machining simulation where a moving milling tool cuts away voxels from the stock material. To save space an octree data structure is used to store the voxels, and to produce a nice looking surface you store the signed distance to the exact surface in each vertex of the octree. You then use marching-cubes to extract triangles for a distance=0 isosurface in order to draw the stock.
Unlike my first attempt, this works well enough to warrant further experiments (on the to-do list are: differently shaped tools, colouring triangles based on which tool cut the voxel, lathe operations, material removal-rate, etc.). It should be straightforward to hook this up to the EMC2 G-code interpreter so that any G-code, not just densely sampled CL-points from OCL, can be simulated. You could also flip the sign of all the numbers, and simulate an additive process, like 3D printing (reprap / makerbot).
Update 3: this leads slowly towards a better and faster cutting simulation. Here's an example with Tux:
Update2: this looks slightly better now (a ball translated in a few steps towards the right). Image and c++ code by fellow OCLer Jiang from China.
Update: in a cutting simulation the stock is updated by removing voxels which fall inside the cutter. Here I'm trying it with a spherical shape positioned at (0,0), and then moved slightly along the X-axis. The white dots are corners of octree nodes, and the cyan triangles are produced by marching cubes. It works quite well, but on the border between the two cutter instances the distance-field is somehow wrong, and marching-cubes doesn't come up with the right triangles, leaving gaps instead.
Earlier I was building an octree volume-representation of a shape using a simple bool isInside(Point p) predicate function to determine which cubes are in and which are out. If instead a distance-function double distance(Point p) which is negative inside the volume, zero exactly on the surface, and positive outside, is used, then the Marching Cubes algorithm (this is a better explanation, someone should make the wikipedia page as good!) can be used to triangulate the octree. This leads to much more visually pleasing results at reasonable maximum tree-depths.
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.
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.
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.
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!
