CGAL error if F5 before F6
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 nop.head@gmail.com 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 ed.nisley@pobox.com 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
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
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/
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 oz.at.michael@gmail.com 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
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
On Thu, 3 Jan 2019 19:59:28 +0000
nop head nop.head@gmail.com 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
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/
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 oz.at.michael@gmail.com 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
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
I added some test code to grid.h
https://github.com/openscad/openscad/blob/master/src/grid.h#L131 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 nop.head@gmail.com 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 oz.at.michael@gmail.com 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
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
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 nop.head@gmail.com wrote:
I added some test code to grid.h
https://github.com/openscad/openscad/blob/master/src/grid.h#L131 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 nop.head@gmail.com 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 oz.at.michael@gmail.com 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
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
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/
I assume you saw this
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/