Blender V2.61 - r43446

bvh_build.cpp

Go to the documentation of this file.
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