Extending QwtPlotItem class to plot huge arrays of data

Qwt

Qwt is a great library. It has a lot of classes, and can be used "out of the box" to perform almost every plot related task. But more important feature is library extendability. Qwt design allow user easily implement custom classes and integrate them seamlessly with standard library.

In this article I will show you how to implement custom class, derived from QwtPlotItem class (base class for all object, displayed on the plot canvas of QwtPlot), that can be used to plot very big arrays of data, with millions of points.

Plotting 101

Plotting is no more then transforming plot (or real data) coordinates to screen (widget) coordinates. One need multiply every data array point with transformation matrix and get new array with points that have coordinates in screen pixels. After that we only need to draw line segments from point to point to get plot curve on screen. In fact, this algorithm is used in QwtPlotCurve class, that allows to plot series of data.

The problem is, this method is effective only when point number is not very big. When you plotting weekly sales stats over year its ok (because there are only about 50 weeks in year). But when, for example, you are trying to plot realtime data from digital oscilloscope, performance will drop drastically (because every second you will get array of data with 4M samples).

Good for us, we can use some tricks here to reduce system overheat and get good performance.

General approach to plot big arrays of data

In two words: clipping and resampling. First one is simple – we do not want waste our processor time on data that is off screen (widget) due to axis settings, or user zooming in.

Second one is originates from the fact that every display has physical limitation – its resolution is fixed, and contains finite number of pixels in each dimension. So if you using Full HD display, it only has 1920 pixel on horizontal axis, that is not that much compared to 1M (or even more) points in our data array. All transformed plot coordinates (that are real numbers with floating points) will be truncated to integer, when drawing pixels on screen.

When the number of data points on screen begins to grow, there will be situation when multiple points (that have different x coordinates) will have the same x coordinate in pixels after transformation (because pixel coordinates are integer). See pictures below that illustrate this:

Points/pixels ratio is less than 1.0: there are more horizontal pixels than points in data array

Start shrinking plot by increasing points/pixels ratio. It's still less than 1.0, however.

Points/pixels ratio is more than 1.0: several data points correspond to the same pixel on screen

If, for example, we are trying to fit our series data with 1M point to full screen widget, in every screen pixel there will be 1M/1920 ~ 500 points. All lines that connect these points will overdraw each other.

And we can reduce calculation/drawing  time (and lag) if we replace that 500 points with only 2 - one is minimum value from array and second - maximum value, and draw only 1 line connecting these points.

To avoid drawing of indistinguishable lines on screen and improve plotting performance we need split our data array to N/P chunks, where N is number of points in data array visible on screen, and P is pixel width of canvas, that will be used to draw these points, find maximum and minimum point in array and draw only one line.

QwtArrayPlotItem class

First of all: you can download full example code from GitHub.
QwtArrayPlotItem class use two overloaded methods from QwtPlotItem:

1. QwtPlotItem::draw()

2. QwtPlotItem::boundingRect()

and one custom method SetData() that is used to pass array pointer to class. I don't use any "safe" container here because its more common when you work with ADC hardware to get your data in raw buffer, and just pass link to buffer is faster than copy data. Fill free to modify this as you want.

Ok, some more details now

Constructor

	QwtArrayPlotItem::QwtArrayPlotItem(const QwtText &title):
	QwtPlotItem(title),
	m_dt(1.0),
	m_size(0),
	m_data(0),
	m_plotColor(Qt::red)
	{
	setItemAttribute(QwtPlotItem::AutoScale, true);
	setRenderHint(QwtPlotItem::RenderAntialiased,true);
	}

view raw QwtArrayPlotItem_constructor.cpp hosted with ❤ by GitHub

Just initialize internal variables and set some flags (autoscale attribute is enabled - we need return proper bounding rect for this item).

QwtArrayPlotItem::boundingRect()

	QRectF QwtArrayPlotItem::boundingRect() const
	{
	//if we have valid rect, return it
	if( m_boundingRect.isValid())
	return m_boundingRect;
	//need to calculate
	else if(m_data != 0 && m_size>1)
	{
	double min =0.0;
	double max =0.0;
	if(m_data[0]<m_data[1])
	{
	min = m_data[0];
	max = m_data[1];
	}
	else
	{
	min = m_data[1];
	max = m_data[0];
	}
	//compare pairs
	for(int k=2;k<m_size-2;k+=2)
	{
	if(m_data[k]>m_data[k+1])
	{
	if(m_data[k]>max)
	{
	max = m_data[k];
	}
	if(m_data[k+1]<min)
	{
	min = m_data[k+1];
	}
	}
	else
	{
	if(m_data[k+1]>max)
	{
	max = m_data[k+1];
	}
	if(m_data[k]<min)
	{
	min = m_data[k];
	}
	}
	}
	m_boundingRect = QRectF(0.0,(double)min, m_size*m_dt, (double)(max-min));
	return m_boundingRect;
	}
	return QRectF( 1.0, 1.0, -2.0, -2.0 );
	}

view raw QwtArrayPlotItem_boundingRect.cpp hosted with ❤ by GitHub

Just iterate over array and found its maximum and minimum values. One trick used here: instead of simple comparing each value in array with current min/max, we form pairs of values and first compare values in pair - after that minimum value in pair is compared with global minimum, and maximum value - with global maximum. In this case we will have only 3N/2 comparisons instead of 2N.

QwtArrayPlotItem::draw()

	void QwtArrayPlotItem::draw( QPainter *painter,
	const QwtScaleMap &xMap, const QwtScaleMap &yMap,
	const QRectF &canvasRect ) const
	{
	//some data checks first
	if(!m_data)
	return;
	if(m_size<2)
	return;
	if(qFuzzyCompare(m_dt,0.0))
	return;
	//array that will be used to store calculated plot points in screen coordinates
	QPointF* points=0;
	//number of points in array (will be calculated later)
	quint32 numberOfPlotPoints = 0;
	//number of visible points for current zoom
	quint32 realpoints = xMap.sDist()/m_dt;
	if(realpoints>m_size) //wrong axes, just use standart value then
	realpoints = m_size;
	//number of pixels
	int pixels = xMap.pDist();
	if(pixels == 0)
	return;
	if(realpoints>2*pixels) //we have twice more points then screen pixels - need to use resample
	{
	/*
	iterate through pixels - need to draw vertical line
	corresponding to value range change for current pixel
	*/
	//only use points from visible range
	double startPoint = xMap.s1()/m_dt;
	if(startPoint>m_size)
	startPoint = m_size;
	else if(startPoint<0)
	startPoint = 0;
	double endPoint = xMap.s2()/m_dt;
	if(endPoint>m_size)
	endPoint = m_size;
	else if(endPoint<0)
	endPoint = 0;
	double pointSize = endPoint - startPoint;
	if ( pointSize <= 0.0 )
	return;
	//allocate memory
	numberOfPlotPoints = pixels*2;
	points = new QPointF[numberOfPlotPoints];
	//iterate over pixels
	int start = startPoint;
	for(int pixel=0;pixel<pixels;++pixel)
	{
	int end = (((double)pixel+1.0)/pixels)*pointSize + startPoint;
	if(end>endPoint)
	end = endPoint;
	//now find range [min;max] for current pixel
	//using search algorithm for comparison optimization (3n/2 instead of 2n)
	double min = 0.0;
	double max = 0.0;
	int minIndex = 0;
	int maxIndex = 0;
	if(m_data[start]<m_data[start+1])
	{
	min = m_data[start];
	max = m_data[start+1];
	minIndex = start;
	maxIndex = start+1;
	}
	else
	{
	min = m_data[start+1];
	max = m_data[start];
	minIndex = start+1;
	maxIndex = start;
	}
	//compare pairs
	for(int k=start+2;k<end-2;k+=2)
	{
	if(m_data[k]>m_data[k+1])
	{
	if(m_data[k]>max)
	{
	max = m_data[k];
	maxIndex = k;
	}
	if(m_data[k+1]<min)
	{
	min = m_data[k+1];
	minIndex = k+1;
	}
	}
	else
	{
	if(m_data[k+1]>max)
	{
	max = m_data[k+1];
	maxIndex = k+1;
	}
	if(m_data[k]<min)
	{
	min = m_data[k];
	minIndex = k;
	}
	}
	}
	//new start for next iteration
	start = end;
	double p1x = 0.0, p2x = 0.0, p1y = 0.0, p2y = 0.0;
	if(minIndex<maxIndex)
	{
	//rising function, push points in direct order
	p1x = xMap.transform(minIndex*m_dt);
	p2x = xMap.transform(maxIndex*m_dt);
	p1y = yMap.transform( min );
	p2y = yMap.transform( max );
	}
	else
	{
	//falling function, push points in reverse order
	p2x = xMap.transform(minIndex*m_dt);
	p1x = xMap.transform(maxIndex*m_dt);
	p2y = yMap.transform( min );
	p1y = yMap.transform( max );
	}
	//add points to array
	points[pixel*2+0].setX(p1x);
	points[pixel*2+0].setY(p1y);
	points[pixel*2+1].setX(p2x);
	points[pixel*2+1].setY(p2y);
	}
	}
	else //normal draw, not using resample
	{
	//only use points from visible range
	quint32 startPoint = xMap.s1()/m_dt;
	if(startPoint>m_size)
	startPoint = m_size;
	else if(startPoint<0)
	startPoint = 0;
	int endPoint = xMap.s2()/m_dt;
	endPoint+=2;
	if(endPoint>m_size)
	endPoint = m_size;
	int pointSize = endPoint - startPoint;
	if ( pointSize <= 0 )
	return;
	//allocate array for points
	numberOfPlotPoints = pointSize;
	points = new QPointF[numberOfPlotPoints];
	for ( int i = startPoint; i < endPoint; i++ )
	{
	double x = xMap.transform( i*m_dt );
	double y = yMap.transform( m_data[i]);
	points[i - startPoint].setX(x);
	points[i - startPoint].setY(y);
	}
	}
	//draw plot
	painter->setPen(m_plotColor);
	painter->drawPolyline(points, numberOfPlotPoints);
	//free memory
	delete points;
	}

view raw QwtArrayPlotItem_draw.cpp hosted with ❤ by GitHub

Drawing and calculating method. Depending on points we need to plot (that is determined not only array size, but user zoom and plot scales set too), method use resampling or just simple plotting. Point threshold is set as twice horizontal size of plotting canvas.

By the way,  memory allocation/release for pixel data array in each draw() method call is not very good solution from performance perspective, it may be better to check if we really need reallocate buffer (if number of points is equal or less than on previous call, we can use old buffer).

Screenshots of running application

4M points filled with random numbers

After few zooms in

And finally, we can see separate data point

That's all. One more reminder - you can use GitHub link to get full example code.