bboxCache.h
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 PXR_USD_USD_GEOM_BBOX_CACHE_H
25 #define PXR_USD_USD_GEOM_BBOX_CACHE_H
26 
27 #include "pxr/pxr.h"
28 #include "pxr/usd/usdGeom/api.h"
29 #include "pxr/usd/usdGeom/xformCache.h"
31 #include "pxr/usd/usd/attributeQuery.h"
32 #include "pxr/base/gf/bbox3d.h"
33 #include "pxr/base/tf/hashmap.h"
35 
36 #include <boost/optional.hpp>
37 #include <boost/shared_array.hpp>
38 
39 PXR_NAMESPACE_OPEN_SCOPE
40 
41 
42 class UsdGeomModelAPI;
43 
88 {
89 public:
107  USDGEOM_API
108  UsdGeomBBoxCache(UsdTimeCode time, TfTokenVector includedPurposes,
109  bool useExtentsHint=false, bool ignoreVisibility=false);
110 
112  USDGEOM_API
113  UsdGeomBBoxCache(UsdGeomBBoxCache const &other);
114 
116  USDGEOM_API
118 
128  USDGEOM_API
129  GfBBox3d ComputeWorldBound(const UsdPrim& prim);
130 
142  USDGEOM_API
144  const UsdPrim &prim,
145  const SdfPathSet &pathsToSkip,
146  const GfMatrix4d &primOverride,
147  const TfHashMap<SdfPath, GfMatrix4d, SdfPath::Hash> &ctmOverrides);
148 
149 
157  USDGEOM_API
159  const UsdPrim &relativeToAncestorPrim);
160 
169  USDGEOM_API
170  GfBBox3d ComputeLocalBound(const UsdPrim& prim);
171 
182  USDGEOM_API
184 
201  USDGEOM_API
203  const UsdPrim &prim,
204  const SdfPathSet &pathsToSkip,
205  const TfHashMap<SdfPath, GfMatrix4d, SdfPath::Hash> &ctmOverrides);
206 
212  USDGEOM_API
213  bool
215  const UsdGeomPointInstancer& instancer,
216  int64_t const *instanceIdBegin,
217  size_t numIds,
218  GfBBox3d *result);
219 
222  GfBBox3d
224  const UsdGeomPointInstancer& instancer, int64_t instanceId) {
225  GfBBox3d ret;
226  ComputePointInstanceWorldBounds(instancer, &instanceId, 1, &ret);
227  return ret;
228  }
229 
240  USDGEOM_API
241  bool
243  const UsdGeomPointInstancer &instancer,
244  int64_t const *instanceIdBegin,
245  size_t numIds,
246  const UsdPrim &relativeToAncestorPrim,
247  GfBBox3d *result);
248 
251  GfBBox3d
253  const UsdGeomPointInstancer &instancer,
254  int64_t instanceId,
255  const UsdPrim &relativeToAncestorPrim) {
256  GfBBox3d ret;
258  instancer, &instanceId, 1, relativeToAncestorPrim, &ret);
259  return ret;
260  }
261 
270  USDGEOM_API
271  bool
273  const UsdGeomPointInstancer& instancer,
274  int64_t const *instanceIdBegin,
275  size_t numIds,
276  GfBBox3d *result);
277 
279  GfBBox3d
281  const UsdGeomPointInstancer& instancer,
282  int64_t instanceId) {
283  GfBBox3d ret;
284  ComputePointInstanceLocalBounds(instancer, &instanceId, 1, &ret);
285  return ret;
286  }
287 
288 
299  USDGEOM_API
300  bool
302  const UsdGeomPointInstancer& instancer,
303  int64_t const *instanceIdBegin,
304  size_t numIds,
305  GfBBox3d *result);
306 
309  GfBBox3d
311  const UsdGeomPointInstancer& instancer,
312  int64_t instanceId) {
313  GfBBox3d ret;
315  instancer, &instanceId, 1, &ret);
316  return ret;
317  }
318 
320  USDGEOM_API
321  void Clear();
322 
331  USDGEOM_API
332  void SetIncludedPurposes(const TfTokenVector& includedPurposes);
333 
335  const TfTokenVector& GetIncludedPurposes() { return _includedPurposes; }
336 
339  bool GetUseExtentsHint() const {
340  return _useExtentsHint;
341  }
342 
345  bool GetIgnoreVisibility() const {
346  return _ignoreVisibility;
347  }
348 
352  USDGEOM_API
353  void SetTime(UsdTimeCode time);
354 
356  UsdTimeCode GetTime() const { return _time; }
357 
366  void SetBaseTime(UsdTimeCode baseTime) {
367  _baseTime = baseTime;
368  }
369 
373  return _baseTime.get_value_or(GetTime());
374  }
375 
378  void ClearBaseTime() {
379  _baseTime = boost::none;
380  }
381 
384  bool HasBaseTime() const {
385  return static_cast<bool>(_baseTime);
386  }
387 
388 private:
389  // Worker task.
390  class _BBoxTask;
391 
392  // Helper object for computing bounding boxes for instance prototypes.
393  class _PrototypeBBoxResolver;
394 
395  // Map of purpose tokens to associated bboxes.
396  typedef std::map<TfToken, GfBBox3d, TfTokenFastArbitraryLessThan>
397  _PurposeToBBoxMap;
398 
399  // Each individual prim will have it's own entry in the bbox cache. When
400  // instancing is involved we store the prototype prims and their children in
401  // the cache for use by each prim that instances each prototype. However,
402  // because of the way we compute and inherit purpose, we may end up needed
403  // to compute multitple different bboxes for prototypes and their children
404  // if the prims that instance them would cause these prototypes to inherit a
405  // different purpose value when the prims under the prototype don't have an
406  // authored purpose of their own.
407  //
408  // This struct is here to represent a prim and the purpose that it would
409  // inherit from the prim that instances it. It is used as the key for the
410  // map of prim's to the cached entries, allowing prims in prototypes to have
411  // more than one bbox cache entry for each distinct context needed to
412  // appropriately compute for all instances. instanceInheritablePurpose will
413  // always be empty for prims that aren't prototypes or children of
414  // prototypes, meaning that prims not in prototypes will only have one
415  // context each.
416  struct _PrimContext {
417  // The prim itself
418  UsdPrim prim;
419 
420  // The purpose that would be inherited from the instancing prim if this
421  // prim does not have an explicit purpose.
422  TfToken instanceInheritablePurpose;
423 
424  _PrimContext() = default;
425  explicit _PrimContext(const UsdPrim &prim_,
426  const TfToken &purpose = TfToken())
427  : prim(prim_), instanceInheritablePurpose(purpose) {};
428 
429  bool operator==(const _PrimContext &rhs) const {
430  return prim == rhs.prim &&
431  instanceInheritablePurpose == rhs.instanceInheritablePurpose;
432  }
433 
434  // Convenience stringify for debugging.
435  std::string ToString() const;
436  };
437 
438  template<typename TransformType>
439  GfBBox3d _ComputeBoundWithOverridesHelper(
440  const UsdPrim &prim,
441  const SdfPathSet &pathsToSkip,
442  const TransformType &primOverride,
443  const TfHashMap<SdfPath, GfMatrix4d, SdfPath::Hash> &ctmOverrides);
444 
445  bool
446  _ComputePointInstanceBoundsHelper(
447  const UsdGeomPointInstancer &instancer,
448  int64_t const *instanceIdBegin,
449  size_t numIds,
450  GfMatrix4d const &xform,
451  GfBBox3d *result);
452 
453  // Returns true if the \p prim should be included during child bounds
454  // accumulation.
455  bool _ShouldIncludePrim(const UsdPrim& prim);
456 
457  // True if \p attr or \p query may return different values given different
458  // time queries. Note that a true result implies the attribute may have no
459  // value, a default value or a single time sample value.
460  bool _IsVarying(const UsdAttribute& attr);
461  bool _IsVarying(const UsdAttributeQuery& query);
462 
463  // Populate the local bbox for the requested prim, without the
464  // local-to-world transform or local transform applied. Return true when
465  // bbox volume > 0.
466  bool _Resolve(const UsdPrim& prim, _PurposeToBBoxMap *bboxes);
467 
468  // Resolves a single prim. This method must be thread safe. Assumes the
469  // cache entry has been created for \p prim.
470  //
471  // \p inverseComponentCtm is used to combine all the child bboxes in
472  // component-relative space.
473  void _ResolvePrim(_BBoxTask* task,
474  const _PrimContext& prim,
475  const GfMatrix4d &inverseComponentCtm);
476 
477  struct _Entry {
478  _Entry()
479  : isComplete(false)
480  , isVarying(false)
481  , isIncluded(false)
482  { }
483 
484  // The cached bboxes for the various values of purpose token.
485  _PurposeToBBoxMap bboxes;
486 
487  // True when data in the entry is valid.
488  bool isComplete;
489 
490  // True when the entry varies over time.
491  bool isVarying;
492 
493  // True when the entry is visible.
494  bool isIncluded;
495 
496  // Computed purpose info of the prim that's associated with the entry.
497  // This data includes the prim's actual computed purpose as well as
498  // whether this purpose is inheritable by child prims.
499  UsdGeomImageable::PurposeInfo purposeInfo;
500 
501  // Queries for attributes that need to be re-computed at each
502  // time for this entry. This will be invalid for non-varying entries.
503  boost::shared_array<UsdAttributeQuery> queries;
504  };
505 
506  // Returns the cache entry for the given \p prim if one already exists.
507  // If no entry exists, creates (but does not resolve) entries for
508  // \p prim and all of its descendents. In this case, the prototype prims
509  // whose bounding boxes need to be resolved in order to resolve \p prim
510  // will be returned in \p prototypePrimContexts.
511  _Entry* _FindOrCreateEntriesForPrim(
512  const _PrimContext& prim,
513  std::vector<_PrimContext> *prototypePrimContexts);
514 
515  // Returns the combined bounding box for the currently included set of
516  // purposes given a _PurposeToBBoxMap.
517  GfBBox3d _GetCombinedBBoxForIncludedPurposes(
518  const _PurposeToBBoxMap &bboxes);
519 
520  // Populates \p bbox with the bounding box computed from the authored
521  // extents hint. Based on the included purposes, the extents in the
522  // extentsHint attribute are combined together to compute the bounding box.
523  bool _GetBBoxFromExtentsHint(
524  const UsdGeomModelAPI &geomModel,
525  const UsdAttributeQuery &extentsHintQuery,
526  _PurposeToBBoxMap *bboxes);
527 
528  // Returns whether the children of the given prim can be pruned
529  // from the traversal to pre-populate entries.
530  bool _ShouldPruneChildren(const UsdPrim &prim, _Entry *entry);
531 
532  // Helper function for computing a prim's purpose info efficiently by
533  // using the parent entry's cached computed purpose info and caching it
534  // its cache entry.
535  // Optionally this can recursively compute and cache the purposes for any
536  // existing parent entries in the cache that haven't had their purposes
537  // computed yet.
538  template <bool IsRecursive>
539  void _ComputePurposeInfo(_Entry *entry, const _PrimContext &prim);
540 
541  // Helper to determine if we should use extents hints for \p prim.
542  inline bool _UseExtentsHintForPrim(UsdPrim const &prim) const;
543 
544  // Need hash_value for boost to key cache entries by prim context.
545  friend size_t hash_value(const _PrimContext &key);
546 
547  typedef boost::hash<_PrimContext> _PrimContextHash;
548  typedef TfHashMap<_PrimContext, _Entry, _PrimContextHash> _PrimBBoxHashMap;
549 
550  // Finds the cache entry for the prim context if it exists.
551  _Entry *_FindEntry(const _PrimContext &primContext)
552  {
553  return TfMapLookupPtr(_bboxCache, primContext);
554  }
555 
556  // Returns the cache entry for the prim context, adding it if doesn't
557  // exist.
558  _Entry *_InsertEntry(const _PrimContext &primContext)
559  {
560  return &(_bboxCache[primContext]);
561  }
562 
563  WorkDispatcher _dispatcher;
564  UsdTimeCode _time;
565  boost::optional<UsdTimeCode> _baseTime;
566  TfTokenVector _includedPurposes;
567  UsdGeomXformCache _ctmCache;
568  _PrimBBoxHashMap _bboxCache;
569  bool _useExtentsHint;
570  bool _ignoreVisibility;
571 };
572 
573 
574 PXR_NAMESPACE_CLOSE_SCOPE
575 
576 #endif // PXR_USD_USD_GEOM_BBOX_CACHE_H
USDGEOM_API UsdGeomBBoxCache & operator=(UsdGeomBBoxCache const &other)
Copy assignment.
bool GetIgnoreVisibility() const
Returns whether prim visibility should be ignored when computing bounding boxes.
Definition: bboxCache.h:345
UsdGeomModelAPI extends the generic UsdModelAPI schema with geometry specific concepts such as cached...
Definition: modelAPI.h:148
A work dispatcher runs concurrent tasks.
Definition: dispatcher.h:75
USDGEOM_API bool ComputePointInstanceLocalBounds(const UsdGeomPointInstancer &instancer, int64_t const *instanceIdBegin, size_t numIds, GfBBox3d *result)
Compute the oriented bounding boxes of the given point instances.
Object for efficiently making repeated queries for attribute values.
const TfTokenVector & GetIncludedPurposes()
Get the current set of included purposes.
Definition: bboxCache.h:335
bool GetUseExtentsHint() const
Returns whether authored extent hints are used to compute bounding boxes.
Definition: bboxCache.h:339
void ClearBaseTime()
Clear this cache's baseTime if one has been set.
Definition: bboxCache.h:378
Caches bounds by recursively computing and aggregating bounds of children in world space and aggregat...
Definition: bboxCache.h:87
Scenegraph object for authoring and retrieving numeric, string, and array valued data,...
Definition: attribute.h:176
UsdTimeCode GetBaseTime() const
Return the base time if set, otherwise GetTime().
Definition: bboxCache.h:372
USDGEOM_API void Clear()
Clears all pre-cached values.
GfBBox3d ComputePointInstanceRelativeBound(const UsdGeomPointInstancer &instancer, int64_t instanceId, const UsdPrim &relativeToAncestorPrim)
Compute the bound of the given point instance in the space of an ancestor prim relativeToAncestorPrim...
Definition: bboxCache.h:252
USDGEOM_API GfBBox3d ComputeWorldBoundWithOverrides(const UsdPrim &prim, const SdfPathSet &pathsToSkip, const GfMatrix4d &primOverride, const TfHashMap< SdfPath, GfMatrix4d, SdfPath::Hash > &ctmOverrides)
Computes the bound of the prim's descendents in world space while excluding the subtrees rooted at th...
Token for efficient comparison, assignment, and hashing of known strings.
Definition: token.h:87
void SetBaseTime(UsdTimeCode baseTime)
Set the base time value for this bbox cache.
Definition: bboxCache.h:366
Stores a 4x4 matrix of double elements.
Definition: matrix4d.h:88
Represent a time value, which may be either numeric, holding a double value, or a sentinel value UsdT...
Definition: timeCode.h:85
USDGEOM_API bool ComputePointInstanceUntransformedBounds(const UsdGeomPointInstancer &instancer, int64_t const *instanceIdBegin, size_t numIds, GfBBox3d *result)
Computes the bound of the given point instances, but does not include the transform (if any) authored...
Value type containing information about a prim's computed effective purpose as well as storing whethe...
Definition: imageable.h:400
UsdPrim is the sole persistent scenegraph object on a UsdStage, and is the embodiment of a "Prim" as ...
Definition: prim.h:134
USDGEOM_API GfBBox3d ComputeWorldBound(const UsdPrim &prim)
Compute the bound of the given prim in world space, leveraging any pre-existing, cached bounds.
std::vector< TfToken > TfTokenVector
Convenience types.
Definition: token.h:442
USDGEOM_API bool ComputePointInstanceWorldBounds(const UsdGeomPointInstancer &instancer, int64_t const *instanceIdBegin, size_t numIds, GfBBox3d *result)
Compute the bound of the given point instances in world space.
GfBBox3d ComputePointInstanceUntransformedBound(const UsdGeomPointInstancer &instancer, int64_t instanceId)
Computes the bound of the given point instances, but does not include the instancer's transform.
Definition: bboxCache.h:310
UsdTimeCode GetTime() const
Get the current time from which this cache is reading values.
Definition: bboxCache.h:356
USDGEOM_API GfBBox3d ComputeRelativeBound(const UsdPrim &prim, const UsdPrim &relativeToAncestorPrim)
Compute the bound of the given prim in the space of an ancestor prim, relativeToAncestorPrim,...
Container::mapped_type * TfMapLookupPtr(Container &map, Key const &key)
Checks if an item exists in a map or TfHashMap, without copying it.
Definition: stl.h:143
USDGEOM_API bool ComputePointInstanceRelativeBounds(const UsdGeomPointInstancer &instancer, int64_t const *instanceIdBegin, size_t numIds, const UsdPrim &relativeToAncestorPrim, GfBBox3d *result)
Compute the bounds of the given point instances in the space of an ancestor prim relativeToAncestorPr...
USDGEOM_API GfBBox3d ComputeLocalBound(const UsdPrim &prim)
Computes the oriented bounding box of the given prim, leveraging any pre-existing,...
USDGEOM_API UsdGeomBBoxCache(UsdTimeCode time, TfTokenVector includedPurposes, bool useExtentsHint=false, bool ignoreVisibility=false)
Construct a new BBoxCache for a specific time and set of includedPurposes.
GfBBox3d ComputePointInstanceLocalBound(const UsdGeomPointInstancer &instancer, int64_t instanceId)
Compute the oriented bounding boxes of the given point instances.
Definition: bboxCache.h:280
GfBBox3d ComputePointInstanceWorldBound(const UsdGeomPointInstancer &instancer, int64_t instanceId)
Compute the bound of the given point instance in world space.
Definition: bboxCache.h:223
Encodes vectorized instancing of multiple, potentially animated, prototypes (object/instance masters)...
VT_API bool operator==(VtDictionary const &, VtDictionary const &)
Equality comparison.
USDGEOM_API void SetTime(UsdTimeCode time)
Use the new time when computing values and may clear any existing values cached for the previous time...
USDGEOM_API GfBBox3d ComputeUntransformedBound(const UsdPrim &prim)
Computes the bound of the prim's children leveraging any pre-existing, cached bounds,...
USDGEOM_API void SetIncludedPurposes(const TfTokenVector &includedPurposes)
Indicate the set of includedPurposes to use when resolving child bounds.
Basic type: arbitrarily oriented 3D bounding box.
Definition: bbox3d.h:84
A caching mechanism for transform matrices.
Definition: xformCache.h:58
bool HasBaseTime() const
Return true if this cache has a baseTime that's been explicitly set, false otherwise.
Definition: bboxCache.h:384