All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
primGather.h
1 //
2 // Copyright 2017 Pixar
3 //
4 // Licensed under the Apache License, Version 2.0 (the "Apache License")
5 // with the following modification; you may not use this file except in
6 // compliance with the Apache License and the following modification to it:
7 // Section 6. Trademarks. is deleted and replaced with:
8 //
9 // 6. Trademarks. This License does not grant permission to use the trade
10 // names, trademarks, service marks, or product names of the Licensor
11 // and its affiliates, except as required to comply with Section 4(c) of
12 // the License and to reproduce the content of the NOTICE file.
13 //
14 // You may obtain a copy of the Apache License at
15 //
16 // http://www.apache.org/licenses/LICENSE-2.0
17 //
18 // Unless required by applicable law or agreed to in writing, software
19 // distributed under the Apache License with the above modification is
20 // distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
21 // KIND, either express or implied. See the Apache License for the specific
22 // language governing permissions and limitations under the Apache License.
23 //
24 #ifndef PXR_IMAGING_HD_PRIM_GATHER_H
25 #define PXR_IMAGING_HD_PRIM_GATHER_H
26 
27 #include "pxr/pxr.h"
28 #include "pxr/imaging/hd/api.h"
29 
30 #include "pxr/usd/sdf/path.h"
31 
32 #include <vector>
33 #include <tbb/enumerable_thread_specific.h>
34 #include <tbb/blocked_range.h>
35 
36 PXR_NAMESPACE_OPEN_SCOPE
37 
38 class HdPrimGather final {
39 public:
40  typedef bool (*FilterPredicateFn)(const SdfPath &path, const void *param);
41 
42  HdPrimGather() = default;
43  ~HdPrimGather() = default;
44 
65  HD_API
66  void Filter(const SdfPathVector &paths,
67  const SdfPathVector &includePaths,
68  const SdfPathVector &excludePaths,
69  SdfPathVector *results);
70 
99  HD_API
100  void PredicatedFilter(const SdfPathVector &paths,
101  const SdfPathVector &includePaths,
102  const SdfPathVector &excludePaths,
103  FilterPredicateFn predicateFn,
104  void *predicateParam,
105  SdfPathVector *results);
106 
116  HD_API
117  void Subtree(const SdfPathVector &paths,
118  const SdfPath &rootPath,
119  SdfPathVector *results);
120 
134  HD_API
135  bool SubtreeAsRange(const SdfPathVector &paths,
136  const SdfPath &rootPath,
137  size_t *start,
138  size_t *end);
139 
140 private:
141  struct _PathFilter {
142  SdfPath _path;
143  bool _includePath; // false = exclude path
144 
145  _PathFilter(const SdfPath &path, bool includePath)
146  : _path(path)
147  , _includePath(includePath)
148  {
149 
150  }
151 
152  bool operator >(const _PathFilter &other) const {
153  return other._path < _path;
154  }
155  };
156  typedef std::vector<_PathFilter> _PathFilterArray;
157 
158  // While processing, the algorithm stores results as a set of ranges
159  // rather than copying all the paths.
160  // This to avoid copying the larger set of paths at intermediate
161  // processing steps.
162  struct _Range {
163  size_t _start;
164  size_t _end; // Inclusive
165 
166  _Range(size_t start, size_t end)
167  : _start(start)
168  , _end(end)
169  {
170 
171  }
172 
173  };
174  typedef std::vector<_Range> _RangeArray;
175  typedef tbb::enumerable_thread_specific<_RangeArray> _ConcurrentRangeArray;
176  typedef tbb::blocked_range<size_t> _ConcurrentRange;
177 
178 
179 
180  _PathFilterArray _filterList;
181  _RangeArray _gatheredRanges;
182  _ConcurrentRangeArray _resultRanges;
183 
184 
185 
186  size_t _FindLowerBound(const SdfPathVector &paths,
187  size_t start,
188  size_t end,
189  const SdfPath &path) const;
190  size_t _FindUpperBound(const SdfPathVector &paths,
191  size_t start,
192  size_t end,
193  const SdfPath &path) const;
194 
195  void _FilterRange(const SdfPathVector &paths,
196  size_t start,
197  size_t end,
198  bool include);
199 
200  void _SetupFilter(const SdfPathVector &includePaths,
201  const SdfPathVector &excludePaths);
202 
203  void _GatherPaths(const SdfPathVector &paths);
204 
205  // Outer Loop called for each range in vector
206  void _DoPredicateTestOnRange(const SdfPathVector &paths,
207  const _Range &range,
208  FilterPredicateFn predicateFn,
209  void *predicateParam);
210 
211  // Inner Loop over each prim in a sub range of _Range.
212  void _DoPredicateTestOnPrims(const SdfPathVector &paths,
213  _ConcurrentRange &range,
214  FilterPredicateFn predicateFn,
215  void *predicateParam);
216 
217  template <class Iterator>
218  static void _WriteResults(const SdfPathVector &paths,
219  const Iterator &rangesBegin,
220  const Iterator &rangesEnd,
221  SdfPathVector *results);
222 
223  void _FilterSubTree(const SdfPathVector &paths,
224  const SdfPath &rootPath);
225 
226  // No default copying or assignment
227  HdPrimGather(const HdPrimGather &) = delete;
228  HdPrimGather &operator =(const HdPrimGather &) = delete;
229 
230 };
231 
232 
233 PXR_NAMESPACE_CLOSE_SCOPE
234 
235 #endif // PXR_IMAGING_HD_PRIM_GATHER_H
A path value used to locate objects in layers or scenegraphs.
Definition: path.h:288