Functional OpenSCAD, working with vertex data
On Thu, Feb 08, 2018 at 08:38:14PM +0000, Alan Cox wrote:
You really need to spend some time actually profiling it. The interpreter
speed is basically irrelevant for OpenSCAD because each operation is
dominated by the 3D model manipulation time which is all in C++ already.
If it takes 0.1 milliseconds longer to interpret than be compiled when
executing an operation that takes CGAL's C++ code 15 seconds it's kind of
irrelevant whether you interpret it or not.
Right! Example anecdote (30 years ago):
I was annoyed at the MSDOS "sort" program (mostly the 64k filesize
limit... Ugh!). I rewrote it. I benchmarked it.
Turns out my code was 10 times slower in reading the source file.
Turns out my code was 10 times faster at the actual sorting.
Overall: my program was 8 times faster than the microsoft version.
So.... If you guess wrong as to what is taking a long time, and start
optimizing, you will end up optimizing the wrong thing.
So you need to either guess right or benchmark.... :-)
Roger.
--
** R.E.Wolff@BitWizard.nl ** http://www.BitWizard.nl/ ** +31-15-2600998 **
** Delftechpark 26 2628 XH Delft, The Netherlands. KVK: 27239233 **
-- BitWizard writes Linux device drivers for any device you may have! --
The plan was simple, like my brother-in-law Phil. But unlike
Phil, this plan just might work.
Once you start adding for loops and recursive functions the interpreter can
get slow. My code to draw a 20 way ribbon cable with a Bezier curve, a fold
and some bends takes about 20 seconds to compute and next to no time to
render. I am contemplating adding a time() function to to aid optimising it.
On 9 February 2018 at 09:08, Rogier Wolff R.E.Wolff@bitwizard.nl wrote:
On Thu, Feb 08, 2018 at 08:38:14PM +0000, Alan Cox wrote:
You really need to spend some time actually profiling it. The interpreter
speed is basically irrelevant for OpenSCAD because each operation is
dominated by the 3D model manipulation time which is all in C++ already.
If it takes 0.1 milliseconds longer to interpret than be compiled when
executing an operation that takes CGAL's C++ code 15 seconds it's kind of
irrelevant whether you interpret it or not.
Right! Example anecdote (30 years ago):
I was annoyed at the MSDOS "sort" program (mostly the 64k filesize
limit... Ugh!). I rewrote it. I benchmarked it.
Turns out my code was 10 times slower in reading the source file.
Turns out my code was 10 times faster at the actual sorting.
Overall: my program was 8 times faster than the microsoft version.
So.... If you guess wrong as to what is taking a long time, and start
optimizing, you will end up optimizing the wrong thing.
So you need to either guess right or benchmark.... :-)
Roger.
--
** R.E.Wolff@BitWizard.nl ** http://www.BitWizard.nl/ ** +31-15-2600998 **
** Delftechpark 26 2628 XH Delft, The Netherlands. KVK: 27239233 **
-- BitWizard writes Linux device drivers for any device you may have! --
The plan was simple, like my brother-in-law Phil. But unlike
Phil, this plan just might work.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
On 9 February 2018 at 09:47, nop head nop.head@gmail.com wrote:
Once you start adding for loops and recursive functions the interpreter
can get slow. My code to draw a 20 way ribbon cable with a Bezier curve, a
fold and some bends takes about 20 seconds to compute and next to no time
to render. I am contemplating adding a time() function to to aid optimising
it.
On 9 February 2018 at 09:08, Rogier Wolff R.E.Wolff@bitwizard.nl wrote:
On Thu, Feb 08, 2018 at 08:38:14PM +0000, Alan Cox wrote:
You really need to spend some time actually profiling it. The
interpreter
speed is basically irrelevant for OpenSCAD because each operation is
dominated by the 3D model manipulation time which is all in C++ already.
If it takes 0.1 milliseconds longer to interpret than be compiled when
executing an operation that takes CGAL's C++ code 15 seconds it's kind
of
irrelevant whether you interpret it or not.
Right! Example anecdote (30 years ago):
I was annoyed at the MSDOS "sort" program (mostly the 64k filesize
limit... Ugh!). I rewrote it. I benchmarked it.
Turns out my code was 10 times slower in reading the source file.
Turns out my code was 10 times faster at the actual sorting.
Overall: my program was 8 times faster than the microsoft version.
So.... If you guess wrong as to what is taking a long time, and start
optimizing, you will end up optimizing the wrong thing.
So you need to either guess right or benchmark.... :-)
Roger.
--
** R.E.Wolff@BitWizard.nl ** http://www.BitWizard.nl/ ** +31-15-2600998
**
** Delftechpark 26 2628 XH Delft, The Netherlands. KVK: 27239233 **
-- BitWizard writes Linux device drivers for any device you may have! --
The plan was simple, like my brother-in-law Phil. But unlike
Phil, this plan just might work.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
I found a post by Carsten Arnholm where he measures Carve as being ~40x
faster than CCAL in OpenSCAD, for boolean operations. This is using a
parallel implementation on 4 cores, so lets say that Carve is at least 10x
faster than CGAL. But the OpenSCAD interpreter is ~1000x slower than C++,
so if the Carve data structures and algorithms were recoded in OpenSCAD,
they'd run roughly 100x slower than CGAL. These are rough estimates. So,
the Carve library seems to be the way to go.
As for ImplicitCAD, that project seems to have been stalled for a few
years. There are newer projects that are pushing the technology of signed
distance fields and function representation much further. The ImplicitCAD
implementation of union and intersection is somewhat worse than O(N), and
can be much worse on a GPU if you aren't careful. In Curv, I can union a
billion spheres in a fraction of a second, but that's a special case where
all of the shapes being unioned are instances of the same shape. There is
further work I need to do to optimize union for the general case: I want to
get the cost < O(N). I don't know if booleans on triangle meshes can be
faster than O(N).
On 8 February 2018 at 15:38, Alan Cox alan@lxorguk.ukuu.org.uk wrote:
On Thu, 8 Feb 2018 13:08:26 -0500
doug moen doug@moens.org wrote:
OpenSCAD is an interpreted language, and the interpreter is not very
fast.
Try profiling it and you'll see the interpreter isn't a problem.
If OpenSCAD programs were compiled into machine code using the back end
of
a C++ compiler, then run times would be similar to C++, but they are not.
They would but that would be almost the same speed as it is now.
The factor of 1000x is based on some informal benchmarks that I have run
You really need to spend some time actually profiling it. The interpreter
speed is basically irrelevant for OpenSCAD because each operation is
dominated by the 3D model manipulation time which is all in C++ already.
If it takes 0.1 milliseconds longer to interpret than be compiled when
executing an operation that takes CGAL's C++ code 15 seconds it's kind of
irrelevant whether you interpret it or not.
It spends all its time doing CGAL stuff in highly inefficient number
representations and quite possibly also wrong algorithms for the task.
Add to the fact it doesn't multi-thread properly and yeah - it's slow.
For many things ImplicitCad is much faster, but not always and it can
do things well that OpenSCAD can't but also lacks things OpenSCAD has.
If CGAL could be rebuilt into 64bit fixed point, made multiprocessor
aware, and some of the interesting problems around the significance of
mathematical errors at joins dealth with then it probably could be 1000
times faster - but it's got zero to do with the interpreter.
Alan
On 2018-02-09 16:11, doug moen wrote:
I found a post by Carsten Arnholm where he measures Carve as being
~40x faster than CCAL in OpenSCAD, for boolean operations. This is
using a parallel implementation on 4 cores, so lets say that Carve is
at least 10x faster than CGAL. But the OpenSCAD interpreter is ~1000x
slower than C++, so if the Carve data structures and algorithms were
recoded in OpenSCAD, they'd run roughly 100x slower than CGAL. These
are rough estimates. So, the Carve library seems to be the way to go.
If you want to experiment with this idea without messing up OpenSCAD,
you could implement the .xcsg file format in OpenSCAD and run the xcsg
application (which uses Carve) separately to compare with the
performance of standard OpenSCAD/CGAL for the same model.
https://github.com/arnholm/xcsg/wiki
https://github.com/arnholm/xcsg/releases
For most models I agree with those who say that the language parsing is
usually not the dominating factor wrt. computational time, because the
mesh booleans dominate everything else, it almost always does not matter
if the language parser is sluggish compared to native C++ (I use
AngelScript and it seems fast enough, the script objects are compiled as
C++).
Carsten Arnholm
On Fri, Feb 09, 2018 at 10:11:19AM -0500, doug moen wrote:
I don't know if booleans on triangle meshes can be
faster than O(N).
I would think that almost nothing can be faster than O(N).
nn=1000;
for (i=[0:nn])
translate ([i*5,0,0]) sphere (r=3.5);
That would surely require O(N) operations, right?
Roger.
--
** R.E.Wolff@BitWizard.nl ** http://www.BitWizard.nl/ ** +31-15-2600998 **
** Delftechpark 26 2628 XH Delft, The Netherlands. KVK: 27239233 **
-- BitWizard writes Linux device drivers for any device you may have! --
The plan was simple, like my brother-in-law Phil. But unlike
Phil, this plan just might work.
rew wrote
On Fri, Feb 09, 2018 at 10:11:19AM -0500, doug moen wrote:
I don't know if booleans on triangle meshes can be
faster than O(N).
I would think that almost nothing can be faster than O(N).
nn=1000;
for (i=[0:nn])
translate ([i*5,0,0]) sphere (r=3.5);
That would surely require O(N) operations, right?
...
What's N? I could, for example, imagine that there's some algorithm that
can do booleans in O(M log N) time where M is the side of the boundary and N
is the size of the mesh. Constructing the mesh would still require at least
O(N) time though. (A 'searchable' mesh probably requires O(N log N) time to
construct.)
--
Sent from: http://forum.openscad.org/
Well, the octree-based booleans seem to work. Just a bit slow to generate
the octrees.
http://forum.openscad.org/file/t2140/octree-booleans.png
--
Sent from: http://forum.openscad.org/