A couple performance optimizations I made that weren't covered in the article:
- When I profiled my initial implementation of the annealing, I found that it was spending a lot of time just rotating bounding boxes to test for intersection. So I precompute all possible rotations of the BVHs (24 rotations) and then only need to deal with translation when checking for intersection - way faster: https://github.com/fogleman/pack3d/blob/master/pack3d/bvh.go...
- Even more interesting, for the bin packing code, I used a recursive algorithm with memoization, like you do. But I realized an improvement can be made. Say you search for the optimal packing for a box sized 10x10x10 and the optimal packing comes back, say, 9x8x9. Now I do another query for a box sized, say, 9x9x9. I should just reuse the result for my 10x10x10 query because 9x9x9 falls between 9x8x9 and 10x10x10. Basically instead of requiring an exact match in the memoization, I want to query a range. I implemented this using a spatial hash and it made things WAY faster. https://github.com/fogleman/pack3d/blob/master/binpack/spati...
Hey Michael - I'm leading the engineering team that is building the Fuse 1 here at Formlabs. This is awesome! I can't wait to try out a few of these prints soon.
Thanks for sharing this with the world. It's so rewarding to see people inspired to make stuff like this based on the printer we have been working on for such a long time.
oh, I was assuming that the time for the rotations was dependent on the size of the models, presumably in number of verts. This memoization would change the runtime.
E.g. if it was linear in that, then you would be going from O(mn) to O(m+n)
- When I profiled my initial implementation of the annealing, I found that it was spending a lot of time just rotating bounding boxes to test for intersection. So I precompute all possible rotations of the BVHs (24 rotations) and then only need to deal with translation when checking for intersection - way faster: https://github.com/fogleman/pack3d/blob/master/pack3d/bvh.go...
- Even more interesting, for the bin packing code, I used a recursive algorithm with memoization, like you do. But I realized an improvement can be made. Say you search for the optimal packing for a box sized 10x10x10 and the optimal packing comes back, say, 9x8x9. Now I do another query for a box sized, say, 9x9x9. I should just reuse the result for my 10x10x10 query because 9x9x9 falls between 9x8x9 and 10x10x10. Basically instead of requiring an exact match in the memoization, I want to query a range. I implemented this using a spatial hash and it made things WAY faster. https://github.com/fogleman/pack3d/blob/master/binpack/spati...