- We split the scene in an octree and make sure we can restrict the rendering of the entire scene to a given cell (either w/ a custom CLI parameter or by transforming the input .scad to a rendering script able to render a single cell or to assemble cells)
- We generate a Makefile that orchestrates the rendering of each cell (and the final reunion, which is free as we rely on lazy-union)
- We let Make parallelize and cache the rendering
- We abuse lazy unions to not pay the cost of final reunion of all cells
They don't matter as much as one might think.
OpenSCAD already uses non-exact doubles when doing Hull, when doing Minkowski, and when doing... transforms.
TODO: what about extrusions?
The approach we suggest is to push transforms down, then do all the operations on double precision inputs which can be efficiently deserialized from disk. CSG operations can even use the elalish/manifold library.
- Read original model's CSG export
- Push transforms down to just above each scene leaf (using openscad/openscad#3637) (leaves are
minkowski,polyhedron,linear_extrude, etc). The scene is now a massive union of intersections of whatever of... transformed scene leaves. - Compute the world bbox of each scene leaf, and the entire scene's bbox
- Create and refine a CGAL Octree:
- ensure an octree leaf cell intersects with at most 2 leaves' bboxes OR has at most N facets (Note: hard to know before doing the intersections, so just doing an estimation by multiplying the scene leaf's # vertices by the ratio of intersecting bounding volume over the scene leaf's bounding volume!).
- for each octree leaf cell, keep track of all the scene leaves that have bboxes that intersect with it. Build the inverse index of that as we go (from scene leaf to index of octree leaf cells)
- We keep track of identical nodes and build a dependency graph. We write a Makefile w/ rendering graph between nodes intertwined w/ cells & assembly nodes (see below)
- Generate an %input%.cells.scad intermediate file:
- includes
octree-slicing.scadabove - Defines variable bbox = list of octree leaves's bounding boxes (min / max points of said boxes in world coordinates)
- Calls render_cells with bbox, node (stage) and the original file path (used as a prefix for the outputs, being
%input%.cell_${N}.stl). This will either run the final assembly, or print the # of leaves, or render an - AST w/ each scene leaf wrapped in a
render_cell(bboxes, [...indices_of_potentially_intersecting_leaves...])call just above themultmatrixnode - Each non-final node (for reused tree) is staged w/o its transform. Nodes are only rendered if they match the global dependency node index.
- includes
There's two processes at play here:
- A slicer: can parallelize the push down of transforms and computation of bboxes but there's little point. Octree construction should be fast. Code generation should also be fast.
- A rendering orchestrator: can be a bash script. Calls GNU parallel with each cell being an openscad render task w/
-Dcell=$i. Or creates a Makefile that can encapsulate any graph dependencies and support parallel execution. Then there's a final step with-Dcell=assemblythat uses--feature=lazy-unionto generate a single STL output at zero union cost.
This should quickly max out core utilization on complex models. In the worst cases it will create a lot more work (splitting solids for nothing).
Optionally we could have a feature that bails out of the minkowski's final union and leaves it in the CSG AST, so that that part can be split too.
We recognize reused subtrees and create a dependency tree w/ full intermediate renderings of reused nodes. Each such node is refered to by its STL output (or serialized nef) in the nodes that depend on it. Cell rendering of downstream reverse dependencies depend on the assembly of the reused subtree. All of those nodes are parallelizable together by Make! Non-final nodes have their own octree sub process and may have a different number of cells.
Todo:
- each 3D scene leaf is as stored in binary STL (pre-transformed) so each cell rendering spends less time loading geometries. All these files will end up in the OS file cache anyway.
- Extra dimension = animation frames (more shared subtrees, start w/ N roots)
# example.scad -> output.renderer.scad, output.Makefile (this file)
# node0 is reused twice (with different transforms) in node1 = world scene and somehow was split in 3 cells.
# note1 depends on node1 and was split in 2 cells. Each of these cells depend on node1's assembly output
output.node0.cell0.stl:
openscad output.renderer.scad -Dnode=0 -Dcell=0
output.node0.cell1.stl:
openscad output.renderer.scad -Dnode=0 -Dcell=1
output.node0.cell2.stl:
openscad output.renderer.scad -Dnode=0 -Dcell=2
output.node0.stl: output.node0.cell0.stl output.node0.cell1.stl output.node0.cell2.stl
openscad output.renderer.scad -Dnode=0 -Dcell=all
output.node1.cell0.stl: output.node0.stl
openscad output.renderer.scad -Dnode=1 -Dcell=0
output.node1.cell1.stl: output.node0.stl
openscad output.renderer.scad -Dnode=1 -Dcell=1
output.stl: output.node1.cell0.stl output.node1.cell1.stl
openscad output.renderer.scad -Dnode=1 -Dcell=allPushing down the transforms and wrapping them with a render_cell call works, but it's a lot of AST fiddling.
Instead, we can add a clip-to-bounds feature that's easy to implement in the 3D rendering logic: before processing operands of any operation, it checks their bounds against the clip bounds. If fully outside, discards them. If partially inside, clips them with the BBox before performing the operation. If fully inside no change. Do the same with top-level result (say, in case there was no operation whatsoever). Visitation needs to keep track of the current transform, and numerical inaccuracy might creep in (works better with transforms pushed down by openscad/openscad#3637)
-
Transform all the points to world coordinates (how to do that w/ minkowksi?? just improvise)
- Simply create a global hash map of point -> solid it's been seen in
-
Use those points to refine an octree (w/ at most N points from at least 2 solids, unsure how to track that)
-
Run a the full model w/ clip bounds for each cell of the octree
OPENSCAD_CLIP_BOUNDS=1.0,0.4,0.2;10.0,13.0,20.0 openscad - -o out.stl --enable=clip-to-bounds --output-format=binarystl -
Keep track of whether we're in a repeated subtree (or inside a minkowski): disable the bounds check