Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/intern/cycles/bvh/bvh_split.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'intern/cycles/bvh/bvh_split.cpp')
-rw-r--r--intern/cycles/bvh/bvh_split.cpp293
1 files changed, 0 insertions, 293 deletions
diff --git a/intern/cycles/bvh/bvh_split.cpp b/intern/cycles/bvh/bvh_split.cpp
deleted file mode 100644
index 263c5834428..00000000000
--- a/intern/cycles/bvh/bvh_split.cpp
+++ /dev/null
@@ -1,293 +0,0 @@
-/*
- * Adapted from code copyright 2009-2010 NVIDIA Corporation
- * Modifications Copyright 2011, Blender Foundation.
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#include "bvh_build.h"
-#include "bvh_split.h"
-#include "bvh_sort.h"
-
-#include "mesh.h"
-#include "object.h"
-
-#include "util_algorithm.h"
-
-CCL_NAMESPACE_BEGIN
-
-/* Object Split */
-
-BVHObjectSplit::BVHObjectSplit(BVHBuild *builder, const BVHRange& range, float nodeSAH)
-: sah(FLT_MAX), dim(0), num_left(0), left_bounds(BoundBox::empty), right_bounds(BoundBox::empty)
-{
- const BVHReference *ref_ptr = &builder->references[range.start()];
- float min_sah = FLT_MAX;
-
- for(int dim = 0; dim < 3; dim++) {
- /* sort references */
- bvh_reference_sort(range.start(), range.end(), &builder->references[0], dim);
-
- /* sweep right to left and determine bounds. */
- BoundBox right_bounds = BoundBox::empty;
-
- for(int i = range.size() - 1; i > 0; i--) {
- right_bounds.grow(ref_ptr[i].bounds());
- builder->spatial_right_bounds[i - 1] = right_bounds;
- }
-
- /* sweep left to right and select lowest SAH. */
- BoundBox left_bounds = BoundBox::empty;
-
- for(int i = 1; i < range.size(); i++) {
- left_bounds.grow(ref_ptr[i - 1].bounds());
- right_bounds = builder->spatial_right_bounds[i - 1];
-
- float sah = nodeSAH +
- left_bounds.safe_area() * builder->params.triangle_cost(i) +
- right_bounds.safe_area() * builder->params.triangle_cost(range.size() - i);
-
- if(sah < min_sah) {
- min_sah = sah;
-
- this->sah = sah;
- this->dim = dim;
- this->num_left = i;
- this->left_bounds = left_bounds;
- this->right_bounds = right_bounds;
- }
- }
- }
-}
-
-void BVHObjectSplit::split(BVHBuild *builder, BVHRange& left, BVHRange& right, const BVHRange& range)
-{
- /* sort references according to split */
- bvh_reference_sort(range.start(), range.end(), &builder->references[0], this->dim);
-
- /* split node ranges */
- left = BVHRange(this->left_bounds, range.start(), this->num_left);
- right = BVHRange(this->right_bounds, left.end(), range.size() - this->num_left);
-
-}
-
-/* Spatial Split */
-
-BVHSpatialSplit::BVHSpatialSplit(BVHBuild *builder, const BVHRange& range, float nodeSAH)
-: sah(FLT_MAX), dim(0), pos(0.0f)
-{
- /* initialize bins. */
- float3 origin = range.bounds().min;
- float3 binSize = (range.bounds().max - origin) * (1.0f / (float)BVHParams::NUM_SPATIAL_BINS);
- float3 invBinSize = 1.0f / binSize;
-
- for(int dim = 0; dim < 3; dim++) {
- for(int i = 0; i < BVHParams::NUM_SPATIAL_BINS; i++) {
- BVHSpatialBin& bin = builder->spatial_bins[dim][i];
-
- bin.bounds = BoundBox::empty;
- bin.enter = 0;
- bin.exit = 0;
- }
- }
-
- /* chop references into bins. */
- for(unsigned int refIdx = range.start(); refIdx < range.end(); refIdx++) {
- const BVHReference& ref = builder->references[refIdx];
- float3 firstBinf = (ref.bounds().min - origin) * invBinSize;
- float3 lastBinf = (ref.bounds().max - origin) * invBinSize;
- int3 firstBin = make_int3((int)firstBinf.x, (int)firstBinf.y, (int)firstBinf.z);
- int3 lastBin = make_int3((int)lastBinf.x, (int)lastBinf.y, (int)lastBinf.z);
-
- firstBin = clamp(firstBin, 0, BVHParams::NUM_SPATIAL_BINS - 1);
- lastBin = clamp(lastBin, firstBin, BVHParams::NUM_SPATIAL_BINS - 1);
-
- for(int dim = 0; dim < 3; dim++) {
- BVHReference currRef = ref;
-
- for(int i = firstBin[dim]; i < lastBin[dim]; i++) {
- BVHReference leftRef, rightRef;
-
- split_reference(builder, leftRef, rightRef, currRef, dim, origin[dim] + binSize[dim] * (float)(i + 1));
- builder->spatial_bins[dim][i].bounds.grow(leftRef.bounds());
- currRef = rightRef;
- }
-
- builder->spatial_bins[dim][lastBin[dim]].bounds.grow(currRef.bounds());
- builder->spatial_bins[dim][firstBin[dim]].enter++;
- builder->spatial_bins[dim][lastBin[dim]].exit++;
- }
- }
-
- /* select best split plane. */
- for(int dim = 0; dim < 3; dim++) {
- /* sweep right to left and determine bounds. */
- BoundBox right_bounds = BoundBox::empty;
-
- for(int i = BVHParams::NUM_SPATIAL_BINS - 1; i > 0; i--) {
- right_bounds.grow(builder->spatial_bins[dim][i].bounds);
- builder->spatial_right_bounds[i - 1] = right_bounds;
- }
-
- /* sweep left to right and select lowest SAH. */
- BoundBox left_bounds = BoundBox::empty;
- int leftNum = 0;
- int rightNum = range.size();
-
- for(int i = 1; i < BVHParams::NUM_SPATIAL_BINS; i++) {
- left_bounds.grow(builder->spatial_bins[dim][i - 1].bounds);
- leftNum += builder->spatial_bins[dim][i - 1].enter;
- rightNum -= builder->spatial_bins[dim][i - 1].exit;
-
- float sah = nodeSAH +
- left_bounds.safe_area() * builder->params.triangle_cost(leftNum) +
- builder->spatial_right_bounds[i - 1].safe_area() * builder->params.triangle_cost(rightNum);
-
- if(sah < this->sah) {
- this->sah = sah;
- this->dim = dim;
- this->pos = origin[dim] + binSize[dim] * (float)i;
- }
- }
- }
-}
-
-void BVHSpatialSplit::split(BVHBuild *builder, BVHRange& left, BVHRange& right, const BVHRange& range)
-{
- /* Categorize references and compute bounds.
- *
- * Left-hand side: [left_start, left_end[
- * Uncategorized/split: [left_end, right_start[
- * Right-hand side: [right_start, refs.size()[ */
-
- vector<BVHReference>& refs = builder->references;
- int left_start = range.start();
- int left_end = left_start;
- int right_start = range.end();
- int right_end = range.end();
- BoundBox left_bounds = BoundBox::empty;
- BoundBox right_bounds = BoundBox::empty;
-
- for(int i = left_end; i < right_start; i++) {
- if(refs[i].bounds().max[this->dim] <= this->pos) {
- /* entirely on the left-hand side */
- left_bounds.grow(refs[i].bounds());
- swap(refs[i], refs[left_end++]);
- }
- else if(refs[i].bounds().min[this->dim] >= this->pos) {
- /* entirely on the right-hand side */
- right_bounds.grow(refs[i].bounds());
- swap(refs[i--], refs[--right_start]);
- }
- }
-
- /* duplicate or unsplit references intersecting both sides. */
- while(left_end < right_start) {
- /* split reference. */
- BVHReference lref, rref;
-
- split_reference(builder, lref, rref, refs[left_end], this->dim, this->pos);
-
- /* compute SAH for duplicate/unsplit candidates. */
- BoundBox lub = left_bounds; // Unsplit to left: new left-hand bounds.
- BoundBox rub = right_bounds; // Unsplit to right: new right-hand bounds.
- BoundBox ldb = left_bounds; // Duplicate: new left-hand bounds.
- BoundBox rdb = right_bounds; // Duplicate: new right-hand bounds.
-
- lub.grow(refs[left_end].bounds());
- rub.grow(refs[left_end].bounds());
- ldb.grow(lref.bounds());
- rdb.grow(rref.bounds());
-
- float lac = builder->params.triangle_cost(left_end - left_start);
- float rac = builder->params.triangle_cost(right_end - right_start);
- float lbc = builder->params.triangle_cost(left_end - left_start + 1);
- float rbc = builder->params.triangle_cost(right_end - right_start + 1);
-
- float unsplitLeftSAH = lub.safe_area() * lbc + right_bounds.safe_area() * rac;
- float unsplitRightSAH = left_bounds.safe_area() * lac + rub.safe_area() * rbc;
- float duplicateSAH = ldb.safe_area() * lbc + rdb.safe_area() * rbc;
- float minSAH = min(min(unsplitLeftSAH, unsplitRightSAH), duplicateSAH);
-
- if(minSAH == unsplitLeftSAH) {
- /* unsplit to left */
- left_bounds = lub;
- left_end++;
- }
- else if(minSAH == unsplitRightSAH) {
- /* unsplit to right */
- right_bounds = rub;
- swap(refs[left_end], refs[--right_start]);
- }
- else {
- /* duplicate */
- left_bounds = ldb;
- right_bounds = rdb;
- refs[left_end++] = lref;
- refs.insert(refs.begin() + right_end, rref);
- right_end++;
- }
- }
-
- left = BVHRange(left_bounds, left_start, left_end - left_start);
- right = BVHRange(right_bounds, right_start, right_end - right_start);
-}
-
-void BVHSpatialSplit::split_reference(BVHBuild *builder, BVHReference& left, BVHReference& right, const BVHReference& ref, int dim, float pos)
-{
- /* initialize boundboxes */
- BoundBox left_bounds = BoundBox::empty;
- BoundBox right_bounds = BoundBox::empty;
-
- /* loop over vertices/edges. */
- Object *ob = builder->objects[ref.prim_object()];
- const Mesh *mesh = ob->mesh;
- const int *inds = mesh->triangles[ref.prim_index()].v;
- const float3 *verts = &mesh->verts[0];
- const float3* v1 = &verts[inds[2]];
-
- for(int i = 0; i < 3; i++) {
- const float3* v0 = v1;
- int vindex = inds[i];
- v1 = &verts[vindex];
- float v0p = (*v0)[dim];
- float v1p = (*v1)[dim];
-
- /* insert vertex to the boxes it belongs to. */
- if(v0p <= pos)
- left_bounds.grow(*v0);
-
- if(v0p >= pos)
- right_bounds.grow(*v0);
-
- /* edge intersects the plane => insert intersection to both boxes. */
- if((v0p < pos && v1p > pos) || (v0p > pos && v1p < pos)) {
- float3 t = lerp(*v0, *v1, clamp((pos - v0p) / (v1p - v0p), 0.0f, 1.0f));
- left_bounds.grow(t);
- right_bounds.grow(t);
- }
- }
-
- /* intersect with original bounds. */
- left_bounds.max[dim] = pos;
- right_bounds.min[dim] = pos;
- left_bounds.intersect(ref.bounds());
- right_bounds.intersect(ref.bounds());
-
- /* set referecnes */
- left = BVHReference(left_bounds, ref.prim_index(), ref.prim_object());
- right = BVHReference(right_bounds, ref.prim_index(), ref.prim_object());
-}
-
-CCL_NAMESPACE_END
-
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-26 07:39:33 +0300