>
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 I don't have a problem if I use 1/128 as it is much courser than the grid. I use 1/128 because it is exact in floating point and is a suitable value to stop Z fighting in OpenCSG when viewed from a typical distance. Where it goes wrong is when points nearly line up but don't because of slight floating point inaccuracies. In my example I am rotating a 11 sided polygon that is rotated 45 degrees one way and then another and stacked on itself. All the vertices theoretically line up but in practice they are very slightly off. The grid snaps them together which breaks the topology. To fix it I make the second polygon smaller by eps so the points remain distinct and it works but then I have a slightly wonky model. It is too small to notice when 3D printed but it can be seen with show edges. It would be better if the vertices where snapped together but it would need to be done after the rotate but before the union. If it is done after the union then the broken topology needs fixing up. In this case removing a ring of degenerate triangles. In other cases it seems to be self intersections as well and whatever this means
Expr: e_below != SHalfedge_handle()" a hole perhaps?
>
What does that code do in your instrumented grid? No collapses, so it works in F5 followed by F6. As rotations by 90 and
cylinder vertices
are now accurate after my changes then there are probably no slightly off vertices to collapse. In the recent past there would have been. But it seems to need a more complex situation to trigger this bug. In my example I had to translate the result away from the origin and union with a cube to get the CGAL error. In one model I had four hanging holes and only one showed the problem. It had a symmetrical twin that was OK, so it is very sensitive to numerical changes. >
Also what was the typical delta u v's v in your 'Collapsed' results? Collapsed (2.164763,4.740169,1.750000) by (2.38419e007,0,0) Collapsed (4.383843,2.817325,1.750000) by (0,7.15256e007,0) Collapsed (4.383843,2.817325,1.750000) by (0,7.15256e007,0) Collapsed (4.383843,2.817325,1.750000) by (0,7.15256e007,0) Collapsed (2.164763,4.740169,1.750000) by (2.38419e007,0,0) Collapsed (4.383843,2.817325,1.750000) by (0,7.15256e007,0) Collapsed (2.164763,4.740169,1.750000) by (2.38419e007,0,0) Collapsed (2.164763,4.740169,1.750000) by (2.38419e007,0,0) Collapsed (2.164763,4.740169,1.750000) by (2.38419e007,0,0) Collapsed (2.164763,4.740169,1.750000) by (2.38419e007,0,0) Collapsed (4.383843,2.817325,1.750000) by (0,7.15256e007,0) Eleven, which matches the polygonal seam that goes wrong. It always seems to give a CGAL error with an odd number of vertices. Some even numbers generate collapses but no CGAL error, so I don't understand it completely. On Sat, 5 Jan 2019 at 22:10, MichaelAtOz <[hidden email]> wrote: I assume you saw this _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
Administrator

In reply to this post by MichaelAtOz
> It appears that the gridness is intended to keep Rationals 'compact' to
speed CGAL processing. No, that was just a refinement, changing from the arbitrary 0.000001, for efficiency. > 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 don't think it is that simple, I haven't fully grasped what it is up to. 'nearest one'  It is taking the Euclidean norm, of the grid points. I've seen this somewhere recently, I think reading on topology repair. I'm wondering if the implementation is wrong. Should it not look for the closest point on the 3x3 grid based on nonquantised values, ie float vector. As is d = sqrt((keyk).squaredNorm())  key & k have both been quantised. Otherwise the +/1 grid space Euclidean distance seems sort of pointless (no pun intended). So where are all the Topologists? What is it mean to do to refine the topology into a grid?  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 sqrt is pointless as it only needs to know the nearest, so could compare the squared value. Also the 27 distances are constants, either 0, 1, sqrt(2) or sqrt(3). The 2D version uses the Manhattan distance, which I think is just as good for +/1 but abs() might take longer than integer multiply. Wouldn't it be roughly the same to make the grid spacing three times bigger? I had actually removed the neighbour search when I posted the offsets above. With that code back in more vertices collapse. Collapsed (2.164763,4.740169,1.750000) by (2.38419e007,0,0) Collapsed (3.412535,3.938275,1.750000) by (1.19209e006,2.38419e007,0) Collapsed (3.412535,3.938275,1.750000) by (1.19209e006,2.38419e007,0) Collapsed (4.383843,2.817325,1.750000) by (0,7.15256e007,0) Collapsed (4.383843,2.817325,1.750000) by (0,7.15256e007,0) Collapsed (4.383843,2.817325,1.750000) by (0,7.15256e007,0) Collapsed (2.164763,4.740169,1.750000) by (2.38419e007,0,0) Collapsed (4.383843,2.817325,1.750000) by (0,7.15256e007,0) Collapsed (2.164763,4.740169,1.750000) by (2.38419e007,0,0) Collapsed (2.164763,4.740169,1.750000) by (2.38419e007,0,0) Collapsed (2.164762,4.740170,2.000000) by (4.76837e007,4.76837e007,0) Collapsed (2.164763,4.740169,1.750000) by (2.38419e007,0,0) Collapsed (2.164762,4.740170,2.000000) by (4.76837e007,4.76837e007,0) Collapsed (2.164763,4.740169,1.750000) by (2.38419e007,0,0) Collapsed (5.000000,1.468132,2.000000) by (4.76837e007,4.76837e007,0) Collapsed (4.383843,2.817325,1.750000) by (0,7.15256e007,0) Collapsed (2.164762,4.740170,2.000000) by (4.76837e007,4.76837e007,0) Collapsed (5.000000,1.468132,2.000000) by (4.76837e007,4.76837e007,0) Collapsed (3.412535,3.938275,1.750000) by (1.19209e006,2.38419e007,0) Collapsed (5.000000,1.468132,2.000000) by (4.76837e007,4.76837e007,0) Collapsed (3.412535,3.938275,1.750000) by (1.19209e006,2.38419e007,0) Collapsed (2.164762,4.740170,2.000000) by (4.76837e007,4.76837e007,0) Collapsed (2.164762,4.740170,2.000000) by (4.76837e007,4.76837e007,0) Collapsed (5.000000,1.468132,2.000000) by (4.76837e007,4.76837e007,0) Collapsed (5.000000,1.468132,2.000000) by (4.76837e007,4.76837e007,0) Collapsed (5.000000,1.468132,2.000000) by (4.76837e007,4.76837e007,0) But the results are the same. Curiously if the number of sides is even F5 works but F6 fails unless the cache is flushed. When it is odd the CGAL error happens in F5. It seems that Polyset is only that, a set of polygons, which are lists of vertices, no edge information. So I think collapsing vertices should be OK in that format as the edges are implied. That would be as long as all the faces have exactly the right vertex values, so that each copy of the vertex in different polygons ends up snapped to the same value. After snapping it removes duplicate triangles and degenerate triangles here: https://github.com/openscad/openscad/blob/master/src/polyset.cc#L220. So there seems to definitely be a bug when it collapses vertices but I no longer think it is fundamentally wrong to do it while in PolySet format. It would be for a mesh with edges. On Sun, 6 Jan 2019 at 03:28, MichaelAtOz <[hidden email]> wrote: > It appears that the gridness is intended to keep Rationals 'compact' to _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
I added some debug to Polyset and simplified my model to be a stacked pentagon subtracted from a cube to reduce the complexity of the polygons. It now looks like this: It looks like during F6 the union is never converted to a Polyset, so there are no near vertices to collapse. F5 converts the union to a Polyset before feeding it to CGAL and that is were it goes wrong as there are close vertices in the same Polyset and they do collapse. Here is the Polyset before, during and after being quantized. polyset: PolySet: num polygons: 44 polygon 0: ( 5 3.63271 2) (1.29953 4.83507 2.25) ( 5 3.63271 2.25) polygon 1: (1.29953 4.83507 2.25) ( 5 3.63271 2) (1.29953 4.83507 2) polygon 2: (2.09182 5.62736 2.25) (4.83195 1.8559 2) (2.09182 5.62736 1.75) polygon 3: (5.06738 1.53185 2.25) (4.83195 1.8559 2) (2.09182 5.62736 2.25) polygon 4: (4.83195 1.8559 2) (5.06738 1.53185 2.25) (5.06738 1.53185 2) polygon 5: (2.09182 5.62736 1.75) (4.83195 1.8559 2) (4.83195 1.8559 1.75) polygon 6: ( 5 3.63271 2) ( 5 1.46447 2.25) ( 5 1.46447 2) polygon 7: ( 5 1.46447 2.25) ( 5 3.63271 2) ( 5 3.63271 2.25) polygon 8: ( 5 1.46447 2.25) (5.06738 1.53185 2.25) (2.09182 5.62736 2.25) polygon 9: (5.06738 1.53185 2.25) ( 5 1.46447 2.25) (1.29953 4.83507 2.25) polygon 10: (1.29953 4.83507 2.25) ( 5 1.46447 2.25) ( 5 3.63271 2.25) polygon 11: ( 5 1.46447 2) (2.09182 5.62736 2.25) (2.09182 5.62736 2) polygon 12: (2.09182 5.62736 2.25) ( 5 1.46447 2) ( 5 1.46447 2.25) polygon 13: (2.09182 5.62736 1.75) (2.09182 5.62736 1.75) (2.09182 5.62736 2) polygon 14: (2.09182 5.62736 2) (2.09182 5.62736 2.25) (2.09182 5.62736 1.75) polygon 15: (4.83195 1.8559 1.75) (2.09182 5.62736 1.75) (2.09182 5.62736 1.75) polygon 16: (1.29953 4.83507 2) (5.06738 1.53185 2.25) (1.29953 4.83507 2.25) polygon 17: (5.06738 1.53185 2.25) (1.29953 4.83507 2) (5.06738 1.53185 2) polygon 18: ( 5 3.63271 0.0078125) ( 1.90983 5.87785 2) ( 5 3.63271 2) polygon 19: ( 1.90983 5.87785 2) ( 5 3.63271 0.0078125) ( 1.90983 5.87785 0.0078125) polygon 20: ( 1.90983 5.87785 2) ( 6.18034 0 0.0078125) (6.18034 0 2) polygon 21: ( 6.18034 0 0.0078125) ( 1.90983 5.87785 2) ( 1.90983 5.87785 0.0078125) polygon 22: ( 1.90983 5.87785 0.0078125) ( 5 3.63271 2) (1.90983 5.87785 2) polygon 23: ( 5 3.63271 2) ( 1.90983 5.87785 0.0078125) ( 5 3.63271 0.0078125) polygon 24: ( 5 3.63271 0.0078125) ( 5 3.63271 2) ( 5 3.63271 0.0078125) polygon 25: ( 5 3.63271 2) ( 5 3.63271 0.0078125) ( 5 3.63271 2) polygon 26: ( 5 3.63271 2) (2.09182 5.62736 2) (1.90983 5.87785 2) polygon 27: ( 5 3.63271 2) ( 5 1.46447 2) ( 5 3.63271 2) polygon 28: (2.09182 5.62736 2) ( 5 3.63271 2) ( 5 1.46447 2) polygon 29: (6.18034 0 2) (4.83195 1.8559 2) (5.06738 1.53185 2) polygon 30: (5.06738 1.53185 2) ( 1.90983 5.87785 2) (6.18034 0 2) polygon 31: (1.29953 4.83507 2) ( 1.90983 5.87785 2) (5.06738 1.53185 2) polygon 32: ( 5 3.63271 2) (1.29953 4.83507 2) ( 5 3.63271 2) polygon 33: (1.29953 4.83507 2) ( 5 3.63271 2) ( 1.90983 5.87785 2) polygon 34: ( 5 1.46447 2) ( 5 3.63271 2) ( 5 3.63271 2) polygon 35: ( 1.90983 5.87785 0.0078125) ( 1.90983 5.87785 0.0078125) ( 6.18034 0 0.0078125) polygon 36: ( 5 3.63271 0.0078125) ( 1.90983 5.87785 0.0078125) ( 1.90983 5.87785 0.0078125) polygon 37: ( 1.90983 5.87785 0.0078125) ( 5 3.63271 0.0078125) ( 5 3.63271 0.0078125) polygon 38: (4.83195 1.8559 2) (6.18034 0 2) (4.83195 1.8559 1.75) polygon 39: (2.09182 5.62736 1.75) (1.90983 5.87785 2) (2.09182 5.62736 2) polygon 40: (1.90983 5.87785 2) (2.09182 5.62736 1.75) ( 1.90983 5.87785 0.0078125) polygon 41: (4.83195 1.8559 1.75) ( 1.90983 5.87785 0.0078125) (2.09182 5.62736 1.75) polygon 42: ( 6.18034 0 0.0078125) (4.83195 1.8559 1.75) (6.18034 0 2) polygon 43: (4.83195 1.8559 1.75) ( 6.18034 0 0.0078125) ( 1.90983 5.87785 0.0078125) PolySet end Collapsed (2.091824,5.627358,1.750000) by (2.38419e007,0,0) polyset: Removing collapsed vertex 0 out of 3 from polygon 13 due to quantizing polyset: Removing collapsed polygon 13 due to quantizing Collapsed (2.091824,5.627358,1.750000) by (2.38419e007,0,0) polyset: Removing collapsed vertex 1 out of 3 from polygon 15 due to quantizing polyset: Removing collapsed polygon 15 due to quantizing Collapsed (5.000000,3.632712,2.000000) by (4.76837e007,0,0) Collapsed (5.000000,3.632712,2.000000) by (4.76837e007,0,0) Collapsed (5.000000,3.632712,2.000000) by (4.76837e007,0,0) Collapsed (5.000000,3.632712,2.000000) by (4.76837e007,0,0) polyset: Removing collapsed vertex 2 out of 3 from polygon 32 due to quantizing polyset: Removing collapsed polygon 32 due to quantizing Collapsed (5.000000,3.632712,2.000000) by (4.76837e007,0,0) Collapsed (5.000000,3.632712,2.000000) by (4.76837e007,0,0) polyset: Removing collapsed vertex 1 out of 3 from polygon 34 due to quantizing polyset: Removing collapsed polygon 34 due to quantizing Collapsed (2.091824,5.627358,1.750000) by (2.38419e007,0,0) Collapsed (2.091824,5.627358,1.750000) by (2.38419e007,0,0) Collapsed (2.091824,5.627358,1.750000) by (2.38419e007,0,0) polyset: PolySet: num polygons: 40 polygon 0: ( 5 3.63271 2) (1.29953 4.83507 2.25) ( 5 3.63271 2.25) polygon 1: (1.29953 4.83507 2.25) ( 5 3.63271 2) (1.29953 4.83507 2) polygon 2: (2.09182 5.62736 2.25) (4.83195 1.8559 2) (2.09182 5.62736 1.75) polygon 3: (5.06738 1.53185 2.25) (4.83195 1.8559 2) (2.09182 5.62736 2.25) polygon 4: (4.83195 1.8559 2) (5.06738 1.53185 2.25) (5.06738 1.53185 2) polygon 5: (2.09182 5.62736 1.75) (4.83195 1.8559 2) (4.83195 1.8559 1.75) polygon 6: ( 5 3.63271 2) ( 5 1.46447 2.25) ( 5 1.46447 2) polygon 7: ( 5 1.46447 2.25) ( 5 3.63271 2) ( 5 3.63271 2.25) polygon 8: ( 5 1.46447 2.25) (5.06738 1.53185 2.25) (2.09182 5.62736 2.25) polygon 9: (5.06738 1.53185 2.25) ( 5 1.46447 2.25) (1.29953 4.83507 2.25) polygon 10: (1.29953 4.83507 2.25) ( 5 1.46447 2.25) ( 5 3.63271 2.25) polygon 11: ( 5 1.46447 2) (2.09182 5.62736 2.25) (2.09182 5.62736 2) polygon 12: (2.09182 5.62736 2.25) ( 5 1.46447 2) ( 5 1.46447 2.25) polygon 13: (2.09182 5.62736 2) (2.09182 5.62736 2.25) (2.09182 5.62736 1.75) polygon 14: (1.29953 4.83507 2) (5.06738 1.53185 2.25) (1.29953 4.83507 2.25) polygon 15: (5.06738 1.53185 2.25) (1.29953 4.83507 2) (5.06738 1.53185 2) polygon 16: ( 5 3.63271 0.0078125) ( 1.90983 5.87785 2) ( 5 3.63271 2) polygon 17: ( 1.90983 5.87785 2) ( 5 3.63271 0.0078125) ( 1.90983 5.87785 0.0078125) polygon 18: ( 1.90983 5.87785 2) ( 6.18034 0 0.0078125) (6.18034 0 2) polygon 19: ( 6.18034 0 0.0078125) ( 1.90983 5.87785 2) ( 1.90983 5.87785 0.0078125) polygon 20: ( 1.90983 5.87785 0.0078125) ( 5 3.63271 2) (1.90983 5.87785 2) polygon 21: ( 5 3.63271 2) ( 1.90983 5.87785 0.0078125) ( 5 3.63271 0.0078125) polygon 22: ( 5 3.63271 0.0078125) ( 5 3.63271 2) ( 5 3.63271 0.0078125) polygon 23: ( 5 3.63271 2) ( 5 3.63271 0.0078125) ( 5 3.63271 2) polygon 24: ( 5 3.63271 2) (2.09182 5.62736 2) (1.90983 5.87785 2) polygon 25: ( 5 3.63271 2) ( 5 1.46447 2) ( 5 3.63271 2) polygon 26: (2.09182 5.62736 2) ( 5 3.63271 2) ( 5 1.46447 2) polygon 27: (6.18034 0 2) (4.83195 1.8559 2) (5.06738 1.53185 2) polygon 28: (5.06738 1.53185 2) ( 1.90983 5.87785 2) (6.18034 0 2) polygon 29: (1.29953 4.83507 2) ( 1.90983 5.87785 2) (5.06738 1.53185 2) polygon 30: (1.29953 4.83507 2) ( 5 3.63271 2) ( 1.90983 5.87785 2) polygon 31: ( 1.90983 5.87785 0.0078125) ( 1.90983 5.87785 0.0078125) ( 6.18034 0 0.0078125) polygon 32: ( 5 3.63271 0.0078125) ( 1.90983 5.87785 0.0078125) ( 1.90983 5.87785 0.0078125) polygon 33: ( 1.90983 5.87785 0.0078125) ( 5 3.63271 0.0078125) ( 5 3.63271 0.0078125) polygon 34: (4.83195 1.8559 2) (6.18034 0 2) (4.83195 1.8559 1.75) polygon 35: (2.09182 5.62736 1.75) (1.90983 5.87785 2) (2.09182 5.62736 2) polygon 36: (1.90983 5.87785 2) (2.09182 5.62736 1.75) ( 1.90983 5.87785 0.0078125) polygon 37: (4.83195 1.8559 1.75) ( 1.90983 5.87785 0.0078125) (2.09182 5.62736 1.75) polygon 38: ( 6.18034 0 0.0078125) (4.83195 1.8559 1.75) (6.18034 0 2) polygon 39: (4.83195 1.8559 1.75) ( 6.18034 0 0.0078125) ( 1.90983 5.87785 0.0078125) PolySet end 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 On Sun, 6 Jan 2019 at 10:20, nop head <[hidden email]> wrote:
_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
I can get the error with 3 vertices which reduces the number of polygons to 24 and look like this: Now with this no vertices get merged but it still fails with: 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 notice in the above data there are triangles that are degenerate when printed as floats. They don't snap to the same indexes though, so perhaps that is the problem. Not enough points get collapsed. In an attempt to investigate this I made the grid 32 times larger. The number of polygons went up to 32 before quantisation and then reduced to 28 due to some merging but still give the error. And there are still degenerate looking triangles that don't get snapped. How can a courser grid lead to more polygons? Is CGAL's idea of degenerate not absolute? I.e. does a very thin triangle count as degenerate? On Sun, 6 Jan 2019 at 12:43, nop head <[hidden email]> wrote:
_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
Actually no, there aren't any degenerate or nearly degenerate triangles after Polyset::quantize(). I was missing a minus sign. The 28 polygon Polyset that is the last to be quantized is actually the inner render(). It is a negative volume that looks like this: I wonder why the top level render doesn't get quantized. Perhaps CGAL fails before. On Sun, 6 Jan 2019 at 17:24, nop head <[hidden email]> wrote:
_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
Actually there are degenerate triangles with zero area caused by quantising the vertices of very thin ones. With a larger grid I can see this: polygon 15: ( 5 1.46447 2) (5.00001 1.46447 1.75) (5.00001 1.46447 2.25) After quantization it becomes this: polygon 11: ( 5 1.46445 2) ( 5 1.46445 1.75) ( 5 1.46445 2.25) So the bug is that quantisation can make very thin triangles into degenerate triangles and these are not removed because they still have three unique vertices. So we need mesh repair during quantization, even though PolySet is not really a mesh format. It seems to be just a polygon soup and they all seem to be triangles so it is just like STL but with doubles instead of floats. If this is fixed perhaps we could change grid to snap to values that are distinguishable as ascii floats by using that as the key. Then STL export would work I think. On Sun, 6 Jan 2019 at 18:32, nop head <[hidden email]> wrote:
_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
When I compile my own version with MSYS2 I get 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 but when I download an MXE version I get ERROR: CGAL error in CGAL_Nef_polyhedron3(): CGAL ERROR: assertion violation! Expr: e_below != SHalfedge_handle() File: /mxe/usr/x86_64w64mingw32.static.posix/include/CGAL/Nef_3/SNC_FM_decorator.h Line: 426 I don't know what
e_below != SHalfedge_handle() means but I have worked out on paper that as well as degenerate triangles you can also get flipped triangles when they are thin and the vertices are snapped. So it looks like we need general mesh repair after quantisation. On Sun, 6 Jan 2019 at 20:25, nop head <[hidden email]> wrote:
_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
Administrator

In reply to this post by nophead
The more I look into topology, as an initiate, the more the grid algorithm,
particularly the historical versions, resemble more complex solutions than just chunkying it. Such as Discrete Spaces. This discretisation <https://en.wikipedia.org/wiki/Discretizationhttp://> is not a new challenge <https://smartech.gatech.edu/bitstream/handle/1853/3239/0328.pdf> (one random link on my browsing). Marius, do you recall where you got the original grid algorithm? Below is just some random observations. Have a look at this <https://zeuxcg.org/2010/12/14/quantizingfloats/> . Do you think floor() may make a difference? Looking at the history of grid shows this explanation: "Reinstate Grid to fix problems introduced due to floating point inaccuracy. Grid does a certain job at vertex melding across objects and also help keeping plans planar" I can't see how the 3x3 part helps with keeping things planar...  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. 
I think the 3x3 is there because two extremely close points can snap to adjacent grid cells if they happen to straddle a boundary. This is very likely with a fine grid and even with a course one it could happen. On Mon, 7 Jan 2019 at 09:39, MichaelAtOz <[hidden email]> wrote: The more I look into topology, as an initiate, the more the grid algorithm, _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
Of course I mean coarse! The 3x3 search will fail if there are two points slightly more than one grid cell apart. They will snap to being two apart, so grid spacing is crucial. With a third point in between they might merge or not depending on which order they are encountered. I will investigate further because one would have hoped that the operands to the union would have been snapped to the same points, eliminating the small triangles in the union. On Mon, 7 Jan 2019 at 09:43, nop head <[hidden email]> wrote:
_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
Administrator

This is why I think the previous use of !grid.has() is important, it is not
used now. I'm still trying to groke it, but I'm wondering if the purpose is to take those adjacent points and snap them to the central point. ?? I haven't been able to commit enough time to deep dive this ATM.  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. 
Looking at my example I think the rotated polygon's vertices do get snapped back together, the problem is the intersection with the cube. That produces intersections with a sloping plane, so those can never line exactly on the plane when expressed as doubles. When the intersection is done in CGAL the results already contain degenerate and nearly degenerate triangles simply by converting them to Polyset doubles. The grid quantization changes one from a sliver to fully degenerate, one fully degenerate into a sliver and leaves two fully degenerate the same. There is a 50% chance each of these will also have the wrong winding order because in the rational format they probably were all slivers correctly orientated. That is lost by truncating them to doubles. So, as we have known since the beginning, you cannot reduce the resolution of the vertices in any way without following it with a mesh repair. OpenSCAD is fundamentally broken in this respect and always has been at the very least on STL export. Now there are many places it can go wrong as switches between rationals, doubles and fixed point. Gridding can't fix points that have to meet a diagonal plane. That will always generate slivers where the originally flat plane gets tessellated. You can see this here where there is an extra edge. On Mon, 7 Jan 2019 at 10:38, MichaelAtOz <[hidden email]> wrote: This is why I think the previous use of !grid.has() is important, it is not _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
In reply to this post by MichaelAtOz
I'm a bit late to the party, but some thoughts:
* Even if we remove vertex quantization in grid, we'll have to round to float at some point (STL export, polyset caching) * Maintaining the topology of a polygon mesh during rounding is not trivial. Here's a relatively early paper on the topic: https://link.springer.com/article/10.1007/PL00009480 * Snap rounding (grid) _may_ be easier than float rounding since we can work on a fixed grid, but I haven't dug into this in detail. * We may need to care about rounding to float vs. rounding to double, as exported STL files may be interpreted as singleprecision float by downstream software. * An alternative to managing rounding properly is to perform mesh repair at various stages. Mesh repair is another challenge which a few people have tried to tackle. I believe Carsten Arnholm implemented a pretty robust one earlier, but not open source. He did outline his algorithm though. * A while ago I started on experimenting with resolving degenerate triangles using edge flip, but I didn't manage to make too much improvement with a naive approach; see https://github.com/openscad/openscad/tree/edgeflip On the origins of gridding: * I cannot remember exactly why vertex quantization (grid) was introduced in the first place, but as Michael pointed out, it does seem to be necessary to resolve commonly occurring degenerate vertices during STL export (due to float rounding I guess). * The same would happen with PolySet caching I think. * There were some issues earlier related to CGAL reconstructing polygons from neighbouring planar triangles. If we round to float, CGAL didn't "see" the planarity, but after quantization, it worked better. Since CGAL operations tend to scale with the # of planes, such merging actually improves performance. I think we can keep this a pretty low priority though. On rationals: * Using Rationals gives us a nice cushion in terms of not having to deal with numeric stability of a bunch of algorithms. These are mostly (all?) implemented by CGAL. * Rationals comes with a significant performance penalty. Some optimization done here is likely the cause of the F5/F6 caching issue. * If we could manage topologies in floating point space, the options of how to process meshes would expand, we could test different libraries, better isolate components of OpenSCAD etc. Finding the time to address this at all is quite daunting : / Marius _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
For reference I tried it without the grid and it still fails. I now know this is because it is already broken at the rational to double truncation. Yes I think STL files only support single precision floats. A fixed grid will not work with floats at all scales because floats have decreasing resolution as you move away from the origin. I had to translate my test from the origin to get it to fail. It might be possible to pick a grid that works for the normal 3D print scale though. I think it needs to be chosen carefully to merge common trig rounding errors. If you have a simple quad then grid snapping will help it stay planar but where you have a more complex face, like a rectangle not parallel to an axis with a rectangular slot then grid snapping actually makes it less planar as the points defining the slot get snapped from their ideal position which is not a rational number and the ideal position changes slightly if the corners are snapped. This is what happens in this example. It keeps the triangular pocket planar but the intersecting cube causes problems. When F6 is run from an empty cache the resulting exported STL looks OK but NetFabb says it is self intersecting and refuses to fix it unless I pay. The complicated second operand to the difference never seems to be converted to a Polyset, so it never gets broken. CGAL is happy but the final result gets broken converting to float for the export. I tried to find where render() was implemented but couldn't find where it did the actual geometry. It seems during F5 is must run CGAL and convert the result to a Polyset and cache it. During F6 it seems to be a NOP. Is this the case? On Mon, 7 Jan 2019 at 13:30, Marius Kintel <[hidden email]> wrote: I'm a bit late to the party, but some thoughts: _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
I had a play with your edgeflip branch but it flipped far edges than necessary and didn't always fix all the degenerate triangles, so didn't always fix the CGAL error. It also generated lots of CGAL warnings about corrupt data structures on the command line console. I rolled my own even more naive version that runs after PolySet::quantizeVertices() and it does seem to remove all the degenerate triangles and fix this issue. Because it works on a PolySet, which is just a triangle soup like STL it should be possible to apply the same algorithm to STL, or just make the grid on ASCII float boundaries. I don't know if it works in all possible cases because it has no theoretical basis. I just hand corrected my test example and then coded it to do the same. It isn't terribly efficient because it has no edge structures, so it is O(MN) when M is the number of degenerate triangles and N the number of faces. However, it is better than failing with an error. On Mon, 7 Jan 2019 at 18:44, nop head <[hidden email]> wrote:
_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
Free forum by Nabble  Edit this page 