CGAL error if F5 before F6

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

CGAL error if F5 before F6

nophead
I am running into this error on F6 unless I flush the cache after the preview.

ERROR: CGAL error in CGAL_Nef_polyhedron3(): CGAL ERROR: assertion violation! Expr: e_below != SHalfedge_handle() File: /mxe/usr/x86_64-w64-mingw32.static.posix/include/CGAL/Nef_3/SNC_FM_decorator.h Line: 426


Anybody know what causes it? I have vague recollection of it being something to do with caching an inexact value during the preview.




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

Re: CGAL error if F5 before F6

MichaelAtOz
Administrator
Like  this
<http://forum.openscad.org/Hmm-CGAL-error-only-after-F5-F6-sequence-td18954i20.html>  
maybe?



-----
Admin - email* me if you need anything, or if I've done something stupid...

* click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work. Obviously inclusion of works of previous authors is not included in the above.

The TPP is no simple “trade agreement.”   Fight it! http://www.ourfairdeal.org/   time is running out!
--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Admin - email* me if you need anything,
or if I've done something stupid...
* click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work.
Obviously inclusion of works of previous authors is not included in the above.


The TPP is no simple “trade agreement.” Fight it! http://www.ourfairdeal.org/ time is running out!
Reply | Threaded
Open this post in threaded view
|

Re: CGAL error if F5 before F6

MichaelAtOz
Administrator
In reply to this post by nophead
i think the "we calculate and cache the transformed object by applying the
transformation ourselves (i.e. without CGAL). " may be at the root of
various corner cases.



-----
Admin - email* me if you need anything, or if I've done something stupid...

* click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work. Obviously inclusion of works of previous authors is not included in the above.

The TPP is no simple “trade agreement.”   Fight it! http://www.ourfairdeal.org/   time is running out!
--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Admin - email* me if you need anything,
or if I've done something stupid...
* click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work.
Obviously inclusion of works of previous authors is not included in the above.


The TPP is no simple “trade agreement.” Fight it! http://www.ourfairdeal.org/ time is running out!
Reply | Threaded
Open this post in threaded view
|

Re: CGAL error if F5 before F6

Marius Kintel
In reply to this post by nophead
Argh, yes, I think this is a bug triggered by an optimization trying to avoid using CGAL where not necessary.

 -Marius

> On Jan 2, 2019, at 13:17, nop head <[hidden email]> wrote:
>
> I am running into this error on F6 unless I flush the cache after the preview.
>
> ERROR: CGAL error in CGAL_Nef_polyhedron3(): CGAL ERROR: assertion violation! Expr: e_below != SHalfedge_handle() File: /mxe/usr/x86_64-w64-mingw32.static.posix/include/CGAL/Nef_3/SNC_FM_decorator.h Line: 426
>
> Anybody know what causes it? I have vague recollection of it being something to do with caching an inexact value during the preview.
>
>
> _______________________________________________
> 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: CGAL error if F5 before F6

nophead
I though that putting render() around it to force CGAL during F5 would fix the problem but it doesn't.

The problematic code is a stack of linear extrudes unioned together.

On Wed, 2 Jan 2019 at 21:20, Marius Kintel <[hidden email]> wrote:
Argh, yes, I think this is a bug triggered by an optimization trying to avoid using CGAL where not necessary.

 -Marius

> On Jan 2, 2019, at 13:17, nop head <[hidden email]> wrote:
>
> I am running into this error on F6 unless I flush the cache after the preview.
>
> ERROR: CGAL error in CGAL_Nef_polyhedron3(): CGAL ERROR: assertion violation! Expr: e_below != SHalfedge_handle() File: /mxe/usr/x86_64-w64-mingw32.static.posix/include/CGAL/Nef_3/SNC_FM_decorator.h Line: 426
>
> Anybody know what causes it? I have vague recollection of it being something to do with caching an inexact value during the preview.
>
>
> _______________________________________________
> 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: CGAL error if F5 before F6

nophead
The problem seems to be caused by very close edges in a stack of polygons with different numbers of vertices.Each polygon has its radius defined by r / cos(180 / fn) so that the flat sides line up. But of course they don't line up exactly when 180 / n is an angle that makes cos return an irrational. Making each one smaller by 1/128 so they never line up exactly AND adding a render() around the stack fixes it.

This is for generating hanging holes that print in mid air without support material.

image.png

I think something must snap the vertices and break the topology during F5 and that gets cached and breaks F6. I don't understand why render doesn't fix it though. It seems geometry generated by render() is different under F5 than it is with F6 but I thought render() was supposed to do the same as F6 for that sub tree. Perhaps that is something that could be fixed, so at least just render() is a work around. I think the underlying problems is using three number systems and not doing topologically aware conversions from one to another.

On Wed, 2 Jan 2019 at 23:35, nop head <[hidden email]> wrote:
I though that putting render() around it to force CGAL during F5 would fix the problem but it doesn't.

The problematic code is a stack of linear extrudes unioned together.

On Wed, 2 Jan 2019 at 21:20, Marius Kintel <[hidden email]> wrote:
Argh, yes, I think this is a bug triggered by an optimization trying to avoid using CGAL where not necessary.

 -Marius

> On Jan 2, 2019, at 13:17, nop head <[hidden email]> wrote:
>
> I am running into this error on F6 unless I flush the cache after the preview.
>
> ERROR: CGAL error in CGAL_Nef_polyhedron3(): CGAL ERROR: assertion violation! Expr: e_below != SHalfedge_handle() File: /mxe/usr/x86_64-w64-mingw32.static.posix/include/CGAL/Nef_3/SNC_FM_decorator.h Line: 426
>
> Anybody know what causes it? I have vague recollection of it being something to do with caching an inexact value during the preview.
>
>
> _______________________________________________
> 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: CGAL error if F5 before F6

nophead
Actually when I eliminated all the nearly coincident edges it don't need a render().

On Thu, 3 Jan 2019 at 08:53, nop head <[hidden email]> wrote:
The problem seems to be caused by very close edges in a stack of polygons with different numbers of vertices.Each polygon has its radius defined by r / cos(180 / fn) so that the flat sides line up. But of course they don't line up exactly when 180 / n is an angle that makes cos return an irrational. Making each one smaller by 1/128 so they never line up exactly AND adding a render() around the stack fixes it.

This is for generating hanging holes that print in mid air without support material.



I think something must snap the vertices and break the topology during F5 and that gets cached and breaks F6. I don't understand why render doesn't fix it though. It seems geometry generated by render() is different under F5 than it is with F6 but I thought render() was supposed to do the same as F6 for that sub tree. Perhaps that is something that could be fixed, so at least just render() is a work around. I think the underlying problems is using three number systems and not doing topologically aware conversions from one to another.

On Wed, 2 Jan 2019 at 23:35, nop head <[hidden email]> wrote:
I though that putting render() around it to force CGAL during F5 would fix the problem but it doesn't.

The problematic code is a stack of linear extrudes unioned together.

On Wed, 2 Jan 2019 at 21:20, Marius Kintel <[hidden email]> wrote:
Argh, yes, I think this is a bug triggered by an optimization trying to avoid using CGAL where not necessary.

 -Marius

> On Jan 2, 2019, at 13:17, nop head <[hidden email]> wrote:
>
> I am running into this error on F6 unless I flush the cache after the preview.
>
> ERROR: CGAL error in CGAL_Nef_polyhedron3(): CGAL ERROR: assertion violation! Expr: e_below != SHalfedge_handle() File: /mxe/usr/x86_64-w64-mingw32.static.posix/include/CGAL/Nef_3/SNC_FM_decorator.h Line: 426
>
> Anybody know what causes it? I have vague recollection of it being something to do with caching an inexact value during the preview.
>
>
> _______________________________________________
> 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: CGAL error if F5 before F6

nophead
Doing F6 before F5 isn't a workaround either because although it keeps CGAL happy the exported STLs are broken according to NetFabb, presumably due to truncating to floats. Basically all vertices, whether specified or generated need to be either exactly coincident or sufficiently difference that they remain different in all number representations, rational, double, float and fixed point and when snapped to the dreaded grid.

In fact, is the grid snapping the major problem with OpenSCAD? How can it be correct to simply snap vertices to a grid? If they start distinct they need to stay distinct. What problem is the grid trying to solve?



On Thu, 3 Jan 2019 at 11:20, nop head <[hidden email]> wrote:
Actually when I eliminated all the nearly coincident edges it don't need a render().

On Thu, 3 Jan 2019 at 08:53, nop head <[hidden email]> wrote:
The problem seems to be caused by very close edges in a stack of polygons with different numbers of vertices.Each polygon has its radius defined by r / cos(180 / fn) so that the flat sides line up. But of course they don't line up exactly when 180 / n is an angle that makes cos return an irrational. Making each one smaller by 1/128 so they never line up exactly AND adding a render() around the stack fixes it.

This is for generating hanging holes that print in mid air without support material.

image.png

I think something must snap the vertices and break the topology during F5 and that gets cached and breaks F6. I don't understand why render doesn't fix it though. It seems geometry generated by render() is different under F5 than it is with F6 but I thought render() was supposed to do the same as F6 for that sub tree. Perhaps that is something that could be fixed, so at least just render() is a work around. I think the underlying problems is using three number systems and not doing topologically aware conversions from one to another.

On Wed, 2 Jan 2019 at 23:35, nop head <[hidden email]> wrote:
I though that putting render() around it to force CGAL during F5 would fix the problem but it doesn't.

The problematic code is a stack of linear extrudes unioned together.

On Wed, 2 Jan 2019 at 21:20, Marius Kintel <[hidden email]> wrote:
Argh, yes, I think this is a bug triggered by an optimization trying to avoid using CGAL where not necessary.

 -Marius

> On Jan 2, 2019, at 13:17, nop head <[hidden email]> wrote:
>
> I am running into this error on F6 unless I flush the cache after the preview.
>
> ERROR: CGAL error in CGAL_Nef_polyhedron3(): CGAL ERROR: assertion violation! Expr: e_below != SHalfedge_handle() File: /mxe/usr/x86_64-w64-mingw32.static.posix/include/CGAL/Nef_3/SNC_FM_decorator.h Line: 426
>
> Anybody know what causes it? I have vague recollection of it being something to do with caching an inexact value during the preview.
>
>
> _______________________________________________
> 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: CGAL error if F5 before F6

ednisley
On 1/3/19 7:18 AM, nop head wrote:
> What problem is the grid trying to solve?

Probably one I stumbled over a while ago:

https://softsolder.com/2015/01/02/openscad-quantized-vertices/

The discussion & pull:

https://github.com/openscad/openscad/issues/1107

https://github.com/openscad/openscad/pull/1115

Perhaps the state of the slicer art has made quantization irrelevant,
but … this may not be a solve-able problem in OpenSCAD.

--
Ed
https://softsolder.com

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

Re: CGAL error if F5 before F6

nophead
The main issue as I see it is every time you quantise the vertices some formally distinct ones may merge and that breaks the topology. That happens when STL files are written because they use floats and every other vertex representation in OpenSCAD is higher resolution.

Quantizing the vertices on a grid courser than a float seems only to make that problem more likely, make it happen earlier and doesn't fix anything. What am I missing?

Basically it seems that users have to ensure their vertices are not closer than the grid or they will get CGAL errors or generate STL files with self intersections or degenerate triangles. This is very difficult because the 2D irrational vertices can never be made to match the 3D ones due to being represented in fixed point, versus doubles or CGAL rationals. So a linear extruded circle does match a cylinder exactly for odd numbers of vertices. So any CGS between them is likely to generate errors.

I think it could be fixed by making sure that whenever vertices get quantized they are checked to make sure ones that were separate are not given the same value. So if they quantize to the same value the one that is the least round number gets moved the minimum distance away. For example if we have (1, 0, 0) and (1.0000000000000001, y, z) then the second vertex becomes (1 + delta, y, z), where delta is the lsb of the floating point mantissa, or the grid spacing if we still need one. As long as they maintain the same numerical order and inequalities after quantization I think the topology might be preserved without further consideration.





On Thu, 3 Jan 2019 at 18:07, Ed Nisley <[hidden email]> wrote:
On 1/3/19 7:18 AM, nop head wrote:
> What problem is the grid trying to solve?

Probably one I stumbled over a while ago:

https://softsolder.com/2015/01/02/openscad-quantized-vertices/

The discussion & pull:

https://github.com/openscad/openscad/issues/1107

https://github.com/openscad/openscad/pull/1115

Perhaps the state of the slicer art has made quantization irrelevant,
but … this may not be a solve-able problem in OpenSCAD.

--
Ed
https://softsolder.com

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

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

Re: CGAL error if F5 before F6

nophead
So a linear extruded circle doesn't match a cylinder exactly for odd numbers of vertices

On Thu, 3 Jan 2019 at 19:59, nop head <[hidden email]> wrote:
The main issue as I see it is every time you quantise the vertices some formally distinct ones may merge and that breaks the topology. That happens when STL files are written because they use floats and every other vertex representation in OpenSCAD is higher resolution.

Quantizing the vertices on a grid courser than a float seems only to make that problem more likely, make it happen earlier and doesn't fix anything. What am I missing?

Basically it seems that users have to ensure their vertices are not closer than the grid or they will get CGAL errors or generate STL files with self intersections or degenerate triangles. This is very difficult because the 2D irrational vertices can never be made to match the 3D ones due to being represented in fixed point, versus doubles or CGAL rationals. So a linear extruded circle does match a cylinder exactly for odd numbers of vertices. So any CGS between them is likely to generate errors.

I think it could be fixed by making sure that whenever vertices get quantized they are checked to make sure ones that were separate are not given the same value. So if they quantize to the same value the one that is the least round number gets moved the minimum distance away. For example if we have (1, 0, 0) and (1.0000000000000001, y, z) then the second vertex becomes (1 + delta, y, z), where delta is the lsb of the floating point mantissa, or the grid spacing if we still need one. As long as they maintain the same numerical order and inequalities after quantization I think the topology might be preserved without further consideration.





On Thu, 3 Jan 2019 at 18:07, Ed Nisley <[hidden email]> wrote:
On 1/3/19 7:18 AM, nop head wrote:
> What problem is the grid trying to solve?

Probably one I stumbled over a while ago:

https://softsolder.com/2015/01/02/openscad-quantized-vertices/

The discussion & pull:

https://github.com/openscad/openscad/issues/1107

https://github.com/openscad/openscad/pull/1115

Perhaps the state of the slicer art has made quantization irrelevant,
but … this may not be a solve-able problem in OpenSCAD.

--
Ed
https://softsolder.com

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

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

Re: CGAL error if F5 before F6

MichaelAtOz
Administrator
But doesn't CGAL stitch them together.
When everything was done as Rationals (Quotient type??) we didn't have these
issues.
But to ran for a looong time.
Then things were done to improve performance...



-----
Admin - email* me if you need anything, or if I've done something stupid...

* click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work. Obviously inclusion of works of previous authors is not included in the above.

The TPP is no simple “trade agreement.”   Fight it! http://www.ourfairdeal.org/   time is running out!
--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Admin - email* me if you need anything,
or if I've done something stupid...
* click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work.
Obviously inclusion of works of previous authors is not included in the above.


The TPP is no simple “trade agreement.” Fight it! http://www.ourfairdeal.org/ time is running out!
Reply | Threaded
Open this post in threaded view
|

Re: CGAL error if F5 before F6

nophead
Yes CGAL works fine with very close edges because it has infinite resolution but you can't convert the results to STL floats without collapsing vertices. So export needs truncation that preserves topology and perhaps so does conversion to doubles for polysets.

Snapping to a grid would align some vertices that are slightly off and simplify the geometry but if it merges vertices again it needs to preserve topology. Once quantised by the grid it is less likely to collapse vertices with making an STL, although floats have variable resolution, so at large scales a gird step would not be representable.

I will put some logging code in the grid snap and see if this bug occurs only when vertices are merged as I suspect.

On Thu, 3 Jan 2019 at 23:33, MichaelAtOz <[hidden email]> wrote:
But doesn't CGAL stitch them together.
When everything was done as Rationals (Quotient type??) we didn't have these
issues.
But to ran for a looong time.
Then things were done to improve performance...



-----
Admin - email* me if you need anything, or if I've done something stupid...

* click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work. Obviously inclusion of works of previous authors is not included in the above.

The TPP is no simple “trade agreement.”   Fight it! http://www.ourfairdeal.org/   time is running out!
--
Sent from: http://forum.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: CGAL error if F5 before F6

Alan Cox-2
In reply to this post by nophead
On Thu, 3 Jan 2019 19:59:28 +0000
nop head <[hidden email]> wrote:

> The main issue as I see it is every time you quantise the vertices some
> formally distinct ones may merge and that breaks the topology. That happens
> when STL files are written because they use floats and every other vertex
> representation in OpenSCAD is higher resolution.

It's an OpenSCAD bug. A proper STL exporter uses a point dictionary and
if two differing points have the same dictionary entry then it minimally
tweaks the values in the dictionary to avoid the ambiguity.

> I think it could be fixed by making sure that whenever vertices get
> quantized they are checked to make sure ones that were separate are not
> given the same value. So if they quantize to the same value the one that is
> the least round number gets moved the minimum distance away. For example if
> we have (1, 0, 0) and (1.0000000000000001, y, z) then the second vertex
> becomes (1 + delta, y, z), where delta is the lsb of the floating point
> mantissa, or the grid spacing if we still need one. As long as they
> maintain the same numerical order and inequalities after quantization I
> think the topology might be preserved without further consideration.

Yes - providing in fixing one you don't break another.

Alan

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

Re: CGAL error if F5 before F6

MichaelAtOz
Administrator
Alan Cox-2 wrote
> It's an OpenSCAD bug. A proper STL exporter uses a point dictionary and
> if two differing points have the same dictionary entry then it minimally
> tweaks the values in the dictionary to avoid the ambiguity.

How can it tweak without analyzing the whole thing.
Just bumping a point in some random direction is just as likely to cause
problems.



-----
Admin - email* me if you need anything, or if I've done something stupid...

* click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work. Obviously inclusion of works of previous authors is not included in the above.

The TPP is no simple “trade agreement.”   Fight it! http://www.ourfairdeal.org/   time is running out!
--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Admin - email* me if you need anything,
or if I've done something stupid...
* click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work.
Obviously inclusion of works of previous authors is not included in the above.


The TPP is no simple “trade agreement.” Fight it! http://www.ourfairdeal.org/ time is running out!
Reply | Threaded
Open this post in threaded view
|

Re: CGAL error if F5 before F6

nophead
I don't think you would do it in a random direction. You need to maintain the same inequalities between the points. I can see that might cause a chain reaction if you have lots of very close points as each would need to move a bit further.

OpenSCAD's grid is a sort of point dictionary but it deliberately tries to merge close points even if they are one grid step away. How can that be right? Doesn't it always break the topology and create a CGAL exception if points get merged?

On Sat, 5 Jan 2019 at 03:09, MichaelAtOz <[hidden email]> wrote:
Alan Cox-2 wrote
> It's an OpenSCAD bug. A proper STL exporter uses a point dictionary and
> if two differing points have the same dictionary entry then it minimally
> tweaks the values in the dictionary to avoid the ambiguity.

How can it tweak without analyzing the whole thing.
Just bumping a point in some random direction is just as likely to cause
problems.



-----
Admin - email* me if you need anything, or if I've done something stupid...

* click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work. Obviously inclusion of works of previous authors is not included in the above.

The TPP is no simple “trade agreement.”   Fight it! http://www.ourfairdeal.org/   time is running out!
--
Sent from: http://forum.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: CGAL error if F5 before F6

nophead
I added some test code to grid.h to save the original value and then print if it merged a different vertex to the same entry.

        if (iter == db.end()) { // Not found: insert using key
            data = db.size();
            db[key] = data;
            values[key] = v;
        }
        else {
            // If found return existing data
            key = iter->first;
            data = iter->second;
            auto u = values[key];
            if(v != u)
                PRINTB("Collapsed (%f,%f,%f) to (%f,%f,%f)", v[0] % v[1] % v[2] % u[0] % u[1] % u[2]);
        }

With my F5 / F6 bug it only prints "Collapsed" when I get the CGAL error. I.e. for F5 before F6 but not for F6 first. So I think this shows that collapsing vertices with a grid is a bug.

This is a distilled down version of my code that gives the bug. There is probably some scope for simplifying it further.

eps = 1/128;
layer_height = 0.25;

module hanging_hole(z, ir, h = 100, h2 = 100) {
    infill_angle =  45;
    render(convexity = 3) translate([0, 0, z]) {
        rotate(infill_angle)
                intersection() {
                    rotate(-infill_angle)
                        linear_extrude(height = 3 * layer_height, center = true)
                                //offset(-eps)
                            children();

                    cube([100, 2 * ir, 2 * layer_height], center = true);
                }
        below = min(z + eps, h2);
        translate([0, 0, -below])
            linear_extrude(height = below)
                children();
    }
}

$fn = 11;
cube();
render()
    translate([20, 10])
        difference() {
            cylinder(d = 15, h = 5);
           
            hanging_hole(z = 2, ir = 2.5)
                circle(r = 5 / cos(180 / $fn));
           
        }

Adding the commented out offset(-eps) moves the vertices apart so they no longer get merged during F5 and the bug goes away. But that forces grid.h to not merge points.

The actual CGAL error varies randomly. It is currently:

ERROR: CGAL error in CGAL_Nef_polyhedron3(): CGAL ERROR: assertion violation! Expr: pe_prev->is_border() || !internal::Plane_constructor<Plane>::get_plane(pe_prev->facet(),pe_prev->facet()->plane()).is_degenerate() File: C:/msys64/mingw64/include/CGAL/Nef_3/polyhedron_3_to_nef_3.h Line: 251


I think merging two vertices that were originally distinct will always result in a non-manifold mesh. How can it be otherwise? The edges would need to be fixed up to correct the topology.

On Sat, 5 Jan 2019 at 09:59, nop head <[hidden email]> wrote:
I don't think you would do it in a random direction. You need to maintain the same inequalities between the points. I can see that might cause a chain reaction if you have lots of very close points as each would need to move a bit further.

OpenSCAD's grid is a sort of point dictionary but it deliberately tries to merge close points even if they are one grid step away. How can that be right? Doesn't it always break the topology and create a CGAL exception if points get merged?

On Sat, 5 Jan 2019 at 03:09, MichaelAtOz <[hidden email]> wrote:
Alan Cox-2 wrote
> It's an OpenSCAD bug. A proper STL exporter uses a point dictionary and
> if two differing points have the same dictionary entry then it minimally
> tweaks the values in the dictionary to avoid the ambiguity.

How can it tweak without analyzing the whole thing.
Just bumping a point in some random direction is just as likely to cause
problems.



-----
Admin - email* me if you need anything, or if I've done something stupid...

* click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work. Obviously inclusion of works of previous authors is not included in the above.

The TPP is no simple “trade agreement.”   Fight it! http://www.ourfairdeal.org/   time is running out!
--
Sent from: http://forum.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: CGAL error if F5 before F6

nophead
I also tested my library and a few big projects and they never trigger the "Collapsed" message. Basically I have avoided it by adding eps all other the place. So I think grid.h would be better throwing an exception saying you have vertices too close for OpenSCAD rather than merging them and causing CGAL to throw a random exception.

There is also code in grid.h that searches 27 neighbouring grid points and picks the nearest one that is populated. I.e. deliberately merging vertices that would otherwise be one grid position apart. Why? 

I still don't know what problem grid.h was intending to solve. It just seems to make things worse.



On Sat, 5 Jan 2019 at 13:33, nop head <[hidden email]> wrote:
I added some test code to grid.h to save the original value and then print if it merged a different vertex to the same entry.

        if (iter == db.end()) { // Not found: insert using key
            data = db.size();
            db[key] = data;
            values[key] = v;
        }
        else {
            // If found return existing data
            key = iter->first;
            data = iter->second;
            auto u = values[key];
            if(v != u)
                PRINTB("Collapsed (%f,%f,%f) to (%f,%f,%f)", v[0] % v[1] % v[2] % u[0] % u[1] % u[2]);
        }

With my F5 / F6 bug it only prints "Collapsed" when I get the CGAL error. I.e. for F5 before F6 but not for F6 first. So I think this shows that collapsing vertices with a grid is a bug.

This is a distilled down version of my code that gives the bug. There is probably some scope for simplifying it further.

eps = 1/128;
layer_height = 0.25;

module hanging_hole(z, ir, h = 100, h2 = 100) {
    infill_angle =  45;
    render(convexity = 3) translate([0, 0, z]) {
        rotate(infill_angle)
                intersection() {
                    rotate(-infill_angle)
                        linear_extrude(height = 3 * layer_height, center = true)
                                //offset(-eps)
                            children();

                    cube([100, 2 * ir, 2 * layer_height], center = true);
                }
        below = min(z + eps, h2);
        translate([0, 0, -below])
            linear_extrude(height = below)
                children();
    }
}

$fn = 11;
cube();
render()
    translate([20, 10])
        difference() {
            cylinder(d = 15, h = 5);
           
            hanging_hole(z = 2, ir = 2.5)
                circle(r = 5 / cos(180 / $fn));
           
        }

Adding the commented out offset(-eps) moves the vertices apart so they no longer get merged during F5 and the bug goes away. But that forces grid.h to not merge points.

The actual CGAL error varies randomly. It is currently:

ERROR: CGAL error in CGAL_Nef_polyhedron3(): CGAL ERROR: assertion violation! Expr: pe_prev->is_border() || !internal::Plane_constructor<Plane>::get_plane(pe_prev->facet(),pe_prev->facet()->plane()).is_degenerate() File: C:/msys64/mingw64/include/CGAL/Nef_3/polyhedron_3_to_nef_3.h Line: 251


I think merging two vertices that were originally distinct will always result in a non-manifold mesh. How can it be otherwise? The edges would need to be fixed up to correct the topology.

On Sat, 5 Jan 2019 at 09:59, nop head <[hidden email]> wrote:
I don't think you would do it in a random direction. You need to maintain the same inequalities between the points. I can see that might cause a chain reaction if you have lots of very close points as each would need to move a bit further.

OpenSCAD's grid is a sort of point dictionary but it deliberately tries to merge close points even if they are one grid step away. How can that be right? Doesn't it always break the topology and create a CGAL exception if points get merged?

On Sat, 5 Jan 2019 at 03:09, MichaelAtOz <[hidden email]> wrote:
Alan Cox-2 wrote
> It's an OpenSCAD bug. A proper STL exporter uses a point dictionary and
> if two differing points have the same dictionary entry then it minimally
> tweaks the values in the dictionary to avoid the ambiguity.

How can it tweak without analyzing the whole thing.
Just bumping a point in some random direction is just as likely to cause
problems.



-----
Admin - email* me if you need anything, or if I've done something stupid...

* click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work. Obviously inclusion of works of previous authors is not included in the above.

The TPP is no simple “trade agreement.”   Fight it! http://www.ourfairdeal.org/   time is running out!
--
Sent from: http://forum.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: CGAL error if F5 before F6

MichaelAtOz
Administrator
https://github.com/openscad/openscad/blob/c6a485651fa29f1a878ea454558192492f7467ec/src/grid.h#L14

/* Using decimals that are exactly convertible to binary floating point
(and then converted exactly to a GMPQ Rational that uses a small amount
of bytes aka "limbs" in CGAL's engine) provides at least a 5% speedup
for ctest -R CGAL. We choose 1/1024 and 1/(1024*1024) In python: print
'%.64f' % float(fractions.Fraction(1,1024)) */

const double GRID_FINE = 0.00000095367431640625;

It appears that the grid-ness is intended to keep Rationals 'compact' to
speed CGAL processing.
This appears to be OK when only GCAL is used.
I'm wondering if the problem is the non-CGAL bits are perhaps operating
without a grid? ?speculation-still-looking?

const double GRID_FINE =0.00000095367431640625;
Your eps=1/128            =0.0078125

I'm wondering if you keep eps more chunky, say 0.001 you will have a higher
probability of staying away from the grid trip points




-----
Admin - email* me if you need anything, or if I've done something stupid...

* click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work. Obviously inclusion of works of previous authors is not included in the above.

The TPP is no simple “trade agreement.”   Fight it! http://www.ourfairdeal.org/   time is running out!
--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Admin - email* me if you need anything,
or if I've done something stupid...
* click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work.
Obviously inclusion of works of previous authors is not included in the above.


The TPP is no simple “trade agreement.” Fight it! http://www.ourfairdeal.org/ time is running out!
Reply | Threaded
Open this post in threaded view
|

Re: CGAL error if F5 before F6

MichaelAtOz
Administrator
In reply to this post by nophead
I assume you saw this

https://github.com/openscad/openscad/blob/548b9c7c932cdc2e709c616a68d5ab377719a916/src/cgalutils.cc#L767

> Using Grid here is important for performance reasons. See following model.
>   minkowski() {
>     cube([200, 50, 7], center = true);
>     rotate([90,0,0]) cylinder($fn = 8, h = 1, r = 8.36, center = true);
>     rotate([0,90,0]) cylinder($fn = 8, h = 1, r = 8.36, center = true);
>   }
>
> If we don't grid the geometry before converting to a Nef Polyhedron, the
> quads
> in the cylinders to tessellated into triangles since floating point
> incertainty causes the faces to not be 100% planar. The incertainty is
> exaggerated
> by the transform. This wasn't a problem earlier since we used Nef for
> everything,
> but optimizations since then has made us keep it in floating point space
> longer.

What does that code do in your instrumented grid?

Also what was the typical delta u v's v in your 'Collapsed' results?



-----
Admin - email* me if you need anything, or if I've done something stupid...

* click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work. Obviously inclusion of works of previous authors is not included in the above.

The TPP is no simple “trade agreement.”   Fight it! http://www.ourfairdeal.org/   time is running out!
--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Admin - email* me if you need anything,
or if I've done something stupid...
* click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work.
Obviously inclusion of works of previous authors is not included in the above.


The TPP is no simple “trade agreement.” Fight it! http://www.ourfairdeal.org/ time is running out!
12