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)
No comments:
Post a Comment