Empathy List Archives

NH

nop head

Sun, Jan 6, 2019 12:56 AM

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.

[image: image.png]

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.38419e-007,0,0)

Collapsed (4.383843,2.817325,1.750000) by (0,7.15256e-007,0)

Collapsed (2.164763,4.740169,1.750000) by (2.38419e-007,0,0)

Collapsed (4.383843,2.817325,1.750000) by (0,7.15256e-007,0)

Collapsed (2.164763,4.740169,1.750000) by (2.38419e-007,0,0)

Collapsed (4.383843,2.817325,1.750000) by (0,7.15256e-007,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 oz.at.michael@gmail.com wrote:

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
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

> 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. [image: image.png] 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.38419e-007,0,0) Collapsed (4.383843,2.817325,1.750000) by (0,7.15256e-007,0) Collapsed (4.383843,2.817325,1.750000) by (0,7.15256e-007,0) Collapsed (4.383843,2.817325,1.750000) by (0,7.15256e-007,0) Collapsed (2.164763,4.740169,1.750000) by (2.38419e-007,0,0) Collapsed (4.383843,2.817325,1.750000) by (0,7.15256e-007,0) Collapsed (2.164763,4.740169,1.750000) by (2.38419e-007,0,0) Collapsed (2.164763,4.740169,1.750000) by (2.38419e-007,0,0) Collapsed (2.164763,4.740169,1.750000) by (2.38419e-007,0,0) Collapsed (2.164763,4.740169,1.750000) by (2.38419e-007,0,0) Collapsed (4.383843,2.817325,1.750000) by (0,7.15256e-007,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 <oz.at.michael@gmail.com> wrote: > 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 > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >

M

MichaelAtOz

Sun, Jan 6, 2019 3:27 AM

It appears that the grid-ness 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
non-quantised values, ie float vector.
As is d = sqrt((key-k).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/

> It appears that the grid-ness 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 non-quantised values, ie float vector. As is d = sqrt((key-k).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/

NH

nop head

Sun, Jan 6, 2019 10:20 AM

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.38419e-007,0,0)

Collapsed (-3.412535,-3.938275,1.750000) by (-1.19209e-006,2.38419e-007,0)

Collapsed (4.383843,2.817325,1.750000) by (0,7.15256e-007,0)

Collapsed (2.164763,4.740169,1.750000) by (2.38419e-007,0,0)

Collapsed (4.383843,2.817325,1.750000) by (0,7.15256e-007,0)

Collapsed (2.164763,4.740169,1.750000) by (2.38419e-007,0,0)

Collapsed (2.164762,4.740170,2.000000) by (4.76837e-007,-4.76837e-007,0)

Collapsed (2.164763,4.740169,1.750000) by (2.38419e-007,0,0)

Collapsed (2.164762,4.740170,2.000000) by (4.76837e-007,-4.76837e-007,0)

Collapsed (2.164763,4.740169,1.750000) by (2.38419e-007,0,0)

Collapsed (-5.000000,-1.468132,2.000000) by (4.76837e-007,-4.76837e-007,0)