Changeset View
Changeset View
Standalone View
Standalone View
intern/cycles/bvh/sort.cpp
- This file was added.
| /* | |||||
| * 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/sort.h" | |||||
| #include "bvh/build.h" | |||||
| #include "util/algorithm.h" | |||||
| #include "util/task.h" | |||||
| CCL_NAMESPACE_BEGIN | |||||
| static const int BVH_SORT_THRESHOLD = 4096; | |||||
| struct BVHReferenceCompare { | |||||
| public: | |||||
| int dim; | |||||
| const BVHUnaligned *unaligned_heuristic; | |||||
| const Transform *aligned_space; | |||||
| BVHReferenceCompare(int dim, | |||||
| const BVHUnaligned *unaligned_heuristic, | |||||
| const Transform *aligned_space) | |||||
| : dim(dim), unaligned_heuristic(unaligned_heuristic), aligned_space(aligned_space) | |||||
| { | |||||
| } | |||||
| __forceinline BoundBox get_prim_bounds(const BVHReference &prim) const | |||||
| { | |||||
| return (aligned_space != NULL) ? | |||||
| unaligned_heuristic->compute_aligned_prim_boundbox(prim, *aligned_space) : | |||||
| prim.bounds(); | |||||
| } | |||||
| /* Compare two references. | |||||
| * | |||||
| * Returns value is similar to return value of strcmp(). | |||||
| */ | |||||
| __forceinline int compare(const BVHReference &ra, const BVHReference &rb) const | |||||
| { | |||||
| BoundBox ra_bounds = get_prim_bounds(ra), rb_bounds = get_prim_bounds(rb); | |||||
| float ca = ra_bounds.min[dim] + ra_bounds.max[dim]; | |||||
| float cb = rb_bounds.min[dim] + rb_bounds.max[dim]; | |||||
| if (ca < cb) | |||||
| return -1; | |||||
| else if (ca > cb) | |||||
| return 1; | |||||
| else if (ra.prim_object() < rb.prim_object()) | |||||
| return -1; | |||||
| else if (ra.prim_object() > rb.prim_object()) | |||||
| return 1; | |||||
| else if (ra.prim_index() < rb.prim_index()) | |||||
| return -1; | |||||
| else if (ra.prim_index() > rb.prim_index()) | |||||
| return 1; | |||||
| else if (ra.prim_type() < rb.prim_type()) | |||||
| return -1; | |||||
| else if (ra.prim_type() > rb.prim_type()) | |||||
| return 1; | |||||
| return 0; | |||||
| } | |||||
| bool operator()(const BVHReference &ra, const BVHReference &rb) | |||||
| { | |||||
| return (compare(ra, rb) < 0); | |||||
| } | |||||
| }; | |||||
| static void bvh_reference_sort_threaded(TaskPool *task_pool, | |||||
| BVHReference *data, | |||||
| const int job_start, | |||||
| const int job_end, | |||||
| const BVHReferenceCompare &compare); | |||||
| /* Multi-threaded reference sort. */ | |||||
| static void bvh_reference_sort_threaded(TaskPool *task_pool, | |||||
| BVHReference *data, | |||||
| const int job_start, | |||||
| const int job_end, | |||||
| const BVHReferenceCompare &compare) | |||||
| { | |||||
| int start = job_start, end = job_end; | |||||
| bool have_work = (start < end); | |||||
| while (have_work) { | |||||
| const int count = job_end - job_start; | |||||
| if (count < BVH_SORT_THRESHOLD) { | |||||
| /* Number of reference low enough, faster to finish the job | |||||
| * in one thread rather than to spawn more threads. | |||||
| */ | |||||
| sort(data + job_start, data + job_end + 1, compare); | |||||
| break; | |||||
| } | |||||
| /* Single QSort step. | |||||
| * Use median-of-three method for the pivot point. | |||||
| */ | |||||
| int left = start, right = end; | |||||
| int center = (left + right) >> 1; | |||||
| if (compare.compare(data[left], data[center]) > 0) { | |||||
| swap(data[left], data[center]); | |||||
| } | |||||
| if (compare.compare(data[left], data[right]) > 0) { | |||||
| swap(data[left], data[right]); | |||||
| } | |||||
| if (compare.compare(data[center], data[right]) > 0) { | |||||
| swap(data[center], data[right]); | |||||
| } | |||||
| swap(data[center], data[right - 1]); | |||||
| BVHReference median = data[right - 1]; | |||||
| do { | |||||
| while (compare.compare(data[left], median) < 0) { | |||||
| ++left; | |||||
| } | |||||
| while (compare.compare(data[right], median) > 0) { | |||||
| --right; | |||||
| } | |||||
| if (left <= right) { | |||||
| swap(data[left], data[right]); | |||||
| ++left; | |||||
| --right; | |||||
| } | |||||
| } while (left <= right); | |||||
| /* We only create one new task here to reduce downside effects of | |||||
| * latency in TaskScheduler. | |||||
| * So generally current thread keeps working on the left part of the | |||||
| * array, and we create new task for the right side. | |||||
| * However, if there's nothing to be done in the left side of the array | |||||
| * we don't create any tasks and make it so current thread works on the | |||||
| * right side. | |||||
| */ | |||||
| have_work = false; | |||||
| if (left < end) { | |||||
| if (start < right) { | |||||
| task_pool->push( | |||||
| function_bind(bvh_reference_sort_threaded, task_pool, data, left, end, compare)); | |||||
| } | |||||
| else { | |||||
| start = left; | |||||
| have_work = true; | |||||
| } | |||||
| } | |||||
| if (start < right) { | |||||
| end = right; | |||||
| have_work = true; | |||||
| } | |||||
| } | |||||
| } | |||||
| void bvh_reference_sort(int start, | |||||
| int end, | |||||
| BVHReference *data, | |||||
| int dim, | |||||
| const BVHUnaligned *unaligned_heuristic, | |||||
| const Transform *aligned_space) | |||||
| { | |||||
| const int count = end - start; | |||||
| BVHReferenceCompare compare(dim, unaligned_heuristic, aligned_space); | |||||
| if (count < BVH_SORT_THRESHOLD) { | |||||
| /* It is important to not use any mutex if array is small enough, | |||||
| * otherwise we end up in situation when we're going to sleep far | |||||
| * too often. | |||||
| */ | |||||
| sort(data + start, data + end, compare); | |||||
| } | |||||
| else { | |||||
| TaskPool task_pool; | |||||
| bvh_reference_sort_threaded(&task_pool, data, start, end - 1, compare); | |||||
| task_pool.wait_work(); | |||||
| } | |||||
| } | |||||
| CCL_NAMESPACE_END | |||||