meshUtil.h

//
// Copyright 2017 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_IMAGING_HD_MESH_UTIL_H
#define PXR_IMAGING_HD_MESH_UTIL_H

#include "pxr/pxr.h"
#include "pxr/imaging/hd/api.h"
#include "pxr/imaging/hd/version.h"
#include "pxr/imaging/hd/types.h"
#include "pxr/imaging/hd/meshTopology.h"

#include "pxr/usd/sdf/path.h"

#include "pxr/base/gf/vec2i.h"
#include "pxr/base/gf/vec3i.h"
#include "pxr/base/gf/vec4i.h"

#include "pxr/base/vt/array.h"
#include "pxr/base/vt/value.h"

PXR_NAMESPACE_OPEN_SCOPE


// v0           v2
// +-----e2----+
//  \    |    /
//   \ __c__ /
//   e0     e1
//     \   /
//      \ /
//       + v1
//
//
//  original points       additional center and edge points
// +------------ ... ----+--------------------------------+
// | v0 v1 v2         vn | e0 e1 e2 c0, e3 e4 e5 c1 ...   |
// +------------ ... ----+--------------------------------+
//                       ^
//                   pointsOffset
//                       <----- numAdditionalPoints  ---->

struct HdQuadInfo {
    HdQuadInfo() : pointsOffset(0), numAdditionalPoints(0), maxNumVert(0) { }

    bool IsAllQuads() const { return numAdditionalPoints == 0; }

    int pointsOffset;
    int numAdditionalPoints;
    int maxNumVert;
    std::vector<int> numVerts;  // num vertices of non-quads
    std::vector<int> verts;     // vertex indices of non-quads
};


class HdMeshUtil
{
public:
    HdMeshUtil(HdMeshTopology const* topology, SdfPath const& id)
        : _topology(topology), _id(id) {}
    virtual ~HdMeshUtil() {}

    // --------------------------------------------------------------------
    /*
                 +--------+-------+
                /| \      |\      |\
               / |  \  1  | \  2  | \
              /  |   \    |  \    |  \
             /   |    \   |   \   | 2 +
            / 0  |  1  \  | 2  \  |  /
           /     |      \ |     \ | /
          /      |       \|      \|/
         +-------+--------+-------+
    */

    HD_API
    void ComputeTriangleIndices(VtVec3iArray *indices,
                                VtIntArray *primitiveParams,
                                VtIntArray *edgeIndices = nullptr) const;

    HD_API
    bool ComputeTriangulatedFaceVaryingPrimvar(void const* source,
                                               int numElements,
                                               HdType dataType,
                                               VtValue *triangulated) const;


    // --------------------------------------------------------------------

    /*
               +--------+-------+
              /|        |    |   \
             / |        |  2 | 2 /\
            /  |        |     \ /  \
           / 0 |    1   |------+  2 +
          /\  /|        |     / \  /
         /  \/ |        |  2 | 2 \/
        / 0 | 0|        |    |   /
       +-------+--------+-------+
    */

    HD_API
    void ComputeQuadInfo(HdQuadInfo* quadInfo) const;

    HD_API
    void ComputeQuadIndices(VtIntArray *indices,
                            VtIntArray *primitiveParams,
                            VtVec2iArray *edgeIndices = nullptr) const;

    HD_API
    void ComputeTriQuadIndices(VtIntArray *indices,
                               VtIntArray *primitiveParams,
                               VtVec2iArray *edgeIndices = nullptr) const;

    HD_API
    bool ComputeQuadrangulatedPrimvar(HdQuadInfo const* qi,
                                      void const* source,
                                      int numElements,
                                      HdType dataType,
                                      VtValue *quadrangulated) const;

    HD_API
    bool ComputeQuadrangulatedFaceVaryingPrimvar(void const* source,
                                                 int numElements,
                                                 HdType dataType,
                                                 VtValue *quadrangulated) const;


    HD_API
    void EnumerateEdges(std::vector<GfVec2i> * edgeVerticesOut) const;

    // --------------------------------------------------------------------

    // Per-primitive coarse-face-param encoding/decoding functions
    static int EncodeCoarseFaceParam(int faceIndex, int edgeFlag) {
        return ((faceIndex << 2) | (edgeFlag & 3));
    }
    static int DecodeFaceIndexFromCoarseFaceParam(int coarseFaceParam) {
        return (coarseFaceParam >> 2);
    }
    static int DecodeEdgeFlagFromCoarseFaceParam(int coarseFaceParam) {
        return (coarseFaceParam & 3);
    }


private:
    int _ComputeNumQuads(VtIntArray const &numVerts,
                         VtIntArray const &holeIndices,
                         bool *invalidFaceFound = nullptr) const;

    void _ComputeQuadIndices(
                            VtIntArray *indices,
                            VtIntArray *primitiveParams,
                            VtVec2iArray *edgeIndices,
                            bool triangulate = false) const;

    HdMeshTopology const* _topology;
    SdfPath const _id;
};

class HdMeshEdgeIndexTable
{
public:
    explicit HdMeshEdgeIndexTable(HdMeshTopology const * topology);
    ~HdMeshEdgeIndexTable();

    bool GetVerticesForEdgeIndex(int edgeId, GfVec2i * edgeVerticesOut) const;

    bool GetVerticesForEdgeIndices(
        std::vector<int> const & edgeIndices,
        std::vector<GfVec2i> * edgeVerticesOut) const;

    bool GetEdgeIndices(GfVec2i const & edgeVertices,
                        std::vector<int> * edgeIndicesOut) const;

private:
    struct _Edge{
        _Edge(GfVec2i const & verts_ = GfVec2i(-1), int index_ = -1)
            : verts(verts_)
            , index(index_)
        {
            // Simplify sorting and searching by keeping the vertices ordered.
            if (verts[0] > verts[1]) {
                std::swap(verts[0], verts[1]);
            }
        }
        GfVec2i verts;
        int index;

    };

    struct _CompareEdgeVertices {
        bool operator() (_Edge const &lhs, _Edge const & rhs) const {
            return (lhs.verts[0] < rhs.verts[0] ||
                    (lhs.verts[0] == rhs.verts[0] &&
                     lhs.verts[1] < rhs.verts[1]));
        }
    };

    struct _EdgeVerticesHash {
        // Use a custom hash so that edges (a,b) and (b,a) are equivalent
        inline size_t operator()(GfVec2i const& v) const {
            // Triangular numbers for 2-d hash.
            int theMin = v[0], theMax = v[1];
            if (theMin > theMax) {
                std::swap(theMin, theMax);
            }
            size_t x = theMin;
            size_t y = x + theMax;
            return x + (y * (y + 1)) / 2;
        }
    };

    std::vector<GfVec2i> _edgeVertices;
    std::vector<_Edge> _edgesByIndex;
};

class HdMeshTriQuadBuilder
{
public:
    static int const NumIndicesPerQuad = 4;
    static int const NumIndicesPerTriQuad = 6;

    HdMeshTriQuadBuilder(int * indicesBuffer, bool triangulate)
        : _outputPtr(indicesBuffer)
        , _triangulate(triangulate)
        { }

    void EmitQuadFace(GfVec4i const & quadIndices) {
        if (_triangulate) {
            *_outputPtr++ = quadIndices[0];
            *_outputPtr++ = quadIndices[1];
            *_outputPtr++ = quadIndices[2];
            *_outputPtr++ = quadIndices[2];
            *_outputPtr++ = quadIndices[3];
            *_outputPtr++ = quadIndices[0];
        } else {
            *_outputPtr++ = quadIndices[0];
            *_outputPtr++ = quadIndices[1];
            *_outputPtr++ = quadIndices[2];
            *_outputPtr++ = quadIndices[3];
        }
    }

private:
    int * _outputPtr;
    bool const _triangulate;
};


PXR_NAMESPACE_CLOSE_SCOPE

#endif // PXR_IMAGING_HD_MESH_UTIL_H