channelbordersimplifier.h

Go to the documentation of this file.

/*
* Copyright 2016 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.
*/

#pragma once

#include "gwnavruntime/channel/channel.h"
#include "gwnavruntime/containers/kyarray.h"
#include "gwnavruntime/containers/sharedpoollist.h"
#include "gwnavruntime/math/vec3f.h"
#include "gwnavruntime/queries/utils/polylinecasthelper.h"
#include "gwnavruntime/channel/channelcomputerconfig.h"
#include "gwnavruntime/queries/fulldebug.h"

namespace Kaim
{

class ChannelComputerConfig;
class DisplayList;

class PolylineExtremityContext
{
public:
    PolylineExtremityContext()
      : m_useStartAsInput(false), m_useEndAsInput(false), m_startCanBeMoved(false), m_endCanBeMoved(false), m_startX(0.0), m_startY(0.0), m_endX(0.0), m_endY(0.0)
    {}

    Vec2f m_startPos;
    Vec2f m_endPos;
    bool m_useStartAsInput;
    bool m_useEndAsInput;
    bool m_startCanBeMoved;
    bool m_endCanBeMoved;

    KyFloat32 m_startX;
    KyFloat32 m_startY;
    KyFloat32 m_endX;
    KyFloat32 m_endY;
};

class ChannelBorderSimplifier
{
public:
    ChannelBorderSimplifier();
    ~ChannelBorderSimplifier();

    void Clear();
    void InitializeForSection(Database* database, const ChannelComputerConfig& channelConfig, const Vec3f& edgeStartPos, const Vec2f& pathEdgeDir2d, KyFloat32 pathEdgeLength, const FullDebug& fullDebug);
    void InitializeForChannelPrePost(Database* database, const ChannelComputerConfig& channelConfig, const Vec3f& edgeStartPos, const Vec2f& pathEdgeDir2d, KyFloat32 pathEdgeLength, const FullDebug& fullDebug);

    KyResult Simplify_Left(const SharedPoolList<PolylineCastIntersector::BorderEdge>& leftBorders, PolylineExtremityContext& extremityContext);
    KyResult Simplify_Right(const SharedPoolList<PolylineCastIntersector::BorderEdge>& rightBorders, PolylineExtremityContext& extremityContext);
    KyResult Simplify(const SharedPoolList<PolylineCastIntersector::BorderEdge>& borders, bool onLeft, PolylineExtremityContext& extremityContext);
    void ProcessExtremity(SharedPoolList<Vec2f>& polyline, PolylineExtremityContext& extremityContext);

    Vec3f GetGlobalPosFromLocalPos(const Vec2f& localPos) { return m_edgeStartPos + Vec3f(localPos.x * m_edgeDir2d + localPos.y * m_edgeDir2d.PerpCCW()); }
    Vec3f GetGlobalPosFromLocalPos(KyFloat32 x, KyFloat32 y) { return GetGlobalPosFromLocalPos(Vec2f(x, y)); }

public: // internal
    void RemoveNoiseInPolyline(SharedPoolList<Vec2f>& polyline);

    void CreatePolylineFromBorder(const SharedPoolList<PolylineCastIntersector::BorderEdge>& borderEdgeList,
        SharedPoolList<Vec2f>& borderPolyline);

    // converts in place the Vec2f coordinates from global coords to EdgeLocal coords
    //                  Y
    //                + ^                   +
    //                 \|                  /
    //   m_edgeStartPos +----> X          + m_edgeEndPos
    //                   \               /
    //                    +             +
    KyResult ConvertPolylineToEdgeLocalCoords(SharedPoolList<Vec2f>& polyline);

    void FixXCoordinatesOrder(SharedPoolList<Vec2f>& polyline);
    void MoveYPositionOfAllPoints(SharedPoolList<Vec2f>& polyline);

    void FixPolylineAroundStartPoint(SharedPoolList<Vec2f>& polyline, KyFloat32& xCoordinate, KyFloat32& yCoordinate, bool canMovePoint);
    void FixPolylineAroundEndPoint(SharedPoolList<Vec2f>& polyline, KyFloat32& xCoordinate, KyFloat32& yCoordinate, bool canMovePoint);

    // ----------- Visual Debug ---------------

    void RenderBorderEdges(const char* listName, Color visualColor, const SharedPoolList<PolylineCastIntersector::BorderEdge>& leftBorders);
    void RenderPolyline(const char* listName, Color visualColor, SharedPoolList<Vec2f>& polyline, bool hideByDefault = true);

private:
    void ComputeMaxTangent(KyFloat32 angleInDegrees);
    void EraseCurrentPoint(SharedPoolList<Vec2f>& polyline, SPL_Iterator<Vec2f>& previous, SPL_Iterator<Vec2f>& current, SPL_Iterator<Vec2f>& next);

    KyFloat32 GetChannelRadius()              { return m_channelConfig.m_channelRadius; }
    KyFloat32 GetMin2dDistanceBetweenPoints() { return m_channelConfig.m_advancedConfig.m_minDistBetweenIntermediaryGates; }
    KyFloat32 GetMax2dDistanceBetweenPoints() { return m_channelConfig.m_advancedConfig.m_maxDistBetweenIntermediaryGates; }

public: // internal
    Database* m_database;
    ChannelComputerConfig m_channelConfig;
    bool m_hasFullDebug;
    KyFloat32 m_maxTangent;

    SharedPoolList<Vec2f> m_leftPolyline;
    SharedPoolList<Vec2f> m_rightPolyline;
    SharedPoolList<Vec2f>::NodePool m_positionPool;
    KyFloat32 m_nonNullMinY;

    Vec3f m_edgeStartPos;
    Vec2f m_edgeDir2d;
    KyFloat32 m_edgeLength2d;
};


class SweepLinePolylineSimplifier
{
public:
    SweepLinePolylineSimplifier(KyFloat32 maxY, KyFloat32 maxSlope, KyFloat32 minProjDistBetweenPoint);
    ~SweepLinePolylineSimplifier() { Clear(); }

    void Clear();

    KyResult Simplify(SharedPoolList<Vec2f>& polyline);

    static bool CompVec2fY(const Vec2f& p0, const Vec2f& p1) { return (p0.y < p1.y) || (p0.y == p1.y && p0.x < p1.x); }

    static bool IsAbsSlope1StrictlyGreaterThanAbsSlope2(const Vec2f& slope1, const Vec2f& slope2) { return (fabsf(slope1.y * slope2.x) > fabsf(slope1.x * slope2.y)); }

private:
    KyResult ConsumeInputPolyline(const SharedPoolList<Vec2f>& inPolyline);
    KyResult SimplifyPolyline();
    KyResult BuildOutput(SharedPoolList<Vec2f>& polyline);

    SPL_Iterator<Vec2f> GetAndPopPointToProcess();

    KyResult SimplifyAfterPolylinePoint(SPL_Iterator<Vec2f> pointIt);
    KyResult SimplifyBeforePolylinePoint(SPL_Iterator<Vec2f> pointIt);

    Vec2f GetMaxSlopeForPoint(const Vec2f &point);

    SPL_Iterator<Vec2f> ComputeFirstPointIteratorAfterLine(SPL_Iterator<Vec2f> firstPointItToCheck, const Vec2f& lineStartPoint, const Vec2f& lineSlope);
    SPL_Iterator<Vec2f> ComputeFirstPointIteratorBeforeLine(SPL_Iterator<Vec2f> firstPointItToCheck, const Vec2f& lineStartPoint, const Vec2f& lineSlope);

    SPL_Iterator<Vec2f> GetMoreConstraintSlopeForward(const Vec2f& point, SPL_Iterator<Vec2f> currentIt);
    SPL_Iterator<Vec2f> GetMoreConstraintSlopeBackward(const Vec2f& point, SPL_Iterator<Vec2f> currentIt);

    void RemoveFromWorkingPolyline(SPL_Iterator<Vec2f> firstIteratorToRemove, SPL_Iterator<Vec2f> stopAtThis);

public:
    SharedPoolList<Vec2f> m_workingPolyline;
    SharedPoolList<Vec2f>::NodePool m_pointPool;

    KyArrayCPP<SPL_Iterator<Vec2f> > m_openNodes;

    Vec2f m_maxSlope;
    KyFloat32 m_minX;
    KyFloat32 m_maxX;
    KyFloat32 m_maxY;
    KyFloat32 m_minY;
    KyFloat32 m_minProjDistBetweenPoints;

    Vec3f m_origin;
    Vec2f m_yAxis;
};


KY_INLINE KyResult ChannelBorderSimplifier::Simplify_Left(const SharedPoolList<PolylineCastIntersector::BorderEdge>& leftBorders, PolylineExtremityContext& extremityContext)
{
    return Simplify(leftBorders, true, extremityContext);
}
KY_INLINE KyResult ChannelBorderSimplifier::Simplify_Right(const SharedPoolList<PolylineCastIntersector::BorderEdge>& rightBorders, PolylineExtremityContext& extremityContext)
{
    return Simplify(rightBorders, false, extremityContext);
}

} // namespace Kaim