render() breaks CGAL compatibility

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

render() breaks CGAL compatibility

nophead
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 re-import 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
Reply | Threaded
Open this post in threaded view
|

Re: render() breaks CGAL compatibility

Ronaldo
I am intrigued with your experience. The following code builds a tetrahedron in a non-standard 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+1-i)/(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);
Reply | Threaded
Open this post in threaded view
|

Re: render() breaks CGAL compatibility

nophead
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_64-w64-mingw32.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 re-imported 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.




On 23 November 2016 at 16:09, Ronaldo <[hidden email]> wrote:
I am intrigued with your experience. The following code builds a tetrahedron
in a non-standard 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+1-i)/(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);





--
View this message in context: http://forum.openscad.org/render-breaks-CGAL-compatibility-tp19333p19339.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
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: render() breaks CGAL compatibility

MichaelAtOz
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!
Reply | Threaded
Open this post in threaded view
|

Re: render() breaks CGAL compatibility

wolf
In reply to this post by Ronaldo
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 run-away 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 built-in 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 close-to-zero 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

Reply | Threaded
Open this post in threaded view
|

Re: render() breaks CGAL compatibility

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

On 23 November 2016 at 22:16, wolf <[hidden email]> wrote:
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 run-away rounding
errors if they are close to parallel.
CGAL is written  explicitly
<http://www.win.tue.nl/~phachenb/Publications/dissertationHachenberger.pdfhttp://>
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 built-in 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 close-to-zero 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





--
View this message in context: http://forum.openscad.org/render-breaks-CGAL-compatibility-tp19333p19343.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
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: render() breaks CGAL compatibility

Alan Cox
In reply to this post by wolf
> 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 close-to-zero 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
Reply | Threaded
Open this post in threaded view
|

Re: render() breaks CGAL compatibility

wolf
In reply to this post by nophead
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 set-selection mark for each item, the map forms a two-dimensional Nef
polyhedron embedded on the sphere. We add a set-selection 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 built-in cut-off, undocumented, to break run-away recursions. If my memory serves me well, $r would be suitable also to handle this condition, and handle it in a user-transparent way.

At the end of the day, OpenSCAD's best feature is it is easy-to-learn and easy-to-use. 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
Reply | Threaded
Open this post in threaded view
|

Re: render() breaks CGAL compatibility

kintel
Administrator
In reply to this post by wolf
> 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
Reply | Threaded
Open this post in threaded view
|

Re: render() breaks CGAL compatibility

kintel
Administrator
In reply to this post by Ronaldo
> On Nov 23, 2016, at 11:09, Ronaldo <[hidden email]> wrote:
>
> I am intrigued with your experience. The following code builds a tetrahedron
> in a non-standard way. […] What kind of degenerated faces annoys
> CGAL?

We don’t always pass polyhedrons directly to CGAL. Whenever we can avoid it we don’t, partially due to the issue with degenerate faces. In your particular case, we deem the polyhedron to be convex, and pass it through a hull operation first, which is guaranteed to return a manifold mesh with no degenerate faces.

..but with concave meshes it’s more tricky. Here’s an example which currently fails to import:
https://github.com/openscad/openscad/blob/08154b19215254c5f60f17af3dd8fdd30d41462b/testdata/scad/bugs/issue945e.scad

 -Marius

PS! A trick to test this without doing a CSG with a unit cube: openscad file.scad -o out.png --render=cgal


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

Re: render() breaks CGAL compatibility

kintel
Administrator
In reply to this post by nophead

> 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
Reply | Threaded
Open this post in threaded view
|

Re: render() breaks CGAL compatibility

kintel
Administrator
In reply to this post by nophead
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
Reply | Threaded
Open this post in threaded view
|

Re: render() breaks CGAL compatibility

nophead
In reply to this post by kintel
>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.

On 24 November 2016 at 03:37, Marius Kintel <[hidden email]> wrote:

> 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


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

Re: render() breaks CGAL compatibility

Stefan Peter
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/2QRvS9xdNzw

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

me.vcf (150 bytes) Download Attachment