Blender V5.3
cycles/bvh/octree.h
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2025 Blender Foundation
2 *
3 * SPDX-License-Identifier: Apache-2.0 */
4
5/* The volume octree is used to determine the necessary step size when rendering the volume. One
6 * volume per object per shader is built, and a node splits in eight when the density difference
7 * inside the node exceeds a certain threshold. */
8
9#ifndef __OCTREE_H__
10#define __OCTREE_H__
11
12#include "util/boundbox.h"
13#include "util/task.h"
14
15#ifdef WITH_OPENVDB
16# include <openvdb/openvdb.h>
17#endif
18
19#include <atomic>
20#include <iosfwd>
21
23
24class Device;
25class Object;
26class Progress;
27class Shader;
28struct KernelOctreeNode;
29
30struct OctreeNode {
31 /* Bounding box of the node. */
33
34 /* Depth of the node in the octree. */
35 int depth;
36
37 /* Minimal and maximal volume density inside the node. */
38 Extrema<float> sigma = {0.0f, 0.0f};
39
40 OctreeNode() : bbox(BoundBox::empty), depth(0) {}
41 OctreeNode(BoundBox bbox_, int depth_) : bbox(bbox_), depth(depth_) {}
42 virtual ~OctreeNode() = default;
43
44 /* Visualize node. */
45 void visualize(std::string &str) const;
46};
47
58
59class Octree {
60 public:
61 Octree(const BoundBox &bbox);
62 ~Octree() = default;
63
64 /* Build the octree according to the volume density. */
65#ifdef WITH_OPENVDB
66 void build(Device *, Progress &, openvdb::BoolGrid::ConstPtr &, const Object *, const Shader *);
67#else
68 void build(Device *, Progress &, const Object *, const Shader *);
69#endif
70
71 /* Convert the octree into an array of nodes for uploading to the kernel. */
72 void flatten(KernelOctreeNode *, const int, const std::shared_ptr<OctreeNode> &, int &) const;
73 void set_flattened(const bool = true);
74 bool is_flattened() const;
75
76 /* Flatten a 3D coordinate in the grid to a 1D index. */
77 int flatten_index(int x, int y, int z) const;
78 /* Convert from index to the position of the lower left corner of the voxel. */
79 float3 index_to_position(int x, int y, int z) const;
80 /* Size of a voxel. */
81 float3 voxel_size() const;
82
83 int get_num_nodes() const;
84 std::shared_ptr<OctreeNode> get_root() const;
85 bool is_built() const;
86
87 /* Draw octree nodes as empty boxes with Blender Python API. */
88 void visualize(std::ofstream &file, const std::string object_name) const;
89
90 private:
91 /* The bounding box of the octree is divided into a regular grid with the same resolution in each
92 * dimension. */
93 int resolution_;
94 /* Extrema of volume densities in the grid. */
95 vector<Extrema<float>> sigmas_;
96 /* Compute the extrema of all the `sigmas_` in a coordinate bounding box defined by `index_min`
97 * and `index_max`. */
98 Extrema<float> get_extrema(const int3 index_min, const int3 index_max) const;
99 /* Randomly sample positions inside the grid to evaluate the shader for the density. */
100#ifdef WITH_OPENVDB
101 void evaluate_volume_density(
102 Device *, Progress &, openvdb::BoolGrid::ConstPtr &, const Object *, const Shader *);
103#else
104 void evaluate_volume_density(Device *, Progress &, const Object *, const Shader *);
105#endif
106 /* Convert from position in object space to grid index space. */
107 float3 position_to_index_scale_;
108 float3 index_to_position_scale_;
109 float3 position_to_index(const float3 p) const;
110 int3 position_to_floor_index(const float3 p) const;
111 int3 position_to_ceil_index(const float3 p) const;
112
113 /* Whether a node should be split into child nodes. */
114 bool should_split(std::shared_ptr<OctreeNode> &node) const;
115 /* Scale the node size so that the octree has the similar subdivision levels in viewport and
116 * final render. */
117 float volume_scale(const Object *object) const;
118 float scale_;
119 /* Recursively build a node and its child nodes. */
120 void recursive_build(std::shared_ptr<OctreeNode> &);
121 /* Turn a node into an internal node. */
122 std::shared_ptr<OctreeInternalNode> make_internal(std::shared_ptr<OctreeNode> &node);
123
124 /* Root node. */
125 std::shared_ptr<OctreeNode> root_;
126
127 /* Bounding box min of the octree, used for computing the indices. */
128 float3 bbox_min;
129
130 /* Whether the octree is already built. */
131 bool is_built_;
132
133 /* Whether the octree is already flattened into an array. */
134 bool is_flattened_;
135
136 /* Number of nodes in the octree. Incremented while building the tree. */
137 std::atomic<int> num_nodes_ = 1;
138
139 /* Task pool for building the octree in parallel. */
140 TaskPool task_pool_;
141};
142
144
145#endif /* __OCTREE_H__ */
SIMD_FORCE_INLINE const btScalar & z() const
Return the z value.
Definition btQuadWord.h:117
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
#define CCL_NAMESPACE_END
#define str(s)
OctreeInternalNode(OctreeNode &node)
vector< std::shared_ptr< OctreeNode > > children_
virtual ~OctreeNode()=default
Extrema< float > sigma
OctreeNode(BoundBox bbox_, int depth_)
void visualize(std::string &str) const