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