meshUtil.h

//
// Copyright 2017 Pixar
//
// Licensed under the terms set forth in the LICENSE.txt file available at
// https://openusd.org/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
};
 
enum class [[nodiscard]] HdMeshComputationResult
{
    Error,
    Success,
    Unchanged
};
 
 
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
    HdMeshComputationResult 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,
        std::vector<int> * firstEdgeIndexForFacesOut = nullptr) 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:
    HD_API
    explicit HdMeshEdgeIndexTable(HdMeshTopology const * topology);
    HD_API
    ~HdMeshEdgeIndexTable();
 
    HD_API
    bool GetVerticesForEdgeIndex(int edgeId, GfVec2i * edgeVerticesOut) const;
 
    HD_API
    bool GetVerticesForEdgeIndices(
        std::vector<int> const & edgeIndices,
        std::vector<GfVec2i> * edgeVerticesOut) const;
 
    HD_API
    bool GetEdgeIndices(GfVec2i const & edgeVertices,
                        std::vector<int> * edgeIndicesOut) const;
 
    HD_API
    VtIntArray CollectFaceEdgeIndices(VtIntArray const &faceIndices) 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;
        }
    };
 
    HdMeshTopology const *_topology;
    std::vector<int> _firstEdgeIndexForFaces;
 
    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