60 const int object_index)
66 for (uint j = 0; j < num_triangles; j++) {
85 for (
int attr_step = 0; attr_step < attr_P->
num_motion_steps(); attr_step++) {
100 const float num_bvh_steps_inv_1 = 1.0f / (num_bvh_steps - 1);
101 const size_t num_steps = mesh->get_motion_steps();
109 prev_bounds.
grow(prev_verts[0]);
110 prev_bounds.
grow(prev_verts[1]);
111 prev_bounds.
grow(prev_verts[2]);
113 for (
int bvh_step = 1; bvh_step < num_bvh_steps; ++bvh_step) {
114 const float curr_time = (
float)(bvh_step)*num_bvh_steps_inv_1;
116 t.
motion_verts(attr_P, num_steps, curr_time, curr_verts);
118 curr_bounds.
grow(curr_verts[0]);
119 curr_bounds.
grow(curr_verts[1]);
120 curr_bounds.
grow(curr_verts[2]);
122 bounds.
grow(curr_bounds);
123 if (bounds.
valid()) {
124 const float prev_time = (
float)(bvh_step - 1) * num_bvh_steps_inv_1;
126 BVHReference(bounds, j, object_index, primitive_type, prev_time, curr_time));
133 prev_bounds = curr_bounds;
142 const int object_index)
151 for (uint j = 0; j < num_curves; j++) {
153 const float *curve_radius = hair->
get_radius();
154 for (
int k = 0; k < curve.
num_keys - 1; k++) {
159 if (bounds.
valid()) {
173 for (
int attr_step = 0; attr_step < attr_P->
num_motion_steps(); attr_step++) {
177 if (bounds.
valid()) {
190 const float num_bvh_steps_inv_1 = 1.0f / (num_bvh_steps - 1);
191 const size_t num_steps = hair->get_motion_steps();
198 attr_P, attr_R, num_steps, 0.0f, k - 1, k, k + 1, k + 2, prev_keys);
202 for (
int bvh_step = 1; bvh_step < num_bvh_steps; ++bvh_step) {
203 const float curr_time = (
float)(bvh_step)*num_bvh_steps_inv_1;
206 attr_P, attr_R, num_steps, curr_time, k - 1, k, k + 1, k + 2, curr_keys);
210 bounds.
grow(curr_bounds);
211 if (bounds.
valid()) {
212 const float prev_time = (
float)(bvh_step - 1) * num_bvh_steps_inv_1;
215 BVHReference(bounds, j, object_index, packed_type, prev_time, curr_time));
222 prev_bounds = curr_bounds;
239 const float *radius_data = pointcloud->
get_radius();
240 const size_t num_points = pointcloud->
num_points();
241 const size_t num_steps = pointcloud->get_motion_steps();
246 for (uint j = 0; j < num_points; j++) {
249 point.
bounds_grow(points_data, radius_data, bounds);
250 if (bounds.
valid()) {
264 for (uint j = 0; j < num_points; j++) {
267 for (
int attr_step = 0; attr_step < attr_P->
num_motion_steps(); attr_step++) {
269 const float *mR = attr_R->
data<
float>(attr_step);
272 if (bounds.
valid()) {
285 const float num_bvh_steps_inv_1 = 1.0f / (num_bvh_steps - 1);
289 for (uint j = 0; j < num_points; j++) {
297 radius_data, attr_P, attr_R_motion, num_steps, 0.0f, j);
301 for (
int bvh_step = 1; bvh_step < num_bvh_steps; ++bvh_step) {
302 const float curr_time = (
float)(bvh_step)*num_bvh_steps_inv_1;
304 radius_data, attr_P, attr_R_motion, num_steps, curr_time, j);
308 bounds.
grow(curr_bounds);
309 if (bounds.
valid()) {
310 const float prev_time = (
float)(bvh_step - 1) * num_bvh_steps_inv_1;
318 prev_bounds = curr_bounds;
327 const int object_index)
330 Mesh *mesh =
static_cast<Mesh *
>(geom);
334 Hair *hair =
static_cast<Hair *
>(geom);
355 for (
size_t i = 0; i < num_curves; i++) {
365 Mesh *mesh =
static_cast<Mesh *
>(geom);
369 Hair *hair =
static_cast<Hair *
>(geom);
383 size_t num_alloc_references = 0;
387 if (!ob->is_traceable()) {
390 if (!ob->get_geometry()->is_instanced()) {
394 num_alloc_references++;
411 if (!ob->is_traceable()) {
415 if (!ob->get_geometry()->is_instanced()) {
434 if (!bounds.
valid()) {
453 if (object->get_geometry()->has_motion_blur()) {
499 double build_start_time;
542 rootnode->update_visibility();
543 rootnode->update_time();
545 if (rootnode !=
nullptr) {
547 <<
" Build time: " <<
time_dt() - build_start_time <<
"\n"
548 <<
" Total number of nodes: "
551 <<
" Number of inner nodes: "
554 <<
" Number of leaf nodes: "
557 <<
" Number of unaligned nodes: "
560 <<
" Allocation slop factor: "
564 <<
" Maximum depth: "
583 "Building BVH %.0f%%, duplicates %.0f%%", progress_start * 100.0, duplicates * 100.0);
638 const size_t size = range.
size();
642 if (size > max_leaf_size) {
646 size_t num_triangles = 0;
647 size_t num_motion_triangles = 0;
648 size_t num_curves = 0;
649 size_t num_motion_curves = 0;
650 size_t num_points = 0;
651 size_t num_motion_points = 0;
653 for (
int i = 0; i < size; i++) {
666 num_motion_triangles++;
693 const size_t size = range.
size();
711 float unalignedSplitSAH =
FLT_MAX;
712 float unalignedLeafSAH =
FLT_MAX;
714 bool do_unalinged_split =
false;
723 if (unalignedLeafSAH < unalignedSplitSAH && unalignedSplitSAH < splitSAH &&
730 if (unalignedSplitSAH < splitSAH) {
731 do_unalinged_split =
true;
738 if (do_unalinged_split) {
746 if (do_unalinged_split) {
760 inner = make_unique<InnerNode>(bounds, std::move(leftnode), std::move(rightnode));
764 inner = make_unique<InnerNode>(bounds);
768 [
this, inner_ptr, left, level] {
thread_build_node(inner_ptr, 0, left, level + 1); });
770 [
this, inner_ptr, right, level] {
thread_build_node(inner_ptr, 1, right, level + 1); });
773 if (do_unalinged_split) {
774 inner->set_aligned_space(aligned_space);
809 if (split.no_split) {
819 float unalignedSplitSAH =
FLT_MAX;
822 bool do_unalinged_split =
false;
832 if (unalignedSplitSAH < splitSAH) {
833 do_unalinged_split =
true;
840 if (do_unalinged_split) {
841 unaligned_split.
split(
this, left, right, range);
844 split.split(
this, left, right, range);
850 if (do_unalinged_split) {
872 inner = make_unique<InnerNode>(bounds, std::move(leftnode), std::move(rightnode));
876 inner = make_unique<InnerNode>(bounds);
888 task_pool.
push([
this, inner_ptr, left, level, refs = std::move(left_references)]()
mutable {
891 task_pool.
push([
this, inner_ptr, right, level, refs = std::move(right_references)]()
mutable {
896 if (do_unalinged_split) {
897 inner->set_aligned_space(aligned_space);
911 return make_unique<LeafNode>(bounds, 0, 0, 0);
924 ref->
bounds(), visibility, start, start + 1);
926 leaf_node->time_to = ref->
time_to();
930 const int mid = num / 2;
935 bounds.
grow(leaf0->bounds);
936 bounds.
grow(leaf1->bounds);
938 const float time_from =
min(leaf0->time_from, leaf1->time_from);
939 const float time_to =
max(leaf0->time_to, leaf1->time_to);
942 bounds, std::move(leaf0), std::move(leaf1));
943 inner_node->time_from = time_from;
944 inner_node->time_to = time_to;
966 using LeafStackAllocator = StackAllocator<256, int>;
967 using LeafTimeStackAllocator = StackAllocator<256, float2>;
968 using LeafReferenceStackAllocator = StackAllocator<256, BVHReference>;
985 int num_new_prims = 0;
987 for (
int i = 0; i < range.
size(); i++) {
991 p_ref[type_index].push_back(ref);
992 p_type[type_index].push_back(ref.
prim_type());
993 p_index[type_index].push_back(ref.
prim_index());
1002 object_references.push_back(ref);
1018 size_t start_index = 0;
1023 local_prim_type.resize(num_new_prims);
1024 local_prim_index.resize(num_new_prims);
1025 local_prim_object.resize(num_new_prims);
1027 local_prim_time.resize(num_new_prims);
1030 const int num = (int)p_type[i].size();
1032 assert(p_type[i].size() == p_index[i].size());
1033 assert(p_type[i].size() == p_object[i].size());
1035 bool alignment_found =
false;
1036 for (
int j = 0; j < num; ++j) {
1037 const int index = start_index + j;
1038 local_prim_type[
index] = p_type[i][j];
1039 local_prim_index[
index] = p_index[i][j];
1040 local_prim_object[
index] = p_object[i][j];
1042 local_prim_time[
index] = p_time[i][j];
1049 bounds[i], visibility[i], start_index, start_index + num);
1051 float time_from = 1.0f;
1052 float time_to = 0.0f;
1053 for (
int j = 0; j < num; ++j) {
1058 leaf_node->time_from = time_from;
1059 leaf_node->time_to = time_to;
1061 if (alignment_found) {
1064 for (
int j = 0; j < num; ++j) {
1067 ref, aligned_space);
1068 leaf_node->bounds.grow(ref_bounds);
1071 leaf_node->set_aligned_space(aligned_space);
1073 leaves[num_leaves++] = std::move(leaf_node);
1078 const int num_new_leaf_data = start_index;
1079 const size_t new_leaf_data_size =
sizeof(int) * num_new_leaf_data;
1092 const size_t range_end = start_index + range.
size();
1099 const float factor = (1.0f -
progress);
1100 const size_t reserve = (size_t)(range_end + (
float)range_end * factor);
1117 if (new_leaf_data_size > 0) {
1118 memcpy(&
prim_type[start_index], local_prim_type.data(), new_leaf_data_size);
1119 memcpy(&
prim_index[start_index], local_prim_index.data(), new_leaf_data_size);
1120 memcpy(&
prim_object[start_index], local_prim_object.data(), new_leaf_data_size);
1123 &
prim_time[start_index], local_prim_time.data(),
sizeof(
float2) * num_new_leaf_data);
1133 start_index = range.
start();
1134 if (new_leaf_data_size > 0) {
1135 memcpy(&
prim_type[start_index], local_prim_type.data(), new_leaf_data_size);
1136 memcpy(&
prim_index[start_index], local_prim_index.data(), new_leaf_data_size);
1137 memcpy(&
prim_object[start_index], local_prim_object.data(), new_leaf_data_size);
1140 &
prim_time[start_index], local_prim_time.data(),
sizeof(
float2) * num_new_leaf_data);
1149 for (
int i = 0; i < num_leaves; ++i) {
1151 leaf->
lo += start_index;
1152 leaf->
hi += start_index;
1156 if (num_leaves == 0 || ob_num) {
1160 const BVHReference *ref = (ob_num) ? object_references.data() :
nullptr;
1168 if (num_leaves == 1) {
1173 return std::move(leaves[0]);
1175 if (num_leaves == 2) {
1176 return make_unique<InnerNode>(range.
bounds(), std::move(leaves[0]), std::move(leaves[1]));
1178 if (num_leaves == 3) {
1179 const BoundBox inner_bounds =
merge(leaves[1]->bounds, leaves[2]->bounds);
1181 inner_bounds, std::move(leaves[1]), std::move(leaves[2]));
1182 return make_unique<InnerNode>(range.
bounds(), std::move(leaves[0]), std::move(inner));
1187 const BoundBox inner_bounds_a =
merge(leaves[0]->bounds, leaves[1]->bounds);
1188 const BoundBox inner_bounds_b =
merge(leaves[2]->bounds, leaves[3]->bounds);
1190 inner_bounds_a, std::move(leaves[0]), std::move(leaves[1]));
1192 inner_bounds_b, std::move(leaves[2]), std::move(leaves[3]));
1193 const BoundBox inner_bounds_c =
merge(inner_a->bounds, inner_b->bounds);
1195 inner_bounds_c, std::move(inner_a), std::move(inner_b));
1196 if (num_leaves == 5) {
1197 return make_unique<InnerNode>(range.
bounds(), std::move(inner_c), std::move(leaves[4]));
1201#undef MAX_ITEMS_PER_LEAF
1211 for (
int i = 0; i < iterations; i++) {
1220 if (
node->is_leaf() || max_depth < 0) {
1227 for (
size_t c = 0; c < 2; c++) {
1235 const float area0 = bounds0.
half_area();
1236 const float area1 = bounds1.
half_area();
1242 int best_child = -1;
1243 int best_target = -1;
1244 int best_other = -1;
1246 for (
size_t c = 0; c < 2; c++) {
1248 if (parent->
children[c]->is_leaf()) {
1253 const BoundBox &other = (c == 0) ? bounds1 : bounds0;
1260 const float cost0 =
merge(other, target1).half_area() - child_area[c];
1261 const float cost1 =
merge(target0, other).half_area() - child_area[c];
1263 if (
min(cost0, cost1) < best_cost) {
1264 best_child = (int)c;
1265 best_other = (int)(1 - c);
1267 if (cost0 < cost1) {
1279 if (best_cost >= 0) {
1283 assert(best_child == 0 || best_child == 1);
1284 assert(best_target != -1);
static size_t count_primitives(Geometry *geom)
static size_t count_curve_segments(Hair *hair)
@ BVH_STAT_UNALIGNED_COUNT
Attribute * find(ustring name) const
const T * data(const int step=0) const
int num_motion_steps() const
void add_reference_triangles(BoundBox &root, BoundBox ¢er, Mesh *mesh, const int object_index)
BVHBuild(const vector< Object * > &objects, array< int > &prim_type, array< int > &prim_index, array< int > &prim_object, array< float2 > &prim_time, const BVHParams ¶ms, Progress &progress)
void thread_build_spatial_split_node(InnerNode *inner, const int child, const BVHRange &range, vector< BVHReference > &references, int level)
unique_ptr< BVHNode > run()
void rotate(BVHNode *node, const int max_depth)
bool range_within_max_leaf_size(const BVHRange &range, const vector< BVHReference > &references) const
thread_spin_lock spatial_spin_lock
void add_references(BVHRange &root)
void add_reference_object(BoundBox &root, BoundBox ¢er, Object *ob, const int i)
unique_ptr< BVHNode > create_leaf_node(const BVHRange &range, const vector< BVHReference > &references)
size_t spatial_free_index
void add_reference_curves(BoundBox &root, BoundBox ¢er, Hair *hair, const int object_index)
BVHUnaligned unaligned_heuristic
friend class BVHObjectBinning
unique_ptr< BVHNode > create_object_leaf_nodes(const BVHReference *ref, const int start, const int num)
array< float2 > & prim_time
vector< Object * > objects
unique_ptr< BVHNode > build_node(const BVHRange &range, vector< BVHReference > &references, const int level, BVHSpatialStorage *storage)
array< int > & prim_index
enumerable_thread_specific< BVHSpatialStorage > spatial_storage
size_t progress_original_total
float spatial_min_overlap
void thread_build_node(InnerNode *inner, const int child, const BVHObjectBinning &range, const int level)
double progress_start_time
array< int > & prim_object
friend class BVHMixedSplit
vector< BVHReference > references
void add_reference_points(BoundBox &root, BoundBox ¢er, PointCloud *pointcloud, const int i)
void add_reference_geometry(BoundBox &root, BoundBox ¢er, Geometry *geom, const int object_index)
__forceinline void split(BVHBuild *builder, BVHRange &left, BVHRange &right, const BVHRange &range)
void split(BVHReference *prims, BVHObjectBinning &left_o, BVHObjectBinning &right_o) const
__forceinline BVHObjectBinning()
__forceinline const BoundBox & unaligned_bounds()
int max_triangle_leaf_size
int num_motion_triangle_steps
float spatial_split_alpha
int max_motion_curve_leaf_size
int max_motion_point_leaf_size
int max_motion_triangle_leaf_size
int num_motion_point_steps
float unaligned_split_threshold
__forceinline bool small_enough_for_leaf(const int size, const int level)
int num_motion_curve_steps
__forceinline int size() const
__forceinline int start() const
__forceinline const BoundBox & bounds() const
__forceinline void set_start(const int start_)
__forceinline int end() const
__forceinline int prim_type() const
__forceinline int prim_object() const
__forceinline BVHReference()=default
__forceinline float time_from() const
__forceinline const BoundBox & bounds() const
__forceinline float time_to() const
__forceinline int prim_index() const
Transform compute_aligned_space(const BVHObjectBinning &range, const BVHReference *references) const
BoundBox compute_aligned_prim_boundbox(const BVHReference &prim, const Transform &aligned_space) const
BoundBox compute_aligned_boundbox(const BVHObjectBinning &range, const BVHReference *references, const Transform &aligned_space, BoundBox *cent_bounds=nullptr) const
__forceinline float half_area() const
__forceinline bool valid() const
__forceinline float safe_area() const
__forceinline void grow(const float3 &pt)
__forceinline float3 center2() const
bool is_pointcloud() const
const packed_float3 * get_position() const
virtual bool has_motion_blur() const
const float * get_radius() const
Curve get_curve(const size_t i) const
size_t num_curves() const
PrimitiveType primitive_type() const override
unique_ptr< BVHNode > children[kNumMaxChildren]
bool has_motion_blur() const override
size_t num_triangles() const
Triangle get_triangle(const size_t i) const
PrimitiveType primitive_type() const override
NODE_DECLARE BoundBox bounds
Point get_point(const int i) const
size_t num_points() const
PrimitiveType primitive_type() const override
void set_substatus(const string &substatus_)
void push(TaskRunFunction &&task)
void wait_work(Summary *stats=nullptr)
void reserve(const size_t newcapacity)
T * resize(const size_t newsize)
#define PRIMITIVE_PACK_SEGMENT(type, segment)
#define PRIMITIVE_INDEX(type)
#define CCL_NAMESPACE_END
#define assert(assertion)
#define storage(slot, qualifiers)
OrientationBounds merge(const OrientationBounds &cone_a, const OrientationBounds &cone_b)
CCL_NAMESPACE_BEGIN ccl_device_inline float3 zero_float3()
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
string string_human_readable_number(size_t num)
CCL_NAMESPACE_BEGIN string string_printf(const char *format,...)
void cardinal_motion_keys(const Attribute *attr_P, const Attribute *attr_R, const size_t num_steps, const float time, size_t k0, size_t k1, size_t k2, size_t k3, float4 r_keys[4]) const
void bounds_grow(const int k, const packed_float3 *curve_keys, const float *curve_radius, BoundBox &bounds) const
void bounds_grow(const packed_float3 *verts, BoundBox &bounds) const
void motion_verts(const Attribute *attr_P, const size_t num_steps, const float time, float3 r_verts[3]) const
bool valid(const packed_float3 *verts) const
void bounds_grow(const packed_float3 *points, const float *radius, BoundBox &bounds) const
float4 motion_key(const float *radius, const Attribute *attr_P, const Attribute *attr_R, const size_t num_steps, const float time, size_t p) const
std::unique_lock< std::mutex > thread_scoped_lock
CCL_NAMESPACE_BEGIN double time_dt()