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.
1. Comment by Dan Heeks
12/Apr/2010 at 13:22
Is this ready to try?
2. Comment by Administrator
12/Apr/2010 at 13:43
For cylindrical and spherical tools, and 3-axis milling, I think I will have a working cutting-simulation going within a week.
For toroidal tools there is no closed-form solution for the tool-swept-volume, so this is much harder. A brute-force solution is not to calculate a swept-volume at all, just position the tool along the toolpath at densely enough spaced points. That will probably be very slow...
true 5-axis moves where the tool is both translated and rotated are also hard.
3. Comment by Matt
6/May/2010 at 01:28
Came across your blog searching for set operations on linear octrees.
Somewhat shocked that these algorithms are not more widely used or
developed. I'd be great full for any comments, code, papers you are
willing to share with me -- I'm just coming up to speed, and see that those
papers you mention are hard to follow.
Cheers, Matt
4. Comment by Administrator
6/May/2010 at 08:53
Hello Matt,
My (experimental!) c++ code is part of opencamlib, or "ocl";
http://code.google.com/p/opencamlib/
specifically, the octree operations are in:
http://code.google.com/p/opencamlib/source/browse/trunk/src/octree.cpp
for building octrees I also define a volume-class:
http://code.google.com/p/opencamlib/source/browse/trunk/src/volume.cpp
I implemented and briefly tested all the set operations of Bauer/Jiang. They are described in terms of index-loops etc., and a more modern implementation would/should use std::list.
For simulating cutting with cnc-machines the interesting operation is stock.diff(tool) so I have now written a diff12 operation which uses std::list. That (maybe) means that in the current code the general linear set-operation function of Bauer/Jiang is broken (?) and you would have to dig in the SVN history to find a working one...
I did not search many days for an open-source linear-octree + set-operations library out there, but if none really exists this could be forked into a project of its own, separate from ocl.
I'll check what papers I have a bit later today,
Anders
5. Comment by jjqcat
20/Jul/2010 at 14:45
I'm interested in CNC simulation,and make one use Z_Vector method, for tool move step, I use swept geometry to intersect with z_vector ray,such as ball_end tool, the swept geometry is cylinder.
I think we needn't create swept-volume to do boolean operation, only to remove those nodes which are in swept geometry from stock octree.
6. Comment by anders
21/Jul/2010 at 14:14
hi jjqcat,
There's a big difference between the z-vector model and the octree. With the z-vector model you already have all the z-vectors for the resolution you want, and cut them down with the sweep. With the octree you only subdivide into octants if you have to. I don't know how you would subtract a sweep without actually constructing the octree that represents the sweep.
In my code the construction of the sweep octree is the time-consuming step, while the function that subtracts one octree from another is quite fast.
If you have any ideas on how to do this smarter, please comment below!
7. Comment by jjqcat
22/Jul/2010 at 10:21
Hi Anders,
First of all, thanks for your reply. I have download your simulation source and compiled successfully with VS2005 (debug mode), and use cutsim_test_1.py for test, but it's very slow(every step spent about 10seconds, my computer's configure: Pentium 4 CPU 2.8GHZ, RAM 1GB), I have modified some source code and make it faster. After tested in release mode, I will send source to you.
Thanks
jiangjinquan
8. Comment by Administrator
22/Jul/2010 at 13:58
sounds good!
there's a mailing-list over here for opencamlib:
http://groups.google.com/group/opencamlib
you could post your ideas and/or code there too.
AW
9. Pingback by anderswallin.net › Octree operations
25/Sep/2011 at 15:02
[...] 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 [...]
10. Pingback by anderswallin.net › Octree-based cutting simulation
1/Oct/2011 at 23:46
[...] 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. [...]