C# occasional large triangles protrude from tops of shapes

[GoogleCodeExporter]

What steps will reproduce the problem?
1. Polygon mode
2. large number of verts 30,000+
3. openGL as renderer (C# wrapper)

What is the expected output? What do you see instead?
World map, ..  get world map with protruding large tris

What version of the product are you using? On what operating system?
C# port

Please provide any additional information below.

The code I use in my SVG viewer is as follows.  Works great for almostt every 
country and then just a handful have artifacts, attached image (subset of 
countries shows all is well except for Mexaco which has the artifact extruding 
north, white lines are border, grey filled by triangulator.  Also, many thanks, 
great library. :)

Poly2Tri.Polygon pointSet = new Poly2Tri.Polygon(points);
P2T.Triangulate(pointSet);
float[] bufferArray2 = new float[(pointSet.Triangles.Count) * 9];
uint triIndex = 0;
for (int i = 0; i < pointSet.Triangles.Count; ++i)
{
 bufferArray2[triIndex] = pointSet.Triangles[i].Points[0].Xf;
 bufferArray2[++triIndex] = pointSet.Triangles[i].Points[0].Yf;
 bufferArray2[++triIndex] = 0.0f;
 bufferArray2[++triIndex] = (float)pointSet.Triangles[i].Points[1].Xf;
 bufferArray2[++triIndex] = (float)pointSet.Triangles[i].Points[1].Yf;
 bufferArray2[++triIndex] = 0.0f;
 bufferArray2[++triIndex] = (float)pointSet.Triangles[i].Points[2].Xf;
 bufferArray2[++triIndex] = (float)pointSet.Triangles[i].Points[2].Yf;
 bufferArray2[++triIndex] = 0.0f;
 ++triIndex;
}
fillVerts = bufferArray2.Length / 3;
BufferManager.Instance.createVBO(ref bufferArray2, out fillVBO);

Original issue reported on code.google.com by danja_...@hotmail.co.uk on 12 May 2013 at 2:27

Attachments:

• PartialWorld.png

[GoogleCodeExporter]

Looks like the triangulation might have failed on Mexico for some unknown 
reason.
The final step in the triangulation is a clean that removes some triangles 
outside the polygon that are created during the triangulation.

Maybe you could dump the point data for Mexico.

You can also test triangulation here:
http://javascript.poly2tri.googlecode.com/hg/index.html

Think you even might be able to paste a svg path(see france preset) at this 
test page.

Original comment by thahlen@gmail.com on 12 May 2013 at 10:33

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

Thanks for your reply

I tried the test page; but the results are tiny on there, and zooming in seems 
to not allow for me to scroll across to look at the rendered geometry.  That 
said, I also did some post triangulate filtering of points outside the bounding 
box, and this left a much better result ; but still containing triangles that 
formed the external hull.

In this case I think you must be right about the method failing before fully 
cleaning up, but no exceptions are thrown so I guess I must investigate further,

I wlll keep looking :)

Original comment by danja_...@hotmail.co.uk on 12 May 2013 at 2:23

Attachments:

• Mexico.png

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

I don't know if this helps, I hav wireframed the render both with and without 
my bounding box post-filter, highlighting the border in red.  Would such 
triangles as fill the outside troughs (in the filtered inmage) be generated 
usually, and later removed?  If not then its prbably some quirk in the data 
that confuses the algorithm as to whether its filling inside tris.  Only 
speculation on my part to be honest.

Original comment by danja_...@hotmail.co.uk on 12 May 2013 at 4:24

Attachments:

• WireFrame.png
• WireFrameBoundingFiltered.png

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

OK, I found the problem, and it is nothing wrong inside the algorithm (btw i 
never assumed it was due to the level of correctly rendered shapes) and I found 
by reducing the number of points to different levels of detail in the bezier 
curves, there was a change in one area from correct to incorrect.  I looked at 
the data and found there was indeed a self intersection near this region, 
presumably corrected at higher detail levels.  Once adjusted, it worked at all 
details and I applied this to the previously affected regions producing the 
attached result.

So apologies to flag this up prematurely, the problem was indeed with the data 
and NOT the triangulation.  Thank you for your earlier reply and 
congratulations on a great library.

Thanks again,

Daniel

Original comment by danja_...@hotmail.co.uk on 12 May 2013 at 5:48

Attachments:

• Mexico.png

[GoogleCodeExporter]

Great that you found the problem and thanks. Always fun to see the lib getting 
used and liked ;)

Original comment by thahlen@gmail.com on 12 May 2013 at 8:42

• Changed state: Invalid

[GoogleCodeExporter]

Heres the final render, took a while to tweak some of the larger countries, the 
nordic fjrds and northern Canada hehe, but looking good :)

Feel free to use this image as an ad for this library because you don't get 
much more complex than a world map as far as triangulation is concerned, good 
job.

Original comment by danja_...@hotmail.co.uk on 13 May 2013 at 4:09

Attachments:

• [world map.png](https://storage.googleapis.com/google-code-attachments/poly2tri/issue-77/comment-10/world map.png)

[GoogleCodeExporter]

Nice :).

I actually did a triangulation of the countries myself as a test before 
poly2tri was released! Not using bezier curves just simple shape file polygons.

http://www.youtube.com/watch?v=Gdceq4fOIMY

Original comment by thahlen@gmail.com on 13 May 2013 at 12:03

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

Wow, that is really stunning!  If I had seen that before trying out a number of 
libraries I would have known to use poly2tri from the beginning.  That render 
really shows the power of the library and in spectacular style :) May I splash 
the poly2tri logo in my university presentation?  It will credit your work that 
way, and deservedly so.

The only issue I have currently is that the results are a new set of points 
(within the triangle structures) rater than indexing the input vertices.  
Unfortunately meaning I have to convert them twice, once for input into the 
algorithm and then marshaled back into a float array for OpenGL. A separate 
vertex buffer being required from the poly-line border.

It is the last day I work on this project and it is great to finally get the 
countries filled in, so much more clarity in the map.

I can only say thanks again, by far the simplest and most effective library I 
used.

Dan

Original comment by danja_...@hotmail.co.uk on 14 May 2013 at 2:00

[GoogleCodeExporter]

You can splash poly2tri as much as you like.

If I released poly2tri today I would have used an interface IPoint2 with two 
methods x() and y() and wrap the IPoint2 inside the TrianglePoint for even 
simpler use. This way anyone using the lib could just implement IPoint2 on 
their own datatype.

Anyways still need a new set of point objects due to the need of a specific 
data structure for the triangulation.

Maybe you could do something like this. Lets say you have your poly-line border 
vertexes in a buffer.

Create you own Point class:
public class MyPoint extends PolygonPoint

To this class you only add an int field called index. When you create the List 
of MyPoint, for each vertex add the index value which is the index to that 
point into the vertex buffer.

When done triangulation you can loop over the triangles and build and 
IndexBuffer with the index values inside MyPoint.

This way you can Bundle your VertexBuffer(ArrayBuffer) and the new 
IndexBuffer(ElementArrayBuffer) into a VertexArrayObject and use that when 
rendering. 

Does this approach help?

Original comment by thahlen@gmail.com on 14 May 2013 at 11:42

[GoogleCodeExporter]

Yes that approach seems entirely sensible.  I must admit I assumed the Point 
classes within the library to be sealed.  I will certainly look into this for 
optimizations and pass it on to those who may follow up the project next year.

Thank you for all your helpful comments and I look forward to an opportunity to 
work with the library again in the future.

Best regards,

Dan

Original comment by danja_...@hotmail.co.uk on 15 May 2013 at 3:35