QwtPlotCurve draw it's full contents without using current zoom information

I'm check Qwt 6.0.1.

I have data from ADC with 200 Hz. Next i'm load to QwtPlot data with one hour from file. That's 3600*200 = 720 000 points. Second i'm install QwtPlotZoomer for zooming and draging plot (In future i'm want to use scrollbar navigation). The problem that QwtPlotCurve draw it's full contents without gettings information from current zoom is VERY SLOW.

I'm find this code that always calling before the curve is draw:

qwt_plot_seriesitem.cpp:

Code:

---

void QwtPlotAbstractSeriesItem::draw( QPainter *painter,
        const QwtScaleMap &xMap, const QwtScaleMap &yMap,
        const QRectF &canvasRect ) const
{
    drawSeries( painter, xMap, yMap, canvasRect, 0, -1 );
}

---

We can see that curve always draw it's full contents (from = 0, to = -1 (size of data)).

Is it possible to workaround this behaviour?

Using the characteristics of the data is the job of the application code - QwtPlotCurve doesn't know about them.

I recommend to derive from QwtSeriesData<QPointF> ( or one of its derived classed ), where you return only points from the current zoom interval: check the pure virtual methods.

To know the current scale interval do:

Code:

---

connect( plot->axisWidget( QwtPlot::xBottom ), SIGNAL( scaleDivChanged() ), this, updateCurrentZoom() );

---

and something like this:

Code:

---

void YourWhatever::updateCurrentZoom()
{
    const QwtScaleDiv scaleDiv = plot->axisScaleDiv( QwtPlot::xBottom );
    updateCurrentZoom( scaleDiv->interval() );
}

---

Uwe

Ok, i'm understand. Now it's works faster for smaller amount of points. Of course it's works SLOW for minimum zoom when user try to see all points. I'm also try to workaround this behaviour using QwtWeedingCurveFitter (Douglas/Peuker algorithm), but that's works slower as compared with disabled fitter. After Douglas/Peuker i see smaller amount of points. It looks like the alogrithm of QwtWeedingCurveFitter working more time than direct drawing operation of full points.

Quote:

---

Originally Posted by Dmitri

Ok, i'm understand. Now it's works faster for smaller amount of points. Of course it's works SLOW for minimum zoom when user try to see all points

---

Check the archive of this forum for "levels of detail".

Using Douglas/Peucker you create ( in advance ) f.e 4 different sets of samples. Depending on the current zoom level one of these sets gets activated. Also enable polygon clipping.

Then you have the effect, that clipping ( the algo is fast ) - or/and your algorithm using the sample order - reduces the number of point when zooming deep and weeding for large scale ranges.

Uwe

Quote:

---

Originally Posted by Uwe

Using the characteristics of the data is the job of the application code - QwtPlotCurve doesn't know about them.

I recommend to derive from QwtSeriesData<QPointF> ( or one of its derived classed ), where you return only points from the current zoom interval: check the pure virtual methods.

To know the current scale interval do:

Code:

---

connect( plot->axisWidget( QwtPlot::xBottom ), SIGNAL( scaleDivChanged() ), this, updateCurrentZoom() );

---

and something like this:

Code:

---

void YourWhatever::updateCurrentZoom()
{
    const QwtScaleDiv scaleDiv = plot->axisScaleDiv( QwtPlot::xBottom );
    updateCurrentZoom( scaleDiv->interval() );
}

---

Uwe

---

Hi
I am interested in doing exactly the same optimization on a zoom. My data is also time domain so for a rectangle x, x + n all I really need to do is return samples x, x+1, x+2, ... x + n.

I understand the concept but not the example code given. I currently have a derived AnalogPlotData class based on QwtSeriesData<QPointF> which stores my plot data. Where however to I add the connect() to get notified of the plot scale change and to what class do I add the updateCurrentZoom() function to limit the from/to parameters to drawSeries(). I tried searching the Qwt sources for references to updateCurrentZoom() but found none (Qwt 6.0.1).

Do I need to derive a version of QwtPlotAbstractSeriesItem as well?

Addituonal guided prods in the right direction much appreciated.

David

It is probably enough to implement:

Code:

---

virtual void AnalogPlotData::setRectOfInterest( const QRectF &rect )
{
   // rect is the visible area in scale coordinates - the scales the corresponding curve is attached to.
 
   ...
}

---

In Qwt 6.0 it gets called automatically when using Qwt from SVN trunk only when the QwtPlotItem::ScaleInterest flag is set.

HTH,
Uwe

PS: internally QwtSyntheticPointData uses this hook too

Hi Uwe

Quote:

---

Originally Posted by Uwe

It is probably enough to implement:

Code:

---

virtual void AnalogPlotData::setRectOfInterest( const QRectF &rect )
{
   // rect is the visible area in scale coordinates - the scales the corresponding curve is attached to.
 
   ...
}

---

In Qwt 6.0 it gets called automatically when using Qwt from SVN trunk only when the QwtPlotItem::ScaleInterest flag is set.

---

Yep, already implemented this, though I was not using it. When I run the code the rectangle parameter passed to the function does indeed define the area selected for zooming. However I don't see how I can use this to limit the from/to range requested by the drawSeries() call. I could use the rectangle to return a NOP sample value, 0.0, for all points outside the rectangle, but would this improve the plotting time as drawSeries() would still call out sample values for indexes 0 to m, even if only x to x+n are the only ones in the rectangle of interest. I could possibly see a speed up if the code around this could then cull the NOP values, is that how it works?

I must be using an older version of Qwt 6 (I think I took the 6.0.1 tag last year some time) as the QwtPlotItem::ScaleInterest is not present in the header. Interestingly however the setRectOfInterest() still gets called. Quite a bit in that header alone has changed, is it worth updating to the trunk?

Quote:

---

Originally Posted by Uwe

HTH,
Uwe

PS: internally QwtSyntheticPointData uses this hook too

---

OK I had a look at the QwtSyntheticPointData use of setRectOfInterest(). If I understand it correctly, the rectangle is used to generate the synthetic data rather than weed out points outside the selected region. Is there not a way given application knowledge of the data set to limit the from/to range?

I am also trying to implement a weeding algorithm to reduce the overall number of points to plot when zoomed out (10,000,000+ sometimes). I have looked at the QwtWeedingCurveFitter as an example and if I understand this correctly, the QwtCurveFitter derived class gets called after the sample data has been converted from sample coordinates to plot coordinates.

In a previous Direct X implementation of our software I found it quite effective to reduce the plot points by taking the min/max of all sample points represented by one plot point (screen pixel) and plot that as a simple vertical line indicating the range of data represented by that one plot point. This I should be able to do from the polygon data passed to the fitCurve() member.

One thing I did notice however was that even when zoomed in, the whole data set if passed to the fitCurve() function. Would it be reasonable at this stage to use the scaleDivChanged() SIGNAL to update the QwtCurveFitter context to enable me to cull all points outside the rectangle of interest? I guess if this is not bad practice I can also use this to cull extra points from the zoomed data as well? Or is the better way to do this to limit the original from/to range?

Thanks

Quote:

---

When I run the code the rectangle parameter passed to the function does indeed define the area selected for zooming. However I don't see how I can use this to limit the from/to range requested by the drawSeries() call.

---

Store the rectangle and use it in your implementation of:

• virtual size_t AnalogPlotData::size() const;
• virtual QPointF AnalogPlotData::sample( size_t i ) const;

Quote:

---

I must be using an older version of Qwt 6 (I think I took the 6.0.1 tag last year some time) as the QwtPlotItem::ScaleInterest is not present in the header. Interestingly however the setRectOfInterest() still gets called.

---

With Qwt 6.0 setRectOfInterest() is always called - with trunk it is called depending on the flag.

Quote:

---

]Quite a bit in that header alone has changed, is it worth updating to the trunk?.

---

Depends on your requirements, but the version in trunk is probably the version with the most new features ever. For curves you find a couple of performance optimizations and when you are not on X11 ( here you have hardware acceleration ) you might be interested in checking the experimental OpenGL canvas.

Quote:

---

]I am also trying to implement a weeding algorithm to reduce the overall number of points to plot when zoomed out (10,000,000+ sometimes). I have looked at the QwtWeedingCurveFitter as an example and if I understand this correctly, the QwtCurveFitter derived class gets called after the sample data has been converted from sample coordinates to plot coordinates.

---

Douglas Peucker is an expensive operation - better don't assign it as fitter to the curve.

Instead I recommend to build a couple of series with different tolerances ( maybe about 5 ) in advance ( using QwtWeedingCurveFitter directly ) and store them in your data class. Then activate one of them according to setRectOfInterest(). Together with clipping ( fast operation ) this should be what you are looking for.

I always wanted to implement a small demo showing how to implement different levels of detail for a huge curve. When you offer me a generator for curve points that make sense for such a demo you would find a working implementation in SVN.

Uwe

Quote:

---

Originally Posted by Uwe

Store the rectangle and use it in your implementation of:

• virtual size_t AnalogPlotData::size() const;
• virtual QPointF AnalogPlotData::sample( size_t i ) const;

---

OK, I think I understand now. The AnalogPlotData would store its actual size as well as the rectangle of interest size. When the ROI is smaller, return that value for size() and for sample() return an offset subset of the data based on where the ROI is in the whole data vector, i.e. if the total size is m and the ROI in the x axis is x to x+n, size() would return n and sample(0), (1), (2), ... would return actual data values data[x], data[x+1], data[x+2], ... instead of data[0], data[1], data[2], .... I can then see that the plot routines would lookup the smaller ROI size() to calculate the from/to values and the sample() function would only return data from the ROI.

I would have to modify some of my existing code and add one or two members to the AnalogPlotData class to return the actual data size and the complete sample data as other parts of my code rely on knowing the real total number of samples and being able to access the whole data array, for example to compute an FFT, etc.

Quote:

---

With Qwt 6.0 setRectOfInterest() is always called - with trunk it is called depending on the flag.


Depends on your requirements, but the version in trunk is probably the version with the most new features ever. For curves you find a couple of performance optimizations and when you are not on X11 ( here you have hardware acceleration ) you might be interested in checking the experimental OpenGL canvas.

---

Are any of the performance improvements likely to benefit Windows?

Quote:

---

Douglas Peucker is an expensive operation - better don't assign it as fitter to the curve.

---

Just to see how the curve fitter class worked I did try attaching this directly and it was indeed very slow.

Quote:

---

Instead I recommend to build a couple of series with different tolerances ( maybe about 5 ) in advance ( using QwtWeedingCurveFitter directly ) and store them in your data class. Then activate one of them according to setRectOfInterest(). Together with clipping ( fast operation ) this should be what you are looking for.

---

The only thing that puts me off using this is the time needed to compute the pyramid of scales prior to displaying the data. As the data sets could be very large (I just calculated the theoretical limit of samples returned by our hardware and it was in excess of 256,000,000, 32bit samples) the time taken to initially plot the data, even if I backgrounded calculation of other pyramid scale levels, would be too large. Once calculated the redraw would indeed be very fast as it would be all cached.

I now have a rough implementation of my min/max of all samples represented by one plot pixel and this works very well even when calculated on each redraw and for all data samples. Once you get multiple line plotted for sub-pixel samples, all you really see if the waveform envelope anyway.

What would be really good would be to push this weeding of sample points back into the AnalogPlotData class as this would eliminate the need for weeding a large data set down before plotting and also reduce the memory requirements of the application as the QPolygonF vector constructed in drawLines() from the sample() data would not need to be as big as the data set (x2 as its x and y coordinates), but only as big as the weeded data set (x2). With the potential number of samples I need to support, the amount of host memory used in storing the actual data and any temp copies is getting quite significant. To do this I would need to know the plot canvas size and also get updates when this changes.

Quote:

---

I always wanted to implement a small demo showing how to implement different levels of detail for a huge curve. When you offer me a generator for curve points that make sense for such a demo you would find a working implementation in SVN.

Uwe

---

If I come up with something simple I will pass it on.

Quote:

---

The only thing that puts me off using this is the time needed to compute the pyramid of scales prior to displaying the data.

---

As you already have the optimization ( according to the ROI ) for the detailled zoom levels in place you can start with a larger tolerance value that should be very successful with weeding out points. How successful depends on the characteristics of your curve, but if it is not noise only you should have a result that is below 10% of the original size. For the following sets ( maybe 1 or 2 more ) you can use the result of the first run.

So there should be no memory problem and performancewise it boils down to the first run only. How long does it take to run the algo for a huge set on your system: more than a second ?

Note that you can split your set into parts and run the algorithm one by one reuniting the results later. This way you can avoid the need of a temporary copy and you can distribute the calculation to different threads. On multicore systems I would expect to have almost a linear effect for each core.

Quote:

---

Are any of the performance improvements likely to benefit Windows?

---

First of all note, that when you have your implentation of the levels of detail I would expect that you are fine with or without optimizations.

Qwt 5.x had a integer based painting engine ( because of Qt3 compatibility ), Qt 6.0 runs on floats. Unfortunatly Qt 4.7 ( raster paint engine ) had a performance issue so that QPainter::drawPolylineF was 3 times slower than QPainter::drawPolyline - for the same values !

So I modified the code in SVN trunk to use integers for paint devices with integer based coordinate systems ( f.e on screen ) and floats for the others ( PDF, SVG ). Having integers ( or rounded floats since Qt 4.8 ) makes it possible to remove duplicates before passing them to Qt. F.e. when drawing a curve with 256,000,000 points to a widget with ~1000 pixels width almost all points will be duplicates.

Here it would also be possible to reduce the memory for the translated points heavily - but this is not done yet ( see qwtToPolylineFiltered in qwt_point_mapper.cpp ). But if you want to avoid a huge temporary buffer you could implement YourCurve::drawSeries calling QwtPlotCurve::drawSeries for intervals of f.e 10000 samples each: from -> from + 10000, from +10000 -> from + 20000 ...

Caching of symbols is another optimization - but this is more important for scatter plots than for your use case.

Using OpenGL is the only way to have hardware accelerated graphics on Windows, but this is more for oscilloscope alike use cases and as QwtPlotGLCanvas is in an experimental state ( f.e no caching yet ) I wouldn't recommend it to you. But you can have a try: setting an OpenGL canvas is one line of code only.

HTH,
Uwe

Quote:

---

Originally Posted by Uwe

As you already have the optimization ( according to the ROI ) for the detailled zoom levels in place you can start with a larger tolerance value that should be very successful with weeding out points. How successful depends on the characteristics of your curve, but if it is not noise only you should have a result that is below 10% of the original size. For the following sets ( maybe 1 or 2 more ) you can use the result of the first run.

So there should be no memory problem and performancewise it boils down to the first run only. How long does it take to run the algo for a huge set on your system: more than a second ?

---

I tried an experiment with one channel run through the QwtWeedingCurveFitter and the other through the min/max weeding routine I have. With 1,000,000 samples the QwtWeedingCurveFitter with a tolerance of 50 (not sure if that's large or small) took about 20+ seconds to weed the 1,000,000 points to about 1557. The routine I used was less than a second and generated about 1600 points (2 x number of plot pixels). This was at full zoom out so no ROI optimisations at this stage. To be fair this was plotting two waveforms, the time domain, which had the weeders attached, and a frequency domain FFT, which had no weeders attached. However the FFT plot time was the same complexity for both time domain plots and from a visual guess was maybe 1-2 seconds to display.

I think the killer for the QwtWeedingCurveFitter routine is the heavy use of qSqrt(). Also from a visual perspective, because I had used what seemed to be a fairly high tolerance, the plot was not all that accurate to the general profile of the data, there were noticable gaps in the plot envelope where sample peaks had obvously been optimised out but where there was data. The data being plotted is simply a sine wave with a slight amount of modulated noise and phase variation to simulate the hardware variations.

Quote:

---

Note that you can split your set into parts and run the algorithm one by one reuniting the results later. This way you can avoid the need of a temporary copy and you can distribute the calculation to different threads. On multicore systems I would expect to have almost a linear effect for each core.

---

Yeh had thought about doing that but given the speed test I tried, even distributing over the 4 cores in my Intel Core i5 would still not be fast enough for the number of points I need. I gave up timing 10,000,000 samples.

Quote:

---

Here it would also be possible to reduce the memory for the translated points heavily - but this is not done yet ( see qwtToPolylineFiltered in qwt_point_mapper.cpp ). But if you want to avoid a huge temporary buffer you could implement YourCurve::drawSeries calling QwtPlotCurve::drawSeries for intervals of f.e 10000 samples each: from -> from + 10000, from +10000 -> from + 20000 ...

---

If you are overloading the drawSeries() could you also restrict the to/from at this level also to solve the ROI data point reduction?

Quote:

---

Using OpenGL is the only way to have hardware accelerated graphics on Windows, but this is more for oscilloscope alike use cases and as QwtPlotGLCanvas is in an experimental state ( f.e no caching yet ) I wouldn't recommend it to you. But you can have a try: setting an OpenGL canvas is one line of code only.

---

What is the magic code loine for this and does it require the latest trunk code?


Thanks for the help.

Quote:

---

I tried an experiment with one channel run through the QwtWeedingCurveFitter and the other through the min/max weeding routine I have. With 1,000,000 samples the QwtWeedingCurveFitter with a tolerance of 50 (not sure if that's large or small) took about 20+ seconds to weed the 1,000,000 points to about 1557.

---

Could you please upload the data set somewhere - I would be interested in checking the DP implementation and playing with alternative algorithms ?

But in the end its obvious that you can implement a faster algorithm easily, when you know that a polygon has increasing x values ( maybe even equidistant ) only !

In general it might be a good idea to introduce an API where the user can pass the information, that the samples are ordered in one direction. At the moment there is only qwtUpperSampleIndex that could use this information, but several other operations could benefit from this information:

• clipping algorithm ( your ROI code would be obsolete )
• bounding rectangle calculation
• closest point lookups
• ...

Quote:

---

If you are overloading the drawSeries() could you also restrict the to/from at this level also to solve the ROI data point reduction

---

Sure.

Maybe its worth to disable polygon clipping for situations, when the curve is vertically also inside of the visible area. But be careful with it as Qt renders before it clips what leads to a horrible performance when the points are far outside the visible area.

Quote:

---

What is the magic code line for this ...

---

As said before: this is more interesting for oscilloscope alike plots that need high refresh rates. With having levels of detail the performance will be by far good enough.

But anyway here is the line:

Code:

---

plot->setCanvas( new QwtPlotGLCanvas() );

---

Uwe

Quote:

---

I tried an experiment with one channel run through the QwtWeedingCurveFitter and the other through the min/max weeding routine I have. With 1,000,000 samples the QwtWeedingCurveFitter with a tolerance of 50 (not sure if that's large or small) took about 20+ seconds to weed the 1,000,000 points to about 1557.

---

Could you please upload the data set somewhere - I would be interested in checking the DP implementation and playing with alternative algorithms ?

But in the end its obvious that you can implement a faster algorithm easily, when you know that a polygon has increasing x values ( maybe even equidistant ) only !

In general it might be a good idea to introduce an API where the user can pass the information, that the samples are ordered in one direction. At the moment there is only qwtUpperSampleIndex that could use this information, but several other operations could benefit from this information:

• clipping algorithm ( your ROI code would be obsolete )
• bounding rectangle calculation
• closest point lookups
• ...

Quote:

---

If you are overloading the drawSeries() could you also restrict the to/from at this level also to solve the ROI data point reduction

---

Sure.

Maybe its worth to disable polygon clipping for situations, when the curve is vertically also inside of the visible area. But be careful with it as Qt renders before it clips what leads to a horrible performance when the points are far outside the visible area.

Quote:

---

What is the magic code line for this ...

---

As said before: this is more interesting for oscilloscope alike plots that need high refresh rates. With having levels of detail the performance will be by far good enough.

But anyway here is the line:

Code:

---

plot->setCanvas( new QwtPlotGLCanvas() );

---

Uwe

---

Added after 4 minutes:

Before it is forgotten: the performance of the Douglas-Peucker algorithm is not linear with increasing n ( worst case : O( n * n ) ).

So it should be possible to improve the performance heavily by splitting up your series in smaller chunks applying the algorithm for each of them. The price for this would be that you lose a possible optimization at the borders of the chunks - what leads to a result with a couple of points more ( depending on the number of chunks ).

Could you please compare your tests with the following code:

Code:

---

QPolygonF fitPolygon( const QPolygonF& points uint chunkSize, double tolerance )
{
    QwtWeedingCurveFitter fitter( tolerance );
 
    QPolygonF fittedPoints;
    for ( int i = 0; i < points.size(); i += chunkSize )
        fittedPoints += fitter.fitCurve(  points.mid( i, qMin( i + chunkSize, points.size() - 1 ) );
 
    return fittedPoints;
}

---

Uwe

---

Added after 6 minutes:

And finally it is possible to speed up the current implementation easily by eliminating the calls of qSqrt by comparing the squares instead.

Uwe

Answering myself:

I have modified the implementation of the algorithm so that it is 3-4 times faster than before. The modifications are in SVN 6.0 and trunk.

Next I have added QwtWeedingCurveFitter::setChunkSize(), where you can control how the algorithm splits the polygon. This modification is available in SVN trunk only.

Next I have tested it with the following polygon:

Code:

---

const int numPoints = 2000000;
 
QPolygonF points;
for ( int i = 0; i < numPoints; i++ )
{
    points += QPointF( i, ::sin( i ) + 0.01 * ( i % 100 ) );
}

---

Now I get the following results on my Atom Board for a tolerance of 0.5 and the following chunkSizes:

Unlimited: 83,403 s -> 641249 points
20000: 13,167s -> 641362 points
2000: 4,504s -> 642208 points
200: 2,806 -> 653027 points

So on a more powerful system ( maybe multithreaded ) you should be able to find a setting that can weed 256,000,000 samples in a reasonable time.

The modified code should need less temporary memory as well.

HTH,
Uwe

Quote:

---

Originally Posted by Uwe

Could you please upload the data set somewhere - I would be interested in checking the DP implementation and playing with alternative algorithms ?

---

To be honest, the data I generate is done pretty much the same way as your code example using sin(). I just add a random variation to the signal magnitude for each sample based on a percentage of the magnitude. A pure sinwave is not an accurate representation of real life ADC hardware, also it's quite difficult when you run our application in repeated capture mode to see the waveform update unless you deliberately introduce some noise.

Quote:

---

But in the end its obvious that you can implement a faster algorithm easily, when you know that a polygon has increasing x values ( maybe even equidistant ) only !

In general it might be a good idea to introduce an API where the user can pass the information, that the samples are ordered in one direction. At the moment there is only qwtUpperSampleIndex that could use this information, but several other operations could benefit from this information:

• clipping algorithm ( your ROI code would be obsolete )
• bounding rectangle calculation
• closest point lookups
• ...

---

This would be an excellent optimisation for more constrained data sets which could really boost plot performance.

Quote:

---

So it should be possible to improve the performance heavily by splitting up your series in smaller chunks applying the algorithm for each of them. The price for this would be that you lose a possible optimization at the borders of the chunks - what leads to a result with a couple of points more ( depending on the number of chunks ).

Could you please compare your tests with the following code:

---

I will have to put some code back to be able to check this. I never actually used the weeder class other than directly in the redraw path, I was trying it out before looking into generating the levels of detail pyramids.

Quote:

---

And finally it is possible to speed up the current implementation easily by eliminating the calls of qSqrt by comparing the squares instead.

---

That should speed things up given the complexity measure for the algorrithm.

Quote:

---

Now I get the following results on my Atom Board for a tolerance of 0.5 and the following chunkSizes:

Unlimited: 83,403 s -> 641249 points
20000: 13,167s -> 641362 points
2000: 4,504s -> 642208 points
200: 2,806 -> 653027 points

So on a more powerful system ( maybe multithreaded ) you should be able to find a setting that can weed 256,000,000 samples in a reasonable time.

The modified code should need less temporary memory as well.

Uwe

---

Wow, excellent speed up there. I guess that is also without the qSqrt().

I am not sure which way to go on optimising my redraw at the moment. I am getting very good speedup by using my min/max QwtCurveFitter without any additional level of detail pyramids. I had to undo the ROI mods to my plot data class as I was getting very weird artifacts, I think due to the rest of the app code using the size() and sample() members but expecting these to return the original data set size. I tried to only store one copy of the sample data and so the FFT, etc. processing routines use the raw sample data directly out of the plot data object as well as the plot widgets.
Now I have the weeding class stable I can try putting the ROI optimisation back in for zoom in operations, though I am tempted to maybe acheive this through overriding the drawSeries() member.
I also want to put add a hook into the code to change the plot style from line (needed to enable the weeder) to step for plots where we don't need to weed out points as the step representation looks better for sample data as its more obvious for the user that the y value is constant for the sample duration, then changes for the next sample.

Qwt is a cracking library, thanks for all the hard work and support.

David

Quote:

---

This would be an excellent optimisation for more constrained data sets which could really boost plot performance.

---

Well, I wouldn't call it a "boost":

The clipping algo is fast ( 261 ms on my Atom board for 2000000 points - this is basically the time your ROI code would optimze ! ) - the calculation of the bounding rectangle is fast too and the result is cached.

The main optimization would be for lookups f.e when you want to display the coordinates of a point under the mouse. But here something like a quadtree would be better for most use cases as it works for any type of data.

Quote:

---

I guess that is also without the qSqrt().

---

The elimination of qSqrt from the inner loop made a factor of 3-4 - independent of the chunk size.

Quote:

---

I am not sure which way to go on optimising my redraw at the moment.

---

Well for 256,000,000 samples I would say whatever you can do in advance ( not again and again for every replot ! ) should be done.

Quote:

---

I am getting very good speedup by using my min/max QwtCurveFitter without any additional level of detail pyramids.

---

An algorithm that is fast enough for millions of points without slowing down a replot significantly - sounds interesting, can you explain the idea or show some code ?

Uwe

Quote:

---

Originally Posted by Uwe

An algorithm that is fast enough for millions of points without slowing down a replot significantly - sounds interesting, can you explain the idea or show some code ?

Uwe

---

OK here is my code. It's not 100% finished at the moment and has a couple of unresolved issues but it mostly works.

The basic principal is as follows:

• If the number of sample points is greater than the number of plot pixels...
  
  • Loop over each plot pixel...
    
    • Loop over all samples which would map to a single plot pixel and calculate the min and max range of the sample values.
    • Define two vertices forming a vertical line from (x,min) to (x,max) where x is the plot x coordinate position.
• If the number of samples is less than the number of pixels, plot as normal...

This should at most give you n * 2 vertices where n is the number of plot pixels. It's also only order O(n).

This was how the original routine we used under DirectX was structured. However as I have had to work the algorithm into the framework of the QwtCurveFitter I have had to derive indirectly a few things such as the number of display pixels, etc. which have introduced a few rounding errors, one which I need to trap at line 39.

Also the data it works on here is already in plot coordinate space, whereas my original algorithm worked in sample space and generated the plot coordinates. THis was a more straighforward.

I am thinking of rewriting this a bit so it steps through the points min/max-ing each sample which falls within a integer pixel positions, rather than using the samples per pixel to determine the sample indexes to min/max over.

This still does not solve the potential memory usage issue I have when the plot is fully zoomed out as every sample point is mapped to a QPolygonF in plot coordinate space, that memory together with the original data and an FFT copy, times 3+ channels adds up. I currently get a memory allocation exception in QwtPlotCurve when allocating the QPolygonF polyline(size) with 67m, though implementing the ROI should make this better when zooming in.

I could implement YourCurve::drawSeries() calling QwtPlotCurve::drawSeries() as you suggested and then process the the ROI in chunks to save memory. This would also allow me to apply the ROI during a zoom. I had also wandered if I could have my data class return my weeded points, as with the pyramid of detail suggestion, though I will need to fix my other code which also calls the sample data out of the class but expects the full original data to be there.

Cheers for the help.

Code:

---

QPolygonF PlotDataFitter::fitCurve(const QPolygonF &points) const
{
    double samplesPerPixel;
    unsigned int numPixels;
    unsigned int prevIndex, currIndex, xIndex, sIndex = 0;
    float min, max;
 
    // Get a pointer to the raw point data.
    const QPointF *p = points.data();
 
    // Calculate the number of samples per pixel. This assumes equidistant
    // data points along the x-axis and as such means we just need to work out
    // the distance between the first two points.
    samplesPerPixel = abs(1.0 / (p[1].x() - p[0].x()));
 
    // Determine the number of plot pixels. We do this by looking to see what
    // the last x coordinate is in the points vector. As this has been
    // transformed from sample coordinates to screen coordinates this is also
    // the number of plot pixels, though there may be a better way to do this.
    numPixels = (unsigned int) ((p[points.size() - 1].x() - p[0].x()) + 0.5F);
 
    // Set the previous transformed sample index.
    prevIndex = 0;
 
    // Only weed out points when we exceed the points per pixel threshold.
    if (samplesPerPixel > (double) m_samplesPerPixel)
    {
        // Construct a vector to hold the stripped point values. As we only plot
        // one vertical line per plot pixel we only need twice the number of pixels.
        QPolygonF stripped(numPixels * 2);
 
        // Loop over each plot pixel and create the polygon to plot for that
        // pixel.
        for (xIndex = 1; xIndex <= numPixels; xIndex++)
        {
            // Calculate the current sample index for the plot pixel.
            currIndex = (unsigned int) (((double) xIndex * samplesPerPixel) + 0.5);
            if (currIndex > (unsigned int) (points.size() - 1))
                currIndex = points.size() - 1;
 
            // Initialise the min and max values.
            min = numeric_limits<float>::max();
            max = numeric_limits<float>::min();
 
            // Loop over the range of samples represented by one plot pixel and
            // calculate the min/max y value.
            for (unsigned int x = prevIndex; x < currIndex; x++)
            {
                min = ((min > p[x].y()) ? p[x].y() : min);
                max = ((max < p[x].y()) ? p[x].y() : max);
            }
 
            // Draw the vertical line for the min/max value at this plot pixel.
            stripped[sIndex++] = QPointF(p[prevIndex].x(), min);
            stripped[sIndex++] = QPointF(p[prevIndex].x(), max);
 
            // Move the range we min/max over for next time.
            prevIndex = currIndex;
        }
 
        // Adjust the stripped vector to the correct size if its not already.
        stripped.resize(sIndex);
 
 
        // Return the stripped points.
        return stripped;
    }
 
 
    // No stripping to be done, return original points.
    return points;
}

---

Quote:

---

Originally Posted by mike_the_tv

I could implement YourCurve::drawSeries() calling QwtPlotCurve::drawSeries() as you suggested and then process the the ROI in chunks to save memory. This would also allow me to apply the ROI during a zoom.

---

Success, well almost but I will come to that.

I derived a class based on QwtPlotCurve and overrode drawSeries(). In there I used the QwtScaleMap xMap to determine the ROI (not sure if this is legitimate but it seems to work) and can use this to set appropriate values for to and from. I can also use the ROI size and the canvas size to work out if I will be plotting multiple samples onto a single plot pixel and if so repeatedly call QwtPlotCurve::drawSeries() on sub-regions of the to/from range to limit the temporary memory usage for the QPolygonF vertices before they get culled by the curve fitter weeding algorithm.

I also overrode drawCurve() to remove the resetting of the to/from values if the Fitted attribute is set as my curve titter does not need the entire data set for reference.

As I said all works excellently. 10,000,000 samples at full zoom out plot in less than a second (in debug) and use minimal extra memory and temp storage. Zooming in gets increasingly faster as the data set called out of the data object get smaller due to the ROI.

I have now only one problem which I don't know how to fix. One of the data sets I want to display can be plotted as magnitude against sample number or magnitude against time (given that the data is samples by a periodic clock running at some set rate). The Qt GUI has an option to switch the x axis parameter from samples to time therefore. This changes the scale in the axis appropriately.

When I implemented this I did it by exposing a scale member function interface to my data class such that when the axis style is changed I calculate the scale factor for the x axis data and set that in my data class. This scale factor is used to dynamically scale the sample values returned by sample() and the rectangle from bountingRect(). Therefore when the sample values are called out by increasing index the data class returns effectively a point such as (index * scale, y) for increasing index. Without the above modifications this worked fine as regardless of the scale factor I used, all data points would be called out from index 0 to the size of the data set returned by size(), which I did not modify by my scale factor. This generated a vector of vertices ranging from 0 to the max value for the scaled data size.

Now however when I try to apply the plot optimisations, the ROI I derive from the QwtScaleMap is based on the data range I am guessing my data class returns via boundingRect(), which is say 0 to 0.1 seconds rather than the sample indexes 0 to 1023. Unfortunately in the drawSeries() member I cannot access the scale factors of my derived data class and so cannot convert the data range back from time to sample index.

This makes me wonder whether I should be doing the data scaling with say a QwtScaleMap for my sample index to time conversion rather than hiding it in my data class, however the scale maps I see in the drawSeries() seem to be more to do with transforming data values to plot coordinates. I sort of have two transforms I want to do, sample index to time value, then time value to plto coordinates.

Am I missing some obvious Qwt feature to make this easier?

Cheers

Quote:

---

In there I used the QwtScaleMap xMap to determine the ROI (not sure if this is legitimate but it seems to work) ...

---

Usually the maps are initialized with the scale boundaries, but it doesn't need to be like this. The following code is always correct:

Code:

---

roi = QwtScaleMap::invTransform( xMap, yMap, canvasRect );

---

Quote:

---

Unfortunately in the drawSeries() member I cannot access the scale factors of my derived data ...

---

Why not - the curve has a getter for the data object and all what is missing is a dynamic_cast.

Uwe

Quote:

---

Originally Posted by Uwe

Usually the maps are initialized with the scale boundaries, but it doesn't need to be like this. The following code is always correct:

Code:

---

roi = QwtScaleMap::invTransform( xMap, yMap, canvasRect );

---

---

That seems like a better way to do it than what I had.

Quote:

---

Why not - the curve has a getter for the data object and all what is missing is a dynamic_cast.

---

Well I did think about doing this when I found the data() member. The only slight problem I had was that the data class I implemented, based on QwtSeriesData<QPointF>, was templated for my underlying data type (int and float). Given the class was templated I could not just dynamic_cast it without knowing the template type so I disregarded that method as a workable solution at that time as I did not want to specialise the overridden QwtPlotCurve class.

As it turns out, needing the data's internal scale factor rather specialises the curve class to the data class anyway, so what I have done is used the typeid() to determine which templated type it is and dynamic_cast the data object appropriately.

With that it is not working really well. 10,000,000 points plot in sub-second times on my Core i5. Zooming is also fast and gets quicker the tigher you go, so the ROI is really helping there.

Thanks for all you help. Look forward to the next revision of Qwt.