Random thought of the morning as I finish my second cup of tea — would it be workable to create an array with grid points to match the motion of Grbl?
Working it up for one layer we get:
1,000mm x 1,000mm * 40 * 40 == 1,600,000,000
and extending that up for not quite 4 inches:
100 * 40 * 1600000000 == 6,400,000,000,000
but if we can do an array of bits it then becomes:
6400000000000 / 8 == 800,000,000,000
which at 800GB still seems a bit unworkable, so brute-forcing this on contemporary computers doesn’t seem likely (my idea was to simulate a series of toolpaths, then iterate over the cut areas so as to generate an optimal toolpath).
Doing this sort of thing for smaller regions might be workable:
25 * 25 * 40 * 40 * 100 * 40 / 8 == 500,000,000
but still, allocating and iterating over half a gigabyte doesn’t seem like the savings in effort I was hoping for.
it’s likely more space and time efficient to calculate a point given a (gcode or other format) toolpath as you need it than to store it like that (since it first needs to be calculated as well) …
you can cache the result with a more efficient cache and as long as you keep some locality that likely works out better
for example, if at coordinate X,Y the height is Z, then all “points” below Z are redundantly stored in your scheme.
A more efficient scheme would be, instead of a 3D bit grid, a 2D grid that stores heights…
you can make that look like a bit grid if needed, but I suspect half the time if you have a bit grid, you will try to find the Z by walking downwards… so might as well just store the height
There are datastructures purpose-built for tasks like this (very sparse bitmaps): compressed bitmaps. See, for example, Roaring Bitmaps.
Wouldn’t that essentially amount to something like “do a 3D-adaptive toolpath followed by a contour/scallop”? Or am I misunderstanding?
And what would you want to do with a bitmap that you couldn’t do with say a graph? I think my first instinct with such a bitmap would be to turn it into a graph anyway…
@WillAdams There is a classic algorithm for addressing this sort of problem - the Travelling Salesperson. Given a constellation of points, what is the most optimal path between them without visiting any point twice. The brute compute power increases as the square of the number of constellation points, so beyond a few hundred points becomes computationally prohibitive. However, there are various strategies that have been published that substantially reduce the processing - I have used this to take SVG images and deconstruct them into lines for my Glass Drawing machine, where avoiding crossing lines is important to avoid the chalk pens picking up dried chalk whilst they travel.
A quick google search on images and ‘TSP’ will lead you to all the rabbit holes you could possible want
