Trying all my GSoC projects (seamless clone, triangulation)

It's about time I post this. My work is actually useable enough (I even received my first bug report by email recently) so it's the time to explain how to use this.

In this post I will explain you how to compile Poly2tri-C (the triangulation and mesh generation library), how to compile GEGL with the seamless cloning operation and GIMP with the seamless clone tool.

Ready? Then let us begin!

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 ;)

[GSoC-2011] Final Results and How to Try

I am very glad to announce that I now officially passed the Google-Summer-of-Code 2011 :) The email from Google arrived in the last few days, and the official Google announcements on the GSoC results (of all projects) are supposed to be published tomorrow.

S/He is eyeing you :)
Sources: background, paste

Now, it’s time to publish the instructions on how to get and try it for the people who want to test it. There are some known bugs, and probably some unknown bugs, so be warned.

Compilation and Set-Up Instructions

1. You should know how to build of GIMP and GEGL from Git. A partially outdated guide is available here, and some things are explained in more depth here.
2. Instead of building the GEGL master (main) branch, switch to the soc-2011-seamless-clone branch. You can do this by running git checkout soc-2011-seamless-clone. Compile it with the regular flags – nothing special is needed.
3. After building the updated version of GEGL, it’s time to build the updated version of GIMP. Switch to the soc-2011-seamless-clone2 branch, and build it.
4. Before running GIMP, you must set the environment variable p2t_refine_steps to some number defining the maximal amount of points to be used in the mesh (in plain English, more should theoretically produce better result). I know this is annoying, I will get rid of it as soon as I finish debugging a certain code part. The typical number I use is 500 for pastes of around 200x200 pixels, and you should probably increase it if you wish to work on large pastes. If you are using the bash terminal, do export p2t_refine_steps=500 (and change the number as you wish)
5. Run GIMP.

Usage Instructions

Basically, you can just try copying a part, selecting the Seamless Clone tool (Shift+L) and clicking anywhere on the image to start the tool’s interaction. Click Enter to apply the final result. If this doesn’t work (and/or crash), then the instructions below are for you.

1. Run Gimp :)
2. Open the image that you wish to use as the background, and open the image you wish to paste into the background. Copy the part you want to paste. Note that opacity of that part will be treated as if it was binary – parts under 50% opacity will be removed, parts of more than 50% opacity will be completely opaque. The shape can be any shape, as long as it follows the following rules:
1. It must not have holes (Temporary limitation)
2. It must be continuous, i.e. composed of only one part (Temporary(?) limitation)
3. It must not have any long thin areas (Temporary(!) limitation).
   This means that if you have any area which is 1 pixel wide and is 3 pixels long or more (i.e. a thin spike), it will crash. Solution for this was already devised, I just need to code it. Select the Seamless-Clone Tool (Either by clicking the second tool on the toolbox that has the same icon as the move tool, or by doing Shift+L).
3. Click anywhere on the canvas while the background layer is active. The paste will be centered on the cursor, and so the cursor should be in a place where the entire paste is inside the background boundaries (both inside the rectangle defining the layer, and inside an area where all the background below it is opaque). This limitation will be enforced by the User Interface later.
4. Move the paste by clicking on it, dragging and releasing. If you move it slow enough (which actually shouldn’t be so slow), you’ll see the preview updating while you are moving.
5. Click Enter to Apply the effect.

Known Bugs

• All the above mentioned crashes and bugs :)
• Due to not yet complete memory management, the tool leaks memory from it’s preprocessing.
• Converting to tile-based processing is NOT 100% done, so it may crash on large pastes. Don’t ask me how large since I didn’t try anything more than 300x300 on my machine.

Other TODO’s

• Integrate the tool with the help system
• Test better the interaction when the the active image/display/drawable are switched during the interaction of the tool.
• Get a decent tool icon. Anyone with ideas for the visual metaphor to be used by a seamless paste tool, is more than welcome to leave them here as comments! I do design icons, but I don’t have an idea for this one.

GSoC 2011 - (Almost) Final results and thanks!

The end of Google Summer of Code 2011 is near, and I have failed to post enough updates on my blog. But that does not mean one bit that I failed to make progress. I'm proud to present you with my results:


Result, using my GIMP tool :D

The image to paste (source)

The image to paste into (source)
Licensed under Creative Commons Attribution-Share Alike 3.0 Unported

My tool allows you to move the paste on the image and see it update according to it's environment, so that it will paste seamlessly. It's not real-time yet, since I recompute some values that should be cached everytime, but most work to enable caching is done, and I hope to reach that before the final deadline. (Even if it won't be before the deadline, I will do it even after GSoC ends).

This is also the time to thanks all the people who made this possible:

• The authors of the Coordinates for Seamless Cloning article, who developed this algorithm.
• Prof. Daniel Cohen-Or, the professor who taught me computer graphics at the university, and helped me understanding the article (he is also one of the article authors).
• My GSoC mentor, Michael Natterer (aka mitch), who agreed to mentor me and assisted me when I was stuck.
• Mason Green, the original author of the poly2tri library, which was heavily used in the project for computing interpolation meshes. I would have never reached the project deadline without his amazing library.
• Prof. Jonathan Richard Shewchuk, who developed some of the geometrical algorithms that were used in this project.
• Finally, special thanks to all the great guys on the GIMP and GEGL irc who helped a lot - mitch, Bat`O, pippin, Alexia_Death, Mikachu, and more.

[GSoC-2011] Bi-Weekly update #1

Hi!

After seeing enough student post of weekly updates, I decided that I should probably also give some progress report. I finished porting the poly2tri library to C! My C port can be found here.

Just compiled it today with gcc and not g++, and it feels great to see it working. And when I say to see, I mean that I created an SVG output tester so that you can see it in any modern browser :D
I still have some optimizations that can be done, including maybe some more documentation of the C api (especially for the constructor-destructor conversion from C++ to C), but it's usable enough for the GSoC as it is. Note that most API changes were simply from p2t::SomeClass::GetFoo to p2t_someclass_get_foo (where the object itself was added as a first parameter of the functions).
It was in "almost C" state on wednesday, but then memory leaks happened (solved with valgrind) and some stupid compilation errors...

At the weekend I went to a short vacation on the dead-sea (pictures soon!) and I had 4 people to discuss Chew's second algorithm (which I should implement next) with during the long ride to the hotel. So hopefully with their help it should be quick(er).

That's all for today :)