Yes the PolySet grid snap bug should be fixed but it is hard. It is exactly
the same issue that STL files have. OpenSCAD needs a mesh fixer to make it
robust whenever vertex resolution is reduced. If it had one then it could
also fix broken STL imports and bad polyhedron data and stop this endless
list of why does my model not render.

On Tue, 26 May 2020 at 12:53, Michael Marx michael@marx.id.au wrote:

nop.head@gmail.com wrote:

Help me to understand that.  It seems that CGAL is not called for doing
minkowski. What library does the minkowski operations? What data structures
are used for that?

I am sure CGAL is used to do 3D Minkowski, that is why it is monumentally
slow.

I get

Total rendering time: 0 hours, 0 minutes, 9 seconds

Top level object is a 3D object:

Simple: yes

Vertices: 359

Halfedges: 1498

Edges: 749

Halffacets: 790

Facets: 395

Volumes: 3

Rendering finished.

NetFabb says there are 906 edges and 604 triangles in the STL. Presumably
that is because CGAL outputs polygons and they have to be broken into
triangles for STL.

[image: image.png]

On Tue, 26 May 2020 at 14:17, arnholm@arnholm.org wrote:

On 2020-05-26 14:42, Ronaldo Persiano wrote:

I believe OpenSCADs implementation of 3D Minkowski sums rely on CGAL
https://doc.cgal.org/latest/Minkowski_sum_3

Carsten Arnholm

For consistency please use add_rotate=7, it seems to be worse.

From: Discuss [mailto:discuss-bounces@lists.openscad.org] On Behalf Of nop head
Sent: Tue, 26 May 2020 23:28
To: OpenSCAD general discussion
Subject: Re: [OpenSCAD] rendering problem

I am sure CGAL is used to do 3D Minkowski, that is why it is monumentally slow.

I get

Total rendering time: 0 hours, 0 minutes, 9 seconds

Top level object is a 3D object:

Simple: yes

Vertices: 359

Halfedges: 1498

Edges: 749

Halffacets: 790

Facets: 395

Volumes: 3

Rendering finished.

NetFabb says there are 906 edges and 604 triangles in the STL. Presumably that is because CGAL
outputs polygons and they have to be broken into triangles for STL.

image.png

On Tue, 26 May 2020 at 14:17, arnholm@arnholm.org wrote:

On 2020-05-26 00:06, Ronaldo Persiano wrote:

Could be an intermittent problem, or behaviour depends on version of
OpenSCAD and/or operating system. It is not necessarily minkowski that
fails, since difference is the final operation.

I tried with OpenSCAD 2017.01.20 under Win10 and it shows no obvious
problems (but see below), it is reported as

Total rendering time: 0 hours, 0 minutes, 10 seconds
Top level object is a 3D object:
Simple:        yes
Vertices:      369
Halfedges:    1556
Edges:        778
Halffacets:    826
Facets:        413
Volumes:        3
Rendering finished.
STL export finished.

However, testing the exported STL in polyfix reveals a higher number of
faces (628) compared to what OpenSCAD reports (413), which is kind of
strange.

polyhedron 0 ================= volume=1469.81, dtol=0.01, atol=1e-06,
maxiter=10
iteration 0: vertices=1884 faces=628
warning: 4 zero area faces.
warning: nonmanifold edges: uc(1)=1884
merged 1574 vertices
removed 16 collapsed or zero area faces
removed 2 duplicate faces
removed 2 nonmanifold faces
total changes=1594
no warnings

iteration 1: vertices=310 faces=608
removed 2 unused vertices
total changes=2
no warnings

iteration 2: vertices=308 faces=608
total changes=0
no warnings

Summary:
polyhedron 0: vertices=308 faces=608 : no warnings

When instead exporting the same model from OpenSCAD to OFF format, it
showed an even higher number of faces (710):

polyhedron 0 ================= volume=1469.81, dtol=0.01, atol=1e-06,
maxiter=10
iteration 0: vertices=359 faces=710
warning: 86 zero area faces.
merged 49 vertices
removed 98 collapsed or zero area faces
removed 2 duplicate faces
removed 2 nonmanifold faces
total changes=151
no warnings

iteration 1: vertices=310 faces=608
removed 2 unused vertices
total changes=2
no warnings

iteration 2: vertices=308 faces=608
total changes=0
no warnings

Summary:
polyhedron 0: vertices=308 faces=608 : no warnings

As you can see, polyfix resolved both of the above to vertices=308
faces=608, even if the starting points were different. I think this
shows that at least part of the problems lie in file export code.

It does not make sense that the number of faces exported depends on the
file format chosen. Clearly, there is no check for zero area faces on
file export in OpenSCAD.

I also tried this, which seemed to work
https://gist.github.com/arnholm/de50168cd1a477be1de116e100a8066a

Carsten Arnholm

OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

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

That does produce a broken STL where the lines are on the sides.

[image: image.png]

I expect CGAL produces vertices that are very close together and they
collapse during export to STL.

On Tue, 26 May 2020 at 14:39, Michael Marx michael@marx.id.au wrote:

On 26.05.20 15:28, nop head wrote:

Yes, CGAL is quite involved, but not the actual
minkowski implementation.

OpenSCAD normally uses CGAL to (optionally)
deconstruct the object into convex parts and
generates a point cloud based on positioning the
second object on all vertices of the convex parts
and afterwards does a convex hull on those.

Afterwards the separate convex minkowski parts
are unioned together -> this is where the slowness
can come in big time depending on how much parts
were generated.

This can be observed in more detail via

openscad --debug=cgalutils-applyops

Pretty much worst case scenario as this very low
resolution object decomposes into 124 parts.

minkowski(){
difference() {
cube(20, center = true);
sphere(13, $fn = 16);
}
sphere(2);
}

Minkowski: child 0 is nonconvex Nef, decomposing...
Minkowski: decomposed into 124 convex parts
Minkowski: decomposition took 1.029088 s
Minkowski: child 1 is convex and PolySet
Minkowski: Point cloud creation (8 ⨉ 28 -> 224) took 1029.115000 ms
Minkowski: Computing convex hull took 0.000985 s
Minkowski: Point cloud creation (8 ⨉ 28 -> 224) took 0.015000 ms
Minkowski: Computing convex hull took 0.001173 s
[snip...]
Minkowski: Point cloud creation (6 ⨉ 28 -> 168) took 0.057000 ms
Minkowski: Computing convex hull took 0.001939 s
Minkowski: Computing union of 124 parts
Minkowski: Union done: 26.550561 s
Minkowski: Total execution time 28.331127 s

ciao,
Torsten.

Yes, CGAL is quite involved, but not the actual

This quite clarify my understanding. But how preview deals with minkowski?
I imagine that the flow above is pretty much the same except the union in
last step. Preview might just throw the convex parts to the z-buffer
avoiding the union. And this last process seems to be creating a flipped
face.

That is what I get after a fresh F6 followed by a F5:

[image: FlushF6F5.PNG]

and that is what comes out from a fresh F5:

[image: FlushF5.PNG]

and that last one with Throw Together:

[image: FlushF5TT.PNG]

So, it seems there is a bug in the F5 process of minkowski,

On 26.05.20 16:55, Ronaldo Persiano wrote:

Hmm, I don't think it's using different path, I believe it
actually does the full processing in preview already. But
that's a good point, in theory it should be possible to skip
the union part for preview.

ciao,
Torsten.

On 2020-05-26 15:55, Torsten Paul wrote:

Yes. This illustrates however that the only real problem is the slow
execution of boolean operations in CGAL, not the Minkowski subdivision
as such. The Minkowski subdivision into convex components seems like a
daunting and complicated task, but that is largely an illusion. The
convex subdivision problem is complicated only if you require to
optimize (=minimize) the number of convex components in Minkowski
subdivision on the assumption that booleans are slow.

If you have fast booleans it is possible to implement Minkowski sum
using a much simpler approach with many more, but much simpler convex
components. This is exactly what xcsg ( https://github.com/arnholm/xcsg
) does, and it is at least an order of magnitude faster because carve
booleans are intrinsically quite fast and because one can compute
booleans in multiple threads.

Carsten Arnholm