Efficiencies and difficulties of creating files

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

Efficiencies and difficulties of creating files

OpenSCAD mailing list-2
If one makes a basic 3D object:

cube(size = [4,9,1], center = false);

then it calculates straight-forwardly enough:

Rendering Polygon Mesh using CGAL...
Geometries in cache: 2
Geometry cache size in bytes: 1456
CGAL Polyhedrons in cache: 0
CGAL cache size in bytes: 0
Total rendering time: 0:00:00.020
   Top level object is a 3D object:
   Facets:          6

but if one makes the same shape using hull operations:

(see screen grab at: https://community.carbide3d.com/t/efficiency-of-stl-generation-in-openscad/25639 )

Rendering Polygon Mesh using CGAL...
Geometries in cache: 11
Geometry cache size in bytes: 154600
CGAL Polyhedrons in cache: 3
CGAL cache size in bytes: 485872
Total rendering time: 0:00:07.088
   Top level object is a 3D object:
   Simple:        yes
   Vertices:        8
   Halfedges:      24
   Edges:          12
   Halffacets:     12
   Facets:          6
   Volumes:         2

which is an increase in some number of 100-fold.

Interestingly if one exports an STL, both files create a 1,535 byte STL file --- presumably there is some optimization which happens when creating the STL.

Would it improve handling of files created using similar techniques to perform this operation intermittently while working on an OpenSCAD file?

Is there some command which would do this already?

William

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

Re: Efficiencies and difficulties of creating files

tp3
On 06.09.20 21:02, William F. Adams via Discuss wrote:
> which is an increase in some number of 100-fold.

Just as you commanded by giving $fn = 80.

> Would it improve handling of files created using
> similar techniques to perform this operation intermittently
> while working on an OpenSCAD file?

What does that mean?

ciao,
  Torsten.


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

Re: Efficiencies and difficulties of creating files

cacb
In reply to this post by OpenSCAD mailing list-2
On 06.09.2020 21:02, William F. Adams via Discuss wrote:
> which is an increase in some number of 100-fold.
>
> Interestingly if one exports an STL, both files create a 1,535 byte STL
> file --- presumably there is some optimization which happens when
> creating the STL.

What you are observing is that the first example is a primitive solid,
no need to involve CGAL booleans in order to create an STL from it.

The second example uses union, hull and difference on multiple solid
primitives, "accidentally" ending up with a result equivalent to the
first primitive solid, in OpenSCAD this means using CGAL datastructures
and operations. What is listed for the second case is resulting CGAL
half edge datastructure object counts for the resulting cuboid-shaped
polyhedron. Translated to STL it gives the same result as in the
primitive case.

There is no optimization happening related to STL, you just devised two
very different routes to creating the same object, where one route is
much more complex than the other.

The 100-fold increase in cache size could perhaps be taken as a measure
of how much more complex the second route is. It does not say anything
about the complexity of the result.

Of course, if you could save intermediate objects to file and forget
about how complex the route was to get there, potentially you could
solve larger problems.

Regards
Carsten Arholm

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

Re: Efficiencies and difficulties of creating files

OpenSCAD mailing list-2
Carsten Arnholm wrote:

>There is no optimization happening related to STL, you just devised two
>very different routes to creating the same object, where one route is
>much more complex than the other.

Oh.

>The 100-fold increase in cache size could perhaps be taken as a measure
>of how much more complex the second route is. It does not say anything
>about the complexity of the result.

Okay. But what about the complexity of the internal representation?

>Of course, if you could save intermediate objects to file and forget
>about how complex the route was to get there, potentially you could
>solve larger problems.

Agreed, but I'd rather not trouble about writing out a file --- would it be feasible/desirable to afford a command in OpenSCAD which would do this sort of internal optimization with an eye towards allowing OpenSCAD to work faster and to allow working on more complex files?

William 


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

Re: Efficiencies and difficulties of creating files

skypuppy

That sounds interesting.


On 9/6/20 3:16 PM, William F. Adams via Discuss wrote:
Carsten Arnholm wrote:

>There is no optimization happening related to STL, you just devised two
>very different routes to creating the same object, where one route is
>much more complex than the other.

Oh.

>The 100-fold increase in cache size could perhaps be taken as a measure
>of how much more complex the second route is. It does not say anything
>about the complexity of the result.

Okay. But what about the complexity of the internal representation?

>Of course, if you could save intermediate objects to file and forget
>about how complex the route was to get there, potentially you could
>solve larger problems.

Agreed, but I'd rather not trouble about writing out a file --- would it be feasible/desirable to afford a command in OpenSCAD which would do this sort of internal optimization with an eye towards allowing OpenSCAD to work faster and to allow working on more complex files?

William 


_______________________________________________
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: Efficiencies and difficulties of creating files

OpenSCAD mailing list-2
In reply to this post by tp3
On 06.09.20 21:02, William F. Adams via Discuss wrote:
>> which is an increase in some number of 100-fold.

and Torsten Paul replied:

>Just as you commanded by giving $fn = 80.

but if I comment that out we still get:

Rendering Polygon Mesh using CGAL...
Geometries in cache: 11
Geometry cache size in bytes: 13048
CGAL Polyhedrons in cache: 3
CGAL cache size in bytes: 77296
Total rendering time: 0:00:00.724
Top level object is a 3D object:
Simple: yes
Vertices: 8
Halfedges: 24
Edges: 12
Halffacets: 12
Facets: 6
Volumes: 2
Rendering finished.

which still has some markedly larger numbers.

>> Would it improve handling of files created using
>> similar techniques to perform this operation intermittently
>> while working on an OpenSCAD file?

>What does that mean?

What if there were a command which would allow when possible simplifying the geometric representation to a simpler form involving fewer triangles?

Presumably if the basic cube and the hulled version had further operations applied to them the hulled version would be more complex in internal representation than the same operation applied to the basic cube.

If there were such a simplification process command it could be called after complex operations (with simple results?) and then simpler, more elegant (in the traditional sense of "scientifically correct") representation be used for further operations.

William


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

Re: Efficiencies and difficulties of creating files

cacb
In reply to this post by OpenSCAD mailing list-2
On 06.09.2020 22:16, William F. Adams via Discuss wrote:
> Carsten Arnholm wrote:
>  >Of course, if you could save intermediate objects to file and forget
>  >about how complex the route was to get there, potentially you could
>  >solve larger problems.
>
> Agreed, but I'd rather not trouble about writing out a file --- would it
> be feasible/desirable to afford a command in OpenSCAD which would do
> this sort of internal optimization with an eye towards allowing OpenSCAD
> to work faster and to allow working on more complex files?

In theory, perhaps. This would be something for the OpenSCAD developers
to answer. My guess is it is not so easy.

Carsten Arnholm


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

Re: Efficiencies and difficulties of creating files

tp3
In reply to this post by OpenSCAD mailing list-2
On 06.09.20 22:56, William F. Adams via Discuss wrote:
>>Just as you commanded by giving $fn = 80.
> but if I comment that out we still get:

Yes, it's still using the default resolution for the
hulled cylinders which have more vertices than just a
plain cube.

> What if there were a command which would allow when
> possible simplifying the geometric representation to
> a simpler form involving fewer triangles?

That might be useful, but could prove a bit difficult
to parameterize (e.g. limit by face angle, and such
things).

In addition to that, there's an almost finished change
implementing a persistent cache. Hopefully that will
get to mergeable state soon-ish. In combination with
render() that would allow to cover cases where people
did export partial models as STL before.

ciao,
  Torsten.

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

Re: Efficiencies and difficulties of creating files

MichaelAtOz
Administrator
In reply to this post by OpenSCAD mailing list-2
You should examine the Design/Display-[CSG Tree / CSG Products] for your
milled version.
You will see the complexity it produces.



-----
OpenSCAD Admin - email* me if you need anything,  or if I've done something stupid...

* on the Forum, click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work. Obviously inclusion of works of previous authors is not included in the above.

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

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
OpenSCAD Admin - email* me if you need anything, or if I've done something stupid...
* on the Forum, click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain;
to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work.
Obviously inclusion of works of previous authors is not included in the above.
Reply | Threaded
Open this post in threaded view
|

Re: Efficiencies and difficulties of creating files

Troberg
In reply to this post by OpenSCAD mailing list-2
OpenSCAD mailing list-2 wrote
> What if there were a command which would allow when possible simplifying
> the geometric representation to a simpler form involving fewer triangles?

Such as render()?

Try activating "show edges" and look at the difference between and after a
render() of your objects.




--
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: Efficiencies and difficulties of creating files

OpenSCAD mailing list-2
I wrote

>> What if there were a command which would allow when possible simplifying
>> the geometric representation to a simpler form involving fewer triangles?


>Such as render()?

>Try activating "show edges" and look at the difference between and after a
>render() of your objects.

Not seeing an appreciable difference between the basic cube and the hulled version, even after adding that command.

Doesn't seem to make a difference:

Original hulled version:

Rendering Polygon Mesh using CGAL...
Geometries in cache: 11
Geometry cache size in bytes: 13048
CGAL Polyhedrons in cache: 3
CGAL cache size in bytes: 77296
Total rendering time: 0:00:00.618
Top level object is a 3D object:
Simple: yes
Vertices: 8
Halfedges: 24
Edges: 12
Halffacets: 12
Facets: 6
Volumes: 2
Rendering finished.

After adding the render() command:

Parsing design (AST generation)...
Saved backup file: C:/Users/willa/OneDrive/Documents/OpenSCAD/backups/cube test -backup-HEciKFYI.scad
Compiling design (CSG Tree generation)...
Rendering Polygon Mesh using CGAL...
Geometries in cache: 11
Geometry cache size in bytes: 13048
CGAL Polyhedrons in cache: 4
CGAL cache size in bytes: 88640
Total rendering time: 0:00:00.034
Top level object is a 3D object:
Simple: yes
Vertices: 8
Halfedges: 24
Edges: 12
Halffacets: 12
Facets: 6
Volumes: 2
Rendering finished.

William



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

Re: Efficiencies and difficulties of creating files

OpenSCAD mailing list-2
In reply to this post by MichaelAtOz
MichaelAtOz wrote:

>You should examine the Design/Display-[CSG Tree / CSG Products] for your
>milled version.
>You will see the complexity it produces.

I'm not disputing this is a complex way to make things and results in a complex representation internally --- it's just that that internal representation is not optimal --- wouldn't having a way (or integrating a mechanism) to optimize the internal representation be a good idea? --- if every time an object is carved into it gets more complex doesn't that limit the ultimate possible complexity?

If there could be an optimization/simplification of the geometric representation, then the program could run faster, right?

William


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

Re: Efficiencies and difficulties of creating files

MichaelAtOz
Administrator

Well, the problem is OpenSCAD uses two libraries.

 

OpenCSG for preview, which for want of a complex description, 'simulates' geometry without actually calculating real 3D objects.

 

CGAL, which actually calculates real CSG points, and is complex and slow.

 

That is the OpenSCAD model, quick preview, then slow real geometry rendering.

 

Both are maintained by other, non-OpenSCAD, agencies.

 

So OpenSCAD developers cannot do what you want.

 

OpenSCAD is what it is. If it doesn't support your method of use, there is little that can be done.

 


From: Discuss [mailto:[hidden email]] On Behalf Of William F. Adams via Discuss
Sent: Mon, 7 Sep 2020 22:38
To: [hidden email]
Cc: William F. Adams
Subject: Re: [OpenSCAD] Efficiencies and difficulties of creating files

 

MichaelAtOz wrote:

>You should examine the Design/Display-[CSG Tree / CSG Products] for your
>milled version.
>You will see the complexity it produces.

 

I'm not disputing this is a complex way to make things and results in a complex representation internally --- it's just that that internal representation is not optimal --- wouldn't having a way (or integrating a mechanism) to optimize the internal representation be a good idea? --- if every time an object is carved into it gets more complex doesn't that limit the ultimate possible complexity?

 

If there could be an optimization/simplification of the geometric representation, then the program could run faster, right?

 

William

 


Virus-free. www.avg.com

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
OpenSCAD Admin - email* me if you need anything, or if I've done something stupid...
* on the Forum, click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain;
to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work.
Obviously inclusion of works of previous authors is not included in the above.
tp3
Reply | Threaded
Open this post in threaded view
|

Re: Efficiencies and difficulties of creating files

tp3
On 07.09.20 15:02, MichaelAtOz wrote:
> So OpenSCAD developers cannot do what you want.

I would not call it impossible, it might be an interesting
challenge as it could be beneficial to make it a pass through
operation for preview.
Remeshing in general (and both directions, simplify and
subdivide) should be doable. CGAL even supports (according to
the documentation) mesh processing for fixing geometry, so
that would fall into the same category of operations.

ciao,
  Torsten.


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

Re: Efficiencies and difficulties of creating files

MichaelAtOz
Administrator
OK, well, perhaps, I could suggest, without criticism, given other activity, it would not be
something that one could expect to happen, in the near future.

> -----Original Message-----
> From: Discuss [mailto:[hidden email]] On Behalf Of Torsten Paul
> Sent: Tue, 8 Sep 2020 00:00
> To: [hidden email]
> Subject: Re: [OpenSCAD] Efficiencies and difficulties of creating files
>
> On 07.09.20 15:02, MichaelAtOz wrote:
> > So OpenSCAD developers cannot do what you want.
>
> I would not call it impossible, it might be an interesting
> challenge as it could be beneficial to make it a pass through
> operation for preview.
> Remeshing in general (and both directions, simplify and
> subdivide) should be doable. CGAL even supports (according to
> the documentation) mesh processing for fixing geometry, so
> that would fall into the same category of operations.
>
> ciao,
>   Torsten.
>
>
> _______________________________________________
> OpenSCAD mailing list
> [hidden email]
> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


--
This email has been checked for viruses by AVG.
https://www.avg.com


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
OpenSCAD Admin - email* me if you need anything, or if I've done something stupid...
* on the Forum, click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain;
to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work.
Obviously inclusion of works of previous authors is not included in the above.
tp3
Reply | Threaded
Open this post in threaded view
|

Re: Efficiencies and difficulties of creating files

tp3
On 07.09.20 16:08, MichaelAtOz wrote:
> OK, well, perhaps, I could suggest, without criticism,
> given other activity, it would not be something that
> one could expect to happen, in the near future.

That's certainly true. But there's always a chance someone
coming along taking on that specific challenge. It does
actually happen, like with the very nice Jump-to-Source
feature which was implemented by someone who contributed
that as first OpenSCAD change.

ciao,
  Torsten.

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

Re: Efficiencies and difficulties of creating files

doug.moen
In reply to this post by OpenSCAD mailing list-2
On Mon, Sep 7, 2020, at 8:37 AM, William F. Adams via Discuss wrote:
If there could be an optimization/simplification of the geometric representation, then the program could run faster, right?

Yes, an optimization pass could speed things up, at least for some special cases. There already is some limited optimization: a stack of affine transformations is converted to a single transformation matrix. This alone won't make OpenSCAD fast.

The main reason that OpenSCAD is slow is that it converts each geometric primitive to a triangle mesh as early as possible, then it performs CSG operations (like union, intersection, difference) directly on these triangle meshes. This is extremely expensive, especially if you are representing curved surfaces that require a large number of triangles for a smooth approximation. The slowness is caused by the large number of triangles that must be processed by the CSG operations.

The way to render these models quickly is to defer mesh generation as long as possible. Ideally, you would build the CSG tree, optimize it, then directly convert the CSG tree to a triangle mesh. The trick is to convert the CSG tree to an intermediate representation from which you can quickly generate triangles.

A number of people have built OpenSCAD-like systems that use signed distance fields in the intermediate representation of the CSG tree (although there is a lot of variation in these intermediate representations, and it's an active area of research). It's not hard to build a system that renders at a million triangles per second (using an algorithm that runs on the CPU). My system, Curv, is about this fast. If you could run your rendering algorithm on the GPU, then mesh generation would be a 100 times faster.

One major barrier to changing OpenSCAD to use this kind of fast rendering technology is backward compatibility. OpenSCAD programs are tightly coupled to the current rendering algorithm. The idiomatic way to make a regular polygon or prism is circle and cylinder, because everybody knows that circles and cylinders are converted to polygons and prisms as early as possible.

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

Re: Efficiencies and difficulties of creating files

tp3
On 07.09.20 16:28, Doug Moen wrote:
> One major barrier to changing OpenSCAD to use this kind
> of fast rendering technology is backward compatibility.
> OpenSCAD programs are tightly coupled to the current
> rendering algorithm.

I totally disagree with that. The only barrier I see is that
there's not enough people working on it.

There's not much limitation in the language that would
prevent doing SDF rendering. It's possible to convert code
without hull/minkowski to a GPU shader. There's even existing
code doing that based on the implicitcad implementation.

The core structure of OpenSCAD to generate an object tree
first and do the mesh rendering in the second step does
work for using different rendering processes (as proven
by the preview / render separation).

Sure there's likely some devil in the details, but if people
would work together on solving the problems, I believe it's
totally doable. If we don't manage to spark the interest of
more developers, it might not happen ever.

Yes, it makes some things more complicated when working in
a team on some existing project, but it also has a number
of huge benefits in the long term. Like we will hopefully
have a 3 month project working on documentation again. This
time with focus on free and open education/course material.

ciao,
  Torsten.


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

Re: Efficiencies and difficulties of creating files

doug.moen
There's no way to create an SDF renderer that is a plug in replacement for the existing CGAL renderer.
 * There aren't SDF implementations of hull and minkowski, as you mention.
 * The meshes that are generated would be completely different. The unit tests would break, and projects that rely on precise control over the triangles that are generated to STL would likely break.

So this would have to be an optional 3rd rendering path that doesn't support the entire OpenSCAD language.

One of the attractive features of SDF modelling is the availability of additional CSG operators like blending and replication, and non-affine transformations like bend and twist. If these were made available in OpenSCAD, they wouldn't work in the OpenCSG previewer or the CGAL renderer. So this is one thing that would lead to OpenSCAD being split into two incompatible dialects, depending on which renderer you are using. Another thing is that when you optimize your code to speed up rendering, you use different tricks depending on which renderer you are using.

Curv and Libfive allow you to define new shape primitives by directly defining signed distance functions. It's the analog of extending OpenSCAD to support splines and sweeps using polyhedron. It's a feature I can't live without; I use it in about half my projects. In Curv and Libfive at least, this feature depends on the treatment of functions and shapes as first class values. An SDF shape operator is a function that takes shapes and other arguments and returns a structure containing a function that maps a point onto a distance, and the OpenSCAD language won't let you do this. If this capability were added to OpenSCAD, it would only work in the SDF dialect of OpenSCAD, because SDFs can't be rendered by OpenCSG or CGAL.

You mention the possibility of previewing a model by converting it to a GPU fragment shader (an approach that works in OpenGL 2). I've implemented this in Curv, but it has performance cliffs when you try to union together a large number of objects.. Limitations of this approach are also why I don't have the text and polyhedron primitives. As a result, you can't just transliterate an arbitrary OpenSCAD program into Curv and expect the previewer to work. You often have to write the code differently. To eliminate these performance cliffs, I am researching alternative previewing technologies based on how high performance 3D rendering engines work in video games, and I hope to use these in the successor to Curv. But these techniques require compute shaders (OpenGL 4.3 or later, a version of OpenGL that isn't supported by MacOS) and other modern APIs. So the successor to Curv will use Vulkan, Metal, DX12, not OpenGL. By contrast, OpenSCAD currently runs on any Windows, MacOS or Linux system with a GPU, since it only requires OpenGL 2.

On Mon, Sep 7, 2020, at 10:54 AM, Torsten Paul wrote:
> The only barrier I see is that
> there's not enough people working on it.

I see more barriers than this. I'm surprised you think this is a viable approach for OpenSCAD, given what I think the challenges are.

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

Re: Efficiencies and difficulties of creating files

mondo
Well, if you need to crunch numbers, then maybe you can use Watson for
free, for a while. https://www.ibm.com/cloud/watson-assistant/

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