Quantcast

cgal error with 2 triangles

classic Classic list List threaded Threaded
19 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

cgal error with 2 triangles

juerg.maier
This post was updated on .
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



Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: cgal error with 2 triangles

wolf
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: cgal error with 2 triangles

Parkinbot
In reply to this post by juerg.maier
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);
    }
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: cgal error with 2 triangles

juerg.maier
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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: cgal error with 2 triangles

wolf
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

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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: cgal error with 2 triangles

juerg.maier
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: cgal error with 2 triangles

nophead
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 <[hidden email]> 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
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: cgal error with 2 triangles

MichaelAtOz
Administrator
In reply to this post by juerg.maier
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!
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: cgal error with 2 triangles

Parkinbot
In reply to this post by juerg.maier
One can speculate a lot, especially if the history of the STL is unknown. Can you share the STL?
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: cgal error with 2 triangles

juerg.maier
In reply to this post by nophead
@nophead
I do not agree that it only accepts manyfolds - otherwise the warning "stl might not be manifold" does not make sense?
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: cgal error with 2 triangles

juerg.maier
In reply to this post by Parkinbot
@Parkinbot My stl represents the land masses of the globe. It is currently only a shell (no thickness). But I first wanted to be able to run this through CGAL before trying to construct a valid manifold from it (adding an inner shell and connect them properly).

However it looks like I will never be able to create CGAL accepted facets .

I am giving a try now to avoid CGAL by creating a printable manifold with the help of the python stl library. The slicers stl handling of the printer software looks to be more robust or flexible concerning small inconsistencies in facets.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: cgal error with 2 triangles

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

Well good luck trying to get CGAL to do CSG operations on invalid meshes in OpenSCAD.

Note that even with manifold operands CSG ops can result in non-manifold results. So the warning does make sense.

On 18 April 2017 at 15:28, juerg.maier <[hidden email]> wrote:
@Parkinbot My stl represents the land masses of the globe. It is currently only a shell (no thickness). But I first wanted to be able to run this through CGAL before trying to construct a valid manifold from it (adding an inner shell and connect them properly).

However it looks like I will never be able to create CGAL accepted facets .

I am giving a try now to avoid CGAL by creating a printable manifold with the help of the python stl library. The slicers stl handling of the printer software looks to be more robust or flexible concerning small inconsistencies in facets.


View this message in context: Re: cgal error with 2 triangles
Sent from the OpenSCAD mailing list archive at Nabble.com.


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org



_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: cgal error with 2 triangles

adrian
In reply to this post by juerg.maier
Hi, just out of curiosity, is that file around 7.2GB in size?
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: cgal error with 2 triangles

wolf
Hi Juerg,
If I understand you correctly, what you really are trying to do is 3D print a globe? If that is the case, forget about CGAL entirely and consider polyhedron() or surface(). Either will give you a 3D shape that is compatible with CGAL, as long as you adhere to CGAL's requirement of Is_Simple. If you violate that requirement and trigger a Is_Simple assertion violation, OpenSCAD will print as error message  "stl might not be manifold". For members of the computer graphics community, these two messages are identical and interchangeable, for someone relying on a background in mathematics the term "non-manifold" is unadulterated nonsense, as any graphics you might display on a computer screen will have a dimension greater than zero. People are entitled to assigning different meanings to a word . . .  (if it isn't done to confuse other people)
If my interpretation is correct and all you want to do is print a globe, the OpenSCAD manual should give you enough on surface() if you want to follow that route. As I have not used that command, I cannot give you further guidance there.
If, on the other hand, you want to use polyhedron() to create your globe, I can give you further guidance, as I have done most of the steps needed before. In step 1, you create a sphere in such a way that you can access and manipulate the distance each facet/vertex on this sphere has. In a second step, you then change the radius of that sphere as a function of both altitude and longitude, and, voila, you have your globe, at the resolution you can obtain radius (=elevation) information.
 wolf
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: cgal error with 2 triangles

juerg.maier
In reply to this post by adrian
@adrian, I have 2 files, one is a profiled globe (mountains and sea depht) from http://www.thingiverse.com/thing:1924651. I would like to use the earth_9_24 data which is 250 MB in binary format.

I have tried to separate the mesh into land and sea parts for a printable 2 color globe but a difference with a sphere at sea level is
a) insufficient as some land parts differ only marginally from the sea level
b) fail due to CGAL errors with the globe mesh

I searched than for a land only mesh but run into more problems (some do not map with the globe data, others are hard to work on). I finally succeeded to extract a land mass shell using my own python script from this globe https://grabcad.com/library/earth-globe.

Next thing I want to try now is to categorize each facet of the profiled globe data into a land and sea part based on my land shell. If I can accomplish that and wait out the processing I will need to add a thickness to my 2 shell data sets to get 2 combinable stl to be loaded into Simplify3D, the printers software program I use.

I also have a Multec 2Move print header which will allow me to get a good 2 colored printout. But currently that looks rather a good distance away. So I do it step by step and also learn a lot about 3d vectors, python and stl.

Unfortunately it is almost impossible to use imported stl data that runs through CGAL unless you create it with an openscad script. Also cleaning such stl's with the bunch of free programs available (meshlab, meshmixer, netfabb, microsoft stl fixer) returns good results but will not be accepted by CGAL. And CGAL instead of at least pointing to a facet of my data only refers to an internal code line which is absolutely of no help to a standard openscad user.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: cgal error with 2 triangles

juerg.maier
In reply to this post by wolf
@wolf

thanks for coming back on this. maybe the explanations I have given to @adrian make it clear what i finally want to accomplish.

My initial question - how come CGAL throws an exception with 2 triangle definitions - must be far out of my math horizon.

The puzzle is not solved in my brain - if CSG can generate a view of an stl from all possible angles and distances - why can we not have a program that creates an stl after applying a boolean operation on that object. And if CGAL is not made for such a job - why can I not select another rendering method that is not as picky as CGAL? Or maybe STL is the real problem and we should have the option to convert STL into another format - apply boolean operations on that data - and reconvert it to a valid STL or stay with this better suited format for 3d objects?

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: cgal error with 2 triangles

nophead
CSG operations work on solids. Two triangles don't define a solid. You need a mesh that completely encloses a volume, with no holes and no self intersections or degenerate triangles.

Even then you might not be able to import it in to OpenSCAD because STL import and export don't work if you have vertices very close together. A long standing bug.

On 19 April 2017 at 10:42, juerg.maier <[hidden email]> wrote:
@wolf

thanks for coming back on this. maybe the explanations I have given to @adrian make it clear what i finally want to accomplish.

My initial question - how come CGAL throws an exception with 2 triangle definitions - must be far out of my math horizon.

The puzzle is not solved in my brain - if CSG can generate a view of an stl from all possible angles and distances - why can we not have a program that creates an stl after applying a boolean operation on that object. And if CGAL is not made for such a job - why can I not select another rendering method that is not as picky as CGAL? Or maybe STL is the real problem and we should have the option to convert STL into another format - apply boolean operations on that data - and reconvert it to a valid STL or stay with this better suited format for 3d objects?


View this message in context: Re: cgal error with 2 triangles
Sent from the OpenSCAD mailing list archive at Nabble.com.


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org



_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: cgal error with 2 triangles

Parkinbot
In reply to this post by juerg.maier
juerg.maier wrote
I finally succeeded to extract a land mass shell using my own python script from this globe https://grabcad.com/library/earth-globe.
...
Unfortunately it is almost impossible to use imported stl data that runs through CGAL unless you create it with an openscad script.
1. if your STL exporter doesn't generate a valid solid (i.e. a proper 3D manifold, no holes and self-intersections allowed), CGAL as well as any other programm seriously processing STLs will complain. The CSG subsystem does not complain, because it does not rely on valid manifolds. It uses the GPU to more or less put the set of triangles or polygons into RAM, calculate a view projection and then apply boolean operations in a "sloppy" way. Slicers in contrast, can be fault-tolerant due to their way of operation. Because they slice a solid into a sequence of 2D-polygon sets (which they further transform into a sequential 1D fill path for G-Code description), it is easy for them to close an open 2D-polygon to fix a hole, or split self-intersecting 2D-polygons (think about an "8") into a set of non self-intersecting polygons (think about "oo"). The result will not always be a "do what I mean", but it is printable.

2. I have created and manipulated hundreds of STLs with C#, C++ and Matlab-Code in ASCII and binary format for import to OpenSCAD. CGAL did not complain. The secret is: proper solids, no holes, no self-intersections.

3. If you have a set of triangles describing a single landmass as a proper surface (i.e. proper triangulation into a 2D-solid embedded in 3D, no holes, no self-intersections), it is quite easy to construct a 3D manifold from that. Add a common center point CP to the point list and introduce a triangle between this point and every edge that is border i.e. that is not shared by two triangles. While this works for one continuous landmass (check: the border must be described by n distinct edges and n distinct vertices. No self-intersection allowed), you run into a problem, if your triangles describe a set of landmasses. Why? OpenSCAD does not allow Boolean operations on sets of solids that share single vertices or edges. See this code:

n=0; // no CGAL union possible
n=0.01; // CGAL union possible

p = [[n, 0, 0], [n, 0, 1], [n, 1, 1], [1, 0, 1]];
p1 = -p;

polyhedron(p, [[0, 2, 1], [0, 3, 2], [0, 1, 3], [1, 2, 3]]);
polyhedron(-p, [[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 2]]);
setting n=0 will create a CGAL warning, which leads to trouble if ignored.

4. That means, if you have a set of triangles describing a set of N landmasses, you need to construct a set of N "center" points, one for each landmass, each respecting the "non self-intersection" rule. A simple selection procedure would be to take one vertex Vi in each of the N borders, project it "half" way down along the line leading to the geometric center point CP. With CP =[0,0,0], you get it by a multiple of  Vi/norm(Vi).

Also cleaning such stl's with the bunch of free programs available (meshlab, meshmixer, netfabb, microsoft stl fixer) returns good results but will not be accepted by CGAL. And CGAL instead of at least pointing to a facet of my data only refers to an internal code line which is absolutely of no help to a standard openscad user.
Hopping around from tool to tool, doesn't make things better.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: cgal error with 2 triangles

juerg.maier
This post was updated on .
@parkinbot

Thanks for your elaborations and the hint for 'multi island problems' i might encounter.

My current plans are to leave CGAL out of my processing steps. I have been able to print objects with many intersecting triangles (some however come out misbuilded) but the slicer looks to accept such inconsistencies.

I am currently working on assining my profiled shell data either to the land or the sea parts. So far it has beef fun to work on the data and I have a lot of time to spend and learn new stuff like "is my profile point in a triangle pyramid defined by the center of my globe and one of the land triangles".

Loading...