Differential D15514 Diff 41666 libbreezecommon/breezeboxshadowhelper.cpp

Changeset View

Standalone View

libbreezecommon/breezeboxshadowhelper.cpp

Show All 17 Lines
18	* along with this program. If not, see <http://www.gnu.org/licenses/>.	18	* along with this program. If not, see <http://www.gnu.org/licenses/>.
19	*/	19	*/
20		20
21	#include "breezeboxshadowhelper.h"	21	#include "breezeboxshadowhelper.h"
22	#include "config-breezecommon.h"	22	#include "config-breezecommon.h"
23		23
24	#include <QVector>	24	#include <QVector>
25		25
26	#include <fftw3.h>
27
28	#include <cmath>	26	#include <cmath>
29		27
30		28
31	namespace Breeze {	29	namespace Breeze {
32	namespace BoxShadowHelper {	30	namespace BoxShadowHelper {
33		31
34	namespace {	32	namespace {
35	// FFT approach outperforms naive blur method when blur radius >= 64.
36	// (was discovered after doing a lot of benchmarks)
37	const int FFT_BLUR_RADIUS_THRESHOLD = 64;
38
39	// According to the CSS Level 3 spec, standard deviation must be equal to	33	// According to the CSS Level 3 spec, standard deviation must be equal to
40	// half of the blur radius. https://www.w3.org/TR/css-backgrounds-3/#shadow-blur	34	// half of the blur radius. https://www.w3.org/TR/css-backgrounds-3/#shadow-blur
41	// Current window size is too small for sigma equal to half of the blur radius.	35	// Current window size is too small for sigma equal to half of the blur radius.
42	// As a workaround, sigma blur scale is lowered. With the lowered sigma	36	// As a workaround, sigma blur scale is lowered. With the lowered sigma
43	// blur scale, area under the kernel equals to 0.98, which is pretty enough.	37	// blur scale, area under the kernel equals to 0.98, which is pretty enough.
44	// Maybe, it should be changed in the future.	38	// Maybe, it should be changed in the future.
45	const double SIGMA_BLUR_SCALE = 0.4375;	39	const qreal BLUR_SIGMA_SCALE = 0.4375;
46	}	40	}
47		41
48	inline int kernelSizeToRadius(int kernelSize)	42	inline qreal radiusToSigma(qreal radius)
49	{	43	{
50	return (kernelSize - 1) / 2;	44	return radius * BLUR_SIGMA_SCALE;
51	}	45	}
52		46
53	inline int radiusToKernelSize(int radius)	47	inline int boxSizeToRadius(int boxSize)
54	{	48	{
55	return radius * 2 + 1;	49	return (boxSize - 1) / 2;
56	}	50	}
57		51
58	QVector<double> computeGaussianKernel(int radius)	52	class BoxBlurProfile
59	{	53	{
60	QVector<double> kernel;	54	public:
61	const int kernelSize = radiusToKernelSize(radius);	55	BoxBlurProfile(int radius, int passes = 3);
62	kernel.reserve(kernelSize);
63		56
64	const double sigma = SIGMA_BLUR_SCALE * radius;	57	int padding() const;
65	const double den = std::sqrt(2.0) * sigma;	58	QVector<int> boxSizes() const;
66	double kernelNorm = 0.0;
67	double lastInt = 0.5 * std::erf((-radius - 0.5) / den);
68		59
69	for (int i = 0; i < kernelSize; i++) {	60	private:
70	const double currInt = 0.5 * std::erf((i - radius + 0.5) / den);	61	int m_padding;
71	const double w = currInt - lastInt;	62	QVector<int> m_boxSizes;
72	kernel << w;	63	};
73	kernelNorm += w;
74	lastInt = currInt;
75	}
76		64
77	for (auto &w : kernel) {	65	BoxBlurProfile::BoxBlurProfile(int radius, int passes)
78	w /= kernelNorm;	66	{
79	}	67	const qreal sigma = radiusToSigma(radius);
80		68
81	return kernel;	69	// Box sizes are computed according to the "Fast Almost-Gaussian Filtering"
		70	// paper by Peter Kovesi.
		71	int lower = std::floor(std::sqrt(12 * std::pow(sigma, 2) / passes + 1));
		72	if (lower % 2 == 0) {
		73	lower--;
82	}	74	}
83		75
84	// Do horizontal pass of the Gaussian filter. Please notice that the result	76	const int upper = lower + 2;
85	// is transposed. So, the dst image should have proper size, e.g. if the src	77	const int threshold = std::round((12 * std::pow(sigma, 2) - passes * std::pow(lower, 2)
86	// image have (wxh) size then the dst image should have (hxw) size. The	78	- 4 * passes * lower - 3 * passes) / (-4 * lower - 4));
87	// result is transposed so we read memory in linear order.
88	void blurAlphaNaivePass(const QImage &src, QImage &dst, const QVector<double> &kernel)
89	{
90	const int alphaOffset = QSysInfo::ByteOrder == QSysInfo::BigEndian ? 0 : 3;
91	const int alphaStride = src.depth() >> 3;
92	const int radius = kernelSizeToRadius(kernel.size());
93
94	for (int y = 0; y < src.height(); y++) {
95	const uchar *in = src.scanLine(y) + alphaOffset;
96	uchar out = dst.scanLine(0) + alphaOffset + y alphaStride;
97		79
98	for (int x = 0; x < radius; x++) {	80	m_boxSizes.reserve(passes);
99	const uchar *window = in;	81	for (int i = 0; i < passes; ++i) {
100	double alpha = 0.0;	82	m_boxSizes.append(i < threshold ? lower : upper);
101	for (int k = radius - x; k < kernel.size(); k++) {
102	alpha += window kernel[k];
103	window += alphaStride;
104	}
105	*out = static_cast<uchar>(alpha);
106	out += dst.width() * alphaStride;
107	}	83	}
108		84
109	for (int x = radius; x < src.width() - radius; x++) {	85	m_padding = radius;
110	const uchar window = in + (x - radius) alphaStride;
111	double alpha = 0.0;
112	for (int k = 0; k < kernel.size(); k++) {
113	alpha += window kernel[k];
114	window += alphaStride;
115	}
116	*out = static_cast<uchar>(alpha);
117	out += dst.width() * alphaStride;
118	}	86	}
119		87
120	for (int x = src.width() - radius; x < src.width(); x++) {	88	int BoxBlurProfile::padding() const
121	const uchar window = in + (x - radius - 1) alphaStride;	89	{
122	double alpha = 0.0;	90	return m_padding;
123	const int outside = x + radius - src.width();
124	for (int k = 0; k < kernel.size() - outside; k++) {
125	alpha += window kernel[k];
126	window += alphaStride;
127	}
128	*out = static_cast<uchar>(alpha);
129	out += dst.width() * alphaStride;
130	}
131	}
132	}	91	}
133		92
134	// Blur alpha channel of the given image using separable convolution	93	QVector<int> BoxBlurProfile::boxSizes() const
135	// gaussian kernel. Not very efficient with big blur radii.
136	void blurAlphaNaive(QImage &img, int radius)
137	{	94	{
138	const QVector<double> kernel = computeGaussianKernel(radius);	95	return m_boxSizes;
139	QImage tmp(img.height(), img.width(), img.format());
140
141	blurAlphaNaivePass(img, tmp, kernel); // horizontal pass
142	blurAlphaNaivePass(tmp, img, kernel); // vertical pass
143	}	96	}
144		97
145	// Blur alpha channel of the given image using Fourier Transform.	98	void boxBlurPass(const QImage &src, QImage &dst, int boxSize)
146	// It's somewhat efficient with big blur radii.
147	//
148	// It works as follows:
149	// - do FFT on given input image(it is expected, that the
150	// input image was padded before)
151	// - compute Gaussian kernel, pad it to the size of the input
152	// image, and do FFT on it
153	// - multiply the two in the frequency domain(element-wise)
154	// - transform the result back to "time domain"
155	//
156	void blurAlphaFFT(QImage &img, int radius)
157	{	99	{
		100	const int alphaStride = src.depth() >> 3;
158	const int alphaOffset = QSysInfo::ByteOrder == QSysInfo::BigEndian ? 0 : 3;	101	const int alphaOffset = QSysInfo::ByteOrder == QSysInfo::BigEndian ? 0 : 3;
159	const int alphaStride = img.depth() >> 3;
160	const int size = img.width() * img.height();
161		102
162	// Use FFTW's malloc function so the returned pointer obeys any	103	const int radius = boxSizeToRadius(boxSize);
163	// special alignment restrictions. (e.g. for SIMD acceleration, etc)	104	const qreal invSize = 1.0 / boxSize;
164	// See http://www.fftw.org/fftw3_doc/MekernelSizeToRadius(mory-Allocation.html
165	fftw_complex *imageIn = fftw_alloc_complex(size);
166	fftw_complex *imageOut = fftw_alloc_complex(size);
167		105
168	uchar *data = img.scanLine(0) + alphaOffset;	106	const int dstStride = dst.width() * alphaStride;
169	for (int i = 0; i < size; i++) {
170	imageIn[i][0] = *data;
171	imageIn[i][1] = 0.0;
172	data += alphaStride;
173	}
174		107
175	fftw_plan imageFFT = fftw_plan_dft_2d(	108	for (int y = 0; y < src.height(); ++y) {
176	img.height(), img.width(),	109	const uchar *srcAlpha = src.scanLine(y);
177	imageIn, imageOut,	110	uchar *dstAlpha = dst.scanLine(0);
178	FFTW_FORWARD, FFTW_ESTIMATE);
179		111
180	fftw_plan imageIFFT = fftw_plan_dft_2d(	112	srcAlpha += alphaOffset;
181	img.height(), img.width(),	113	dstAlpha += alphaOffset + y * alphaStride;
182	imageOut, imageIn,
183	FFTW_BACKWARD, FFTW_ESTIMATE);
184		114
185	// The computed Gaussian kernel has to have the same size as the input image.	115	const uchar *left = srcAlpha;
186	// Please note that the center of the computed Gaussian kernel is placed	116	const uchar right = left + alphaStride radius;
187	// at the top-left corner and the whole kernel is wrapped around so we read
188	// result in linear order.
189	// Note: the kernel is computed by taking a product of two 1-D Gaussian kernels.
190	QVector<double> kernel(size, 0);
191	const QVector<double> kernel_ = computeGaussianKernel(radius);
192	for (int y = 0; y < kernel_.size(); y++) {
193	const int i = (img.height() + y - radius) % img.height();
194	for (int x = 0; x < kernel_.size(); x++) {
195	const int j = (img.width() + x - radius) % img.width();
196	kernel[j + i * img.width()] = kernel_[x] * kernel_[y];
197	}
198	}
199		117
200	fftw_complex *kernelIn = fftw_alloc_complex(kernel.size());	118	int window = 0;
201	fftw_complex *kernelOut = fftw_alloc_complex(kernel.size());	119	for (int x = 0; x < radius; ++x) {
202		120	window += *srcAlpha;
203	for (int i = 0; i < size; i++) {	121	srcAlpha += alphaStride;
204	kernelIn[i][0] = kernel[i];
205	kernelIn[i][1] = 0.0;
206	}	122	}
207		123
208	fftw_plan kernelFFT = fftw_plan_dft_2d(	124	for (int x = 0; x <= radius; ++x) {
209	img.height(), img.width(),	125	window += *right;
210	kernelIn, kernelOut,	126	right += alphaStride;
211	FFTW_FORWARD, FFTW_ESTIMATE);	127	dstAlpha = static_cast<uchar>(window invSize);
212		128	dstAlpha += dstStride;
213	// Do actual FFT.
214	fftw_execute(imageFFT);
215	fftw_execute(kernelFFT);
216
217	for (int i = 0; i < size; i++) {
218	const double re = imageOut[i][0] * kernelOut[i][0] - imageOut[i][1] * kernelOut[i][1];
219	const double im = imageOut[i][0] * kernelOut[i][1] + imageOut[i][1] * kernelOut[i][0];
220	imageOut[i][0] = re;
221	imageOut[i][1] = im;
222	}	129	}
223		130
224	fftw_execute(imageIFFT);	131	for (int x = radius + 1; x < src.width() - radius; ++x) {
225		132	window += right - left;
226	// Copy result back. Please note, result is scaled by `width x height` so we need to scale it down.	133	left += alphaStride;
227	const double invSize = 1.0 / size;	134	right += alphaStride;
228	data = img.scanLine(0) + alphaOffset;	135	dstAlpha = static_cast<uchar>(window invSize);
229	for (int i = 0; i < size; i++) {	136	dstAlpha += dstStride;
230	data = imageIn[i][0] invSize;
231	data += alphaStride;
232	}	137	}
233		138
234	fftw_destroy_plan(kernelFFT);	139	for (int x = src.width() - radius; x < src.width(); ++x) {
235	fftw_destroy_plan(imageFFT);	140	window -= *left;
236	fftw_destroy_plan(imageIFFT);	141	left += alphaStride;
		142	dstAlpha = static_cast<uchar>(window invSize);
		143	dstAlpha += dstStride;
		144	}
		145	}
		146	}
237		147
238	fftw_free(kernelIn);	148	void boxBlurAlpha(QImage &image, const BoxBlurProfile &profile)
239	fftw_free(kernelOut);	149	{
		150	// Temporary buffer is transposed so we always read memory
		151	// in linear order.
		152	QImage tmp(image.height(), image.width(), image.format());
240		153
241	fftw_free(imageIn);	154	const auto boxSizes = profile.boxSizes();
242	fftw_free(imageOut);	155	for (const int &boxSize : boxSizes) {
		156	boxBlurPass(image, tmp, boxSize); // horizontal pass
		157	boxBlurPass(tmp, image, boxSize); // vertical pass
		158	}
243	}	159	}
244		160
245	void boxShadow(QPainter *p, const QRect &box, const QPoint &offset, int radius, const QColor &color)	161	void boxShadow(QPainter *p, const QRect &box, const QPoint &offset,
		162	int radius, const QColor &color)
246	{	163	{
247	const QSize size = box.size() + 2 * QSize(radius, radius);
248
249	#if BREEZE_COMMON_USE_KDE4	164	#if BREEZE_COMMON_USE_KDE4
250	const qreal dpr = 1.0;	165	const qreal dpr = 1.0;
251	#else	166	#else
252	const qreal dpr = p->device()->devicePixelRatioF();	167	const qreal dpr = p->device()->devicePixelRatioF();
253	#endif	168	#endif
254		169	const BoxBlurProfile profile(radius * dpr, 3);
255	QPainter painter;	170	const QSize size = box.size() + 2 * QSize(profile.padding(), profile.padding());
256		171
257	QImage shadow(size * dpr, QImage::Format_ARGB32_Premultiplied);	172	QImage shadow(size * dpr, QImage::Format_ARGB32_Premultiplied);
258	#if !BREEZE_COMMON_USE_KDE4	173	#if !BREEZE_COMMON_USE_KDE4
259	shadow.setDevicePixelRatio(dpr);	174	shadow.setDevicePixelRatio(dpr);
260	#endif	175	#endif
261	shadow.fill(Qt::transparent);	176	shadow.fill(Qt::transparent);
262		177
		178	QPainter painter;
263	painter.begin(&shadow);	179	painter.begin(&shadow);
264	painter.fillRect(QRect(QPoint(radius, radius), box.size()), Qt::black);	180	painter.fillRect(QRect(QPoint(profile.padding(), profile.padding()), box.size()), Qt::black);
265	painter.end();	181	painter.end();
266		182
267	// There is no need to blur RGB channels. Blur the alpha	183	// There is no need to blur RGB channels. Blur the alpha
268	// channel and then give the shadow a tint of the desired color.	184	// channel and do compositing stuff later.
269	const int radius_ = radius * dpr;	185	boxBlurAlpha(shadow, profile);
270	if (radius_ < FFT_BLUR_RADIUS_THRESHOLD) {
271	blurAlphaNaive(shadow, radius_);
272	} else {
273	blurAlphaFFT(shadow, radius_);
274	}
275		186
276	painter.begin(&shadow);	187	painter.begin(&shadow);
277	painter.setCompositionMode(QPainter::CompositionMode_SourceIn);	188	painter.setCompositionMode(QPainter::CompositionMode_SourceIn);
278	painter.fillRect(shadow.rect(), color);	189	painter.fillRect(shadow.rect(), color);
279	painter.end();	190	painter.end();
280		191
281	QRect shadowRect = shadow.rect();	192	QRect shadowRect = shadow.rect();
282	shadowRect.setSize(shadowRect.size() / dpr);	193	shadowRect.setSize(shadowRect.size() / dpr);
283	shadowRect.moveCenter(box.center() + offset);	194	shadowRect.moveCenter(box.center() + offset);
284	p->drawImage(shadowRect, shadow);	195	p->drawImage(shadowRect, shadow);
285	}	196	}
286		197
287	} // BoxShadowHelper	198	} // BoxShadowHelper
288	} // Breeze	199	} // Breeze