100x Faster Slicing of SCAD Files for 3D Printing
Replace 3D CSG by Fast 2D Polygon Clipping
Preparing a 3D model in CSG format (e.g., when using OpenSCAD) for printing may take a long time and is often computationally instable.
by a workflow 'slice, then apply 2D CSG, then print':
In the hope that the latter is faster. First experiments indeed indicate a huge speed-up for a non-trivial example, and much better computational stability.
The idea is explained in more detail in my blog.
Hob3l's main output formats are
- STL for printing
The purpose of this project is definitely not to rant about OpenSCAD. It is a great tool that I am also using.
Instead, this is about a different technique for rendering CSG into STL that is especially suited for 3D printing, where individual slices from your model is all you need. If you really need a 3D solid from your CSG, then do use OpenSCAD's CGAL based rendering.
Table of Contents
- Replace 3D CSG by Fast 2D Polygon Clipping
- Table of Contents
- SCAD Input Format
- Status, Stability, Limitations, Future Work, TODO
- Supported Output Formats
- Running Tests
- Using This Tool, Command Line Options
- Algorithmic Improvements
- Speed comparison
- Rendering Differences
SCAD Input Format
The Hob3l tool reads a subset of the SCAD format used by OpenSCAD -- I did not want to invent another format.
Please check the SCAD format documentation for a definition of the subset of SCAD that is supported by Hob3l.
Also note that OpenSCAD's
csg export can be used as a preprocessor
for Hob3l in case some SCAD syntax is still unsupported.
See Using This Tool.
Status, Stability, Limitations, Future Work, TODO
Despite quite some testing and debugging, this may still assert-fail occasionally or output rubbish. The floating point algorithms are somewhat brittle and hard to get right.
OTOH, the basic workflow is implemented and tested, i.e., the tool can read the specified subset of SCAD (e.g. from OpenSCAD's CSG output), it can slice the input object, it can apply the 2D boolean operations (AKA polygon clipping), and it can triangulate the resulting polgygons, and write STL. Slic3r can read the STL files Hob3l produces.
Corner cases in the algorithms have been dealt with (except for unknown bugs). Because of the stability design goal that extends from computational real number stability to corner cases, this was in focus from the start. Corner case handling took up most of the development time and takes up a large portion of the code, because doing floating point computations in a stable way is really tricky.
The input polyhedra must be 2-manifold. This is because the slicing algorithm is edge driven and uses a notion of 'left and right face' at an edge, so an edge must have a unique face on each of its sides. This restriction will probably not be fixed soon.
The output STL contains separate layers instead of a single solid.
This will be fixed in the future. For now, if you hit
split e.g. in
slic3r, you'll get hundreds of separate layer objects -- which is not
Memory management has leaks. I admit I don't care enough, because Hob3l basically starts, allocates, exits, i.e., it does not run for long, so the memory leaks do not build up. The goal is to have a proper, fast pool based allocation. This is prepared, but incomplete.
There are not enough tests.
The tests that exist often only test for absence of a crash or assertion failure, but whether the algorithm works correctly then needs to be inspected by a human.
Supported Output Formats
STL: The output format of Hob3l for which it was first developed, is
STL. This way, the input SCAD files can be converted and directly
used in the slicer for 3D printing.
PS: For debugging and documentation, including algorithm
visualisation, Hob3l can output in PostScript. This is how the
overview images on this page where generated: by using single-page PS
output, converted to
GraphicsMagick. For debugging,
mainly multi-page debug PS output was used, which allows easy browsing
gv for its speed and other nice features). Also, this allows
to compare different runs and do a step-by-step analysis of what is
going on during the algorithm runs. The PS modules has a large number
of command line options to customise the output.
JS/WEBGL: For prototyping SCAD files, a web browser can be used as a
file can be edited in your favourite editor, then for visualisation,
Hob3l can generate WebGL data (possibly with an intermediate step to
let OpenSCAD simplify the input file using its .csg output), and a
reload in the web browser will show the new model. This package
contains auxiliary files to make it immediately usable, e.g. the
surrounding .html file with the WebGL viewer that loads the generated
data. See the
SCAD: For debugging intermediate steps in the parser and converter,
SCAD format output is available from several processing stages.
Here's a screenshot of my browser with a part of the Prusa i3 MK3 3D printer rendered by Hob3l:
There is an online version available here to play with.
The conversion from
.js takes about 0.7s on my machine,
so this is very well suited for prototyping: write the
.scad in a
text editor, run 'make', reload in browser. To run this conversion
yourself, after building, run:
make clean-test time make test-out/curry.js
This should print something like:
./hob3l.exe scad-test/curry.scad -o test-out/curry.js.new.js Info: Z: min=0.1, step=0.2, layer_cnt=75, max=14.9 mv test-out/curry.js.new.js test-out/curry.js real 0m0.650s user 0m0.592s sys 0m0.044s
Building relies on GNU make and gcc, and uses no automake or other meta-make layer. Both Linux native and the MingW Windows cross compiler have been tested, and I hope that the MingW compiler will also work when run natively under Cygwin.
Make variables can be used to switch how the stuff is compiled. Since
I tried not to overdo with gcc extensions (
are used frequently, though), it should be compilable without too much
One unusual step is the generation of the font files (for the
command, which is currently not completely implemented, but the files
are needed already for compilation). The font files are generated by
fontgen, which needs to be compiled and run. The font files
are not checked in, because they are quite large (about 10 .c files
each ~2 MB), and they tend to change a lot even for minute changes to
the font. This would cause huge diffs. So the first step is to
This only needs to be done once (even when switching compilation
targets). The font files are not deleted even with
or similar (only
make font-clean and
make zap remove them), so
now the compilation goes on normally:
make clean make make test
The resulting executable is called 'hob3l.exe' (also under Linux -- this is so that it also works under Windows).
Parallel building should be fully supported using the
-j option to
Some Perl scripts are used to generate C code, but all generated C code is also checked in, so the scripts are only invoked when changes are made.
Different Build Variants
The makefile supports 'normal', 'release', and 'devel' build variants,
which can be switched using the
MODE=devel command line variables for make. The
selection is stored in a file
.mode.d, so next time you invoke
'make' without a
MODE parameter, the previous build variant will be
make clean make MODE=release make test
Different Compiler Targets
To compile with the standard 'gcc', whatever that is, for x86:
To compile with gcc for x86_64 (e.g., 64 bit x86 Linux):
To compile with gcc for i686 (e.g., 32 bit x86 Linux):
To cross compile for Windows 64 using MingW:
To cross compile for Windows 32 using MingW:
Tweaking Compiler Settings
The Makefile has more settings that can be used to switch to other compilers like clang, or to other target architectures. This is not properly documented yet, so reading the Makefile may be necessary here.
The most likely ones you may want to change are the following (listed with their default setting):
CFLAGS_ARCH := -march=core2 -mfpmath=sse
After building, tests can be run, provided that the 'hob3l.exe' executable can actually be executed (hopefully). On systems where it works, use
for that. This runs both the unit tests as well as basic SCAD conversion tests. For full set of checks (asserts) during testing, the 'devel' build variant should be used in addition to the actual build variant.
After installation, the SCAD conversion tests can be run with the installed binary by using
make check is invoked, it will first remove the old test
output files to make sure that the check is actually run.
make check also honours the
DESTDIR variable to construct the path to the
installed executable in the same way as
The usual installation ceremony is implemented, hopefully according to
the GNU Coding Standard. I.e., you have
make install with
*dir options and also
DESTDIR support as well as
$(NORMAL_INSTALL) markers, and also
make DESTDIR=./install-root prefix=/usr install
For better package separation, the
install target is split into
(e.g. to have a separate
-dev package as in Debian distributions).
Unfortunately, there is no
install-doc yet. FIXME.
The package name Hob3l can be changed during installation using the
package_name variable, but this only changes the executable name and
the library name, but not the include subdirectory, because this would
not work as the name is explicitly used in the header files.
Using This Tool, Command Line Options
In general, use
To convert a normal scad file into the subset this Hob3l can read, start by using OpenSCAD to convert to a flat 3D CSG structure with all the syntactic sugar removed. This conversion is fast.
openscad thing.scad -o thing.csg
You can now use Hob3l to slice this directly instead of applying 3D CSG:
hob3l thing.csg -o thing.stl
This can then be used in your favorite tool for computing print paths.
Tweaking Command Line Settings
The underlying technique of Hob3l is computationally difficult, because it relies on floating point operations. The goal was stability, but it turned out to be really difficult to achieve, so Hob3l might still occasionally fail. If this happens, the following command line options change internal settings that might push the tool back on track:
--max-simultaneous=N # decrease for better stability; min. is 2
The following options also have an influence, but neither large nor
small is really better -- changing them causes different perturbations
and thus different results, some of which might be more likely to
succeed. A good heuristics is to keep
gran larger than
eps2 be about the square of
--gran=X --eps=X --eps2=X
Computing the difference between adjacent layer (e.g. for JS/WebGL output) often has to deal with very close points, so switching this off often helps to move forward, too. Of course, this may produce output that is less nice.
The triangulation algorithm of Hertel & Mehlhorn (1983) was extended to support coincident vertices, because this is what the polygon clipping outputs. Also, sequences of collinear edges are fully supported, because, again, this may happen.
The polygon clipping algorithm of Martínez, Rueda, Feito (2009) was improved to have less computational instability by deriving crossing points always from the original edge (although currently, each 2D operation restarts this -- this could be improved). Also, computational stability was improved by rigorous use of epsilon-aware arithmetics. Further, a better polygon reassembling algorithm with O(n log n) runtime was implemented -- the original paper and reference implementation do not focus on this part. Also, several additional corner cases are handled.
For further speed-up, the polygon clipping algorithm was extended to support processing more than two polygons at the same time, because with a runtime of O(n log n), it benefits from larger n. Currently, it usually works with max. 10 polygons. Even processing 3 polygons at once speeds up some examples by a factor of 2 over processing 2 polygons at once.
Depending on the complexity of the model, Hob3l may be much faster than using OpenSCAD with CGAL rendering.
The x-carriage.scad part of my
Prusa i3 MK3
printer from the Prusa github repository: let's first convert it
.csg. This conversion is quickly done with OpenSCAD, and the
resulting flat SCAD format is what Hob3l can read:
time openscad x-carriage.scad -o x-carriage.csg 0m0.034s
To convert to STL using openscad 3D CSG takes a while:
time openscad x-carriage.csg -o x-carriage.stl 0m45.208s
Doing the same with Hob3l in 0.2mm layers is about 50 times faster:
time hob3l x-carriage.csg -o x-carriage.stl 0m0.824s
The most complex part of the i3 MK3 printer, the
before it was reimplemented as
step file, takes 2m42s in openscad to
convert to STL, while Hob3l takes 1.24s, again with 0.2mm layers.
That is 130 times faster.
For one of my own parts
useless-box+body, which is less complex, but
does not care much about making rendering fast (I definitely set up
cylinders with too many polygon corners):
time openscad uselessbox+body.scad -o uselessbox+body.stl 0m53.433s time hob3l uselessbox+body.scad -o uselessbox+body.stl 0m0.610s
This is 85 times faster. Over half of the time is spent on writing the STL file, which is 23MB -- STL is huge. Loading and converting only takes 0.23s.
You can push the difference in speed by making the model more complex,
particularly when using high detail levels. E.g., the test31b.scad
$fn=99 for a few ellipsoids, causing openscad to slow
time openscad scad-test/test31b.scad -o test31b.stl 4m30.198s
In contrast, the different algorithms used by Hob3l do not slow down much:
time ./hob3l.exe scad-test/test31b.scad -o test31b.stl 0m0.748s
This is 350 times faster. The difference is of course that with Hob3l, the result is sliced into layers, as the following image demonstrates. The top is the OpenSCAD F6 view, the bottom is Hob3l's WebGL output in my web browser.
The difference of the conversion technique is visible in the model view of the STL, where the 2D CSG slicing technique clearly shows the layers, e.g. for a real-life example sliced a 0.2mm with Hob3l. The top is OpenSCAD's output in Slic3r, the bottom is Hob3l's output in Slic3r:
The final result of the slicer, however, is indistinguishable (I was unable to replicate the exact same view, so the Moiré patterns are different -- but the result is really the same), again OpenSCAD output top, Hob3l bottom:
The name Hob3l derives from the German word 'Hobel', which is a
'planer' (as in 'wood planer') in English. The 'e' was turned to
in recognition of the `slic3r' program.