Problem with Triangulation

Dec 7, 2012 at 6:27 AM

I have a lot of Triangulation Problems.

endless loops, out of memory, null or write input geometrie to poly file and read it back it works. Code is at the end. it will be nice when add this code to FileWriter (for Debugging).

i can create test .poly files from me 3D data if you want ?? !!

in same cases.

but i see i the code

behavior.Algorithm == TriangulationAlgorithm.Dwyer behavior.Algorithm == TriangulationAlgorithm.SweepLine

the default is Dwyer but i can not change this from user code.

i have changed your code the default to use SweepLine and alle problems go away.

can you add a option to change the TriangulationAlgorithm ?? !!


An other question is what do you doing with the attributes in points. this is a double array.

will be this attributes in the mesh triangles ?? when i write a z value in one attribute - is this

z value in the triangle ? but when you add a new vertex - z value linear interpolated ?


sorry my english is not so good.






        public static void Write(InputGeometry geo, string filename)
            using (StreamWriter writer = new StreamWriter(filename))
                int invertices = 0;
                invertices = geo.points.Count;
                int dimensions = 2;
                int startedge = 1;
                double[] attribs = geo.points[0].attributes;
                int attributes = 0;
                if (attribs != null)
                    attributes = attribs.Length;
                int nodemarkers = 1;
                writer.WriteLine("{0} {1} {2} {3}", invertices, dimensions, attributes, nodemarkers);
                int ii = 1;
                foreach (var pt in geo.Points)
                    String str = "";
                    if (attributes > 0)
                        foreach (var attr in pt.attributes)
                            if (str.Length > 0)
                                str = str + " ";
                            str = str + attr;
                    if (str.Length > 0)
                        str = str + " ";
                    str = str + pt.mark;
                    writer.WriteLine("{0} {1} {2} {3}", ii, pt.X.ToString(nfi), pt.Y.ToString(nfi), str);
//                writer.WriteLine("");
                int insegments = 0;
                insegments = geo.Segments.Count;
                int segmentmarkers = 1;
                writer.WriteLine("{0} {1}", insegments, segmentmarkers);
                ii = startedge;
                foreach (var edge in geo.Segments)
                    writer.WriteLine("{0} {1} {2} {3}", ii,edge.P0+1,edge.P1+1,edge.Boundary);
//                writer.WriteLine("");
                int holes = 0;
                holes = geo.Holes.Count;
                writer.WriteLine("{0}", holes);
                ii = 1;
                foreach (var hole in geo.Holes)
                    writer.WriteLine("{0} {1} {2}", ii, hole.X.ToString(nfi), hole.Y.ToString(nfi));
Dec 7, 2012 at 8:42 AM
Edited Dec 7, 2012 at 12:24 PM
  1. If not too large, post the geometry data here. Otherwise send the poly files to [deleted]
  2. I will add an option to change the triangulation algorithm like
    mesh.SetOption(Options.TriangulationAlgorithm, TriangulationAlgorithm.SweepLine)
  3. In the test app there's a class MeshExplorer.IO.GeometryWriter which you can use to write input geomtries. Just copy this file to your projects and you should be fine. I don't intend to add this to the library...
  4. Point attributes are working exactly the way you described it (linear interpolation).
Dec 7, 2012 at 10:03 AM

1. Ok -- i send a mail

2. nice

3. sorry i download the newest revision 71203 and search GeometryWriter - but i can not find !?

4. very nice -- my first code i translate and rotate all the surface in xy plane -> triangulate -> rotate, translate triangles and generate OpenGL triangles

  second i swap the x,y,z by the normale direction and write one coordinate to attributes -> triangulate -> swap coordinates back and generate OpenGL triangles

this needs only 500ms less time than the translate and rotate code (by 13200 polygons 1100 holes and 70000 vertices)

Tesslation over (only mesh.Triangulate(data)) 4000ms

Dec 7, 2012 at 12:20 PM
Edited Dec 7, 2012 at 12:25 PM

Hadn't checked in the GeometryWriter, should be online with the latest changeset.

Thanks for sending the poly file. It's a bug in Dwyer.cs, the triangulation is not correct. The actual exception is then thrown while trying to insert the segments later on. Maybe I'll find some time this weekend to track it down.

Seems it's the special alternating sort which is messed up. You can disable it in Dwyer.cs by setting

bool useDwyer = false;

Let me know if that solves the issue or if there are still geometries that fail.

Dec 7, 2012 at 12:31 PM


but thanks for the other changes

i mail a screenshot from the backtrace

Dec 7, 2012 at 1:06 PM

Ok, since the first poly file you sent me works when setting useDwyer = false, could you send another file which does not work.

Thanks again for your help!

Dec 8, 2012 at 2:16 PM

So, this does not seem to be a problem of the triangulation algorithm, but a problem of floating point precision. I added higher precision primitives in the latest changeset, but this of course doesn't solve the actual problem. Let me know if the problems reside!

I don't plan to implement robust floating point arithmetics (it would be a major effort). Read more about it at

BTW: you sent a mail with subject OutofMemory with SweepLine. I could not reproduce any out of memory exception!?