& text()
;)

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

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.

The TPP is no simple “trade agreement.”  Fight it! http://www.ourfairdeal.org/  time is running out!

View this message in context: http://forum.openscad.org/Functional-OpenSCAD-working-with-vertex-data-tp21080p21082.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

On Wed, Apr 5, 2017 at 1:31 AM, MichaelAtOz oz.at.michael@gmail.com wrote:

Haven't done a ton of testing.  Things like sphere take a little
longer to process when initially hitting f5, but the actual framerate
of previewing them should be nearly the same.

In general I would expect slightly worse performance if for example
translating an existing script to a functional version, one-to-one for
every operation.  The advantage comes when you use some of the
features to generate a shape in an alternate way.  For example one
enhancement I made was supporting radius on squares.  Internally it
concatenates 4 90-degree arc paths, which isn't directly comparable to
any builtin modules.  I did a little bit of comparing this with other
methods of generating rounded squares (hull of 4 circles, etc.) and it
was the fastest of the methods I tested.

On Wed, Apr 5, 2017 at 1:34 AM, MichaelAtOz oz.at.michael@gmail.com wrote:

Yeah I didn't put text since I consider that completely out of the
question. Its not possible to open files to read font definitions or
any other lower level font api that would give vertex data.  Even if I
could read files, i'm not particularly interested in implementing my
own truetype library or whatever it is that would be needed.

The other ones listed I could see maybe being feasible, but will
require some more research on my part as to what algorithms to use and
how to shoehorn them into the openscad language.

On Wed, Apr 5, 2017 at 9:21 AM, TLC123 torleif.ceder@gmail.com wrote:

I haven't looked into the others, but subdivision is definitely a
possibility!  I developed some alternative sphere implementations
shortly before releasing this functional library:
https://gist.github.com/thehans/052129033443d8a8c14ac1e69b42e8da

At the bottom of the file is a subdivision function that is used for
generating the icosahedron based sphere.
I think I will add these to the repo soon, I just need to rewrite some
of the functions to be consistent with the interface conventions of
the rest of the library.

On Wed, Apr 5, 2017 at 10:28 AM, Parkinbot rudolf@parkinbot.com wrote:

I think it should be theoretically possible to perform boolean
operations directly on the vertex/face data from within openscad.
They are definitely going to be some of the more involved code
compared with the other functions, that is why I put them off for some
of the last things to attempt.

I would probably try to replicate the simplest implementation that
I've seen which is this: http://evanw.github.io/csg.js/docs/
That code was the basis for the original OpenJSCAD code.  It actually
makes it look not so bad, though translating some of these functions
into openscad might prove difficult.  I'm not sure as I haven't yet
attempted it.

Wouldn't it be something if it could be done faster than the current
CGAL implementation?  :P
I'd give it 50% odds of being faster, assuming it gets written.

I just added some more files to the repo.

The alternative_spheres and subdivision I had mentioned in a previous
post and those might have some niche uses, but double_fillet.scad is
one that I think is quite versatile and applicable to a wide range of
designs.
It creates a 2d path for a smooth transition between two heights by
having a top radius and bottom radius, and calculating the line
tangent to both for the slope in between the radii.
Then you can linear_extrude this 2d shape to create a sort of ledge on
a part, or rotate extrude to create a mound, protrusion, knob, and
even shapes roughly resembling a mushroom cloud!

If you load the double_fillet.scad file in OpenSCAD, you can view an
animated example of some of the possibilities with different
combinations of radii and offsets.

Or watch this short video animation:
https://photos.google.com/share/AF1QipPO5TCMSigJob_mThznq7jmtVjRaA_dSE-_LTLx76KZnfHrLHYEYpivonuTdGaWDQ?key=QzkwX2l2QUtmVXdpWjU3Q05SLW5DNUpFY29YSUJB

I've been developing some of these functions and ideas gradually over
time as I design new parts that need particular difficult features,
etc.  And I think the most powerful concept I've taken away from it is
a fairly simple one:  The creation of 2d paths, building them up by
concatenating lists of points and arcs, can be used to make really
nice designs with smooth fillets, and does so quite efficiently.
Every arc that can be placed as part of a 2d path before its extruded
is at least one less boolean operation required to make that shape.
At its heart the double fillet is just two arcs on a path.

Another example is this endstop mount design which I'm quite proud of:
http://www.thingiverse.com/thing:2204123
In the scad for that, there is a module to create the "base_profile"
which is a fairly complex 2d shape that would have otherwise used
quite a lot of boolean operations.
All it is, is a bunch of arcs concatenated together (in the script the
function is called arcPath, I've since shortened it to just "arc" in
functional.scad )

http://i.imgur.com/FKqiiNr.png

On Wed, Apr 5, 2017 at 1:31 PM, Hans L thehans@gmail.com wrote:

operations directly on the vertex/face data from within openscad. ...

I have a pretty good idea of a way to do it, but it's going to be a chore to
write.  I also don't know how to running into issues with the recursion
limit.

P.S. I'm not sure I've ever seen then ".x" in "s.x" in OpenSCAD before.  Do
you know if it's documented anywhere?

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

Marius said:

not used to this syntax.

v.x is the first element of vector v, same as v[0].

Another way of designing this feature is to provide built-in global
variables
X = 0
Y = 1
Z = 2
and then you can write v[X] to get the first element of v.

On 25 January 2018 at 16:28, Marius Kintel marius@kintel.net wrote:

I like the .x .y .z shortcuts and I think they are somewhat useful
feature, but I actually feel that it doesn't go far enough!  I think
support for swizzling, much like GLSL would be a really handy
addition.  https://www.khronos.org/opengl/wiki/Data_Type_(GLSL)#Swizzling

So you could do something like this for example:
p3d = [1,2,3];
p2d = p3d.xy; // alternative to: [ p3d[0], p3d[1] ]  more clean and
concise with swizzling

And all the other combinations and transposing of axes could also be possible.

On Thu, Jan 25, 2018 at 3:28 PM, Marius Kintel marius@kintel.net wrote:

Wow… I agree… I love the dot notation and had no idea it existed… I think it really helps with readability of code.
I also agree the swizzling would be great.

The resurrection of this thread has spurred me to make some updates to
the library over the past few days.

https://github.com/thehans/FunctionalOpenSCAD

• I've created an overall README.md for the project and tried to
  document everything a bit better.
• A signed_volume function has been added, thanks to NateTG.
• Added new planes.scad file for creating planes from points,
  visualization, etc.
• Plus a handful of other minor additions and changes.

I hope the new documentation makes it all easier to understand.  Let
me know if anything in particular is unclear.

The splitPolygonByPlane function in planes.scad is my attempt to port
this function from OpenJSCAD/csg.js  My implementation doesn't work
100% and I guess that's where I stalled on further implementing
boolean ops, etc.  I haven't touched that code in months and forgot a
lot of what I was doing.  I'm not particularly motivated to pick that
code back up at the moment, but I fiured it was still worthwhile to
show what progress I had made.

Do you have ideas for any other features you would like to see added?
(aside from the currently unsupported OpenSCAD builtins)

Lastly I'm curious anyone has found FunctionalOpenSCAD useful in their
own projects so far?

Thanks
-Hans

On Thu, Jan 25, 2018 at 6:19 PM, Hugo Jackson hugo@apres.net wrote:

(aside from the currently unsupported OpenSCAD builtins)

I'm not sure what you want the scope of the project to be.

Something that is likely to be useful in general (but may be scope creep) is
a 'mesh checker' that takes points and faces as arguments and identifies
easy-to-detect topological flaws like holes and non-manifold edges.
Reverse-wound faces or sections are relatively easy to detect as a special
case, and non-manifold vertices shouldn't be that much more effort.  A more
advanced version could also detect self-intersection (though that's halfway
to a clipper.)  Another ambitious extension of this idea is to have
functions to fix some of these issues.

A function that fills in a solid under a patch of surface could be handy,
and shouldn't be that hard to write.

I see you have subdivide, but no face triangulation function that lets you
apply it to to the output of cube().  That seems like a missing piece and
the algorithms are well-documented.  (I was tinkering with this yesterday.)
Armed with that, you can start doing plastic deform stuff pretty easily.
Generic plastic deforms aren't going to be available without functions as
first-class variables, but you can still have good support for basic stuff
like projective, cylindrical, and spherical transforms.

An alternative to using a clipper for booleans is a voxel-based geometry
engine.  Union, intersection, and subtraction are really easy with that,
but making it viable in OpenSCAD requires conversion utilities to switch
between the voxel and surface models of geometry.

Automated mesh smoothing operations like filleting, beveling, and spline
fitting are things that people want, but that aren't available in OpenSCAD.

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

Thanks for doing this project!

It strikes me that writing more of openscad in openscad
will make porting easier, and maybe foster unification
of openscad and openjscad.

On Sun, Jan 28, 2018 at 12:10 PM, Hans L thehans@gmail.com wrote:

--

Best Regards.
This is unedited.
This message came out of me
via a suboptimal keyboard.

On Mon, Jan 29, 2018 at 9:08 AM, NateTG nate-openscadforum@pedantic.org wrote:

Well, the core "functional.scad" is primarily intended to implement
only OpenSCAD's builtins, with minimal extra functions needed to
accomplish that.
On one hand it can be looked at as a sort of reference implementation,
like Tony was saying just above.  On the other hand the library is a
sort of conversation piece for discussion on some of OpenSCAD's
limitations and how we might improve OpenSCAD in such a way that makes
this library obsolete!

For any addiitonal functionality that extends beyond builtins, I
have tried to split these into other files, which include
functional.scad.  As far as scope of additional functionality goes,
the sky is the limit.
I like to use this project as a showcase of some of the cool things
you can do when you have full access to the geometry.  I'm interested
in pushing limits of what can be accomplished in OpenSCAD, and showing
unique features that were otherwise not possible or too cumbersome.

The project can also be seen a testing ground for additional features
that, if proven useful, could be later implemented natively in
OpenSCAD.
For example I added an optional "r" (radius) parameter to the square
function.  My implementation concatenates four 90degree arcs, so no
extra boolean or hull or minkowski operations are required.  By itself
I don't think its particularly remarkable, but I also plan to add the
same radius parameter for cube which I do think is a big deal.
Currently there is no particularly efficient way to generate a rounded
cube and a pure functional method like this would be blazing fast (and
accurate) in comparison to existing methods.
Conceptually you would generate the vertices/faces for each octant of
a sphere(or just one octant and mirror it around), and then add quad
faces to connect the edges of those sphere corners.  I've done some
work towards this purely functional rounded cube implementation but it
is not finished yet.

Here is a quick implementation of the rounded cube concept which I
made as a module, since this version does still require one hull
operation.
https://gist.github.com/thehans/2c96601af4e5c8c2d232e50252dd37b1

Compare that to something like OpenSCAD's example006.scad, which is a
model of a six sided die.  The body of the die is a rounded cube, but
if you look closely the corners are a mess; the faces and edges of
spheres and cyllinders that make up the shape don't line up.
I'd love to see such a radius parameter added to the native cube
module, so an example such as this could be so much cleaner both in
the code and in the geometry it creates.

Yeah... I think I might look into finishing up that cube radius
parameter as one of my next tasks.

I agree that some form mesh validation would be pretty handy, but I'm
not well versed in relevant algorithms for that sort of thing.

I don't understand what you mean here.

Yeah the subdivision was written specifically for the
alternative_spheres, and could really use triangulation to be more
widely applicable.  I've heard of delaunay triangulation, for
example, but have never attempted to implement it myself.
Oh, is the 2-3 tree structure you made intended for use in
triangulation?  I skimmed briefly but I'm not famliiar with that data
structure or its applications.

Adding new transformations / deformations is something I'm
particularly interested in, like "wrapping" an object around a
cylinder or sphere (if that's what you mean).  Projective transform is
already possible using a 4x4 matrix though, right?

Fillets in particular I really like to include in most of my designs.
I usually end up building a 2d profile from arcs, then linear or
rotate extruding it.
double_fillet was my attempt to make slightly easier to generalize
some tricky cases of fillets, but I still wouldn't consider it
"automated" by any means; you have to build the fillets into your
model from the beginning.

The best sort of automated fillet approach I've seen would be a blend
function used by a SDF(signed distance function) based renderer, (like
Doug Moen is doing with Curv: https://github.com/doug-moen/curv ,
another exciting project) but SDF is a complete paradigm shift that I
don't think would be practical to attempt implementing in OpenSCAD.

-Hans

It's super simple.  I'll just write it up and submit it on github.

example, but have never attempted to implement it myself. ...

Delauney triangulation and voronoi diagrams are for things like finding
nearest neighbors.  Polygon triangulation involves different algorithms.  (
https://en.wikipedia.org/wiki/Polygon_triangulation )

I'll submit a simple stupid one on github.

It is possible with 4x4 matrices but not supported in OpenSCAD.

https://en.wikibooks.org/wiki/OpenSCAD_User_Manual/Transformations#multmatrix

"...the fourth row is used in 3D environments to define a view of the
object. it is not used in OpenSCAD and should be [0,0,0,1]..."

(I thought it was too, but realized it wasn't after suggesting it as an
improvement in the 'bend algorithm' that uses intersections and multmatrix.
https://github.com/openscad/openscad/issues/815 )

P.S.:

A 2-3 tree is a self-balancing tree.  It's a data structure for searchable
lists.

https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

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

thehans wrote

let me annote that hull() itself is not the problem. To avoid a time
consuming CGAL round trip, don't use (implicit) unions inside a hull(). If
you implement rounded_cube() more explicitely, rendering is fast (seconds).

$fa = 0.1;
$fs = 0.1;
rounded_cube_([4, 20, 5], r=1, center=[1,1,1]);

module rounded_cube_(size, r=0, center=false)
{
sz = size[0]==undef?[size, size, size]:size;
ce = center[0]==undef?[center, center, center]:center;
r_ = min(abs(r), abs(size.x/2), abs(size.y/2), abs(size.z/2));  // correct
r
translate([ce.x?-sz.x/2:0,ce.y?-sz.y/2:0, ce.z?-sz.z/2:0])
if(r)
hull()
{
translate([r_, r_, r_]) sphere(r_);
translate([r_, r_, sz.z-r_]) sphere(r_);
translate([r_, sz.y-r_, r_]) sphere(r_);
translate([r_, sz.y-r_, sz.z-r_]) sphere(r_);
translate([sz.x-r_, r_, r_]) sphere(r_);
translate([sz.x-r_, r_, sz.z-r_]) sphere(r_);
translate([sz.x-r_, sz.y-r_, r_]) sphere(r_);
translate([sz.x-r_, sz.y-r_, sz.z-r_]) sphere(r_);
}
else
cube(size);
}

in contrast the following call of hull will take minutes.

hull()
for(x=[r_,size.x-r_], y=[r_,size.y-r_], z=[r_,size.z-r_])
translate([x,y,z]) sphere(r_);

However, rounded_cube_ is currently a typical libary module. I wouldn't add
it to the core language unless cylinder(), linear_extrude() and maybe hull()
also get a r parameter.

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

Sorry to be clueless, but why is it faster to enumerate the explicit
locations of the spheres vs having them in a loop?

Jon

On 1/30/2018 10:42 AM, Parkinbot wrote:

--
Sent from my desktop computer.
I do not receive emails while away from my desk,
nor do I receive texts on my main phone number
(which is a land line).
If you know that I am on the road, please text me.
If you know that I am home, please email me.

On 1/30/2018 7:42 AM, Parkinbot wrote:

So you're saying it's better if the objects are simple and direct
children of the hull, rather than being a union (through whatever
mechanism) of those same objects?

JordanBrown wrote

Exactly. Have a look at the CSG structures. Results of a for loop are
represented as group node and processed as (implicit) union. And this needs
to be done by CGAL.

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

Thank you Parkinbot!

This is an excellent example of how a user new to OpenSCAD could spin
their wheels "needlessly".  I know nothing about the internals of
OpenSCAD.  I imagine that most C programmers do not wish to have to
understand the details of the parser or the code generator.  I hope that
we can eventually have a tool where two seemingly identical structures
take roughly the same time to calculate.  I imagine there are good (and
subtle) reasons why this objective is difficult to achieve

Jon

On 1/30/2018 11:41 AM, Parkinbot wrote:

--
Sent from my desktop computer.
I do not receive emails while away from my desk,
nor do I receive texts on my main phone number
(which is a land line).
If you know that I am on the road, please text me.
If you know that I am home, please email me.

Oh, wow.  I guess I had always assumed that hull was a CGAL operation.

You say this belongs in a library, but is there a single library that
has a properly implemented rounded cube?  Everyone's implementation is
different and 99.9% of them are slow and/or poduce ugly geometry.
This is why It should be standardized from the source.

I guess what I'm saying is at the very least MCAD should get updated
with an efficient module like you wrote here, because I think its
currently using what is more-or-less the same implementation as that
example006.scad I mentioned.
Also I should just say that my attention was originally drawn to
example006.scad a while ago when I was looking at improving OpenSCAD's
Travis build times, particularly in the execution time of individual
tests.  And example006.scad was one of the longest running tests.

Hans

On Tue, Jan 30, 2018 at 9:42 AM, Parkinbot rudolf@parkinbot.com wrote:

On 1/30/2018 8:41 AM, Parkinbot wrote:

Not knowing how hull( ) works, I wouldn't have expected there to be a
difference.

Good information, thanks.

I wonder if we could alleviate most of the slowdown of implicit union
by having group nodes do a simple bounding box check before passing to
CGAL, if no bounding boxes overlap then just skip it?

On Tue, Jan 30, 2018 at 10:49 AM, Jordan Brown
openscad@jordan.maileater.net wrote:

thehans wrote

Well I prefer libraries, which I write on my own, because they let me define
my own parameters and defaults and I can refer to the implementation. I
never understood why cube(), cylinder() and linear_extrude() are not
centered by default. And to be honest, I still don't know which prototypes
and defaults they exactly have. OK, this could be fixed by a proper
documentation ...

We have discussed it before several times that OpenSCAD is missing a
(standard) library concept. Have a look at the libraries folder shipped with
OpenSCAD and you will discover pretty old stuff that hasn't been maintained
for years.

See my implementation of a rounded_cylinder() and how it deals with
conflicts between diameters and radii. It is pretty fast, but I have no way
to figure out, whether it is semantically equivalent with cylinder,
therefore I can't call cylinder() with all its parameters in case r_ is 0.

$fa=.2;
$fs=.2;

CyR(r1=1, r2=6, h=7, r_=1.4, center = false);
//CyR(h=12, r_=1, r1=6, d2=1);

module CyR(r = 10, h=10, r_=1, d = undef, r1=undef, r2=undef, d1 = undef, d2
= undef, center=false)
{
r1 = r1==undef?d1==undef?d==undef?r:d/2:d1/2:r1;
r2 = r2==undef?d2==undef?d==undef?r:d/2:d2/2:r2;
r1_=min(abs(h/4), abs(r1), abs(r_));
r2_=min(abs(h/4), abs(r2), abs(r_));
echo(r1, r2, r1_, r2_);
h=abs(h);
translate([0,0,(center?-h/2:0)])
rotate_extrude()
intersection()
{
hull()
{
translate([r1-r1_, r1_]) circle(r1_);
translate([r2-r2_, h-r2_]) circle(r2_);
polygon([[0,0], [r1-r1_, r1_], [r2-r2_, h-r2_], [0,h]] );
}
square([max(r1,r2), h]);
}
}

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

thehans wrote

This issue has also been discussed many times, in the context of
multithreading and also in the context with a lazy_union() operator.

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

Parkinbot wrote

Sorry, here is my latest implementation:

$fa=.2;
$fs=.2;

module CyR(r = 10, h=10, r_=1, d = undef, r1=undef, r2=undef, d1 = undef, d2
= undef, center=false)
{
r1 = r1==undef?d1==undef?d==undef?r:d/2:d1/2:r1;
r2 = r2==undef?d2==undef?d==undef?r:d/2:d2/2:r2;
r_=min(abs(h/4), abs(r1), abs(r2), abs(r_));
h=abs(h);
translate([0,0,center?-h/2:0])
rotate_extrude()
intersection()
{
offset(r_)offset(-r_) polygon([[-2r_,0], [r1, 0], [r2, h], [0,h],
[-2r_,h]] );
square(max(r1,r2), h);
}
}

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

On 30. jan. 2018 17:49, Jordan Brown wrote:

The problem is not hull(), but implicit union. Hull only needs the
points in the input mesh(es). Applying [implicit] union() before
applying hull() to the result is like unknowingly driving with the hand
brake engaged. You perform a potentially costly computation (union())
only to immediately throw away the result.

One idea would be to provide an option to switch off implicit union, and
such issues will go away.

Carsten Arnholm

I would welcome a switch that turned off implicit union, if the result
was better performance.  I understand that I would need to alter my
source code, and that I might need to modify library source code.

Jon

On 1/30/2018 2:05 PM, Carsten Arnholm wrote:

--
Sent from my desktop computer.
I do not receive emails while away from my desk,
nor do I receive texts on my main phone number
(which is a land line).
If you know that I am on the road, please text me.
If you know that I am home, please email me.

By the way, here is a relevant issue that looks like had a lot of work
done towards it but never completely finalized.

Lazy union (aka. no implicit union):
https://github.com/openscad/openscad/issues/350

On Tue, Jan 30, 2018 at 1:25 PM, jon jon@jonbondy.com wrote:

Any insight in why the first hull() (the one with explicit union()) is
faster (16s*) than the second one (26s)?

(*) These times are with version 2018.01.06, Windows 10 x64, i5-4570S @
2.90GHz and 32 GB of RAM

size=30;
radius=1;
$fn=60;
// 16s if $fn=60
hull() {
union() translate([size/2, size/2]) {
translate([0, 0, -size/2]) sphere(radius);
translate([0, 0, size/2]) sphere(radius);
cylinder(radius, h=size, center=true);
}
rotate(90) union() translate([size/2, size/2]) {
translate([0, 0, -size/2]) sphere(radius);
translate([0, 0, size/2]) sphere(radius);
cylinder(radius, h=size, center=true);
}
rotate(180) union() translate([size/2, size/2]) {
translate([0, 0, -size/2]) sphere(radius);
translate([0, 0, size/2]) sphere(radius);
cylinder(radius, h=size, center=true);
}
rotate(270) union() translate([size/2, size/2]) {
translate([0, 0, -size/2]) sphere(radius);
translate([0, 0, size/2]) sphere(radius);
cylinder(radius, h=size, center=true);
}
}

// 26s if $fn=60
hull() {
translate([size/2, size/2]) {
translate([0, 0, -size/2]) sphere(radius);
translate([0, 0, size/2]) sphere(radius);
cylinder(radius, h=size, center=true);
}
rotate(90) translate([size/2, size/2]) {
translate([0, 0, -size/2]) sphere(radius);
translate([0, 0, size/2]) sphere(radius);
cylinder(radius, h=size, center=true);
}
rotate(180) translate([size/2, size/2]) {
translate([0, 0, -size/2]) sphere(radius);
translate([0, 0, size/2]) sphere(radius);
cylinder(radius, h=size, center=true);
}
rotate(270) translate([size/2, size/2]) {
translate([0, 0, -size/2]) sphere(radius);
translate([0, 0, size/2]) sphere(radius);
cylinder(radius, h=size, center=true);
}
}

(I know there are faster methods to do that, but they are a couple of
samples from an speed test I did some time ago and illustrate well my doubt)

2018-01-30 20:05 GMT+01:00 Carsten Arnholm arnholm@arnholm.org:

--
Saludos,
Antonio

On 30. jan. 2018 20:35, Antonio Bueno wrote:

Implicit or explicit union takes time. You are doing both in this case.

Why not simplify. Shorter, easier code. And faster.

size=30;
radius=1;
$fn=60;
hull() {
translate([-size/2, -size/2, -size/2]) sphere(radius);
translate([+size/2, -size/2, -size/2]) sphere(radius);
translate([+size/2, +size/2, -size/2]) sphere(radius);
translate([-size/2, +size/2, -size/2]) sphere(radius);

 translate([-size/2, -size/2, +size/2]) sphere(radius);
 translate([+size/2, -size/2, +size/2]) sphere(radius);
 translate([+size/2, +size/2, +size/2]) sphere(radius);
 translate([-size/2, +size/2, +size/2]) sphere(radius);

}

Carsten Arnholm

Its basically just easier for CGAL to handle a bunch of smaller unions
than one big one.

On Tue, Jan 30, 2018 at 2:07 PM, Carsten Arnholm arnholm@arnholm.org wrote:

than one big one.

If that's true, then can OpenSCAD get a performance improvement with divide
and conquer?

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

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 nate-openscadforum@pedantic.org 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 doug@moens.org 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 drifter.frank@gmail.com
wrote:

Where is library subdivision.scad found?

2018-02-08 0:33 GMT-02:00 NateTG nate-openscadforum@pedantic.org:

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 rcmpersiano@gmail.com:

On Thu, 8 Feb 2018 13:08:26 -0500
doug moen doug@moens.org wrote:

Try profiling it and you'll see the interpreter isn't a problem.

They would but that would be almost the same speed as it is now.

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

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 doug@moens.org wrote:

frankv wrote

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/

Alan Cox wrote

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/

On Thu, Feb 08, 2018 at 08:38:14PM +0000, Alan Cox wrote:

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 9 February 2018 at 09:47, nop head nop.head@gmail.com 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.

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 2018-02-09 16:11, doug moen wrote:

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

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/