Blender V5.3
build.cpp
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2009-2010 NVIDIA Corporation
2 * SPDX-FileCopyrightText: 2011-2022 Blender Foundation
3 *
4 * SPDX-License-Identifier: Apache-2.0
5 *
6 * Adapted code from NVIDIA Corporation. */
7
8#include "bvh/build.h"
9
10#include "bvh/binning.h"
11#include "bvh/node.h"
12#include "bvh/params.h"
13#include "bvh/split.h"
14
15#include "scene/curves.h"
16#include "scene/hair.h"
17#include "scene/mesh.h"
18#include "scene/object.h"
19#include "scene/pointcloud.h"
20#include "scene/scene.h"
21
22#include "util/algorithm.h"
23
24#include "util/log.h"
25#include "util/progress.h"
27#include "util/time.h"
28
30
31/* Constructor / Destructor */
32
34 array<int> &prim_type_,
35 array<int> &prim_index_,
36 array<int> &prim_object_,
37 array<float2> &prim_time_,
38 const BVHParams &params_,
39 Progress &progress_)
40 : objects(objects_),
41 prim_type(prim_type_),
42 prim_index(prim_index_),
43 prim_object(prim_object_),
44 prim_time(prim_time_),
45 params(params_),
46 progress(progress_),
48 unaligned_heuristic(objects_)
49{
51}
52
53BVHBuild::~BVHBuild() = default;
54
55/* Adding References */
56
58 BoundBox &center,
59 Mesh *mesh,
60 const int object_index)
61{
62 const PrimitiveType primitive_type = mesh->primitive_type();
63 const Attribute *attr_P = mesh->attributes.find(ATTR_STD_POSITION);
64 const bool has_motion = mesh->has_motion_blur() && attr_P->has_motion();
65 const size_t num_triangles = mesh->num_triangles();
66 for (uint j = 0; j < num_triangles; j++) {
67 const Mesh::Triangle t = mesh->get_triangle(j);
68 const packed_float3 *verts = mesh->get_position();
69 if (!has_motion) {
71 t.bounds_grow(verts, bounds);
72 if (bounds.valid() && t.valid(verts)) {
73 references.push_back(BVHReference(bounds, j, object_index, primitive_type));
74 root.grow(bounds);
75 center.grow(bounds.center2());
76 }
77 }
79 /* Motion triangles, simple case: single node for the whole
80 * primitive. Lowest memory footprint and faster BVH build but
81 * least optimal ray-tracing.
82 */
83 /* TODO(sergey): Support motion steps for spatially split BVH. */
85 for (int attr_step = 0; attr_step < attr_P->num_motion_steps(); attr_step++) {
86 t.bounds_grow(attr_P->data<packed_float3>(attr_step), bounds);
87 }
88 if (bounds.valid()) {
89 references.push_back(BVHReference(bounds, j, object_index, primitive_type));
90 root.grow(bounds);
91 center.grow(bounds.center2());
92 }
93 }
94 else {
95 /* Motion triangles, trace optimized case: we split triangle
96 * primitives into separate nodes for each of the time steps.
97 * This way we minimize overlap of neighbor triangle primitives.
98 */
99 const int num_bvh_steps = params.num_motion_triangle_steps * 2 + 1;
100 const float num_bvh_steps_inv_1 = 1.0f / (num_bvh_steps - 1);
101 const size_t num_steps = mesh->get_motion_steps();
102 /* Calculate bounding box of the previous time step.
103 * Will be reused later to avoid duplicated work on
104 * calculating BVH time step boundbox.
105 */
106 float3 prev_verts[3];
107 t.motion_verts(attr_P, num_steps, 0.0f, prev_verts);
108 BoundBox prev_bounds = BoundBox::empty;
109 prev_bounds.grow(prev_verts[0]);
110 prev_bounds.grow(prev_verts[1]);
111 prev_bounds.grow(prev_verts[2]);
112 /* Create all primitive time steps, */
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;
115 float3 curr_verts[3];
116 t.motion_verts(attr_P, num_steps, curr_time, curr_verts);
117 BoundBox curr_bounds = BoundBox::empty;
118 curr_bounds.grow(curr_verts[0]);
119 curr_bounds.grow(curr_verts[1]);
120 curr_bounds.grow(curr_verts[2]);
121 BoundBox bounds = prev_bounds;
122 bounds.grow(curr_bounds);
123 if (bounds.valid()) {
124 const float prev_time = (float)(bvh_step - 1) * num_bvh_steps_inv_1;
125 references.push_back(
126 BVHReference(bounds, j, object_index, primitive_type, prev_time, curr_time));
127 root.grow(bounds);
128 center.grow(bounds.center2());
129 }
130 /* Current time boundbox becomes previous one for the
131 * next time step.
132 */
133 prev_bounds = curr_bounds;
134 }
135 }
136 }
137}
138
140 BoundBox &center,
141 Hair *hair,
142 const int object_index)
143{
144 const Attribute *attr_P = hair->attributes.find(ATTR_STD_POSITION);
145 const Attribute *attr_R = hair->attributes.find(ATTR_STD_RADIUS);
146 const bool has_motion = hair->has_motion_blur() && attr_P->has_motion();
147
148 const PrimitiveType primitive_type = hair->primitive_type();
149
150 const size_t num_curves = hair->num_curves();
151 for (uint j = 0; j < num_curves; j++) {
152 const Hair::Curve curve = hair->get_curve(j);
153 const float *curve_radius = hair->get_radius();
154 for (int k = 0; k < curve.num_keys - 1; k++) {
155 if (!has_motion) {
156 /* Really simple logic for static hair. */
157 BoundBox bounds = BoundBox::empty;
158 curve.bounds_grow(k, hair->get_position(), curve_radius, bounds);
159 if (bounds.valid()) {
160 const int packed_type = PRIMITIVE_PACK_SEGMENT(primitive_type, k);
161 references.push_back(BVHReference(bounds, j, object_index, packed_type));
162 root.grow(bounds);
163 center.grow(bounds.center2());
164 }
165 }
167 /* Simple case of motion curves: single node for the whole
168 * shutter time. Lowest memory usage but less optimal
169 * rendering.
170 */
171 /* TODO(sergey): Support motion steps for spatially split BVH. */
172 BoundBox bounds = BoundBox::empty;
173 for (int attr_step = 0; attr_step < attr_P->num_motion_steps(); attr_step++) {
174 curve.bounds_grow(
175 k, attr_P->data<packed_float3>(attr_step), attr_R->data<float>(attr_step), bounds);
176 }
177 if (bounds.valid()) {
178 const int packed_type = PRIMITIVE_PACK_SEGMENT(primitive_type, k);
179 references.push_back(BVHReference(bounds, j, object_index, packed_type));
180 root.grow(bounds);
181 center.grow(bounds.center2());
182 }
183 }
184 else {
185 /* Motion curves, trace optimized case: we split curve keys
186 * primitives into separate nodes for each of the time steps.
187 * This way we minimize overlap of neighbor curve primitives.
188 */
189 const int num_bvh_steps = params.num_motion_curve_steps * 2 + 1;
190 const float num_bvh_steps_inv_1 = 1.0f / (num_bvh_steps - 1);
191 const size_t num_steps = hair->get_motion_steps();
192 /* Calculate bounding box of the previous time step.
193 * Will be reused later to avoid duplicated work on
194 * calculating BVH time step boundbox.
195 */
196 float4 prev_keys[4];
198 attr_P, attr_R, num_steps, 0.0f, k - 1, k, k + 1, k + 2, prev_keys);
199 BoundBox prev_bounds = BoundBox::empty;
200 curve.bounds_grow(prev_keys, prev_bounds);
201 /* Create all primitive time steps, */
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;
204 float4 curr_keys[4];
206 attr_P, attr_R, num_steps, curr_time, k - 1, k, k + 1, k + 2, curr_keys);
207 BoundBox curr_bounds = BoundBox::empty;
208 curve.bounds_grow(curr_keys, curr_bounds);
209 BoundBox bounds = prev_bounds;
210 bounds.grow(curr_bounds);
211 if (bounds.valid()) {
212 const float prev_time = (float)(bvh_step - 1) * num_bvh_steps_inv_1;
213 const int packed_type = PRIMITIVE_PACK_SEGMENT(primitive_type, k);
214 references.push_back(
215 BVHReference(bounds, j, object_index, packed_type, prev_time, curr_time));
216 root.grow(bounds);
217 center.grow(bounds.center2());
218 }
219 /* Current time boundbox becomes previous one for the
220 * next time step.
221 */
222 prev_bounds = curr_bounds;
223 }
224 }
225 }
226 }
227}
228
230 BoundBox &center,
231 PointCloud *pointcloud,
232 const int i)
233{
234 const Attribute *attr_P = pointcloud->attributes.find(ATTR_STD_POSITION);
235 const Attribute *attr_R = pointcloud->attributes.find(ATTR_STD_RADIUS);
236 const bool has_motion = pointcloud->has_motion_blur() && attr_P->has_motion();
237
238 const packed_float3 *points_data = pointcloud->get_position();
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();
242
243 if (!has_motion) {
244 /* Really simple logic for static points. */
245 const PrimitiveType primitive_type = pointcloud->primitive_type();
246 for (uint j = 0; j < num_points; j++) {
247 const PointCloud::Point point = pointcloud->get_point(j);
248 BoundBox bounds = BoundBox::empty;
249 point.bounds_grow(points_data, radius_data, bounds);
250 if (bounds.valid()) {
251 references.push_back(BVHReference(bounds, j, i, primitive_type));
252 root.grow(bounds);
253 center.grow(bounds.center2());
254 }
255 }
256 }
258 /* Simple case of motion points: single node for the whole
259 * shutter time. Lowest memory usage but less optimal
260 * rendering.
261 */
262 /* TODO(sergey): Support motion steps for spatially split BVH. */
263 const PrimitiveType primitive_type = pointcloud->primitive_type();
264 for (uint j = 0; j < num_points; j++) {
265 const PointCloud::Point point = pointcloud->get_point(j);
266 BoundBox bounds = BoundBox::empty;
267 for (int attr_step = 0; attr_step < attr_P->num_motion_steps(); attr_step++) {
268 const packed_float3 *mP = attr_P->data<packed_float3>(attr_step);
269 const float *mR = attr_R->data<float>(attr_step);
270 point.bounds_grow(make_float4(float3(mP[j]), mR[j]), bounds);
271 }
272 if (bounds.valid()) {
273 references.push_back(BVHReference(bounds, j, i, primitive_type));
274 root.grow(bounds);
275 center.grow(bounds.center2());
276 }
277 }
278 }
279 else {
280 /* Motion points, trace optimized case: we split point
281 * primitives into separate nodes for each of the time steps.
282 * This way we minimize overlap of neighbor point primitives.
283 */
284 const int num_bvh_steps = params.num_motion_point_steps * 2 + 1;
285 const float num_bvh_steps_inv_1 = 1.0f / (num_bvh_steps - 1);
286 const Attribute *attr_R_motion = attr_R->has_motion() ? attr_R : nullptr;
287 const PrimitiveType primitive_type = pointcloud->primitive_type();
288
289 for (uint j = 0; j < num_points; j++) {
290 const PointCloud::Point point = pointcloud->get_point(j);
291
292 /* Calculate bounding box of the previous time step.
293 * Will be reused later to avoid duplicated work on
294 * calculating BVH time step boundbox.
295 */
296 const float4 prev_key = point.motion_key(
297 radius_data, attr_P, attr_R_motion, num_steps, 0.0f, j);
298 BoundBox prev_bounds = BoundBox::empty;
299 point.bounds_grow(prev_key, prev_bounds);
300 /* Create all primitive time steps, */
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;
303 const float4 curr_key = point.motion_key(
304 radius_data, attr_P, attr_R_motion, num_steps, curr_time, j);
305 BoundBox curr_bounds = BoundBox::empty;
306 point.bounds_grow(curr_key, curr_bounds);
307 BoundBox bounds = prev_bounds;
308 bounds.grow(curr_bounds);
309 if (bounds.valid()) {
310 const float prev_time = (float)(bvh_step - 1) * num_bvh_steps_inv_1;
311 references.push_back(BVHReference(bounds, j, i, primitive_type, prev_time, curr_time));
312 root.grow(bounds);
313 center.grow(bounds.center2());
314 }
315 /* Current time boundbox becomes previous one for the
316 * next time step.
317 */
318 prev_bounds = curr_bounds;
319 }
320 }
321 }
322}
323
325 BoundBox &center,
326 Geometry *geom,
327 const int object_index)
328{
329 if (geom->is_mesh() || geom->is_volume()) {
330 Mesh *mesh = static_cast<Mesh *>(geom);
331 add_reference_triangles(root, center, mesh, object_index);
332 }
333 else if (geom->is_hair()) {
334 Hair *hair = static_cast<Hair *>(geom);
335 add_reference_curves(root, center, hair, object_index);
336 }
337 else if (geom->is_pointcloud()) {
338 PointCloud *pointcloud = static_cast<PointCloud *>(geom);
339 add_reference_points(root, center, pointcloud, object_index);
340 }
341}
342
343void BVHBuild::add_reference_object(BoundBox &root, BoundBox &center, Object *ob, const int i)
344{
345 references.push_back(BVHReference(ob->bounds, -1, i, 0));
346 root.grow(ob->bounds);
347 center.grow(ob->bounds.center2());
348}
349
350static size_t count_curve_segments(Hair *hair)
351{
352 size_t num = 0;
353 const size_t num_curves = hair->num_curves();
354
355 for (size_t i = 0; i < num_curves; i++) {
356 num += hair->get_curve(i).num_keys - 1;
357 }
358
359 return num;
360}
361
362static size_t count_primitives(Geometry *geom)
363{
364 if (geom->is_mesh() || geom->is_volume()) {
365 Mesh *mesh = static_cast<Mesh *>(geom);
366 return mesh->num_triangles();
367 }
368 if (geom->is_hair()) {
369 Hair *hair = static_cast<Hair *>(geom);
370 return count_curve_segments(hair);
371 }
372 if (geom->is_pointcloud()) {
373 PointCloud *pointcloud = static_cast<PointCloud *>(geom);
374 return pointcloud->num_points();
375 }
376
377 return 0;
378}
379
381{
382 /* reserve space for references */
383 size_t num_alloc_references = 0;
384
385 for (Object *ob : objects) {
386 if (params.top_level) {
387 if (!ob->is_traceable()) {
388 continue;
389 }
390 if (!ob->get_geometry()->is_instanced()) {
391 num_alloc_references += count_primitives(ob->get_geometry());
392 }
393 else {
394 num_alloc_references++;
395 }
396 }
397 else {
398 num_alloc_references += count_primitives(ob->get_geometry());
399 }
400 }
401
402 references.reserve(num_alloc_references);
403
404 /* add references from objects */
405 BoundBox bounds = BoundBox::empty;
406 BoundBox center = BoundBox::empty;
407 int i = 0;
408
409 for (Object *ob : objects) {
410 if (params.top_level) {
411 if (!ob->is_traceable()) {
412 ++i;
413 continue;
414 }
415 if (!ob->get_geometry()->is_instanced()) {
416 add_reference_geometry(bounds, center, ob->get_geometry(), i);
417 }
418 else {
419 add_reference_object(bounds, center, ob, i);
420 }
421 }
422 else {
423 add_reference_geometry(bounds, center, ob->get_geometry(), i);
424 }
425
426 i++;
427
428 if (progress.get_cancel()) {
429 return;
430 }
431 }
432
433 /* happens mostly on empty meshes */
434 if (!bounds.valid()) {
435 bounds.grow(zero_float3());
436 }
437
438 root = BVHRange(bounds, center, 0, references.size());
439}
440
441/* Build */
442
444{
445 BVHRange root;
446
447 /* Spatial splits do not work correctly for motion blur: BVHSpatialSplit::split_*_primitive()
448 * methods do not handle motion blur positions.
449 *
450 * TODO(sergey): Support motion blur attributes in the BVHSpatialSplit. */
451 if (!params.top_level) {
452 for (const Object *object : objects) {
453 if (object->get_geometry()->has_motion_blur()) {
455 }
456 }
457 }
458
459 /* add references */
460 add_references(root);
461
462 if (progress.get_cancel()) {
463 return nullptr;
464 }
465
466 /* init spatial splits */
467 if (params.top_level) {
468 /* NOTE: Technically it is supported by the builder but it's not really
469 * optimized for speed yet and not really clear yet if it has measurable
470 * improvement on render time. Needs some extra investigation before
471 * enabling spatial split for top level BVH.
472 */
474 }
475
477 !references.empty())
478 {
479 /* Spatial splitting for curve splitting leads to very long build times.
480 *
481 * There are also some issues (and, possibly, bugs in the split builder w.r.t how the alignment
482 * space is interpreted. It would be good to fix those issues, but due to performance, and the
483 * BVH becoming more obsolete with time it might not be the most optimal development time
484 * investment.
485 *
486 * The check is a bit implicit here, it relies on the fact that spatial splits are disabled on
487 * the top level, and that an object has primitives of the same type. */
490 }
491 }
492
495
497
498 /* init progress updates */
499 double build_start_time;
500 build_start_time = progress_start_time = time_dt();
501 progress_count = 0;
502 progress_total = references.size();
504
508 if (need_prim_time) {
510 }
511 else {
512 prim_time.resize(0);
513 }
514
515 /* build recursively */
516 unique_ptr<BVHNode> rootnode;
517
519 /* Perform multithreaded spatial split build. */
520 BVHSpatialStorage *local_storage = &spatial_storage.local();
521 rootnode = build_node(root, references, 0, local_storage);
523 }
524 else {
525 /* Perform multithreaded binning build. */
526 const BVHObjectBinning rootbin(root, (!references.empty()) ? references.data() : nullptr);
527 rootnode = build_node(rootbin, 0);
529 }
530
531 /* clean up temporary memory usage by threads */
532 spatial_storage.clear();
533
534 /* delete if we canceled */
535 if (rootnode) {
536 if (progress.get_cancel()) {
537 rootnode.reset();
538 LOG_DEBUG << "BVH build canceled.";
539 }
540 else {
541 /*rotate(rootnode, 4, 5);*/
542 rootnode->update_visibility();
543 rootnode->update_time();
544 }
545 if (rootnode != nullptr) {
546 LOG_DEBUG << "BVH build statistics:"
547 << " Build time: " << time_dt() - build_start_time << "\n"
548 << " Total number of nodes: "
549 << string_human_readable_number(rootnode->getSubtreeSize(BVH_STAT_NODE_COUNT))
550 << "\n"
551 << " Number of inner nodes: "
552 << string_human_readable_number(rootnode->getSubtreeSize(BVH_STAT_INNER_COUNT))
553 << "\n"
554 << " Number of leaf nodes: "
555 << string_human_readable_number(rootnode->getSubtreeSize(BVH_STAT_LEAF_COUNT))
556 << "\n"
557 << " Number of unaligned nodes: "
558 << string_human_readable_number(rootnode->getSubtreeSize(BVH_STAT_UNALIGNED_COUNT))
559 << "\n"
560 << " Allocation slop factor: "
561 << ((prim_type.capacity() != 0) ? (float)prim_type.size() / prim_type.capacity() :
562 1.0f)
563 << "\n"
564 << " Maximum depth: "
565 << string_human_readable_number(rootnode->getSubtreeSize(BVH_STAT_DEPTH));
566 }
567 }
568
569 return rootnode;
570}
571
573{
574 if (time_dt() - progress_start_time < 0.25) {
575 return;
576 }
577
578 const double progress_start = (double)progress_count / (double)progress_total;
579 const double duplicates = (double)(progress_total - progress_original_total) /
580 (double)progress_total;
581
582 const string msg = string_printf(
583 "Building BVH %.0f%%, duplicates %.0f%%", progress_start * 100.0, duplicates * 100.0);
584
587}
588
590 const int child,
591 const BVHObjectBinning &range,
592 const int level)
593{
594 if (progress.get_cancel()) {
595 return;
596 }
597
598 /* build nodes */
599 unique_ptr<BVHNode> node = build_node(range, level);
600
601 /* set child in inner node */
602 inner->children[child] = std::move(node);
603
604 /* update progress */
605 if (range.size() < THREAD_TASK_SIZE) {
606 /*rotate(node, INT_MAX, 5);*/
607
609
610 progress_count += range.size();
612 }
613}
614
616 const int child,
617 const BVHRange &range,
619 const int level)
620{
621 if (progress.get_cancel()) {
622 return;
623 }
624
625 /* Get per-thread memory for spatial split. */
626 BVHSpatialStorage *local_storage = &spatial_storage.local();
627
628 /* build nodes */
629 unique_ptr<BVHNode> node = build_node(range, references, level, local_storage);
630
631 /* set child in inner node */
632 inner->children[child] = std::move(node);
633}
634
636 const vector<BVHReference> &references) const
637{
638 const size_t size = range.size();
639 const size_t max_leaf_size = max(max(params.max_triangle_leaf_size, params.max_curve_leaf_size),
641
642 if (size > max_leaf_size) {
643 return false;
644 }
645
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;
652
653 for (int i = 0; i < size; i++) {
654 const BVHReference &ref = references[range.start() + i];
655
656 if (ref.prim_type() & PRIMITIVE_CURVE) {
657 if (ref.prim_type() & PRIMITIVE_MOTION) {
658 num_motion_curves++;
659 }
660 else {
661 num_curves++;
662 }
663 }
664 else if (ref.prim_type() & PRIMITIVE_TRIANGLE) {
665 if (ref.prim_type() & PRIMITIVE_MOTION) {
666 num_motion_triangles++;
667 }
668 else {
669 num_triangles++;
670 }
671 }
672 else if (ref.prim_type() & PRIMITIVE_ANY_POINT) {
673 if (ref.prim_type() & PRIMITIVE_MOTION) {
674 num_motion_points++;
675 }
676 else {
677 num_points++;
678 }
679 }
680 }
681
682 return (num_triangles <= params.max_triangle_leaf_size) &&
683 (num_motion_triangles <= params.max_motion_triangle_leaf_size) &&
684 (num_curves <= params.max_curve_leaf_size) &&
685 (num_motion_curves <= params.max_motion_curve_leaf_size) &&
686 (num_points <= params.max_point_leaf_size) &&
687 (num_motion_points <= params.max_motion_point_leaf_size);
688}
689
690/* multithreaded binning builder */
692{
693 const size_t size = range.size();
694 const float leafSAH = params.sah_primitive_cost * range.leafSAH;
695 const float splitSAH = params.sah_node_cost * range.bounds().half_area() +
697
698 /* Have at least one inner node on top level, for performance and correct
699 * visibility tests, since object instances do not check visibility flag.
700 */
701 if (!(range.size() > 0 && params.top_level && level == 0)) {
702 /* Make leaf node when threshold reached or SAH tells us. */
703 if ((params.small_enough_for_leaf(size, level)) ||
704 (range_within_max_leaf_size(range, references) && leafSAH < splitSAH))
705 {
706 return create_leaf_node(range, references);
707 }
708 }
709
710 BVHObjectBinning unaligned_range;
711 float unalignedSplitSAH = FLT_MAX;
712 float unalignedLeafSAH = FLT_MAX;
713 Transform aligned_space;
714 bool do_unalinged_split = false;
715 if (params.use_unaligned_nodes && splitSAH > params.unaligned_split_threshold * leafSAH) {
716 aligned_space = unaligned_heuristic.compute_aligned_space(range, references.data());
717 unaligned_range = BVHObjectBinning(
718 range, references.data(), &unaligned_heuristic, &aligned_space);
719 unalignedSplitSAH = params.sah_node_cost * unaligned_range.unaligned_bounds().half_area() +
720 params.sah_primitive_cost * unaligned_range.splitSAH;
721 unalignedLeafSAH = params.sah_primitive_cost * unaligned_range.leafSAH;
722 if (!(range.size() > 0 && params.top_level && level == 0)) {
723 if (unalignedLeafSAH < unalignedSplitSAH && unalignedSplitSAH < splitSAH &&
725 {
726 return create_leaf_node(range, references);
727 }
728 }
729 /* Check whether unaligned split is better than the regular one. */
730 if (unalignedSplitSAH < splitSAH) {
731 do_unalinged_split = true;
732 }
733 }
734
735 /* Perform split. */
736 BVHObjectBinning left;
737 BVHObjectBinning right;
738 if (do_unalinged_split) {
739 unaligned_range.split(references.data(), left, right);
740 }
741 else {
742 range.split(references.data(), left, right);
743 }
744
745 BoundBox bounds;
746 if (do_unalinged_split) {
747 bounds = unaligned_heuristic.compute_aligned_boundbox(range, references.data(), aligned_space);
748 }
749 else {
750 bounds = range.bounds();
751 }
752
753 /* Create inner node. */
755 if (range.size() < THREAD_TASK_SIZE) {
756 /* local build */
757 unique_ptr<BVHNode> leftnode = build_node(left, level + 1);
758 unique_ptr<BVHNode> rightnode = build_node(right, level + 1);
759
760 inner = make_unique<InnerNode>(bounds, std::move(leftnode), std::move(rightnode));
761 }
762 else {
763 /* Threaded build */
764 inner = make_unique<InnerNode>(bounds);
765 InnerNode *inner_ptr = inner.get();
766
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); });
771 }
772
773 if (do_unalinged_split) {
774 inner->set_aligned_space(aligned_space);
775 }
776
777 return inner;
778}
779
780/* multithreaded spatial split builder */
783 const int level,
785{
786 /* Update progress.
787 *
788 * TODO(sergey): Currently it matches old behavior, but we can move it to the
789 * task thread (which will mimic non=split builder) and save some CPU ticks
790 * on checking cancel status.
791 */
793 if (progress.get_cancel()) {
794 return nullptr;
795 }
796
797 /* Small enough or too deep => create leaf. */
798 if (!(range.size() > 0 && params.top_level && level == 0)) {
799 if (params.small_enough_for_leaf(range.size(), level)) {
800 progress_count += range.size();
801 return create_leaf_node(range, references);
802 }
803 }
804
805 /* Perform splitting test. */
806 BVHMixedSplit split(this, storage, range, references, level);
807
808 if (!(range.size() > 0 && params.top_level && level == 0)) {
809 if (split.no_split) {
810 progress_count += range.size();
811 return create_leaf_node(range, references);
812 }
813 }
814 const float leafSAH = params.sah_primitive_cost * split.leafSAH;
815 const float splitSAH = params.sah_node_cost * range.bounds().half_area() +
816 params.sah_primitive_cost * split.nodeSAH;
817
818 BVHMixedSplit unaligned_split;
819 float unalignedSplitSAH = FLT_MAX;
820 // float unalignedLeafSAH = FLT_MAX;
821 Transform aligned_space;
822 bool do_unalinged_split = false;
823 if (params.use_unaligned_nodes && splitSAH > params.unaligned_split_threshold * leafSAH) {
824 aligned_space = unaligned_heuristic.compute_aligned_space(range, &references.at(0));
825 unaligned_split = BVHMixedSplit(
826 this, storage, range, references, level, &unaligned_heuristic, &aligned_space);
827 // unalignedLeafSAH = params.sah_primitive_cost * split.leafSAH;
828 unalignedSplitSAH = params.sah_node_cost * unaligned_split.bounds.half_area() +
829 params.sah_primitive_cost * unaligned_split.nodeSAH;
830 /* TODO(sergey): Check we can create leaf already. */
831 /* Check whether unaligned split is better than the regular one. */
832 if (unalignedSplitSAH < splitSAH) {
833 do_unalinged_split = true;
834 }
835 }
836
837 /* Do split. */
838 BVHRange left;
839 BVHRange right;
840 if (do_unalinged_split) {
841 unaligned_split.split(this, left, right, range);
842 }
843 else {
844 split.split(this, left, right, range);
845 }
846
847 progress_total += left.size() + right.size() - range.size();
848
849 BoundBox bounds;
850 if (do_unalinged_split) {
851 bounds = unaligned_heuristic.compute_aligned_boundbox(range, &references.at(0), aligned_space);
852 }
853 else {
854 bounds = range.bounds();
855 }
856
857 /* Create inner node. */
859 if (range.size() < THREAD_TASK_SIZE) {
860 /* Local build. */
861
862 /* Build left node. */
863 vector<BVHReference> right_references(references.begin() + right.start(),
864 references.begin() + right.end());
865 right.set_start(0);
866
867 unique_ptr<BVHNode> leftnode = build_node(left, references, level + 1, storage);
868
869 /* Build right node. */
870 unique_ptr<BVHNode> rightnode = build_node(right, right_references, level + 1, storage);
871
872 inner = make_unique<InnerNode>(bounds, std::move(leftnode), std::move(rightnode));
873 }
874 else {
875 /* Threaded build. */
876 inner = make_unique<InnerNode>(bounds);
877
878 vector<BVHReference> left_references(references.begin() + left.start(),
879 references.begin() + left.end());
880 vector<BVHReference> right_references(references.begin() + right.start(),
881 references.begin() + right.end());
882 right.set_start(0);
883
884 InnerNode *inner_ptr = inner.get();
885
886 /* Create tasks for left and right nodes, using copy for most arguments and
887 * move for reference to avoid memory copies. */
888 task_pool.push([this, inner_ptr, left, level, refs = std::move(left_references)]() mutable {
889 thread_build_spatial_split_node(inner_ptr, 0, left, refs, level + 1);
890 });
891 task_pool.push([this, inner_ptr, right, level, refs = std::move(right_references)]() mutable {
892 thread_build_spatial_split_node(inner_ptr, 1, right, refs, level + 1);
893 });
894 }
895
896 if (do_unalinged_split) {
897 inner->set_aligned_space(aligned_space);
898 }
899
900 return inner;
901}
902
903/* Create Nodes */
904
906 const int start,
907 const int num)
908{
909 if (num == 0) {
910 const BoundBox bounds = BoundBox::empty;
911 return make_unique<LeafNode>(bounds, 0, 0, 0);
912 }
913 if (num == 1) {
914 assert(start < prim_type.size());
915 prim_type[start] = ref->prim_type();
916 prim_index[start] = ref->prim_index();
917 prim_object[start] = ref->prim_object();
918 if (need_prim_time) {
919 prim_time[start] = make_float2(ref->time_from(), ref->time_to());
920 }
921
922 const uint visibility = objects[ref->prim_object()]->visibility_for_tracing();
923 unique_ptr<BVHNode> leaf_node = make_unique<LeafNode>(
924 ref->bounds(), visibility, start, start + 1);
925 leaf_node->time_from = ref->time_from();
926 leaf_node->time_to = ref->time_to();
927 return leaf_node;
928 }
929
930 const int mid = num / 2;
931 unique_ptr<BVHNode> leaf0 = create_object_leaf_nodes(ref, start, mid);
932 unique_ptr<BVHNode> leaf1 = create_object_leaf_nodes(ref + mid, start + mid, num - mid);
933
934 BoundBox bounds = BoundBox::empty;
935 bounds.grow(leaf0->bounds);
936 bounds.grow(leaf1->bounds);
937
938 const float time_from = min(leaf0->time_from, leaf1->time_from);
939 const float time_to = max(leaf0->time_to, leaf1->time_to);
940
941 unique_ptr<BVHNode> inner_node = make_unique<InnerNode>(
942 bounds, std::move(leaf0), std::move(leaf1));
943 inner_node->time_from = time_from;
944 inner_node->time_to = time_to;
945 return inner_node;
946}
947
950{
951 /* This is a bit over-allocating here (considering leaf size into account),
952 * but chunk-based re-allocation in vector makes it difficult to use small
953 * size of stack storage here. Some tweaks are possible tho.
954 *
955 * NOTES:
956 * - If the size is too big, we'll have inefficient stack usage,
957 * and lots of cache misses.
958 * - If the size is too small, then we can run out of memory
959 * allowed to be used by vector.
960 * In practice it wouldn't mean crash, just allocator will fall back
961 * to heap which is slower.
962 * - Optimistic re-allocation in STL could jump us out of stack usage
963 * because re-allocation happens in chunks and size of those chunks we
964 * can not control.
965 */
966 using LeafStackAllocator = StackAllocator<256, int>;
967 using LeafTimeStackAllocator = StackAllocator<256, float2>;
968 using LeafReferenceStackAllocator = StackAllocator<256, BVHReference>;
969
975
976 /* TODO(sergey): In theory we should be able to store references. */
978
979 uint visibility[PRIMITIVE_NUM] = {0};
980 BoundBox bounds[PRIMITIVE_NUM] = {};
981 for (int i = 0; i < PRIMITIVE_NUM; i++) {
982 bounds[i] = BoundBox::empty;
983 }
984 int ob_num = 0;
985 int num_new_prims = 0;
986 /* Fill in per-type type/index array. */
987 for (int i = 0; i < range.size(); i++) {
988 const BVHReference &ref = references[range.start() + i];
989 if (ref.prim_index() != -1) {
990 const uint32_t type_index = PRIMITIVE_INDEX(ref.prim_type() & PRIMITIVE_ALL);
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());
994 p_object[type_index].push_back(ref.prim_object());
995 p_time[type_index].push_back(make_float2(ref.time_from(), ref.time_to()));
996
997 bounds[type_index].grow(ref.bounds());
998 visibility[type_index] |= objects[ref.prim_object()]->visibility_for_tracing();
999 ++num_new_prims;
1000 }
1001 else {
1002 object_references.push_back(ref);
1003 ++ob_num;
1004 }
1005 }
1006
1007 /* Create leaf nodes for every existing primitive.
1008 *
1009 * Here we write primitive types, indices and objects to a temporary array.
1010 * This way we keep all the heavy memory allocation code outside of the
1011 * thread lock in the case of spatial split building.
1012 *
1013 * TODO(sergey): With some pointer trickery we can write directly to the
1014 * destination buffers for the non-spatial split BVH.
1015 */
1017 int num_leaves = 0;
1018 size_t start_index = 0;
1019 vector<int, LeafStackAllocator> local_prim_type;
1020 vector<int, LeafStackAllocator> local_prim_index;
1021 vector<int, LeafStackAllocator> local_prim_object;
1023 local_prim_type.resize(num_new_prims);
1024 local_prim_index.resize(num_new_prims);
1025 local_prim_object.resize(num_new_prims);
1026 if (need_prim_time) {
1027 local_prim_time.resize(num_new_prims);
1028 }
1029 for (int i = 0; i < PRIMITIVE_NUM; ++i) {
1030 const int num = (int)p_type[i].size();
1031 if (num != 0) {
1032 assert(p_type[i].size() == p_index[i].size());
1033 assert(p_type[i].size() == p_object[i].size());
1034 Transform aligned_space;
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];
1041 if (need_prim_time) {
1042 local_prim_time[index] = p_time[i][j];
1043 }
1044 if (params.use_unaligned_nodes && !alignment_found) {
1045 alignment_found = unaligned_heuristic.compute_aligned_space(p_ref[i][j], &aligned_space);
1046 }
1047 }
1048 unique_ptr<LeafNode> leaf_node = make_unique<LeafNode>(
1049 bounds[i], visibility[i], start_index, start_index + num);
1050 if (true) {
1051 float time_from = 1.0f;
1052 float time_to = 0.0f;
1053 for (int j = 0; j < num; ++j) {
1054 const BVHReference &ref = p_ref[i][j];
1055 time_from = min(time_from, ref.time_from());
1056 time_to = max(time_to, ref.time_to());
1057 }
1058 leaf_node->time_from = time_from;
1059 leaf_node->time_to = time_to;
1060 }
1061 if (alignment_found) {
1062 /* Need to recalculate leaf bounds with new alignment. */
1063 leaf_node->bounds = BoundBox::empty;
1064 for (int j = 0; j < num; ++j) {
1065 const BVHReference &ref = p_ref[i][j];
1067 ref, aligned_space);
1068 leaf_node->bounds.grow(ref_bounds);
1069 }
1070 /* Set alignment space. */
1071 leaf_node->set_aligned_space(aligned_space);
1072 }
1073 leaves[num_leaves++] = std::move(leaf_node);
1074 start_index += num;
1075 }
1076 }
1077 /* Get size of new data to be copied to the packed arrays. */
1078 const int num_new_leaf_data = start_index;
1079 const size_t new_leaf_data_size = sizeof(int) * num_new_leaf_data;
1080 /* Copy actual data to the packed array. */
1082 spatial_spin_lock.lock();
1083 /* We use first free index in the packed arrays and mode pointer to the
1084 * end of the current range.
1085 *
1086 * This doesn't give deterministic packed arrays, but it shouldn't really
1087 * matter because order of children in BVH is deterministic.
1088 */
1089 start_index = spatial_free_index;
1090 spatial_free_index += range.size();
1091 /* Extend an array when needed. */
1092 const size_t range_end = start_index + range.size();
1093 if (prim_type.size() < range_end) {
1094 /* Avoid extra re-allocations by pre-allocating bigger array in an
1095 * advance.
1096 */
1097 if (range_end >= prim_type.capacity()) {
1098 const float progress = (float)progress_count / (float)progress_total;
1099 const float factor = (1.0f - progress);
1100 const size_t reserve = (size_t)(range_end + (float)range_end * factor);
1101 prim_type.reserve(reserve);
1102 prim_index.reserve(reserve);
1103 prim_object.reserve(reserve);
1104 if (need_prim_time) {
1105 prim_time.reserve(reserve);
1106 }
1107 }
1108
1109 prim_type.resize(range_end);
1110 prim_index.resize(range_end);
1111 prim_object.resize(range_end);
1112 if (need_prim_time) {
1113 prim_time.resize(range_end);
1114 }
1115 }
1116 /* Perform actual data copy. */
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);
1121 if (need_prim_time) {
1122 memcpy(
1123 &prim_time[start_index], local_prim_time.data(), sizeof(float2) * num_new_leaf_data);
1124 }
1125 }
1126 spatial_spin_lock.unlock();
1127 }
1128 else {
1129 /* For the regular BVH builder we simply copy new data starting at the
1130 * range start. This is totally thread-safe, all threads are living
1131 * inside of their own range.
1132 */
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);
1138 if (need_prim_time) {
1139 memcpy(
1140 &prim_time[start_index], local_prim_time.data(), sizeof(float2) * num_new_leaf_data);
1141 }
1142 }
1143 }
1144
1145 /* So far leaves were created with the zero-based index in an arrays,
1146 * here we modify the indices to correspond to actual packed array start
1147 * index.
1148 */
1149 for (int i = 0; i < num_leaves; ++i) {
1150 LeafNode *leaf = (LeafNode *)leaves[i].get();
1151 leaf->lo += start_index;
1152 leaf->hi += start_index;
1153 }
1154
1155 /* Create leaf node for object. */
1156 if (num_leaves == 0 || ob_num) {
1157 /* Only create object leaf nodes if there are objects or no other
1158 * nodes created.
1159 */
1160 const BVHReference *ref = (ob_num) ? object_references.data() : nullptr;
1161 leaves[num_leaves] = create_object_leaf_nodes(ref, start_index + num_new_leaf_data, ob_num);
1162 ++num_leaves;
1163 }
1164
1165 /* TODO(sergey): Need to take care of alignment when number of leaves
1166 * is more than 1.
1167 */
1168 if (num_leaves == 1) {
1169 /* Simplest case: single leaf, just return it.
1170 * In all the rest cases we'll be creating intermediate inner node with
1171 * an appropriate bounding box.
1172 */
1173 return std::move(leaves[0]);
1174 }
1175 if (num_leaves == 2) {
1176 return make_unique<InnerNode>(range.bounds(), std::move(leaves[0]), std::move(leaves[1]));
1177 }
1178 if (num_leaves == 3) {
1179 const BoundBox inner_bounds = merge(leaves[1]->bounds, leaves[2]->bounds);
1180 unique_ptr<BVHNode> inner = make_unique<InnerNode>(
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));
1183 }
1184
1185 /* Should be doing more branches if more primitive types added. */
1186 assert(num_leaves <= 5);
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);
1189 unique_ptr<BVHNode> inner_a = make_unique<InnerNode>(
1190 inner_bounds_a, std::move(leaves[0]), std::move(leaves[1]));
1191 unique_ptr<BVHNode> inner_b = make_unique<InnerNode>(
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);
1194 unique_ptr<BVHNode> inner_c = make_unique<InnerNode>(
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]));
1198 }
1199 return inner_c;
1200
1201#undef MAX_ITEMS_PER_LEAF
1202}
1203
1204/* Tree Rotations */
1205
1206void BVHBuild::rotate(BVHNode *node, const int max_depth, const int iterations)
1207{
1208 /* In tested scenes, this resulted in slightly slower ray-tracing, so disabled
1209 * it for now. could be implementation bug, or depend on the scene. */
1210 if (node) {
1211 for (int i = 0; i < iterations; i++) {
1212 rotate(node, max_depth);
1213 }
1214 }
1215}
1216
1217void BVHBuild::rotate(BVHNode *node, const int max_depth)
1218{
1219 /* nothing to rotate if we reached a leaf node. */
1220 if (node->is_leaf() || max_depth < 0) {
1221 return;
1222 }
1223
1224 InnerNode *parent = (InnerNode *)node;
1225
1226 /* rotate all children first */
1227 for (size_t c = 0; c < 2; c++) {
1228 rotate(parent->children[c].get(), max_depth - 1);
1229 }
1230
1231 /* compute current area of all children */
1232 const BoundBox bounds0 = parent->children[0]->bounds;
1233 const BoundBox bounds1 = parent->children[1]->bounds;
1234
1235 const float area0 = bounds0.half_area();
1236 const float area1 = bounds1.half_area();
1237 float4 child_area = make_float4(area0, area1, 0.0f, 0.0f);
1238
1239 /* find best rotation. we pick a target child of a first child, and swap
1240 * this with an other child. we perform the best such swap. */
1241 float best_cost = FLT_MAX;
1242 int best_child = -1;
1243 int best_target = -1;
1244 int best_other = -1;
1245
1246 for (size_t c = 0; c < 2; c++) {
1247 /* ignore leaf nodes as we cannot descent into */
1248 if (parent->children[c]->is_leaf()) {
1249 continue;
1250 }
1251
1252 InnerNode *child = (InnerNode *)parent->children[c].get();
1253 const BoundBox &other = (c == 0) ? bounds1 : bounds0;
1254
1255 /* transpose child bounds */
1256 const BoundBox target0 = child->children[0]->bounds;
1257 const BoundBox target1 = child->children[1]->bounds;
1258
1259 /* compute cost for both possible swaps */
1260 const float cost0 = merge(other, target1).half_area() - child_area[c];
1261 const float cost1 = merge(target0, other).half_area() - child_area[c];
1262
1263 if (min(cost0, cost1) < best_cost) {
1264 best_child = (int)c;
1265 best_other = (int)(1 - c);
1266
1267 if (cost0 < cost1) {
1268 best_cost = cost0;
1269 best_target = 0;
1270 }
1271 else {
1272 best_cost = cost0;
1273 best_target = 1;
1274 }
1275 }
1276 }
1277
1278 /* if we did not find a swap that improves the SAH then do nothing */
1279 if (best_cost >= 0) {
1280 return;
1281 }
1282
1283 assert(best_child == 0 || best_child == 1);
1284 assert(best_target != -1);
1285
1286 /* perform the best found tree rotation */
1287 InnerNode *child = (InnerNode *)parent->children[best_child].get();
1288
1289 swap(parent->children[best_other], child->children[best_target]);
1290 child->bounds = merge(child->children[0]->bounds, child->children[1]->bounds);
1291}
1292
volatile int lock
btScalar max
static size_t count_primitives(Geometry *geom)
Definition build.cpp:362
static size_t count_curve_segments(Hair *hair)
Definition build.cpp:350
@ BVH_STAT_NODE_COUNT
Definition bvh/node.h:17
@ BVH_STAT_DEPTH
Definition bvh/node.h:28
@ BVH_STAT_UNALIGNED_COUNT
Definition bvh/node.h:23
@ BVH_STAT_INNER_COUNT
Definition bvh/node.h:18
@ BVH_STAT_LEAF_COUNT
Definition bvh/node.h:19
Attribute * find(ustring name) const
const T * data(const int step=0) const
bool has_motion() const
int num_motion_steps() const
void add_reference_triangles(BoundBox &root, BoundBox &center, Mesh *mesh, const int object_index)
Definition build.cpp:57
size_t progress_count
Definition build.h:127
BVHBuild(const vector< Object * > &objects, array< int > &prim_type, array< int > &prim_index, array< int > &prim_object, array< float2 > &prim_time, const BVHParams &params, Progress &progress)
Definition build.cpp:33
void thread_build_spatial_split_node(InnerNode *inner, const int child, const BVHRange &range, vector< BVHReference > &references, int level)
Definition build.cpp:615
unique_ptr< BVHNode > run()
Definition build.cpp:443
void rotate(BVHNode *node, const int max_depth)
Definition build.cpp:1217
bool range_within_max_leaf_size(const BVHRange &range, const vector< BVHReference > &references) const
Definition build.cpp:635
thread_spin_lock spatial_spin_lock
Definition build.h:135
thread_mutex build_mutex
Definition build.h:99
void add_references(BVHRange &root)
Definition build.cpp:380
void add_reference_object(BoundBox &root, BoundBox &center, Object *ob, const int i)
Definition build.cpp:343
unique_ptr< BVHNode > create_leaf_node(const BVHRange &range, const vector< BVHReference > &references)
Definition build.cpp:948
bool need_prim_time
Definition build.h:119
size_t spatial_free_index
Definition build.h:134
void add_reference_curves(BoundBox &root, BoundBox &center, Hair *hair, const int object_index)
Definition build.cpp:139
BVHUnaligned unaligned_heuristic
Definition build.h:141
TaskPool task_pool
Definition build.h:138
friend class BVHObjectBinning
Definition build.h:57
unique_ptr< BVHNode > create_object_leaf_nodes(const BVHReference *ref, const int start, const int num)
Definition build.cpp:905
Progress & progress
Definition build.h:125
array< float2 > & prim_time
Definition build.h:117
vector< Object * > objects
Definition build.h:109
unique_ptr< BVHNode > build_node(const BVHRange &range, vector< BVHReference > &references, const int level, BVHSpatialStorage *storage)
Definition build.cpp:781
array< int > & prim_index
Definition build.h:115
enumerable_thread_specific< BVHSpatialStorage > spatial_storage
Definition build.h:133
size_t progress_total
Definition build.h:128
size_t progress_original_total
Definition build.h:129
BVHParams params
Definition build.h:122
float spatial_min_overlap
Definition build.h:132
@ THREAD_TASK_SIZE
Definition build.h:89
void thread_build_node(InnerNode *inner, const int child, const BVHObjectBinning &range, const int level)
Definition build.cpp:589
array< int > & prim_type
Definition build.h:114
double progress_start_time
Definition build.h:126
array< int > & prim_object
Definition build.h:116
void progress_update()
Definition build.cpp:572
friend class BVHMixedSplit
Definition build.h:52
vector< BVHReference > references
Definition build.h:110
void add_reference_points(BoundBox &root, BoundBox &center, PointCloud *pointcloud, const int i)
Definition build.cpp:229
void add_reference_geometry(BoundBox &root, BoundBox &center, Geometry *geom, const int object_index)
Definition build.cpp:324
BVHMixedSplit()=default
__forceinline void split(BVHBuild *builder, BVHRange &left, BVHRange &right, const BVHRange &range)
Definition bvh/split.h:220
BoundBox bounds
Definition bvh/split.h:177
BoundBox bounds
Definition bvh/node.h:89
void split(BVHReference *prims, BVHObjectBinning &left_o, BVHObjectBinning &right_o) const
Definition binning.cpp:212
__forceinline BVHObjectBinning()
Definition binning.h:28
__forceinline const BoundBox & unaligned_bounds()
Definition binning.h:37
int max_point_leaf_size
Definition params.h:76
bool use_spatial_split
Definition params.h:60
int max_triangle_leaf_size
Definition params.h:72
int num_motion_triangle_steps
Definition params.h:100
float spatial_split_alpha
Definition params.h:61
int max_curve_leaf_size
Definition params.h:74
bool use_unaligned_nodes
Definition params.h:88
int max_motion_curve_leaf_size
Definition params.h:75
int max_motion_point_leaf_size
Definition params.h:77
int max_motion_triangle_leaf_size
Definition params.h:73
float sah_node_cost
Definition params.h:67
bool use_motion_steps()
Definition params.h:168
int num_motion_point_steps
Definition params.h:102
float sah_primitive_cost
Definition params.h:68
bool top_level
Definition params.h:80
float unaligned_split_threshold
Definition params.h:64
__forceinline bool small_enough_for_leaf(const int size, const int level)
Definition params.h:163
int num_motion_curve_steps
Definition params.h:101
__forceinline int size() const
Definition params.h:281
__forceinline int start() const
Definition params.h:277
__forceinline const BoundBox & bounds() const
Definition params.h:269
__forceinline BVHRange()
Definition params.h:245
__forceinline void set_start(const int start_)
Definition params.h:264
__forceinline int end() const
Definition params.h:285
__forceinline int prim_type() const
Definition params.h:216
__forceinline int prim_object() const
Definition params.h:212
__forceinline BVHReference()=default
__forceinline float time_from() const
Definition params.h:220
__forceinline const BoundBox & bounds() const
Definition params.h:204
__forceinline float time_to() const
Definition params.h:224
__forceinline int prim_index() const
Definition params.h:208
Transform compute_aligned_space(const BVHObjectBinning &range, const BVHReference *references) const
Definition unaligned.cpp:20
BoundBox compute_aligned_prim_boundbox(const BVHReference &prim, const Transform &aligned_space) const
Definition unaligned.cpp:78
BoundBox compute_aligned_boundbox(const BVHObjectBinning &range, const BVHReference *references, const Transform &aligned_space, BoundBox *cent_bounds=nullptr) const
Definition unaligned.cpp:99
__forceinline float half_area() const
Definition boundbox.h:106
__forceinline bool valid() const
Definition boundbox.h:127
__forceinline float safe_area() const
Definition boundbox.h:92
__forceinline void grow(const float3 &pt)
Definition boundbox.h:35
__forceinline float3 center2() const
Definition boundbox.h:117
bool is_volume() const
bool is_pointcloud() const
bool is_hair() const
const packed_float3 * get_position() const
virtual bool has_motion_blur() const
const float * get_radius() const
AttributeSet attributes
bool is_mesh() const
Definition hair.h:13
Curve get_curve(const size_t i) const
Definition hair.h:94
size_t num_curves() const
Definition hair.h:109
PrimitiveType primitive_type() const override
Definition hair.cpp:449
unique_ptr< BVHNode > children[kNumMaxChildren]
Definition bvh/node.h:166
bool has_motion_blur() const override
size_t num_triangles() const
Definition scene/mesh.h:73
Triangle get_triangle(const size_t i) const
Definition scene/mesh.h:67
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_)
Definition progress.h:259
bool get_cancel() const
Definition progress.h:77
void push(TaskRunFunction &&task)
Definition task.cpp:21
void wait_work(Summary *stats=nullptr)
Definition task.cpp:27
size_t size() const
size_t capacity() const
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 FLT_MAX
#define storage(slot, qualifiers)
#define index(i)
PrimitiveType
@ PRIMITIVE_ALL
@ PRIMITIVE_MOTION
@ PRIMITIVE_NUM
@ PRIMITIVE_CURVE
@ PRIMITIVE_ANY_POINT
@ PRIMITIVE_TRIANGLE
@ ATTR_STD_POSITION
@ ATTR_STD_RADIUS
OrientationBounds merge(const OrientationBounds &cone_a, const OrientationBounds &cone_b)
#define LOG_DEBUG
Definition log.h:107
CCL_NAMESPACE_BEGIN ccl_device_inline float3 zero_float3()
Definition math_float3.h:17
#define make_float2
#define make_float4
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
#define swap(a, b)
Definition sort.cc:61
#define min(a, b)
Definition sort.cc:38
string string_human_readable_number(size_t num)
Definition string.cpp:352
CCL_NAMESPACE_BEGIN string string_printf(const char *format,...)
Definition string.cpp:25
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
Definition hair.cpp:158
void bounds_grow(const int k, const packed_float3 *curve_keys, const float *curve_radius, BoundBox &bounds) const
Definition hair.cpp:44
int num_keys
Definition hair.h:20
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
Definition thread.h:28
CCL_NAMESPACE_BEGIN double time_dt()
Definition time.cpp:31