After the kd-tree search is done, I've added an overlap-check which leaves only triangles with a bounding box intersecting the cutter's bounding box for the drop-cutter algorithm. It's seems like a band-aid kind of hack to get it working, I think if the tree-search would be bug free the overlap check would not be needed...

The HD-version of the video is much better, once youtube has finished processing.

I've continued to translate into C++ the old cam-experiments I wrote in C#. The kd-tree search for which triangles lie under the cutter seems to work, and the best way to visualize what is going on is through a video. Trying Vimeo for a change, to see if it's any better than youtube for these CAD/CAM-visualizations, since they advertise HD.

There are 360 original frames captured from VTK, and the original was created with

mogrify -format jpg -quality 97 *.png

followed by (copy/pasted from some site google found for me...)

OK, so the video doesn't really show what is going on with the kd-tree search at all 🙂 . It only shows two toolpaths, one coloured in many colours which is calculated without the kd-tree, and another one (offset upwards for clarity) that is calculated, much faster, using the kd-tree.

First test with drop-cutter aided by the kd-tree. The output toolpath looks very much like the one without kd-tree, which is good. Less great is that I expected a speed-up of the algorithm - but in fact when I use kd-tree the program slows down! Something to investigate over the next few days.

Drop-cutter requires a fast way of searching for triangles under the tool. A kd-tree (4-dimensional in this case) is suggested by Yau et al. I've tried to implement one here (look in trunk/Project2). Just ran some timing tests using Stopwatch() on it, and indeed the build_kdtree() function which takes a pile of triangles as input and generates a kd-tree seems to run in O(N*log(N)) time as it should.

I've never drawn this type of plot before, and I was surprised at how close N*log(N) is to N - in a loglog plot they are almost equal!

This is a recursive function. I wonder if there's a good way of multi-threading recursive functions? My laptop is dual-core and a modern desktop PCs is likely a quad-core - so let's try to write these things multi-threaded from the start.

Next up is a function for doing the orthogonal range-search for triangles that lie under the tool. That's supposed to run in O(N^(1-1/D)+K) time, where D is the dimension of the tree and K is the number of reported triangles - so O(N^(3/4)+K) in this case. I'll try to get that done during the weekend.