* * *

Author Topic: Interpolation unit for ColorMapSeries  (Read 3545 times)

wp

  • Hero Member
  • *****
  • Posts: 1018
Interpolation unit for ColorMapSeries
« on: October 26, 2012, 12:09:17 am »
In another thread (http://www.lazarus.freepascal.org/index.php/topic,18405.0.html) there was a question how to interpolate data for displaying them in a ColorMapSeries.

Here is a unit which contains a bilinear, bicubic and spline interpolation of two-dimensional gridded data. The interpolation classes provide a method Calculate which can be called from the corresponding event of the ColorMapSeries.

See the header of the attached MapInterpolation unit for some more detailed instructions on how to use it. Basically you have to provide event handlers for OnNeedX, OnNeedY and OnNeedZ because the interpolation does not know anything about the data to be interpolated. And you have to call Prepare where you pass the size of the grid (CountX and CountY) and where some pre-calculations are performed.

The unit is not specific to TAChart and can also be used in other projects, it does depend on the numlib of FPC, though. Initially I wanted to write a descendant of TColorMapSeries, but I think this solution is more general.

Of course, this unit opens a bunch of new ideas: As can be expected the drawing time can be very long and annoying, in particular in case of panning and if the form is dragged beyond the edge of the monitor. Therefore, I got the idea to buffer the output in a bitmap. The OnCalculate event should be executed only once after resizing/panning/changing of data; its output should be stored in a bitmap which should be painted upon subsequent requests for drawing. For fluent panning, I think the bitmap additionally should be a bit larger than the viewport, and on each MouseMove event the calculation should add the new pixels which will soon come into view and remove those which are moving away. I think the Draw method can be rewritten to achieve this behavior, but I don't know how to be compatible with the ChartDrawers. Another question is how the series gets notified that the chart is repainting because of resizing and panning and other "destructive" events for the bitmap. Finally, maybe this kind of doublebuffering should be added as an option to all TBasicFuncSeries descendants.
« Last Edit: October 26, 2012, 12:52:33 pm by wp »
Lazarus trunk / fpc 2.6.4 / Win32

Ask

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 687
Re: Interpolation unit for ColorMapSeries
« Reply #1 on: October 28, 2012, 08:56:19 pm »
Thank you, this is a substantial piece of work.
Unfortunately, I have little time now, so it will take a while to review.

A few comments from a cursory reading of code:
1) I think that this kind of interpolation is commonly called two-dimensional, so TInterpolation3D name is not optimal.
2) Maybe TInterpolationNeedsValue1Event should be called TInterpolationNeedsCoordEvent?
3) You call OnNeed events multiple times in arbitrary order -- perhaps either a cache
or a single-pass algorithm will be useful for performance, particularly of bilinear interpolation, which is cheap by itself.
4) Do you have references for the algorithms used, especially spline interpolation?
5) If you have time and inclination, please adapt the source to TAChart coding style. I can do it myself, of course.

Quote
The unit is not specific to TAChart and can also be used in other projects, it does depend on the numlib of FPC, though. Initially I wanted to write a descendant of TColorMapSeries, but I think this solution is more general.
Yes, you got this quite right. I have even given some thought to moving this unit outside of TAChart, but decided against it since it will add significant maintenance overhead.

As for your caching ideas -- yes, they are theoretically good, but are not easy to implement. Based on your description, I can see the following plan:
1) Extend drawer interface for saving/restoring images or their parts. I have not yet thought how to achieve this -- consider OpenGL and SVN back-ends...
2) Change notification mechanism so that assignments to logical extent might be distinguished from other changes.
3) Include series into notification mechanism (currently they initiate, but not receive notifications).
4) Use the above to implement caching as you described
5) Make sure that drawing algorithm is independent from initial offset, so that copied part seamlessly integrates with newly-drawn part
(I think I have already taken care of that, but I may have erred).
6) Update drawing algorithm for partial drawing.
7) Introduce some sort of out-of-view caching. Note that this means support for non-rectangular cached areas.

Quote
this kind of doublebuffering should be added as an option to all TBasicFuncSeries descendants.
Actually, it can be applied to all series. The only obstacle is point 6, which must be implemented differently for each series type, even for other functional series.


wp

  • Hero Member
  • *****
  • Posts: 1018
Re: Interpolation unit for ColorMapSeries
« Reply #2 on: October 28, 2012, 11:00:29 pm »
Quote
TInterpolation3D name is not optimal
My motivation for this name was that it is an interpolation which results in a 3D-point. But you are right: it starts from two independent variables. So let us call it TInterpolation2D in the final version.

Quote
Maybe TInterpolationNeedsValue1Event should be called TInterpolationNeedsCoordEvent
No problem

Quote
a single-pass algorithm will be useful for performance
Sorry, what do you mean by that? Regarding performance the spline interpolation is rather squeezed-out, but the two others would benefit from clever ideas.

Quote
Do you have references for the algorithms used
  • Bilinear is from wikipedia (http://en.wikipedia.org/wiki/Bilinear_interpolation).
  • Bicubic is based on "Numerical Recipes in Pascal" by Press et al
  • Spline is basically also from "Numerical Recipes", but after some adaption to the requirements for the numlib 1D spline which result in some speed-up.

Quote
please adapt the source to TAChart coding style
I always try to, but still may miss some items. What in particular do you have in mind?
Lazarus trunk / fpc 2.6.4 / Win32

Ask

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 687
Re: Interpolation unit for ColorMapSeries
« Reply #3 on: October 29, 2012, 12:54:06 pm »
Quote
   
Quote
a single-pass algorithm will be useful for performance
Sorry, what do you mean by that?

Your code supposes that calls to Need{XYZ} functions are cheap.
If this is not so, there will be significant overhead because these functions will be called multiple times on the same coordinates. This situation is similar to chart sources, which are cheap to access by default, but may have expensive variants, like DbSource.

This is a minor point -- can definitely be improved later.

Quote
references for the algorithms used
Are there any on-line versions?
Anyway, please include references in comments, perhaps along with a word your modifications.

Quote
coding style
See specification.

In particular, spaces in declarations and assignments, parameter names, extra parenthesis around conditions.

wp

  • Hero Member
  • *****
  • Posts: 1018
Re: Interpolation unit for ColorMapSeries
« Reply #4 on: October 29, 2012, 11:10:18 pm »
Find in the attachment a revised version of the interpolation unit including references and some brush-up of coding style. Since you want to keep the unit within TAChart I renamed it to TAInterpolation.pas.

Quote
calls to Need{XYZ} functions are cheap... significant overhead because these functions will be called multiple times on the same coordinates
I was assuming that the Need* functions access data in arrays, and I would consider this to be fast in comparison with the many multiplications involved. Of course, if data come from a database lookup things may be different. For the time being I'd tend to put it into the user's responsibility to buffer data in case of speed issues with database access.

My main questions was on what you mean by "single-pass algorithm".

Quote
online versions
Old C and Fortran editions of "Numerical Recipes" are available free at http://www.nr.com/oldverswitcher.html; they are a bit uncomfortable to read. If you prefer a pdf google for "Numerical recipes interpolation" - I don't want to give the direct link here because I am not sure if these are legal online copies.
Lazarus trunk / fpc 2.6.4 / Win32

wp

  • Hero Member
  • *****
  • Posts: 1018
Re: Interpolation unit for ColorMapSeries
« Reply #5 on: December 20, 2012, 10:50:51 pm »
I want to come back to this old thread reagrding the drawing speed of a fully interpolated colormapseries. Would it be possible to put the drawing code into its own thread? This would allow to continue working with the program while the colormap is drawn in the background.
Lazarus trunk / fpc 2.6.4 / Win32

Ask

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 687
Re: Interpolation unit for ColorMapSeries
« Reply #6 on: December 21, 2012, 12:38:42 am »
Quote
put the drawing code into its own thread
LCL design does not allow access to the UI from any thread besides the main one.
So the only option is to draw an image into a buffer, then output it.
However, the notion of "buffer" is dependent on the drawing back-end --
consider cases of OpenGL, SVG and standard canvas.
So the plan could be formulated as follows:
1) Extend drawer interface with PutImage method to allow drawing of arbitrary bitmap
  (this will also be useful for other purposes, such as background images).
2) Implement PutImage at least for a canvas drawer, preferably for others as well.
3) Modify ColorMap to draw image on in-memory bitmap first, then use PutImage.
  If at step (2) there are some drawers left without implementation, this modification must be made optional.
3.1) Depending on the bitmap type, step (3) might already give significant speedup, because I suspect that calling drawer for every pixel is currently a bottleneck.
4) If speedup achieved at step (3) is insufficient, then, at this stage, drawing-to-bitmap code can be extracted to a separate thread.

Ask

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 687
Re: Interpolation unit for ColorMapSeries
« Reply #7 on: January 30, 2013, 03:31:41 pm »
Since r40059, drawing of TColorMapSeries with StepX = StepY = 1 uses intermediate image, which should work much faster.

wp

  • Hero Member
  • *****
  • Posts: 1018
Re: Interpolation unit for ColorMapSeries
« Reply #8 on: January 30, 2013, 10:11:24 pm »
Thank you, that's great. The improvement in the example posted above by a factor of 10 is dramatic!
Lazarus trunk / fpc 2.6.4 / Win32

wp

  • Hero Member
  • *****
  • Posts: 1018
Re: Interpolation unit for ColorMapSeries
« Reply #9 on: January 31, 2013, 09:45:31 am »
Here's an idea to avoid unnecessary calculations, for example, when the chart is partly dragged out of the screen:
  • introduce status variable FBitmapValid
  • initialize as false
  • set to true after calculation of bitmap
  • set to false after "destructive" operations, like resizing of chart, changing of extent, changing of colormap, etc.
  • in Draw, paint the bitmap when FBitmapValid is true, otherwise use the current procedure for recalculation.
Lazarus trunk / fpc 2.6.4 / Win32

Ask

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 687
Re: Interpolation unit for ColorMapSeries
« Reply #10 on: February 02, 2013, 09:51:01 am »
Yes, the idea is generally good. I have had it for a long time, and even posted it, in a brief form.
Here is a more detailed plan:
1) Re-work notification subsystem to support passing detailed information on invalidated part of the chart and reason of invalidation. I have stalled this stage waiting for Observer property to be included in FPC.
However, as I said, this property seems too limited, so there is no reason to wait.
Still, this is substantial task -- additionally, I wanted to use interfaces and refcounting to reduce the amound of bookkeeping necessary to use notifications.
Design input on this subsystem would be appreciated.

2) Introduce a concept of "cache" in drawers. Recent work on adding PutImage is a good first step in this direction.
Note that, while I have already implemented PutImage for Canvas, BGRA and SVG back-ends, there are at least four more back-ends in queue, so even this part is not complete yet.
Also note that, depending on drawer type, cache may not necessarily be a bitmap -- for example, it will be a string for SVG.

3) Introduce "cache layers" in TAChart, connect layers to invalidable parts. Upon redrawing, find the highest valid layer, and redraw only parts above it.
Proposed levels are:
3.1) Background and sidepanes (legend, etc)
3.2) Series and axises, according to ZPosition
3.3) Labels
3.4) Tools

4) Give user control over caching, perhaps also introduce some heuristics for automatic layer selection.

5) After all of the above, some classes of operations might see a speedup:
5.1) Crosshair and similar tools over a complex chart
5.2) Animation of series over a complex background
5.3) Drag-and-drop
5.4) As you noted, repaint after a partial invalidation by external source

6) As a further optimization, after a panning by a small amount chart may use cache of the previous
extent to draw most of the current one, and recalculate only changed part. Cost/benefit ratio of this optimization is, in my estimate, substantially lower compared to the above.

ThB

  • Newbie
  • Posts: 3
Re: Interpolation unit for ColorMapSeries
« Reply #11 on: February 15, 2013, 09:38:16 pm »
Hi there,
I would like to add another interpolation unit for non-gridded (scattered) 3 dimensional data.
The delaunay interpolation code was adapted to Freepascal by Corpsman (www.corpsman.de).
I only made some minor changes by exploit common FPC units. I use it in my own projects favorable.

Attached you will find a demo project showing imported data in a colormap TAChart. The circle points illustrate the data-x-y positions, together with the triangles used.

Thomas

wp

  • Hero Member
  • *****
  • Posts: 1018
Re: Interpolation unit for ColorMapSeries
« Reply #12 on: February 16, 2013, 11:55:30 pm »
Thanks for sharing
Lazarus trunk / fpc 2.6.4 / Win32

 

Recent

Get Lazarus at SourceForge.net. Fast, secure and Free Open Source software downloads