Blender V2.61 - r43446
|
00001 /* 00002 * Adapted from code copyright 2009-2010 NVIDIA Corporation 00003 * Modifications Copyright 2011, Blender Foundation. 00004 * 00005 * Licensed under the Apache License, Version 2.0 (the "License"); 00006 * you may not use this file except in compliance with the License. 00007 * You may obtain a copy of the License at 00008 * 00009 * http://www.apache.org/licenses/LICENSE-2.0 00010 * 00011 * Unless required by applicable law or agreed to in writing, software 00012 * distributed under the License is distributed on an "AS IS" BASIS, 00013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 00014 * See the License for the specific language governing permissions and 00015 * limitations under the License. 00016 */ 00017 00018 #include "bvh_build.h" 00019 #include "bvh_node.h" 00020 #include "bvh_params.h" 00021 #include "bvh_sort.h" 00022 00023 #include "mesh.h" 00024 #include "object.h" 00025 #include "scene.h" 00026 00027 #include "util_algorithm.h" 00028 #include "util_foreach.h" 00029 #include "util_progress.h" 00030 #include "util_time.h" 00031 00032 CCL_NAMESPACE_BEGIN 00033 00034 /* Constructor / Destructor */ 00035 00036 BVHBuild::BVHBuild(const vector<Object*>& objects_, 00037 vector<int>& prim_index_, vector<int>& prim_object_, 00038 const BVHParams& params_, Progress& progress_) 00039 : objects(objects_), 00040 prim_index(prim_index_), 00041 prim_object(prim_object_), 00042 params(params_), 00043 progress(progress_), 00044 progress_start_time(0.0) 00045 { 00046 spatial_min_overlap = 0.0f; 00047 progress_num_duplicates = 0; 00048 } 00049 00050 BVHBuild::~BVHBuild() 00051 { 00052 } 00053 00054 /* Adding References */ 00055 00056 void BVHBuild::add_reference_mesh(NodeSpec& root, Mesh *mesh, int i) 00057 { 00058 for(uint j = 0; j < mesh->triangles.size(); j++) { 00059 Mesh::Triangle t = mesh->triangles[j]; 00060 Reference ref; 00061 00062 for(int k = 0; k < 3; k++) { 00063 float3 pt = mesh->verts[t.v[k]]; 00064 ref.bounds.grow(pt); 00065 } 00066 00067 if(ref.bounds.valid()) { 00068 ref.prim_index = j; 00069 ref.prim_object = i; 00070 00071 references.push_back(ref); 00072 root.bounds.grow(ref.bounds); 00073 } 00074 } 00075 } 00076 00077 void BVHBuild::add_reference_object(NodeSpec& root, Object *ob, int i) 00078 { 00079 Reference ref; 00080 00081 ref.prim_index = -1; 00082 ref.prim_object = i; 00083 ref.bounds = ob->bounds; 00084 00085 references.push_back(ref); 00086 root.bounds.grow(ref.bounds); 00087 } 00088 00089 void BVHBuild::add_references(NodeSpec& root) 00090 { 00091 /* init root spec */ 00092 root.num = 0; 00093 root.bounds = BoundBox(); 00094 00095 /* add objects */ 00096 int i = 0; 00097 00098 foreach(Object *ob, objects) { 00099 if(params.top_level) { 00100 if(ob->mesh->transform_applied) 00101 add_reference_mesh(root, ob->mesh, i); 00102 else 00103 add_reference_object(root, ob, i); 00104 } 00105 else 00106 add_reference_mesh(root, ob->mesh, i); 00107 00108 i++; 00109 00110 if(progress.get_cancel()) return; 00111 } 00112 00113 /* happens mostly on empty meshes */ 00114 if(!root.bounds.valid()) 00115 root.bounds.grow(make_float3(0.0f, 0.0f, 0.0f)); 00116 00117 root.num = references.size(); 00118 } 00119 00120 /* Build */ 00121 00122 BVHNode* BVHBuild::run() 00123 { 00124 NodeSpec root; 00125 00126 /* add references */ 00127 add_references(root); 00128 00129 if(progress.get_cancel()) return NULL; 00130 00131 /* init spatial splits */ 00132 if(params.top_level) /* todo: get rid of this */ 00133 params.use_spatial_split = false; 00134 00135 spatial_min_overlap = root.bounds.area() * params.spatial_split_alpha; 00136 spatial_right_bounds.clear(); 00137 spatial_right_bounds.resize(max(root.num, (int)BVHParams::NUM_SPATIAL_BINS) - 1); 00138 00139 /* init progress updates */ 00140 progress_num_duplicates = 0; 00141 progress_start_time = time_dt(); 00142 00143 /* build recursively */ 00144 return build_node(root, 0, 0.0f, 1.0f); 00145 } 00146 00147 void BVHBuild::progress_update(float progress_start, float progress_end) 00148 { 00149 if(time_dt() - progress_start_time < 0.25f) 00150 return; 00151 00152 float duplicates = (float)progress_num_duplicates/(float)references.size(); 00153 string msg = string_printf("Building BVH %.0f%%, duplicates %.0f%%", 00154 progress_start*100.0f, duplicates*100.0f); 00155 00156 progress.set_substatus(msg); 00157 progress_start_time = time_dt(); 00158 } 00159 00160 BVHNode* BVHBuild::build_node(const NodeSpec& spec, int level, float progress_start, float progress_end) 00161 { 00162 /* progress update */ 00163 progress_update(progress_start, progress_end); 00164 if(progress.get_cancel()) return NULL; 00165 00166 /* small enough or too deep => create leaf. */ 00167 if(spec.num <= params.min_leaf_size || level >= BVHParams::MAX_DEPTH) 00168 return create_leaf_node(spec); 00169 00170 /* find split candidates. */ 00171 float area = spec.bounds.area(); 00172 float leafSAH = area * params.triangle_cost(spec.num); 00173 float nodeSAH = area * params.node_cost(2); 00174 ObjectSplit object = find_object_split(spec, nodeSAH); 00175 SpatialSplit spatial; 00176 00177 if(params.use_spatial_split && level < BVHParams::MAX_SPATIAL_DEPTH) { 00178 BoundBox overlap = object.left_bounds; 00179 overlap.intersect(object.right_bounds); 00180 00181 if(overlap.area() >= spatial_min_overlap) 00182 spatial = find_spatial_split(spec, nodeSAH); 00183 } 00184 00185 /* leaf SAH is the lowest => create leaf. */ 00186 float minSAH = min(min(leafSAH, object.sah), spatial.sah); 00187 00188 if(minSAH == leafSAH && spec.num <= params.max_leaf_size) 00189 return create_leaf_node(spec); 00190 00191 /* perform split. */ 00192 NodeSpec left, right; 00193 00194 if(params.use_spatial_split && minSAH == spatial.sah) 00195 do_spatial_split(left, right, spec, spatial); 00196 if(!left.num || !right.num) 00197 do_object_split(left, right, spec, object); 00198 00199 /* create inner node. */ 00200 progress_num_duplicates += left.num + right.num - spec.num; 00201 00202 float progress_mid = lerp(progress_start, progress_end, (float)right.num / (float)(left.num + right.num)); 00203 00204 BVHNode* rightNode = build_node(right, level + 1, progress_start, progress_mid); 00205 if(progress.get_cancel()) { 00206 if(rightNode) rightNode->deleteSubtree(); 00207 return NULL; 00208 } 00209 00210 BVHNode* leftNode = build_node(left, level + 1, progress_mid, progress_end); 00211 if(progress.get_cancel()) { 00212 if(leftNode) leftNode->deleteSubtree(); 00213 return NULL; 00214 } 00215 00216 return new InnerNode(spec.bounds, leftNode, rightNode); 00217 } 00218 00219 BVHNode *BVHBuild::create_object_leaf_nodes(const Reference *ref, int num) 00220 { 00221 if(num == 0) { 00222 BoundBox bounds; 00223 return new LeafNode(bounds, 0, 0, 0); 00224 } 00225 else if(num == 1) { 00226 prim_index.push_back(ref[0].prim_index); 00227 prim_object.push_back(ref[0].prim_object); 00228 uint visibility = objects[ref[0].prim_object]->visibility; 00229 return new LeafNode(ref[0].bounds, visibility, prim_index.size()-1, prim_index.size()); 00230 } 00231 else { 00232 int mid = num/2; 00233 BVHNode *leaf0 = create_object_leaf_nodes(ref, mid); 00234 BVHNode *leaf1 = create_object_leaf_nodes(ref+mid, num-mid); 00235 00236 BoundBox bounds; 00237 bounds.grow(leaf0->m_bounds); 00238 bounds.grow(leaf1->m_bounds); 00239 00240 return new InnerNode(bounds, leaf0, leaf1); 00241 } 00242 } 00243 00244 BVHNode* BVHBuild::create_leaf_node(const NodeSpec& spec) 00245 { 00246 vector<int>& p_index = prim_index; 00247 vector<int>& p_object = prim_object; 00248 BoundBox bounds; 00249 int num = 0; 00250 uint visibility = 0; 00251 00252 for(int i = 0; i < spec.num; i++) { 00253 if(references.back().prim_index != -1) { 00254 p_index.push_back(references.back().prim_index); 00255 p_object.push_back(references.back().prim_object); 00256 bounds.grow(references.back().bounds); 00257 visibility |= objects[references.back().prim_object]->visibility; 00258 references.pop_back(); 00259 num++; 00260 } 00261 } 00262 00263 BVHNode *leaf = NULL; 00264 00265 if(num > 0) { 00266 leaf = new LeafNode(bounds, visibility, p_index.size() - num, p_index.size()); 00267 00268 if(num == spec.num) 00269 return leaf; 00270 } 00271 00272 /* while there may be multiple triangles in a leaf, for object primitives 00273 * we want them to be the only one, so we */ 00274 int ob_num = spec.num - num; 00275 const Reference *ref = (ob_num)? &references.back() - (ob_num - 1): NULL; 00276 BVHNode *oleaf = create_object_leaf_nodes(ref, ob_num); 00277 for(int i = 0; i < ob_num; i++) 00278 references.pop_back(); 00279 00280 if(leaf) 00281 return new InnerNode(spec.bounds, leaf, oleaf); 00282 else 00283 return oleaf; 00284 } 00285 00286 /* Object Split */ 00287 00288 BVHBuild::ObjectSplit BVHBuild::find_object_split(const NodeSpec& spec, float nodeSAH) 00289 { 00290 ObjectSplit split; 00291 const Reference *ref_ptr = &references[references.size() - spec.num]; 00292 00293 for(int dim = 0; dim < 3; dim++) { 00294 /* sort references */ 00295 bvh_reference_sort(references.size() - spec.num, references.size(), &references[0], dim); 00296 00297 /* sweep right to left and determine bounds. */ 00298 BoundBox right_bounds; 00299 00300 for(int i = spec.num - 1; i > 0; i--) { 00301 right_bounds.grow(ref_ptr[i].bounds); 00302 spatial_right_bounds[i - 1] = right_bounds; 00303 } 00304 00305 /* sweep left to right and select lowest SAH. */ 00306 BoundBox left_bounds; 00307 00308 for(int i = 1; i < spec.num; i++) { 00309 left_bounds.grow(ref_ptr[i - 1].bounds); 00310 right_bounds = spatial_right_bounds[i - 1]; 00311 00312 float sah = nodeSAH + 00313 left_bounds.area() * params.triangle_cost(i) + 00314 right_bounds.area() * params.triangle_cost(spec.num - i); 00315 00316 if(sah < split.sah) { 00317 split.sah = sah; 00318 split.dim = dim; 00319 split.num_left = i; 00320 split.left_bounds = left_bounds; 00321 split.right_bounds = right_bounds; 00322 } 00323 } 00324 } 00325 00326 return split; 00327 } 00328 00329 void BVHBuild::do_object_split(NodeSpec& left, NodeSpec& right, const NodeSpec& spec, const ObjectSplit& split) 00330 { 00331 /* sort references according to split */ 00332 int start = references.size() - spec.num; 00333 int end = references.size(); /* todo: is this right? */ 00334 00335 bvh_reference_sort(start, end, &references[0], split.dim); 00336 00337 /* split node specs */ 00338 left.num = split.num_left; 00339 left.bounds = split.left_bounds; 00340 right.num = spec.num - split.num_left; 00341 right.bounds = split.right_bounds; 00342 } 00343 00344 /* Spatial Split */ 00345 00346 BVHBuild::SpatialSplit BVHBuild::find_spatial_split(const NodeSpec& spec, float nodeSAH) 00347 { 00348 /* initialize bins. */ 00349 float3 origin = spec.bounds.min; 00350 float3 binSize = (spec.bounds.max - origin) * (1.0f / (float)BVHParams::NUM_SPATIAL_BINS); 00351 float3 invBinSize = 1.0f / binSize; 00352 00353 for(int dim = 0; dim < 3; dim++) { 00354 for(int i = 0; i < BVHParams::NUM_SPATIAL_BINS; i++) { 00355 SpatialBin& bin = spatial_bins[dim][i]; 00356 00357 bin.bounds = BoundBox(); 00358 bin.enter = 0; 00359 bin.exit = 0; 00360 } 00361 } 00362 00363 /* chop references into bins. */ 00364 for(unsigned int refIdx = references.size() - spec.num; refIdx < references.size(); refIdx++) { 00365 const Reference& ref = references[refIdx]; 00366 float3 firstBinf = (ref.bounds.min - origin) * invBinSize; 00367 float3 lastBinf = (ref.bounds.max - origin) * invBinSize; 00368 int3 firstBin = make_int3((int)firstBinf.x, (int)firstBinf.y, (int)firstBinf.z); 00369 int3 lastBin = make_int3((int)lastBinf.x, (int)lastBinf.y, (int)lastBinf.z); 00370 00371 firstBin = clamp(firstBin, 0, BVHParams::NUM_SPATIAL_BINS - 1); 00372 lastBin = clamp(lastBin, firstBin, BVHParams::NUM_SPATIAL_BINS - 1); 00373 00374 for(int dim = 0; dim < 3; dim++) { 00375 Reference currRef = ref; 00376 00377 for(int i = firstBin[dim]; i < lastBin[dim]; i++) { 00378 Reference leftRef, rightRef; 00379 00380 split_reference(leftRef, rightRef, currRef, dim, origin[dim] + binSize[dim] * (float)(i + 1)); 00381 spatial_bins[dim][i].bounds.grow(leftRef.bounds); 00382 currRef = rightRef; 00383 } 00384 00385 spatial_bins[dim][lastBin[dim]].bounds.grow(currRef.bounds); 00386 spatial_bins[dim][firstBin[dim]].enter++; 00387 spatial_bins[dim][lastBin[dim]].exit++; 00388 } 00389 } 00390 00391 /* select best split plane. */ 00392 SpatialSplit split; 00393 00394 for(int dim = 0; dim < 3; dim++) { 00395 /* sweep right to left and determine bounds. */ 00396 BoundBox right_bounds; 00397 00398 for(int i = BVHParams::NUM_SPATIAL_BINS - 1; i > 0; i--) { 00399 right_bounds.grow(spatial_bins[dim][i].bounds); 00400 spatial_right_bounds[i - 1] = right_bounds; 00401 } 00402 00403 /* sweep left to right and select lowest SAH. */ 00404 BoundBox left_bounds; 00405 int leftNum = 0; 00406 int rightNum = spec.num; 00407 00408 for(int i = 1; i < BVHParams::NUM_SPATIAL_BINS; i++) { 00409 left_bounds.grow(spatial_bins[dim][i - 1].bounds); 00410 leftNum += spatial_bins[dim][i - 1].enter; 00411 rightNum -= spatial_bins[dim][i - 1].exit; 00412 00413 float sah = nodeSAH + 00414 left_bounds.area() * params.triangle_cost(leftNum) + 00415 spatial_right_bounds[i - 1].area() * params.triangle_cost(rightNum); 00416 00417 if(sah < split.sah) { 00418 split.sah = sah; 00419 split.dim = dim; 00420 split.pos = origin[dim] + binSize[dim] * (float)i; 00421 } 00422 } 00423 } 00424 00425 return split; 00426 } 00427 00428 void BVHBuild::do_spatial_split(NodeSpec& left, NodeSpec& right, const NodeSpec& spec, const SpatialSplit& split) 00429 { 00430 /* Categorize references and compute bounds. 00431 * 00432 * Left-hand side: [left_start, left_end[ 00433 * Uncategorized/split: [left_end, right_start[ 00434 * Right-hand side: [right_start, refs.size()[ */ 00435 00436 vector<Reference>& refs = references; 00437 int left_start = refs.size() - spec.num; 00438 int left_end = left_start; 00439 int right_start = refs.size(); 00440 00441 left.bounds = right.bounds = BoundBox(); 00442 00443 for(int i = left_end; i < right_start; i++) { 00444 if(refs[i].bounds.max[split.dim] <= split.pos) { 00445 /* entirely on the left-hand side */ 00446 left.bounds.grow(refs[i].bounds); 00447 swap(refs[i], refs[left_end++]); 00448 } 00449 else if(refs[i].bounds.min[split.dim] >= split.pos) { 00450 /* entirely on the right-hand side */ 00451 right.bounds.grow(refs[i].bounds); 00452 swap(refs[i--], refs[--right_start]); 00453 } 00454 } 00455 00456 /* duplicate or unsplit references intersecting both sides. */ 00457 while(left_end < right_start) { 00458 /* split reference. */ 00459 Reference lref, rref; 00460 00461 split_reference(lref, rref, refs[left_end], split.dim, split.pos); 00462 00463 /* compute SAH for duplicate/unsplit candidates. */ 00464 BoundBox lub = left.bounds; // Unsplit to left: new left-hand bounds. 00465 BoundBox rub = right.bounds; // Unsplit to right: new right-hand bounds. 00466 BoundBox ldb = left.bounds; // Duplicate: new left-hand bounds. 00467 BoundBox rdb = right.bounds; // Duplicate: new right-hand bounds. 00468 00469 lub.grow(refs[left_end].bounds); 00470 rub.grow(refs[left_end].bounds); 00471 ldb.grow(lref.bounds); 00472 rdb.grow(rref.bounds); 00473 00474 float lac = params.triangle_cost(left_end - left_start); 00475 float rac = params.triangle_cost(refs.size() - right_start); 00476 float lbc = params.triangle_cost(left_end - left_start + 1); 00477 float rbc = params.triangle_cost(refs.size() - right_start + 1); 00478 00479 float unsplitLeftSAH = lub.area() * lbc + right.bounds.area() * rac; 00480 float unsplitRightSAH = left.bounds.area() * lac + rub.area() * rbc; 00481 float duplicateSAH = ldb.area() * lbc + rdb.area() * rbc; 00482 float minSAH = min(min(unsplitLeftSAH, unsplitRightSAH), duplicateSAH); 00483 00484 if(minSAH == unsplitLeftSAH) { 00485 /* unsplit to left */ 00486 left.bounds = lub; 00487 left_end++; 00488 } 00489 else if(minSAH == unsplitRightSAH) { 00490 /* unsplit to right */ 00491 right.bounds = rub; 00492 swap(refs[left_end], refs[--right_start]); 00493 } 00494 else { 00495 /* duplicate */ 00496 left.bounds = ldb; 00497 right.bounds = rdb; 00498 refs[left_end++] = lref; 00499 refs.push_back(rref); 00500 } 00501 } 00502 00503 left.num = left_end - left_start; 00504 right.num = refs.size() - right_start; 00505 } 00506 00507 void BVHBuild::split_reference(Reference& left, Reference& right, const Reference& ref, int dim, float pos) 00508 { 00509 /* initialize references. */ 00510 left.prim_index = right.prim_index = ref.prim_index; 00511 left.prim_object = right.prim_object = ref.prim_object; 00512 left.bounds = right.bounds = BoundBox(); 00513 00514 /* loop over vertices/edges. */ 00515 Object *ob = objects[ref.prim_object]; 00516 const Mesh *mesh = ob->mesh; 00517 const int *inds = mesh->triangles[ref.prim_index].v; 00518 const float3 *verts = &mesh->verts[0]; 00519 const float3* v1 = &verts[inds[2]]; 00520 00521 for(int i = 0; i < 3; i++) { 00522 const float3* v0 = v1; 00523 int vindex = inds[i]; 00524 v1 = &verts[vindex]; 00525 float v0p = (*v0)[dim]; 00526 float v1p = (*v1)[dim]; 00527 00528 /* insert vertex to the boxes it belongs to. */ 00529 if(v0p <= pos) 00530 left.bounds.grow(*v0); 00531 00532 if(v0p >= pos) 00533 right.bounds.grow(*v0); 00534 00535 /* edge intersects the plane => insert intersection to both boxes. */ 00536 if((v0p < pos && v1p > pos) || (v0p > pos && v1p < pos)) { 00537 float3 t = lerp(*v0, *v1, clamp((pos - v0p) / (v1p - v0p), 0.0f, 1.0f)); 00538 left.bounds.grow(t); 00539 right.bounds.grow(t); 00540 } 00541 } 00542 00543 /* intersect with original bounds. */ 00544 left.bounds.max[dim] = pos; 00545 right.bounds.min[dim] = pos; 00546 left.bounds.intersect(ref.bounds); 00547 right.bounds.intersect(ref.bounds); 00548 } 00549 00550 CCL_NAMESPACE_END 00551