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 <nop.head@gmail.com> wrote: > 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 <oz.at.michael@gmail.com> wrote: > >> 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/03-28.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/quantizing-floats/> >> . >> 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 >> Discuss@lists.openscad.org >> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >> >

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/

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. [image: image.png] On Mon, 7 Jan 2019 at 10:38, MichaelAtOz <oz.at.michael@gmail.com> wrote: > 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 > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >

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 single-precision 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

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. [image: image.png] 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 <kintel@kintel.net> wrote: > 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 single-precision 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 > Discuss@lists.openscad.org > 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. The PR is https://github.com/openscad/openscad/pull/2694 On Mon, 7 Jan 2019 at 18:44, nop head <nop.head@gmail.com> wrote: > 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. > > [image: image.png] > > 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 <kintel@kintel.net> wrote: > >> 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 single-precision 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 >> Discuss@lists.openscad.org >> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >> >