Empathy List Archives

J

juerg.maier

Sun, Apr 16, 2017 2:38 PM

I have a 100'000 facet stl file that throws a CGAL error when I try to render
it.Worked it down to the first 2 facets causing an error.Any hint how the
combination of these 2 facets are a problem for CGAL and how I could
probably fix it? (I use python stl library to filter out my facets from a
larger stl file I use as a base. So I might be able to modify the points
coordinates?).I get the error with F6 when I try to difference() these 2
triangles from a cube.ERROR: CGAL error in CGAL_Nef_polyhedron3(): CGAL
ERROR: assertion violation difference() {
import("outerShell_ml.stl"); translate([-11.4,-9.8,-6.5])
#cube(1); } solid outerShell_ml facet normal -0.685994 -0.514497
-0.514495 outer loop vertex -11.440000 -9.540000 -6.400000
vertex -11.259999 -9.780000 -6.400000 vertex -11.320000 -9.719999
-6.380000 endloop endfacet facet normal -0.665639 -0.554699
-0.499233 outer loop vertex -11.440000 -9.540000 -6.400000
vertex -11.620000 -9.360000 -6.360000 vertex -11.740000 -9.179999
-6.400000 endloop endfacet endsolid outerShell_ml

--
View this message in context: http://forum.openscad.org/cgal-error-with-2-triangles-tp21240.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

I have a 100'000 facet stl file that throws a CGAL error when I try to render it.Worked it down to the first 2 facets causing an error.Any hint how the combination of these 2 facets are a problem for CGAL and how I could probably fix it? (I use python stl library to filter out my facets from a larger stl file I use as a base. So I might be able to modify the points coordinates?).I get the error with F6 when I try to difference() these 2 triangles from a cube.ERROR: CGAL error in CGAL_Nef_polyhedron3(): CGAL ERROR: assertion violation difference() { import("outerShell_ml.stl"); translate([-11.4,-9.8,-6.5]) #cube(1); } solid outerShell_ml facet normal -0.685994 -0.514497 -0.514495 outer loop vertex -11.440000 -9.540000 -6.400000 vertex -11.259999 -9.780000 -6.400000 vertex -11.320000 -9.719999 -6.380000 endloop endfacet facet normal -0.665639 -0.554699 -0.499233 outer loop vertex -11.440000 -9.540000 -6.400000 vertex -11.620000 -9.360000 -6.360000 vertex -11.740000 -9.179999 -6.400000 endloop endfacet endsolid outerShell_ml -- View this message in context: http://forum.openscad.org/cgal-error-with-2-triangles-tp21240.html Sent from the OpenSCAD mailing list archive at Nabble.com.

W

wolf

Mon, Apr 17, 2017 8:36 AM

Triangles are not the cause of your problem, vertices and edges are. OpenSCAD
converts all polygons into triangles prior to presenting them to CGAL,
because CGAL is rather particular about accuracy (CGAL prides itself about
"NO ROUNDING ERRORS"). In your two triangles, I notice three occasions where
rounding was not done properly, e.g. -11.259999 instead of -11.260000. That
is where your problem starts.
To fix it, it is not enough to round "snap-to-grid" as I have indicated.
That works only if two edges are parallel with the axes of the coordinate
system. Proper rounding requires "snap-to-edge" rounding, and that is
inherently impossible if your numbers are restricted to a finite number of
decimal places. Thus, proper rounding has to be part of the mesh generator
itself. And besides - once the mesh generator has done its work, to undo the
nonsense it produces because it was fed with the wrong numbers you need to
undo the work of the mesh generator. And that ain't so easy . . .
CGAL only accepts simple polygons, polygons where vertices are only on the
end points of edges. Edges that intersect each other, or are stacked on top
of one another, are unacceptable and will generate one of several assertion
violations.

For an example on how to find the trouble spots see
http://forum.openscad.org/stl-not-correct-by-mesh-generators-td21241.html

wolf

--
View this message in context: http://forum.openscad.org/cgal-error-with-2-triangles-tp21240p21259.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

Triangles are not the cause of your problem, vertices and edges are. OpenSCAD converts all polygons into triangles prior to presenting them to CGAL, because CGAL is rather particular about accuracy (CGAL prides itself about "NO ROUNDING ERRORS"). In your two triangles, I notice three occasions where rounding was not done properly, e.g. -11.259999 instead of -11.260000. That is where your problem starts. To fix it, it is not enough to round "snap-to-grid" as I have indicated. That works only if two edges are parallel with the axes of the coordinate system. Proper rounding requires "snap-to-edge" rounding, and that is inherently impossible if your numbers are restricted to a finite number of decimal places. Thus, proper rounding has to be part of the mesh generator itself. And besides - once the mesh generator has done its work, to undo the nonsense it produces because it was fed with the wrong numbers you need to undo the work of the mesh generator. And that ain't so easy . . . CGAL only accepts simple polygons, polygons where vertices are only on the end points of edges. Edges that intersect each other, or are stacked on top of one another, are unacceptable and will generate one of several assertion violations. For an example on how to find the trouble spots see <http://forum.openscad.org/stl-not-correct-by-mesh-generators-td21241.html> wolf -- View this message in context: http://forum.openscad.org/cgal-error-with-2-triangles-tp21240p21259.html Sent from the OpenSCAD mailing list archive at Nabble.com.

P

Parkinbot

Mon, Apr 17, 2017 10:52 AM

I doubt it is the .xx9999 rounds, even rounding errors might play a role.
Don't know, how you visualize your code. An STL import with two triags is
not possible. But putting the vertices into a polyhedron will show that the
two triangles are almost coplanar. You can see this, when you hull the
polyhedron! So the triangulation might have exceeded some (float) resolution
limit.

v= [
[-11.440000, -9.540000, -6.400000],
[-11.259999, -9.780000, -6.400000],
[-11.320000, -9.719999, -6.380000],
[-11.440000, -9.540000, -6.400000],
[-11.620000, -9.360000, -6.360000],
[-11.740000, -9.179999, -6.400000],
];
// difference()
{
// hull()
polyhedron(v, [[0,1,2], [3,4,5]]);
translate([-11.4,-9.8,-6.5]) #cube(1);
}

--
View this message in context: http://forum.openscad.org/cgal-error-with-2-triangles-tp21240p21260.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

I doubt it is the .xx9999 rounds, even rounding errors might play a role. Don't know, how you visualize your code. An STL import with two triags is not possible. But putting the vertices into a polyhedron will show that the two triangles are almost coplanar. You can see this, when you hull the polyhedron! So the triangulation might have exceeded some (float) resolution limit. > v= [ > [-11.440000, -9.540000, -6.400000], > [-11.259999, -9.780000, -6.400000], > [-11.320000, -9.719999, -6.380000], > [-11.440000, -9.540000, -6.400000], > [-11.620000, -9.360000, -6.360000], > [-11.740000, -9.179999, -6.400000], > ]; > // difference() > { > // hull() > polyhedron(v, [[0,1,2], [3,4,5]]); > translate([-11.4,-9.8,-6.5]) #cube(1); > } -- View this message in context: http://forum.openscad.org/cgal-error-with-2-triangles-tp21240p21260.html Sent from the OpenSCAD mailing list archive at Nabble.com.

J

juerg.maier

Mon, Apr 17, 2017 1:47 PM

I am aware that my 2 triangles are not a usable stl file, but trying to
render them separately does not produce a cgal error but only a warning,
that the stl might not be a valid manifold.
Both triangles have the same rounded point where they are connected
(-11.44,-9.54,-6.4) so from my point of view the point is a valid common
point for the 2 triangles?

Openscad does not show any error importing the ascii-stl file containing
only the 2 triangles.

You mention it could be due to a rounding problem. I rounded then the
.xx99999 values to the next higher digit -9.179999 -> -9.180000 etc. and
with these slightly modified points the CGAL-error went away (for my very
limited 2 facet example).

You also mention it's not as simple as applying a rounding to the vertex
values to make the whole stl valid but I am tempted to give it a try.

--
View this message in context: http://forum.openscad.org/cgal-error-with-2-triangles-tp21240p21263.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

I am aware that my 2 triangles are not a usable stl file, but trying to render them separately does not produce a cgal error but only a warning, that the stl might not be a valid manifold. Both triangles have the same rounded point where they are connected (-11.44,-9.54,-6.4) so from my point of view the point is a valid common point for the 2 triangles? Openscad does not show any error importing the ascii-stl file containing only the 2 triangles. You mention it could be due to a rounding problem. I rounded then the .xx99999 values to the next higher digit -9.179999 -> -9.180000 etc. and with these slightly modified points the CGAL-error went away (for my very limited 2 facet example). You also mention it's not as simple as applying a rounding to the vertex values to make the whole stl valid but I am tempted to give it a try. -- View this message in context: http://forum.openscad.org/cgal-error-with-2-triangles-tp21240p21263.html Sent from the OpenSCAD mailing list archive at Nabble.com.

W

wolf

Tue, Apr 18, 2017 1:24 AM

If you want to give it a try . . .

My own version of fixing what on this forum is called "degenerate triangles"
is pretty advanced, but it still got issues. If you can handle Free Pascal /
Lazarus, I am willing to share my source with you. Just drop me a mail off
this list . . .

Rounding can be done two ways, "Snap-to-Grid" and "Snap-to-Edge". For
"Snap-to-Grid" you simply divide your number by the rounding factor r, round
to the nearest integer, and multiply with r again. This way, you get a grid
of points spaced by r, thus "Snap-to-Grid" type rounding. For "Snap-to-Edge"
type rounding, you find the longest edge AB of your triangle ABC and then
replace the coordinates of your point C with the coordinates of the
perpendicular foot of this point. There the problem starts: Unless two of
the edges of your triangle are parallel with your coordinate system, the
perpendicular foot does not lie on AB, but some distance away from it,
because of rounding.
Have a look at this
http://forum.openscad.org/file/n21278/Rounding.jpg
Consider ABC and DEF to be the same triangle, differing only in one feature:
Point C lies above edge AB, because of some rounding accident, and Point E
lies below DE. The dots in the picture mark the positions to which you can
round ("Snap-To-Grid" rounding). If you want to do boolean operations on it,
i.e. find where this triangle intersects any other, you need to derive the
equation of the plane that passes through A,B, and C. The first step there
is to obtain the normal as a cross product ABxAC in such a way that it is
well-defined, i.e. norm(ABxAC) does not change noticeably with minor changes
in the coordinates of A, B, or C. When you do that for both triangle ABC
and DEF, you'll see that the very minor change in the coordinates from C to
F results in a change of sign of the normal, and thus ABC or DEF cannot be
subjected to boolean operations, since the results are undefined!

You see now that "well-defined" implies that point C must be either far away
from AC, or lie on AC. In the latter case, ABC has no surface area and you
can drop the triangle from your shape, without your user noticing it. But
your mesh now contains an edge with three points on it, and that is
unacceptable to CGAL. Thus, you need to change the mesh in such a way that
point C is no longer part of the overall shape . . . So you have to create a
new mesh . . .

And if you move C far away from AB, you change the geometry. That is
unacceptable to the user . . .

You have a 100000 facet .stl file. Since most of the computing work consists
in searching, you'll need highly efficient search routines, something way
better than QuickSort (in big O notation, QuickSort is O(n log n) only for
random inputs. For pre-sorted inputs, and that is what you likely have,
QuickSort is O(n^2). And big O notation does not take into account the size
and relative speeds of the multitude of caches a modern computer offers, so
you'll face extensive profiling of your code . . .

If you still want to give it a try, drop me a mail.

wolf

--
View this message in context: http://forum.openscad.org/cgal-error-with-2-triangles-tp21240p21278.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

If you want to give it a try . . . My own version of fixing what on this forum is called "degenerate triangles" is pretty advanced, but it still got issues. If you can handle Free Pascal / Lazarus, I am willing to share my source with you. Just drop me a mail off this list . . . Rounding can be done two ways, "Snap-to-Grid" and "Snap-to-Edge". For "Snap-to-Grid" you simply divide your number by the rounding factor r, round to the nearest integer, and multiply with r again. This way, you get a grid of points spaced by r, thus "Snap-to-Grid" type rounding. For "Snap-to-Edge" type rounding, you find the longest edge AB of your triangle ABC and then replace the coordinates of your point C with the coordinates of the perpendicular foot of this point. There the problem starts: Unless two of the edges of your triangle are parallel with your coordinate system, the perpendicular foot does not lie on AB, but some distance away from it, because of rounding. Have a look at this <http://forum.openscad.org/file/n21278/Rounding.jpg> Consider ABC and DEF to be the same triangle, differing only in one feature: Point C lies above edge AB, because of some rounding accident, and Point E lies below DE. The dots in the picture mark the positions to which you can round ("Snap-To-Grid" rounding). If you want to do boolean operations on it, i.e. find where this triangle intersects any other, you need to derive the equation of the plane that passes through A,B, and C. The first step there is to obtain the normal as a cross product ABxAC in such a way that it is well-defined, i.e. norm(ABxAC) does not change noticeably with minor changes in the coordinates of A, B, or C. When you do that for both triangle ABC and DEF, you'll see that the very minor change in the coordinates from C to F results in a change of sign of the normal, and thus ABC or DEF cannot be subjected to boolean operations, since the results are undefined! You see now that "well-defined" implies that point C must be either far away from AC, or lie on AC. In the latter case, ABC has no surface area and you can drop the triangle from your shape, without your user noticing it. But your mesh now contains an edge with three points on it, and that is unacceptable to CGAL. Thus, you need to change the mesh in such a way that point C is no longer part of the overall shape . . . So you have to create a new mesh . . . And if you move C far away from AB, you change the geometry. That is unacceptable to the user . . . You have a 100000 facet .stl file. Since most of the computing work consists in searching, you'll need highly efficient search routines, something way better than QuickSort (in big O notation, QuickSort is O(n log n) only for random inputs. For pre-sorted inputs, and that is what you likely have, QuickSort is O(n^2). And big O notation does not take into account the size and relative speeds of the multitude of caches a modern computer offers, so you'll face extensive profiling of your code . . . If you still want to give it a try, drop me a mail. wolf -- View this message in context: http://forum.openscad.org/cgal-error-with-2-triangles-tp21240p21278.html Sent from the OpenSCAD mailing list archive at Nabble.com.

J

juerg.maier

Tue, Apr 18, 2017 7:32 AM

Hi Wolf

Thanks for your lengthy explanations. Looks however to me like my own
capabilities will not bring me to any result with this.
What I have problems to understand is why the preview of my object is able
to show me the triangles - not only the 2 ones that already cause CGAL
issues but also the whole 100000 triangles object to any zoom level I go -
but that this data can not be used to run boolean operations on it.

So maybe I will need something else than CGAL - or is CGAL the only option?

Regards

Juerg

--
View this message in context: http://forum.openscad.org/cgal-error-with-2-triangles-tp21240p21285.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

Hi Wolf Thanks for your lengthy explanations. Looks however to me like my own capabilities will not bring me to any result with this. What I have problems to understand is why the preview of my object is able to show me the triangles - not only the 2 ones that already cause CGAL issues but also the whole 100000 triangles object to any zoom level I go - but that this data can not be used to run boolean operations on it. So maybe I will need something else than CGAL - or is CGAL the only option? Regards Juerg -- View this message in context: http://forum.openscad.org/cgal-error-with-2-triangles-tp21240p21285.html Sent from the OpenSCAD mailing list archive at Nabble.com.

NH

nop head

Tue, Apr 18, 2017 7:45 AM

The preview just draws the triangles. CGAL is not involved until you do CSG
operations and it requires manifold data.

On 18 April 2017 at 08:32, juerg.maier juerg.maier@pobox.ch wrote:

Hi Wolf

Thanks for your lengthy explanations. Looks however to me like my own
capabilities will not bring me to any result with this.
What I have problems to understand is why the preview of my object is able
to show me the triangles - not only the 2 ones that already cause CGAL
issues but also the whole 100000 triangles object to any zoom level I go -
but that this data can not be used to run boolean operations on it.

So maybe I will need something else than CGAL - or is CGAL the only option?

Regards

Juerg

--
View this message in context: http://forum.openscad.org/
cgal-error-with-2-triangles-tp21240p21285.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

The preview just draws the triangles. CGAL is not involved until you do CSG operations and it requires manifold data. On 18 April 2017 at 08:32, juerg.maier <juerg.maier@pobox.ch> wrote: > Hi Wolf > > Thanks for your lengthy explanations. Looks however to me like my own > capabilities will not bring me to any result with this. > What I have problems to understand is why the preview of my object is able > to show me the triangles - not only the 2 ones that already cause CGAL > issues but also the whole 100000 triangles object to any zoom level I go - > but that this data can not be used to run boolean operations on it. > > So maybe I will need something else than CGAL - or is CGAL the only option? > > Regards > > Juerg > > > > -- > View this message in context: http://forum.openscad.org/ > cgal-error-with-2-triangles-tp21240p21285.html > Sent from the OpenSCAD mailing list archive at Nabble.com. > > _______________________________________________ > OpenSCAD mailing list > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >

M

MichaelAtOz

Tue, Apr 18, 2017 8:55 AM

Think of preview like old western movie sets, you only see the front of the
buildings, nothing exists behind. If you rotate it, the swarm of set
builders, just make another false front. It uses OpenCSG, not CGAL.

Render, builds the whole building including all fittings. That's what takes
all the time, but once built you can look from any angle.

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

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!

View this message in context: http://forum.openscad.org/cgal-error-with-2-triangles-tp21240p21287.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

Think of preview like old western movie sets, you only see the front of the buildings, nothing exists behind. If you rotate it, the swarm of set builders, just make another false front. It uses OpenCSG, not CGAL. Render, builds the whole building including all fittings. That's what takes all the time, but once built you can look from any angle. ----- Admin - PM me if you need anything, or if I've done something stupid... 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! -- View this message in context: http://forum.openscad.org/cgal-error-with-2-triangles-tp21240p21287.html Sent from the OpenSCAD mailing list archive at Nabble.com.

P

Parkinbot

Tue, Apr 18, 2017 1:25 PM

One can speculate a lot, especially if the history of the STL is unknown. Can
you share the STL?

--
View this message in context: http://forum.openscad.org/cgal-error-with-2-triangles-tp21240p21289.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

One can speculate a lot, especially if the history of the STL is unknown. Can you share the STL? -- View this message in context: http://forum.openscad.org/cgal-error-with-2-triangles-tp21240p21289.html Sent from the OpenSCAD mailing list archive at Nabble.com.

J

juerg.maier

Tue, Apr 18, 2017 2:12 PM

@nophead
I do not agree that it only accepts manyfolds - otherwise the warning "stl
might not be manifold" does not make sense?

--
View this message in context: http://forum.openscad.org/cgal-error-with-2-triangles-tp21240p21290.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

@nophead I do not agree that it only accepts manyfolds - otherwise the warning "stl might not be manifold" does not make sense? -- View this message in context: http://forum.openscad.org/cgal-error-with-2-triangles-tp21240p21290.html Sent from the OpenSCAD mailing list archive at Nabble.com.

discuss@lists.openscad.org

cgal error with 2 triangles

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