Blender V5.3
node_geo_grid_solve_poisson.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 "BLI_math_vector.hh"
6
8
10#include "UI_resources.hh"
11
12#include "node_geometry_util.hh"
13
14#ifdef WITH_OPENVDB
15# include "openvdb/tools/PoissonSolver.h"
16#endif
17
19
26
29 "RELATIVE",
30 0,
31 "Relative",
32 "Threshold relative to the maximum absolute value of the input grid (infinity norm)"},
34 "ABSOLUTE",
35 0,
36 "Absolute",
37 "Threshold based on the maximum absolute value of the solution (infinity norm)"},
38 {0, nullptr, 0, nullptr, nullptr},
39};
40
41enum class Boundary {
47 Mixed,
48};
49
51 {int(Boundary::Fixed),
52 "FIXED",
53 0,
54 "Fixed",
55 "Dirichlet boundary condition, specify the solution value for all exterior boundary voxels"},
57 "GRADIENT",
58 0,
59 "Gradient",
60 "Neumann boundary condition, specify gradient for all exterior boundary voxels"},
61 {int(Boundary::Mixed),
62 "MIXED",
63 0,
64 "Mixed",
65 "Select between fixed and normal boundary condition"},
66 {0, nullptr, 0, nullptr, nullptr},
67};
68
70{
71 b.use_custom_socket_order();
72 b.allow_any_socket_order();
73
74 b.add_output<decl::Float>("Solution"_ustr)
75 .structure_type(StructureType::Grid)
76 .description("Solution to the Poisson equation");
77 b.add_output<decl::Bool>("Success"_ustr).description("If the solver converged successfully");
78 b.add_output<decl::Int>("Iterations"_ustr).description("Number of iterations performed");
79 b.add_output<decl::Float>("Absolute Error"_ustr)
80 .description("Final absolute error of the solution");
81 b.add_output<decl::Float>("Relative Error"_ustr)
82 .description("Final relative error of the solution");
83
84 b.add_input<decl::Float>("Grid"_ustr)
85 .hide_value()
86 .structure_type(StructureType::Grid)
87 .description("Right-hand side of the Poisson equation");
88 b.add_input<decl::Int>("Max Iterations"_ustr)
89 .default_value(100)
90 .min(1)
91 .max(10000)
92 .description("Maximum number of solver iterations");
93 b.add_input<decl::Float>("Error Threshold"_ustr)
94 .min(0.0f)
95 .default_value(1e-3f)
96 .description("Error threshold below which a solution is considered valid");
97 b.add_input<decl::Menu>("Threshold Mode"_ustr)
98 .static_items(threshold_mode_items)
99 .expanded()
101 .short_label("Threshold"_ustr)
102 .description("Mode that defines how the error threshold is interpreted");
103
104 b.add_input<decl::Menu>("Boundary"_ustr)
105 .static_items(boundary_items)
107 .description("Boundary conditions for the solution between active and inactive voxels");
108 b.add_input<decl::Float>("Boundary Value"_ustr)
109 .structure_type(StructureType::Field)
110 .hide_value()
111 .usage_by_menu("Boundary"_ustr, {int(Boundary::Fixed), int(Boundary::Mixed)});
112 b.add_input<decl::Vector>("Boundary Gradient"_ustr)
113 .structure_type(StructureType::Field)
114 .hide_value()
115 .usage_by_menu("Boundary"_ustr, {int(Boundary::Gradient), int(Boundary::Mixed)});
116 b.add_input<decl::Float>("Boundary Factor"_ustr)
117 .subtype(PROP_FACTOR)
118 .min(0.0f)
119 .max(1.0f)
120 .structure_type(StructureType::Field)
121 .usage_by_menu("Boundary"_ustr, int(Boundary::Mixed))
122 .description("Mix factor between boundary conditions (0=value, 1=gradient)");
123
124 PanelDeclarationBuilder &p = b.add_panel("Debug"_ustr).default_closed(true);
125 p.add_output<decl::Float>("Debug Boundary Value"_ustr)
126 .structure_type(StructureType::Grid)
127 .usage_by_menu("Boundary"_ustr, {int(Boundary::Fixed), int(Boundary::Mixed)});
128 p.add_output<decl::Vector>("Debug Boundary Gradient"_ustr)
129 .structure_type(StructureType::Grid)
130 .usage_by_menu("Boundary"_ustr, {int(Boundary::Gradient), int(Boundary::Mixed)});
131 p.add_output<decl::Float>("Debug Boundary Factor"_ustr)
132 .structure_type(StructureType::Grid)
133 .usage_by_menu("Boundary"_ustr, int(Boundary::Mixed));
134}
135
136#ifdef WITH_OPENVDB
137
138struct DirichletBoundaryOp {
139 const openvdb::FloatGrid::ConstAccessor value_accessor_;
140 const float value_scale_;
141
142 DirichletBoundaryOp(const openvdb::FloatGrid &value_grid)
143 : value_accessor_(value_grid.getConstAccessor()),
144 value_scale_(math::rcp(math::square(value_grid.voxelSize().x())))
145 {
146 }
147
148 void operator()(const openvdb::Coord & /*ijk*/,
149 const openvdb::Coord &neighbor,
150 double &source,
151 double &diagonal) const
152 {
153 const float value = value_accessor_.getValue(neighbor);
154 diagonal -= 1.0;
155 source -= value * value_scale_;
156 };
157};
158
159struct NeumannBoundaryOp {
160 const openvdb::Vec3SGrid::ConstAccessor gradient_accessor_;
161 const openvdb::Mat3s gradient_transform_;
162
163 NeumannBoundaryOp(const openvdb::Vec3SGrid &gradient_grid)
164 : gradient_accessor_(gradient_grid.getConstAccessor()),
165 gradient_transform_(
166 gradient_grid.transform().baseMap()->getAffineMap()->getMat4().getMat3().inverse())
167 {
168 }
169
170 void operator()(const openvdb::Coord &ijk,
171 const openvdb::Coord &neighbor,
172 double &source,
173 double & /*diagonal*/) const
174 {
175 const openvdb::math::Vec3s normal = neighbor.asVec3s() - ijk.asVec3s();
176 const openvdb::math::Vec3s gradient = gradient_transform_.transform(
177 gradient_accessor_.getValue(neighbor));
178 source -= gradient.dot(normal);
179 };
180};
181
182struct MixedBoundaryOp {
183 const openvdb::FloatGrid::ConstAccessor value_accessor_;
184 const openvdb::Vec3SGrid::ConstAccessor gradient_accessor_;
185 const openvdb::FloatGrid::ConstAccessor factor_accessor_;
186 const float value_scale_;
187 const openvdb::Mat3s gradient_transform_;
188
189 MixedBoundaryOp(const openvdb::FloatGrid &value_grid,
190 const openvdb::Vec3SGrid &gradient_grid,
191 const openvdb::FloatGrid &factor_grid)
192 : value_accessor_(value_grid.getConstAccessor()),
193 gradient_accessor_(gradient_grid.getConstAccessor()),
194 factor_accessor_(factor_grid.getConstAccessor()),
195 value_scale_(math::rcp(math::square(value_grid.voxelSize().x()))),
196 gradient_transform_(
197 gradient_grid.transform().baseMap()->getAffineMap()->getMat4().getMat3().inverse())
198 {
199 }
200
201 void operator()(const openvdb::Coord &ijk,
202 const openvdb::Coord &neighbor,
203 double &source,
204 double &diagonal) const
205 {
206 const openvdb::math::Vec3s normal = neighbor.asVec3s() - ijk.asVec3s();
207 const float value = value_accessor_.getValue(neighbor);
208 const openvdb::math::Vec3s gradient = gradient_transform_.transform(
209 gradient_accessor_.getValue(neighbor));
210 const float factor = factor_accessor_.getValue(neighbor);
211 diagonal -= 1.0 * (1.0f - factor);
212 source -= math::interpolate(value * value_scale_, gradient.dot(normal), factor);
213 };
214};
215
216/* Extract the outermost layer of active voxels on which to evaluate boundary conditions. */
217static openvdb::MaskTree::Ptr get_boundary_mask(const openvdb::FloatTree &tree)
218{
219 using MaskTreeT = openvdb::MaskTree;
220 typename MaskTreeT::Ptr interior_mask(new MaskTreeT(tree, false, openvdb::TopologyCopy()));
221 typename MaskTreeT::Ptr boundary_mask(new MaskTreeT(tree, false, openvdb::TopologyCopy()));
222
223 openvdb::tools::dilateActiveValues(
224 *boundary_mask, /*iterations=*/1, openvdb::tools::NN_FACE, openvdb::tools::PRESERVE_TILES);
225 boundary_mask->topologyDifference(*interior_mask);
226 return boundary_mask;
227}
228
229static bool is_uniform_scale(const float3 &s, const float epsilon = 1e-5f)
230{
231 return math::abs(s.x - s.y) < epsilon && math::abs(s.x - s.z) < epsilon;
232}
233
234/* Returns true if all values in the tree are finite. */
235static bool all_values_finite(const openvdb::FloatTree &tree)
236{
237 threading::EnumerableThreadSpecific<bool> all_finite_tls = true;
238 openvdb::tools::foreach(
239 tree.cbeginValueOn(), [&](const typename openvdb::FloatTree::ValueOnCIter &iter) {
240 const float value = iter.getValue();
241 all_finite_tls.local() = all_finite_tls.local() && std::isfinite(value);
242 });
243 return std::all_of(
244 all_finite_tls.begin(), all_finite_tls.end(), [](const bool value) { return value; });
245}
246
247#endif
248
250{
251#ifdef WITH_OPENVDB
253 "Grid"_ustr);
254 if (!source_grid) {
256 return;
257 }
258
259 const int max_iterations = params.extract_input<int>("Max Iterations"_ustr);
260 const ThresholdMode threshold_mode = params.extract_input<ThresholdMode>("Threshold Mode"_ustr);
261 const float error_threshold = params.extract_input<float>("Error Threshold"_ustr);
262 const Boundary boundary = params.extract_input<Boundary>("Boundary"_ustr);
263 /* The OpenVDB Poisson solver has a "staggered" and a "collocated" variant.
264 * The difference seems to be that the staggered version uses a +-1 stencil while the collocated
265 * version uses a +-2 size stencil. The collocated stencil (according to code comments) leads to
266 * a smoother solution at boundaries, but it requires a smoother input grid as well:
267 * any variation smaller than 2 voxels can lead to "ringing" artifacts with odd/even coupling.
268 * The "staggered" variant of the Laplacian seems to be the better choice in most cases.
269 *
270 * Note: By the looks of it the "staggered" Laplacian version was the original implementation,
271 * and the collocated version with the +-2 stencil was added later. Not much documentation is
272 * available to explain the use cases. This could be exposed as an option if it ever becomes
273 * necessary.
274 */
275 const bool staggered = true;
276
277 bke::VolumeTreeAccessToken tree_token;
278 const openvdb::FloatGrid &source_vdb_grid = source_grid.grid(tree_token);
279 const openvdb::math::Transform &grid_transform = source_vdb_grid.transform();
280 const float3 voxel_size = bke::VolumeGridTraits<float3>::to_blender(grid_transform.voxelSize());
281 if (!is_uniform_scale(voxel_size)) {
282 params.error_message_add(NodeWarningType::Warning, "Non-uniform grid scale not supported");
283 }
284 const float voxel_scale = voxel_size.x;
285 /* The solver works in index space, where the voxel size is h=1. The Laplace operator applies two
286 * derivative operators div(grad(X)) which both add a voxel scale factor of 1/h in the
287 * "staggered" 1st order version used here. The solver computes the inverse, so the resulting
288 * solution should have a factor of h^2 applied, which we have to do manually to produce the
289 * correct result in grid space. */
290 const float solution_scale = math::square(voxel_scale);
291 /* The absolute error is given as a solution value in grid space, which is scaled by h^2 compared
292 * to index space. The absolute error in index space must be scaled by 1/h^2. */
293 const float absolute_error_scale = math::rcp(solution_scale);
294
295 openvdb::math::pcg::State solver_state;
296 solver_state.iterations = max_iterations;
297 switch (threshold_mode) {
299 solver_state.relativeError = double(error_threshold);
300 solver_state.absoluteError = 0.0;
301 break;
303 solver_state.relativeError = 0.0;
304 solver_state.absoluteError = double(error_threshold * absolute_error_scale);
305 break;
306 }
307
308 openvdb::FloatTree::Ptr solution_tree;
309 using PreconditionerType =
310 openvdb::math::pcg::JacobiPreconditioner<openvdb::tools::poisson::LaplacianMatrix>;
311 openvdb::util::NullInterrupter interrupter;
312 SocketValueVariant debug_boundary_value = SocketValueVariant::from(0.0f);
313 SocketValueVariant debug_boundary_gradient = SocketValueVariant::from(float3(0.0f));
314 SocketValueVariant debug_boundary_factor = SocketValueVariant::from(0.0f);
315 switch (boundary) {
316 case Boundary::Fixed: {
317 const Field<float> boundary_value_field = params.extract_input<Field<float>>(
318 "Boundary Value"_ustr);
319
320 std::array<bke::GVolumeGrid, 1> grids;
321 bke::VolumeTreeAccessToken grid_token;
322 if (boundary_value_field.depends_on_input()) {
323 const openvdb::MaskTree::Ptr mask_tree = get_boundary_mask(source_vdb_grid.tree());
324 bke::volume_grid::evaluate_fields_to_grid(
325 *mask_tree, grid_transform, {boundary_value_field}, grids);
326 }
327 else {
328 const float boundary_value = fn::evaluate_constant_field(boundary_value_field);
329 openvdb::FloatGrid::Ptr vdb_grid = openvdb::FloatGrid::create(boundary_value);
330 vdb_grid->setTransform(source_vdb_grid.constTransformPtr()->copy());
331 grids[0] = bke::VolumeGrid<float>(std::move(vdb_grid));
332 }
333
334 DirichletBoundaryOp boundary_op(grids[0].typed<float>().grid(grid_token));
335 solution_tree = openvdb::tools::poisson::solveWithBoundaryConditionsAndPreconditioner<
336 PreconditionerType>(
337 source_vdb_grid.tree(), boundary_op, solver_state, interrupter, staggered);
338
339 debug_boundary_value = SocketValueVariant::from(grids[0]);
340 break;
341 }
342
343 case Boundary::Gradient: {
344 const Field<float3> boundary_gradient_field = params.extract_input<Field<float3>>(
345 "Boundary Gradient"_ustr);
346
347 std::array<bke::GVolumeGrid, 1> grids;
348 bke::VolumeTreeAccessToken grid_token;
349 if (boundary_gradient_field.depends_on_input()) {
350 const openvdb::MaskTree::Ptr mask_tree = get_boundary_mask(source_vdb_grid.tree());
351 bke::volume_grid::evaluate_fields_to_grid(
352 *mask_tree, grid_transform, {boundary_gradient_field}, grids);
353 }
354 else {
355 const float3 boundary_gradient = fn::evaluate_constant_field(boundary_gradient_field);
356 openvdb::Vec3SGrid::Ptr vdb_grid = openvdb::Vec3SGrid::create(
357 bke::VolumeGridTraits<float3>::to_openvdb(boundary_gradient));
358 vdb_grid->setTransform(source_vdb_grid.constTransformPtr()->copy());
359 grids[0] = bke::VolumeGrid<float3>(std::move(vdb_grid));
360 }
361
362 NeumannBoundaryOp boundary_op(grids[0].typed<float3>().grid(grid_token));
363 solution_tree = openvdb::tools::poisson::solveWithBoundaryConditionsAndPreconditioner<
364 PreconditionerType>(
365 source_vdb_grid.tree(), boundary_op, solver_state, interrupter, staggered);
366
367 debug_boundary_gradient = SocketValueVariant::from(grids[0]);
368 break;
369 }
370
371 case Boundary::Mixed: {
372 const Field<float> boundary_value_field = params.extract_input<Field<float>>(
373 "Boundary Value"_ustr);
374 const Field<float3> boundary_gradient_field = params.extract_input<Field<float3>>(
375 "Boundary Gradient"_ustr);
376 const Field<float> boundary_factor_field = params.extract_input<Field<float>>(
377 "Boundary Factor"_ustr);
378 const openvdb::MaskTree::Ptr mask_tree = get_boundary_mask(source_vdb_grid.tree());
379
380 std::array<bke::GVolumeGrid, 3> grids;
381 std::array<bke::VolumeTreeAccessToken, 3> grid_tokens;
382
383 if (boundary_value_field.depends_on_input() || boundary_gradient_field.depends_on_input() ||
384 boundary_factor_field.depends_on_input())
385 {
386 bke::volume_grid::evaluate_fields_to_grid(
387 *mask_tree,
388 grid_transform,
389 {boundary_value_field, boundary_gradient_field, boundary_factor_field},
390 grids);
391 }
392 else {
393 const float boundary_value = fn::evaluate_constant_field(boundary_value_field);
394 const float3 boundary_gradient = fn::evaluate_constant_field(boundary_gradient_field);
395 const float boundary_factor = fn::evaluate_constant_field(boundary_factor_field);
396 openvdb::FloatGrid::Ptr vdb_value_grid = openvdb::FloatGrid::create(boundary_value);
397 openvdb::Vec3SGrid::Ptr vdb_gradient_grid = openvdb::Vec3SGrid::create(
398 bke::VolumeGridTraits<float3>::to_openvdb(boundary_gradient));
399 openvdb::FloatGrid::Ptr vdb_factor_grid = openvdb::FloatGrid::create(boundary_factor);
400 vdb_value_grid->setTransform(source_vdb_grid.constTransformPtr()->copy());
401 vdb_gradient_grid->setTransform(source_vdb_grid.constTransformPtr()->copy());
402 vdb_factor_grid->setTransform(source_vdb_grid.constTransformPtr()->copy());
403 grids[0] = bke::VolumeGrid<float>(std::move(vdb_value_grid));
404 grids[1] = bke::VolumeGrid<float3>(std::move(vdb_gradient_grid));
405 grids[2] = bke::VolumeGrid<float>(std::move(vdb_factor_grid));
406 }
407
408 MixedBoundaryOp boundary_op(grids[0].typed<float>().grid(grid_tokens[0]),
409 grids[1].typed<float3>().grid(grid_tokens[1]),
410 grids[2].typed<float>().grid(grid_tokens[2]));
411 solution_tree = openvdb::tools::poisson::solveWithBoundaryConditionsAndPreconditioner<
412 PreconditionerType>(
413 source_vdb_grid.tree(), boundary_op, solver_state, interrupter, staggered);
414
415 debug_boundary_value = SocketValueVariant::from(grids[0]);
416 debug_boundary_gradient = SocketValueVariant::from(grids[1]);
417 debug_boundary_factor = SocketValueVariant::from(grids[2]);
418 break;
419 }
420
421 default:
423 solution_tree = std::make_shared<openvdb::FloatTree>();
424 break;
425 }
426
427 /* Note: OpenVDB infNorm function of the conjugate gradient solver
428 * outputs 0.0 if the solution contains only non-finite values.
429 * Handle the case of a non-finite solution explicitly here: If the solution contains any
430 * non-finite value it has diverged and should be considered invalid. */
431 if (solver_state.absoluteError == 0.0) {
432 const bool all_finite = all_values_finite(*solution_tree);
433 if (!all_finite) {
434 solver_state.absoluteError = std::numeric_limits<float>::infinity();
435 solver_state.relativeError = std::numeric_limits<float>::infinity();
436 solver_state.success = false;
437 }
438 }
439
440 openvdb::tools::foreach(solution_tree->beginValueOn(),
441 [&](const typename openvdb::FloatTree::ValueOnIter &iter) {
442 iter.setValue(iter.getValue() * solution_scale);
443 });
444
445 openvdb::FloatGrid::Ptr solution_grid = openvdb::FloatGrid::create(std::move(solution_tree));
446 solution_grid->setTransform(grid_transform.copy());
447
448 params.set_output("Solution"_ustr, bke::VolumeGrid<float>(std::move(solution_grid)));
449 params.set_output("Iterations"_ustr, solver_state.iterations);
450 params.set_output("Success"_ustr, solver_state.success);
451 params.set_output("Absolute Error"_ustr, float(solver_state.absoluteError * solution_scale));
452 params.set_output("Relative Error"_ustr, float(solver_state.relativeError));
453 if (params.output_is_required("Debug Boundary Value"_ustr)) {
454 params.set_output("Debug Boundary Value"_ustr, std::move(debug_boundary_value));
455 }
456 if (params.output_is_required("Debug Boundary Gradient"_ustr)) {
457 params.set_output("Debug Boundary Gradient"_ustr, std::move(debug_boundary_gradient));
458 }
459 if (params.output_is_required("Debug Boundary Factor"_ustr)) {
460 params.set_output("Debug Boundary Factor"_ustr, std::move(debug_boundary_factor));
461 }
462
463 if (!solver_state.success) {
464 params.error_message_add(
466 "Poisson solver failed to converge within the iteration limit. Try increasing "
467 "the maximum iterations or tolerance.");
468 }
469#else
471#endif
472}
473
474static void node_register()
475{
476 static blender::bke::bNodeType ntype;
477 geo_node_type_base(&ntype, "GeometryNodeGridSolvePoisson"_ustr);
478 ntype.ui_name = "Grid Solve Poisson";
479 ntype.ui_description =
480 "Solve the Poisson equation for a scalar field. Computes a grid whose Laplacian equals the "
481 "input scalar grid.";
484 ntype.declare = node_declare;
487}
489
490} // namespace blender::nodes::node_geo_grid_solve_poisson_cc
#define NODE_CLASS_GEOMETRY
Definition BKE_node.hh:492
#define NOD_REGISTER_NODE(REGISTER_FUNC)
#define BLI_assert_unreachable()
SIMD_FORCE_INLINE btVector3 transform(const btVector3 &point) const
SIMD_FORCE_INLINE btVector3 operator()(const btVector3 &x) const
Return the transform of the vector.
Definition btTransform.h:90
bool depends_on_input() const
Definition FN_field.hh:513
DeclType::Builder & add_output(UString name, UString identifier=""_ustr)
void error_message_add(const NodeWarningType type, StringRef message) const
T extract_input(const UString identifier)
bool output_is_required(const UString identifier) const
void set_output(const UString identifier, T &&value)
static SocketValueVariant from(T &&value)
MatBase< C, R > inverse(MatBase< C, R >) RET
float square(float v)
#define Absolute(a)
double epsilon
default precision while comparing with Equal(..,..) functions. Initialized at 0.0000001.
Definition utility.cpp:22
void node_register_type(bNodeType &ntype)
Definition node.cc:2920
void evaluate_constant_field(const GField &field, void *r_value)
T rcp(const T &a)
T square(const T &a)
T abs(const T &a)
static void node_declare(NodeDeclarationBuilder &b)
void node_geo_exec_with_missing_openvdb(GeoNodeExecParams &params)
VecBase< float, 3 > float3
@ PROP_FACTOR
Definition RNA_types.hh:308
void geo_node_type_base(bke::bNodeType *ntype, UString idname, const std::optional< int16_t > legacy_type)
#define min(a, b)
Definition sort.cc:38
static constexpr int _200
Definition BKE_node.hh:248
Defines a node type.
Definition BKE_node.hh:265
std::string ui_description
Definition BKE_node.hh:271
NodeGeometryExecFunction geometry_node_execute
Definition BKE_node.hh:385
NodeDeclareFunction declare
Definition BKE_node.hh:393
float z
Definition sky_math.h:136
float y
Definition sky_math.h:136
float x
Definition sky_math.h:136