not valid 2-manifold (union of two cubes)
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);
Compiling design (CSG Tree generation)...
Rendering Polygon Mesh using CGAL...
Geometries in cache: 41
Geometry cache size in bytes: 9400
CGAL Polyhedrons in cache: 3
CGAL cache size in bytes: 64632
Total rendering time: 0 hours, 0 minutes, 0 seconds
Top level object is a 3D object:
Simple: no
Vertices: 14
Halfedges: 46
Edges: 23
Halffacets: 24
Facets: 12
Volumes: 3
WARNING: Object may not be a valid 2-manifold and may need repair!
Rendering finished.
I don't truly understand the geometry involved, but I suspect that the
issue is that the touching face of the rotated cube is internally
described in the opposite direction of the touching face of the
unrotated cube, and that that gives CGAL indigestion.
It is simply because the built in version of rotate is not accurate for
right angles, etc, because it works in radians.
If you include this version it works:
module rotate(angle) // 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();
}
On 30 July 2017 at 16:44, Jordan Brown openscad@jordan.maileater.net
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);
Compiling design (CSG Tree generation)...
Rendering Polygon Mesh using CGAL...
Geometries in cache: 41
Geometry cache size in bytes: 9400
CGAL Polyhedrons in cache: 3
CGAL cache size in bytes: 64632
Total rendering time: 0 hours, 0 minutes, 0 seconds
Top level object is a 3D object:
Simple: no
Vertices: 14
Halfedges: 46
Edges: 23
Halffacets: 24
Facets: 12
Volumes: 3
WARNING: Object may not be a valid 2-manifold and may need repair!
Rendering finished.
I don't truly understand the geometry involved, but I suspect that the
issue is that the touching face of the rotated cube is internally described
in the opposite direction of the touching face of the unrotated cube, and
that that gives CGAL indigestion.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Cool, thanks! Yes, indeed.
(One wonders why the internal version doesn't work this way - or even
how it works, if not this way.)
On 7/30/2017 8:58 AM, nop head wrote:
It is simply because the built in version of rotate is not accurate
for right angles, etc, because it works in radians.
If you include this version it works:
module rotate(angle) // 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();
}
It uses the trigonometry functions from the standard C library which take
radians as parameters. To convert degrees to radians you need to multiply
by pi / 180 but that is a transcendental number, so can't be represented
exactly. The result of the rotation is then not quite 270 degrees, so the
cubes meet at an edge instead of a face.
The OpenSCAD trig functions have special case tests for 90 degrees, etc.
On 30 July 2017 at 17:17, Jordan Brown openscad@jordan.maileater.net
wrote:
Cool, thanks! Yes, indeed.
(One wonders why the internal version doesn't work this way - or even how
it works, if not this way.)
On 7/30/2017 8:58 AM, nop head wrote:
It is simply because the built in version of rotate is not accurate for
right angles, etc, because it works in radians.
If you include this version it works:
module rotate(angle) // 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();
}
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Yeah, that's basically correct. On Mac and Linux, 'sin(pi)' is
1.2246467991473532e-16, not 0. However, 'cos(pi)' is -1 exactly. It's a
problem with the sin/cos function implementations on those platforms: they
mess up when the result should be zero. It could also be fixed by using a
more accurate trig function library. There are a number of alternative
libraries that claim to be more accurate and faster; at this point my
problem is I don't know which one is best.
On 30 July 2017 at 13:28, nop head nop.head@gmail.com wrote:
It uses the trigonometry functions from the standard C library which take
radians as parameters. To convert degrees to radians you need to multiply
by pi / 180 but that is a transcendental number, so can't be represented
exactly. The result of the rotation is then not quite 270 degrees, so the
cubes meet at an edge instead of a face.
The OpenSCAD trig functions have special case tests for 90 degrees, etc.
On 30 July 2017 at 17:17, Jordan Brown openscad@jordan.maileater.net
wrote:
Cool, thanks! Yes, indeed.
(One wonders why the internal version doesn't work this way - or even how
it works, if not this way.)
On 7/30/2017 8:58 AM, nop head wrote:
It is simply because the built in version of rotate is not accurate for
right angles, etc, because it works in radians.
If you include this version it works:
module rotate(angle) // 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();
}
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
On 7/30/2017 11:03 AM, doug moen wrote:
Yeah, that's basically correct. On Mac and Linux, 'sin(pi)' is
1.2246467991473532e-16, not 0. However, 'cos(pi)' is -1 exactly. It's
a problem with the sin/cos function implementations on those
platforms: they mess up when the result should be zero. It could also
be fixed by using a more accurate trig function library. There are a
number of alternative libraries that claim to be more accurate and
faster; at this point my problem is I don't know which one is best.
Sorry, I should have said: this is OpenSCAD 2017.01.20 on Windows.
On Sun, Jul 30, 2017 at 02:03:23PM -0400, doug moen wrote:
Yeah, that's basically correct. On Mac and Linux, 'sin(pi)' is
1.2246467991473532e-16, not 0. However, 'cos(pi)' is -1 exactly.
Pi is equal to pi down to the 52nd bit after the most significant bit
in the representation.
Then taking the sine of that number is going to give you -1 times
the error in the accuracy in your representation of pi. Or about 10^-16.
So... knowing a little about the representation of floating point numbers
you should not expect to get zero when you take the sine of the floating
point representation of PI.
Formulated more mathematically,
sin (PI + epsilon) = -epsilon
with a floating point representation of PI there is always an eplsion.
I did
double p;
p = 4 * atan (1);
and got
3.141592653589793116
which underestimates pi by 1.22e-16, resulting in epsilon=-1.22e-16,
and the expected sine of that number to be 1.22e-16.
When you take the cosine of pi+epsilon, you should get 1-epsilon^2. So
even when there is epsilon of 2^-26 on your value of PI, the cosine
should come out to 1.000 accurate to about 2^-52, or rounded to 1.0
exactly.
In fact, both results are accurate to about 2^-52, Near "1" the floating
point representation has no way of specifying 1+epsilon where epsilon is
smaller than 2^-52. On the other hand, the floating point representation
DOES allow specifying epsilon in the 0+epsilon case.
It's a
problem with the sin/cos function implementations on those platforms:
So... no, it is not a problem with the implementation of these
functions on these platforms. It is a fundamental problem with floating
point representations of numbers.
Roger.
--
** R.E.Wolff@BitWizard.nl ** http://www.BitWizard.nl/ ** +31-15-2600998 **
** Delftechpark 26 2628 XH Delft, The Netherlands. KVK: 27239233 **
-- BitWizard writes Linux device drivers for any device you may have! --
The plan was simple, like my brother-in-law Phil. But unlike
Phil, this plan just might work.
http://kottke.org/16/03/how-many-digits-of-pi-does-nasa-use
you could argue that another solution might be a fixed point bcd
representation ...
but in any case using the local math routines is probably not a great
idea as it guarantees
nondeterministic behaviour between platforms
What would people think about the idea of picking a math library that
guarantees the
same behaviour regardless of platform... ?
On 31/07/17 08:38, Rogier Wolff wrote:
On Sun, Jul 30, 2017 at 02:03:23PM -0400, doug moen wrote:
Yeah, that's basically correct. On Mac and Linux, 'sin(pi)' is
1.2246467991473532e-16, not 0. However, 'cos(pi)' is -1 exactly.
Pi is equal to pi down to the 52nd bit after the most significant bit
in the representation.
Then taking the sine of that number is going to give you -1 times
the error in the accuracy in your representation of pi. Or about 10^-16.
So... knowing a little about the representation of floating point numbers
you should not expect to get zero when you take the sine of the floating
point representation of PI.
Formulated more mathematically,
sin (PI + epsilon) = -epsilon
with a floating point representation of PI there is always an eplsion.
I did
double p;
p = 4 * atan (1);
and got
3.141592653589793116
which underestimates pi by 1.22e-16, resulting in epsilon=-1.22e-16,
and the expected sine of that number to be 1.22e-16.
When you take the cosine of pi+epsilon, you should get 1-epsilon^2. So
even when there is epsilon of 2^-26 on your value of PI, the cosine
should come out to 1.000 accurate to about 2^-52, or rounded to 1.0
exactly.
In fact, both results are accurate to about 2^-52, Near "1" the floating
point representation has no way of specifying 1+epsilon where epsilon is
smaller than 2^-52. On the other hand, the floating point representation
DOES allow specifying epsilon in the 0+epsilon case.
It's a
problem with the sin/cos function implementations on those platforms:
So... no, it is not a problem with the implementation of these
functions on these platforms. It is a fundamental problem with floating
point representations of numbers.
Roger.
On 7/31/2017 6:50 AM, Mr C Camacho wrote:
you could argue that another solution might be a fixed point bcd
representation ...
That helps for numbers that are terminating fractions in decimal. It -
or decimal floating point - is great for accounting, where you need to
be able to represent $0.01 precisely.
It does not help for numbers that are infinitely repeating fractions in
decimal - 1/3, for instance. A decimal representation cannot precisely
represent 1/3; its value is 0.333... and repeats forever. This is the
reason that $0.01 cannot be represented precisely in binary floating
point; its value in binary is
0.00000010100011110101110000101000111101011100001010001111011...
It also, and relevant here, does not help for irrational numbers like
pi. There is no precise representation of pi in any conventional base.
(I suppose it's precisely representable in base pi, but few people work
in base pi. :-)
does 1/3 +/- 0.0000000000000004 really matter ?
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...
On 31/07/17 15:41, Jordan Brown wrote:
On 7/31/2017 6:50 AM, Mr C Camacho wrote:
you could argue that another solution might be a fixed point bcd
representation ...
That helps for numbers that are terminating fractions in decimal. It -
or decimal floating point - is great for accounting, where you need to
be able to represent $0.01 precisely.
It does not help for numbers that are infinitely repeating fractions
in decimal - 1/3, for instance. A decimal representation cannot
precisely represent 1/3; its value is 0.333... and repeats forever.
This is the reason that $0.01 cannot be represented precisely in
binary floating point; its value in binary is
0.00000010100011110101110000101000111101011100001010001111011...
It also, and relevant here, does not help for irrational numbers like
pi. There is no precise representation of pi in any conventional
base. (I suppose it's precisely representable in base pi, but few
people work in base pi. :-)
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org