not valid 2-manifold (union of two cubes)

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

not valid 2-manifold (union of two cubes)

JordanBrown

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
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: not valid 2-manifold (union of two cubes)

nophead
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 <[hidden email]> 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
[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: not valid 2-manifold (union of two cubes)

JordanBrown
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
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: not valid 2-manifold (union of two cubes)

nophead
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 <[hidden email]> 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
[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: not valid 2-manifold (union of two cubes)

doug.moen
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 <[hidden email]> 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 <[hidden email]> 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
[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



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

Re: not valid 2-manifold (union of two cubes)

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


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

Re: not valid 2-manifold (union of two cubes)

rew
In reply to this post by doug.moen
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.

--
** [hidden email] ** 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.

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

Re: not valid 2-manifold (union of two cubes)

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


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

Re: not valid 2-manifold (union of two cubes)

JordanBrown
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
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: not valid 2-manifold (union of two cubes)

codifies
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
[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: not valid 2-manifold (union of two cubes)

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


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

Re: not valid 2-manifold (union of two cubes)

cacb
In reply to this post by JordanBrown
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

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

cube.xcsg (790 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: not valid 2-manifold (union of two cubes)

wolf
In reply to this post by rew
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

Reply | Threaded
Open this post in threaded view
|

Re: not valid 2-manifold (union of two cubes)

wolf
In reply to this post by cacb
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




Reply | Threaded
Open this post in threaded view
|

Re: not valid 2-manifold (union of two cubes)

cacb
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


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

Re: not valid 2-manifold (union of two cubes)

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

Re: not valid 2-manifold (union of two cubes)

cacb
In reply to this post by cacb
On 01. aug. 2017 10:16, [hidden email] 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


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

issue1258.xcsg (1K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: not valid 2-manifold (union of two cubes)

cacb
In reply to this post by wolf
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

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

Re: not valid 2-manifold (union of two cubes)

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

Re: not valid 2-manifold (union of two cubes)

nophead
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 <[hidden email]> 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
[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
12