Blender V5.3
source/blender/compositor/algorithms/intern/convolve.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2025 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
5#include <complex>
6#include <numeric>
7
8#include "BLI_array.hh"
9#include "BLI_assert.hh"
11#include "BLI_fftw.hh"
12#include "BLI_index_range.hh"
13#include "BLI_memory_utils.hh"
14#include "BLI_task.hh"
15
16#if defined(WITH_FFTW3)
17# include <fftw3.h>
18#endif
19
20#include "COM_context.hh"
21#include "COM_result.hh"
22#include "COM_utilities.hh"
23
25
26namespace blender::compositor {
27
28void convolve(Context &context,
29 const Result &input,
30 const Result &kernel,
32 const bool normalize_kernel)
33{
34#if defined(WITH_FFTW3)
36 BLI_assert(kernel.type() == ResultType::Float || kernel.type() == ResultType::Color);
38
39 /* Since we will be doing a circular convolution, we need to zero pad the input image by the
40 * kernel size and vice versa to avoid the kernel affecting the pixels at the other side of
41 * image. The kernel size is limited by the image size since it will have no effect on the image
42 * during convolution. */
43 const int2 image_size = input.domain().data_size;
44 const int2 kernel_size = kernel.domain().data_size;
45 const int2 needed_padding_amount = math::max(kernel_size, image_size);
46 const int2 needed_spatial_size = image_size + needed_padding_amount - 1;
47 const int2 spatial_size = fftw::optimal_size_for_real_transform(needed_spatial_size);
48
49 /* The FFTW real to complex transforms utilizes the hermitian symmetry of real transforms and
50 * stores only half the output since the other half is redundant, so we only allocate half of
51 * the first dimension. See Section 4.3.4 Real-data DFT Array Format in the FFTW manual for
52 * more information. */
53 const int2 frequency_size = int2(spatial_size.x / 2 + 1, spatial_size.y);
54
55 constexpr int input_channels_count = 4;
56 const int64_t spatial_pixels_count = int64_t(spatial_size.x) * spatial_size.y;
57 const int64_t frequency_pixels_count = int64_t(frequency_size.x) * frequency_size.y;
58
59 /* A structure to gather all buffers that need to be forward transformed from the real to the
60 * frequency domain. */
61 struct ForwardTransformTask {
62 float *input;
63 std::complex<float> *output;
64 };
65 Vector<ForwardTransformTask> forward_transform_tasks;
66
67 /* Allocate a real buffer and a complex buffer for each of the input channels for the FFT input
68 * and output respectively, then add a forward transform task for it. */
69 Array<float *> image_spatial_domain_channels(input_channels_count);
70 Array<std::complex<float> *> image_frequency_domain_channels(input_channels_count);
71 for (const int channel : image_spatial_domain_channels.index_range()) {
72 image_spatial_domain_channels[channel] = fftwf_alloc_real(spatial_pixels_count);
73 image_frequency_domain_channels[channel] = reinterpret_cast<std::complex<float> *>(
74 fftwf_alloc_complex(frequency_pixels_count));
75 forward_transform_tasks.append(ForwardTransformTask{image_spatial_domain_channels[channel],
76 image_frequency_domain_channels[channel]});
77 }
78
79 BLI_SCOPED_DEFER([&]() {
80 for (const int channel : image_spatial_domain_channels.index_range()) {
81 fftwf_free(image_spatial_domain_channels[channel]);
82 fftwf_free(image_frequency_domain_channels[channel]);
83 }
84 });
85
86 const int kernel_channels_count = kernel.channels_count();
87 const bool is_color_kernel = kernel_channels_count == 4;
88
89 /* Allocate a real buffer and a complex buffer for each of the kernel channels for the FFT input
90 * and output respectively, then add a forward transform task for it. */
91 Array<float *> kernel_spatial_domain_channels(kernel_channels_count);
92 Array<std::complex<float> *> kernel_frequency_domain_channels(kernel_channels_count);
93 for (const int channel : kernel_spatial_domain_channels.index_range()) {
94 kernel_spatial_domain_channels[channel] = fftwf_alloc_real(spatial_pixels_count);
95 kernel_frequency_domain_channels[channel] = reinterpret_cast<std::complex<float> *>(
96 fftwf_alloc_complex(frequency_pixels_count));
97 forward_transform_tasks.append(ForwardTransformTask{
98 kernel_spatial_domain_channels[channel], kernel_frequency_domain_channels[channel]});
99 }
100
101 BLI_SCOPED_DEFER([&]() {
102 for (const int channel : kernel_spatial_domain_channels.index_range()) {
103 fftwf_free(kernel_spatial_domain_channels[channel]);
104 fftwf_free(kernel_frequency_domain_channels[channel]);
105 }
106 });
107
108 /* Create a real to complex and complex to real plans to transform the image to the frequency
109 * domain.
110 *
111 * Notice that FFTW provides an advanced interface as per Section 4.4.2 Advanced Real-data DFTs
112 * to transform all image channels simultaneously with interleaved pixel layouts. But profiling
113 * showed better performance when running a single plan in parallel for all image channels with a
114 * planner pixel format, so this is what we will be doing.
115 *
116 * The input and output buffers here are dummy buffers and still not initialized, because they
117 * are required by the planner internally for planning and their data will be overwritten. So
118 * make sure not to initialize the buffers before creating the plan. */
119 fftwf_plan forward_plan = fftwf_plan_dft_r2c_2d(
120 spatial_size.y,
121 spatial_size.x,
122 image_spatial_domain_channels[0],
123 reinterpret_cast<fftwf_complex *>(image_frequency_domain_channels[0]),
124 FFTW_ESTIMATE);
125 fftwf_plan backward_plan = fftwf_plan_dft_c2r_2d(
126 spatial_size.y,
127 spatial_size.x,
128 reinterpret_cast<fftwf_complex *>(image_frequency_domain_channels[0]),
129 image_spatial_domain_channels[0],
130 FFTW_ESTIMATE);
131
132 BLI_SCOPED_DEFER([&]() {
133 fftwf_destroy_plan(forward_plan);
134 fftwf_destroy_plan(backward_plan);
135 });
136
137 Result convolve_input = context.create_result(input.type());
138 Result convolve_kernel = context.create_result(kernel.type());
139
140 if (context.use_gpu()) {
141 Result input_cpu = input.download_to_cpu();
142 convolve_input.share_data(input_cpu);
143 input_cpu.release();
144
145 Result kernel_cpu = kernel.download_to_cpu();
146 convolve_kernel.share_data(kernel_cpu);
147 kernel_cpu.release();
148 }
149 else {
150 convolve_input.share_data(input);
151 convolve_kernel.share_data(kernel);
152 }
153
154 /* Zero pad the image to the required spatial domain size, storing each channel in planar
155 * format for better cache locality, that is, RRRR...GGGG...BBBB...AAAA. */
156 threading::memory_bandwidth_bound_task(spatial_pixels_count * sizeof(float), [&]() {
157 parallel_for(spatial_size, [&](const int2 texel) {
158 const Color pixel_color = convolve_input.load_pixel_zero<Color>(texel);
159 for (const int channel : IndexRange(input_channels_count)) {
160 float *buffer = image_spatial_domain_channels[channel];
161 const int64_t index = texel.y * int64_t(spatial_size.x) + texel.x;
162 buffer[index] = pixel_color[channel];
163 }
164 });
165 });
166
167 convolve_input.release();
168
169 /* Use doubles to sum the kernel since floats are not stable with threaded summation. We always
170 * use a double4 even for float kernels for generality, in that case, only the first component
171 * is initialized. */
172 threading::EnumerableThreadSpecific<double4> sum_by_thread([]() { return double4(0.0); });
173
174 /* Compute the kernel while zero padding to match the spatial size. */
175 const int2 kernel_center = kernel_size / 2;
176 parallel_for(spatial_size, [&](const int2 texel) {
177 /* We offset the computed kernel with wrap around such that it is centered at the zero
178 * point, which is the expected format for doing circular convolutions in the frequency
179 * domain. */
180 const int2 centered_texel = kernel_center - texel;
181 const int2 wrapped_texel = int2(mod_i(centered_texel.x, spatial_size.x),
182 mod_i(centered_texel.y, spatial_size.y));
183
184 const float4 kernel_value = is_color_kernel ?
185 float4(convolve_kernel.load_pixel_zero<Color>(wrapped_texel)) :
186 float4(convolve_kernel.load_pixel_zero<float>(wrapped_texel));
187 for (const int channel : IndexRange(kernel_channels_count)) {
188 float *buffer = kernel_spatial_domain_channels[channel];
189 buffer[texel.x + texel.y * int64_t(spatial_size.x)] = kernel_value[channel];
190 }
191 sum_by_thread.local() += double4(kernel_value);
192 });
193
194 convolve_kernel.release();
195
196 /* The computed kernel is not normalized and should be normalized, but instead of normalizing the
197 * kernel during computation, we normalize it in the frequency domain when convolving the kernel
198 * to the image since we will be doing sample normalization anyways. This is okay since the
199 * Fourier transform is linear. */
200 const float4 sum = float4(
201 std::accumulate(sum_by_thread.begin(), sum_by_thread.end(), double4(0.0)));
202 const float4 sanitized_sum = float4(sum[0] == 0.0f ? 1.0f : sum[0],
203 sum[1] == 0.0f ? 1.0f : sum[1],
204 sum[2] == 0.0f ? 1.0f : sum[2],
205 sum[3] == 0.0f ? 1.0f : sum[3]);
206 const float4 normalization_factor = normalize_kernel ? sanitized_sum : float4(1.0f);
207
208 /* Transform all necessary data from the real domain to the frequency domain. */
210 forward_transform_tasks.index_range(), 1, [&](const IndexRange sub_range) {
211 for (const int64_t i : sub_range) {
212 fftwf_execute_dft_r2c(
213 forward_plan,
214 forward_transform_tasks[i].input,
215 reinterpret_cast<fftwf_complex *>(forward_transform_tasks[i].output));
216 }
217 });
218
219 /* Multiply the kernel and the image in the frequency domain to perform the convolution. The
220 * FFT is not normalized, meaning the result of the FFT followed by an inverse FFT will result
221 * in an image that is scaled by a factor of the product of the width and height, so we take
222 * that into account by dividing by that scale. See Section 4.8.6 Multi-dimensional Transforms
223 * of the FFTW manual for more information. */
224 const float4 normalization_scale = float(spatial_size.x) * spatial_size.y * normalization_factor;
225 threading::parallel_for(IndexRange(frequency_size.y), 1, [&](const IndexRange sub_y_range) {
226 for (const int64_t channel : IndexRange(input_channels_count)) {
227 const int kernel_channel = is_color_kernel ? channel : 0;
228 std::complex<float> *image_buffer = image_frequency_domain_channels[channel];
229 const std::complex<float> *kernel_buffer = kernel_frequency_domain_channels[kernel_channel];
230 for (const int64_t y : sub_y_range) {
231 for (const int64_t x : IndexRange(frequency_size.x)) {
232 const int64_t index = x + y * int64_t(frequency_size.x);
233 image_buffer[index] *= kernel_buffer[index] / normalization_scale[kernel_channel];
234 }
235 }
236 }
237 });
238
239 /* Transform channels from the frequency domain to the real domain. */
240 threading::parallel_for(IndexRange(input_channels_count), 1, [&](const IndexRange sub_range) {
241 for (const int64_t channel : sub_range) {
242 fftwf_execute_dft_c2r(
243 backward_plan,
244 reinterpret_cast<fftwf_complex *>(image_frequency_domain_channels[channel]),
245 image_spatial_domain_channels[channel]);
246 }
247 });
248
249 Result output_cpu = context.create_result(input.type());
250 output_cpu.allocate_texture(input.domain(), true, ResultStorageType::CPUImage);
251
252 /* Copy the result to the output. */
253 threading::memory_bandwidth_bound_task(input.size_in_bytes(), [&]() {
254 parallel_for(image_size, [&](const int2 texel) {
255 float4 color = float4(0.0f);
256 for (const int channel : IndexRange(input_channels_count)) {
257 const int64_t index = texel.x + texel.y * int64_t(spatial_size.x);
258 color[channel] = image_spatial_domain_channels[channel][index];
259 }
260 output_cpu.store_pixel(texel, Color(color));
261 });
262 });
263
264 if (context.use_gpu()) {
265 Result output_gpu = output_cpu.upload_to_gpu(true);
266 output.share_data(output_gpu);
267 output_gpu.release();
268 }
269 else {
270 output.share_data(output_cpu);
271 }
272 output_cpu.release();
273#else
274 UNUSED_VARS(kernel, normalize_kernel);
275 output.allocate_texture(input.domain());
276 if (context.use_gpu()) {
277 GPU_texture_copy(output, input);
278 }
279 else {
280 parallel_for(output.domain().data_size, [&](const int2 texel) {
281 output.store_pixel(texel, input.load_pixel<float4>(texel));
282 });
283 }
284#endif
285}
286
287} // namespace blender::compositor
#define BLI_SCOPED_DEFER(function_to_defer)
#define UNUSED_VARS(...)
long long int int64_t
#define output
IndexRange index_range() const
Definition BLI_array.hh:371
constexpr IndexRange()=default
void share_data(const Result &source)
Definition result.cc:996
int64_t channels_count() const
Definition result.cc:1180
Result download_to_cpu() const
Definition result.cc:747
T load_pixel_zero(const int2 &texel) const
static ResultType type(gpu::TextureFormat format)
Definition result.cc:337
ColorSceneLinear4f< eAlpha::Premultiplied > Color
Definition COM_result.hh:96
void convolve(Context &context, const Result &input, const Result &kernel, Result &output, const bool normalize_kernel)
void parallel_for(const int2 range, const Function &function)
int context(const bContext *C, const char *member, bContextDataResult *result)
int optimal_size_for_real_transform(int size)
Definition fftw.cc:59
T max(const T &a, const T &b)
void parallel_for(const IndexRange range, const int64_t grain_size, const Function &function, const TaskSizeHints &size_hints=detail::TaskSizeHints_Static(1))
Definition BLI_task.hh:69
void memory_bandwidth_bound_task(const int64_t approximate_bytes_touched, const Function &function)
Definition BLI_task.hh:251
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
MINLINE int mod_i(int i, int n)
__int64 int64_t
Definition BKE_text.h:90
void GPU_texture_copy(gpu::Texture *dst, gpu::Texture *src)
VecBase< float, 4 > float4
VecBase< double, 4 > double4
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float