Revision control
++ // Copyright 2009-2021 Intel Corporation
++ // SPDX-License-Identifier: Apache-2.0
++
++ #pragma once
++
++ #include "../common/primref_mb.h"
++ #include "../../common/algorithms/parallel_filter.h"
++
++ #define MBLUR_TIME_SPLIT_THRESHOLD 1.25f
++
++ namespace embree
++ {
++ namespace isa
++ {
++ /*! Performs standard object binning */
++ template<typename PrimRefMB, typename RecalculatePrimRef, size_t BINS>
++ struct HeuristicMBlurTemporalSplit
++ {
++ typedef BinSplit<MBLUR_NUM_OBJECT_BINS> Split;
++ typedef mvector<PrimRefMB>* PrimRefVector;
++ typedef typename PrimRefMB::BBox BBox;
++
++ static const size_t PARALLEL_THRESHOLD = 3 * 1024;
++ static const size_t PARALLEL_FIND_BLOCK_SIZE = 1024;
++ static const size_t PARALLEL_PARTITION_BLOCK_SIZE = 128;
++
++ HeuristicMBlurTemporalSplit (MemoryMonitorInterface* device, const RecalculatePrimRef& recalculatePrimRef)
++ : device(device), recalculatePrimRef(recalculatePrimRef) {}
++
++ struct TemporalBinInfo
++ {
++ __forceinline TemporalBinInfo () {
++ }
++
++ __forceinline TemporalBinInfo (EmptyTy)
++ {
++ for (size_t i=0; i<BINS-1; i++)
++ {
++ count0[i] = count1[i] = 0;
++ bounds0[i] = bounds1[i] = empty;
++ }
++ }
++
++ void bin(const PrimRefMB* prims, size_t begin, size_t end, BBox1f time_range, const SetMB& set, const RecalculatePrimRef& recalculatePrimRef)
++ {
++ for (int b=0; b<BINS-1; b++)
++ {
++ const float t = float(b+1)/float(BINS);
++ const float ct = lerp(time_range.lower,time_range.upper,t);
++ const float center_time = set.align_time(ct);
++ if (center_time <= time_range.lower) continue;
++ if (center_time >= time_range.upper) continue;
++ const BBox1f dt0(time_range.lower,center_time);
++ const BBox1f dt1(center_time,time_range.upper);
++
++ /* find linear bounds for both time segments */
++ for (size_t i=begin; i<end; i++)
++ {
++ if (prims[i].time_range_overlap(dt0))
++ {
++ const LBBox3fa bn0 = recalculatePrimRef.linearBounds(prims[i],dt0);
++ #if MBLUR_BIN_LBBOX
++ bounds0[b].extend(bn0);
++ #else
++ bounds0[b].extend(bn0.interpolate(0.5f));
++ #endif
++ count0[b] += prims[i].timeSegmentRange(dt0).size();
++ }
++
++ if (prims[i].time_range_overlap(dt1))
++ {
++ const LBBox3fa bn1 = recalculatePrimRef.linearBounds(prims[i],dt1);
++ #if MBLUR_BIN_LBBOX
++ bounds1[b].extend(bn1);
++ #else
++ bounds1[b].extend(bn1.interpolate(0.5f));
++ #endif
++ count1[b] += prims[i].timeSegmentRange(dt1).size();
++ }
++ }
++ }
++ }
++
++ __forceinline void bin_parallel(const PrimRefMB* prims, size_t begin, size_t end, size_t blockSize, size_t parallelThreshold, BBox1f time_range, const SetMB& set, const RecalculatePrimRef& recalculatePrimRef)
++ {
++ if (likely(end-begin < parallelThreshold)) {
++ bin(prims,begin,end,time_range,set,recalculatePrimRef);
++ }
++ else
++ {
++ auto bin = [&](const range<size_t>& r) -> TemporalBinInfo {
++ TemporalBinInfo binner(empty); binner.bin(prims, r.begin(), r.end(), time_range, set, recalculatePrimRef); return binner;
++ };
++ *this = parallel_reduce(begin,end,blockSize,TemporalBinInfo(empty),bin,merge2);
++ }
++ }
++
++ /*! merges in other binning information */
++ __forceinline void merge (const TemporalBinInfo& other)
++ {
++ for (size_t i=0; i<BINS-1; i++)
++ {
++ count0[i] += other.count0[i];
++ count1[i] += other.count1[i];
++ bounds0[i].extend(other.bounds0[i]);
++ bounds1[i].extend(other.bounds1[i]);
++ }
++ }
++
++ static __forceinline const TemporalBinInfo merge2(const TemporalBinInfo& a, const TemporalBinInfo& b) {
++ TemporalBinInfo r = a; r.merge(b); return r;
++ }
++
++ Split best(int logBlockSize, BBox1f time_range, const SetMB& set)
++ {
++ float bestSAH = inf;
++ float bestPos = 0.0f;
++ for (int b=0; b<BINS-1; b++)
++ {
++ float t = float(b+1)/float(BINS);
++ float ct = lerp(time_range.lower,time_range.upper,t);
++ const float center_time = set.align_time(ct);
++ if (center_time <= time_range.lower) continue;
++ if (center_time >= time_range.upper) continue;
++ const BBox1f dt0(time_range.lower,center_time);
++ const BBox1f dt1(center_time,time_range.upper);
++
++ /* calculate sah */
++ const size_t lCount = (count0[b]+(size_t(1) << logBlockSize)-1) >> int(logBlockSize);
++ const size_t rCount = (count1[b]+(size_t(1) << logBlockSize)-1) >> int(logBlockSize);
++ float sah0 = expectedApproxHalfArea(bounds0[b])*float(lCount)*dt0.size();
++ float sah1 = expectedApproxHalfArea(bounds1[b])*float(rCount)*dt1.size();
++ if (unlikely(lCount == 0)) sah0 = 0.0f; // happens for initial splits when objects not alive over entire shutter time
++ if (unlikely(rCount == 0)) sah1 = 0.0f;
++ const float sah = sah0+sah1;
++ if (sah < bestSAH) {
++ bestSAH = sah;
++ bestPos = center_time;
++ }
++ }
++ return Split(bestSAH*MBLUR_TIME_SPLIT_THRESHOLD,(unsigned)Split::SPLIT_TEMPORAL,0,bestPos);
++ }
++
++ public:
++ size_t count0[BINS-1];
++ size_t count1[BINS-1];
++ BBox bounds0[BINS-1];
++ BBox bounds1[BINS-1];
++ };
++
++ /*! finds the best split */
++ const Split find(const SetMB& set, const size_t logBlockSize)
++ {
++ assert(set.size() > 0);
++ TemporalBinInfo binner(empty);
++ binner.bin_parallel(set.prims->data(),set.begin(),set.end(),PARALLEL_FIND_BLOCK_SIZE,PARALLEL_THRESHOLD,set.time_range,set,recalculatePrimRef);
++ Split tsplit = binner.best((int)logBlockSize,set.time_range,set);
++ if (!tsplit.valid()) tsplit.data = Split::SPLIT_FALLBACK; // use fallback split
++ return tsplit;
++ }
++
++ __forceinline std::unique_ptr<mvector<PrimRefMB>> split(const Split& tsplit, const SetMB& set, SetMB& lset, SetMB& rset)
++ {
++ assert(tsplit.sah != float(inf));
++ assert(tsplit.fpos > set.time_range.lower);
++ assert(tsplit.fpos < set.time_range.upper);
++
++ float center_time = tsplit.fpos;
++ const BBox1f time_range0(set.time_range.lower,center_time);
++ const BBox1f time_range1(center_time,set.time_range.upper);
++ mvector<PrimRefMB>& prims = *set.prims;
++
++ /* calculate primrefs for first time range */
++ std::unique_ptr<mvector<PrimRefMB>> new_vector(new mvector<PrimRefMB>(device, set.size()));
++ PrimRefVector lprims = new_vector.get();
++
++ auto reduction_func0 = [&] (const range<size_t>& r) {
++ PrimInfoMB pinfo = empty;
++ for (size_t i=r.begin(); i<r.end(); i++)
++ {
++ if (likely(prims[i].time_range_overlap(time_range0)))
++ {
++ const PrimRefMB& prim = recalculatePrimRef(prims[i],time_range0);
++ (*lprims)[i-set.begin()] = prim;
++ pinfo.add_primref(prim);
++ }
++ else
++ {
++ (*lprims)[i-set.begin()] = prims[i];
++ }
++ }
++ return pinfo;
++ };
++ PrimInfoMB linfo = parallel_reduce(set.object_range,PARALLEL_PARTITION_BLOCK_SIZE,PARALLEL_THRESHOLD,PrimInfoMB(empty),reduction_func0,PrimInfoMB::merge2);
++
++ /* primrefs for first time range are in lprims[0 .. set.size()) */
++ /* some primitives may need to be filtered out */
++ if (linfo.size() != set.size())
++ linfo.object_range._end = parallel_filter(lprims->data(), size_t(0), set.size(), size_t(1024),
++ [&](const PrimRefMB& prim) { return prim.time_range_overlap(time_range0); });
++
++ lset = SetMB(linfo,lprims,time_range0);
++
++ /* calculate primrefs for second time range */
++ auto reduction_func1 = [&] (const range<size_t>& r) {
++ PrimInfoMB pinfo = empty;
++ for (size_t i=r.begin(); i<r.end(); i++)
++ {
++ if (likely(prims[i].time_range_overlap(time_range1)))
++ {
++ const PrimRefMB& prim = recalculatePrimRef(prims[i],time_range1);
++ prims[i] = prim;
++ pinfo.add_primref(prim);
++ }
++ }
++ return pinfo;
++ };
++ PrimInfoMB rinfo = parallel_reduce(set.object_range,PARALLEL_PARTITION_BLOCK_SIZE,PARALLEL_THRESHOLD,PrimInfoMB(empty),reduction_func1,PrimInfoMB::merge2);
++ rinfo.object_range = range<size_t>(set.begin(), set.begin() + rinfo.size());
++
++ /* primrefs for second time range are in prims[set.begin() .. set.end()) */
++ /* some primitives may need to be filtered out */
++ if (rinfo.size() != set.size())
++ rinfo.object_range._end = parallel_filter(prims.data(), set.begin(), set.end(), size_t(1024),
++ [&](const PrimRefMB& prim) { return prim.time_range_overlap(time_range1); });
++
++ rset = SetMB(rinfo,&prims,time_range1);
++
++ return new_vector;
++ }
++
++ private:
++ MemoryMonitorInterface* device; // device to report memory usage to
++ const RecalculatePrimRef recalculatePrimRef;
++ };
++ }
++ }