intern/cycles/bvh/bvh_build.cpp

   1 /*
   2  * Adapted from code copyright 2009-2010 NVIDIA Corporation
   3  * Modifications Copyright 2011, Blender Foundation.
   4  *
   5  * Licensed under the Apache License, Version 2.0 (the "License");
   6  * you may not use this file except in compliance with the License.
   7  * You may obtain a copy of the License at
   8  *
   9  * http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  */
  17
  18 #include "bvh_build.h"
  19 #include "bvh_node.h"
  20 #include "bvh_params.h"
  21 #include "bvh_sort.h"
  22
  23 #include "mesh.h"
  24 #include "object.h"
  25 #include "scene.h"
  26
  27 #include "util_algorithm.h"
  28 #include "util_foreach.h"
  29 #include "util_progress.h"
  30 #include "util_time.h"
  31
  32 CCL_NAMESPACE_BEGIN
  33
  34 /* Constructor / Destructor */
  35
  36 BVHBuild::BVHBuild(const vector<Object*>& objects_,
  37         vector<int>& prim_index_, vector<int>& prim_object_,
  38         const BVHParams& params_, Progress& progress_)
  39 : objects(objects_),
  40   prim_index(prim_index_),
  41   prim_object(prim_object_),
  42   params(params_),
  43   progress(progress_),
  44   progress_start_time(0.0)
  45 {
  46         spatial_min_overlap = 0.0f;
  47         progress_num_duplicates = 0;
  48 }
  49
  50 BVHBuild::~BVHBuild()
  51 {
  52 }
  53
  54 /* Adding References */
  55
  56 void BVHBuild::add_reference_mesh(NodeSpec& root, Mesh *mesh, int i)
  57 {
  58         for(uint j = 0; j < mesh->triangles.size(); j++) {
  59                 Mesh::Triangle t = mesh->triangles[j];
  60                 Reference ref;
  61
  62                 ref.prim_index = j;
  63                 ref.prim_object = i;
  64
  65                 for(int k = 0; k < 3; k++) {
  66                         float3 pt = mesh->verts[t.v[k]];
  67                         ref.bounds.grow(pt);
  68                 }
  69
  70                 references.push_back(ref);
  71                 root.bounds.grow(ref.bounds);
  72         }
  73 }
  74
  75 void BVHBuild::add_reference_object(NodeSpec& root, Object *ob, int i)
  76 {
  77         Reference ref;
  78
  79         ref.prim_index = -1;
  80         ref.prim_object = i;
  81         ref.bounds = ob->bounds;
  82
  83         references.push_back(ref);
  84         root.bounds.grow(ref.bounds);
  85 }
  86
  87 void BVHBuild::add_references(NodeSpec& root)
  88 {
  89         /* init root spec */
  90         root.num = 0;
  91         root.bounds = BoundBox();
  92
  93         /* add objects */
  94         int i = 0;
  95
  96         foreach(Object *ob, objects) {
  97                 if(params.top_level) {
  98                         if(ob->mesh->transform_applied)
  99                                 add_reference_mesh(root, ob->mesh, i);
 100                         else
 101                                 add_reference_object(root, ob, i);
 102                 }
 103                 else
 104                         add_reference_mesh(root, ob->mesh, i);
 105
 106                 i++;
 107
 108                 if(progress.get_cancel()) return;
 109         }
 110
 111         /* happens mostly on empty meshes */
 112         if(!root.bounds.valid())
 113                 root.bounds.grow(make_float3(0.0f, 0.0f, 0.0f));
 114
 115         root.num = references.size();
 116 }
 117
 118 /* Build */
 119
 120 BVHNode* BVHBuild::run()
 121 {
 122         NodeSpec root;
 123
 124         /* add references */
 125         add_references(root);
 126
 127         if(progress.get_cancel()) return NULL;
 128
 129         /* init spatial splits */
 130         if(params.top_level) /* todo: get rid of this */
 131                 params.use_spatial_split = false;
 132
 133         spatial_min_overlap = root.bounds.area() * params.spatial_split_alpha;
 134         spatial_right_bounds.clear();
 135         spatial_right_bounds.resize(max(root.num, (int)BVHParams::NUM_SPATIAL_BINS) - 1);
 136
 137         /* init progress updates */
 138         progress_num_duplicates = 0;
 139         progress_start_time = time_dt();
 140
 141         /* build recursively */
 142         return build_node(root, 0, 0.0f, 1.0f);
 143 }
 144
 145 void BVHBuild::progress_update(float progress_start, float progress_end)
 146 {
 147         if(time_dt() - progress_start_time < 0.25f)
 148                 return;
 149
 150         float duplicates = (float)progress_num_duplicates/(float)references.size();
 151         string msg = string_printf("Building BVH %.0f%%, duplicates %.0f%%",
 152                 progress_start*100.0f, duplicates*100.0f);
 153
 154         progress.set_substatus(msg);
 155         progress_start_time = time_dt();
 156 }
 157
 158 BVHNode* BVHBuild::build_node(const NodeSpec& spec, int level, float progress_start, float progress_end)
 159 {
 160         /* progress update */
 161         progress_update(progress_start, progress_end);
 162         if(progress.get_cancel()) return NULL;
 163
 164         /* small enough or too deep => create leaf. */
 165         if(spec.num <= params.min_leaf_size || level >= BVHParams::MAX_DEPTH)
 166                 return create_leaf_node(spec);
 167
 168         /* find split candidates. */
 169         float area = spec.bounds.area();
 170         float leafSAH = area * params.triangle_cost(spec.num);
 171         float nodeSAH = area * params.node_cost(2);
 172         ObjectSplit object = find_object_split(spec, nodeSAH);
 173         SpatialSplit spatial;
 174
 175         if(params.use_spatial_split && level < BVHParams::MAX_SPATIAL_DEPTH) {
 176                 BoundBox overlap = object.left_bounds;
 177                 overlap.intersect(object.right_bounds);
 178
 179                 if(overlap.area() >= spatial_min_overlap)
 180                         spatial = find_spatial_split(spec, nodeSAH);
 181         }
 182
 183         /* leaf SAH is the lowest => create leaf. */
 184         float minSAH = min(min(leafSAH, object.sah), spatial.sah);
 185
 186         if(minSAH == leafSAH && spec.num <= params.max_leaf_size)
 187                 return create_leaf_node(spec);
 188
 189         /* perform split. */
 190         NodeSpec left, right;
 191
 192         if(params.use_spatial_split && minSAH == spatial.sah)
 193                 do_spatial_split(left, right, spec, spatial);
 194         if(!left.num || !right.num)
 195                 do_object_split(left, right, spec, object);
 196
 197         /* create inner node. */
 198         progress_num_duplicates += left.num + right.num - spec.num;
 199
 200         float progress_mid = lerp(progress_start, progress_end, (float)right.num / (float)(left.num + right.num));
 201
 202         BVHNode* rightNode = build_node(right, level + 1, progress_start, progress_mid);
 203         if(progress.get_cancel()) {
 204                 if(rightNode) rightNode->deleteSubtree();
 205                 return NULL;
 206         }
 207
 208         BVHNode* leftNode = build_node(left, level + 1, progress_mid, progress_end);
 209         if(progress.get_cancel()) {
 210                 if(leftNode) leftNode->deleteSubtree();
 211                 return NULL;
 212         }
 213
 214         return new InnerNode(spec.bounds, leftNode, rightNode);
 215 }
 216
 217 BVHNode *BVHBuild::create_object_leaf_nodes(const Reference *ref, int num)
 218 {
 219         if(num == 0) {
 220                 BoundBox bounds;
 221                 return new LeafNode(bounds, 0, 0, 0);
 222         }
 223         else if(num == 1) {
 224                 prim_index.push_back(ref[0].prim_index);
 225                 prim_object.push_back(ref[0].prim_object);
 226                 uint visibility = objects[ref[0].prim_object]->visibility;
 227                 return new LeafNode(ref[0].bounds, visibility, prim_index.size()-1, prim_index.size());
 228         }
 229         else {
 230                 int mid = num/2;
 231                 BVHNode *leaf0 = create_object_leaf_nodes(ref, mid);
 232                 BVHNode *leaf1 = create_object_leaf_nodes(ref+mid, num-mid);
 233
 234                 BoundBox bounds;
 235                 bounds.grow(leaf0->m_bounds);
 236                 bounds.grow(leaf1->m_bounds);
 237
 238                 return new InnerNode(bounds, leaf0, leaf1);
 239         }
 240 }
 241
 242 BVHNode* BVHBuild::create_leaf_node(const NodeSpec& spec)
 243 {
 244         vector<int>& p_index = prim_index;
 245         vector<int>& p_object = prim_object;
 246         BoundBox bounds;
 247         int num = 0;
 248         uint visibility = 0;
 249
 250         for(int i = 0; i < spec.num; i++) {
 251                 if(references.back().prim_index != -1) {
 252                         p_index.push_back(references.back().prim_index);
 253                         p_object.push_back(references.back().prim_object);
 254                         bounds.grow(references.back().bounds);
 255                         visibility |= objects[references.back().prim_object]->visibility;
 256                         references.pop_back();
 257                         num++;
 258                 }
 259         }
 260
 261         BVHNode *leaf = NULL;
 262
 263         if(num > 0) {
 264                 leaf = new LeafNode(bounds, visibility, p_index.size() - num, p_index.size());
 265
 266                 if(num == spec.num)
 267                         return leaf;
 268         }
 269
 270         /* while there may be multiple triangles in a leaf, for object primitives
 271          * we want them to be the only one, so we  */
 272         int ob_num = spec.num - num;
 273         const Reference *ref = (ob_num)? &references.back() - (ob_num - 1): NULL;
 274         BVHNode *oleaf = create_object_leaf_nodes(ref, ob_num);
 275         for(int i = 0; i < ob_num; i++)
 276                 references.pop_back();
 277
 278         if(leaf)
 279                 return new InnerNode(spec.bounds, leaf, oleaf);
 280         else
 281                 return oleaf;
 282 }
 283
 284 /* Object Split */
 285
 286 BVHBuild::ObjectSplit BVHBuild::find_object_split(const NodeSpec& spec, float nodeSAH)
 287 {
 288         ObjectSplit split;
 289         const Reference *ref_ptr = &references[references.size() - spec.num];
 290
 291         for(int dim = 0; dim < 3; dim++) {
 292                 /* sort references */
 293                 bvh_reference_sort(references.size() - spec.num, references.size(), &references[0], dim);
 294
 295                 /* sweep right to left and determine bounds. */
 296                 BoundBox right_bounds;
 297
 298                 for(int i = spec.num - 1; i > 0; i--) {
 299                         right_bounds.grow(ref_ptr[i].bounds);
 300                         spatial_right_bounds[i - 1] = right_bounds;
 301                 }
 302
 303                 /* sweep left to right and select lowest SAH. */
 304                 BoundBox left_bounds;
 305
 306                 for(int i = 1; i < spec.num; i++) {
 307                         left_bounds.grow(ref_ptr[i - 1].bounds);
 308                         right_bounds = spatial_right_bounds[i - 1];
 309
 310                         float sah = nodeSAH +
 311                                 left_bounds.area() * params.triangle_cost(i) +
 312                                 right_bounds.area() * params.triangle_cost(spec.num - i);
 313
 314                         if(sah < split.sah) {
 315                                 split.sah = sah;
 316                                 split.dim = dim;
 317                                 split.num_left = i;
 318                                 split.left_bounds = left_bounds;
 319                                 split.right_bounds = right_bounds;
 320                         }
 321                 }
 322         }
 323
 324         return split;
 325 }
 326
 327 void BVHBuild::do_object_split(NodeSpec& left, NodeSpec& right, const NodeSpec& spec, const ObjectSplit& split)
 328 {
 329         /* sort references according to split */
 330         int start = references.size() - spec.num;
 331         int end = references.size(); /* todo: is this right? */
 332
 333         bvh_reference_sort(start, end, &references[0], split.dim);
 334
 335         /* split node specs */
 336         left.num = split.num_left;
 337         left.bounds = split.left_bounds;
 338         right.num = spec.num - split.num_left;
 339         right.bounds = split.right_bounds;
 340 }
 341
 342 /* Spatial Split */
 343
 344 BVHBuild::SpatialSplit BVHBuild::find_spatial_split(const NodeSpec& spec, float nodeSAH)
 345 {
 346         /* initialize bins. */
 347         float3 origin = spec.bounds.min;
 348         float3 binSize = (spec.bounds.max - origin) * (1.0f / (float)BVHParams::NUM_SPATIAL_BINS);
 349         float3 invBinSize = 1.0f / binSize;
 350
 351         for(int dim = 0; dim < 3; dim++) {
 352                 for(int i = 0; i < BVHParams::NUM_SPATIAL_BINS; i++) {
 353                         SpatialBin& bin = spatial_bins[dim][i];
 354
 355                         bin.bounds = BoundBox();
 356                         bin.enter = 0;
 357                         bin.exit = 0;
 358                 }
 359         }
 360
 361         /* chop references into bins. */
 362         for(unsigned int refIdx = references.size() - spec.num; refIdx < references.size(); refIdx++) {
 363                 const Reference& ref = references[refIdx];
 364                 float3 firstBinf = (ref.bounds.min - origin) * invBinSize;
 365                 float3 lastBinf = (ref.bounds.max - origin) * invBinSize;
 366                 int3 firstBin = make_int3((int)firstBinf.x, (int)firstBinf.y, (int)firstBinf.z);
 367                 int3 lastBin = make_int3((int)lastBinf.x, (int)lastBinf.y, (int)lastBinf.z);
 368
 369                 firstBin = clamp(firstBin, 0, BVHParams::NUM_SPATIAL_BINS - 1);
 370                 lastBin = clamp(lastBin, firstBin, BVHParams::NUM_SPATIAL_BINS - 1);
 371
 372                 for(int dim = 0; dim < 3; dim++) {
 373                         Reference currRef = ref;
 374
 375                         for(int i = firstBin[dim]; i < lastBin[dim]; i++) {
 376                                 Reference leftRef, rightRef;
 377
 378                                 split_reference(leftRef, rightRef, currRef, dim, origin[dim] + binSize[dim] * (float)(i + 1));
 379                                 spatial_bins[dim][i].bounds.grow(leftRef.bounds);
 380                                 currRef = rightRef;
 381                         }
 382
 383                         spatial_bins[dim][lastBin[dim]].bounds.grow(currRef.bounds);
 384                         spatial_bins[dim][firstBin[dim]].enter++;
 385                         spatial_bins[dim][lastBin[dim]].exit++;
 386                 }
 387         }
 388
 389         /* select best split plane. */
 390         SpatialSplit split;
 391
 392         for(int dim = 0; dim < 3; dim++) {
 393                 /* sweep right to left and determine bounds. */
 394                 BoundBox right_bounds;
 395
 396                 for(int i = BVHParams::NUM_SPATIAL_BINS - 1; i > 0; i--) {
 397                         right_bounds.grow(spatial_bins[dim][i].bounds);
 398                         spatial_right_bounds[i - 1] = right_bounds;
 399                 }
 400
 401                 /* sweep left to right and select lowest SAH. */
 402                 BoundBox left_bounds;
 403                 int leftNum = 0;
 404                 int rightNum = spec.num;
 405
 406                 for(int i = 1; i < BVHParams::NUM_SPATIAL_BINS; i++) {
 407                         left_bounds.grow(spatial_bins[dim][i - 1].bounds);
 408                         leftNum += spatial_bins[dim][i - 1].enter;
 409                         rightNum -= spatial_bins[dim][i - 1].exit;
 410
 411                         float sah = nodeSAH +
 412                                 left_bounds.area() * params.triangle_cost(leftNum) +
 413                                 spatial_right_bounds[i - 1].area() * params.triangle_cost(rightNum);
 414
 415                         if(sah < split.sah) {
 416                                 split.sah = sah;
 417                                 split.dim = dim;
 418                                 split.pos = origin[dim] + binSize[dim] * (float)i;
 419                         }
 420                 }
 421         }
 422
 423         return split;
 424 }
 425
 426 void BVHBuild::do_spatial_split(NodeSpec& left, NodeSpec& right, const NodeSpec& spec, const SpatialSplit& split)
 427 {
 428         /* Categorize references and compute bounds.
 429          *
 430          * Left-hand side:                      [left_start, left_end[
 431          * Uncategorized/split:         [left_end, right_start[
 432          * Right-hand side:                     [right_start, refs.size()[ */
 433
 434         vector<Reference>& refs = references;
 435         int left_start = refs.size() - spec.num;
 436         int left_end = left_start;
 437         int right_start = refs.size();
 438
 439         left.bounds = right.bounds = BoundBox();
 440
 441         for(int i = left_end; i < right_start; i++) {
 442                 if(refs[i].bounds.max[split.dim] <= split.pos) {
 443                         /* entirely on the left-hand side */
 444                         left.bounds.grow(refs[i].bounds);
 445                         swap(refs[i], refs[left_end++]);
 446                 }
 447                 else if(refs[i].bounds.min[split.dim] >= split.pos) {
 448                         /* entirely on the right-hand side */
 449                         right.bounds.grow(refs[i].bounds);
 450                         swap(refs[i--], refs[--right_start]);
 451                 }
 452         }
 453
 454         /* duplicate or unsplit references intersecting both sides. */
 455         while(left_end < right_start) {
 456                 /* split reference. */
 457                 Reference lref, rref;
 458
 459                 split_reference(lref, rref, refs[left_end], split.dim, split.pos);
 460
 461                 /* compute SAH for duplicate/unsplit candidates. */
 462                 BoundBox lub = left.bounds;             // Unsplit to left:             new left-hand bounds.
 463                 BoundBox rub = right.bounds;    // Unsplit to right:    new right-hand bounds.
 464                 BoundBox ldb = left.bounds;             // Duplicate:                   new left-hand bounds.
 465                 BoundBox rdb = right.bounds;    // Duplicate:                   new right-hand bounds.
 466
 467                 lub.grow(refs[left_end].bounds);
 468                 rub.grow(refs[left_end].bounds);
 469                 ldb.grow(lref.bounds);
 470                 rdb.grow(rref.bounds);
 471
 472                 float lac = params.triangle_cost(left_end - left_start);
 473                 float rac = params.triangle_cost(refs.size() - right_start);
 474                 float lbc = params.triangle_cost(left_end - left_start + 1);
 475                 float rbc = params.triangle_cost(refs.size() - right_start + 1);
 476
 477                 float unsplitLeftSAH = lub.area() * lbc + right.bounds.area() * rac;
 478                 float unsplitRightSAH = left.bounds.area() * lac + rub.area() * rbc;
 479                 float duplicateSAH = ldb.area() * lbc + rdb.area() * rbc;
 480                 float minSAH = min(min(unsplitLeftSAH, unsplitRightSAH), duplicateSAH);
 481
 482                 if(minSAH == unsplitLeftSAH) {
 483                         /* unsplit to left */
 484                         left.bounds = lub;
 485                         left_end++;
 486                 }
 487                 else if(minSAH == unsplitRightSAH) {
 488                         /* unsplit to right */
 489                         right.bounds = rub;
 490                         swap(refs[left_end], refs[--right_start]);
 491                 }
 492                 else {
 493                         /* duplicate */
 494                         left.bounds = ldb;
 495                         right.bounds = rdb;
 496                         refs[left_end++] = lref;
 497                         refs.push_back(rref);
 498                 }
 499         }
 500
 501         left.num = left_end - left_start;
 502         right.num = refs.size() - right_start;
 503 }
 504
 505 void BVHBuild::split_reference(Reference& left, Reference& right, const Reference& ref, int dim, float pos)
 506 {
 507         /* initialize references. */
 508         left.prim_index = right.prim_index = ref.prim_index;
 509         left.prim_object = right.prim_object = ref.prim_object;
 510         left.bounds = right.bounds = BoundBox();
 511
 512         /* loop over vertices/edges. */
 513         Object *ob = objects[ref.prim_object];
 514         const Mesh *mesh = ob->mesh;
 515         const int *inds = mesh->triangles[ref.prim_index].v;
 516         const float3 *verts = &mesh->verts[0];
 517         const float3* v1 = &verts[inds[2]];
 518
 519         for(int i = 0; i < 3; i++) {
 520                 const float3* v0 = v1;
 521                 int vindex = inds[i];
 522                 v1 = &verts[vindex];
 523                 float v0p = (*v0)[dim];
 524                 float v1p = (*v1)[dim];
 525
 526                 /* insert vertex to the boxes it belongs to. */
 527                 if(v0p <= pos)
 528                         left.bounds.grow(*v0);
 529
 530                 if(v0p >= pos)
 531                         right.bounds.grow(*v0);
 532
 533                 /* edge intersects the plane => insert intersection to both boxes. */
 534                 if((v0p < pos && v1p > pos) || (v0p > pos && v1p < pos)) {
 535                         float3 t = lerp(*v0, *v1, clamp((pos - v0p) / (v1p - v0p), 0.0f, 1.0f));
 536                         left.bounds.grow(t);
 537                         right.bounds.grow(t);
 538                 }
 539         }
 540
 541         /* intersect with original bounds. */
 542         left.bounds.max[dim] = pos;
 543         right.bounds.min[dim] = pos;
 544         left.bounds.intersect(ref.bounds);
 545         right.bounds.intersect(ref.bounds);
 546 }
 547
 548 CCL_NAMESPACE_END
 549