scheme.h

Go to the documentation of this file.

//
//   Copyright 2014 DreamWorks Animation LLC.
//
//   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 OPENSUBDIV3_SDC_SCHEME_H
#define OPENSUBDIV3_SDC_SCHEME_H

#include "../version.h"

#include "../sdc/types.h"
#include "../sdc/options.h"
#include "../sdc/crease.h"

#include <cassert>
#include <cstdlib>
#include <vector>

namespace OpenSubdiv {
namespace OPENSUBDIV_VERSION {

namespace Sdc {

template <SchemeType SCHEME_TYPE>
class Scheme {

public:

    Scheme() : _options() { }

    Scheme(Options const& options) : _options(options) { }

    Options GetOptions() const { return _options; }
    void    SetOptions(const Options& newOptions) { _options = newOptions; }

    template <typename FACE, typename MASK>
    void ComputeFaceVertexMask(FACE const& faceNeighborhood, MASK& faceVertexMask) const;

    template <typename EDGE, typename MASK>
    void ComputeEdgeVertexMask(EDGE const& edgeNeighborhood, MASK& edgeVertexMask,
                               Crease::Rule parentRule = Crease::RULE_UNKNOWN,
                               Crease::Rule childRule = Crease::RULE_UNKNOWN) const;

    template <typename VERTEX, typename MASK>
    void ComputeVertexVertexMask(VERTEX const& vertexNeighborhood, MASK& vertexVertexMask,
                                    Crease::Rule parentRule = Crease::RULE_UNKNOWN,
                                    Crease::Rule childRule = Crease::RULE_UNKNOWN) const;

    template <typename VERTEX, typename MASK>
    void ComputeVertexLimitMask(VERTEX const& vertexNeighborhood, MASK& positionMask,
                                Crease::Rule vertexRule) const;

    template <typename VERTEX, typename MASK>
    void ComputeVertexLimitMask(VERTEX const& vertexNeighborhood, MASK& positionMask,
                                MASK& tangent1Mask, MASK& tangent2Mask,
                                Crease::Rule vertexRule) const;

    //
    //  Static methods defining traits/properties of the scheme:
    //
    static Split GetTopologicalSplitType();
    static int   GetRegularFaceSize();
    static int   GetRegularVertexValence();
    static int   GetLocalNeighborhoodSize();

protected:

    //
    //  Supporting internal methods -- optionally implemented, depending on specialization:
    //

    //  Subdivision/refinement masks -- two for edge-vertices and three for vertex-vertices:
    //
    template <typename EDGE, typename MASK>
    void assignCreaseMaskForEdge(EDGE const& edge, MASK& mask) const;
    template <typename EDGE, typename MASK>
    void assignSmoothMaskForEdge(EDGE const& edge, MASK& mask) const;

    template <typename VERTEX, typename MASK>
    void assignCornerMaskForVertex(VERTEX const& edge, MASK& mask) const;
    template <typename VERTEX, typename MASK>
    void assignCreaseMaskForVertex(VERTEX const& edge, MASK& mask, int const creaseEnds[2]) const;
    template <typename VERTEX, typename MASK>
    void assignSmoothMaskForVertex(VERTEX const& edge, MASK& mask) const;

    //
    //  Limit masks for position and tangents at vertices -- three cases for each:
    //
    template <typename VERTEX, typename MASK>
    void assignCornerLimitMask(VERTEX const& vertex, MASK& pos) const;
    template <typename VERTEX, typename MASK>
    void assignCreaseLimitMask(VERTEX const& vertex, MASK& pos, int const creaseEnds[2]) const;
    template <typename VERTEX, typename MASK>
    void assignSmoothLimitMask(VERTEX const& vertex, MASK& pos) const;

    template <typename VERTEX, typename MASK>
    void assignCornerLimitTangentMasks(VERTEX const& vertex, MASK& tan1, MASK& tan2) const;
    template <typename VERTEX, typename MASK>
    void assignCreaseLimitTangentMasks(VERTEX const& vertex, MASK& tan1, MASK& tan2, int const creaseEnds[2]) const;
    template <typename VERTEX, typename MASK>
    void assignSmoothLimitTangentMasks(VERTEX const& vertex, MASK& tan1, MASK& tan2) const;

private:
    Options _options;

protected:

    //
    //  Internal implementation support:
    //
    //  We need a local "mask" class to be declared locally within the vertex-vertex mask query
    //  to hold one of the two possible mask required and to combine the local mask with the mask
    //  the caller provides.  It has been parameterized by <WEIGHT> so that a version compatible
    //  with the callers mask class is created.
    //
    template <typename WEIGHT>
    class LocalMask {

    public:
        typedef WEIGHT Weight;

    public:
        LocalMask(Weight* v, Weight* e, Weight* f) : _vWeights(v), _eWeights(e), _fWeights(f) { }
        ~LocalMask() { }

    public:

        //
        //  Methods required for general mask assignments and queries:
        //
        int GetNumVertexWeights() const { return _vCount; }
        int GetNumEdgeWeights()   const { return _eCount; }
        int GetNumFaceWeights()   const { return _fCount; }

        void SetNumVertexWeights(int count) { _vCount = count; }
        void SetNumEdgeWeights(  int count) { _eCount = count; }
        void SetNumFaceWeights(  int count) { _fCount = count; }

        Weight const& VertexWeight(int index) const { return _vWeights[index]; }
        Weight const& EdgeWeight(  int index) const { return _eWeights[index]; }
        Weight const& FaceWeight(  int index) const { return _fWeights[index]; }

        Weight& VertexWeight(int index) { return _vWeights[index]; }
        Weight& EdgeWeight(  int index) { return _eWeights[index]; }
        Weight& FaceWeight(  int index) { return _fWeights[index]; }

        bool AreFaceWeightsForFaceCenters() const  { return _fWeightsForCenters; }
        void SetFaceWeightsForFaceCenters(bool on) { _fWeightsForCenters = on; }

    public:

        //
        //  Additional methods -- mainly the blending method for vertex-vertex masks:
        //
        template <typename USER_MASK>
        inline void
        CombineVertexVertexMasks(Weight thisCoeff, Weight dstCoeff, USER_MASK& dst) const {

            //
            //  This implementation is convoluted by the potential sparsity of each mask.  Since
            //  it is specific to a vertex-vertex mask, we are guaranteed to have exactly one
            //  vertex-weight for both masks, but the edge- and face-weights are optional.  The
            //  child mask (the "source") should have a superset of the weights of the parent
            //  (the "destination") given its reduced sharpness, so we fortunately don't need to
            //  test all permutations.
            //
            dst.VertexWeight(0) = dstCoeff * dst.VertexWeight(0) + thisCoeff * this->VertexWeight(0);

            int edgeWeightCount = this->GetNumEdgeWeights();
            if (edgeWeightCount) {
                if (dst.GetNumEdgeWeights() == 0) {
                    dst.SetNumEdgeWeights(edgeWeightCount);
                    for (int i = 0; i < edgeWeightCount; ++i) {
                        dst.EdgeWeight(i) = thisCoeff * this->EdgeWeight(i);
                    }
                } else {
                    for (int i = 0; i < edgeWeightCount; ++i) {
                        dst.EdgeWeight(i) = dstCoeff * dst.EdgeWeight(i) + thisCoeff * this->EdgeWeight(i);
                    }
                }
            }

            int faceWeightCount = this->GetNumFaceWeights();
            if (faceWeightCount) {
                //
                //  If combining face weights, be sure their interpretation (i.e. face-centers
                //  or opposite vertices) is properly set in the destination mask:
                //
                if (dst.GetNumFaceWeights() == 0) {
                    dst.SetNumFaceWeights(faceWeightCount);
                    dst.SetFaceWeightsForFaceCenters(this->AreFaceWeightsForFaceCenters());

                    for (int i = 0; i < faceWeightCount; ++i) {
                        dst.FaceWeight(i) = thisCoeff * this->FaceWeight(i);
                    }
                } else {
                    assert(this->AreFaceWeightsForFaceCenters() == dst.AreFaceWeightsForFaceCenters());

                    for (int i = 0; i < faceWeightCount; ++i) {
                        dst.FaceWeight(i) = dstCoeff * dst.FaceWeight(i) + thisCoeff * this->FaceWeight(i);
                    }
                }
            }
        }

    private:
        Weight* _vWeights;
        Weight* _eWeights;
        Weight* _fWeights;
        int _vCount;
        int _eCount;
        int _fCount;
        bool _fWeightsForCenters;
    };
};


//
//  Crease and corner masks are common to most schemes -- the rest need to be provided
//  for each Scheme specialization.
//
template <SchemeType SCHEME>
template <typename EDGE, typename MASK>
inline void
Scheme<SCHEME>::assignCreaseMaskForEdge(EDGE const&, MASK& mask) const {

    mask.SetNumVertexWeights(2);
    mask.SetNumEdgeWeights(0);
    mask.SetNumFaceWeights(0);
    mask.SetFaceWeightsForFaceCenters(false);

    mask.VertexWeight(0) = 0.5f;
    mask.VertexWeight(1) = 0.5f;
}

template <SchemeType SCHEME>
template <typename VERTEX, typename MASK>
inline void
Scheme<SCHEME>::assignCornerMaskForVertex(VERTEX const&, MASK& mask) const {

    mask.SetNumVertexWeights(1);
    mask.SetNumEdgeWeights(0);
    mask.SetNumFaceWeights(0);
    mask.SetFaceWeightsForFaceCenters(false);

    mask.VertexWeight(0) = 1.0f;
}


//
//  The computation of a face-vertex mask is trivial and consistent for all schemes:
//
template <SchemeType SCHEME>
template <typename FACE, typename MASK>
void
Scheme<SCHEME>::ComputeFaceVertexMask(FACE const& face, MASK& mask) const {

    int vertCount = face.GetNumVertices();

    mask.SetNumVertexWeights(vertCount);
    mask.SetNumEdgeWeights(0);
    mask.SetNumFaceWeights(0);
    mask.SetFaceWeightsForFaceCenters(false);

    typename MASK::Weight vWeight = 1.0f / (typename MASK::Weight) vertCount;
    for (int i = 0; i < vertCount; ++i) {
        mask.VertexWeight(i) = vWeight;
    }
}


//
//  The computation of an edge-vertex mask requires inspection of sharpness values to
//  determine if smooth or a crease, and also to detect and apply a transition from a
//  crease to smooth.  Using the protected methods to assign the specific masks (only
//  two -- smooth or crease) this implementation should serve all non-linear schemes
//  (currently Catmark and Loop) and only need to be specialized it for Bilinear to
//  trivialize it to the crease case.
//
//  The implementation here is slightly complicated by combining two scenarios into a
//  single implementation -- either the caller knows the parent and child rules and
//  provides them, or they don't and the Rules have to be determined from sharpness
//  values.  Both cases include quick return once the parent is determined to be
//  smooth or the child a crease, leaving the transitional case remaining.
//
//  The overall process is as follows:
//
//      - quickly detect the most common specified or detected Smooth case and return
//      - quickly detect a full Crease by child Rule assignment and return
//      - determine from sharpness if unspecified child is a crease -- return if so
//      - compute smooth mask for child and combine with crease from parent
//
//  Usage of the parent Rule here allows some misuse in that only three of five possible
//  assignments are legitimate for the parent and four for the child (Dart being only
//  valid for the child and Corner for neither).  Results are undefined in these cases.
//
template <SchemeType SCHEME>
template <typename EDGE, typename MASK>
void
Scheme<SCHEME>::ComputeEdgeVertexMask(EDGE const&     edge,
                                         MASK&           mask,
                                         Crease::Rule parentRule,
                                         Crease::Rule childRule) const {

    //
    //  If the parent was specified or determined to be Smooth, we can quickly return
    //  with a Smooth mask.  Otherwise the parent is a crease -- if the child was
    //  also specified to be a crease, we can quickly return with a Crease mask.
    //
    if ((parentRule == Crease::RULE_SMOOTH) ||
       ((parentRule == Crease::RULE_UNKNOWN) && (edge.GetSharpness() <= 0.0f))) {
        assignSmoothMaskForEdge(edge, mask);
        return;
    }
    if (childRule == Crease::RULE_CREASE) {
        assignCreaseMaskForEdge(edge, mask);
        return;
    }

    //
    //  We have a Crease on the parent and the child was either specified as Smooth
    //  or was not specified at all -- deal with the unspecified case first (again
    //  returning a Crease mask if the child is also determined to be a Crease) and
    //  continue if we have a transition to Smooth.
    //
    //  Note when qualifying the child that if the parent sharpness > 1.0, regardless
    //  of the creasing method, whether the child sharpness values decay to zero is
    //  irrelevant -- the fractional weight for such a case (the value of the parent
    //  sharpness) is > 1.0, and when clamped to 1 effectively yields a full crease.
    //
    if (childRule == Crease::RULE_UNKNOWN) {
        Crease crease(_options);

        bool childIsCrease = false;
        if (parentRule == Crease::RULE_CREASE) {
            //  Child unknown as default value but parent Rule specified as Crease
            childIsCrease = true;
        } else if (edge.GetSharpness() >= 1.0f) {
            //  Sharpness >= 1.0 always a crease -- see note above
            childIsCrease = true;
        } else if (crease.IsUniform()) {
            //  Sharpness < 1.0 is guaranteed to decay to 0.0 for Uniform child edges
            childIsCrease = false;
        } else {
            //  Sharpness <= 1.0 does not necessarily decay to 0.0 for both child edges...
            float cEdgeSharpness[2];
            edge.GetChildSharpnesses(crease, cEdgeSharpness);
            childIsCrease = (cEdgeSharpness[0] > 0.0f) && (cEdgeSharpness[1] > 0.0f);
        }
        if (childIsCrease) {
            assignCreaseMaskForEdge(edge, mask);
            return;
        }
    }

    //
    //  We are now left with have the Crease-to-Smooth case -- compute the Smooth mask
    //  for the child and augment it with the transitional Crease of the parent.
    //
    //  A general combination of separately assigned masks here (as done in the vertex-
    //  vertex case) is overkill -- trivially combine the 0.5f vertex coefficient for
    //  the Crease of the parent with the vertex weights and attenuate the face weights
    //  accordingly.
    //
    assignSmoothMaskForEdge(edge, mask);

    typedef typename MASK::Weight Weight;

    Weight pWeight = edge.GetSharpness();
    Weight cWeight = 1.0f - pWeight;

    mask.VertexWeight(0) = pWeight * 0.5f + cWeight * mask.VertexWeight(0);
    mask.VertexWeight(1) = pWeight * 0.5f + cWeight * mask.VertexWeight(1);

    int faceCount = mask.GetNumFaceWeights();
    for (int i = 0; i < faceCount; ++i) {
        mask.FaceWeight(i) *= cWeight;
    }
}

//
//  The computation of a vertex-vertex mask requires inspection of creasing sharpness values
//  to determine what subdivision Rules apply to the parent and its child vertex, and also to
//  detect and apply a transition between two differing Rules.  Using the protected methods to
//  assign specific masks, this implementation should serve all non-linear schemes (currently
//  Catmark and Loop) and only need to be specialized for Bilinear to remove all unnecessary
//  complexity relating to creasing, Rules, etc.
//
//  The implementation here is slightly complicated by combining two scenarios into one --
//  either the caller knows the parent and child rules and provides them, or they don't and
//  the Rules have to be determined from sharpness values.  Even when the Rules are known and
//  provided though, there are cases where the parent and child sharpness values need to be
//  identified, so accounting for the unknown Rules too is not much of an added complication.
//
//  The benefit of supporting specified Rules is that they can often often be trivially
//  determined from context (e.g. a vertex derived from a face at a previous level will always
//  be smooth) rather than more generally, and at greater cost, inspecting neighboring and
//  they are often the same for parent and child.
//
//  The overall process is as follows:
//
//      - quickly detect the most common Smooth case when specified and return
//      - determine if sharpness for parent is required and gather if so
//      - if unspecified, determine the parent rule
//      - assign mask for the parent rule -- returning if Smooth/Dart
//      - return if child rule matches parent
//      - gather sharpness for child to determine or combine child rule
//      - if unspecified, determine the child rule, returning if it matches parent
//      - assign local mask for child rule
//      - combine local child mask with the parent mask
//
//  Remember -- if the parent rule is specified but the child is not, this implies only one
//  of the two optional rules was specified and is meant to indicate there is no transition,
//  so the child rule should be assigned to be the same (wish the compiler would allow this
//  in default value assignment).
//
template <SchemeType SCHEME>
template <typename VERTEX, typename MASK>
void
Scheme<SCHEME>::ComputeVertexVertexMask(VERTEX const&   vertex,
                                           MASK&           mask,
                                           Crease::Rule pRule,
                                           Crease::Rule cRule) const {

    //  Quick assignment and return for the most common case:
    if ((pRule == Crease::RULE_SMOOTH) || (pRule == Crease::RULE_DART)) {
        assignSmoothMaskForVertex(vertex, mask);
        return;
    }
    //  If unspecified, assign the child rule to match the parent rule if specified:
    if ((cRule == Crease::RULE_UNKNOWN) && (pRule != Crease::RULE_UNKNOWN)) {
        cRule = pRule;
    }
    int valence = vertex.GetNumEdges();

    //
    //  Determine if we need the parent edge sharpness values -- identify/gather if so
    //  and use it to compute the parent rule if unspecified:
    //
    float * pEdgeSharpnessBuffer = (float *)alloca(valence*sizeof(float)),
          * pEdgeSharpness   = 0,
            pVertexSharpness = 0.0f;

    bool requireParentSharpness = (pRule == Crease::RULE_UNKNOWN) ||
                                  (pRule == Crease::RULE_CREASE) ||
                                  (pRule != cRule);
    if (requireParentSharpness) {
        pVertexSharpness = vertex.GetSharpness();
        pEdgeSharpness   = vertex.GetSharpnessPerEdge(pEdgeSharpnessBuffer);

        if (pRule == Crease::RULE_UNKNOWN) {
            pRule = Crease(_options).DetermineVertexVertexRule(pVertexSharpness, valence, pEdgeSharpness);
        }
    }
    if ((pRule == Crease::RULE_SMOOTH) || (pRule == Crease::RULE_DART)) {
        assignSmoothMaskForVertex(vertex, mask);
        return;  //  As done on entry, we can return immediately if parent is Smooth/Dart
    } else if (pRule == Crease::RULE_CREASE) {
        int creaseEnds[2];
        Crease(_options).GetSharpEdgePairOfCrease(pEdgeSharpness, valence, creaseEnds);

        assignCreaseMaskForVertex(vertex, mask, creaseEnds);
    } else {
        assignCornerMaskForVertex(vertex, mask);
    }
    if (cRule == pRule) return;

    //
    //  Identify/gather child sharpness to combine masks for the two differing Rules:
    //
    Crease crease(_options);

    float * cEdgeSharpnessBuffer = (float *)alloca(valence*sizeof(float)),
          * cEdgeSharpness = vertex.GetChildSharpnessPerEdge(crease, cEdgeSharpnessBuffer),
            cVertexSharpness = vertex.GetChildSharpness(crease);

    if (cRule == Crease::RULE_UNKNOWN) {
        cRule = crease.DetermineVertexVertexRule(cVertexSharpness, valence, cEdgeSharpness);
        if (cRule == pRule) return;
    }

    //
    //  Intialize a local child mask, compute the fractional weight from parent and child
    //  sharpness values and combine the two masks:
    //
    typedef typename MASK::Weight Weight;

    Weight * cMaskWeights = (Weight *)alloca((1 + 2 * valence)*sizeof(Weight));
    LocalMask<Weight> cMask(cMaskWeights, cMaskWeights + 1, cMaskWeights + 1 + valence);

    if ((cRule == Crease::RULE_SMOOTH) || (cRule == Crease::RULE_DART)) {
        assignSmoothMaskForVertex(vertex, cMask);
    } else if (cRule == Crease::RULE_CREASE) {
        int creaseEnds[2];
        Crease(_options).GetSharpEdgePairOfCrease(cEdgeSharpness, valence, creaseEnds);

        assignCreaseMaskForVertex(vertex, cMask, creaseEnds);
    } else {
        assignCornerMaskForVertex(vertex, cMask);
    }

    Weight pWeight = crease.ComputeFractionalWeightAtVertex(pVertexSharpness, cVertexSharpness,
                                                   valence, pEdgeSharpness, cEdgeSharpness);
    Weight cWeight = 1.0f - pWeight;

    cMask.CombineVertexVertexMasks(cWeight, pWeight, mask);
}

//
//  The computation of limit masks for vertices:
//
template <SchemeType SCHEME>
template <typename VERTEX, typename MASK>
void
Scheme<SCHEME>::ComputeVertexLimitMask(VERTEX const& vertex,
                                       MASK&         mask,
                                       Crease::Rule  rule) const {

    if ((rule == Crease::RULE_SMOOTH) || (rule == Crease::RULE_DART)) {
        assignSmoothLimitMask(vertex, mask);
    } else if (rule == Crease::RULE_CREASE) {
        float * edgeSharpness = (float *)alloca(vertex.GetNumEdges() * sizeof(float));
        vertex.GetSharpnessPerEdge(edgeSharpness);

        int creaseEnds[2];
        Crease(_options).GetSharpEdgePairOfCrease(edgeSharpness, vertex.GetNumEdges(), creaseEnds);

        assignCreaseLimitMask(vertex, mask, creaseEnds);
    } else {
        assignCornerLimitMask(vertex, mask);
    }
}

template <SchemeType SCHEME>
template <typename VERTEX, typename MASK>
void
Scheme<SCHEME>::ComputeVertexLimitMask(VERTEX const& vertex,
                                       MASK&         posMask,
                                       MASK&         tan1Mask,
                                       MASK&         tan2Mask,
                                       Crease::Rule  rule) const {

    if ((rule == Crease::RULE_SMOOTH) || (rule == Crease::RULE_DART)) {
        assignSmoothLimitMask(vertex, posMask);
        assignSmoothLimitTangentMasks(vertex, tan1Mask, tan2Mask);
    } else if (rule == Crease::RULE_CREASE) {
        float * edgeSharpness = (float *)alloca(vertex.GetNumEdges() * sizeof(float));
        vertex.GetSharpnessPerEdge(edgeSharpness);

        int creaseEnds[2];
        Crease(_options).GetSharpEdgePairOfCrease(edgeSharpness, vertex.GetNumEdges(), creaseEnds);

        assignCreaseLimitMask(vertex, posMask, creaseEnds);
        assignCreaseLimitTangentMasks(vertex, tan1Mask, tan2Mask, creaseEnds);
    } else {
        assignCornerLimitMask(vertex, posMask);
        assignCornerLimitTangentMasks(vertex, tan1Mask, tan2Mask);
    }
}


} // end namespace sdc

} // end namespace OPENSUBDIV_VERSION
using namespace OPENSUBDIV_VERSION;
} // end namespace OpenSubdiv

#endif /* OPENSUBDIV3_SDC_SCHEME_H */