GU_Decompose.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * NAME:        GU_Decompose.h (GU Library, C++)
 *
 * COMMENTS:
 *
 */


#ifndef __GU_Decompose_h__
#define __GU_Decompose_h__

#include "GU_API.h"
#include <GEO/GEO_HedgeInterface.h>
#include <GA/GA_Edge.h>
#include <UT/UT_Classifier.h>
#include <UT/UT_Map.h>
#include <UT/UT_Set.h>
#include <GA/GA_Handle.h>
#include <SYS/SYS_Types.h>

class GU_Detail;
class GA_Group;
class GA_VertexGroup;
class GA_EdgeGroup;
class GA_PrimitiveGroup;
class GA_PointGroup;

// "Decompositions" are break-down of the elements of a polygon sub-detail
// into pieces which allow efficient querying of each piece.
//
// The supported types of decompositions are:
//
// PolyPatches: Decomposition of a (subset of a) polygon geometry into maximal
// manifold "patches". Each patch will have 0 or more "boundaries" each
// consisting of a cycle of edges. The boundaries of a component will be
// ordered in decreasing total length (in 3D).
//
// EdgePaths: Decomposition of an edge group (or a set of half-edges) into
// maximal chains (1-manifolds) which meet at endpoints or are closed.
//
// EulerPaths: decomposition of an edge group (or a set of half-edges) into
// "Euler paths": viewed as walls over the surface, each Euler path will the
// sequence of half-edges which correspond to a traversal of the walls starting
// from some point and always maintaining the wall on one's left. Maximal Euler
// paths can be open if they run into boundary points.

namespace GU_Decomposition
{

using HedgeInterface = const GEO_DetachedHedgeInterface;
using HedgeArray = UT_Array<GEO_Hedge>;
using BoolArray = UT_Array<bool>;

template <typename T>
struct PtrRange
{
                         PtrRange(const T *s, const T *e) :
                                 myStart(s), myEnd(e) { }

    SYS_FORCE_INLINE
    const T             *begin() const { return myStart; }

    SYS_FORCE_INLINE
    const T             *end() const { return myEnd; }

    SYS_FORCE_INLINE
    exint                size() const { return exint(myEnd - myStart); }

    SYS_FORCE_INLINE
    const T             &first() const
                            { UT_ASSERT_P(size() > 0); return *myStart; }

    SYS_FORCE_INLINE
    const T             &last() const
                            { UT_ASSERT_P(size() > 0); return *(myEnd - 1); }
private:
    const T              *myStart, *myEnd;
};


class GU_API PolyPatches
{
public:
                         PolyPatches(const GU_Detail *gdp,
                                const GA_PrimitiveGroup *polys,
                                const GA_EdgeGroup *split_edges = nullptr,
                                bool split_all = false,
                                HedgeInterface *hip = nullptr,
                                bool sort_patches = true);

                        ~PolyPatches() = default;

    /// Returns the number of maximal manifold components (patches).
    int                  numPatches() const
                            { return int(myPatchEnd.size()); }

    // Returns the total number of boundary chains (all closed cycles) in all
    // patches. Note that some patches may have no boundary chains
    // and others may have multiple.
    int                  numBoundaries() const
                            { return int(myBoundaryStart.size()) - 1; }

    // Returns the number of boundaries of a given patch.
    int                  numPatchBoundaries(int p) const
                            { return myPatchFirstBoundary(p + 1)
                                        - myPatchFirstBoundary(p); }

    // Returns patch to which the b-th boundary belongs. Boundaries of the
    // same patch get consecutive indices and within the same patch they
    // are sorted in decreasing order of total (3D) length.
    //
    // TODO: This is a bad choice for ordering since it makes the structure
    //       dependent on geometry as opposed to topology alone. We should
    //       order boundaries by edge-count instead.
    int                  boundaryPatch(int b) const
                            { return myBoundaryPatch(b); }

    // Returns total number of polygons in all patches.
    int                  numPolys() const
                            { return int(myPatchPolys.size()); }

    // Returns total number of boundary hedges over all boundaries.
    int                  numBoundaryHedges() const
                            { return int(myBoundaryHedges.size()); }


    PtrRange<GA_Offset>  patchPolys(int p) const
                            { return { myPatchPolys.data()
                                                + (p ? myPatchEnd(p - 1) : 0),
                                       myPatchPolys.data() + myPatchEnd(p) }; }

    PtrRange<GEO_Hedge>  boundaryHedges(int b) const
                            { return { myBoundaryHedges.data()
                                               + myBoundaryStart(b),
                                       myBoundaryHedges.data()
                                               + myBoundaryStart(b + 1) }; }

    PtrRange<GEO_Hedge>  patchBoundaryHedges(int p, int b) const
                            { return boundaryHedges(myPatchFirstBoundary(p)
                                                            + b); }

private:
    using SubIndexMap = UT_Map<GA_Offset, int>;
    using OffsetSet = UT_Set<GA_Offset>;

    int                  polyIndex(GA_Offset poly,
                                const SubIndexMap &poly_index_map) const;

    int                  extractPatches(HedgeInterface *hip,
                                        const GA_PrimitiveGroup *polys,
                                const GA_EdgeGroup *split_edges,
                                bool split_all,
                                bool sort_patches);

    void                 extractPatchBoundaries(HedgeInterface *hip,
                                const OffsetSet &bd_src_vtxs);

    // List of polygons ordered by belonging to same patch.
    GA_OffsetArray       myPatchPolys;

    // Index of the end of the patch polygons in myPatchPolys.
    UT_IntArray          myPatchEnd;

    // Mapping from patches to their first boundary.
    UT_IntArray          myPatchFirstBoundary;

    // List of boundary half-edges ordered by belonging to same patch boundary.
    HedgeArray           myBoundaryHedges;

    // Index of the first boundary half-edge in myBoundaryHedges.
    UT_IntArray          myBoundaryStart;

    // Mapping boundaries to patches to which they belongs.
    UT_IntArray          myBoundaryPatch;
};

class GU_API EdgePaths
{
public:

                         EdgePaths(const GU_Detail *gdp,
                                const GA_EdgeGroup *edges,
                                const GA_PointGroup *split_pts = nullptr,
                                bool split_all = false,
                                HedgeInterface *hip = nullptr);

                         EdgePaths(const GU_Detail *gdp,
                                const GA_VertexGroup *hedges,
                                const GA_PointGroup *split_pts = nullptr,
                                bool split_all = false,
                                HedgeInterface *hip = nullptr);

                        ~EdgePaths() = default;

    int                  numPaths() const
                            { return int(myPathStarts.size()) - 1; }

    bool                 isClosed(int path) const
                            { return myPathClosed(path); }

    // Returns the total number of points in all paths combined.
    int                  numPathPoints() const
                            { return int(myPathPoints.size()); }

    PtrRange<GA_Offset>  pathPoints(int path) const
                            { return { myPathPoints.data()
                                               + myPathStarts(path),
                                       myPathPoints.data()
                                               + myPathStarts(path + 1) }; }
private:
    using EdgeArray = UT_Array<GA_Edge>;

    void                         extractPaths(HedgeInterface *hip,
                                const EdgeArray &edges,
                                const GA_PointGroup *split_pts,
                                bool split_all);

    void                 reversePath(int i);

    // the points in a path will be point offsets in the geometry. When they
    // represent Euler paths, they will be vertex offsets of the source
    // vertices of the path half-edges.
    GA_OffsetArray       myPathPoints;

    // Index of the first point of each path in myPathPoints.
    UT_IntArray          myPathStarts;

    // Flag indicating whether each path is closed.
    BoolArray            myPathClosed;

};

class GU_API EulerPaths
{
public:

                         EulerPaths(const GU_Detail *gdp,
                                const GA_EdgeGroup *edges,
                                HedgeInterface *hip = nullptr);

                         EulerPaths(const GU_Detail *gdp,
                                const GA_VertexGroup *hedge_srcs,
                                HedgeInterface *hip = nullptr);

                        ~EulerPaths() = default;

    int                  numPaths() const
                            { return int(myPathStarts.size()) - 1; }

    bool                 isClosed(int path) const
                            { return myPathClosed(path); }

    // Returns the total number of half-edges in all paths combined.
    int                  numPathHedges() const
                            { return int(myPathHedges.size()); }

    PtrRange<GEO_Hedge>  pathHedges(int path) const
                            { return { myPathHedges.data() + myPathStarts(path),
                                       myPathHedges.data()
                                               + myPathStarts(path + 1) }; }

    // Move a closed path starting position `shift` entries forward around
    // the loop.
    void                 shiftPath(int path, int shift);

private:
    void                 extractPaths(HedgeInterface *hip,
                                const HedgeArray &group_hedges);

    HedgeArray           myPathHedges;

    // Index of the first point of each path in myPathPoints.
    UT_IntArray          myPathStarts;

    // Flag indicating whether each path is closed.
    BoolArray            myPathClosed;

};

} // namespace GU_Decomposition
#endif