not valid 2-manifold (union of two cubes)
On 7/31/2017 7:59 AM, Mr C Camacho wrote:
does 1/3 +/- 0.0000000000000004 really matter ?
It does if you care whether 1/3 * 3 is equal to 1. That was the root of
my original problem, that two faces that should have been parallel and
identical weren't, because of a tiny error in the trig calculations.
but yes to be honest BCD was in actuality an entirely specious attempt
at humour...
but my actual point still stands using a common set of robust math
routines rather than local C routines can only improve things
hopefully it would include a common metric internally for orientation...
Yes.
On 30. juli 2017 17:44, Jordan Brown wrote:
Here's a pretty simple example that yields the not-valid-2-manifold
warning, that I don't see mentioned elsewhere:
translate([1, -1, 0]) cube(1);
rotate([0, 0, 270]) cube(1);
I tried the same using https://github.com/arnholm/xcsg
ref. attached file, generated from AngelCAD as follows:
shape@ main_shape()
{
return translate(1,-1,0)*cube(1)
+ rotate_z(deg:270)*cube(1);
}
There is no problem in the manifoldness of the result in this case. The
sines and cosines of the rotate transformation are computed using
ordinary C++ functions, the results are as expected for cosine:
1.8369701987210297e-16
The fact that there is finite numerical precision does not imply that
such things should fail. It depends on the implementation of the boolean
operations library, in this case Carve
https://github.com/arnholm/abmesh-carve
So the original problem in OpenSCAD is probably an artifact of the
boolean operation (CGAL) in my opinion and not really a problem with
calculation of sines and cosines.
Carsten Arnhom
rew wrote
When you take the cosine of pi+epsilon, you should get 1-epsilon^2.
That is, of course, wrong. The formula Rogier relies upon is sin^2+cos^=1,
and thus he should have written "... you should get sqrt(1-epsilon^2),
which, for small values of epsilon, may be approximated by 1-epsilon". And
from here rounding produces the same effect as Rogier has given: if
sin(Angle) has a one binary digit rounding error, cos(Angle) will not have
it, and vice versa, because of sin^2+cos^=1.
So the whole issue is about rounding, and rounding properly. If your CPU (at
least any X86-CPU behaves that way) makes a rounding error, it sets the
"Inexact" flag, and gcc can access it, if so desired.
But there is no need for it. A chain of conditionals like
(Angle % 360)==90 ? 1.0 : sin(Angle*pi/180);
will nicely take care of it - and I assume here that the sine function
accepts radians, not degrees.
No need to search for a library, only a need for someone who understands
OpenSCAD's source well enough to do it, and do it in the right place.
wolf
--
View this message in context: http://forum.openscad.org/not-valid-2-manifold-union-of-two-cubes-tp21953p21973.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
Hi Carsten,
As Marius Kintel explained to me some time ago quote"We print this warning
(i.e. non-valid manifold, [wolf]) if CGAL’s Nef_polyhedron_3 is not simple"
unquote. Thus, since you do not use CGAL for your boolean operations, you
are not expected to get the warning either.
And since it is a CGAL warning, the underlying rounding error must have been
made before the two cubes were presented to CGAL for the implicit union of
the two cubes. Since CGAL is designed to be free of rounding errors, it
cannot accept floating point numbers. Instead, it requires conversion to the
CMPQ format, which is in effect a struct containing integers (a dividend and
a divisor) which together may be described as a rational number - but not as
a real number, if you are familiar with the distinction.
You may blame CGAL for flagging the warning, and Marius Kintel for hiding
its origin, but you cannot blame CGAL for causing it. But you do may blame
typecasting to CMPQ for it, as that would be the step where rounding errors
would have been irreversibly cast in stone.
You may also take a look at the .stl file. If there were no rounding errors,
the .stl file would only contain 0,+1 and -1 values. None of the 0.999999
values would have been present. And, if I read your cube.xcsg aright, that
is exactly the same you would report if you had done the .stl file.
As further food for thought, I will give you my variant of issue1258.scad,
which started me on the journey battling degenerate triangles. You have done
quite some work on that yourself, so you may appreciate the many facets
rounding errors can show. And, please remember that the final test for any
variant of issue1258.scad is: How does the .stl fare when subjected to a
boolean operation? Observe how the mesh changes, and that only Final() does
produce the proper mesh. All the others are messed up somehow, but only
Original() is messed up fatally.
wolf
// source for Original:
https://github.com/openscad/openscad/blob/master/testdata/scad/3D/issues/issue1258.scad
module Original()
{difference() {
translate([-6, 4, 30]) cube(size = [17.5, 48, 60], center = true);
translate([-10.5, 3, 30]) cube(size = [20.5, 55, 80], center = true);
}
translate([-.25, -19, 33])
rotate([0, 90, 0])
rotate([0, 0, -45])
cube(size = [15, 15, 3], center = false);}
module Moved()
{difference() {
translate([-4, 4, 30]) cube(size = [17.5, 48, 60], center = true);
translate([-8.5, 3, 30]) cube(size = [20.5, 55, 80], center = true);
}
translate([1.75, -19, 33])
rotate([0, 90, 0])
rotate([0, 0, -45])
cube(size = [15, 15, 3], center = false);}
module Rotate(angle) // Nophead: built-in rotate is inaccurate
for 90 degrees, etc
{
a = len(angle) == undef ? [0, 0, angle] : angle;
cx = cos(a[0]);
cy = cos(a[1]);
cz = cos(a[2]);
sx = sin(a[0]);
sy = sin(a[1]);
sz = sin(a[2]);
multmatrix([
[ cy * cz, cz * sx * sy - cx * sz, cx * cz * sy + sx * sz, 0],
[ cy * sz, cx * cz + sx * sy * sz,-cz * sx + cx * sy * sz, 0],
[-sy, cy * sx, cx * cy, 0],
[ 0, 0, 0, 1]
]) children();
}
module Nophead()
{ difference() {
translate([1.25, 4, 30]) cube(size = [3, 48, 60], center = true);
translate([-10.5, 3, 30]) cube(size = [20.5, 55, 80], center = true);
}
translate([-0.25, -19, 33]) Rotate([0, 90, 0]) rotate([0, 0, -45])
cube(size = [15, 15, 3], center = false); }
module NoRotate90Degree()
{difference() {
translate([-6, 4, 30]) cube(size = [17.5, 48, 60], center = true);
translate([-10.5, 3, 30]) cube(size = [20.5, 55, 80], center = true);
}
translate([-.25, -19, 12]) rotate([45, 0, 0]) cube(size = [3, 15, 15],
center = false);}
module Final()
{translate([1.25, 4, 30]) cube(size = [3, 48, 60], center = true);
translate([-0.25, -19, 12]) rotate([45,0, 0]) cube(size = [3, 15, 15],
center = false); }
// test: export shape as .stl, re-import .stl into OpenSCAD, do this
difference() with it:
/* difference() {
.stl
translate([-10,0,10]) cube([30,10,10]);} */
Original(); // fails
//Moved(); // pass
//Nophead(); // pass
//NoRotate90Degree(); // pass
//Final(); // pass
--
View this message in context: http://forum.openscad.org/not-valid-2-manifold-union-of-two-cubes-tp21953p21978.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
On 2017-08-01 06:13, wolf wrote:
Hi Carsten,
As Marius Kintel explained to me some time ago quote"We print this
warning
(i.e. non-valid manifold, [wolf]) if CGAL’s Nef_polyhedron_3 is not
simple"
unquote. Thus, since you do not use CGAL for your boolean operations,
you
are not expected to get the warning either.
Hi wolf,
I think you misunderstand me. I am not concerned about warnings issued
by CGAL, on the contrary it is very important to warn about any topology
problem, and that is what OpenSCAD is doing. The warning from CGAL about
non-valid 2-manifold is a warning about topology, which is central to
any implementation of mesh based boolean operation libraries. Obviously
I am not getting the same warning since I am not using CGAL, that is
self evident. See below though.
What OpenSCAD via CGAL is saying, is that sometimes valid modelling
sequences result in invalid topology. That would be a concern if the
problem was common. It is being claimed in this thread that such
problems are due to the finite precision of numbers in a computer and
specifically it is claimed that implementations of radian based
trigonometric functions are to be blamed.
What I am saying is that I don't quite agree with such logic. The
original example in this thread applied to xcsg was to show that using a
library other than CGAL did not have topology issues in the result. I
believe it is not the finite precision of numbers or the trigonometric
functions that cause such issues in OpenSCAD/CGAL, because the same
radian based trigonometric functions are being used in xcsg, also with
finite precision. The difference is how booleans are implemented in
those libraries. Note I am not saying one library perfect and the other
is not, I am just saying they behave differently and experience
different problems for problems that are sometimes inherently ambiguous.
The reason why I started looking for an alternative to CGAL was that I
didn't quite believe in the idea in CGAL that you can somehow employ
quasi infinite precision ("fractional numbers") and solve all tolerance
problems that way. In reality it does not always work any better than a
more straightforward approach, and it comes with a very significant
price in degraded performance that I find unacceptable.
So I am not blaming CGAL for flagging the warning, but rather I think
the example shows that the approach with fractional numbers in reality
is not neccessarly significantly more reliable than a more straight
forward approach as employed in Carve (ordinary 64 bit double precision
numbers). At least one has to consider if the benefits are worth the
penalties in performance.
In xcsg, the final model is also checked for valid topology and in this
case no problems were found, which means it created a valid 2-manifold
topology. This should not be confused with the STL file representation,
because an STL files does not include any topology at all. An STL file
is a "polygon soup", i.e. lots of completely independent, detached
triangles. It is up to an application reading the STL to guess at what
the original topology might have been. So I would keep STL out of a test
like this. To investigate the actual topology created one could use AMF
or other formats with explicit topology. Almost every mesh file format
ever created has explicit topology, but not STL.
You can use STL as input for booleans in OpenSCAD, but the problem with
that approach is that you sometimes experience topology interpretation
problems as discussed above, or even hide topology problems that were
there in the first place (i.e. as showed by the original warning
OpeSCAD/CGAL issued). Because I have worked with interpretation of STL
files, I don't support direct import of STL in my AngelCAD software, but
require a format with explicit topology, e.g. AMF. When someone gives me
an STL, I run it through a separate program to interpret/guess at the
topology (several parameters can be tweaked in that process, giving
different results) and store the accepted result as AMF, which may then
be used in AngelCAD in further booleans.
Thanks for the issue1258.scad example with your extensions, I will see
what I can make of it. If I find something of interest I will report
back.
Carsten Arnholm
Hi Carsten,
cacb wrote
So I am not blaming CGAL for flagging the warning, but rather I think
the example shows that the approach with fractional numbers in reality
is not neccessarly significantly more reliable than a more straight
forward approach as employed in Carve (ordinary 64 bit double precision
numbers). At least one has to consider if the benefits are worth the
penalties in performance.
I couldn't agree more with you, but CGAL bashing is part of the OpenSCAD
forum, and no action is ever taken to address perceived problems. In my
view, the real cause for that warning are rounding errors arising from data
type conversions, "typecasting". Converting angles from degree to radians,
needed if you do rotations (the 90degree vs pi/2 rounding issue with trig
functions), are just one of them. Converting from long double (as x86
hardware uses exclusively for floating point operations) to double, to
float, or eventually, to a decimal format as used in the .stl's are other,
and they all introduce rounding errors. Other rounding errors still may be
arising from different sources, but all of them are cast into stone by the
typecasting necessary if you want to do booleans using CGAL. I am sure
Marius Kintel would welcome you with open arms if you were to send him a
patch replacing CGAL with Carve in OpenSCAD, if only to replace CGAL's
[quote]"finicky"[unquote]ness with somewhat more robust behavior. Other
improvements such as extra speed, and, I guess, a slew of solved issues
currently not even recognized as originating from CGAL, would be welcome,
too.
Converting to decimal, as needed for .stl's, are another source of rounding
errors, simply because they do not give the number of decimal places needed
to reproduce floats (6-8 places) accurately, and even more so doubles (16
places) or the long doubles (18-20 places) that x-86 hardware uses
internally. Once you have worked through the extended version of
issue1258.scad, created all the .stl's and viewed the different meshes, you
will be closer to my interpretation that meshes afford an excellent view of
the rounding errors that have been made prior to sending the data to
OpenSCAD's tesselator, and even that, given some effort, these rounding
errors can be re-constructed from the mesh.
I have no experience with amf files. Reading the Wikipedia entry on amf, the
amf file is roughly the same as the stl file, adding information like color,
texture and material, and taking action to shrink the file size, e.g. with
the option of having curve-edged facets. Even more so, to emphasize that amf
sees itself as an upgrade of stl, the domain stl2.org leads directly to the
amf website. But that's it, no mention of the word topology, and no mention
of anything that reminds me of the mathematician's definition of topology.
So I do not know what you refer to with "topology" or "topology problems".
If you mean with "topology" that faces/facets are listed in amf format by
index numbers into the vertex list rather than explicitly by their vertex
coordinates, to me that is part of shrinking the file size. But it also has
the effect of avoiding holes or self-intersections originating from rounding
errors of vertex coordinates. And that, such is my current understanding, is
what computer graphics practitioners might call "topology". I would rather
have them be more specific, discard the word "topology" and state exactly
what is meant, so that the place where problems arise is not hidden by the
choice of words used to flag them.
wolf
--
View this message in context: http://forum.openscad.org/not-valid-2-manifold-union-of-two-cubes-tp21953p21989.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
On 01. aug. 2017 10:16, arnholm@arnholm.org wrote:
Thanks for the issue1258.scad example with your extensions, I will see
what I can make of it. If I find something of interest I will report back.
Hi Wolf,
I tried OpenSCAD 2016.10.04 on Windows using the original model you
referred to:
https://github.com/openscad/openscad/blob/master/testdata/scad/3D/issues/issue1258.scad
I could not observe any problems with it, no errors or warnings
reported, the STL produced seems fine. I also checked it with my
abm_polyfix program and converted it to AMF, and there were no problems
observed.
To experiment, I translated the code into AngelCAD code and ran it under
Linux Kubuntu 17.04
shape@ main_shape()
{
return
translate(-6, 4, 30)*cuboid(17.5, 48, 60, center:true)
- translate(-10.5, 3, 30)*cuboid(20.5, 55, 80, center:true)
+ translate(-0.25, -19, 33)
*rotate_y(90)
*rotate_z(-45)
*cuboid(15, 15, 3,center:false);
}
Again, no problems. It creates a different mesh, but otherwise
equivalent OpenSCAD (The angelcad code translates into the attached file
that can be processed with xcsg, binaries at
https://github.com/arnholm/xcsg/releases )
I tried subtracting one from the other, using OpenSCAD 2015.03-2 on
Linux (forgot to run the nightly):
difference() {
import("xcsg/issue_1258_openscad.stl");
import("xcsg/issue1258.stl");
}
The result was as expected, empty. No warnings. For completeness, I
tried the same with angelcad after converting the OpenSCAD to AMF
shape@ main_shape()
{
return polyhedron("xcsg/issue_1258_openscad.amf")
- polyhedron("xcsg/issue1258.amf");
}
Again, same correct result, empty. Bare in mind the two files had
different mesh.
All in all I find no problems relating to rounding or anything else in
this case.
carsten Arnholm
Hi Wolf,
On 02. aug. 2017 12:15, wolf wrote:
In my
view, the real cause for that warning are rounding errors arising from data
type conversions, "typecasting". Converting angles from degree to radians,
needed if you do rotations (the 90degree vs pi/2 rounding issue with trig
functions), are just one of them.
As I have mentioned before, I believe there is no way around handling
tolerances properly. I don't think you will be able to solve such issues
by tweaking trigonometric functions. On the contrary, I think it can
cause more problems.
I am sure
Marius Kintel would welcome you with open arms if you were to send him a
patch replacing CGAL with Carve in OpenSCAD,
Anyone who wants to give that a try is free to do so. The version of
Carve I am using is at https://github.com/arnholm/abmesh-carve
For sample use, see e.g. https://github.com/arnholm/xcsg
However, one would have to either remove or re-implement special
functions in OpenSCAD like minkowski to make it complete.
Other
improvements such as extra speed, and, I guess, a slew of solved issues
currently not even recognized as originating from CGAL, would be welcome,
too.
The best I can offer is xcsg as an alternative for such cases, it is
already there.
Converting to decimal, as needed for .stl's, are another source of rounding
errors,
This is a slight misunderstanding. STL files are usually binary these
days, there is no conversion to decimals for binary STLs. Coordinates
are stored as 32 bit little endian IEEE floating point values. Some
rounding can happen if the application computes using higher precision,
like 64 bit. But this does not relate to decimal conversion.
For ASCII STL it is a different matter, the values are formatted as
decimal, but this STL format is less frequently used. Then it is up to
the application to format the numbers with high enough precision, xcsg
uses 16 significant digits in this case, so there is no automatic
precision loss even in this case.
I have no experience with amf files. Reading the Wikipedia entry on amf, the
amf file is roughly the same as the stl file, adding information like color,
texture and material, and taking action to shrink the file size, e.g. with
the option of having curve-edged facets.
Forget color, texture and curved facets here. The important difference
that remains is that the connectivity between the facets (i.e. the
topology) is explicitly stated. This is not so in STL.
Even more so, to emphasize that amf
sees itself as an upgrade of stl, the domain stl2.org leads directly to the
amf website. But that's it, no mention of the word topology, and no mention
of anything that reminds me of the mathematician's definition of topology.
So I do not know what you refer to with "topology" or "topology problems".
If you mean with "topology" that faces/facets are listed in amf format by
index numbers into the vertex list rather than explicitly by their vertex
coordinates, to me that is part of shrinking the file size.
That is topology yes, but the important aspect is not the reduction of
file size even though that is a good thing. The important thing is that
all information about how the mesh hangs together (or not) is preserved
explicitly. That is the topology. AMF as a file format is not important
or even ideal, there are many other formats that also preserve the
topology information, but STL doesn't.
But it also has
the effect of avoiding holes or self-intersections originating from rounding
errors of vertex coordinates.
Yes, then there is no need to interpret coordinates to understand how
the model hangs together (or not).
And that, such is my current understanding, is
what computer graphics practitioners might call "topology".
Topology is a basic term in CAD or mesh models. To simplify, geometry
defines coordinates, topology defines connectivity.
Carsten Arnholm
cacb wrote
I could not observe any problems with it, no errors or warnings
reported, the STL produced seems fine.
Did you run any boolean operation on the .stl? Creating the .stl, or
importing it, is not the problem. The problem only arises when you run a
boolean operation on the imported .stl. And the problem arises only with the
original script, not with any of my variants. And once you have built the
necessary experience in interpreting meshes, it is obvious why only the
original .stl is failing - three vertices on a single edge (the fourth one
is 0.000001 off the edge, not enough to be visible). In CGAL parlance, the
polygon is not simple! And most of the other variants contain vertices that
are not supposed to be there, meaning that the implicit union between the
two cubes "has failed partially".
"Has failed partially" I have put in quotes because I do not believe the
union has failed, rather, in my view, the six decimal precision used by
OpenSCAD - and OpenSCAD outputs .stl's as text files, not binary files -
obscures the the two cubes are not in the same plane by an amount less than
0.000001, but more than zero. In binary terms, only the 19 most significant
bits of the binary number have been used in writing the .stl.
wolf
--
View this message in context: http://forum.openscad.org/not-valid-2-manifold-union-of-two-cubes-tp21953p22009.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
OpenSCAD cannot import STL files where the vertices are very close
together. It merges them and corrupts the topology, so CGAL operations
don't work. It is a long standing bug.
On 3 August 2017 at 10:58, wolf wv99999@gmail.com wrote:
cacb wrote
I could not observe any problems with it, no errors or warnings
reported, the STL produced seems fine.
Did you run any boolean operation on the .stl? Creating the .stl, or
importing it, is not the problem. The problem only arises when you run a
boolean operation on the imported .stl. And the problem arises only with
the
original script, not with any of my variants. And once you have built the
necessary experience in interpreting meshes, it is obvious why only the
original .stl is failing - three vertices on a single edge (the fourth one
is 0.000001 off the edge, not enough to be visible). In CGAL parlance, the
polygon is not simple! And most of the other variants contain vertices that
are not supposed to be there, meaning that the implicit union between the
two cubes "has failed partially".
"Has failed partially" I have put in quotes because I do not believe the
union has failed, rather, in my view, the six decimal precision used by
OpenSCAD - and OpenSCAD outputs .stl's as text files, not binary files -
obscures the the two cubes are not in the same plane by an amount less than
0.000001, but more than zero. In binary terms, only the 19 most significant
bits of the binary number have been used in writing the .stl.
wolf
--
View this message in context: http://forum.openscad.org/not-
valid-2-manifold-union-of-two-cubes-tp21953p22009.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