Blender V5.3
cycles/bvh/octree.cpp
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2025 Blender Foundation
2 *
3 * SPDX-License-Identifier: Apache-2.0 */
4
5#include "bvh/octree.h"
6
7#include "scene/object.h"
8#include "scene/volume.h"
9
11
12#include "util/log.h"
13#include "util/progress.h"
14
15#ifdef WITH_OPENVDB
16# include <openvdb/tools/FindActiveValues.h>
17#endif
18
19#include <fstream>
20
22
23__forceinline int Octree::flatten_index(int x, int y, int z) const
24{
25 return x + resolution_ * (y + z * resolution_);
26}
27
28Extrema<float> Octree::get_extrema(const int3 index_min, const int3 index_max) const
29{
30 const blocked_range3d<int> range(
31 index_min.x, index_max.x, 32, index_min.y, index_max.y, 32, index_min.z, index_max.z, 32);
32
33 const Extrema<float> identity = {FLT_MAX, -FLT_MAX};
34
35 auto reduction_func = [&](const blocked_range3d<int> &r, Extrema<float> init) -> Extrema<float> {
36 for (int z = r.cols().begin(); z < r.cols().end(); ++z) {
37 for (int y = r.rows().begin(); y < r.rows().end(); ++y) {
38 for (int x = r.pages().begin(); x < r.pages().end(); ++x) {
39 init = merge(init, sigmas_[flatten_index(x, y, z)]);
40 }
41 }
42 }
43 return init;
44 };
45
46 auto join_func = [](Extrema<float> a, Extrema<float> b) -> Extrema<float> {
47 return merge(a, b);
48 };
49
50 return parallel_reduce(range, identity, reduction_func, join_func);
51}
52
53__forceinline float3 Octree::position_to_index(const float3 p) const
54{
55 return (p - bbox_min) * position_to_index_scale_;
56}
57
58int3 Octree::position_to_floor_index(const float3 p) const
59{
60 const float3 index = round(position_to_index(p));
61 return clamp(make_int3(int(index.x), int(index.y), int(index.z)), 0, resolution_ - 1);
62}
63
64int3 Octree::position_to_ceil_index(const float3 p) const
65{
66 if (any_zero(position_to_index_scale_)) {
67 /* Octree with degenerate shape, force max index. */
68 return make_int3(resolution_);
69 }
70 const float3 index = round(position_to_index(p));
71 return clamp(make_int3(int(index.x), int(index.y), int(index.z)), 1, resolution_);
72}
73
75{
76 return bbox_min + make_float3(x, y, z) * index_to_position_scale_;
77}
78
80{
81 return index_to_position_scale_;
82}
83
84bool Octree::should_split(std::shared_ptr<OctreeNode> &node) const
85{
86 const int3 index_min = position_to_floor_index(node->bbox.min);
87 const int3 index_max = position_to_ceil_index(node->bbox.max);
88 node->sigma = get_extrema(index_min, index_max);
89
90 const float3 bbox_size = node->bbox.size();
91 if (any_zero(bbox_size)) {
92 /* Octree with degenerate shape, can happen for implicit volume. */
93 return false;
94 }
95
96 /* The threshold is set so that ideally only one sample needs to be taken per node. Value taken
97 * from "Volume Rendering for Pixar's Elemental". */
98 return (node->sigma.range() * len(bbox_size) * scale_ > 1.442f &&
100}
101
102#ifdef WITH_OPENVDB
103/* Check if a interior mask grid intersects with a bounding box defined by `p_min` and `p_max`. */
104static bool vdb_voxel_intersect(const float3 p_min,
105 const float3 p_max,
106 openvdb::BoolGrid::ConstPtr &grid,
107 const openvdb::tools::FindActiveValues<openvdb::BoolTree> &find)
108{
109 if (grid->empty()) {
110 /* Non-mesh volume or open mesh. */
111 return true;
112 }
113
114 const openvdb::math::CoordBBox coord_bbox(
115 openvdb::Coord::floor(grid->worldToIndex({p_min.x, p_min.y, p_min.z})),
116 openvdb::Coord::ceil(grid->worldToIndex({p_max.x, p_max.y, p_max.z})));
117
118 /* Check if the bounding box lies inside or partially overlaps the mesh.
119 * For interior mask grids, all the interior voxels are active. */
120 return find.anyActiveValues(coord_bbox, true);
121}
122#endif
123
124/* Fill in coordinates for shading the volume density. */
126 const Octree *octree,
127 const Object *object,
128 const Shader *shader,
129#ifdef WITH_OPENVDB
130 openvdb::BoolGrid::ConstPtr &interior_mask,
131#endif
132 const int resolution)
133{
134 const int object_id = object->get_device_index();
135 const uint shader_id = shader->id;
136
137 KernelShaderEvalInput *d_input_data = d_input.data();
138
139 const float3 voxel_size = octree->voxel_size();
140 /* Dilate the voxel in case we miss features at the boundary. */
141 const float3 pad = 0.2f * voxel_size;
142 const float3 padded_size = voxel_size + pad * 2.0f;
143
144 const blocked_range3d<int> range(0, resolution, 8, 0, resolution, 8, 0, resolution, 8);
145 parallel_for(range, [&](const blocked_range3d<int> &r) {
146#ifdef WITH_OPENVDB
147 /* One accessor per thread is important for cached access. */
148 const auto find = openvdb::tools::FindActiveValues(interior_mask->tree());
149#endif
150
151 for (int z = r.cols().begin(); z < r.cols().end(); ++z) {
152 for (int y = r.rows().begin(); y < r.rows().end(); ++y) {
153 for (int x = r.pages().begin(); x < r.pages().end(); ++x) {
154 const int offset = octree->flatten_index(x, y, z);
155 const float3 p = octree->index_to_position(x, y, z);
156
157#ifdef WITH_OPENVDB
158 /* Zero density for cells outside of the mesh. */
159 if (!vdb_voxel_intersect(p, p + voxel_size, interior_mask, find)) {
160 d_input_data[offset * 2].object = OBJECT_NONE;
161 d_input_data[offset * 2 + 1].object = SHADER_NONE;
162 continue;
163 }
164#endif
165
167 in.object = object_id;
168 in.prim = __float_as_int(p.x - pad.x);
169 in.u = p.y - pad.y;
170 in.v = p.z - pad.z;
171 d_input_data[offset * 2] = in;
172
173 in.object = shader_id;
174 in.prim = __float_as_int(padded_size.x);
175 in.u = padded_size.y;
176 in.v = padded_size.z;
177 d_input_data[offset * 2 + 1] = in;
178 }
179 }
180 }
181 });
182}
183
184/* Read back the volume density. */
185static void read_shader_output(const device_vector<float> &d_output,
186 const Octree *octree,
187 const int num_channels,
188 const int resolution,
189 vector<Extrema<float>> &sigmas)
190{
191 const float *d_output_data = d_output.data();
192 const blocked_range3d<int> range(0, resolution, 32, 0, resolution, 32, 0, resolution, 32);
193
194 parallel_for(range, [&](const blocked_range3d<int> &r) {
195 for (int z = r.cols().begin(); z < r.cols().end(); ++z) {
196 for (int y = r.rows().begin(); y < r.rows().end(); ++y) {
197 for (int x = r.pages().begin(); x < r.pages().end(); ++x) {
198 const int index = octree->flatten_index(x, y, z);
199 sigmas[index].min = d_output_data[index * num_channels + 0];
200 sigmas[index].max = d_output_data[index * num_channels + 1];
201 }
202 }
203 }
204 });
205}
206
207void Octree::evaluate_volume_density(Device *device,
208 Progress &progress,
209#ifdef WITH_OPENVDB
210 openvdb::BoolGrid::ConstPtr &interior_mask,
211#endif
212 const Object *object,
213 const Shader *shader)
214{
215 /* For heterogeneous volume, the grid resolution is 2^max_depth in each 3D dimension;
216 * for homogeneous volume, only one grid is needed. */
217 resolution_ = VolumeManager::is_homogeneous_volume(object, shader) ?
218 1 :
220 index_to_position_scale_ = root_->bbox.size() / float(resolution_);
221 position_to_index_scale_ = safe_divide(one_float3(), index_to_position_scale_);
222
223 /* Initialize density field. */
224 /* TODO(weizhen): maybe lower the resolution depending on the object size. */
225 const int size = resolution_ * resolution_ * resolution_;
226 sigmas_.resize(size);
227 parallel_for(0, size, [&](int i) { sigmas_[i] = {0.0f, 0.0f}; });
228
229 /* Min and max. */
230 const int num_channels = 2;
231
232 /* Need the size of two `KernelShaderEvalInput`s per voxel for evaluating the shader. */
233 const int num_inputs = size * 2;
234
235 /* Evaluate shader on device. */
236 ShaderEval shader_eval(device, progress);
237 shader_eval.eval(
239 num_inputs,
240 num_channels,
241 [&](device_vector<KernelShaderEvalInput> &d_input) {
242#ifdef WITH_OPENVDB
243 fill_shader_input(d_input, this, object, shader, interior_mask, resolution_);
244#else
245 fill_shader_input(d_input, this, object, shader, resolution_);
246#endif
247 return size;
248 },
249 [&](device_vector<float> &d_output) {
250 read_shader_output(d_output, this, num_channels, resolution_, sigmas_);
251 });
252}
253
254float Octree::volume_scale(const Object *object) const
255{
256 const Geometry *geom = object->get_geometry();
257 if (geom->is_volume()) {
258 const Volume *volume = static_cast<const Volume *>(geom);
259 if (volume->get_object_space()) {
260 /* The density changes with object scale, we scale the density accordingly in the final
261 * render. */
262 if (volume->transform_applied) {
263 const float3 unit = normalize(one_float3());
264 return 1.0f / len(transform_direction(&object->get_tfm(), unit));
265 }
266 }
267 else {
268 /* The density does not change with object scale, we scale the node in the viewport to it's
269 * true size. */
270 if (!volume->transform_applied) {
271 const float3 unit = normalize(one_float3());
272 return len(transform_direction(&object->get_tfm(), unit));
273 }
274 }
275 }
276 else {
277 /* TODO(weizhen): use the maximal scale of all instances. */
278 if (!geom->transform_applied) {
279 const float3 unit = normalize(one_float3());
280 return len(transform_direction(&object->get_tfm(), unit));
281 }
282 }
283
284 return 1.0f;
285}
286
287std::shared_ptr<OctreeInternalNode> Octree::make_internal(std::shared_ptr<OctreeNode> &node)
288{
289 num_nodes_ += 8;
290 auto internal = std::make_shared<OctreeInternalNode>(*node);
291
292 /* Create bounding boxes for children. */
293 const float3 center = internal->bbox.center();
294 for (int i = 0; i < 8; i++) {
295 const float3 t = make_float3(i & 1, (i >> 1) & 1, (i >> 2) & 1);
296 const BoundBox bbox(mix(internal->bbox.min, center, t), mix(center, internal->bbox.max, t));
297 internal->children_[i] = std::make_shared<OctreeNode>(bbox, internal->depth + 1);
298 }
299
300 return internal;
301}
302
303void Octree::recursive_build(std::shared_ptr<OctreeNode> &octree_node)
304{
305 if (!should_split(octree_node)) {
306 return;
307 }
308
309 /* Make the current node an internal node. */
310 auto internal = make_internal(octree_node);
311
312 for (auto &child : internal->children_) {
313 task_pool_.push([&] { recursive_build(child); });
314 }
315
316 octree_node = internal;
317}
318
320 const int current_index,
321 const std::shared_ptr<OctreeNode> &node,
322 int &child_index) const
323{
324 KernelOctreeNode &knode = knodes[current_index];
325 knode.sigma = node->sigma;
326
327 if (auto internal_ptr = std::dynamic_pointer_cast<OctreeInternalNode>(node)) {
328 knode.first_child = child_index;
329 child_index += 8;
330 /* Loop through all the children and flatten in breadth-first manner, so that children are
331 * stored in contiguous indices. */
332 for (int i = 0; i < 8; i++) {
333 knodes[knode.first_child + i].parent = current_index;
334 flatten(knodes, knode.first_child + i, internal_ptr->children_[i], child_index);
335 }
336 }
337 else {
338 knode.first_child = -1;
339 }
340}
341
342void Octree::set_flattened(const bool flattened)
343{
344 is_flattened_ = flattened;
345}
346
348{
349 return is_flattened_;
350}
351
353 Progress &progress,
354#ifdef WITH_OPENVDB
355 openvdb::BoolGrid::ConstPtr &interior_mask,
356#endif
357 const Object *object,
358 const Shader *shader)
359{
360 const char *name = object->get_asset_name().c_str();
361 progress.set_substatus(string_printf("Evaluating density for %s", name));
362
363#ifdef WITH_OPENVDB
364 evaluate_volume_density(device, progress, interior_mask, object, shader);
365#else
366 evaluate_volume_density(device, progress, object, shader);
367#endif
368 if (progress.get_cancel()) {
369 return;
370 }
371
372 progress.set_substatus(string_printf("Building octree for %s", name));
373
374 scale_ = volume_scale(object);
375 recursive_build(root_);
376
377 task_pool_.wait_work();
378
379 is_built_ = true;
380 sigmas_.clear();
381}
382
384{
385 bbox_min = bbox.min;
386 root_ = std::make_shared<OctreeNode>(bbox, 0);
387 is_built_ = false;
388 is_flattened_ = false;
389}
390
392{
393 return is_built_;
394}
395
397{
398 return num_nodes_;
399}
400
401std::shared_ptr<OctreeNode> Octree::get_root() const
402{
403 return root_;
404}
405
406void OctreeNode::visualize(std::string &str) const
407{
408 const auto *internal = dynamic_cast<const OctreeInternalNode *>(this);
409
410 if (!internal) {
411 /* Skip leaf nodes. */
412 return;
413 }
414
415 /* Create three orthogonal faces for inner nodes. */
416 const float3 mid = bbox.center();
417 const float3 max = bbox.max;
418 const float3 min = bbox.min;
419 const std::string mid_x = to_string(mid.x), mid_y = to_string(mid.y), mid_z = to_string(mid.z),
420 min_x = to_string(min.x), min_y = to_string(min.y), min_z = to_string(min.z),
421 max_x = to_string(max.x), max_y = to_string(max.y), max_z = to_string(max.z);
422 // clang-format off
423 str += "(" + mid_x + "," + mid_y + "," + min_z + "), "
424 "(" + mid_x + "," + mid_y + "," + max_z + "), "
425 "(" + mid_x + "," + max_y + "," + max_z + "), "
426 "(" + mid_x + "," + max_y + "," + min_z + "), "
427 "(" + mid_x + "," + min_y + "," + min_z + "), "
428 "(" + mid_x + "," + min_y + "," + max_z + "), ";
429 str += "(" + min_x + "," + mid_y + "," + mid_z + "), "
430 "(" + max_x + "," + mid_y + "," + mid_z + "), "
431 "(" + max_x + "," + mid_y + "," + max_z + "), "
432 "(" + min_x + "," + mid_y + "," + max_z + "), "
433 "(" + min_x + "," + mid_y + "," + min_z + "), "
434 "(" + max_x + "," + mid_y + "," + min_z + "), ";
435 str += "(" + mid_x + "," + min_y + "," + mid_z + "), "
436 "(" + mid_x + "," + max_y + "," + mid_z + "), "
437 "(" + max_x + "," + max_y + "," + mid_z + "), "
438 "(" + max_x + "," + min_y + "," + mid_z + "), "
439 "(" + min_x + "," + min_y + "," + mid_z + "), "
440 "(" + min_x + "," + max_y + "," + mid_z + "), ";
441 // clang-format on
442 for (const auto &child : internal->children_) {
443 child->visualize(str);
444 }
445}
446
447void Octree::visualize(std::ofstream &file, const std::string object_name) const
448{
449 std::string str = "vertices = [";
450 root_->visualize(str);
451 str +=
452 "]\nr = range(len(vertices))\n"
453 "edges = [(i, i+1 if i%6<5 else i-4) for i in r]\n"
454 "mesh = bpy.data.meshes.new('Octree')\n"
455 "mesh.from_pydata(vertices, edges, [])\n"
456 "mesh.update()\n"
457 "obj = bpy.data.objects.new('" +
458 object_name +
459 "', mesh)\n"
460 "octree.objects.link(obj)\n"
461 "bpy.context.view_layer.objects.active = obj\n"
462 "bpy.ops.object.mode_set(mode='EDIT')\n";
463 file << str;
464
465 const float3 center = root_->bbox.center();
466 const float3 size = root_->bbox.size() * 0.5f;
467 file << "bpy.ops.mesh.primitive_cube_add(location = " << center << ", scale = " << size << ")\n";
468 file << "bpy.ops.mesh.delete(type='ONLY_FACE')\n"
469 "bpy.ops.object.mode_set(mode='OBJECT')\n"
470 "obj.select_set(True)\n";
471}
472
int pad[32 - sizeof(int)]
void init()
btScalar max
SIMD_FORCE_INLINE const btScalar & z() const
Return the z value.
Definition btQuadWord.h:117
__forceinline float3 center() const
Definition boundbox.h:112
float3 max
Definition boundbox.h:20
float3 min
Definition boundbox.h:20
bool transform_applied
bool is_volume() const
void visualize(std::ofstream &file, const std::string object_name) const
int get_num_nodes() const
float3 voxel_size() const
int flatten_index(int x, int y, int z) const
void flatten(KernelOctreeNode *, const int, const std::shared_ptr< OctreeNode > &, int &) const
void set_flattened(const bool=true)
float3 index_to_position(int x, int y, int z) const
std::shared_ptr< OctreeNode > get_root() const
void build(Device *, Progress &, const Object *, const Shader *)
bool is_flattened() const
Octree(const BoundBox &bbox)
bool is_built() const
void set_substatus(const string &substatus_)
Definition progress.h:259
bool get_cancel() const
Definition progress.h:77
static bool is_homogeneous_volume(const Object *, const Shader *)
static void fill_shader_input(device_vector< KernelShaderEvalInput > &d_input, const Octree *octree, const Object *object, const Shader *shader, const int resolution)
static void read_shader_output(const device_vector< float > &d_output, const Octree *octree, const int num_channels, const int resolution, vector< Extrema< float > > &sigmas)
#define SHADER_NONE
#define OBJECT_NONE
#define VOLUME_OCTREE_MAX_DEPTH
#define __forceinline
#define CCL_NAMESPACE_END
ccl_device_forceinline float3 make_float3(const float x, const float y, const float z)
ccl_device_forceinline int3 make_int3(const int x, const int y, const int z)
#define __float_as_int(x)
#define str(s)
#define FLT_MAX
#define index(i)
#define round
VecBase< float, D > normalize(VecOp< float, D >) RET
constexpr T clamp(T, U, U) RET
VecBase< float, 3 > float3
float3 transform_direction(float3x3 mat, float3 direction)
float safe_divide(float a, float b)
OrientationBounds merge(const OrientationBounds &cone_a, const OrientationBounds &cone_b)
ccl_device_inline int power_of_2(const int a)
Definition math_base.h:679
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
ccl_device_inline float3 one_float3()
Definition math_float3.h:26
ccl_device_inline bool any_zero(const float3 a)
int size(const AssetLibraryReference *library_reference)
const std::any * find(const AnyDictionary &dictionary, const std::string &key)
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
Value parallel_reduce(IndexRange range, int64_t grain_size, const Value &identity, const Function &function, const Reduction &reduction)
Definition BLI_task.hh:127
#define mix
@ SHADER_EVAL_VOLUME_DENSITY
Definition shader_eval.h:22
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
#define min(a, b)
Definition sort.cc:38
string to_string(const char *str)
Definition string.cpp:202
CCL_NAMESPACE_BEGIN string string_printf(const char *format,...)
Definition string.cpp:25
Extrema< float > sigma
void visualize(std::string &str) const
float z
Definition sky_math.h:136
float y
Definition sky_math.h:136
float x
Definition sky_math.h:136