GU_QuadLayout.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 Library (C++)
 *
 */

#ifndef __GU_QuadLayout_h__
#define __GU_QuadLayout_h__

#include "GU_API.h"
#include "GU_Detail.h"

#include <GEO/GEO_HedgeInterface.h>

#include <GA/GA_Edge.h>
#include <GA/GA_EdgeGroup.h>

#include <UT/UT_Map.h>
#include <UT/UT_ParallelUtil.h>
#include <UT/UT_UniquePtr.h>
#include <UT/UT_TriangleMesh.h>


// GU_QuadLayout generates a virtual partitioning a quad mesh into its maximal
// blocks. The quad mesh here is the restriction of the input detail to its
// quads. Non-quad polygons and other tings are treated as absent.
//
// The quad layout is determined by "singular" vertices of the mesh. These are
// interior vertices of degrees other than 4 or boundary vertices of degree
// other than 2. The quads are partitioned into "blocks" by cutting the surface
// along a number of edge paths, called "separatrices". Each separatrix starts
// at a singular vertex and continues "straight" across regular vertices until
// it hits a boundary or reaches a singular vertex. Separatrices generated this
// way may cross each other at some regular vertices which will call, along
// with the singular vertices, the "nodes" of the layout. The spans of
// separatrices that run between two nodes are called the "arcs" of the layout.
// The regions left behind after cutting the surface along the separatrices are
// called the "blocks" of the layout and can be shown to all be either ordinary
// grids bounded by exactly 4 arcs, or are grids with identification(s) of
// one or both pairs of opposite sides (with their respective arcs missing)
// resulting topologies of any of cylinder or torus (or if non-orientable
// surfaces are permissible, even Möbius ring, Klein bottle, or
// the projective plane) which are considered "degenerated".


class GU_API GU_QuadLayout
{
public:
    // Construct the quad layout for the given detail and group. Non-group
    // quads will be regarded as non-existent. `separator` edges can be used
    // to specify additional cuts on the surface where the surface is otherwise
    // connected. The `poly_island` attribute can be used to additionally
    // pre-divide the geometry into a number of virtual islands (those with
    // identical attribute values) with edges between different values treated
    // as cuts. The half-edge interface `hip` is used if passed or constructed
    // internally if not.

    explicit             GU_QuadLayout(const GU_Detail *gdp,
                                const GA_PrimitiveGroup *group = nullptr,
                                const GA_EdgeGroup *separator_edges = nullptr,
                                const GA_PointGroup *forced_nodes = nullptr,
                                const GA_Attribute *poly_island = nullptr,
                                const GEO_DetachedHedgeInterface *hip
                                        = nullptr);

    enum ArcOrientation { UNASSIGNED = 0, ROW, COL };

    // Returns number of blocks of the layout.
    int                  numBlocks() const
                            { return int(myArcStart.size() / 4); }

    // Returns number of arcs of the layout. This is always 4 times the number
    // of blocks (arcs to blocks are like half-edges to polygons).
    int                  numArcs() const { return int(myArcStart.size()); }

    // Returns the block to which a polygon belongs. (Non-quads return -1).
    SYS_FORCE_INLINE
    int                  polyBlock(GA_Offset poly) const
                            { return myPolyBlock.get(poly); }


    // Returns the block to which a hedge belongs (whether along the boundary
    // or interior).
    SYS_FORCE_INLINE
    int                  hedgeBlock(GEO_Hedge h) const
                            { return polyBlock(hedgePoly(h)); }


    // Determine if a vertex offset is a singular vertex of the quad layout.
    SYS_FORCE_INLINE
    bool                 isSingular(GA_Offset vtx) const
                            { return getFlags(vtx, SINGULAR_VTX) != 0; }

    // Determine if a vertex offset is a node (singular or separatrix crossing)
    // of the quad layout.
    SYS_FORCE_INLINE
    bool                 isNode(GA_Offset vtx) const
                            { return getFlags(vtx, NODE_VTX) != 0; }

    // Determine if the given hedge lies along an arc of the quad layout.
    SYS_FORCE_INLINE
    bool                 isOnArc(GEO_Hedge h) const
                            { return getFlags(srcVertex(h), ARC_HDG) != 0; }

    // Is arc `a` (by number) valid? Note that even degenerate blocks are
    // assigned four arcs but they can be invalid arcs.
    SYS_FORCE_INLINE
    bool                 isValidArc(int a) const
                            { return a >= 0 && isValid(arcStart(a)); }

    // Is the block `b` a valid (non-degenerate) one? This is equivalent to
    // all the four arcs of it being valid. Note that being valid means that
    // the separatrices give the block a single boundary with four nodes and
    // four arcs. However, these boundary arcs can still be `sym()` to each
    // other, as long as the topology of the block itself is a proper disk.
    SYS_FORCE_INLINE
    bool                 isValidBlock(int b) const;

    // Test whether any of the four block arcs are identified with another.
    // Note that this is a stronger condition than being valid.
    SYS_FORCE_INLINE
    bool                 isFreeBlock(int b) const;

    // Returns the arc `a` (a = 0, 1, 2, or 3) of block `b`. Note that the
    // returned value can be -1 in degenerate blocks.
    SYS_FORCE_INLINE
    int                  blockArc(int b, int a = 0) const { return 4 * b + a; }

    // Returns block to which a given arc belongs.
    SYS_FORCE_INLINE
    int                  arcBlock(int a) const { return a / 4; }

    // Returns the arc sharing the same sequence of edges with `a` in the
    // neighbouring block (similar to sym() operation on half-edges).
    SYS_FORCE_INLINE
    int                  arcSym(int a) const { return myArcSym(a); }

    // Returns the next arc in the same block as `a`.
    SYS_FORCE_INLINE
    int                  arcLnext(int a) const
                            { return (a % 4 == 3) ? a - 3 : a + 1; }

    // Returns the previous arc in the same block as `a`.
    SYS_FORCE_INLINE
    int                  arcLprev(int a) const
                            { return (a % 4 == 0) ? a + 3 : a - 1; }

    // Returns the first half-edge in arc `a`.
    SYS_FORCE_INLINE
    GEO_Hedge            arcStart(int a) const { return myArcStart(a); }

    // Returns the last half-edge of arc `a`.
    SYS_FORCE_INLINE
    GEO_Hedge            arcEnd(int a) const;

    // Returns the next hedge along the arc after `h`.
    SYS_FORCE_INLINE
    GEO_Hedge            hedgeSucc(GEO_Hedge h) const
                            { return quadSucc(h, ARC_HDG); }

    using HedgeArray = UT_Array<GEO_Hedge>;

    // Traces the quad line from h. Returns the last hedge before hitting
    // a boundary, or GEO_INVALID_HEDGE if we loop back to h. If hedges
    // passed, the traversed edges are appended to hedges (not cleared).
    GEO_Hedge            trace(GEO_Hedge h, HedgeArray *hedges = nullptr) const;

    // Construct a consistent horizontal/vertical orientation for the arcs of
    // of the layout. Each arc will be assigned an orientation in UNASSIGNED,
    // ROW, COL. Note that this is pretty arbitrary and only comes up with a
    // feasible solution given the constraints.
    void                 orientArcs();

    // Returns the derived orientation for arc a.
    SYS_FORCE_INLINE
    ArcOrientation       arcOrientation(int a) const
                            { return myArcOrientation(a); }

    // Returns the index of the connected component of quad layout blocks to
    // which block `b` belongs.
    SYS_FORCE_INLINE
    int                  blockComponent(int b) const { return myBlockComp(b); }

    // Returns the number of connected components of the quad layout blocks.
    SYS_FORCE_INLINE
    int                  numBlockComponents() const
                            { return myNumBlockComponents; }

    // Runs `func` on each polygon of the block `b`.
    template <typename T>
    int                  foreachBlockPoly(int b, const T& func) const;

private:

    using HedgeInterface = GEO_DetachedHedgeInterface;
    using HedgeInterfaceUptr = UT_UniquePtr<HedgeInterface>;
    using ArcOrientationArray = UT_Array<ArcOrientation>;

    // Flags indicate for each vertex properties relative to the restriction
    // of the geometry to the quads in the given group. Some flags treat the
    // vertex as a vertex in restricted geometry (VTX) and others view it as
    // it's outgoing half-edge (HDG).

    enum VertexFlag
    {
        NONE             = 0,
        CATEGORIZED      = 1,           // determined singular or regular
        QUAD_VTX         = 1 << 1,      // vertex of a quad
        INTERIOR_VTX     = 1 << 2,      // interior vertex
        SINGULAR_VTX     = 1 << 3,      // singular (equiv. not regular)
        NODE_VTX         = 1 << 4,      // layout node (block corner)
        BOUNDARY_HDG     = 1 << 5,      // mesh boundary hedge
        ARC_HDG          = 1 << 6       // layout arc (separatrix) hedge
    };

    void                 buildArcTopology(const GA_OffsetArray &block_corners);


    SYS_FORCE_INLINE
    bool                 isValid(GEO_Hedge h) const
                            { return h != GEO_INVALID_HEDGE; }

    SYS_FORCE_INLINE
    GA_Offset            srcVertex(GEO_Hedge h) const
                            { return myHip->srcVertex(h); }

    SYS_FORCE_INLINE
    GA_Offset            srcPoint(GEO_Hedge h) const
                            { return myHip->srcPoint(h); }

    SYS_FORCE_INLINE
    GA_Offset            dstPoint(GEO_Hedge h) const
                            { return myHip->dstPoint(h); }

    SYS_FORCE_INLINE
    GEO_Hedge            lnext(GEO_Hedge h) const
                            { return myHip->lnext(h); }

    SYS_FORCE_INLINE
    GEO_Hedge            lprev(GEO_Hedge h) const
                            { return myHip->lprev(h); }

    SYS_FORCE_INLINE
    GA_Offset            vertexPoly(GA_Offset vtx) const
                            { return myGdp->vertexPrimitive(vtx); }

    SYS_FORCE_INLINE
    GA_Offset            hedgePoly(GEO_Hedge h) const
                            { return vertexPoly(srcVertex(h)); }

    SYS_FORCE_INLINE
    int                  polyIsland(GA_Offset poly) const
                            { return myPolyIsland.isValid()
                                     ? myPolyIsland.get(poly) : 0; }

    SYS_FORCE_INLINE
    int                  hedgeIsland(GEO_Hedge h) const
                            { return polyIsland(hedgePoly(h)); }

    // Local "overriding" of `sym()` to respect poly_island attribute or
    // separator edges, and to emulate the absence of non-quads.
    // Note that here we override the usual half-edge interface sym behaviour
    // of returning the half-edge itself for boundary half-edges and instead
    // return GEO_INVALID_HEDGE. Note also that if the user supplies us with
    // a half-edge interface that doesn't cover the supplied group polygons,
    // the group is implicitly overridden by the half-edge interface.
    SYS_FORCE_INLINE
    GEO_Hedge            sym(GEO_Hedge h) const
    {
        GEO_Hedge h_sym = myHip->sym(h);
        if (h_sym == h || myHip->sym(h_sym) != h)
            return GEO_INVALID_HEDGE;

        if (srcPoint(h) == srcPoint(h_sym))
            return GEO_INVALID_HEDGE;

        if (getFlags(h, BOUNDARY_HDG) || !getFlags(h_sym, QUAD_VTX))
            return GEO_INVALID_HEDGE;

        if (hedgeIsland(h) != hedgeIsland(h_sym))
            return GEO_INVALID_HEDGE;

        return h_sym;
    };

    SYS_FORCE_INLINE
    GEO_Hedge            onext(GEO_Hedge h) const { return sym(lprev(h)); }

    SYS_FORCE_INLINE
    bool                 isQuad(GA_Offset poly) const
    {
        return myGdp->getPrimitiveTypeId(poly) == GEO_PRIMPOLY
               && myGdp->getPrimitiveVertexCount(poly) == 4
               && myGdp->getPrimitiveClosedFlag(poly);
    };

    SYS_FORCE_INLINE
    GEO_Hedge            quadSucc(GEO_Hedge h, uint32 stop_mask) const;

    SYS_FORCE_INLINE
    uint32               getFlags(GA_Offset vtx) const
                            { return uint32(myVertexFlags.get(vtx)); }

    SYS_FORCE_INLINE
    uint32               getFlags(GA_Offset vtx, uint32 mask) const
                            { return (uint32(myVertexFlags.get(vtx)) & mask); }

    SYS_FORCE_INLINE
    uint32               getFlags(GEO_Hedge h, uint32 mask) const
                            { return getFlags(srcVertex(h), mask); }

    SYS_FORCE_INLINE
    void                 setFlags(GA_Offset vtx, uint32 mask) const
                            { myVertexFlags.set(vtx, getFlags(vtx) | mask); }

    SYS_FORCE_INLINE
    void                 setFlags(GEO_Hedge h, uint32 mask) const
                            { setFlags(srcVertex(h), mask); }

    SYS_FORCE_INLINE
    void                 clearFlags(GA_Offset vtx, uint32 mask) const
                            { myVertexFlags.set(vtx, getFlags(vtx) & (!mask)); }

    GA_AttributeUPtr     myVertexFlagsOwner;
    GA_AttributeUPtr     myPolyBlockOwner;
    GA_RWHandleI         myVertexFlags;
    GA_RWHandleI         myPolyBlock;
    GA_ROHandleI         myPolyIsland;

    const GU_Detail     *myGdp                                  = nullptr;

    const
    HedgeInterface      *myHip                                  = nullptr;
    HedgeInterfaceUptr   myOwnHip;

    int                  myNumBlockComponents                   = 0;
    ArcOrientationArray  myArcOrientation;
    HedgeArray           myArcStart;
    UT_IntArray          myArcSym;
    UT_IntArray          myBlockComp;
};

GEO_Hedge
GU_QuadLayout::quadSucc(GEO_Hedge h, uint32 stop_mask) const
{
    h = lnext(h);
    if (getFlags(h, stop_mask) || getFlags(h, SINGULAR_VTX))
        return GEO_INVALID_HEDGE;       // hit a blocking hedge

    h = sym(h);
    if (h == GEO_INVALID_HEDGE)
        return h;                       // hit a boundary

    return lnext(h);
}

bool
GU_QuadLayout::isValidBlock(int b) const
{
    return isValidArc(blockArc(b, 0)) && isValidArc(blockArc(b, 1))
           && isValidArc(blockArc(b, 2)) && isValidArc(blockArc(b, 3));
}

bool
GU_QuadLayout::isFreeBlock(int b) const
{
    if (!isValidBlock(b))
        return false;

    for (int i = 0; i < 4; i++)
    {
        int a_i_sym = arcSym(blockArc(b, i));
        for (int j = 0; j < 4; j++)
            if (a_i_sym == blockArc(b, j))
                return false;
    }
    return true;
}


template <typename T>
int
GU_QuadLayout::foreachBlockPoly(int b, const T& func) const
{
    UT_ASSERT_P(b >= 0 && b < numBlocks());

    auto a = blockArc(b);
    if (!isValidArc(a))
        return 0;

    HedgeArray row_hedges;
    int num_polys = 0;

    auto h0 = arcStart(a);
    while (h0 != GEO_INVALID_HEDGE)
    {
        if (hedgeBlock(h0) != b)
            break;

        row_hedges.clear();
        trace(h0, &row_hedges);
        for (auto h : row_hedges)
        {
            func(hedgePoly(h));
            num_polys++;
        }
        h0 = sym(lnext(lnext(h0)));
    }
    return num_polys;
}


#endif