

While it is well known that OpenSCAD corrupts topology when it converts to STL and back I found wrapping a CGAL object in render() can also make it no longer acceptable to CGAL. It seems that when it converts to the simpler representation it loses resolution and so some points collapse.
I imported three very high resolution STL files and unioned them together. The result was still manifold and I could, for example, union it with a unit cube. If I wrapped it in render() then I could no longer union it with a unit cube, it gave the usual CGAL construction errors.
So if the STL truncation problem is ever fixed it needs to go into render() as well. Any reduction in numerical precision must be topologically aware, not just a simple truncation.
I fixed my problem by exporting the unioned object as an STL. That had lots of degenerate triangles due to truncation to float. I fixed them with Netfabb and can then reimport the STL and CGAL is happy with it.
The reason I had to do all this was that with three high resolution STLs the F5 pan and zoom performance was too slow. Unioning them together also took too long to do every time I load my project.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


I am intrigued with your experience. The following code builds a tetrahedron in a nonstandard way. When the variable degface is false, the render() fails because the face topology does not defines a manifold. When degface is true, two new faces are added correcting the face topology: they are degenerated but seem to appease CGAL. What kind of degenerated faces annoys CGAL? The code is a modification of one I have published in another thread.
// tetrahedron with a missing face
p = [ [0,0,0], [10,0,0], [0,10,0], [0,0,10] ];
f = [ [0,1,2], [0,3,1], [0,2,3] ];
// n additional faces composing the missing one
// but with new vertices
n=3;
ps = [for(i=[0:n+1]) p[1]*i/(n+1) + p[2]*(n+1i)/(n+1) ];
fs = [for(i=[1:n+1]) [ 3, 3+i, 4+i ] ];
// two degenerated faces will be added when degface=true
degface = true;
df1 = [for(i=[n+2:1:1]) 3+i ];
df2 = [2,3,4];
// the full tetrahedron data
pts = concat(p,ps);
fcs = degface?
concat(f,fs,[df1, df2]):
concat(f,fs);
// boolean operated to check render()
render()
difference(){
polyhedron(pts,fcs);
cube(3,center=true);
translate([10,0,0]) cube(3,center=true);
}
echo(points=pts);
echo(faces=fcs);


The error I get is: ERROR: CGAL error in CGAL_Nef_polyhedron3(): CGAL ERROR: assertion violation! Expr: pe_prev>is_border()  !internal::Plane_constructor::get_plane(pe_prev>facet(),pe_prev>facet()>plane()).is_degenerate() File: /opt/mxe/usr/x86_64w64mingw32.static/include/CGAL/Nef_3/polyhedron_3_to_nef_3.h Line: 293
It is hard to say exactly what causes it because it is the union of three STL files that total around 16MB. If I export it to STL after the union the only thing NetFabb finds wrong is lots of degenerate faces. Cleaning those up makes a file that can be reimported and CGAL is happy with it. It can also be wrapped in render and CGAL is still happy.
So I suspect that render() creates degenerate faces just the same as STL export when it converts from CGAL's rational format to floats. The STL files are much higher resolution than they need to be, so I expect the vertices are very close together not degenerate. After being converted to CGAL's representation they are still valid but converting back to OpenSCAD's 3D representation must collapse some vertices.
OpenSCAD used to snap vertices to a grid. I am not sure if it still does that, but that would certainly break models with vertices closer than the grid.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

Administrator

Same error and cause, render() simplification, as my F5 before F6 problem.
While nobody reproduced it, I changed it by making the two CGAL'ed section have the same render() so the geometry was compatible, as mentioned in the last post.
I have felt that geometry since 2015.03 has had imperfections that the previous CGAL only versions didn't. Basically it is more finicky with close surfaces.
Admin  email* me if you need anything, or if I've done something stupid...
* 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.
The TPP is no simple “trade agreement.” Fight it! http://www.ourfairdeal.org/ time is running out!


I have come to realize that there are two kinds of people who write computer programs: PROGRAMMERS and CODERS. The distinction between the two groups is that coders can string libraries (written by others, of course) together, but cannot be bothered to make sure that the assumptions upon which these libraries are based do not conflict with each other.
If you want to do boolean operations on geometric objects, one step in the process is to calculate the coordinate of the point at which two lines intersect, or, if you want to, to calculate the equation of the line at which two planes intersect. To do so, you need to divide by the slope that one line/plane has relative to the other. This results, as you may readily perceive, in a division by zero if the two lines/planes are parallel (i.e. their difference in slopes is zero), and it results in runaway rounding errors if they are close to parallel.
CGAL is written explicitly to ensure that rounding errors do not exist. It does so by using Arbitrary Precision Arithmetic, which makes it inherently slow. How slow? I have picked up somewhere a rule of thumb: 1000 times slower than using a computer's builtin floating point arithmetic. That is the price you pay using CGAL: to ensure that any boolean operation will not fail because of internal rounding errors, your code gets slow.
There is no way around it. Period. Attempts to replace CGAL with a faster library are destined to fail, as any library capable of accurately handling divisions by numbers arbitrarily closetozero can do so only when using arbitrary precision arithmetic, i.e. being equally slow.
Because CGAL insists on "no rounding error", it represents numbers as ratios: it will not write 0.6666... when the exact value is 2/3 (two thirds) The STL file specification, on the other hand, insists on writing the same number as 0.6666, chopping off the ellipsis (...), and enforcing the presence of rounding errors. It represents point coordinates using finite accuracy, usually equivalent to what C/C++ calls a FLOAT, i.e. a 32 bit floating point number. Whether to use rounding up (0.6667) or rounding down (0.6666) is immaterial to STL, but not to the geometry it represents. The geometry will respond with "degenerated" faces, i.e. faces that have an area of zero.
The transition from CGAL to STL is the responsibility of the OpenSCAD development team, who have acted as coders would, handling the transition from arbitrary precision to floating point accuracy the way it is done. A competent programmer would have recognized that rules are required to handle this transition, rules that may be set by the OpenSCAD user.
Let me propose here such a rule. I am well aware that this rule is going to break backward compatibility. If you consider carefully what I have said above about how and why degenerate faces are created by OpenSCAD when transiting from CGAL to STL, you understand that backward compatibility needs to be broken so that trustworthy STL generation becomes possible: Deprecate $fn, a number effectively describing the number of faces used to approximate a cylinder, and replace it with $r, describing the minimum distance a point must have from its nearest neighbor to be considered to be unique and includable into a STL. As far as I know, CGAL does calculate this distance for each point, but OpenSCAD does not use it. A useful default value for $r would be 0.05>$r>0.01, which is about the resolution available from 3D printers.
The time frame for implementing this rule would be the same as for building OpenSCAD2.
wolf


Degenerate faces would not be a problem if OpenSCAD recognised it had created them in the conversion to float and removed them. Or if it tweaked vertices by minute amounts to ensure the topology was not broken. Probably easier said than done but other programs can do this, Netfabb for instance, so it isn't impossible. It's probably the biggest bug in OpenSCAD at the moment.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


> There is no way around it. Period. Attempts to replace CGAL with a faster
> library are destined to fail, as any library capable of accurately handling
> divisions by numbers arbitrarily closetozero can do so only when using
> arbitrary precision arithmetic, i.e. being equally slow.
There are also two kinds of people who work with 3D, mathematicians and
engineers 8)
Mathematicians insist the problem cannot be solved because there is no
arbitrary perfect generic solution, engineers don't care because it's
possible to be good enough.
There are numerous ways to approach the problem and most 3D printing
tools are wonderfully robust against crappy STL input because they were
written by engineers and tested by lots of really bad STL generated by
engineers.
CGAL is from the mathematics end so tends to implode when faced with
these cases.
There are also algorithms dealing with real world 3D that are robust in
their methods  intrinsic functions with marching cubes for example.
> The transition from CGAL to STL is the responsibility of the OpenSCAD
> development team, who have acted as coders would, handling the transition
> from arbitrary precision to floating point accuracy the way it is done. A
> competent programmer would have recognized that rules are required to handle
> this transition, rules that may be set by the OpenSCAD user.
This is an open source project  send patches to fix it. It's not anyone's
'responsibility' unless you've got some kind of paid contract with the
developers.
Import and export of floating point STL is a well understood problem
because as soon as STL was heavily used people realised it was broken by
design.
Good STL writers use point dictionaries and having identified any
pair of points that map to the same dictionary entry but differ either
does removals or just jiggles the values to be the smallest ordered
distinct floating point difference apart (which in IEEE float is
thankfully really trivial). Readers do the reverse )assuming their
internal format may be ambiguous in some cases).
You can't deprecate $fn because it's used so much with small values to
make other shapes, but a precision value would be useful (indeed I've
long argued you could actually used 64bit fixed point for openscad given
time and people to do the work).
Alan
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


CGAL does contain a mechanism to recognize which point is neighbored to which point under the heading "Sphere Maps" (Chapter 3.1 in Peter Hachenbergers thesis). To quote:
"We represent the local pyramid of a vertex by conceptually intersecting the local
neighborhood of a vertex with an ε sphere. This intersection forms a subdivision of
the sphere (Figure 3.1) which we represent by a map. A map is a bidirected edge
paired graph, i.e., every edge e = (v, w) has a reversal edge e′ = (w, v), and there
exists a bijective mapping twin such that twin(e) = e′ and twin(e ′ ) = e. Together
with a setselection mark for each item, the map forms a twodimensional Nef
polyhedron embedded on the sphere. We add a setselection mark for the vertex
and call the resulting structure the sphere map of the vertex."
Once you know which vertex is neighbored by which, it is possible to calculate the distance vertices have from each other and to sort them by this distance. From there, delete all but one vertex whose distance is smaller than the minimum distance $r, (or merge them into a single vertex using a 'sum of least squares' method to move all of them by a minute amount, if you like that better).
The problem is that to do so, you need to define $r, and that breaks the viability of $fa, $fs and $fn. You might want to handle this by assigning priorities, but then you will get endless queries on this forum regarding "My code does not behave as expected" as we had it, and still have, along the line this forum sports messages on errors arising from listing faces for polyhedron().
I remember also kintel once writing here that there is a builtin cutoff, undocumented, to break runaway recursions. If my memory serves me well, $r would be suitable also to handle this condition, and handle it in a usertransparent way.
At the end of the day, OpenSCAD's best feature is it is easytolearn and easytouse. To maintain (and possibly to enhance) that should be more important than backward compatibility. Compatibility with legacy codes can always be handled by an appropriate error message (e.g.: $fn is deprecated, replace $fn=20 with $r=0.1).
wolf

Administrator

> On Nov 23, 2016, at 17:16, wolf < [hidden email]> wrote:
>
> Let me propose here such a rule. […]
> Deprecate $fn, a number effectively describing the number of faces used to
> approximate a cylinder, and replace it with $r, describing the minimum
> distance a point must have from its nearest neighbor to be considered to be
> unique and includable into a STL
Do you have an implementation in mind as well? As CGAL natively reads and writes OFF files, which has the same floating point challenges as STL, it should be easy to write a minimal proof of concept without dragging in any complexity from OpenSCAD.
> The time frame for implementing this rule would be the same as for building
> OpenSCAD2.
>
Not sure what you mean by that statement  that the expected time frame for a developer to implement your suggestion is a large project?
Marius
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

Administrator

> On Nov 23, 2016, at 17:38, nop head < [hidden email]> wrote:
>
> Degenerate faces would not be a problem if OpenSCAD recognised it had created them in the conversion to float and removed them. Or if it tweaked vertices by minute amounts to ensure the topology was not broken. Probably easier said than done but other programs can do this, Netfabb for instance, so it isn't impossible. It's probably the biggest bug in OpenSCAD at the moment.
>
This is not trivial, but I’m working smth. which may yield a “80% solution”, see https://github.com/openscad/openscad/issues/1580(the issue title says import, but this can be applied to exports as well)
If anyone wants to help by submitting _minimal_ test cases, that would be appreciated :)
I wasn’t aware that Netfabb fixes this. Is there a freely available version of Netfabb which could be used to test this?
Marius
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

Administrator

On Nov 23, 2016, at 06:05, nop head < [hidden email]> wrote:
>
> I imported three very high resolution STL files and unioned them together. The result was still manifold and I could, for example, union it with a unit cube. If I wrapped it in render() then I could no longer union it with a unit cube, it gave the usual CGAL construction errors.
>
I’d be interested in a minimal example of such behavior.
By minimal I’m hoping for < 100 polygons per mesh.
I know that takes time  I’ve spend countless hours in Blender stitching together minimal examples for test cases, hours which could be better spent fixing bugs :/
Marius
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


> I wasn’t aware that Netfabb fixes this. Is there a freely available version of Netfabb which could be used to test this?
The free version of Netfabb I have can fix degenerate triangles and holes but I don't think it is still available now that Netfabb as been taken over by Autodesk.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


On 24.11.2016 10:55, nop head wrote:
>>I wasn’t aware that Netfabb fixes this. Is there a freely available
> version of Netfabb which could be used to test this?
>
> The free version of Netfabb I have can fix degenerate triangles and
> holes but I don't think it is still available now that Netfabb as been
> taken over by Autodesk.
It still is, although I do not know if intentionally or not.
Have a look at Thomas Sanladerers 'Guide: How to get the new, free
Autodesk "Netfabb Basic"!' at
https://youtu.be/2QRvS9xdNzwWarning: There only is a windows version, if it runs under wine is
unknown for now.
Regards
Stefan Peter

There is no system but GNU, and Linux is one of its kernels.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

