HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
bboxCache.h
Go to the documentation of this file.
1 //
2 // Copyright 2016 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 USDGEOM_BBOXCACHE_H
25 #define USDGEOM_BBOXCACHE_H
26 
27 #include "pxr/pxr.h"
28 #include "pxr/usd/usdGeom/api.h"
32 #include "pxr/base/gf/bbox3d.h"
33 #include "pxr/base/tf/hashmap.h"
35 
36 #include <hboost/optional.hpp>
37 #include <hboost/shared_array.hpp>
38 
40 
41 
42 class UsdGeomModelAPI;
43 
44 /// \class UsdGeomBBoxCache
45 ///
46 /// Caches bounds by recursively computing and aggregating bounds of children in
47 /// world space and aggregating the result back into local space.
48 ///
49 /// The cache is configured for a specific time and
50 /// \ref UsdGeomImageable::GetPurposeAttr() set of purposes. When querying a
51 /// bound, transforms and extents are read either from the time specified or
52 /// UsdTimeCode::Default(), following \ref Usd_ValueResolution standard
53 /// time-sample value resolution. As noted in SetIncludedPurposes(), changing
54 /// the included purposes does not invalidate the cache, because we cache
55 /// purpose along with the geometric data.
56 ///
57 /// Child prims that are invisible at the requested time are excluded when
58 /// computing a prim's bounds. However, if a bound is requested directly for an
59 /// excluded prim, it will be computed. Additionally, only prims deriving from
60 /// UsdGeomImageable are included in child bounds computations.
61 ///
62 /// Unlike standard UsdStage traversals, the traversal performed by the
63 /// UsdGeomBBoxCache includes prims that are unloaded (see UsdPrim::IsLoaded()).
64 /// This makes it possible to fetch bounds for a UsdStage that has been opened
65 /// without \em forcePopulate , provided the unloaded model prims have authored
66 /// extent hints (see UsdGeomModelAPI::GetExtentsHint()).
67 ///
68 /// This class is optimized for computing tight <b>untransformed "object"
69 /// space</b> bounds for component-models. In the absence of component models,
70 /// bounds are optimized for world-space, since there is no other easily
71 /// identifiable space for which to optimize, and we cannot optimize for every
72 /// prim's local space without performing quadratic work.
73 ///
74 /// The TfDebug flag, USDGEOM_BBOX, is provided for debugging.
75 ///
76 /// Warnings:
77 /// * This class should only be used with valid UsdPrim objects.
78 ///
79 /// * This cache does not listen for change notifications; the user is
80 /// responsible for clearing the cache when changes occur.
81 ///
82 /// * Thread safety: instances of this class may not be used concurrently.
83 ///
84 /// * Plugins may be loaded in order to compute extents for prim types provided
85 /// by that plugin. See UsdGeomBoundable::ComputeExtentFromPlugins
86 ///
88 {
89 public:
90  /// Construct a new BBoxCache for a specific \p time and set of
91  /// \p includedPurposes.
92  ///
93  /// Only prims with a purpose that matches the \p includedPurposes will be
94  /// considered when accumulating child bounds. See UsdGeomImageable for
95  /// allowed purpose values.
96  ///
97  /// If \p useExtentsHint is true, then when computing the bounds for any
98  /// model-root prim, if the prim is visible at \p time, we will fetch its
99  /// extents hint (via UsdGeomModelAPI::GetExtentsHint()). If it is authored,
100  /// we use it to compute the bounding box for the selected combination of
101  /// includedPurposes by combining bounding box hints that have been cached
102  /// for various values of purposes.
103  ///
104  /// If \p ignoreVisibility is true invisible prims will be included during
105  /// bounds computations.
106  ///
109  bool useExtentsHint=false, bool ignoreVisibility=false);
110 
111  /// Copy constructor.
113  UsdGeomBBoxCache(UsdGeomBBoxCache const &other);
114 
115  /// Copy assignment.
117  UsdGeomBBoxCache &operator=(UsdGeomBBoxCache const &other);
118 
119  /// Compute the bound of the given prim in world space, leveraging any
120  /// pre-existing, cached bounds.
121  ///
122  /// The bound of the prim is computed, including the transform (if any)
123  /// authored on the node itself, and then transformed to world space.
124  ///
125  /// Error handling note: No checking of \p prim validity is performed. If
126  /// \p prim is invalid, this method will abort the program; therefore it is
127  /// the client's responsibility to ensure \p prim is valid.
129  GfBBox3d ComputeWorldBound(const UsdPrim& prim);
130 
131  /// Compute the bound of the given prim in the space of an ancestor prim,
132  /// \p relativeToAncestorPrim, leveraging any pre-existing cached bounds.
133  ///
134  /// The computed bound excludes the local transform at
135  /// \p relativeToAncestorPrim. The computed bound may be incorrect if
136  /// \p relativeToAncestorPrim is not an ancestor of \p prim.
137  ///
140  const UsdPrim &relativeToAncestorPrim);
141 
142  /// Computes the oriented bounding box of the given prim, leveraging any
143  /// pre-existing, cached bounds.
144  ///
145  /// The computed bound includes the transform authored on the prim itself,
146  /// but does not include any ancestor transforms (it does not include the
147  /// local-to-world transform).
148  ///
149  /// See ComputeWorldBound() for notes on performance and error handling.
151  GfBBox3d ComputeLocalBound(const UsdPrim& prim);
152 
153  /// Computes the bound of the prim's children leveraging any pre-existing,
154  /// cached bounds, but does not include the transform (if any) authored on
155  /// the prim itself.
156  ///
157  /// \b IMPORTANT: while the BBox does not contain the local transformation,
158  /// in general it may still contain a non-identity transformation matrix to
159  /// put the bounds in the correct space. Therefore, to obtain the correct
160  /// axis-aligned bounding box, the client must call ComputeAlignedRange().
161  ///
162  /// See ComputeWorldBound() for notes on performance and error handling.
165 
166  /// \overload
167  /// Computes the bound of the prim's descendents while excluding the
168  /// subtrees rooted at the paths in \p pathsToSkip. Additionally, the
169  /// parameter \p ctmOverrides is used to specify overrides to the CTM values
170  /// of certain paths underneath the prim. The CTM values in the
171  /// \p ctmOverrides map are in the space of the given prim, \p prim.
172  ///
173  /// This leverages any pre-existing, cached bounds, but does not include the
174  /// transform (if any) authored on the prim itself.
175  ///
176  /// \b IMPORTANT: while the BBox does not contain the local transformation,
177  /// in general it may still contain a non-identity transformation matrix to
178  /// put the bounds in the correct space. Therefore, to obtain the correct
179  /// axis-aligned bounding box, the client must call ComputeAlignedRange().
180  ///
181  /// See ComputeWorldBound() for notes on performance and error handling.
184  const UsdPrim &prim,
185  const SdfPathSet &pathsToSkip,
187 
188  /// Compute the bound of the given point instances in world space.
189  ///
190  /// The bounds of each instance is computed and then transformed to world
191  /// space. The \p result pointer must point to \p numIds GfBBox3d instances
192  /// to be filled.
194  bool
196  const UsdGeomPointInstancer& instancer,
197  int64_t const *instanceIdBegin,
198  size_t numIds,
199  GfBBox3d *result);
200 
201  /// Compute the bound of the given point instance in world space.
202  ///
203  GfBBox3d
205  const UsdGeomPointInstancer& instancer, int64_t instanceId) {
206  GfBBox3d ret;
207  ComputePointInstanceWorldBounds(instancer, &instanceId, 1, &ret);
208  return ret;
209  }
210 
211  /// Compute the bounds of the given point instances in the space of an
212  /// ancestor prim \p relativeToAncestorPrim. Write the results to
213  /// \p result.
214  ///
215  /// The computed bound excludes the local transform at
216  /// \p relativeToAncestorPrim. The computed bound may be incorrect if
217  /// \p relativeToAncestorPrim is not an ancestor of \p prim.
218  ///
219  /// The \p result pointer must point to \p numIds GfBBox3d instances to be
220  /// filled.
222  bool
224  const UsdGeomPointInstancer &instancer,
225  int64_t const *instanceIdBegin,
226  size_t numIds,
227  const UsdPrim &relativeToAncestorPrim,
228  GfBBox3d *result);
229 
230  /// Compute the bound of the given point instance in the space of an
231  /// ancestor prim \p relativeToAncestorPrim.
232  GfBBox3d
234  const UsdGeomPointInstancer &instancer,
235  int64_t instanceId,
236  const UsdPrim &relativeToAncestorPrim) {
237  GfBBox3d ret;
239  instancer, &instanceId, 1, relativeToAncestorPrim, &ret);
240  return ret;
241  }
242 
243  /// Compute the oriented bounding boxes of the given point instances.
244  ///
245  /// The computed bounds include the transform authored on the instancer
246  /// itself, but does not include any ancestor transforms (it does not
247  /// include the local-to-world transform).
248  ///
249  /// The \p result pointer must point to \p numIds GfBBox3d instances to be
250  /// filled.
252  bool
254  const UsdGeomPointInstancer& instancer,
255  int64_t const *instanceIdBegin,
256  size_t numIds,
257  GfBBox3d *result);
258 
259  /// Compute the oriented bounding boxes of the given point instances.
260  GfBBox3d
262  const UsdGeomPointInstancer& instancer,
263  int64_t instanceId) {
264  GfBBox3d ret;
265  ComputePointInstanceLocalBounds(instancer, &instanceId, 1, &ret);
266  return ret;
267  }
268 
269 
270  /// Computes the bound of the given point instances, but does not include
271  /// the transform (if any) authored on the instancer itself.
272  ///
273  /// \b IMPORTANT: while the BBox does not contain the local transformation,
274  /// in general it may still contain a non-identity transformation matrix to
275  /// put the bounds in the correct space. Therefore, to obtain the correct
276  /// axis-aligned bounding box, the client must call ComputeAlignedRange().
277  ///
278  /// The \p result pointer must point to \p numIds GfBBox3d instances to be
279  /// filled.
281  bool
283  const UsdGeomPointInstancer& instancer,
284  int64_t const *instanceIdBegin,
285  size_t numIds,
286  GfBBox3d *result);
287 
288  /// Computes the bound of the given point instances, but does not include
289  /// the instancer's transform.
290  GfBBox3d
292  const UsdGeomPointInstancer& instancer,
293  int64_t instanceId) {
294  GfBBox3d ret;
296  instancer, &instanceId, 1, &ret);
297  return ret;
298  }
299 
300  /// Clears all pre-cached values.
302  void Clear();
303 
304  /// Indicate the set of \p includedPurposes to use when resolving child
305  /// bounds. Each child's purpose must match one of the elements of this set
306  /// to be included in the computation; if it does not, child is excluded.
307  ///
308  /// Note the use of *child* in the docs above, purpose is ignored for the
309  /// prim for whose bounds are directly queried.
310  ///
311  /// Changing this value <b>does not invalidate existing caches</b>.
313  void SetIncludedPurposes(const TfTokenVector& includedPurposes);
314 
315  /// Get the current set of included purposes.
316  const TfTokenVector& GetIncludedPurposes() { return _includedPurposes; }
317 
318  /// Returns whether authored extent hints are used to compute
319  /// bounding boxes.
320  bool GetUseExtentsHint() const {
321  return _useExtentsHint;
322  }
323 
324  /// Returns whether prim visibility should be ignored when computing
325  /// bounding boxes.
326  bool GetIgnoreVisibility() const {
327  return _ignoreVisibility;
328  }
329 
330  /// Use the new \p time when computing values and may clear any existing
331  /// values cached for the previous time. Setting \p time to the current time
332  /// is a no-op.
334  void SetTime(UsdTimeCode time);
335 
336  /// Get the current time from which this cache is reading values.
337  UsdTimeCode GetTime() const { return _time; }
338 
339  /// Set the base time value for this bbox cache. This value is used only
340  /// when computing bboxes for point instancer instances (see
341  /// ComputePointInstanceWorldBounds(), for example). See
342  /// UsdGeomPointInstancer::ComputeExtentAtTime() for more information. If
343  /// unset, the bbox cache uses its time (GetTime() / SetTime()) for this
344  /// value.
345  ///
346  /// Note that setting the base time does not invalidate any cache entries.
347  void SetBaseTime(UsdTimeCode baseTime) {
348  _baseTime = baseTime;
349  }
350 
351  /// Return the base time if set, otherwise GetTime(). Use HasBaseTime() to
352  /// observe if a base time has been set.
354  return _baseTime.get_value_or(GetTime());
355  }
356 
357  /// Clear this cache's baseTime if one has been set. After calling this,
358  /// the cache will use its time as the baseTime value.
359  void ClearBaseTime() {
360  _baseTime = hboost::none;
361  }
362 
363  /// Return true if this cache has a baseTime that's been explicitly set,
364  /// false otherwise.
365  bool HasBaseTime() const {
366  return static_cast<bool>(_baseTime);
367  }
368 
369 private:
370  // Worker task.
371  class _BBoxTask;
372 
373  // Helper object for computing bounding boxes for instance masters.
374  class _MasterBBoxResolver;
375 
376  // Map of purpose tokens to associated bboxes.
377  typedef std::map<TfToken, GfBBox3d, TfTokenFastArbitraryLessThan>
378  _PurposeToBBoxMap;
379 
380  bool
381  _ComputePointInstanceBoundsHelper(
382  const UsdGeomPointInstancer &instancer,
383  int64_t const *instanceIdBegin,
384  size_t numIds,
385  GfMatrix4d const &xform,
386  GfBBox3d *result);
387 
388  // Returns true if the \p prim should be included during child bounds
389  // accumulation.
390  bool _ShouldIncludePrim(const UsdPrim& prim);
391 
392  // True if \p attr or \p query may return different values given different
393  // time queries. Note that a true result implies the attribute may have no
394  // value, a default value or a single time sample value.
395  bool _IsVarying(const UsdAttribute& attr);
396  bool _IsVarying(const UsdAttributeQuery& query);
397 
398  // Populate the local bbox for the requested prim, without the
399  // local-to-world transform or local transform applied. Return true when
400  // bbox volume > 0.
401  bool _Resolve(const UsdPrim& prim, _PurposeToBBoxMap *bboxes);
402 
403  // Compute the extent of a UsdGeomBoundable object. Return true if the
404  // computation succeeds and false on failure.
405  bool _ComputeExtent(
406  const UsdGeomBoundable& boundableObj,
407  VtVec3fArray* extent) const;
408 
409  // Resolves a single prim. This method must be thread safe. Assumes the
410  // cache entry has been created for \p prim.
411  //
412  // \p inverseComponentCtm is used to combine all the child bboxes in
413  // component-relative space.
414  void _ResolvePrim(_BBoxTask* task,
415  const UsdPrim& prim,
416  const GfMatrix4d &inverseComponentCtm);
417 
418  struct _Entry {
419  _Entry()
420  : isComplete(false)
421  , isVarying(false)
422  , isIncluded(false)
423  { }
424 
425  // The cached bboxes for the various values of purpose token.
426  _PurposeToBBoxMap bboxes;
427 
428  // True when data in the entry is valid.
429  bool isComplete;
430 
431  // True when the entry varies over time.
432  bool isVarying;
433 
434  // True when the entry is visible.
435  bool isIncluded;
436 
437  // Computed purpose value of the prim that's associated with the entry.
438  TfToken purpose;
439 
440  // Queries for attributes that need to be re-computed at each
441  // time for this entry. This will be invalid for non-varying entries.
442  hboost::shared_array<UsdAttributeQuery> queries;
443  };
444 
445  // Returns the cache entry for the given \p prim if one already exists.
446  // If no entry exists, creates (but does not resolve) entries for
447  // \p prim and all of its descendents. In this case, the master prims
448  // whose bounding boxes need to be resolved in order to resolve \p prim
449  // will be returned in \p masterPrims.
450  _Entry* _FindOrCreateEntriesForPrim(const UsdPrim& prim,
451  std::vector<UsdPrim>* masterPrims);
452 
453  // Returns the combined bounding box for the currently included set of
454  // purposes given a _PurposeToBBoxMap.
455  GfBBox3d _GetCombinedBBoxForIncludedPurposes(
456  const _PurposeToBBoxMap &bboxes);
457 
458  // Populates \p bbox with the bounding box computed from the authored
459  // extents hint. Based on the included purposes, the extents in the
460  // extentsHint attribute are combined together to compute the bounding box.
461  bool _GetBBoxFromExtentsHint(
462  const UsdGeomModelAPI &geomModel,
463  const UsdAttributeQuery &extentsHintQuery,
464  _PurposeToBBoxMap *bboxes);
465 
466  // Returns whether the children of the given prim can be pruned
467  // from the traversal to pre-populate entries.
468  bool _ShouldPruneChildren(const UsdPrim &prim, _Entry *entry);
469 
470  // Helper function for computing a prim's purpose efficiently by using the
471  // parent entry's cached computed-purpose.
472  TfToken _ComputePurpose(const UsdPrim &prim);
473 
474  // Helper to determine if we should use extents hints for \p prim.
475  inline bool _UseExtentsHintForPrim(UsdPrim const &prim) const;
476 
477  typedef hboost::hash<UsdPrim> _UsdPrimHash;
478  typedef TfHashMap<UsdPrim, _Entry, _UsdPrimHash> _PrimBBoxHashMap;
479 
480  WorkArenaDispatcher _dispatcher;
481  UsdTimeCode _time;
482  hboost::optional<UsdTimeCode> _baseTime;
483  TfTokenVector _includedPurposes;
484  UsdGeomXformCache _ctmCache;
485  _PrimBBoxHashMap _bboxCache;
486  bool _useExtentsHint;
487  bool _ignoreVisibility;
488 };
489 
490 
492 
493 #endif // USDGEOM_BBOXCACHE_H
USDGEOM_API GfBBox3d ComputeUntransformedBound(const UsdPrim &prim)
USDGEOM_API bool ComputePointInstanceLocalBounds(const UsdGeomPointInstancer &instancer, int64_t const *instanceIdBegin, size_t numIds, GfBBox3d *result)
USDGEOM_API void SetIncludedPurposes(const TfTokenVector &includedPurposes)
bool none(const vbool4 &v)
Definition: simd.h:3373
bool HasBaseTime() const
Definition: bboxCache.h:365
GT_API const UT_StringHolder time
USDGEOM_API GfBBox3d ComputeLocalBound(const UsdPrim &prim)
USDGEOM_API bool ComputePointInstanceWorldBounds(const UsdGeomPointInstancer &instancer, int64_t const *instanceIdBegin, size_t numIds, GfBBox3d *result)
GLenum query
Definition: glew.h:5704
bool GetIgnoreVisibility() const
Definition: bboxCache.h:326
USDGEOM_API void Clear()
Clears all pre-cached values.
bool GetUseExtentsHint() const
Definition: bboxCache.h:320
USDGEOM_API bool ComputePointInstanceUntransformedBounds(const UsdGeomPointInstancer &instancer, int64_t const *instanceIdBegin, size_t numIds, GfBBox3d *result)
USDGEOM_API UsdGeomBBoxCache & operator=(UsdGeomBBoxCache const &other)
Copy assignment.
Definition: token.h:89
void ClearBaseTime()
Definition: bboxCache.h:359
GfBBox3d ComputePointInstanceRelativeBound(const UsdGeomPointInstancer &instancer, int64_t instanceId, const UsdPrim &relativeToAncestorPrim)
Definition: bboxCache.h:233
USDGEOM_API bool ComputePointInstanceRelativeBounds(const UsdGeomPointInstancer &instancer, int64_t const *instanceIdBegin, size_t numIds, const UsdPrim &relativeToAncestorPrim, GfBBox3d *result)
Definition: prim.h:131
std::vector< TfToken > TfTokenVector
Convenience types.
Definition: token.h:438
void SetBaseTime(UsdTimeCode baseTime)
Definition: bboxCache.h:347
GLint GLenum GLsizei GLsizei GLsizei GLsizei extent
Definition: glew.h:15538
GfBBox3d ComputePointInstanceUntransformedBound(const UsdGeomPointInstancer &instancer, int64_t instanceId)
Definition: bboxCache.h:291
std::set< class SdfPath > SdfPathSet
A set of SdfPaths.
Definition: path.h:206
PXR_NAMESPACE_CLOSE_SCOPE PXR_NAMESPACE_OPEN_SCOPE
Definition: path.h:1245
GfBBox3d ComputePointInstanceLocalBound(const UsdGeomPointInstancer &instancer, int64_t instanceId)
Compute the oriented bounding boxes of the given point instances.
Definition: bboxCache.h:261
GfBBox3d ComputePointInstanceWorldBound(const UsdGeomPointInstancer &instancer, int64_t instanceId)
Definition: bboxCache.h:204
#define PXR_NAMESPACE_CLOSE_SCOPE
Definition: pxr.h:83
GLuint64EXT * result
Definition: glew.h:14007
USDGEOM_API void SetTime(UsdTimeCode time)
UsdTimeCode GetBaseTime() const
Definition: bboxCache.h:353
#define USDGEOM_API
Definition: api.h:40
USDGEOM_API GfBBox3d ComputeWorldBound(const UsdPrim &prim)
USDGEOM_API GfBBox3d ComputeRelativeBound(const UsdPrim &prim, const UsdPrim &relativeToAncestorPrim)
USDGEOM_API UsdGeomBBoxCache(UsdTimeCode time, TfTokenVector includedPurposes, bool useExtentsHint=false, bool ignoreVisibility=false)
const TfTokenVector & GetIncludedPurposes()
Get the current set of included purposes.
Definition: bboxCache.h:316
UsdTimeCode GetTime() const
Get the current time from which this cache is reading values.
Definition: bboxCache.h:337