HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
primGather.h
Go to the documentation of this file.
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 
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 
45  ///
46  /// Filter takes a list of paths and returns a list of paths that
47  /// match the following criteria:
48  ///
49  /// - A path is prefixed by at least one include path
50  /// - A path is not prefixed by an exclude path that has more elements
51  /// than the include path with the most element that is a prefix
52  /// of the path.
53  ///
54  /// The list of paths to filter must be pre-sorted with
55  /// ordering defined by std::less<SdfPath &>.
56  ///
57  /// The list of include and exclude paths do not need to be pre-sorted.
58  ///
59  /// If the same path appears in the list of include and exclude paths
60  /// results are undefined.
61  ///
62  /// The resulting set of paths are stored in results arg, the results
63  /// might not be in sorted order.
64  ///
65  HD_API
66  void Filter(const SdfPathVector &paths,
67  const SdfPathVector &includePaths,
68  const SdfPathVector &excludePaths,
69  SdfPathVector *results);
70 
71  ///
72  /// PredicatedFilter takes a list of paths and returns a list of paths that
73  /// match the following criteria:
74  ///
75  /// - A path is prefixed by at least one include path
76  /// - A path is not prefixed by an exclude path that has more elements
77  /// than the include path with the most element that is a prefix
78  /// of the path.
79  /// - The predicate function for the path returns true.
80  ///
81  /// The list of paths to filter must be pre-sorted with
82  /// ordering defined by std::less<SdfPath &>.
83  ///
84  /// The list of include and exclude paths do not need to be pre-sorted.
85  ///
86  /// If the same path appears in the list of include and exclude paths
87  /// results are undefined.
88  ///
89  /// The predicate function has the prototype:
90  /// bool Predicate(const SdfPath &path, void *param);
91  ///
92  /// The function should return true if the path should appear in the results
93  /// and false if not. The Predicate function may be called on worker
94  /// threads and as such must be thread-safe.
95  ///
96  /// The resulting set of paths are stored in results arg, the results
97  /// might not be in sorted order.
98  ///
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 
107  ///
108  /// Subtree is a simplified form of filter, that gathers
109  /// all prims that meet the single rootPath prefix condition.
110  ///
111  /// The list of paths to filter must be pre-sorted with
112  /// ordering defined by std::less<SdfPath &>.
113  ///
114  /// The returned result maintain the sorted order.
115  ///
116  HD_API
117  void Subtree(const SdfPathVector &paths,
118  const SdfPath &rootPath,
119  SdfPathVector *results);
120 
121  ///
122  /// Subtree is a simplified form of filter, that gathers
123  /// all prims that meet the single rootPath prefix condition.
124  ///
125  /// The list of paths to filter must be pre-sorted with
126  /// ordering defined by std::less<SdfPath &>.
127  ///
128  /// Rather than returning a list the paths, it instead returns
129  /// the start and end (inclusive) indexes into the paths
130  /// vector of that subtree range.
131  ///
132  /// If the rootPath wasn't found or an error occurred, that
133  /// otherwise produces an invalid range. The method returns false.
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 
234 
235 #endif // PXR_IMAGING_HD_PRIM_GATHER_H
HdPrimGather()=default
GLenum GLint * range
Definition: glcorearb.h:1925
GLuint start
Definition: glcorearb.h:475
GLsizei const GLchar *const * path
Definition: glcorearb.h:3341
#define HD_API
Definition: api.h:40
~HdPrimGather()=default
OIIO_FORCEINLINE vbool4 operator>(const vint4 &a, const vint4 &b)
Definition: simd.h:4561
GLuint GLuint end
Definition: glcorearb.h:475
bool(* FilterPredicateFn)(const SdfPath &path, const void *param)
Definition: primGather.h:40
Definition: path.h:291
HD_API void Subtree(const SdfPathVector &paths, const SdfPath &rootPath, SdfPathVector *results)
std::vector< class SdfPath > SdfPathVector
A vector of SdfPaths.
Definition: path.h:212
HD_API void Filter(const SdfPathVector &paths, const SdfPathVector &includePaths, const SdfPathVector &excludePaths, SdfPathVector *results)
GLenum GLfloat param
Definition: glcorearb.h:104
PXR_NAMESPACE_CLOSE_SCOPE PXR_NAMESPACE_OPEN_SCOPE
Definition: path.h:1441
#define PXR_NAMESPACE_CLOSE_SCOPE
Definition: pxr.h:91
HD_API bool SubtreeAsRange(const SdfPathVector &paths, const SdfPath &rootPath, size_t *start, size_t *end)
HD_API void PredicatedFilter(const SdfPathVector &paths, const SdfPathVector &includePaths, const SdfPathVector &excludePaths, FilterPredicateFn predicateFn, void *predicateParam, SdfPathVector *results)