Fuzzy optimizations in QTransform

Submitted by mimec on 2012-12-06

Before I get to the point, just a quick note: I recently released a new version of both WebIssues and Fraqtive and I'm planning to release a new version of Saladin by the end of this year, so I'm quite busy, as usual at this time of the year. Also check out the fractal animations created using the latest version of Fraqtive. There are much more impressive deep zoom animations available, but they were created using specialized tools which use high precision numbers. Fraqtive uses SSE2 to maximize the real-time experience, so it's limited to double precision, which allows to zoom the fractal about 10^13 times. But this is enough to produce some cool effects.

Now back to the main topic. For a long time there was a strange bug in Fraqtive that I thought was impossible to fix. As those who use it know, in Fraqtive it is possible to move and zoom around the fractal using the mouse, and when you release the mouse button, the new region of the fractal is recalculated. This works by converting the start and end position to a QTransform (which is basically a 3x3 matrix defining the offset, zoom and rotation) and calculating the relative transformation. It worked fine until a certain zoom level was reached; then it started producing weird results. I always blamed the limited precision of double numbers, though the effect could be observed a few orders of magnitude before reaching the maximum valid zoom.

Recently I debugged the entire code, including the calculations performed inside QTransform class and discovered that it performs some optimizations which cause the wrong results. The documentation mentions that QTransform performs some optimizations based on the type of the matrix. For example, if the transform includes translation only, the scale and rotation components are ignored. What the documentation doesn't mention, though, is that Qt uses fuzzy compare functions (such as qFuzzyCompare) to determine the type of the matrix.

The problem with qFuzzyCompare and it's undocumented qFuzzyIsNull counterpart is that they assume that only about 12 digits are significant in a double precision floating point number. This often makes sense, because limited precision can result in some subtle differences which cause the strict comparison operator to fail. We all know that 10 / 3 is 3.33333... and that value multiplied by 3 gives 9.99999.... In mathematics, this value is equal to 10, but for a computer, these numbers are not necessarily equal.

The effect of using fuzzy comparisons is that at a zoom level higher than 12, the scale factors are considered equal to 0, so the transformation is considered non-invertible, when in fact it is. Also rotation tends to be ignored at this zoom level. The solution is not to use QTransform when high precision is required or to write custom functions which do not have these side effects. See also [#QTBUG-8557] where a similar problem is discussed.

Note that fuzzy comparisons are used not only in QTransform, but also in other classes like QMatrix4x4 and QVector3D. Some time ago I came across the a similar problem with QVector3D::normalized which caused Descend to incorrectly calculate normal vectors for the surfaces. The problem is that Descend calculates three samples that are very close to one another in order to precisely determine the normal vector. In some areas of the surface it would hit the 12 significant digit limit, so I ended up writing my own version of this function which didn't use fuzzy comparisons.


Submitted by mimec on 2008-01-22

A few days ago I made a new skin for the website and I must say for the first time I'm quite satisfied with it. I didn't plan to do it now, it was just an experiment, but the result was so encouraging that I decided to make a new skin from it. It lost its 'individual' style, but it's much cleaner, readable and visually appealing. I'm not much of a web designer so I just tried to imitate designs that I like (for example the KDE website) and make it as simple as possible.

I always thought that fixed width layout is a bad thing, but I finally changed my mind as the width of the screen grows and the lines of text become annoyingly long. Now it doesn't fit entirely on a 800x600 screen, but I had to make it wider so that the images fit well. It's not a problem these days (recent statistics show that for 'technical' sites only about 3% of visitors use a resolution lower than 1024x768).

What's coming next? It's time to upgrade the engine of this website. Soon I'm going to start playing with the upcoming Drupal 6.0 because the version I'm using now is rather ancient. But I like the way it works now with all customizations that I made. It won't be an easy task to keep it working the same way.

Also, now that the WebIssues Client reached stable version I can finally work on another project. As I mentioned some time ago, I'm not inventing anything new, just removing dust from an old project. I recently started rewriting Fraqtive, the fractal generator, planning to give it a completely new look and feel, an improved engine (with support for SSE2 and multi-core processors and possibility to customize fractal types) and obviously porting it to Qt4. It may not be such serious project as WebIssues, but sometimes it's good to make something just for fun. It's too early to say precisely when it will be available, but I'd say spring is realistic.

Fraqtive and MFC articles

Submitted by mimec on 2005-12-18

Yesterday I created a web site for Fraqtive, a fractal generator for KDE written by me. The official address is now Some parts are still missing, for example a forum and the binary packages, but the source packages can be downloaded.

Today I moved my MFC articles, along with all 230 comments posted over the past few years. These articles are still quite popular, even though MFC is a rather old technology, and honestly it's pain in the ass to use it. Yeah, I know, too much time spent with Qt :). I can't fully support these articles, simply because I forgot most of the MFC hacks I used to know... however here they are, if anyone finds them useful.