bubblestringpullerbetweenpivots.h

Go to the documentation of this file.

/*
* Copyright 2015 Autodesk, Inc. All rights reserved.
* Use of this software is subject to the terms of the Autodesk license agreement and any attachments or Appendices thereto provided at the time of installation or download,
* or which otherwise accompanies this software in either electronic or hard copy form, or which is signed by you and accepted by Autodesk.
*/

#ifndef Navigation_BubbleStringPullerBetweenPivots_H
#define Navigation_BubbleStringPullerBetweenPivots_H

#include "gwnavruntime/channel/bubblearray.h"


namespace Kaim
{

class StringPulledBubbleList;

// Internal.
// This class computes a string pull on Bubbles that are so that the line 
class BubbleStringPullerBetweenPivots
{
private:
    // A chained-list node identifying a pivot Bubble in both a BubbleArray (globalArrayIdx)
    // and a local corner index array (localArrayIdx).
    class Pivot : public ListNode<Pivot>
    {
    public:
        Pivot(KyUInt32 globalArrayIdx, KyUInt32 localArrayIdx)
            : m_globalArrayIdx(globalArrayIdx)
            , m_localArrayIdx(localArrayIdx)
        {}

        void Set(KyUInt32 globalArrayIdx, KyUInt32 localArrayIdx)
        {
            m_globalArrayIdx = globalArrayIdx;
            m_localArrayIdx = localArrayIdx;
        }

        KyUInt32 m_globalArrayIdx;
        KyUInt32 m_localArrayIdx;
    };


    // Defines a sub set for iterative corner index array sort and local
    // string pull resolution.
    class BubbleArraySubSet
    {
    public:
        enum SubSetSide
        {
            BeforePivot = 0,
            AfterPivot
        };

        BubbleArraySubSet()
            : m_pivot(KY_NULL)
            , m_startGlobalIndex(KyUInt32MAXVAL)
            , m_endGlobalIndex(KyUInt32MAXVAL)
            , m_refBubbleGlobalIndex(KyUInt32MAXVAL)
            , m_startLocalIndex(KyUInt32MAXVAL)
            , m_endLocalIndex(KyUInt32MAXVAL)
            , m_subSetSide(BeforePivot)
        {}

        BubbleArraySubSet(const KyUInt32 startGlobalIndex, const KyUInt32 endGlobalIndex, KyUInt32 startLocalIndex, KyUInt32 endLocalIndex)
            : m_pivot(KY_NULL)
            , m_startGlobalIndex(startGlobalIndex)
            , m_endGlobalIndex(endGlobalIndex)
            , m_refBubbleGlobalIndex(endGlobalIndex)
            , m_startLocalIndex(startLocalIndex)
            , m_endLocalIndex(endLocalIndex)
            , m_subSetSide(BeforePivot)
        {}

        BubbleArraySubSet(Pivot* pivot, SubSetSide subSetSide, const KyUInt32 startGlobalIndex, const KyUInt32 endGlobalIndex, KyUInt32 startLocalIndex, KyUInt32 endLocalIndex)
            : m_pivot(pivot)
            , m_startGlobalIndex(startGlobalIndex)
            , m_endGlobalIndex(endGlobalIndex)
            , m_refBubbleGlobalIndex(endGlobalIndex)
            , m_startLocalIndex(startLocalIndex)
            , m_endLocalIndex(endLocalIndex)
            , m_subSetSide(subSetSide)
        {}

        Pivot* m_pivot;
        KyUInt32 m_startGlobalIndex;
        KyUInt32 m_endGlobalIndex;
        KyUInt32 m_refBubbleGlobalIndex;
        KyUInt32 m_startLocalIndex;
        KyUInt32 m_endLocalIndex;
        SubSetSide m_subSetSide;
    };

    class IncreasingProjectionDistance2dLessSorter
    {
    public:
        IncreasingProjectionDistance2dLessSorter(
            const BubbleArray* bubbleArray, const Vec2f& referencePosition,
            const Vec2f& referenceVector, KyUInt32 referenceEndBubbleIdx)
            : m_bubbleArray(bubbleArray)
            , m_referencePosition(referencePosition)
            , m_referenceVector(referenceVector)
            , m_referenceEndBubbleIdx(referenceEndBubbleIdx)
        {}

        KY_INLINE bool operator() (KyUInt32 firstIdx, KyUInt32 secondIdx) const
        {
            // Let m_referenceEndBubbleIdx be sorted in last position
            if (firstIdx == m_referenceEndBubbleIdx)
                return false;
            if (secondIdx == m_referenceEndBubbleIdx)
                return true;

            const Bubble& firstBubble  = m_bubbleArray->At(firstIdx);
            const Bubble& secondBubble = m_bubbleArray->At(secondIdx);

            const Vec2f vecToFirst  =  firstBubble.GetCenter().Get2d() - m_referencePosition;
            const Vec2f vecToSecond = secondBubble.GetCenter().Get2d() - m_referencePosition;

            return (DotProduct(vecToFirst, m_referenceVector) < DotProduct(vecToSecond, m_referenceVector));
        }

    private:
        const BubbleArray* m_bubbleArray;
        Vec2f m_referencePosition;
        Vec2f m_referenceVector;
        KyUInt32 m_referenceEndBubbleIdx;
    };


public:
    KyResult SolveLocalStringPulledBubbleList(const BubbleArray& bubbleArray, KyArrayPOD<KyUInt32>& cornerIndexArray,
        KyUInt32 startGlobalIndex, KyUInt32 endGlobalIndex, StringPulledBubbleList& stringPulledBubbleList);

private:
    // This function analyzes a subset of corner index array to detect a intermediary
    // pivot. It then split the current subset in two subsets around the identified pivot.
    // Note that in fact the second part of the initial subset is not created, so that the
    // first identified pivot is used as start bubble for the next main loop.
    KyResult TreatNextSubStrip(const BubbleArray& bubbleArray, KyArrayPOD<KyUInt32>& funnelCornerIndices,
        KyArray<BubbleArraySubSet>& subSets, KyArray<Pivot>& pivotArray, List<Pivot>& pivotList);
};

} // namespace Kaim

#endif // Navigation_BubbleStringPullerBetweenPivots_H