Trained Monkey Hacking Experience

LibreOffice Visio Import Filter: 20 years of drawings opened in your favourite office suite

2012-12-07T17:19:00.001+01:00

It is true that the support of the most used Microsoft Visio file formats in LibreOffice will celebrate 1 year next February. And I will gladly have a birthday talk with any of you who will be freezing in Brussels during the next FOSDEM 2013. Nonetheless, even though libvisio was in development for several months already, the Visio story was far from finished when we released that day. As I already mentioned in another blogpost concerning reverse-engineering of file formats, assessment of a conversion quality in this kind of cases is illusory before real users get to stress-test it with real-life documents.
Since the first release of our filter in LibreOffice 3.5.0, we were improving it thanks to bug reports from our users. It is a big thank you that I would like to say to all those that took the bother to submit reports in our bugzilla. Without you, guys, this filter would be only a moot exercise.
But wait... Do I write this blog now only to thank the people who contributed to the current quality of the filter? Yes to a big extent! Nevertheless, I know that the distinguished readers of this blog would like to have some news. And, yes, we have some news.
The libvisio library underwent heavy re-factoring as we started to understand more and more details about the underlying file-format.

A particular bug report about files imported as empty pages provided us with a document structure that we did never see before. This resulted in a more generic parser and unification on the way we parse master shapes and visible pages.
This re-factoring in its turn allowed us to extend our file-format coverage to all earlier binary Visio file-format versions. We now support all binary Visio documents starting from Visio 1 (released in 1992).
Extending the support to earlier file-format versions allowed us to better understand the development of the file-format, to find more information that we did not parse before, and improve the conversion quality for other binary versions too.
Another re-factoring came with our work to support the XML-based Visio file-formats, namely the "XML Drawing" also known as *.vdx; and the Microsoft Visio 2013 new file-format, known as *.vsdx.

So the news is that LibreOffice 4.0.0 will be able to open ALL Visio files starting from Visio 1 (release in 1992) until Microsoft Visio 2013 (released just some weeks ago).
And since the readers of this blog are more interested in pictures than in pointless words, here come some candies for your eyes:

File opened in Visio 1.0		The same file opened in LibreOffice 4.0.0 beta1

VSDX File opened in Microsoft Visio 2013		The same file opened in LibreOffice 4.0.0 beta1

So, download the LibreOffice 4.0.0 beta1 and help us testing the new big release. We are interested in bug reports that help us to improve our quality. And for those that would love to support us with donations, just click here:

LibreOffice CorelDraw import filter: improvements by user input

2012-11-26T15:57:00.001+01:00

It has been a long time without communicating with the distinguished readership of my blog. There was a hard decision to be made between producing code and producing literature. The code won until now. But now I have found a time to lift my head up from the coding, so the literature is back.

Many of you might be wondering what happened since my post about the text support in CorelDraw files from last June. Things are going pretty well. Since the CorelDraw import filter was released with LibreOffice 3.6, the users started to use the feature and report bugs. We were working on fixing them and improving the libcdr's quality.

Quick overview of reverse-engineering process

From my discussions with our users and developers on-line and during some of the conferences that I attended, I realize that there is a slight misunderstanding in the large public about how the reverse-engineering works. So, here are some thoughts that may help understand it a bit more:

At the beginning of the process, there is a file-format. We don't know anything about its internal structure. There is no documentation whatsoever about it. One tries to generate a file in this file-format and examine it in hexadecimal viewer. Next, one tries to operate some little change in the document and examine what changed in the file itself. Eventually after many iterations, one might find regularities and some structure that helps to divide the file into several sections or blocks of more manageable size. It is essential in this phase that one can encode this information into some kind of introspection tool, since a plain hexadecimal viewer is not a very productive tool in the long run. We use for introspection of documents Valek Filippov's oletoy, a python tool that stores our knowledge about the structure of different file-formats.

Once there is enough information about how to parse the document structure, the next target becomes to get some visible results. In order to save time and get visible results in a short time, all libraries such as libcdr or libvisio, use the libwpg's interface. Reusing this interface means a considerable saving of time, since there are already working generators of ODG and SVG from the callbacks of this interface. Having visible results soon in the development/reverse-engineering cycle also allows visually asses the import results and correct them if necessary. Eventually, one can realize the absence of necessary information and try to go back to reverse-engineering to find it.

Users' feedback is essential

The support of reverse-engineered file-formats is a constant work-in-progress. A subtle dance between implementation and information digging. In this process, the user feedback is an essential element. The theories about the meaning of some information inside file hold only until a file comes to falsify them. Even a complex file generated by a developer is easily beaten by real life documents. And each file that shows a "weird" bug is advancing the understanding of the file-format. Let us look at this example:

After the release of LibreOffice 3.6.1, we got a not so good assessment of the quality of the CorelDraw import filter in the heise.de' c't review. Those of you that understand German can delight in the nuanced evaluation:

Ein neuer Import-Filter in Draw öffnet jetzt auch CorelDraw-Dateien, was uns im Test allerdings nur mit sehr einfachen Zeichnungen fehlerfrei gelang. In dieser Form ist er schlicht unbrauchbar.

Which can be mildly translated into English (given the understatements so common in en-GB):

A new import filter in Draw opens now also CorelDraw files, which we managed to do without errors only with very simple drawings. In this form, it is rather unusable.

Since we are really concerned about the quality of our software, we are thankful for any bug report whether it is brought to us in a friendly or other manner. This specific bug report helped us to understand how are stored in newer CorelDraw files chains of matrix transforms. And since a picture speaks louder then thousand words, compare the document c't was refering to opened in LibreOffice 3.6.2 and then in LibreOffice 3.6.3, after we fixed the position bits.

File opened in Libreoffice 3.6.2		The same file opened in LibreOffice 3.6.3

So feel encouraged to submit bugs against the CorelDraw import filter, or — even better — send us patches for your favorite itch.

Susan's Book on Intellectual Property and Access to Education

2012-07-02T10:52:00.001+02:00

I am happy to announce the upcoming book of my dear wife. A must read for all interested in intellectual property, in access to copyrighted materials and in development issues.

This book originates from a PhD thesis defended at the Graduate Institute of International and Development Studies, Geneva, Switzerland. It has been awarded "summa cum laude" mention.

Check, please, with your libraries whether they know about the book and advise them strongly to purchase it for the biggest good of the humanity :)

LibreOffice CorelDraw Import filter - text support hatches out

2012-06-12T10:01:00.000+02:00

Uff, it is done!!!

We started to work on the text support inside libcdr already before the Libre Graphics Meeting in Vienna. We worked hard during the talks and the long evenings after having eaten some portions of Wienerschnitzl.

Now we are proud to announce that we managed to release yesterday libcdr-0.0.8 with "basic initial primitive [u]ncomplete" (further BIPU) text support. At the moment, we are supporting only a couple of parameters as a font face and font size and we are able to detect the encoding and produce a corresponding utf-8 string. Far from being perfect, it is nonetheless a milestone, because in the FOSS world, there was no support for CorelDraw text before.

We know that you prefer to look at nice pictures instead of reading bad text. So, this gives your heart's desires.

A simple document with text in CorelDraw 7:

The same document opened in a build of LibreOffice from yesterday:

At the moment, libcdr is able to convert text in CorelDraw documents from versions 7 to 16. Nonetheless, we know already roughly how to read it in files of lower versions and we will add the support for next release. In the same way, we will extend our support of other text properties, like font colour, transparency, effects, paragraph alignments, character positions, etc.

How can I test it? All this goodness will be part of LibreOffice 3.6.0 release. You will be able to test the text support in the 3.6.0 beta2 pre-release. For the brave, any of the daily builds that are built from a code checkout after June 11th also include libcdr-0.0.8 and thus the text support in CorelDraw files.

As usual, this is a free and open source software project and, as such, it delights in developers that want to help. So, if you feel the itch, patches can be sent to libreoffice-dev mailing list. And, do not forget to find a way to join the #libreoffice-dev channel at irc.freenode.net in order to meet other developers. We can promis you that you will feel at home in the LibreOffice community.

LibreOffice MS Publisher Import filter - young but strong baby

2012-06-06T15:23:00.000+02:00

As Sophie Gauthier announced in the language of Voltaire, LibreOffice was branched for the beta phase in view of the 3.6 release. This is a major step in order to bring the features we were working on during the last half a year to the end users. But, it is also oportunity to bring to the main codebase all the nifty nice features that were developed in feature branches and targeted for the next big release, presumably the 3.7.

It is this way that the first version of our new Microsoft Publisher import filter landed to the master. This filter is developed by Brennan Vincent from the University of Arizona in the frame of the Google Summer of Code. Although being a work in progress and supporting for the while only the Publisher 2003 file-format, the progress is spectacular. Brennan has been busy like a bee even long before the start of the program. After only two weeks from the official kick-off, we have a first (non-)release, libmspub-0.0.0.

And as the careful readers of this blog already know, an image speaks louder then thousand words, here are the pics:

A random document from the Internet opened in Microsoft Publisher 2003:

The same document opened in LibreOffice master build from yesterday:

With Valek Filippov, we have a lot of fun mentoring this project. If anybody of the distinguished readership wants to join this effort, the code of libmspub lives in LibreOffice freedesktop.org repository. The patches can be sent to libreoffice-dev mailing list. And, do not forget to find a way to join the #libreoffice-dev channel at irc.freenode.net in order to meet other developers.

You will never regret the decision to get involved in LibreOffice.

Google Summer of Code 2012 - accepted projects for LibreOffice

2012-04-23T21:57:00.001+02:00

Google announced today the accepted students for Google Summer of Code 2011.

The students working on LibreOffice will be:

Student	Title	Mentor
Andrzej Hunt	Smartphone remote control for LibreOffice Impress	Muthu Subramanian
ArturoPL	Tooling - More and better tests	Michael Stahl
Brennan Vincent	Implementing a Microsoft Publisher import filter for LibreOffice	Valek Filippov
Daniel Bankston	Calc Performance Improvements	Kohei Yoshida
Daniel Korostil	Lightproof improvements	László Németh
Gökcen Eraslan	Signed PDF export	Stephan Bergmann
iainb	Java GUI for Libre-Office Based Android App(s)	Tor Lillqvist
Marco Cecchetti	Enhanced Impress svg export filter	Thorsten Behrens
Matúš Kukan	Telepathy for collaboration	Eike Rathke (erAck)
Rafael	New templates picking UI	Cédric Bosdonnat

Let the summer start immediately and let quality code fall like a spring rain!

LibreOffice CorelDraw Import filter - the best file-format coverage in the FOSS world

2012-04-02T17:37:00.001+02:00

I just realized that has been a long long time since I last blogged about libcdr and the CorelDraw import filter in LibreOffice. Those that know me well can imagine that it is much more fun to write code then to write blogs. Nonetheless, one serious breakthrough happened this weekend and I cannot prevent myself from climbing on the roofs and shout.

On 20^th of March 2012, Corel released a new version of CorelDraw Graphics Suite X6. We got the information from this Wikipedia page and downloaded the evaluation version on Friday. Although it was usual to see the file-format mutate a bit with every released version, this release changed the file-format substantially in what concerns the RIFF chunks. To cut the long story short, we managed to get the last pieces reverse-engineered today and we released libcdr-0.0.6 with support of all 32-bit CorelDraw formats, from version 6 to 16.

The new release tarball was integrated in LibreOffice which became the first and only FOSS application that supports versions 6, 15 and 16 of the CorelDraw file-format. This goodness will be part of our 3.6 release later this year. For those that do not know fear, the feature can be tested in daily builds that will start to appear tomorrow morning here.

I know that the distinguished readership prefers pictures to words. Here is this simple document in CorelDraw X6 format:

Here is the same document opened by LibreOffice Draw:

And here is the libcdr-generated SVG opened in Inkscape:

If you are tempted and think that it might be fun to participate in a reverse-engineering endavour, we have with Valek two project proposals for Google Summer of Code 2012. The first is the implementation of MS Publisher import filter for LibreOffice and the second is to help to improve and extend the Corel Draw import filter I am currently blogging about. Try to apply with LibreOffice and your life will never be the same again.

Be aware though that the application deadline is the 6^th of April and you will need to accomplish a simple programing task in order to be eligible. More details in this blog.

Google Summer of Code at LibreOffice: become famous and maybe rich!

2012-03-19T14:30:00.002+01:00

So, just before the weekend, we received the great news that Google chose LibreOffice as a mentoring organisation for Google Summer of Code again this year. Some of you might remember that last year we had several extremely successful Google Summer of Code projects and that two of our successful students are currently employed working on free and opensource software as a direct consequence of their participation in the program. I had a priviledge to mentor Eilidh McAdam and we implemented a Visio import filter that is one of the flagship features of LibreOffice 3.5. Eilidh is now employed by Lanedo.

This year, we proposed with Valek Filippov two projects related to reverse-engineered file-formats. The first is the implementation of MS Publisher import filter for LibreOffice and the second is to help to improve and extend the Corel Draw import filter that will be part of LibreOffice 3.6 release. Both projects require working knowledge of C++ and a lot of good will. Each of the import filters consists of a standalone library and a glue that plugs the library into LibreOffice. These libraries can be built as system libraries and LibreOffice can use them from the system. The advantage of this approach for a student participating at the development is that there is only a minimum need of recompiling LibreOffice if some substantial part of the glue (that is rather small) changes. Therefore, I encourage all of you who are considering applying with LibreOffice for this year's Google Summer of Code to have a close look at those two projects. As a bonus is that if you are successful, you become famous and eventually rich.

You can have a look at libcdr, the horsepower behind the Corel Draw import filter and at the skeleton of libmspub, that will be the basis of the Publisher import filter. And don't hesitate to become rich and famous with Google Summer of Code at LibreOffice

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

2012-01-31T15:56:00.001+01:00

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

2012-01-25T23:19:00.002+01:00

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:

Find a bug that is bothering you in the current Visio import filter, or some simple feature that the importer currently does not support
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)
Build them as system libraries and install them in the same order.
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-libwpd
- --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

2012-01-02T15:19:00.002+01:00

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

2011-11-15T12:34:00.002+01:00

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

2011-11-15T01:25:00.001+01:00

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

2011-09-15T14:10:00.000+02:00

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

2011-07-08T15:15:00.004+02:00

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

2011-06-20T20:14:00.005+02:00

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 (x_extreme-cx, y_extreme-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; }

LibreOffice Visio import filter - shaping up the baby

2011-06-17T16:21:00.003+02:00

Maybe you were asking yourself what happened in the Google Summer of Code Visio Import filter project since last week. But even if you did not ask yourself this necessary question, here is some update about the baby:

The focus this week was mainly on shaping the baby up. Eilidh added to her blog a photo and an "About" line and then she got exhausted and decided to rest by coding. And it is like this that she implemented polylines, ellipses and circular arcs.

And since the images speak louder then any words, enjoy the look:

Microsoft Visio		LibreOffice Draw

For those interested in some technical details, or even for those that desire to give hand, the code of the libvisio library is living here. And as usual, for any question or encouragement, feel free to join our #libreoffice-dev irc channel at irc.freenode.net, ping tibbylickle and pat her back, if she is not lost too deep inside her Emacs.

LibreOffice Visio Import filter - first steps of a new baby

2011-06-10T13:49:00.005+02:00

The Google Summer of Code started some weeks ago and we have some nice projects at LibreOffice too.

I am having again this year the privilege to mentor a brilliant student Eilidh McAdam working on a Microsoft Visio import filter. She got up to the speed very quickly to the point that she is now very intimate with any hexadecimal number of any width. And the first results of her diving into the binary world can speak for themselves.

This Visio document : can be currently imported into LibreOffice Draw: .

For those that might be interested in such a detail as the source code of this endavour, the filter is developped as two elements, a shared library living here and an import filter based on this library living in the LibreOffice's writerperfect module.

For any question or encouragement, feel free to join our #libreoffice-dev irc channel at irc.freenode.net and ping tibbylickle (for encouragements) or Fridrich (for blames).

opensuse-mingw mailing list

2011-03-03T22:04:00.004+01:00

The windows::mingw project and its sub-project quickly gain a true community around themselves. This week, the number of source packages that we build for Windows in openSUSE Build Service reached 200 for both the 32-bit as well as 64-bit Windows versions.

In order to make the communication between contributors, developers and users easier, we got a sparkling new mailing list at lists.opensuse.org. You can subscribe it by sending a mail to opensuse-mingw+subscribe@opensuse.org and enjoy all the intelligent and edifying talk we are having there.

Voreppe Win32 Tinderbox

2011-02-26T08:07:00.004+01:00

As you can see here, we have now a working Windows tinderbox. It finished tonight its first successful build of master branch and will send you nagging e-mails for any breakages from now on. It is our hope that this tinderbox will help us to keep LibreOffice buildable on Windows much easier.

This tinderbox is running Windows Server 2008 R2 Service Pack 1 with Visual Studio 2008 Service Pack 1 and Windows SDK 7.1. The server was graciously given at the disposition of the LibreOffice community by the French town of Voreppe through the association La Mouette. I want to personally thank Laurent Godard, a long-time community member and contributor who was more then instrumental in this transaction.

GNU Make 3.82

2010-09-11T10:53:00.001+02:00

Just noticed that this kind of constructs chokes GNU Make 3.82

     test x$CC = x && CC = gcc

It can be replaced by

     CC ?= gcc

Which can be written in a long form:

     ifeq ($(origin CC), undefined)
     CC= gcc
     endif

The other thing that is making this version of GNU Make choke are leading spaces in multi-line rules. Please, use tabs when writing Makefiles.

Hackweek V - Day 1

2010-06-07T18:12:00.000+02:00

It is Hackweek V here at Novell. And as with all good things that are supposed to start on Monday, and end on Friday, the best thing is that they can start on Friday evening and go until the night becomes a dawn on Monday morning. It is in this spririt that I started to do some preparation to the long overdue release of libwpd libwpg and all projects that are depending on these two. Already during the week-end I fixed some obvious regressions in libwpg, caused by the complete API rewrite. I added some callbacks to the libwpd's API, so that we can try to support named styles during the 0.9.x series and will not have to break ABI too soon (libwpd 0.8.x were API stable for about 5 years). And today, I was playing with some more regressions and bugs found by sum1, the best QA person that I know.

The fun part for libwpg was to somehow start to support elliptical arcs so that some graphs can have nice smooth edges. This is when one converts the WPG files to SVG. Another fun was generating ODG. Although the ODF 1.1 specifications somehow allow to have elliptical arcs in a path, the reference implementation of ODF does not render them. Needless to say that it is pretty tedious task to try to compute a proper bounding box for a path that has only one elliptical element. Just wondering whether ODG can ever become so easy to use and as expressive as SVG. Never mind, just ranting!

The other thing that I wanted to work on during hackweek was the Evolution installer that I spoke about some time ago. Nonetheless, it would be not wise (the less one can say) to put that as a principal task for oneself. Unless, one is crazy in love with progress-bars and enjoys staring at them for 15-20 minutes in row. But, I can report some progress in there. It is now possible to install only the languages one wants, although that functionality must be somehow fine-tuned so that we don't publish languages where only one of the *.mo files is present. Another little work was done in order to make the installer Welcome page a bit more sexy.

For those that would like to debug Evolution on Windows, there is now a debug installer in the dummy rpm file that I mentioned in my previous blog post. This debug installer will install the debug symbols for all DLLs and EXEs in the Evolution installer and will add also a working gdb.exe as a courtesy of your faithful.

Last, but not least, I would like to announce officially that a 64-bit evolution starts and work on a 64-bit Windows operating system. It can even show some fancy blog entries. Please, don't focus on the content, or lack thereof :-P, rather enjoy the nice picture) of rss plugin using 64-bit version of webkit-gtk.

Experimental Evolution installer for Windows

2010-05-25T16:48:00.004+02:00

It is a pleasure, fun and honour to introduce to the distinguished audience our newest Evolution installer for Windows. You can find it for instance in this repository of our wonderful openSUSE Build Service. The installer is hiding in /usr/i686-pc-mingw32/sys-root/mingw directory of the mingw32-evolution-installer RPM. For people that don't know what to do with RPM packages on windows, 7-zip does just a wonderful job at unpacking RPMs even if they use LZMA payload.

As you can see from following pictures,

the functionality offered by the installer is basic for instance. Nevertheless, it does the most important job which is to install Evolution on your windows box.

On the first launch, Evolution will register itself as a mail client able to handle mailto protocol and it also registeres the necessary verbs to be able to become default mail client on Windows,

and on versions of Windows where the start menu Internet and E-mail links are supported, it can install its icon and open verb in that region:

Apart of those technicalities, it can be used to read mail:

to manage one's contacts and timetables, even to understand why one is feeling suddenly so hot:

Not to mention that evolution will in principle detect your timezone and even your online status.

The installer is for the development series of Evolution (2.31.x). It is possible to produce one for the "stable" (2.30.x) branch, but the quality of both branches on Windows is comparable and doing a "stable" installer would be slightly missleading for the user. Having said that, this version is quite usable although, I would not advise anybody to use it in mission-critical environment yet. But if you decide to adventure into this, it will be enriching endavour for all of us. The bugs can be filed in GNOME Bugzilla against evolution. Help us to make it better!

OpenSUSE Build Service

What is really really really cool with this installer is that it is produced completely inside the openSUSE Build Service, a wondeful tool, a once-in-a-lifetime innovation. All the binaries are cross-compiled from Linux and the installer is produced by a version of Nullsoft Scriptable Install System running on Linux and producing Windows installers. The installer is automatically regenerated when the rebuild of Evolution is triggered by any event: change in dependencies, change in Evolution version, etc. It requires a minimum maintainance and is a good starting point for improving further. Since such improvement can now be an incremental one building on the top of the existing infrastructure.

I will never say it enough, but openSUSE Build Service is one of the best invention on the earth since the Butterbrot

ISensNetwork based network monitor for Evolution

2010-03-29T15:39:00.001+02:00

These weeks I was using my spare cycles to prepare evolution to be buildable and running before the GNOME 2.30 freeze. One of the things that Evolution for windows was missing was an alternative for the NetworkManager network connection detection module. I crafted one using Windows ISensNetwork COM interface. The result is to be found here for those that might be interested in seeing how to implement COM callbacks in plain C.

There are some examples out there showing how to implement ISensNetwork. One of them using heavy ATL framework is to be found here. Another, one, using C++ is to be found here. Both examples have a little problem that actually prevents them from being properly used from unprivileged account, although they work well when Administrator runs them. The problem is that the registering of the event subscription will return E_ACCESSDENIED. Judging from the number of post on different fora when one querries Uncle Google, the solution is not very known. If you have the same problem, please check the plain C example that I crafted using the above-mentioned C++ code as a base. I discovered that specifying that the subscription is a per user one, by using IEventSubscription::put_PerUser(..) method allows your program to register for system events even if it is run as unprivileged user. The source code can be built with different flavours of MinGW and also with Visual Studio and the program installs an icon in the system tray that will notify you when connection status of your computer changes.

By the way, there is not a lot of sample code out there that would use COM from a plain C. Apart excellent code produced by my colleague and object of mute admiration, Tor Lillqvist, there is an wonderful serie of articles by Jeff Glatt. It is worth reading for anybody that wants to do COM the real men's way, in plain C. Here are the links to part 1, part 2, part 3, part 4, part 5, part 6, part 7 and part 8. It is worth to register and get the example code as well as a neat clean html version of the articles. It is enough to download the files linked from the part 8 since they are always cumulated with all files from all previous parts.

DBus for windows in windows:mingw repositories

2010-03-02T09:27:00.002+01:00

Last night two important new packages landed into windows:mingw:win32 and windows:mingw:win64 projects and repositories in openSUSE build service: mingw32-dbus-1 and mingw32-dbus-1-glib glib bindings for 32-bit Windows and mingw64-dbus-1 and mingw64-dbus-1-glib for 64-bit Windows. Although, they are known to work in certain setting, they might be buggy in others. So, if you build for Windows some package that needs Dbus, please use these rpms to solve that dependency. And if you find bugs, just report them against the corresponding repository. We will take care of investigating and pushing the reports up the stream.

As a nice result of this new packages would be that the development version of evolution-data-server and evolution should be buildable now on Windows too. Not tried yet though, but I know someone who did ;-)

Note that the dbus-1 package is based on the latest development tarball (1.3.0) and is brought to the level of recent git master by a patch inside the rpm package. The dbus-1-glib is basically the 0.84 tarball with a little patch allowing cross-compiling and disabling one test that hard-codes the use of Unix sockets.

So, please, use those packages, stress-test them and report all useful information.