Functional OpenSCAD, working with vertex data

classic Classic list List threaded Threaded
58 messages Options
123
Reply | Threaded
Open this post in threaded view
|

Re: Functional OpenSCAD, working with vertex data

doug.moen
Fast booleans are not a trivial problem, regardless of what shape representation you use.

Also, keep in mind that any data structure or algorithm you code in OpenSCAD can be reproduced in C++ where it will run a thousand times faster, and you can get even higher performance by rendering on the GPU instead of on the CPU.

On 7 February 2018 at 21:33, NateTG <[hidden email]> wrote:
As an attempt to attack the problem of booleans, I wrote an octree voxelizer
- that would make the boolean operations trivial, but it seems too slow to
be viable.

octree.scad <http://forum.openscad.org/file/t2140/octree.scad>



--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Functional OpenSCAD, working with vertex data

frankv
A thousand times faster? I don't understand that. Given that OpenSCAD is written in C++, it seems to me that it will take only a little more time -- the time to read the OpenSCAD source code and to parse them. The time to do the actual operation will be exactly the same.

Frank

On Fri, Feb 9, 2018 at 2:27 AM, doug moen <[hidden email]> wrote:
Fast booleans are not a trivial problem, regardless of what shape representation you use.

Also, keep in mind that any data structure or algorithm you code in OpenSCAD can be reproduced in C++ where it will run a thousand times faster, and you can get even higher performance by rendering on the GPU instead of on the CPU.




_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Functional OpenSCAD, working with vertex data

doug.moen
OpenSCAD is an interpreted language, and the interpreter is not very fast. 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. The factor of 1000x is based on some informal benchmarks that I have run comparing speed of the two languages. Javascript interpreters are much faster: they typically use JIT compilers that compile some parts of the program into machine code. This is why you can't expect to match the performance of openjscad (or C++ mesh libraries) by implementing mesh primitives in openscad.


On 8 February 2018 at 12:30, Frank van der Hulst <[hidden email]> wrote:
A thousand times faster? I don't understand that. Given that OpenSCAD is written in C++, it seems to me that it will take only a little more time -- the time to read the OpenSCAD source code and to parse them. The time to do the actual operation will be exactly the same.

Frank

On Fri, Feb 9, 2018 at 2:27 AM, doug moen <[hidden email]> wrote:
Fast booleans are not a trivial problem, regardless of what shape representation you use.

Also, keep in mind that any data structure or algorithm you code in OpenSCAD can be reproduced in C++ where it will run a thousand times faster, and you can get even higher performance by rendering on the GPU instead of on the CPU.




_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org



_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Functional OpenSCAD, working with vertex data

Ronaldo
In reply to this post by NateTG
Where is library subdivision.scad found?

2018-02-08 0:33 GMT-02:00 NateTG <[hidden email]>:
As an attempt to attack the problem of booleans, I wrote an octree voxelizer
- that would make the boolean operations trivial, but it seems too slow to
be viable.

octree.scad <http://forum.openscad.org/file/t2140/octree.scad>



--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Functional OpenSCAD, working with vertex data

Ronaldo
Ok, I have found it but the function triangulate_poly3d() called by octree.scad is missing.

2018-02-08 18:04 GMT-02:00 Ronaldo Persiano <[hidden email]>:
Where is library subdivision.scad found?

2018-02-08 0:33 GMT-02:00 NateTG <[hidden email]>:
As an attempt to attack the problem of booleans, I wrote an octree voxelizer
- that would make the boolean operations trivial, but it seems too slow to
be viable.

octree.scad <http://forum.openscad.org/file/t2140/octree.scad>

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Functional OpenSCAD, working with vertex data

Alan Cox
In reply to this post by doug.moen
On Thu, 8 Feb 2018 13:08:26 -0500
doug moen <[hidden email]> 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

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Functional OpenSCAD, working with vertex data

NateTG
In reply to this post by Ronaldo
Sorry, forgot about that.

subdivision.scad <http://forum.openscad.org/file/t2140/subdivision.scad>  




--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Functional OpenSCAD, working with vertex data

frankv
In reply to this post by doug.moen
Right. But when I do a difference of two complex meshes, something less than a millisecond will be spent on interpreting the code, and 10 minutes on doing the operation. If I could compile OpenScad code (perhaps via C++) or wrote an entire C++ program to do that operation,  it would still take 10 minutes to execute. Unless there is some faster difference() function available. In which case we should link that faster library into OpenScad. 

On Friday, February 9, 2018, doug moen <[hidden email]> wrote:
OpenSCAD is an interpreted language, and the interpreter is not very fast. 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. The factor of 1000x is based on some informal benchmarks that I have run comparing speed of the two languages. Javascript interpreters are much faster: they typically use JIT compilers that compile some parts of the program into machine code. This is why you can't expect to match the performance of openjscad (or C++ mesh libraries) by implementing mesh primitives in openscad.


On 8 February 2018 at 12:30, Frank van der Hulst <[hidden email]> wrote:
A thousand times faster? I don't understand that. Given that OpenSCAD is written in C++, it seems to me that it will take only a little more time -- the time to read the OpenSCAD source code and to parse them. The time to do the actual operation will be exactly the same.

Frank

On Fri, Feb 9, 2018 at 2:27 AM, doug moen <[hidden email]> wrote:
Fast booleans are not a trivial problem, regardless of what shape representation you use.

Also, keep in mind that any data structure or algorithm you code in OpenSCAD can be reproduced in C++ where it will run a thousand times faster, and you can get even higher performance by rendering on the GPU instead of on the CPU.




_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org



_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Functional OpenSCAD, working with vertex data

NateTG
frankv wrote
> ...
>  In which case we should link that faster library into OpenScad.
> ...

Here's a github issue from 2014 where people are taking about that.

https://github.com/openscad/openscad/issues/630



--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Functional OpenSCAD, working with vertex data

NateTG
In reply to this post by Alan Cox
Alan Cox wrote
> ... 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
> ...

That's not always the case.  My (admittedly somewhat demented) userland
voxel geometry stuff spends almost all of its time in the interpreter.   If
the interpreter were more computationally capable, it would be a much more
interesting thing in terms of applications.



--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
rew
Reply | Threaded
Open this post in threaded view
|

Re: Functional OpenSCAD, working with vertex data

rew
In reply to this post by Alan Cox
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.

--
** [hidden email] ** 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
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Functional OpenSCAD, working with vertex data

nophead
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 <[hidden email]> 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.

--
** [hidden email] ** http://www.BitWizard.nl/ ** <a href="tel:%2B31-15-2600998" value="+31152600998">+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
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Functional OpenSCAD, working with vertex data

nophead



On 9 February 2018 at 09:47, nop head <[hidden email]> 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 <[hidden email]> 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.

--
** [hidden email] ** http://www.BitWizard.nl/ ** <a href="tel:%2B31-15-2600998" value="+31152600998" target="_blank">+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
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org



_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Functional OpenSCAD, working with vertex data

doug.moen
In reply to this post by Alan Cox
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 <[hidden email]> wrote:
On Thu, 8 Feb 2018 13:08:26 -0500
doug moen <[hidden email]> 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


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Functional OpenSCAD, working with vertex data

cacb
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

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
rew
Reply | Threaded
Open this post in threaded view
|

Re: Functional OpenSCAD, working with vertex data

rew
In reply to this post by doug.moen
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.

--
** [hidden email] ** 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
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Functional OpenSCAD, working with vertex data

NateTG
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/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Functional OpenSCAD, working with vertex data

NateTG
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/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
123