primGather.h

//
// Copyright 2017 Pixar
//
// Licensed under the Apache License, Version 2.0 (the "Apache License")
// with the following modification; you may not use this file except in
// compliance with the Apache License and the following modification to it:
// Section 6. Trademarks. is deleted and replaced with:
//
// 6. Trademarks. This License does not grant permission to use the trade
//    names, trademarks, service marks, or product names of the Licensor
//    and its affiliates, except as required to comply with Section 4(c) of
//    the License and to reproduce the content of the NOTICE file.
//
// You may obtain a copy of the Apache License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the Apache License with the above modification is
// distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied. See the Apache License for the specific
// language governing permissions and limitations under the Apache License.
//
#ifndef PXR_IMAGING_HD_PRIM_GATHER_H
#define PXR_IMAGING_HD_PRIM_GATHER_H
 
#include "pxr/pxr.h"
#include "pxr/imaging/hd/api.h"
 
#include "pxr/usd/sdf/path.h"
 
#include <vector>
#include <tbb/enumerable_thread_specific.h>
#include <tbb/blocked_range.h>
 
PXR_NAMESPACE_OPEN_SCOPE
 
class HdPrimGather final {
public:
    typedef bool (*FilterPredicateFn)(const SdfPath &path, const void *param);
 
    HdPrimGather()  = default;
    ~HdPrimGather() = default;
 
    HD_API
    void Filter(const SdfPathVector &paths,
                const SdfPathVector &includePaths,
                const SdfPathVector &excludePaths,
                SdfPathVector       *results);
 
    HD_API
    void PredicatedFilter(const SdfPathVector &paths,
                          const SdfPathVector &includePaths,
                          const SdfPathVector &excludePaths,
                          FilterPredicateFn    predicateFn,
                          void                *predicateParam,
                          SdfPathVector       *results);
 
    HD_API
    void Subtree(const SdfPathVector &paths,
                 const SdfPath       &rootPath,
                 SdfPathVector       *results);
 
    HD_API
    bool SubtreeAsRange(const SdfPathVector &paths,
                        const SdfPath       &rootPath,
                        size_t *start,
                        size_t *end);
 
private:
    struct _PathFilter {
        SdfPath _path;
        bool    _includePath;  // false = exclude path
 
        _PathFilter(const SdfPath &path, bool includePath)
         : _path(path)
         , _includePath(includePath)
        {
 
        }
 
        bool operator >(const _PathFilter &other) const {
            return other._path < _path;
        }
    };
    typedef std::vector<_PathFilter> _PathFilterArray;
 
    // While processing, the algorithm stores results as a set of ranges
    // rather than copying all the paths.
    // This to avoid copying the larger set of paths at intermediate
    // processing steps.
    struct _Range {
        size_t _start;
        size_t _end; // Inclusive
 
        _Range(size_t start, size_t end)
         : _start(start)
         , _end(end)
        {
 
        }
 
    };
    typedef std::vector<_Range> _RangeArray;
    typedef tbb::enumerable_thread_specific<_RangeArray> _ConcurrentRangeArray;
    typedef tbb::blocked_range<size_t>                   _ConcurrentRange;
 
 
 
    _PathFilterArray      _filterList;
    _RangeArray           _gatheredRanges;
    _ConcurrentRangeArray _resultRanges;
 
 
 
    size_t _FindLowerBound(const SdfPathVector &paths,
                           size_t start,
                           size_t end,
                           const SdfPath &path) const;
    size_t _FindUpperBound(const SdfPathVector &paths,
                           size_t start,
                           size_t end,
                           const SdfPath &path) const;
 
    void _FilterRange(const SdfPathVector &paths,
                      size_t start,
                      size_t end,
                      bool include);
 
    void _SetupFilter(const SdfPathVector &includePaths,
                     const SdfPathVector &excludePaths);
 
    void _GatherPaths(const SdfPathVector &paths);
 
    // Outer Loop called for each range in vector
    void _DoPredicateTestOnRange(const SdfPathVector &paths,
                                 const _Range        &range,
                                 FilterPredicateFn    predicateFn,
                                 void                *predicateParam);
 
    // Inner Loop over each prim in a sub range of _Range.
    void _DoPredicateTestOnPrims(const SdfPathVector &paths,
                                 _ConcurrentRange    &range,
                                 FilterPredicateFn    predicateFn,
                                 void                *predicateParam);
 
    template <class Iterator>
    static void _WriteResults(const SdfPathVector &paths,
                              const Iterator &rangesBegin,
                              const Iterator &rangesEnd,
                              SdfPathVector *results);
 
    void _FilterSubTree(const SdfPathVector &paths,
                        const SdfPath       &rootPath);
 
    // No default copying or assignment
    HdPrimGather(const HdPrimGather &) = delete;
    HdPrimGather &operator =(const HdPrimGather &) = delete;
 
};
 
 
PXR_NAMESPACE_CLOSE_SCOPE
 
#endif // PXR_IMAGING_HD_PRIM_GATHER_H