LibreOffice CorelDraw Import filter - don't despise the humble beginnings

You might still remember some of my blogs about our new and shiny MS Visio import filter in the upcoming LibreOffice 3.5.0.

But what about 3.6.0? Is it going to be an exciting version too? Well, the answer depends on what kind of things excite you generally, but for sure, there will be a lot of goodness as usual to make the best free office suite even better.

In my free time, I have been working for some time already on the next graphics import filter for LibreOffice. This time it will be a CorelDraw import filter. The horse-power is a library, libcdr. In the same way as libvisio, libcdr reuses the API of libwpg and thus is easily pluggable into LibreOffice reusing all the ODG generator classes of the current writerperfect module. The importer is currently part of the git master tree.

You might be already shouting: "Where are the screenshots?" I know that a picture speaks louder then hundred words, and so here you are served:

Simple and more complex shapes in CorelDraw 7

The same shapes imported into LibreOffice Draw.

As you can see, it is an initial implementation, which cannot but get better. If you want to participate in this adventure, you can drop around at our IRC channel #libreoffice-dev channel at irc.freenode.net where a community of smart and friendly developers can direct you.

Stay tuned for more nice pictures as this project advances.

FOSDEM 2012 - How to make the best of it and become LibreOffice developer

FOSDEM 2012 is just round the corner and, as you might know, LibreOffice will have a DevRoom this year too. And, as it was already publicized, your servant and Eilidh McAdam of libvisio fame will attend too. The goal of this event will be to help you to become a LibreOffice developer, by helping you to get your first contact with the code from inside.

How to prepare for the event?

In order to give as many community members the possibility to speak, the presentations will not take more then 15 minutes each. But we will be there for one-to-one contacts and hacking goodness. If you are interested in contributing to our new Visio import filter, or the upcomming Corel Draw and MS Publisher filters, here is what you can do:

1. Find a bug that is bothering you in the current Visio import filter, or some simple feature that the importer currently does not support
2. Check out the following libraries:
   • master branch of libwpd (git clone git://libwpd.git.sourceforge.net/gitroot/libwpd/libwpd)
   • STABLE-0-2-0 branch of libwpg (git clone -b STABLE-0-2-0 git://libwpg.git.sourceforge.net/gitroot/libwpg/libwpg)
   • master branch of libwps (git clone git://libwps.git.sourceforge.net/gitroot/libwps/libwps)
   • master branch of libvisio (git clone git://anongit.freedesktop.org/libreoffice/contrib/libvisio), and
   • master branch of libcdr (git clone git://anongit.freedesktop.org/libreoffice/libcdr)
3. Build them as system libraries and install them in the same order.
4. Then build LibreOffice according to these instructions. The important thing is to use those system libraries that you just built. To do so, be sure you added to the configure flags
   • --with-system-liwpd
   • --with-system-libwpg
   • --with-system-libwps
   • --with-system-libvisio
   • --with-system-libcdr

With this kind of build, you will be ready to make the most from your Brussels weekend. Nevetheless, you can drop around at our IRC channel #libreoffice-dev channel at irc.freenode.net for more information and ideas.

Starting to do it instead of planning to do it ...

... is the best way to enter the FOSS development. That is why your servant and Eilidh will be around to hold your hand with debugging and finding way to implement your favourite features. We will answer your questions about the library design. We will point you to the place in the code where your bug might linger. And for more complicated stuff, we will debug it with you.

Don't expect us to give you a fish, but we will certainly teach you how to catch it by yourself. And in the same token, you will become a contributor inside a community of smart people that is fun to hang and hack with.

See you in Brussels the 4^th and 5^th of February 2012.

Take a decision to enter FOSS in 2012

So, the year changed again and with it come quite often new decisions. Some swear to work out the superfluous kilos, pounds, or whatever standardized measure your country uses, gained too fast during the festivals. If it is your decision, it is for sure good for your body and I wish you success that goes beyond the act of subscribing to a local gym (and never appearing there after first month).

But this could be also a nice time to take a decision that you were procrastinating with for too long. That one is good for your intellect and programming skills (even though you don't consider yourself a programmer yet). What about starting to contribute to a Free and Open Source Software project (FOSS)?

Sounds interesting? So I have one for your. It is having a big and growing community. It can accomodate all levels of skills. And the impact you will have is multiplied by the wide addoption of the product itself.

Well, you must have guessed right by now. I am speaking about the LibreOffice project, your natural entry point into the marvelous world of the FOSS.

Whether you are expert or beginner programmer or C++ is sounding Chinese Traditional for you, just find a way to join channel #libreoffice-dev channel at irc.freenode.net in order to meet other developers and visit our Easy Hacks for ideas where to start.

I promis you that a year from now, you will not regret that you have started. Although, it is quite probable that you will pour a tear over an unused year-pass from the local gym.

7th ODF Plugfest in Gouda

For those that might care, your servant will be attending this week the ODF Plugfest #7 in Gouda (Netherlands).

I will have on Friday a short presentation of the best free and open source library for parsing Microsoft Visio Documents. The other exciting thing is that after more then 6 years of common collaboration I will get to meet personally one of my libwpd co-maintainers, Johannes Marcus Maurer also know as "uwog".

What an exciting time before us!!!

LibreOffice Visio Import filter: the goodness soon on your desktop

It has been a long time since I last time blogged about the LibreOffice Visio import filter. My silence did not prevent a pretty cool code from falling gradually into our git repository. To the point where now we are working on the last 5% of features that normally take the 95% of development time. But, let us see what happened since my July blog:

First of all, Eilidh was busy as a bee and, in the second half of the Google Summer of Code, implemented support of stylesheets, stencils and basic text. She also debugged and fixed quite a number of imperfections that Valek found. Frankly speaking, this Google Summer of Code was by far the best from my point of view. We managed to achieve a very good fidelity of import only in about 3 and half months. Impressive.

During the LibreOffice HackFest weekend in Munich, I had a time to add a support for uniform splines in libvisio and to implement the actual import in text on the side of LibreOffice.

The next highlight was the fact that the whole team met in Paris during the LibreOffice Conference 2011. It was delight to meet in person Valek and Eilidh. There is even a photo witnessing this meeting:

Valek, me and Eilidh from left to right

This conference was not only an occasion to know each other a bit better, but also to improve and add some new features to libvisio. During boring parties full of non-developer talk, we withdrew with Eilidh to some corner and improved together the text import: paragraph and span properties, text box properties, etc. Later on, Eilidh added initial support for line markers (aka arrows). Recently we implemented emulation of the last Visio primitive that we did not handle before - Infinite Line.

For those that have big piles of Visio documents on their disks, but cannot read on their favourite Linux distribution: Your pain is coming to an end. The LibreOffice Visio Import filter will be part of LibreOffice 3.5 release, which will be the next major release early next year.

And since images speak louder then thousands of words, here are some pics to illustrate our achievements:

OrgChart.vsd in Visio		OrgChart.vsd in Draw
				You can see the achievement by comparing with the pictures from my June blog

DNetwork.vsd in Visio		DNetwork.vsd in Draw
				Compare with the picture from this libregraphicsworld.org article.

Calendar.vsd in Visio		Calendar.vsd in Draw
				This picture shows a good mix of the complicated features like stencils with NURBS, text fields, gradients, stencil text, etc.

If you are impatient and cannot wait anymore, just grab one of the daily builds uploaded by our tinderboxes here and enjoy all that goodness on your own.

LibreOffice Visio import filter on libregraphicsworld.org

For those that could be interested in my shameless self-promotion, there is some news about the LibreOffice Visio import filter at libregraphicsworld.org web site, accompanied by a fine interview with two fine hackers. So, click and enjoy the wonderful screenshots in a preview of the happiness LibreOffice 3.5 will bring you.

LibreOffice Visio import filter - round shapes are beautiful

Some might be wondering why the Visio import filter project is so quiet. But the answer is easy: we were busy as bees adding new features.

You might remember my blog about the bounding box of an elliptical arc. It is because Eilidh added the support of elliptical arcs into libvisio. And then we discovered that LibreOffice did not support elliptical arcs in the path at all, just ignored them. Fortunately, there was this patch of a hacker extraordinaire, Thorsten that was used to teach LibreOffice some sane behaviour.

Eilidh implemented further the conversion of gradient fill and with this and the support of elliptical arcs, this Visio document:

looks in Draw pretty well:

You will realize that we do not support text in Visio documents yet, but be assured that it is now our top priority feature. It is also worthy to note that the above-mentionned document is actually a document in Visio file-format 6 (used by Visio 2000 and Visio XP). We refactored libvisio the way that our support of both version 6 and 11 is equivalent. Moreover, we implemented two-pass parsing of Visio documents which allows us to draw shapes in a correct order and position them accurately.

In the same line, Eilidh implemented reading of NURBS, which is pretty tedious since the conversion must be done by approximation, since neither ODF, nor SVG support this kind of non-uniform rational basis splines. For the while, we are approximating them with 50 lineto segments for one spline, but it is our intention to use a serie of smooth cubic splines to achieve as much visual similarity as possible.

The libvisio library now is able to position correctly any point even if it is in a rotated shape that is part of a group rotated differently, which also might be part of another group with a diferent transformation. This allows us to load this Visio document:

in Draw this way:

You can see some graphic problems. The missing shapes are polylines that we will very soon correctly support. Nevertheless, this could be another one of my "we all love ODF, but ..." blogs, because some of the visual glitches are given by the fact that OpenDocument Graphics (ODG) file-format is suboptimal for representing more complex drawings. One is not even able to specify fill-rules or rules of polygon clipping. Clerly, this SVG inside XHTML version, converted using the vsd2xhtml tool, that is part of the libvisio library, is much closer to the original:

So, a bottom line is that the project is well alive and kicking. We even tagged the second alpha release and the tarball is now what LibreOffice master build is using. So, if you build your LibreOffice yourself, you will be able to enjoy the fruits of the work or Eilidh's hands and — why not — even start to contribute to this cool and interesting project.

Stay tuned for more news soon ...

Bounding Box of an SVG Elliptical Arc

We all love ODF, the best and the most vendor-neutral file-format in the Universe and its surroundings. But for sure, we have some spots where we would prefer it to be somehow less cumbersome. My favourite spot is the need to compute the bounding box of the path element when one writes the draw:path into an OpenDocument Graphics file. Without proper svg:x, svg:y, svg:height, svg:width and svg:viewBox values the path will not be correctly placed.

Computing bounding boxes is not so complicated work when everything is a polygon (which is the case in the internal model of basegfx module), but it becomes a bit more complicated if an application wants to generate paths including elliptical arcs.

I hit this problem about a year ago when I was working during my hackweek on an improvement of libwpg. I tried first to implement the bounding box of an elliptical arc the lazy hacker way, by googling for what other people did. And to my surprise, there is a huge vacuum in what concerns computation of a bounding box of the "A" element of an SVG path. So, I settled for the lazy hacker's plan B: I abandoned the idea by saying I will handle it later, in the first moment, and by implementing a suboptimal solution in the second time. But, since Eilidh did some spectacular progress last week in handling elliptic arcs, my lazyness became the bottle-neck of the progress. So, it was time to remember those nice times when I was warming the benches of the University, dust off my knowledge of mathematical analysis and analytical algebra (or the lack thereof), and try to compute the bounding box of an elliptical arc myself.

And for the purpose of people that might be as lazy as me, I decided to fight my lazyness the second time to give Uncle Google the opportunity to spit out something meaningful, when someone asks it about "Bounding box of an elliptical arc". Here are the notes:

Compute extremes using parametric description of ellipse

Let us start from this parametric description of an ellipse:

x(theta) = cx + rx*cos(theta)*cos(phi) - ry*sin(theta)*sin(phi)
y(theta) = cy + rx*cos(theta)*sin(phi) + ry*sin(theta)*cos(phi)

where cx and cy are the coordinates of the centre of the ellipse, rx and ry are the radii and phi is the x-axis-rotation.

To compute the bounding box of the whole ellipse we need to find for which value of theta the above mentioned functions reach the local extremes. It means where the first derivatives of x and y according to theta are zero. We will get this two equations:

0 = -rx*sin(theta)*cos(phi) - ry*cos(theta)*sin(phi)
0 = -rx*sin(theta)*sin(phi) - ry*cos(theta)*cos(phi)

which give us two solutions for x:

theta = -atan(ry*tan(phi)/rx) and theta = M_PI -atan(ry*tan(phi)/rx)

and two solutions for y:

theta = atan(ry/(tan(phi)*rx)) and theta = M_PI + atan(ry/(tan(phi)*rx))

Compute the center of the ellipse

Since we know now the values of theta describing the extremes of our ellipse, we can compute the x and y values of the bounding box of the whole ellipse. Just to do that, we still need to know the coordinates of the center of the ellipse, cx and cy.

The computation of the center of the ellipse is pretty well described in the Appendix F.6.5 of the SVG standard and does not need to be reproduced here. Just note that for this we need the coordinates of the starting point of the arc that correspond to the end point of the previous path segment.

Determine the bounding box of the whole ellipse

Compute the xmin, xmax, ymin and ymax using the values of theta for the local extremes and the newly computed cx and cy coordinates. Like this not only we will know the bounding box of the whole ellipse, but we will also know which value of theta corresponds to maximum and which one to minimum. This knowledge will be later valuable for determining the tightest possible bounding box of a given elliptical arc.

Tightest possible bounding box

By calculation of the bounding box of the whole ellipse, we now know the rectangle that will contain the ellipse and thus our elliptical arc too. Nonetheless, this rectangle is too big for our arc. So, the next thing is to trim it down so that it becomes the tightest possible rectangle that will still contain the whole arc.

For this task, we will use the polar coordinates rather then the cartesian ones. The principle is that if any of the points corresponding to xmin, xmax, ymin or ymax of the whole ellipse, lie on the arc they will be be the extremes of the arc too. Nevertheless, if for instance the point ymin does not lie on the arc, the new ymin will be the minimum of the y coordinates of the starting and ending points. In the same way, if the point xmax does not lie on the arc, the new xmax will be the maximum of the x coordinates of the starting and ending points. Whether an extreme does or does not lie on our arc is something trivial to see once the arc is drawn, to determine it programatically will require some efforts.

First, we will compute the coordinates of the points where the whole ellipse touches the bounding box using the parametric description of the ellipse and the values of the theta that we found out in the previous steps. And for determination whether they lie or not on our arc we will use their position in polar coordinates. We will thus need to compute the angles with the x-axis of the lines going through the center of the ellipse and our extreme points. In other terms, we will compute the angle between vector (1,0) and vector (xextreme-cx, yextreme-cy).

The formula for computing the angle between two vectors is known and mentioned inter alia as formula F.6.5.4 of the SVG standard. Generally, the expression to calculate the angle between a vector (ax,ay) and a vector (bx,by) is:

(ax * by > ay * bx ? 1.0 : -1.0) * acos( (ax * bx) + (ay * by) / ( sqrt(ax * ax + ay * ay) * sqrt(bx * bx + by * by) ) ).

But since we already know that the first vector is (1,0), we can simplify it:

(by > 0.0 ? 1.0 : -1.0) * acos( bx / sqrt(bx * bx + by * by) ), which could be eventually simplified to atan(by / bx), but this expression has a potential division by zero and the code would have to handle those border situations in a special way.

Once we know the angles of the extremes, we still need to calculate the angles of the starting and the end points or our arc using exactly the same formula. So we get angle1 corresponding to our starting point and angle2 corresponding to the endpoint. It is necessary to normalize all angles so that they lie in the interval of [0.0, 2.0*M_PI).

In case the sweep flag is 0, the angles are decreasing when the ellipse is drawn. But, for the computation of bounding box the direction of rotation is irrelevant and only complicates the situation. So we swap the angles if the sweep flag is not set. In this way, we can just check for the absence of the extreme points on our elliptical arc, rotating from angle1 to angle2. Nevertheless, we have another difficulty with the fact that the angle of 0 radians is the same as the one of 2*M_PI radians. This passage through the 2*M_PI / 0 border is not very easy to handle directly. That is why we swap the points in case where angle1 > angle2 and will not look in this case for absence of the extreme points on the arc, but for their presence on the complement arc that would close the ellipse.

And as my teachers used to say: "Grey is the theory, but green is the tree of life," here is what it looks like in a plain C++:

---

#include <algorithm>
#include <cmath>

#ifndef M_PI
#define M_PI 3.14159265358979323846
#endif

inline double getAngle(double bx, double by)
{
  return fmod(2*M_PI + (by > 0.0 ? 1.0 : -1.0) * acos( bx / sqrt(bx * bx + by * by) ), 2*M_PI);
}

void EllpArcBBox(double x1, double y1,
                 double rx, double ry, double phi, bool largeArc, bool sweep, double x2, double y2,
                 double &xmin, double &ymin, double &xmax, double &ymax)
{
  if (rx < 0.0)
    rx *= -1.0;
  if (ry < 0.0)
    ry *= -1.0;

  if (rx == 0.0 || ry == 0.0) {
    xmin = (x1 < x2 ? x1 : x2);
    xmax = (x1 > x2 ? x1 : x2);
    ymin = (y1 < y2 ? y1 : y2);
    ymax = (y1 > y2 ? y1 : y2);
    return;
  }

  const double x1prime = cos(phi)*(x1 - x2)/2 + sin(phi)*(y1 - y2)/2;
  const double y1prime = -sin(phi)*(x1 - x2)/2 + cos(phi)*(y1 - y2)/2;

  double radicant = (rx*rx*ry*ry - rx*rx*y1prime*y1prime - ry*ry*x1prime*x1prime);
  radicant /= (rx*rx*y1prime*y1prime + ry*ry*x1prime*x1prime);
  double cxprime = 0.0;
  double cyprime = 0.0;
  if (radicant < 0.0) {
    double ratio = rx/ry;
    double radicant = y1prime*y1prime + x1prime*x1prime/(ratio*ratio);
    if (radicant < 0.0) {
      xmin = (x1 < x2 ? x1 : x2);
      xmax = (x1 > x2 ? x1 : x2);
      ymin = (y1 < y2 ? y1 : y2);
      ymax = (y1 > y2 ? y1 : y2);
      return;
    }
    ry=sqrt(radicant);
    rx=ratio*ry;
  } else {
    double factor = (largeArc==sweep ? -1.0 : 1.0)*sqrt(radicant);

    cxprime = factor*rx*y1prime/ry;
    cyprime = -factor*ry*x1prime/rx;
  }

  double cx = cxprime*cos(phi) - cyprime*sin(phi) + (x1 + x2)/2;
  double cy = cxprime*sin(phi) + cyprime*cos(phi) + (y1 + y2)/2;

  double txmin, txmax, tymin, tymax;

  if (phi == 0 || phi == M_PI) {
    xmin = cx - rx;
    txmin = getAngle(-rx, 0);
    xmax = cx + rx;
    txmax = getAngle(rx, 0);
    ymin = cy - ry;
    tymin = getAngle(0, -ry);
    ymax = cy + ry;
    tymax = getAngle(0, ry);
  } else if (phi == M_PI / 2.0 || phi == 3.0*M_PI/2.0) {
    xmin = cx - ry;
    txmin = getAngle(-ry, 0);
    xmax = cx + ry;
    txmax = getAngle(ry, 0);
    ymin = cy - rx;
    tymin = getAngle(0, -rx);
    ymax = cy + rx;
    tymax = getAngle(0, rx);
  }  else {
    txmin = -atan(ry*tan(phi)/rx);
    txmax = M_PI - atan (ry*tan(phi)/rx);
    xmin = cx + rx*cos(txmin)*cos(phi) - ry*sin(txmin)*sin(phi);
    xmax = cx + rx*cos(txmax)*cos(phi) - ry*sin(txmax)*sin(phi);
    if (xmin > xmax) {
      std::swap(xmin,xmax);
      std::swap(txmin,txmax);
    }
    double tmpY = cy + rx*cos(txmin)*sin(phi) + ry*sin(txmin)*cos(phi);
    txmin = getAngle(xmin - cx, tmpY - cy);
    tmpY = cy + rx*cos(txmax)*sin(phi) + ry*sin(txmax)*cos(phi);
    txmax = getAngle(xmax - cx, tmpY - cy);


    tymin = atan(ry/(tan(phi)*rx));
    tymax = atan(ry/(tan(phi)*rx))+M_PI;
    ymin = cy + rx*cos(tymin)*sin(phi) + ry*sin(tymin)*cos(phi);
    ymax = cy + rx*cos(tymax)*sin(phi) + ry*sin(tymax)*cos(phi);
    if (ymin > ymax) {
      std::swap(ymin,ymax);
      std::swap(tymin,tymax);
    }
    double tmpX = cx + rx*cos(tymin)*cos(phi) - ry*sin(tymin)*sin(phi);
    tymin = getAngle(tmpX - cx, ymin - cy);
    tmpX = cx + rx*cos(tymax)*cos(phi) - ry*sin(tymax)*sin(phi);
    tymax = getAngle(tmpX - cx, ymax - cy);
  }

  double angle1 = getAngle(x1 - cx, y1 - cy);
  double angle2 = getAngle(x2 - cx, y2 - cy);

  if (!sweep)
    std::swap(angle1, angle2);

  bool otherArc = false;
  if (angle1 > angle2) {
    std::swap(angle1, angle2);
    otherArc = true;
  }

  if ((!otherArc && (angle1 > txmin || angle2 < txmin)) || (otherArc && !(angle1 > txmin || angle2 < txmin)))
    xmin = x1 < x2 ? x1 : x2;
  if ((!otherArc && (angle1 > txmax || angle2 < txmax)) || (otherArc && !(angle1 > txmax || angle2 < txmax)))
    xmax = x1 > x2 ? x1 : x2;
  if ((!otherArc && (angle1 > tymin || angle2 < tymin)) || (otherArc && !(angle1 > tymin || angle2 < tymin)))
    ymin = y1 < y2 ? y1 : y2;
  if ((!otherArc && (angle1 > tymax || angle2 < tymax)) || (otherArc && !(angle1 > tymax || angle2 < tymax)))
    ymax = y1 > y2 ? y1 : y2;
}