GIMP GSoC 2011 - Seamless Cloning Project - Technical Overview & Status

Recently, I was asked by email to help with the status of my GSoC (2011!) project. So before I say anything about that, let me explain a few things about my current situation.

For those of you who didn't figure it out already from the lack of activity on this website (and the lack of my activity on the web in general), due to my current real-life situation, I barely have any free time except for those few precious hours in the weekend in which I try to run my own life.

This means that my open-source activity went to a level which is not enough to do anything which requires long sessions (*cough* coding new stuff *cough*), and only translations of open source software are being kept in progress (very slowly, but they are being worked on and I'll commit them when I have enough material).

Now that I said that, and now that you know why I'm rather unresponsive by email/comments to this site, let us begin a technical overview of the project status. Note that this was originally written as an email, so I'll sometimes write as if I'm addressing someone specific in a conversation, and sometimes I talk in general (3rd person). Please ignore this inconsistency...

Technical Overview & Status

Proposal
Unfortunately, I failed to find the original proposal. However, you can find the proposal which I recorded in the GIMP wiki. The proposal is located here.

Papers
I'm listing them here, it will become clearer once you see the modules listing.

• The paper behind the seamless cloning algorithm: Coordinates for Instant Image Cloning
• Unfortunately, due to open source licensing issues and some other reasons, I had to implement myself an algorithm for creating fine triangular meshes.
• The algorithm I used (and implemented!) was the Delaunay Terminator, as described by Jonathan Richard Shewchuk in his paper Delaunay Refinement Algorithms for Triangular Mesh Generation.
• Some of the code was based on an existing library (poly2tri) which is in turn based on it's own papers

Modules
The project is divided into 3 main modules

• A library for creating fine triangular meshes - poly2tri-c
• The first part of this library is a C port of a library for creating Constrained Delaunay Triangulations, which are basically "nice" triangulations of existing outlines with/without holes.
  The original library is poly2tri, and the C port I wrote can be found in poly2tri-c's repository under the poly2tri-c/p2t folder
• The second part of this library is an implementation of the Delaunay Terminator algorithm for what we call a Delaunay Refinement.
• Delaunay Triangulations are triangulations which are considered "nice", meaning that most triangles are more or less of equal size, without too big or too small angles.
• Delaunay refinement is the process of taking a Constrained Delaunay Triangulation (which is not exactly Delaunay due to constraints such as outline that must be respected) and refining it by inserting more and more points. The process terminates when the resulting triangulation is almost Delaunay.
• The implementation of the algorithm above was made from scratch and in fact was the biggest part of the GSoC project (the assumption was that there was an existing open source library to do this. Apparently it wasn't so...)
• My implementation can be found in poly2tri-c's repository under the poly2tri-c/refine folder
• The third and final part of this library is an implementation of a triangular mesh render. The render basically takes a mesh created from the refinement process, a buffer to fill and a vertex-to-color function, and creates an image of the mesh in the specified resolution and size.
• This is another implementation from zero, although quite trivial and could probably be made more efficient
• The original article used OpenGL to do this rendering, resulting an ultra-fast renderer. Since the project was done when GIMP/GEGL were in an unclear state regarding usage of graphics hardware acceleration, it was done on the CPU purely which is much slower (yet still almost interactive - less than a second for rendering regular objects)
• My implementation can be found in poly2tri-c's repository under the poly2tri-c/render folder

• The second part of the project is a GEGL operation for doing the actual seamless-cloning operation.
• In brief, here is a description of the process (needed to understand the state of the code):
• Do a heavy preprocessing step for creating a fine triangular mesh from the outline of the pasted area
• Now, for each render attempt, compute the color differences between the edges of the paste and the background image, and use the previously created mesh to interpolate the differences in the colors along the entire area of the pasted image. Add the interpolated color differences on-top of the paste and you get a seamless pasting!
• The GEGL implementation of the operation can be found under gegl/operations/common/seamless-clone (in the soc-2011-seamless-clone branch):
• Files beginning with sc-* are part of a "shared library" with the code required to do seamless cloning
• This library is used using the GeglScContext object (sc-context.h) which manages a seamless cloning operation for a specified buffer to use as a paste.
• GeglScContext implements smart logic to notice when a paste doesn't change between rendering sessions (i.e. calls to the process function) in order to avoid re-doing the heavy preprocessing step
• Ideally, GIMP would use this "seamless cloning library" to implement seamless cloning with an internal op that does not need to do this check over and over, since the paste can't change when moving it on the canvas in the GIMP UI. However, currently gimp uses the GEGL op which is described below in a rather dumb way...
• This library even exposes a pkg-config file to be easily linked against later...
• seamless-clone.c implements gegl:seamless-clone - A simple seamless cloning operation using the above library.
• seamless-clone-compose.c implements gegl:seamless-clone-compose - A simple meta-op for GEGL that composes the seamless paste above a given background...
• Finally, in order to have the triangulation algorithm included, a copy of poly2tri-c is included under the libs directory of GEGL. This is since poly2tri-c has no package that can be installed and it was asked for so that developers won't need to download additional source code from more locations. This is not a desired situation, yet I'm unaware of any package owners for various Linux distributions which would be willing to help with distributing poly2tri-c as it's own package. If any such developer would be found, send them to me and I'll give them any access/help to the repositories (and I'll do any code modifications needed)

• A GIMP tool using the seamless cloning GEGL op
• The tool is a bit buggy in terms of refreshing the canvas (sometimes, artifacts are left when dragging the paste)
• Additionally, it is inefficient since it doesn't use the library directly and so it does the check of whether the paste buffer changes each time
• I'm not sure whether the errors regarding non-continuous pastes (with holes and/or composed of several unconnected parts) do find themselves into the GIMP UI in a proper way...

GIMP/GEGL TODO

• Make GIMP check for the presence of the seamless cloning operation on the startup of the tool
• Make GIMP use the library directly (and check for it's presence on compilation time)
• Conditional OpenGL for doing the rendering of the triangular mesh!
• Implementing the OpenGL rendering in poly2tri-c should be very easy for anyone knowing OpenGL. I'll do it if GIMP/GEGL accepts OpenGL (not OpenCL! That's different!) into the pipeline
• Fix the described bugs in the GIMP tool UI

Poly2tri-C TODO

• Code cleanup, prepare for distribution (I'll do that - it requires less coding then the GIMP stuff and does not require a long coding session - so I can do it on my short available time periods)

בלנדר בעברית? (Non-English post)

לפני למעלה משנה יצא לי לדבר בערוץ הצ'אט של בלנדר ישראל, כשהייתי סטודנט פוחז עם זמן פנוי.
בזמנו, אמרתי שבמידה ואני אמצא מספיק אנשים שירצו את בלנדר בעברית, אני מוכן לנסות להתחיל לתרגם אותו כמו שבזמנו תרגמתי חלקים מגימפ.

עבר די הרבה זמן מאז, ולאחרונה התחלתי לקבל מיילים מעוד ועוד אנשים שמבקשים את זה. ואני מאמין שהבטחות צריך לקיים... אז למען הסדר הטוב, הנה מה שהולך לקרות: בסוף השבוע הזה אני אנסה להגיע למצב שאני מקמפל את בלנדר ומריץ אותו עם מעט עברית. רק שצריך להגיד מספר דברים לגבי זה:

1. לפחות לפי ההערה בעמוד התרגום הרשמי, יש צורך שמפתח כלשהו יקמפל את בלנדר עם תמיכה בעברית בשביל שהתרגומים שלי יכנסו לשימוש. אני אנסה לקמפל את בלנדר בעצמי עד שזה יקרה, אך אני לא בטוח שיש לי מחשב מספיק חזק בשביל לעשות את זה (המחשב שלי בן 5 ואני מריץ בתוכו מכונה וירטואלית של לינוקס)
2. אין לי מושג מה רמת התמיכה של בלנדר כיום בשפות מימין לשמאל. על פניו מעמוד התרגום עושה רושם שיש, אך את זה נחכה ונראה
3. לאור העובדה שאני כרגע במקום שאליו מגיעים רוב הנערים הישראליים אחרי תיכון (במקרה שלי הייתה גם אוניברסיטה בדרך, אבל זה פרט שולי), אתם יכולים להבין ככל הנראה שזמן רב אין לי - אז ייקח זמן שתראו תוצאות מהותיות מהתרגום.
4. אחרון חביב - לגבי הרבה מהמונחים בגרפיקה בכלל, ובתלת מימד בפרט, אני לא מכיר הסכמה רחבה לגבי התרגום. אני כן מתכוון לבצע מספר חיפושים עבור תרגומים קיימים לפני שאני "ממציא" מונחים, אבל קיים סיכוי לא קטן שאני אצטרך להמציא מילים או לקחת מילים שרק האקדמיה ללשון מכירה...

 ואחרי כל מה שאמרתי - אין זו סיבה שלא תמשיכו לשלוח לי מיילים. אני אמרתי הרי שאם ימצאו 10-20 איש שרוצים את בלנדר בעברית, אני אנסה לראות מה אני יכול לעשות. עברנו את המספר הזה מזמן אך זה לא מזיק לקבל עוד מיילים של מוטיבציה.

אז בהצלחה, ואני באמת מקווה שיצא מזה משהו.
בברכת שנה טובה ושבת שלום,
ברק

נ.ב.
להלן מילון מונחים בסיסי, בהתאם לתרגומים שמצאתי. אני אציין מראש שחלקם ממש יפים, בעוד שאחרים מזעזעים אותי בתור מי שקודם בא מהרקע האנגלי ורק אז ראה את המונח העברי:

• Animation - הנפשה (האקדמיה)
• Diffuse (Reflection)
• החזרה פיזורית (האקדמיה)
• החזרה דיפוזית (האקדמיה, כניעה למונחים לועזיים)
• Edge - מקצוע (האקדמיה)
• Face - פאה (האקדמיה)
• Lighting - תאורה, הארה (האקדמיה)
• Material - חומר (האקדמיה)
• Mesh - ?
• יש תוכנות שמשתמשות ב"רשת". זה נשמע לי איום ונורא למרות שזה התרגום המתבקש
• אריג - מעניין, אם כי לא בטוח שהמונח במקום (w3dictionary)
• תשזורת - נפלא! אני תוהה אם עוד אנשים מסכימים על זה (w3dictionary)
• Particle - חלקיק (האקדמיה)
•  Render - ?
• צְלִימָה (ש"פ), צָלַם (פ') - מקורי, חביב, אבל ספק אם מישהו שלא מכיר יבין... (האקדמיה)
• עיבוד תמונה (ש"פ) - תרגום שמופיע בתוכנות קוד פתוח אחרות. בתור מי שבא מתחום של עיבוד תמונה (Image Processing) אני נאלץ להתנגד למונח הזה!
• רנדר (ש"ע), רינדור (פ') - הבריחה מלמצוא תרגום. יש סיכוי שאני אאלץ להשתמש בזה...
• Shading - הצללה (האקדמיה)
• Specular (Reflection)
• החזרה אספקלרית (האקדמיה)
• אם נתעלם רגע ממונחים אופטיים מדוייקים, הרי שהמשמעות שאנו רגילים לה בתוכנות גרפיקה תהיה כנראה "בוהק" או משהו בסגנון הזה
• Vertex - קודקוד (האקדמיה)
• Volume - נפח (האקדמיה)
• Volumetric - ?
• נפחי (האקדמיה)
• וולומטרי (האקדמיה, כניעה למונחים לועזיים)

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!

Very big steps towards finishing post GSoC (2011) work

It works!

An outline and it's refinement

If you have been tracking my blog, you saw that I was struggling in the last few weeks to implement a constrained delaunay refinement algorithm. It took ages, as I always encountered lack of available materials and/or programming bugs. But I'm here to say that it works now!
This implementation is in C# (easier to prototype algorithms than in C), and I will convert it to C later for usage with GIMP and the rest of the project. It's based on a paper by Jonathan Shewchuk: Delaunay Refinement Algorithms for Triangular Mesh Generation.

Now, what about the GEGL side of the project?
As you may have all heard, GIMP is progressing onwards to use GEGL as it's image processing core. My seamless clone tool is not different - it was written as a GEGL operation (meaning you can use it outside of GIMP, in your own programs!). The GEGL operation has received lots of work this week, including:

• Working in tiles instead of whole at once (reduces memory usage and makes it scalable for images as large as supported by GEGL)
• Bug Fixing and Compiler calming (making the warnings disappear)
• Removing code duplication

The op is pretty much done now! I will need to use the new triangulation algorithm (as mentioned above), but it should be transparent to the rest of the code.

Now, what about the GIMP side of the project?
Other than a bit nicer looking GUI for tuning some settings, it's already done since the summer.

Remaining TODO:

• Make the GEGL operation handle blank images to paste and images with very thin (1 pixel wide) areas. Also make it handle holes (I would probably warn about these and refuse to paste).
• Port the triangulation algorithm to C
• Also finally make it a standalone package...
• Improve a bit the GIMP user interface for the tool
• Bonuses:
• Implement an OpenGL and/or a OpenCL (I'm unfamiliar with openCL, and this op is actually very easy with OpenGL) version of the seamless clone operations, to speed things up even more.
• Code optimizations....

That's it for now. I'm off to bed...

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

Quicky Update on my Post-GSOC work

Some people at the GIMP irc said it's rather unwise I work on the post-gsoc work without comitting it to somewhere public. They are probably right :P
Therefor you can see updates on Poly2Tri-C - I'll be updating once in a while (starting from a minute ago). During the weekend, I reached a deep understanding of how wrong my implementation was for the triangulation algorithm because of a misunderstanding of some basic terms. I'm implementing a smaller algorithm (Rupert's algorithm) to see if I'm right now, and then I'll update the main algorithm.

Also, to my few readers: I don't always have enough time to respond to comments because I'm very busy in real life. If you feel it is important, you should be able to find my email on this site - feel free to email me for the important stuff!

And for all the people who celebrate it (like me!), Happy Purim! (Yes, I know it's only in 4 days, it's just that I probably won't get to this blog before the holiday)

Post-GSoC work, End(?) of University

I have done the seamless cloning project for GIMP and finished it in August. So, you may ask, why on earth is it not integrated yet? The answer is short and simple - last university semester combined with real life. But, I'm not here to bring excuses, I'm here to bring results:

• On Thursday I had my last university exam (Computational Complexity). Unless I fail, and I hope I don't, I finished university!
• In the last two weeks of university, I had more and more free time so I began working again on my GSoC project. The current things that are waiting to happen are:
• Fix the triangulation refinement implementation. For those who are not familiar with the algorithm behind the scene, the algorithm itself is based on interpolation of image differences in a triangular mesh. Therfor, it is a critical part.
  The algorithm currently would get stuck in an infinite loop of refining the triangulation, even though it was gauranteed to stop (meaning an implementation bug). I think I just fixed it now (now as in 5 minutes ago), more on this below.
• Make the algorithm iterate over tiles inside of allocating a big chunk of memory, and thus limiting the maximal image size for the algorithm.
• Fix memory leaks (there are several known leaks, and hopefully none unknown).
• Improve a small glitch on the borders of the image.
• Optimize the speed!
• Get it reviewed, and merge back to master.
• Being free of university, and free from other work (I have a day work on which I don't work "after-hours"), I'm now free from chores on evenings (if I get home at sane hours) and weekends. For the first time in the last 3.5 years, I really have free time with nothing on my mind. So don't worry, I'll get into GIMP :D

Now, before I get into details on my GSoC bug, a short "what's going on?".

• Last time I left the geometry library, I was completly stuck with no idea what was the bug.
• When I got to it again, I decided to re-write it in a language which is more type-safe (no pointer bugs), with less memory issues (garbage collection), and much easier to debug (no offense, but gdb isn't always ideal). Eventually I chose C# (and not Java, my favorite language) in order to learn a bit.
• I have been spending my free time between the exams, in the last two weekends, to re-write the library. The re-write was something like "look at the code and write it in a different language". Almost no structural changes or anything, so that I'll keep synced with the source.
• And then I found the bug...

Now for the bug, which made me like C much less than I did before:

// Relevant type declarations:
typedef enum
{
  INCIRCLE_ON,
  INCIRCLE_INSIDE,
  INCIRCLE_OUTSIDE
} P2tRInCircle;

// Types from GLib
typedef int  gint;
typedef gint gboolean;

// The function I called
P2tRInCircle p2tr_math_incircle (P2tRPoint* a,
                                 P2tRPoint* b,
                                 P2tRPoint* c,
                                 P2tRPoint* d);

// Somewhere in the code, in the function that I knew that
// was deeply related to the problem:
gboolean inside = p2tr_math_incircle (p, a, q, b);

if (inside)
  {
    ...
  }

I don't even feel like explaining this. It is so trivial (and if not, go learn C!) Other than feeling stupid silly for falling on such a bug for days of debugging, I don't have anything else I can say... So, with all the dislike of some people to high level languages, I like type safety. It saved my here simply since this code, when converted directly to C#, didn't compile and produce an error instead!

So, Hurray for C#, Hurray for end of University (hopefully) at least untill second degree, and just some other random hapiness. And don't worry, I'm not gone yet :)

Edit: More silly bugs found. I'm starting to like re-writing stuff - way better than debugging...
Edit 2 (February 11th, 2012): The geometry library works, at least in C#. Now it's time to re-implement in C.

Quick Update - NGtk

To those of you who have read my previous blog post regarding NGtk, here is a quick status update:

• NGtk works. Tested the XLib and NCurses backends on several linux distributions, and tested the WinApi backend on many versions of windows. I have a calculator app working with keyboard and mouse support.
• Keyboard focus is crappy, in all backends. Currently, I just tell all the widgets to listen to keyboard events. This is not something that is hard to fix - an hour or two.
• In backends with custom drawings (XLib, NCurses), the widget state isn't considered when drawing (so the widget looks the same all the time (if it's visible)). Not a bug, but could use some fixing. Base code for fixing that is already there.
• Clicking on disabled Widgets in the WinApi backend causes the mouse event to pass to the parent container (instead of being sent to /dev/null). Does anyone actually care about this? Can this do any harm? Anyway, the nice guys at Stackoverflow suggested a solution that should be easy to implement (but it's not top priority at the moment).
• Removing widgets from their container isn't tested well enough. That's not a bug, but I simply can't gaurantee good behaviour

Also, here are some good things:

• It works!
• It doesn't crash
• It doesn't leak memory (take that Gtk+!)
• Valgrind is generally happy
• Did I mention that it works? :P

I handed in NGtk to my proffessor, which means I'm now on my own with this project. Expect release 1.0 soon (my submission was titled 0.99). For those who want to take a look at the API usage already, you can take a look at the tester program: main.c (forgive me for the ugly macro in line 204, there is already a way around it in the code on my computer).

It is useable already (you can get the link to the project homepage from the main.c link), but I deeply recommend waiting for me to solve the above technical issues.

By the way, I did 40 km of bicycling in the city last friday (October 14th) in the Sovev Tel-Aviv event. It's the first time I participate, and I really enjoyed. Riding the bicycle on the busiest highways in the country and then along the sea shore together with other hundreds of people, is a great experience. So, if you can participate next year, I highly recommend that you do so ;)

Teaser: Project NGtk - Native Gui ToolKit

Recently, I wasn't exactly active in GIMP and other projects. The main reason for that is an open-source university project I am doing as part of my studies, in the course Advanced Topics in Operating Systems. I believe pictures can demonstrate better than words, so take a look:

Click on the image to view it in fullsize

Project NGtk is an extremly light-weight library for creating GUI's on different platforms. It includes the following features/concepts:

• Has support for the following widgets and events:
• Button (stable)
• Labels (stable)
• Text-Entries (stable on 2 of 3 platforms)
• Windows (stable)
• Mouse up/down/click events
• Keyboard key type events, with translation from key code to ascii
• Works on the following platforms:
• Windows - Uses native Windows widgets via the windows API.
  For this backend, the only dependancy is the windows libraries which already ship with Windows.
• Unix/Linux Terminal - Any terminal which NCurses works on (which should be most modern terminals). This means you can also use this via SSH without X11-forwarding! Unlike many curses applications, NGtk includes full support for mouse cursor in the terminal.
  For this backend, the only dependancy is NCurses, which is shipped with most (if not all) modern linux distributions. NCurses supports a large variety of terminals.
• Xlib - Any operating system which has an Xlib (X11) client library. This means graphical Linux/Unix work environments.
  The only dependancy for this backend is an Xlib implementation, which is shipped with all modern graphical Linux/Unix environments.
• Gtk+ wrapper - Support planned for near future. This will practically be a simple API wrapper to give API consistent with other NGtk backends.
• 30 KB for the core library + 30 KB for each "adapter" (backend library). Just for comparision, Gtk+-3 is approximatly 4 MB (130 times bigger), not including it's dependancies.
• Written in C
• Object-Oriented structure - NGtk uses a very small C object system that was written as part of this project to make it easy to rogram, and without requiring C++. The object system is easy to learn and well documented.
• Display "Resolution" Independant - Forget the term pixel, as it doesn't exist in NGtk. Since NGtk is meant for a wide amount of platforms, such as the terminal (where a the smallest unit, a "pixel", can actually be a whole letter), NGtk will handle sizing of widgets itself. You can specify logic layouts, but no need to actually specify a size for widgets. There is a built-in interface for accepting custom made layouts (anything from grids, relative sizings, etc.), and writing new layouts is easy.

As you can see, NGtk doesn't have any real dependancy - the only dependancy it has is the existance of the graphical system that you wish to use. It is also not a replacement for Gtk+/Qt/etc. - it's targetted only at people who want very light-weight GUIs (both in features and in actual library disk size), and want to acheive maximal support. The NGtk goal is to achieve a state where every platform with a compiler will have an NGtk backend that will work on it without requiring any library which isn't already on the platform.

The first stable release of NGtk will happen this week when I hand in the project to my university. You can already find the project source by googling it, but I do recommend waiting for the official stable release.

Regarding my GSoC project: no I haven't forgotten. It won't make it in time for 2.8, but I will work on it as soon as I can hand in NGtk to my proffessor. Sorry to disappoint the people who wanted to see it soon, but it just won't happen...

Saving Vertical space in GNOME 3 (Especially for Firefox)

I have been using GNOME 3 for more than a week now. I really like it, and after tweaking my desktop back to show the files and launchers (like in GNOME 2) I really felt at home.

However, not everything is great with GNOME 3. One of the most irritating features of it, is the gigantic titlebar of windows. I actually like gigantic titlebars, but not when I need to maximize my working area. The web is full of people complaining "Why Firefox on Linux can't be space efficient as it is on Windows 7?" This is even more critical when in the fallback mode, you have two very thick panels that also take additional vertical space (I switch between fallback and regular all the time because of some hardware limitations).

Comparision between Firefox titlebar on Windows 7 and GNOME 3 (fullsize)

 As you can see, the Windows 7 setup takes much less space, by combining the titlebar with the tab area. Very neat!

Anyway, I'm here to say that you can make Firefox on Linux thinner. I'm not talking about fullscreen mode in firefox - since I do like seeing my tabs and toolbars (Which firefox hides in fulscreen mode).

In Linux, windows are displayed and managed using a special program called a Window Manager. We are going to request the window manager to display Firefox in full-screen. This is different from firefox's built-in full-screen mode! In the full-screen mode created by the window manager, Firefox will continue to show it's tabs and toolbars like before, but it's titlebar will be gone and it will fill the area that was used by the gnome panels!

1. Open the System Settings dialog (in fallback mode, it's in Applications → System Tools) and Choose Keyboard. (Screenshot)
2. Switch to the Shortcuts tab and choose Windows from the options on the side. (Screenshot)
3. Find the Toggle fullscreen mode option, and assign a new keyboard shortcut which is easy to remember (I used Ctrl+Alt+F). To assign a new shortcut, click on the area which displays the shortcut (it displays Disabled if no shortcut is set) and type the desired key combination.

Now, whenever you open Firefox (or any other program that needs more vertical space, without sacrificing any toolbars that disappear in the built-in fullscreen mode of that program) simply type the shortcut from above to go fullscreen! Type again to get out of the full-screen mode.
You are going to miss the close/un-maximize/minimize buttons in fullscreen mode. However, you can probably live without them (or if you like keyboard shortcuts, configure some for these also!) when working in fullscreen.

That's it, I hope it helps those of you who need to use more height of their screen and don't like the built-in fullscreen modes (if any) of their programs. If anyone knows any better way (especially for Firefox on GNOME 3), please leave a comment :)

Video demo of my GSoC project

[If you are reading this from RSS, you may not be able to see the video. Click here to see it]

[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.

Open Devhelp books installed in unusual locations

If you are a GNOME developer, there are high chances you encountered this problem - you install your beta versions to a seperate prefix (something like /opt/my-beta instead of the regular /usr), and then when you come to browse their documentation in Devhelp, it fails to find them. Some will be tempted to sudo, and then symlink the documentation to /usr/share/gtk-doc. Personally, I'm not a fan of sudo-ing and messing around...

Today I had enough of this, and decided I'm going to solve this. A quick search in the Devhelp source code found the code that searches for books. The book_manager_add_books_in_data_dir () function searches SOME_PREFIX/gtk-doc/html for Devhelp books, and it's called from dh_book_manager_populate () with the directories returned by g_get_user_data_dir () and by g_get_system_data_dirs ().

Thanks to some help from Mikachu (from #gimp irc), which matched the much longer description on the freedesktop basedir-specs, I found out that appending a directory to the environment variable $XDG_DATA_DIRS is enough to make Devhelp search for documentation there.

Sweet! That was much easier than I thought it would be :D

So to summarize, this is what you do:

1. Compile your program, while setting the installation prefix to some prefix $PREFIX
2. Build and install it (make and make install)
3. Find your installed gtk-doc documentation. Usually it is located on $PREFIX/share/gtk-doc/html/YOUR_PROGRAM. Make sure that directory contains a file with the suffix of .devhelp.
4. Set the $XDG_DATA_DIRS environment variables, and prepend (don't append!) that directory (usually $PREFIX/share) to that variable. In bash syntax, you should type
   export XDG_DATA_DIRS=$PREFIX/share/:$XDG_DATA_DIRS

Why prepend and not append? Well, apparently Devhelp doesn't seem to like having two books with the same title, so it takes the first one it finds... Since it follows the directories in that environment variables by their order, it means that we should add our directory to the begining of the search path.

Note that this method has 2 cons:

1. You can't view previous versions of the documentation, since as I said Devhelp takes only the first version it finds
2. You must launch Devhelp with the above environment variable set. So either lunch it from your build console, or create a script to modify the variable and then lunch Devhelp. Note that IDEs that launch Devhelp (like anjuta, and gedit with plugins) must have the variable set for themselves (by launching them with the variable set already).

So, it's not perfect. But way better that symlinking stuff into the /usr/share/gtk-doc directory. This also shows why open source is so good - "If you don't like it, fix it!". Or as I prefer to say "If you don't like it, hack it" :D

QuickBox–A quick point-in-triangle test, and an example of how algorithm descriptions matter!

In this blog post I'm going to post something which is rather unrelated to my usual topics. I'm going to talk about how can minor changes in concept when coding, can have dramatic impact on your code performance. I also introduce a technique that I “developed myself” while coding the problem. When I say “developed myself”, I mean that I actually took time to code all the ways people describe the problem’s solution – although all seem very similar, the performance difference is huge.

While working on my GSoC project, I needed a fast predicate to check if a point is inside a polygon (specifically, a triangle). The test doesn't have to be accurate, but it must be sound in the sense that when it states a point is outside, then it must be outside. To do so, I decided to use bounding box testing - see if the point is in the bounding box of the polygon. Computing the bounding box of a group of points should be easy - just keep track of minimal and maximal X and Y and you should be done. So, how much can you screw it up?

Well, apparently, you can screw pretty damn hard. By coding without thinking, you can make this twice as inefficient without even noticing! Thinking before you code, to try and merge cases, can apparently be very productive. My solution will be referred to through this post as the QuickBox solution.

Explanation

The QuickBox test uses an improved version of a common idea. The usual checks see if in a point, one of it's components is larger/smaller than the matching component in all of the triangle's points. The implementation here takes this one step further, under the assumption we are willing to say that a triangle made of 3 collinear points contains no point at all (not even it's own points). This is fair for most triangulation libraries, that simply don't accept such triangles.

The idea is like this: If all the points of the triangle have the same boolean result for testing order (using <=) against a component of the point (for all i, Pt[i].x <= P.x is the same) then the following cases are possible:

• All have the same value of the component. But then all the points of the triangle are collinear so it's practically empty!
• All triangles points have the component larger than the tested point. So the point is outside!

• All triangles points have the component smaller than the tested point. So the point is outside!

Note that principle explained above is also applicable for polygons with more than 3 vertices.

Implementation Analysis

Let the points of the triangle be A, B and C. Let P be the point we are testing.

Naïve implementation

This is what people would usually do if they translate directly the description “See if all polygon points are on one side of the input point (check that for each side)”

Compute:

((Ax <= Px) && (Bx <= Px) && (Cx <= Px)) ||
((Ax >= Px) && (Bx >= Px) && (Cx >= Px)) ||
((Ay <= Py) && (By <= Py) && (Cy <= Py)) ||
((Ay >= Py) && (By >= Py) && (Cy >= Py))

Total Cost: 12 double boolean operations, 11 binary boolean operations

Border implementation

This is what people would usually do if they translate directly the description “Find the the border on each side of the box, see if the point is beyond it”

           ABx           ACx                       BCx
xMin := (Ax <= Bx) ? ((Ax <= Cx) ? Ax : Cx)) : ((Bx <= Cx) ? Bx : Cx))
yMin := (Ay <= By) ? ((Ay <= Cy) ? Ay : Cy)) : ((By <= Cy) ? By : Cy))
           ABy           ACy                       BCy

// OPTION 1 - Requires computing all of ABx, ACx, BCx, ABy, ACy, BCy
xMax := (! ABx) ? ((! ACx) ? Ax : Cx)) : ((! BCx) ? Bx : Cx))
yMax := (! ABy) ? ((! ACy) ? Ay : Cy)) : ((! BCy) ? By : Cy))

// OPTION 2
xMax := (Ax >= Bx) ? ((Ax >= Cx) ? Ax : Cx)) : ((Bx >= Cx) ? Bx : Cx))
yMax := (Ay >= By) ? ((Ay >= Cy) ? Ay : Cy)) : ((By >= Cy) ? By : Cy))

Compute:    Px <= xMin || Px >= xMax || Py <= yMin || Py >= yMax

I'll assume that a trenary op is just one boolean operation and I will also ignore the need to save the values computed in the process such as ABx, etc. And even with that is still costs a lot!

Total Cost:

• Option 1: 6+4 double boolean operations, 15 binary boolean operations. Actually, this method is rather inefficient, unless binary boolean operations are much much cheaper than double ones.
  
• Option 2: 8+4 double boolean operations, 11 binary boolean operations. Exactly the same as the naïve method!

Note: separating the computation to one coordinate a time, can cut memory consumption by half.

QuickBox implementation, This is my method!

This is what people would usually do if they translate directly the description - “See if the point is on the same side of all the polygon-points”

xPBorder := Bx <= Px 
yPBorder := By <= Py


Compute: (((Ax <= Px) == xPBorder) && ((C->x <= Px) == xPBorder)) || 
         (((Ay <= Py) == yPBorder) && ((C->y <= Py) == yPBorder))

Total Cost: 6 double boolean operations (7 if we can’t save values (not 8! see below)), 7 binary boolean operations.

Note that you can expand this to polygons of much more vertices, using the trick above to avoid repeating computations, while keeping with only 1 variables which is neat :) Work on one coordinate (component each time) and keep an accumulating variable that after it’s initialized with the first comparison, you just compare to it! When done with that coordinate, if indeed you found no proof that it’s outside, pass on to the next coordinate and repeat.

Conclusions

It’s pretty easy to see that the QuickBox method beats the hell out of the competition! Less memory, less computations, and all because we checked “all points are on the same side” and not “all points are on one side” (and checked that for each side). So, when someone tells you how to implement an algorithm, try to rephrase his sentence. It can be critical!

Just some context about this post - I’m implementing a geometric algorithm that was given in 55 lines of pseudo code with ambiguous meanings. After passing 2500 lines of implementation (real C code), and after having to actually add many cases which were dealt with because the algorithm was phrased ambiguously enough with no hint to these cases, I started being very picky about how people describe their algorithms :P I spent 1.5 months of my GSoC on this, which is way more than I expected.

So do us all a favor – if you know how something works, describe it exactly and clearly, so other people can implement it correctly and efficiently. It’s preferable to have 100 lines of code that are readable in 15 minutes, instead of 15 lines of pseudo code which are quickly read but take a 100 minutes to understand! (But don’t over-do it! Bombarding with details will make people like me fall asleep when they read your article…)

[Final note: I don’t have any criticism at the original article author – he did explain it so that people from the field would understand (and eventually, even I understood so it shows he did his job very well). I just came from a different field since this is a side dependency of my project, and not it’s main part… This simply made me aware of how much phrasing of an algorithm can change it’s implementation for people who don’t think exactly like you]