More progress on poly2tri, Solutions to Linguistic Problems

Time for another update on the GSoC project:

My C port of Poly2Tri (part of my Google summer of code project, see my previous post(s)) has received much work in the last weekend and things start to look pretty good.

One of the problems I had was an incorrect understanding of what is an encroached edge. As someone who don't speak English natively, in university I heard many different (non-English) terms to describe edges and vertices in graph, since it's not really formalized what terms should be used in my language.

When I first came to read about Delaunay Refinement for generating a triangular mesh from an outline, I was sure that the following terms (marked in bold) are used freely without some rules (meaning you can use each one of them to express the same common meaning as the others):

• Edge - Used to describe a connection between two points(/vertices/nodes) in a Mathematical Graph and also used to describe one of the three lines which from a triangle. This term is used in triangles simple because triangular meshes are indeed a form of a graph.
• Segment - Used to describe a straight line between two points of a PSLG.
• Sub-Segment - The result of splitting a Segment into smaller parts (this happens during the refinement of the mesh produced from the outlines described by the PSLG).
  

This confusion is  partially because I haven't deeply understood the concept of Constrained Delaunay Triangulation. Basically, the source of confusion was lingual, due to conflicting terms in my native language (Hebrew) - there are several words used to describe these terms, and the people who use them aren't always exactly consistent in their usage. Anyway, I believe I got it more or less right now - I read all the material in English from scratch, and now I understand the differences between all the three terms above.

And a small teaser - I needed to test if I can detect which points are "visible" from a triangle (to test whether an edge is encroached). To do so I wrote a small and quick algorithm, and here is the demo app I wrote to test it:

Another good announcement is that I have been receiving help from my partner in lots of my university coding assignments, and he has worked on the part which is relevant for the GIMP/GEGL side of the project - a better outline finding algorithm. The current algorithm would crash/freeze on selections with thin areas and randomly in some other cases.

His algorithm finds outlines for every BW image, and it builds an hierarchy of them (so that outlines which actually represent black holes inside of white areas would be associated with the white outline as child outlines). His algorithm also returns points with locations which have sub-pixel accuracy, to prevent the problem that the current algorithm has with thin areas (thin lines would cause a pixel to be marked twice as an edge pixel - one time for each direction that we go around it. This would crash some parts of the library).

I still haven't integrated it or looked at the code, but he showed me the outcomes and they look pretty awesome. You'll hear more on that as soon as I get to work on it.

That's all for now. Stay tuned for more ;)