GU_PathFinder.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_PathFinder.h
 *
 * COMMENTS:
 *      Finds paths of various specifications between various element types
 *      in polygon meshes.
 */

#ifndef __GU_PathFinder__
#define __GU_PathFinder__

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

#include <GA/GA_Types.h>
#include <SYS/SYS_Math.h>
#include <GEO/GEO_HedgeInterface.h>
#include <GA/GA_DataBitArray.h>
#include <GA/GA_Group.h>
#include <GA/GA_ElementGroup.h>
#include <GA/GA_EdgeGroup.h>
#include <UT/UT_PriorityQueue.h>
#include <UT/UT_Set.h>
#include <UT/UT_Map.h>
#include <UT/UT_Array.h>
#include <UT/UT_BitArray.h>

class gu_ShortestPathCost;

using GU_SHedgeArray = UT_Array<GU_PathSHedge>;


class GU_EdgeSuccessor
{
public:
    enum Type
    {
        QUAD_LEFT = 0,
        QUAD_RIGHT,
        QUAD_OPPOSITE,
        OPPOSITE,
        BOUNDARY,
        ANY,
        NUM_TYPES = ANY
    };

    enum Mask
    {
        ANY_MASK                = 0,
        QUAD_LEFT_MASK          = 1 << QUAD_LEFT,
        QUAD_RIGHT_MASK         = 1 << QUAD_RIGHT,
        QUAD_OPPOSITE_MASK      = 1 << QUAD_OPPOSITE,
        OPPOSITE_MASK           = 1 << OPPOSITE,
        BOUNDARY_MASK           = 1 << BOUNDARY
    };

                         GU_EdgeSuccessor() { clear(); }

    GU_PathSHedge               &operator()(int i) { return mySucc[i]; }
    GU_PathSHedge                operator()(int i) const { return mySucc[i]; }

    static
    Mask                 typeMask(Type t)
                            { return t < NUM_TYPES ? Mask(1 << t) : ANY_MASK; }

    void clear()
    {
        for (int i = 0; i < NUM_TYPES; ++i)
            mySucc[i] = GU_PathSHedge();
    }

private:
    GU_PathSHedge                mySucc[NUM_TYPES];
};

// Template parameter T is the cost class

template <class T = gu_ShortestPathCost>
class GU_API GU_PathFinder
{
public:

    class PathEdge
    {
    public:
        PathEdge() : mySHedge(GU_PathSHedge()), myPrev(GU_PathSHedge())
        { }

        explicit
        PathEdge(GU_PathSHedge sh,
                  GU_PathSHedge prev = GU_PathSHedge()) :
             mySHedge(sh), myPrev(prev) { myPathCost.zero(); }

        PathEdge(GU_PathSHedge sh, GU_PathSHedge prev, const T &cost) :
             mySHedge(sh), myPrev(prev), myPathCost(cost) { }

        bool             operator()(PathEdge &p1, PathEdge &p2) const
                                { return (p1.myPathCost > p2.myPathCost); }

        T                getPathCost() { return myPathCost; }
        GU_PathSHedge    getSHedge() { return mySHedge; }
        GU_PathSHedge    getPrev() { return myPrev; }
        bool             hasPrev() { return myPrev.isValid(); }

    private:
        GU_PathSHedge    mySHedge, myPrev;
        T                myPathCost;
    };

    using CostType = T;

public:

    // If the uv_attrib parameter is passed, then the search takes place
    // in UV space (boundaries, connectivity, etc follow the UVs).

    explicit             GU_PathFinder(GU_PathHedge::Interface *dhip,
                                const GA_Attribute *uv_attrib = nullptr);

    // Paths are formed of *signed* half-edges, where the sign indicates
    // whether the half-edge is being travelled from source to destination
    // (positive) or the other way around (negative). Dual paths are sequences
    // of edges (represented by half-edges) which are typically separated by
    // polygons but may share endpoints. In specifying the start and end
    // targets for path search, we used signed half-edges to indicate the
    // direction of departure or arrival at the start or end edges
    // respectively. In the dual path search, we only use positive half-edges
    // since all that we care about are the start and end edges. Note that
    // a search can specify multiple start and end (signed) half-edges. This
    // is particularly used in implementing primitive, point, and vertex loops.

    // Set a start or ending half-edge for the next search. If and_equiv
    // is set to true, then all equivalent half-edges to the given one are
    // also added as possible start or end half-edges. Note that any generated
    // path should follow the direction of one of these starting half-edges.
    void                 setStartHedge(const GU_PathHedge& sh, bool and_equiv = true);
    void                 setEndHedge(const GU_PathHedge& eh, bool and_equiv = true);

    // Set a start or end *signed* half-edge. Specifying the start or end
    // half-edge this way can be used to free us from the actual direction of
    // existing half-edges, particularly when the intended direction may not
    // be realized by any half-edges, mostly notably in case of boundaries when
    // we have a single half-edge. If and_reverse is set to true, the half-edge
    // is added in both directions.
    void                 setStartSHedge(const GU_PathSHedge& ssh,
                                  bool and_reverse = false);
    void                 setEndSHedge(const GU_PathSHedge& ssh,
                                  bool and_reverse = false);

    // Specify the search start and end by points. These get translated to
    // appropriate half-edges.
    void                 setStartPoint(GA_Offset pt);
    void                 setEndPoint(GA_Offset pt);

    // Specify the search start and end by vertices. These get translated to
    // appropriate half-edges. Note that vertex path returns "representative"
    // vertices between the two ends which are themselves treated as
    // representatives of their respective points (or their respective island
    // points if there's an active UV attribute).

    void                 setStartVertex(GA_Offset vtx);
    void                 setEndVertex(GA_Offset vtx);

    // Set start and end primitives. These get translated to appropriate
    // half-edges.
    void                 setStartPrimitive(GA_Offset prim);
    void                 setEndPrimitive(GA_Offset prim);


    void                 clearStartSHedges();
    void                 addStartSHedge(const GU_PathSHedge& sh,
                                  bool and_reverse = false);

    void                 clearEndSHedges();
    void                 addEndSHedge(const GU_PathSHedge& sh, bool and_reverse = false);

    // The main method to search for a the shortest path between a start
    // signed half edge and an end one. The successor type mask allows
    // to prioritize various types of successors and change the cost values
    // and is utilized by the template parameter cost class.
    T                    findPath(GU_SHedgeArray &path,
                                  GU_EdgeSuccessor::Mask succ_type);

    // Find a dual path between a source and a destination half-edge.
    T                    findDualPath(GU_SHedgeArray &path,
                                  GU_EdgeSuccessor::Mask succ_type);


    // Assign a group of points to be avoided by search paths.
    void                 avoidPoints(GA_PointGroup *grp)
                                { myAvoidPoints = grp; }

    // Assign a group of edges to be avoided by search paths.
    void                 avoidEdges(GA_EdgeGroup *grp)
                                { myAvoidEdges = grp; }

    // Assign a group of primitives to be avoided by search paths.
    void                 avoidPrimitives(GA_PrimitiveGroup *grp)
                                { myAvoidPrimitives = grp; }

    // Assign a group of vertices to be avoided by search paths.
    void                 avoidVertices(GA_VertexGroup *grp)
                                { myAvoidVertices = grp; }


    void                 avoidGroups(GA_PointGroup * ptgrp,
                                     GA_EdgeGroup * edgegrp,
                                     GA_VertexGroup *vtxgrp,
                                     GA_PrimitiveGroup *primgrp)
    {
        if (ptgrp && ptgrp->entries())
            avoidPoints(ptgrp);

        if (edgegrp && edgegrp->entries())
            avoidEdges(edgegrp);

        if (vtxgrp && vtxgrp->entries())
            avoidVertices(vtxgrp);

        if (primgrp && primgrp->entries())
            avoidPrimitives(primgrp);
    };

    void                resetAvoidGroups()
    {
        avoidPoints(nullptr);
        avoidEdges(nullptr);
        avoidPrimitives(nullptr);
        avoidVertices(nullptr);
    }

    void                setCollisionGroup(const GA_Group * group, bool exclude, bool strong)
    {
        myCollisionPoints = nullptr;
        myCollisionPrimitives = nullptr;
        myCollisionVertices = nullptr;
        myCollisionEdges = nullptr;
        myCollisionGroup = group;
        myExcludeCollisionGroup = exclude;
        myCollisionStrong = strong;
        if (!group)
            return;

        switch (group->classType())
        {
            case GA_GROUP_POINT:
                myCollisionPoints = static_cast<const GA_PointGroup *>(group);
                break;
            case GA_GROUP_PRIMITIVE:
                myCollisionPrimitives = static_cast<const GA_PrimitiveGroup *>(group);
                break;
            case GA_GROUP_VERTEX:
                myCollisionVertices = static_cast<const GA_VertexGroup *>(group);
                break;
            case GA_GROUP_EDGE:
                myCollisionEdges = static_cast<const GA_EdgeGroup *>(group);
                break;
            default:
                break;
        }
    }

    // Reset partial search results. This clears the start and end elements,
    // unless heap_only is set to true in which case only the partial search
    // tree is cleared.
    void                 reset(bool heap_only = false);

    const
    GU_SHedgeArray      &getStartSHedges() const
                                { return myStartSHedges; }

    SYS_FORCE_INLINE
    T                   &getBestCost(const GU_PathSHedge & sh);

    // Bypass cycles in the path or dual path.
    void                 simplifyPath(GU_SHedgeArray &path);
    void                 simplifyDualPath(GU_SHedgeArray &path);

    // Extend an open path on both ends by walking straight at regular
    // quad junctions until the two ends meet or irregular points are reached.
    // Returns true if the path changes and false otherwise.
    bool                 extendPath(GU_SHedgeArray &path,
                                bool trim_crossing = true);

    // Extend an open dual path on both ends by walk over opposite quad edges
    // until a closed edge ring is formed or a non-quad is reached.
    bool                 extendDualPath(GU_SHedgeArray &path,
                                bool trim_crossing = true,
                                bool is_for_prim_loo = false);

    // Determine whether the start or end edges are boundary edges. When a
    // UV attribute is given, this is determined with regard to that.

    bool                 isStartOnBoundary() { return myStartOnBoundary; }
    bool                 isEndOnBoundary() { return myEndOnBoundary; }

private:

    void                 dumpSHedge(const GU_PathSHedge & sh) const;

    SYS_FORCE_INLINE
    void                 mark(const GU_PathSHedge & sh);

    SYS_FORCE_INLINE
    bool                 isMarked(const GU_PathSHedge & sh);

    void                 initializeEdgeHeap();

    SYS_FORCE_INLINE
    void                 setBestCost(const GU_PathSHedge& sh, const T &cost,
                                GU_PathSHedge prev_sh = GU_PathSHedge());

    SYS_FORCE_INLINE
    GU_PathSHedge                getPrev(const GU_PathSHedge & sh);

    SYS_FORCE_INLINE
    bool                 hasPrev(const GU_PathSHedge & sh)
                            { return myDhip->isValidHedge(getPrev(sh).hedge()); }

    // Search for the destination point of the first signed half-edge in the
    // path that matches pt and truncates the rest of the path. Returns true
    // if the point is found or false otherwise.
    bool                 trimPathAtPoint(GU_SHedgeArray &path, GA_Offset pt);

    // Search for a half-edge in the path incident to a primitive and truncates
    // the rest of the path after that half-edge. Returns true if the primitive
    // is found.
    bool                 trimDualPathAtPrimitive(GU_SHedgeArray &path,
                                const GU_PathHedge & h);

    GA_Offset            trimCrossingPaths(GU_SHedgeArray &w0,
                                GU_SHedgeArray &w1);

    GA_Offset            trimCrossingDualPaths(GU_SHedgeArray &w0,
                                GU_SHedgeArray &w1);


    // fills path with signed hedges from the optimal path found from a start
    // signed hedge to esh.
    void                 extractPath(const GU_PathSHedge & esh, GU_SHedgeArray &path);
    void                 extractDualPath(const GU_PathSHedge &esh, GU_SHedgeArray &path);

    bool                 isStartSHedge(const GU_PathSHedge & sh);
    bool                 isStartSHedgePrimary(const GU_PathSHedge &sh);

    bool                 isEndSHedge(const GU_PathSHedge & sh);
    bool                 isEndSHedgePrimary(const GU_PathSHedge & sh);

    GU_PathSHedge                findMarkedEndSHedge();
    GU_PathSHedge                findMarkedEndSHedgePrimary();

    // Some signed hedge helper methods

    GU_PathSHedge                primary(const GU_PathSHedge &sh) const;
    bool                 isPrimary(const GU_PathSHedge &sh) const;

    // Returns the right sign for h to have pt as it source.
    SYS_FORCE_INLINE
    int                  relativeSign(const GU_PathHedge & h, GA_Offset pt) const
                            { return pt == myDhip->srcPoint(h) ? 1 : -1; }


    SYS_FORCE_INLINE
    GA_Edge              gaEdge(const GU_PathHedge & h) const
                            { return GA_Edge(myDhip->srcPoint(h),
                                             myDhip->dstPoint(h)); }

    SYS_FORCE_INLINE
    GA_Edge              gaEdge(const GU_PathSHedge & sh) const;

    using EdgeHeap = UT_PriorityQueue<PathEdge, PathEdge, false>;
    using HedgeInterface = GU_PathHedge::Interface;
    using SuccessorMask = GU_EdgeSuccessor::Mask;

    //const
    GU_PathHedge::Interface     *myDhip;

    const GA_Detail     *myGdp;
    GA_ROHandleV2        myUV;

    //These are very costly, may want to find some other way
    UT_Set<GU_PathHedge> myPosMarked, myNegMarked;
    UT_Map<GU_PathHedge, GU_PathSHedge> myPosPrev, myNegPrev;
    UT_Map<GU_PathHedge, T> myPosCost, myNegCost;

    //Versions for polygons as an optimization
    UT_BitArray myPolyPosMarked, myPolyNegMarked;
    UT_Array<GU_PathSHedge> myPolyPosPrev, myPolyNegPrev;
    UT_Array<T> myPolyPosCost, myPolyNegCost;

    EdgeHeap             myEdgeHeap;

    GU_SHedgeArray       myStartSHedges;
    GU_SHedgeArray       myStartSHedgePrimaries;
    GU_SHedgeArray       myEndSHedges;
    GU_SHedgeArray       myEndSHedgePrimaries;

    GU_PathSHedge        myLastStartSHedge              = GU_PathSHedge();
    bool                 myLastStartSHedgeFlag          = false;

    GU_PathHedge         myLastStartHedge               = GU_PathHedge();
    bool                 myLastStartHedgeFlag           = false;

    bool                 myStartOnBoundary              = false;
    bool                 myEndOnBoundary                = false;

    GA_Offset            myLastStartPoint               = GA_INVALID_OFFSET;
    GA_Offset            myLastStartPrimitive           = GA_INVALID_OFFSET;
    GA_Offset            myLastStartVertex              = GA_INVALID_OFFSET;


    GA_EdgeGroup        *myAvoidEdges                   = nullptr;
    GA_PointGroup       *myAvoidPoints                  = nullptr;
    GA_PrimitiveGroup   *myAvoidPrimitives              = nullptr;
    GA_VertexGroup      *myAvoidVertices                = nullptr;

    //keep a pointer to each collision group type as an optimization
    const GA_EdgeGroup          *myCollisionEdges               = nullptr;
    const GA_PointGroup         *myCollisionPoints              = nullptr;
    const GA_PrimitiveGroup     *myCollisionPrimitives          = nullptr;
    const GA_VertexGroup        *myCollisionVertices            = nullptr;
    //should be the same pointer as the non-null one above
    const GA_Group              * myCollisionGroup              = nullptr;

    //when true will NOT allow paths containing collision group
    //when false will constrain paths to collision group
    bool                        myExcludeCollisionGroup = true; 

    //when true will NOT allow paths along boundar
    //when false will allow paths to partially contain collision group
    bool                        myCollisionStrong       = false;

    SuccessorMask        mySuccessorTypeMask;
};

class gu_ShortestPathCost
{
public:
                         gu_ShortestPathCost() = default;
    explicit             gu_ShortestPathCost(fpreal l) : myLength(l) { }

                         gu_ShortestPathCost(const GU_PathSHedge & sh,
                                GU_PathHedge::Interface *dhip)
                            { myLength = dhip->length(sh.hedge()); }

                         gu_ShortestPathCost(const gu_ShortestPathCost &c)
                                 = default;

    SYS_FORCE_INLINE
    void                 zero() { myLength = 0.0; }

    SYS_FORCE_INLINE
    void                 unset() { myLength = -1.0; }

    SYS_FORCE_INLINE
    bool                 isSet() { return myLength > -0.5; }

    SYS_FORCE_INLINE
    bool                 operator>(const gu_ShortestPathCost &c) const
                            { return myLength > c.myLength; }

    SYS_FORCE_INLINE
    gu_ShortestPathCost &operator=(const gu_ShortestPathCost &c) = default;

    SYS_FORCE_INLINE
    const
    gu_ShortestPathCost &operator+=(const gu_ShortestPathCost &c)
    {
        myLength += c.myLength;
        return *this;
    }

    SYS_FORCE_INLINE
    static
    gu_ShortestPathCost  turnCost(GU_PathHedge::Interface *dhip,
                                const GU_PathSHedge & from_sh, 
                                const GU_PathSHedge & to_sh,
                                const GU_EdgeSuccessor &exits)
    {
        return gu_ShortestPathCost(dhip->length(to_sh.hedge()));
    }

    SYS_FORCE_INLINE
    fpreal               getLength() { return myLength; }

private:
    fpreal               myLength                       = -1.0;
};

class gu_EdgeLoopCost
{
public:
                         gu_EdgeLoopCost() = default;
                         gu_EdgeLoopCost(const GU_PathSHedge & sh,
                                         GU_PathHedge::Interface *dhip) :
                                 myPenalty(0),
                                 myPathLength(dhip->length(sh.hedge())) { }

                         gu_EdgeLoopCost(fpreal len, int bends) :
                                myPathLength(len), myPenalty(bends) { }

                         gu_EdgeLoopCost(const gu_EdgeLoopCost &c) :
                                myPathLength(c.myPathLength),
                                myPenalty(c.myPenalty) { }

    SYS_FORCE_INLINE
    void                 zero()
    {
        myPathLength = 0.0;
        myPenalty = 0;
    }

    SYS_FORCE_INLINE
    void                 unset() { myPathLength = -1.0; }

    SYS_FORCE_INLINE
    bool                 isSet() { return myPathLength > -0.5; }

    SYS_FORCE_INLINE
    bool                 operator>(const gu_EdgeLoopCost &c) const
    {
        if (myPenalty != c.myPenalty)
            return myPenalty > c.myPenalty;

        return myPathLength > c.myPathLength;
    }

    gu_EdgeLoopCost     &operator=(const gu_EdgeLoopCost &c) = default;

    SYS_FORCE_INLINE
    const
    gu_EdgeLoopCost     &operator+=(const gu_EdgeLoopCost &c)
    {
        myPenalty += c.myPenalty;
        myPathLength += c.myPathLength;
        return *this;
    }

    SYS_FORCE_INLINE
    static
    gu_EdgeLoopCost      turnCost(GU_PathHedge::Interface *dhip,
                                  const GU_PathSHedge & from_sh, 
                                  const GU_PathSHedge & to_sh,
                                  const GU_EdgeSuccessor &successors)
    {
        fpreal len = dhip->length(to_sh.hedge());

        GU_PathSHedge bd_succ = successors(GU_EdgeSuccessor::BOUNDARY);
        if (bd_succ.isValid() && dhip->areEquivalent(to_sh, bd_succ))
            return gu_EdgeLoopCost(len, 0);

        GU_PathSHedge sided_quad_succ = successors(GU_EdgeSuccessor::QUAD_LEFT);
        if (!sided_quad_succ.isValid())
            sided_quad_succ = successors(GU_EdgeSuccessor::QUAD_RIGHT);

        GU_PathSHedge opposite = successors(GU_EdgeSuccessor::QUAD_OPPOSITE);
        if (!opposite.isValid())
            opposite = successors(GU_EdgeSuccessor::OPPOSITE);

        bool to_sided_quad_succ = (sided_quad_succ.isValid() &&
            dhip->areEquivalent(to_sh, sided_quad_succ));

        bool to_opposite = opposite.isValid() &&
            dhip->areEquivalent(to_sh, opposite);

        if (to_sided_quad_succ)
            return gu_EdgeLoopCost(len, 1);

        if (to_opposite)
            return gu_EdgeLoopCost(len, 99);

        return gu_EdgeLoopCost(len, 100);
    }

    SYS_FORCE_INLINE
    fpreal               getLength() { return myPathLength; }

private:
    fpreal               myPathLength                   = -1.0;
    int                  myPenalty                      = -1;
};



class gu_EdgeRingCost
{
public:
                         gu_EdgeRingCost() = default;
                         gu_EdgeRingCost(const GU_PathSHedge &sh,
                                         GU_PathHedge::Interface *dhip) :
                                 myPenalty(0),
                                 myPathLength(dhip->length(sh.hedge())) { }

                         gu_EdgeRingCost(fpreal len, int bends) :
                                 myPathLength(len), myPenalty(bends) { }


                         gu_EdgeRingCost(const gu_EdgeRingCost &c) = default;

    SYS_FORCE_INLINE
    void                 zero()
    {
        myPathLength = 0.0;
        myPenalty = 0;
    }

    SYS_FORCE_INLINE
    void                 unset() { myPathLength = -1.0; }

    SYS_FORCE_INLINE
    bool                 isSet() { return myPathLength > -0.5; }

    SYS_FORCE_INLINE
    bool                 operator>(const gu_EdgeRingCost &c) const
    {
        if (myPenalty != c.myPenalty)
            return myPenalty > c.myPenalty;

        return myPathLength > c.myPathLength;
    }

    gu_EdgeRingCost     &operator=(const gu_EdgeRingCost &c) = default;

    SYS_FORCE_INLINE
    const
    gu_EdgeRingCost     &operator+=(const gu_EdgeRingCost &c)
    {
        myPenalty += c.myPenalty;
        myPathLength += c.myPathLength;
        return *this;
    }

    SYS_FORCE_INLINE
    static
    gu_EdgeRingCost      turnCost(GU_PathHedge::Interface *dhip,
                                  const GU_PathSHedge& from_sh,
                                  const GU_PathSHedge& to_sh,
                                  const GU_EdgeSuccessor &successors)
    {
        fpreal len = dhip->length(to_sh.hedge());

        GU_PathSHedge bd_succ = successors(GU_EdgeSuccessor::BOUNDARY);
        bool to_bd_succ = bd_succ.isValid() &&
            dhip->areEquivalent(to_sh, bd_succ);

        if (to_bd_succ)
            return gu_EdgeRingCost(len, 0);

        GU_PathSHedge sided_quad_succ = successors(GU_EdgeSuccessor::QUAD_LEFT);
        if (!sided_quad_succ.isValid())
            sided_quad_succ = successors(GU_EdgeSuccessor::QUAD_RIGHT);

        GU_PathSHedge opposite = successors(GU_EdgeSuccessor::QUAD_OPPOSITE);
        if (!opposite.isValid())
            opposite = successors(GU_EdgeSuccessor::OPPOSITE);

        bool to_sided_quad_succ = (sided_quad_succ.isValid() &&
            dhip->areEquivalent(to_sh, sided_quad_succ));

        bool to_opposite = opposite.isValid() &&
            dhip->areEquivalent(to_sh, opposite);

        if (to_sided_quad_succ)
            return gu_EdgeRingCost(len, 1);

        if (to_opposite)
            return gu_EdgeRingCost(len, 99);

        return gu_EdgeRingCost(len, 100);
    }

    SYS_FORCE_INLINE
    fpreal               getLength() { return myPathLength; }

private:
    fpreal               myPathLength                   = -1.0;
    int                  myPenalty                      = -1;
};


// Marking of signed half-edges: Each half-edge in each orientation is
// given a flag which can be set or checked.

template <class T>
void
GU_PathFinder<T>::mark(const GU_PathSHedge & sh)
{
    if (myDhip->isHedgeValidPolygon(sh.hedge()))
    {
        if (sh.isPositive())
            myPolyPosMarked.setBitFast(sh.hedge().v0(), true);
        else
            myPolyNegMarked.setBitFast(sh.hedge().v0(), true);
    }
    else
    {
        if (sh.isPositive())
            myPosMarked.insert(sh.hedge());
        else
            myNegMarked.insert(sh.hedge());
    }
}

template <class T>
bool
GU_PathFinder<T>::isMarked(const GU_PathSHedge & sh)
{
    if (myDhip->isHedgeValidPolygon(sh.hedge()))
    {
        if (sh.isPositive())
            return myPolyPosMarked.getBitFast(sh.hedge().v0());
        else
            return myPolyNegMarked.getBitFast(sh.hedge().v0());
    }
    else
    {
        if (sh.isPositive())
            return myPosMarked.contains(sh.hedge());
        else
            return myNegMarked.contains(sh.hedge());
    }
}

template <class T>
void
GU_PathFinder<T>::setBestCost(const GU_PathSHedge & sh, 
                              const T &cost,
                              GU_PathSHedge prev_sh)
{
    if (myDhip->isHedgeValidPolygon(sh.hedge()))
    {
        if (sh.isPositive())
        {
            myPolyPosCost[sh.hedge().v0()] = cost;
            myPolyPosPrev[sh.hedge().v0()] = prev_sh;
        }
        else
        {
            myPolyNegCost[sh.hedge().v0()] = cost;
            myPolyNegPrev[sh.hedge().v0()] = prev_sh;
        }
    }
    else
    {
        if (sh.isPositive())
        {
            myPosCost[sh.hedge()] = cost;
            myPosPrev[sh.hedge()] = prev_sh;
        }
        else
        {
            myNegCost[sh.hedge()] = cost;
            myNegPrev[sh.hedge()] = prev_sh;
        }
    }
}

template <class T>
T &
GU_PathFinder<T>::getBestCost(const GU_PathSHedge & sh)
{
    if (myDhip->isHedgeValidPolygon(sh.hedge()))
    {
        if (sh.isPositive())
            return myPolyPosCost[sh.hedge().v0()];
        else
            return myPolyNegCost[sh.hedge().v0()];
    }
    else
    {
        if (sh.isPositive())
            return myPosCost[sh.hedge()];
        else
            return myNegCost[sh.hedge()];
    }
}


template <class T>
GU_PathSHedge
GU_PathFinder<T>::getPrev(const GU_PathSHedge & sh)
{
    if (myDhip->isHedgeValidPolygon(sh.hedge()))
    {
        if (sh.isPositive())
            return myPolyPosPrev[sh.hedge().v0()];
        else
            return myPolyNegPrev[sh.hedge().v0()];
    }
    else
    {
        if (sh.isPositive())
            return myPosPrev[sh.hedge()];
        else
            return myNegPrev[sh.hedge()];
    }
}


template <class T>
GA_Edge
GU_PathFinder<T>::gaEdge(const GU_PathSHedge & sh) const
{
    return sh.isNegative() ?
        GA_Edge(myDhip->dstPoint(sh.hedge()), myDhip->srcPoint(sh.hedge())) :
        GA_Edge(myDhip->srcPoint(sh.hedge()), myDhip->dstPoint(sh.hedge()));
}



typedef GU_PathFinder<gu_EdgeLoopCost>  GU_EdgeLoopFinder;
typedef GU_PathFinder<gu_EdgeRingCost>  GU_EdgeRingFinder;

enum GU_WalkEndReason
{
    GU_NO_SUCCESSOR,            // No viable successors to take
    GU_HIT_BOUNDARY,            // Reached a boundary
    GU_HIT_SELF,                // Crossed itself
    GU_COMPLETED                // Closed the path
};

GU_WalkEndReason GU_API  guEdgeWalk(GU_PathHedge::Interface *dhip,
                                const GA_ROHandleV2 &uvh,
                                GU_SHedgeArray &path,
                                GU_SHedgeArray &walk,
                                bool backward = false,
                                bool no_self_intersection = false,
                                bool include_ends = false,
                                const GA_PrimitiveGroup * avoid_prims = nullptr,
                                const GA_PointGroup * avoid_points = nullptr,
                                const GA_VertexGroup * avoid_vtx = nullptr,
                                const GA_EdgeGroup * avoid_edges = nullptr,
                                const GA_Group * collision_group = nullptr,
                                bool exclude_collision = true,
                                bool strong_rule = true);

GU_WalkEndReason GU_API  guDualEdgeWalk(GU_PathHedge::Interface *dhip,
                                const GA_ROHandleV2 &uvh,
                                GU_SHedgeArray &path,
                                GU_SHedgeArray &walk,
                                bool backward = false,
                                bool no_self_intersection = false,
                                bool include_ends = false,
                                const GA_PrimitiveGroup * avoid_prims = nullptr,
                                const GA_PointGroup * avoid_points = nullptr,
                                const GA_VertexGroup * avoid_vtx = nullptr,
                                const GA_EdgeGroup * avoid_edges = nullptr,
                                const GA_Group * collision_group = nullptr,
                                bool exclude_collision = true,
                                bool strong_rule = true);

#endif