bboxCache.h

//
// Copyright 2016 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_USD_USD_GEOM_BBOX_CACHE_H
#define PXR_USD_USD_GEOM_BBOX_CACHE_H

#include "pxr/pxr.h"
#include "pxr/usd/usdGeom/api.h"
#include "pxr/usd/usdGeom/xformCache.h"
#include "pxr/usd/usdGeom/pointInstancer.h"
#include "pxr/usd/usd/attributeQuery.h"
#include "pxr/base/gf/bbox3d.h"
#include "pxr/base/tf/hash.h"
#include "pxr/base/tf/hashmap.h"
#include "pxr/base/work/dispatcher.h"

#include <boost/optional.hpp>
#include <boost/shared_array.hpp>

PXR_NAMESPACE_OPEN_SCOPE


class UsdGeomModelAPI;

class UsdGeomBBoxCache
{
public:
    USDGEOM_API
    UsdGeomBBoxCache(UsdTimeCode time, TfTokenVector includedPurposes,
                     bool useExtentsHint=false, bool ignoreVisibility=false);

    USDGEOM_API
    UsdGeomBBoxCache(UsdGeomBBoxCache const &other);
     
    USDGEOM_API
    UsdGeomBBoxCache &operator=(UsdGeomBBoxCache const &other);

    USDGEOM_API
    GfBBox3d ComputeWorldBound(const UsdPrim& prim);

    USDGEOM_API
    GfBBox3d ComputeWorldBoundWithOverrides(
        const UsdPrim &prim,
        const SdfPathSet &pathsToSkip,
        const GfMatrix4d &primOverride,
        const TfHashMap<SdfPath, GfMatrix4d, SdfPath::Hash> &ctmOverrides);


    USDGEOM_API
    GfBBox3d ComputeRelativeBound(const UsdPrim &prim,
                                  const UsdPrim &relativeToAncestorPrim);

    USDGEOM_API
    GfBBox3d ComputeLocalBound(const UsdPrim& prim);

    USDGEOM_API
    GfBBox3d ComputeUntransformedBound(const UsdPrim& prim);

    USDGEOM_API
    GfBBox3d ComputeUntransformedBound(
        const UsdPrim &prim,
        const SdfPathSet &pathsToSkip,
        const TfHashMap<SdfPath, GfMatrix4d, SdfPath::Hash> &ctmOverrides);

    USDGEOM_API
    bool
    ComputePointInstanceWorldBounds(
        const UsdGeomPointInstancer& instancer,
        int64_t const *instanceIdBegin,
        size_t numIds,
        GfBBox3d *result);

    GfBBox3d
    ComputePointInstanceWorldBound(
        const UsdGeomPointInstancer& instancer, int64_t instanceId) {
        GfBBox3d ret;
        ComputePointInstanceWorldBounds(instancer, &instanceId, 1, &ret);
        return ret;
    }

    USDGEOM_API
    bool
    ComputePointInstanceRelativeBounds(
        const UsdGeomPointInstancer &instancer,
        int64_t const *instanceIdBegin,
        size_t numIds,
        const UsdPrim &relativeToAncestorPrim,
        GfBBox3d *result);

    GfBBox3d
    ComputePointInstanceRelativeBound(
        const UsdGeomPointInstancer &instancer,
        int64_t instanceId,
        const UsdPrim &relativeToAncestorPrim) {
        GfBBox3d ret;
        ComputePointInstanceRelativeBounds(
            instancer, &instanceId, 1, relativeToAncestorPrim, &ret);
        return ret;
    }

    USDGEOM_API
    bool
    ComputePointInstanceLocalBounds(
        const UsdGeomPointInstancer& instancer,
        int64_t const *instanceIdBegin,
        size_t numIds,
        GfBBox3d *result);

    GfBBox3d
    ComputePointInstanceLocalBound(
        const UsdGeomPointInstancer& instancer,
        int64_t instanceId) {
        GfBBox3d ret;
        ComputePointInstanceLocalBounds(instancer, &instanceId, 1, &ret);
        return ret;
    }
            

    USDGEOM_API
    bool
    ComputePointInstanceUntransformedBounds(
        const UsdGeomPointInstancer& instancer,
        int64_t const *instanceIdBegin,
        size_t numIds,
        GfBBox3d *result);

    GfBBox3d
    ComputePointInstanceUntransformedBound(
        const UsdGeomPointInstancer& instancer,
        int64_t instanceId) {
        GfBBox3d ret;
        ComputePointInstanceUntransformedBounds(
            instancer, &instanceId, 1, &ret);
        return ret;
    }
    
    USDGEOM_API
    void Clear();

    USDGEOM_API
    void SetIncludedPurposes(const TfTokenVector& includedPurposes);

    const TfTokenVector& GetIncludedPurposes() { return _includedPurposes; }

    bool GetUseExtentsHint() const {
        return _useExtentsHint;
    }

    bool GetIgnoreVisibility() const {
        return _ignoreVisibility;
    }    

    USDGEOM_API
    void SetTime(UsdTimeCode time);

    UsdTimeCode GetTime() const { return _time; }

    void SetBaseTime(UsdTimeCode baseTime) {
        _baseTime = baseTime;
    }

    UsdTimeCode GetBaseTime() const {
        return _baseTime.get_value_or(GetTime());
    }

    void ClearBaseTime() {
        _baseTime = boost::none;
    }

    bool HasBaseTime() const {
        return static_cast<bool>(_baseTime);
    }

private:
    // Worker task.
    class _BBoxTask;

    // Helper object for computing bounding boxes for instance prototypes.
    class _PrototypeBBoxResolver;

    // Map of purpose tokens to associated bboxes.
    typedef std::map<TfToken, GfBBox3d,  TfTokenFastArbitraryLessThan>
        _PurposeToBBoxMap;

    // Each individual prim will have it's own entry in the bbox cache.  When
    // instancing is involved we store the prototype prims and their children in
    // the cache for use by each prim that instances each prototype.  However,
    // because of the way we compute and inherit purpose, we may end up needed
    // to compute multitple different bboxes for prototypes and their children
    // if the prims that instance them would cause these prototypes to inherit a
    // different purpose value when the prims under the prototype don't have an
    // authored purpose of their own.
    //
    // This struct is here to represent a prim and the purpose that it would
    // inherit from the prim that instances it. It is used as the key for the
    // map of prim's to the cached entries, allowing prims in prototypes to have
    // more than one bbox cache entry for each distinct context needed to
    // appropriately compute for all instances. instanceInheritablePurpose will
    // always be empty for prims that aren't prototypes or children of
    // prototypes, meaning that prims not in prototypes will only have one
    // context each.
    struct _PrimContext {
        // The prim itself
        UsdPrim prim;

        // The purpose that would be inherited from the instancing prim if this
        // prim does not have an explicit purpose.
        TfToken instanceInheritablePurpose;

        _PrimContext() = default;
        explicit _PrimContext(const UsdPrim &prim_, 
                               const TfToken &purpose = TfToken()) 
            : prim(prim_), instanceInheritablePurpose(purpose) {};

        bool operator==(const _PrimContext &rhs) const {
            return prim == rhs.prim && 
                instanceInheritablePurpose == rhs.instanceInheritablePurpose;
        }

        // Convenience stringify for debugging.
        std::string ToString() const;
    };

    template<typename TransformType>
    GfBBox3d _ComputeBoundWithOverridesHelper(
        const UsdPrim &prim,
        const SdfPathSet &pathsToSkip,
        const TransformType &primOverride,
        const TfHashMap<SdfPath, GfMatrix4d, SdfPath::Hash> &ctmOverrides);

    bool
    _ComputePointInstanceBoundsHelper(
        const UsdGeomPointInstancer &instancer,
        int64_t const *instanceIdBegin,
        size_t numIds,
        GfMatrix4d const &xform,
        GfBBox3d *result);

    // Returns true if the \p prim should be included during child bounds
    // accumulation.
    bool _ShouldIncludePrim(const UsdPrim& prim);

    // True if \p attr or \p query may return different values given different
    // time queries. Note that a true result implies the attribute may have no
    // value, a default value or a single time sample value.
    bool _IsVarying(const UsdAttribute& attr);
    bool _IsVarying(const UsdAttributeQuery& query);

    // Populate the local bbox for the requested prim, without the
    // local-to-world transform or local transform applied. Return true when
    // bbox volume > 0.
    bool _Resolve(const UsdPrim& prim, _PurposeToBBoxMap *bboxes);

    // Resolves a single prim. This method must be thread safe. Assumes the
    // cache entry has been created for \p prim.
    //
    // \p inverseComponentCtm is used to combine all the child bboxes in
    // component-relative space.
    void _ResolvePrim(_BBoxTask* task,
                      const _PrimContext& prim,
                      const GfMatrix4d &inverseComponentCtm);

    struct _Entry {
        _Entry()
            : isComplete(false)
            , isVarying(false)
            , isIncluded(false)
        { }

        // The cached bboxes for the various values of purpose token.
        _PurposeToBBoxMap bboxes;

        // Queries for attributes that need to be re-computed at each
        // time for this entry. This will be invalid for non-varying entries.
        boost::shared_array<UsdAttributeQuery> queries;

        // Computed purpose info of the prim that's associated with the entry.
        // This data includes the prim's actual computed purpose as well as
        // whether this purpose is inheritable by child prims.
        UsdGeomImageable::PurposeInfo purposeInfo;

        // True when data in the entry is valid.
        bool isComplete;

        // True when the entry varies over time.
        bool isVarying;

        // True when the entry is visible.
        bool isIncluded;
    };

    // Returns the cache entry for the given \p prim if one already exists.
    // If no entry exists, creates (but does not resolve) entries for
    // \p prim and all of its descendents. In this case, the prototype prims
    // whose bounding boxes need to be resolved in order to resolve \p prim
    // will be returned in \p prototypePrimContexts.
    _Entry* _FindOrCreateEntriesForPrim(
        const _PrimContext& prim,
        std::vector<_PrimContext> *prototypePrimContexts);

    // Returns the combined bounding box for the currently included set of
    // purposes given a _PurposeToBBoxMap.
    GfBBox3d _GetCombinedBBoxForIncludedPurposes(
        const _PurposeToBBoxMap &bboxes);

    // Populates \p bbox with the bounding box computed from the authored
    // extents hint. Based on the included purposes, the extents in the
    // extentsHint attribute are combined together to compute the bounding box.
    bool _GetBBoxFromExtentsHint(
        const UsdGeomModelAPI &geomModel,
        const UsdAttributeQuery &extentsHintQuery,
        _PurposeToBBoxMap *bboxes);

    // Returns whether the children of the given prim can be pruned
    // from the traversal to pre-populate entries.
    bool _ShouldPruneChildren(const UsdPrim &prim, _Entry *entry);

    // Helper function for computing a prim's purpose info efficiently by 
    // using the parent entry's cached computed purpose info and caching it
    // its cache entry.
    // Optionally this can recursively compute and cache the purposes for any 
    // existing parent entries in the cache that haven't had their purposes 
    // computed yet.
    template <bool IsRecursive>
    void _ComputePurposeInfo(_Entry *entry, const _PrimContext &prim);

    // Helper to determine if we should use extents hints for \p prim.
    inline bool _UseExtentsHintForPrim(UsdPrim const &prim) const;

    // Specialize TfHashAppend for TfHash
    template <typename HashState>
    friend void TfHashAppend(HashState& h, const _PrimContext &key)
    {
        h.Append(key.prim);
        h.Append(key.instanceInheritablePurpose);
    }

    // Need hash_value for boost to key cache entries by prim context.
    friend size_t hash_value(const _PrimContext &key) { return TfHash{}(key); }

    typedef TfHash _PrimContextHash;
    typedef TfHashMap<_PrimContext, _Entry, _PrimContextHash> _PrimBBoxHashMap;

    // Finds the cache entry for the prim context if it exists.
    _Entry *_FindEntry(const _PrimContext &primContext)
    {
        return TfMapLookupPtr(_bboxCache, primContext);
    }

    // Returns the cache entry for the prim context, adding it if doesn't 
    // exist.
    _Entry *_InsertEntry(const _PrimContext &primContext)
    {
        return &(_bboxCache[primContext]);
    }

    WorkDispatcher _dispatcher;
    UsdTimeCode _time;
    boost::optional<UsdTimeCode> _baseTime;
    TfTokenVector _includedPurposes;
    UsdGeomXformCache _ctmCache;
    _PrimBBoxHashMap _bboxCache;
    bool _useExtentsHint;
    bool _ignoreVisibility;
};


PXR_NAMESPACE_CLOSE_SCOPE

#endif // PXR_USD_USD_GEOM_BBOX_CACHE_H