Mandelbrot Example▲
The heavy computation here is the Mandelbrot set, probably the world's most famous fractal. These days, while sophisticated programs such as XaoS that provide real-time zooming in the Mandelbrot set, the standard Mandelbrot algorithm is just slow enough for our purposes.
In real life, the approach described here is applicable to a large set of problems, including synchronous network I/O and database access, where the user interface must remain responsive while some heavy operation is taking place. The Blocking Fortune Client Example shows the same principle at work in a TCP client.
The Mandelbrot application supports zooming and scrolling using the mouse or the keyboard. To avoid freezing the main thread's event loop (and, as a consequence, the application's user interface), we put all the fractal computation in a separate worker thread. The thread emits a signal when it is done rendering the fractal.
During the time where the worker thread is recomputing the fractal to reflect the new zoom factor position, the main thread simply scales the previously rendered pixmap to provide immediate feedback. The result doesn't look as good as what the worker thread eventually ends up providing, but at least it makes the application more responsive. The sequence of screenshots below shows the original image, the scaled image, and the rerendered image.
|
|
|
Similarly, when the user scrolls, the previous pixmap is scrolled immediately, revealing unpainted areas beyond the edge of the pixmap, while the image is rendered by the worker thread.
|
|
|
The application consists of two classes:
-
RenderThread is a QThread subclass that renders the Mandelbrot set.
-
MandelbrotWidget is a QWidget subclass that shows the Mandelbrot set on screen and lets the user zoom and scroll.
If you are not already familiar with Qt's thread support, we recommend that you start by reading the Thread Support in Qt overview.
RenderThread Class Definition▲
We'll start with the definition of the RenderThread class:
class
RenderThread : public
QThread
{
Q_OBJECT
public
:
RenderThread(QObject *
parent =
nullptr
);
~
RenderThread();
void
render(double
centerX, double
centerY, double
scaleFactor, QSize resultSize);
signals
:
void
renderedImage(const
QImage &
amp;image, double
scaleFactor);
protected
:
void
run() override
;
private
:
uint rgbFromWaveLength(double
wave);
QMutex mutex;
QWaitCondition condition;
double
centerX;
double
centerY;
double
scaleFactor;
QSize resultSize;
bool
restart;
bool
abort;
enum
{
ColormapSize =
512
}
;
uint colormap[ColormapSize];
}
;
The class inherits QThread so that it gains the ability to run in a separate thread. Apart from the constructor and destructor, render() is the only public function. Whenever the thread is done rendering an image, it emits the renderedImage() signal.
The protected run() function is reimplemented from QThread. It is automatically called when the thread is started.
In the private section, we have a QMutex, a QWaitCondition, and a few other data members. The mutex protects the other data member.
RenderThread Class Implementation▲
RenderThread::
RenderThread(QObject *
parent)
:
QThread(parent)
{
restart =
false
;
abort =
false
;
for
(int
i =
0
; i &
lt; ColormapSize; ++
i)
colormap[i] =
rgbFromWaveLength(380.0
+
(i *
400.0
/
ColormapSize));
}
In the constructor, we initialize the restart and abort variables to false. These variables control the flow of the run() function.
We also initialize the colormap array, which contains a series of RGB colors.
RenderThread::
~
RenderThread()
{
mutex.lock();
abort =
true
;
condition.wakeOne();
mutex.unlock();
wait();
}
The destructor can be called at any point while the thread is active. We set abort to true to tell run() to stop running as soon as possible. We also call QWaitCondition::wakeOne() to wake up the thread if it's sleeping. (As we will see when we review run(), the thread is put to sleep when it has nothing to do.)
The important thing to notice here is that run() is executed in its own thread (the worker thread), whereas the RenderThread constructor and destructor (as well as the render() function) are called by the thread that created the worker thread. Therefore, we need a mutex to protect accesses to the abort and condition variables, which might be accessed at any time by run().
At the end of the destructor, we call QThread::wait() to wait until run() has exited before the base class destructor is invoked.
void
RenderThread::
render(double
centerX, double
centerY, double
scaleFactor,
QSize resultSize)
{
QMutexLocker locker(&
amp;mutex);
this
-&
gt;centerX =
centerX;
this
-&
gt;centerY =
centerY;
this
-&
gt;scaleFactor =
scaleFactor;
this
-&
gt;resultSize =
resultSize;
if
(!
isRunning()) {
start(LowPriority);
}
else
{
restart =
true
;
condition.wakeOne();
}
}
The render() function is called by the MandelbrotWidget whenever it needs to generate a new image of the Mandelbrot set. The centerX, centerY, and scaleFactor parameters specify the portion of the fractal to render; resultSize specifies the size of the resulting QImage.
The function stores the parameters in member variables. If the thread isn't already running, it starts it; otherwise, it sets restart to true (telling run() to stop any unfinished computation and start again with the new parameters) and wakes up the thread, which might be sleeping.
void
RenderThread::
run()
{
forever {
mutex.lock();
QSize resultSize =
this
-&
gt;resultSize;
double
scaleFactor =
this
-&
gt;scaleFactor;
double
centerX =
this
-&
gt;centerX;
double
centerY =
this
-&
gt;centerY;
mutex.unlock();
run() is quite a big function, so we'll break it down into parts.
The function body is an infinite loop which starts by storing the rendering parameters in local variables. As usual, we protect accesses to the member variables using the class's mutex. Storing the member variables in local variables allows us to minimize the amout of code that needs to be protected by a mutex. This ensures that the main thread will never have to block for too long when it needs to access RenderThread's member variables (e.g., in render()).
The forever keyword is, like foreach, a Qt pseudo-keyword.
int
halfWidth =
resultSize.width() /
2
;
int
halfHeight =
resultSize.height() /
2
;
QImage image(resultSize, QImage::
Format_RGB32);
const
int
NumPasses =
8
;
int
pass =
0
;
while
(pass &
lt; NumPasses) {
const
int
MaxIterations =
(1
&
lt;&
lt; (2
*
pass +
6
)) +
32
;
const
int
Limit =
4
;
bool
allBlack =
true
;
for
(int
y =
-
halfHeight; y &
lt; halfHeight; ++
y) {
if
(restart)
break
;
if
(abort)
return
;
uint *
scanLine =
reinterpret_cast
&
lt;uint *&
gt;(image.scanLine(y +
halfHeight));
double
ay =
centerY +
(y *
scaleFactor);
for
(int
x =
-
halfWidth; x &
lt; halfWidth; ++
x) {
double
ax =
centerX +
(x *
scaleFactor);
double
a1 =
ax;
double
b1 =
ay;
int
numIterations =
0
;
do
{
++
numIterations;
double
a2 =
(a1 *
a1) -
(b1 *
b1) +
ax;
double
b2 =
(2
*
a1 *
b1) +
ay;
if
((a2 *
a2) +
(b2 *
b2) &
gt; Limit)
break
;
++
numIterations;
a1 =
(a2 *
a2) -
(b2 *
b2) +
ax;
b1 =
(2
*
a2 *
b2) +
ay;
if
((a1 *
a1) +
(b1 *
b1) &
gt; Limit)
break
;
}
while
(numIterations &
lt; MaxIterations);
if
(numIterations &
lt; MaxIterations) {
*
scanLine++
=
colormap[numIterations %
ColormapSize];
allBlack =
false
;
}
else
{
*
scanLine++
=
qRgb(0
, 0
, 0
);
}
}
}
if
(allBlack &
amp;&
amp; pass ==
0
) {
pass =
4
;
}
else
{
if
(!
restart)
emit renderedImage(image, scaleFactor);
++
pass;
}
}
Then comes the core of the algorithm. Instead of trying to create a perfect Mandelbrot set image, we do multiple passes and generate more and more precise (and computationally expensive) approximations of the fractal.
If we discover inside the loop that restart has been set to true (by render()), we break out of the loop immediately, so that the control quickly returns to the very top of the outer loop (the forever loop) and we fetch the new rendering parameters. Similarly, if we discover that abort has been set to true (by the RenderThread destructor), we return from the function immediately, terminating the thread.
The core algorithm is beyond the scope of this tutorial.
mutex.lock();
if
(!
restart)
condition.wait(&
amp;mutex);
restart =
false
;
mutex.unlock();
}
}
Once we're done with all the iterations, we call QWaitCondition::wait() to put the thread to sleep, unless restart is true. There's no use in keeping a worker thread looping indefinitely while there's nothing to do.
uint RenderThread::
rgbFromWaveLength(double
wave)
{
double
r =
0.0
;
double
g =
0.0
;
double
b =
0.0
;
if
(wave &
gt;=
380.0
&
amp;&
amp; wave &
lt;=
440.0
) {
r =
-
1.0
*
(wave -
440.0
) /
(440.0
-
380.0
);
b =
1.0
;
}
else
if
(wave &
gt;=
440.0
&
amp;&
amp; wave &
lt;=
490.0
) {
g =
(wave -
440.0
) /
(490.0
-
440.0
);
b =
1.0
;
}
else
if
(wave &
gt;=
490.0
&
amp;&
amp; wave &
lt;=
510.0
) {
g =
1.0
;
b =
-
1.0
*
(wave -
510.0
) /
(510.0
-
490.0
);
}
else
if
(wave &
gt;=
510.0
&
amp;&
amp; wave &
lt;=
580.0
) {
r =
(wave -
510.0
) /
(580.0
-
510.0
);
g =
1.0
;
}
else
if
(wave &
gt;=
580.0
&
amp;&
amp; wave &
lt;=
645.0
) {
r =
1.0
;
g =
-
1.0
*
(wave -
645.0
) /
(645.0
-
580.0
);
}
else
if
(wave &
gt;=
645.0
&
amp;&
amp; wave &
lt;=
780.0
) {
r =
1.0
;
}
double
s =
1.0
;
if
(wave &
gt; 700.0
)
s =
0.3
+
0.7
*
(780.0
-
wave) /
(780.0
-
700.0
);
else
if
(wave &
lt; 420.0
)
s =
0.3
+
0.7
*
(wave -
380.0
) /
(420.0
-
380.0
);
r =
std::
pow(r *
s, 0.8
);
g =
std::
pow(g *
s, 0.8
);
b =
std::
pow(b *
s, 0.8
);
return
qRgb(int
(r *
255
), int
(g *
255
), int
(b *
255
));
}
The rgbFromWaveLength() function is a helper function that converts a wave length to a RGB value compatible with 32-bit QImages. It is called from the constructor to initialize the colormap array with pleasing colors.
MandelbrotWidget Class Definition▲
The MandelbrotWidget class uses RenderThread to draw the Mandelbrot set on screen. Here's the class definition:
class
MandelbrotWidget : public
QWidget
{
Q_OBJECT
public
:
MandelbrotWidget(QWidget *
parent =
nullptr
);
protected
:
void
paintEvent(QPaintEvent *
event) override
;
void
resizeEvent(QResizeEvent *
event) override
;
void
keyPressEvent(QKeyEvent *
event) override
;
#if QT_CONFIG(wheelevent)
void
wheelEvent(QWheelEvent *
event) override
;
#endif
void
mousePressEvent(QMouseEvent *
event) override
;
void
mouseMoveEvent(QMouseEvent *
event) override
;
void
mouseReleaseEvent(QMouseEvent *
event) override
;
private
slots:
void
updatePixmap(const
QImage &
amp;image, double
scaleFactor);
void
zoom(double
zoomFactor);
private
:
void
scroll(int
deltaX, int
deltaY);
RenderThread thread;
QPixmap pixmap;
QPoint pixmapOffset;
QPoint lastDragPos;
double
centerX;
double
centerY;
double
pixmapScale;
double
curScale;
}
;
The widget reimplements many event handlers from QWidget. In addition, it has an updatePixmap() slot that we'll connect to the worker thread's renderedImage() signal to update the display whenever we receive new data from the thread.
Among the private variables, we have thread of type RenderThread and pixmap, which contains the last rendered image.
MandelbrotWidget Class Implementation▲
const
double
DefaultCenterX =
-
0.637011
f;
const
double
DefaultCenterY =
-
0.0395159
f;
const
double
DefaultScale =
0.00403897
f;
const
double
ZoomInFactor =
0.8
f;
const
double
ZoomOutFactor =
1
/
ZoomInFactor;
const
int
ScrollStep =
20
;
The implementation starts with a few constants that we'll need later on.
MandelbrotWidget::
MandelbrotWidget(QWidget *
parent)
:
QWidget(parent)
{
centerX =
DefaultCenterX;
centerY =
DefaultCenterY;
pixmapScale =
DefaultScale;
curScale =
DefaultScale;
connect(&
amp;thread, &
amp;RenderThread::
renderedImage,
this
, &
amp;MandelbrotWidget::
updatePixmap);
setWindowTitle(tr("Mandelbrot"
));
#ifndef QT_NO_CURSOR
setCursor(Qt::
CrossCursor);
#endif
resize(550
, 400
);
}