Improve heatmap performance using GPU rendering

[marcizhu]

I've been thinking about this for a while and I think we could greatly improve the performance of heatmaps if we change the way the rendering works. If I'm not mistaken, right now the CPU computes the color for each pixel, saving that data in a 2D array of some sort and then it sends to the GPU a bunch of quads to render, each one with its color and coordinates. This approach is quite effective, fast enough for most uses but it uses the CPU when in reality we could do 90% of that work on the GPU.

This is what I suggest: each colormap (the 1D array of colors indicating the range of colors we should use to render the colormap) will be stored on the GPU as a texture1D. The input data (the raw 2D array of points) will be a texture2D of float/int (as desired, probably float), and using a pretty basic fragment shader we render the heatmap onto an OpenGL framebuffer. Finally, instead of rendering all the quads as we do now, we just need to render a single quad and use that framebuffer as a texture. As far as I know, implot does already support rendering images on plots, so this change shouldn't be too hard to implement.

The proposed solution has quite some benefits, mainly:

1. Reduced number of vertices for heatmaps. As far as I know, for a 256x256 heatmap, we now need 256x256x3x2 vertices. That's ~393k vertices! The new approach only needs 4 vertices, but requires an additional framebuffer of size 256x256.
2. Because we are passing the raw data to the GPU, we can let OpenGL normalize it for us (so no need to calculate the minimum and maximum on the CPU) and also the color selection and interpolation will be done on the GPU, improving performance and removing a lot of work from the CPU.
3. Storing the colormap as a 1D texture on the GPU allows the user to mix and match formats for the colormap, so no more having to choose between uint32_t RGBA or four float32 for colors.
4. Reduced memory usage. Now, colormaps are interpolated and stored in memory to improve CPU performance (thus using a constant memory access time instead of a more expensive linear interpolation for each pixel). By using the GPU, we don't need to store this array, and instead we can rely on the GPU for interpolation (maybe?).
5. Because we are rendering a texture, we can allow the user to choose between a linear or nearest filter. In some cases it might be desired to present a smooth heatmap without having to use thousands and thousand of points, while in other cases it might be desired to render the heatmap as is, without any interpolation.

However, I know this change has its own drawbacks. For example:

1. This solution is only for OpenGL. Supporting other backends (such as DirectX) would require a similar implementation for the desired platform. As a small fix, we could "fall back" to the current approach on unsupported platforms.
2. For small heatmaps, probably the overhead of an additional draw call isn't worth it. Real-world testing will be needed.
3. We would need to support loading & basic handling of shaders and framebuffers. Even though the shader needed for this is a one-liner (it would be something like pixel = texture(colormap, mix(0.0f, 1.0f, texture(heatmap_data, coords)));) we still need to handle creation, destruction and binding of shaders and framebuffers. This con is not so bad though, as it would open the door to other similar optimizations for other kinds of plots, or even adding post-processing effects if the user wants to.
4. Transformations such as Lin-Log, Log-Lin or Log-Log must be implemented in the shader, and selected through a shader uniform (probably a couple of booleans, each one specifying if the X or Y axis is logarithmic or not).

As usual I'm open to any feedback, discussion or proposal. Maybe this is a dumb idea, but maybe it would allow us to draw massive heatmaps with close to zero CPU usage, less memory and fully taking advantage of the GPU rendering capabilities :D
Let me know what you guys think! 😄

[epezent]

@marcizhu , in general I think your idea is quite good, and I am open to having backend-specific, shader-accelerated support for our plotting functions so long as we maintain a pure ImGui fallback. Similarly, GPU accelerations could be made on thick line triangulation as well (#185 is tangentially related). I think the logical approach is to start slow, and try to build a few examples that work in OpenGL and then maybe we can explore other backends in the future.

I'd love to explore this together, so let's keep the discussion going. I've been meaning to explore custom ImGui draw commands, as I think this is our path forward to inserting platform specific drawing code. Are you at all familiar with the process?

[epezent]

No worries Marc. I'm swamped right now too :)

This is really impressive work so far. I'm excited to see how it will fit into ImPlot!

Regarding the transformations -- there are 4 "Transformers" that take in plot points and output pixel coordinates. LinLin is regular linear scale for both x and y. LogLin is logarithmic on x, and linear on y. And so on. The math involved can be found in the transformer objects here:

implot/implot_items.cpp

Lines 421 to 472 in 3109940

	// Transforms points for linear x and linear y space
	struct TransformerLinLin {
	TransformerLinLin() : YAxis(GetCurrentYAxis()) {}
	// inline ImVec2 operator()(const ImPlotPoint& plt) const { return (*this)(plt.x, plt.y); }
	inline ImVec2 operator()(const ImPlotPoint& plt) const {
	ImPlotContext& gp = *GImPlot;
	return ImVec2( (float)(gp.PixelRange[YAxis].Min.x + gp.Mx * (plt.x - gp.CurrentPlot->XAxis.Range.Min)),
	(float)(gp.PixelRange[YAxis].Min.y + gp.My[YAxis] * (plt.y - gp.CurrentPlot->YAxis[YAxis].Range.Min)) );
	}
	const int YAxis;
	};
	// Transforms points for log x and linear y space
	struct TransformerLogLin {
	TransformerLogLin() : YAxis(GetCurrentYAxis()) {}
	inline ImVec2 operator()(const ImPlotPoint& plt) const {
	ImPlotContext& gp = *GImPlot;
	double t = ImLog10(plt.x / gp.CurrentPlot->XAxis.Range.Min) / gp.LogDenX;
	double x = ImLerp(gp.CurrentPlot->XAxis.Range.Min, gp.CurrentPlot->XAxis.Range.Max, (float)t);
	return ImVec2( (float)(gp.PixelRange[YAxis].Min.x + gp.Mx * (x - gp.CurrentPlot->XAxis.Range.Min)),
	(float)(gp.PixelRange[YAxis].Min.y + gp.My[YAxis] * (plt.y - gp.CurrentPlot->YAxis[YAxis].Range.Min)) );
	}
	const int YAxis;
	};
	// Transforms points for linear x and log y space
	struct TransformerLinLog {
	TransformerLinLog() : YAxis(GetCurrentYAxis()) {}
	inline ImVec2 operator()(const ImPlotPoint& plt) const {
	ImPlotContext& gp = *GImPlot;
	double t = ImLog10(plt.y / gp.CurrentPlot->YAxis[YAxis].Range.Min) / gp.LogDenY[YAxis];
	double y = ImLerp(gp.CurrentPlot->YAxis[YAxis].Range.Min, gp.CurrentPlot->YAxis[YAxis].Range.Max, (float)t);
	return ImVec2( (float)(gp.PixelRange[YAxis].Min.x + gp.Mx * (plt.x - gp.CurrentPlot->XAxis.Range.Min)),
	(float)(gp.PixelRange[YAxis].Min.y + gp.My[YAxis] * (y - gp.CurrentPlot->YAxis[YAxis].Range.Min)) );
	}
	const int YAxis;
	};
	// Transforms points for log x and log y space
	struct TransformerLogLog {
	TransformerLogLog() : YAxis(GetCurrentYAxis()) {}
	inline ImVec2 operator()(const ImPlotPoint& plt) const {
	ImPlotContext& gp = *GImPlot;
	double t = ImLog10(plt.x / gp.CurrentPlot->XAxis.Range.Min) / gp.LogDenX;
	double x = ImLerp(gp.CurrentPlot->XAxis.Range.Min, gp.CurrentPlot->XAxis.Range.Max, (float)t);
	t = ImLog10(plt.y / gp.CurrentPlot->YAxis[YAxis].Range.Min) / gp.LogDenY[YAxis];
	double y = ImLerp(gp.CurrentPlot->YAxis[YAxis].Range.Min, gp.CurrentPlot->YAxis[YAxis].Range.Max, (float)t);
	return ImVec2( (float)(gp.PixelRange[YAxis].Min.x + gp.Mx * (x - gp.CurrentPlot->XAxis.Range.Min)),
	(float)(gp.PixelRange[YAxis].Min.y + gp.My[YAxis] * (y - gp.CurrentPlot->YAxis[YAxis].Range.Min)) );
	}
	const int YAxis;
	};

You can see that they need the size of the plot in plot coordinates and pixel coordinates, as well as a few cached computations (e.g. gp.Mx, gp.My, gp.LogDenX, gp.LogDenY). Those get pre-computed in 'BeginPlot` since they won't change once items begin.

I think you'd need to write a fragment shader that takes in these values as uniforms to achieve the scaling. For now though, I would say it's a rather niche thing to do any lograthmic scaling on a heatmap. If it does happen, we can default back to the current method. I think we should focus on integrating what you have so far.

[marcizhu]

Yeah, I agree with you. For now I think I will focus on integrating my work with ImPlot and once that is done maybe I can try to implement other features such as the logarithmic density and such. Thanks for the details though, it will be useful once I begin working on that :D

[marcizhu]

@epezent I got it working finally!! It was easier than I thought initially. I will do some cleanup now, commit everything and open a PR as soon as possible. There are some improvements we can do to this and some things left to implement but the basics are implemented and working. As a small performance test, I ran your spectrogram demo on a small Linux computer with integrated GPU. It used to take ~45ms per frame (22 FPS or so) and required 12 draw calls to draw that heatmap. It now renders the entire heatmap in a single draw call and the FPS are capped at 60 due to VSync.

I will do more benchmarks and let you know the performance gains of this on the PR! 😄

[epezent]

AWESOME!!! Can't wait to see this PR! I'd like to see some numbers without vsync on, and some side by side comparisons with the current implementation.

Congrats. This is great work.

[marcizhu]

Thank you so much! I think I will have the PR ready in like an hour or two at most.