render() breaks CGAL compatibility
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.
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.
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 rcmpersiano@gmail.com 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
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Same error and cause, render() simplification, as my F5 before F6
http://forum.openscad.org/Hmm-CGAL-error-only-after-F5-F6-sequence-td18954.html
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 - 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/render-breaks-CGAL-compatibility-tp19333p19341.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
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.
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 wv99999@gmail.com 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
Discuss@lists.openscad.org
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 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
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
http://www.win.tue.nl/~phachenb/Publications/dissertationHachenberger.pdf
). 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
--
View this message in context: http://forum.openscad.org/render-breaks-CGAL-compatibility-tp19333p19346.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
On Nov 23, 2016, at 17:16, wolf wv99999@gmail.com 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
On Nov 23, 2016, at 11:09, Ronaldo rcmpersiano@gmail.com 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