polylinecastintersector.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.
*/


// Primary contact: JUBA - secondary contact: NOBODY
#ifndef Navigation_PolylineCastIntersector_H
#define Navigation_PolylineCastIntersector_H

#include "gwnavruntime/navmesh/identifiers/navhalfedgerawptr.h"
#include "gwnavruntime/containers/sharedpoollist.h"


namespace Kaim
{

class DatabaseGenMetrics;
class PolylineCastIntersector
{
    KY_DEFINE_NEW_DELETE_OPERATORS(MemStat_Query)

public:
    enum VolumeType { Quad, TriangleAroundRight, TriangleAroundLeft };

    class BorderEdge
    {
    public:
        BorderEdge() : m_startAxis_f(0.f), m_endAxis_f(0.f), m_startOrdinate_f(0.f), m_endOrdinate_f(0.f) {}
        void Init(KyFloat32 startAxis, KyFloat32 endAxis, KyFloat32 startOrdinate, KyFloat32 endOrdinate, const Vec3f& startPos, const Vec3f& endPos);
    public:
        KyFloat32 m_startAxis_f; // between 0 and 1
        KyFloat32 m_endAxis_f; // between 0 and 1
        KyFloat32 m_startOrdinate_f;
        KyFloat32 m_endOrdinate_f;
        Vec3f m_startPos;
        Vec3f m_endPos;
        NavHalfEdgeRawPtr m_edgeRawPtr;
    };

    PolylineCastIntersector();
    ~PolylineCastIntersector();

    void InitTrapezoid(const Vec3f& pathEdgeStartPos3f, const Vec3f& pathEdgeEndPos3f, const Vec3f& onStartLeft, const Vec3f& onEndLeft,
        const Vec3f& onStartRight, const Vec3f& onEndRight, const DatabaseGenMetrics& genMetrics);

    void InitTriangleAroundRight(const Vec3f& pathEdgeStartPos3f, const Vec3f& pathEdgeEndPos3f, const Vec3f& onStartLeft, const Vec3f& onEndLeft,
        const Vec3f& onRight, const DatabaseGenMetrics& genMetrics);

    void InitTriangleAroundLeft(const Vec3f& pathEdgeStartPos3f, const Vec3f& pathEdgeEndPos3f, const Vec3f& onLeft,
        const Vec3f& onStartRight, const Vec3f& onEndRight, const DatabaseGenMetrics& genMetrics);

    bool IsEdgeVisible(const CoordPos64& /*startEdgeCoordPos*/, const CoordPos64& /*endEdgeCoordPos*/, const NavHalfEdgeRawPtr& edgeRawPtr, bool edgeIsCrossable);

    void ComputeTriangleCost(const CoordPos64& v0CoordPos, const CoordPos64& v1CoordPos, const CoordPos64& v2CoordPos, KyFloat32& cost);

protected:

    void Init(VolumeType volumeType, KyFloat32 integerPrecision, const Vec3f& pathEdgeStartPos3f, const Vec3f& pathEdgeEndPos3f,
        const Vec3f& onStartLeft, const Vec3f& onEndLeft, const Vec3f& onStartRight, const Vec3f& onEndRight);

    bool ProcessCrossableEdge(KyFloat32 firstAxis, KyFloat32 lastAxis, const Vec3f& firstPos, const Vec3f& lastPos);
    bool ProcessNonCrossableEdge(const Vec3f& firstPos, const Vec3f& lastPos, KyFloat32 firstAxis, KyFloat32 lastAxis,
        KyFloat32 axisEdgeStart, KyFloat32 axisEdgeEnd, const NavHalfEdgeRawPtr& edgeRawPtr);

    bool BoundEdgeToBorderEdgeAxis(const Vec3f& firstPos, const Vec3f& lastPos, KyFloat32& firstAxis, KyFloat32& lastAxis, KyFloat32 borderEdgeAxisStart,
        KyFloat32 borderEdgeAxisEnd, Vec3f& startPosForThisBorder, Vec3f& endPosForThisBorder);

    bool SnapExtremityIfNeeded(const Vec3f& firstPos, const Vec3f& lastPos, bool onLeft, BorderEdge* currentBorderEdge,
         Vec3f& startPosForThisBorder, Vec3f& endPosForThisBorder, KyFloat32& snappedFirstAxis, KyFloat32& snappedLastAxis,
         KyFloat32& ordinateForStartPosForThisBorder, KyFloat32& ordinateForEndPosForThisBorder);

    bool SnappedEdgeStartToBorderStartAxis(const Vec3f& firstPos, const Vec3f& lastPos, BorderEdge* currentBorderEdge, bool onLeft, Vec3f& startPosForThisBorder,
        KyFloat32& ordinateForStartPosForThisBorder);
    bool SnappedEdgeEndToBorderEndAxis(const Vec3f& firstPos, const Vec3f& lastPos, BorderEdge* currentBorderEdge, bool onLeft,
        Vec3f& endPosForThisBorder, KyFloat32& ordinateForEndPosForThisBorder);

    bool IsVisibleForBorderLeft(const Vec3f& startPosForThisBorder, const Vec3f& endPosForThisBorder, PolylineCastIntersector::BorderEdge* borderEdgeOnLeft);
    bool IsVisibleForBorderRight(const Vec3f& startPosForThisBorder, const Vec3f& endPosForThisBorder, PolylineCastIntersector::BorderEdge* borderEdgeOnRight);

    bool DoesEdgeIntersectVolume(const Vec3f& startEdgePos, const Vec3f& endEdgePos);

    KyFloat32 GetAxisValue(const Vec3f& pos);
    KyFloat32 GetOrdinateValue(const Vec3f& pos) { return CrossProduct_z(m_pathEdgeEndPos3f-m_pathEdgeStartPos3f, pos-m_pathEdgeStartPos3f); }

    bool GetPointAtAxisOnEdgeRatio(const Vec3f& startEdgePos, const Vec3f& endEdgePos, KyFloat32 wantedAxis, KyFloat32& ratio);
    bool GetPointAtAxisOnEdge(const Vec3f& startEdgePos, const Vec3f& endEdgePos, KyFloat32 wantedAxis, Vec3f& pos);

    bool BoundEdgeToTrapezoidEdge(Vec3f& startEdgePos, Vec3f& endEdgePos, const Vec3f& trapezoidEdgeStart, const Vec3f& trapezoidEdgeEnd);
    bool BoundEdgeToTrapezoidLimit(Vec3f& startEdgePos, Vec3f& endEdgePos);

public:
    Vec3f m_pathEdgeStartPos3f;
    Vec3f m_pathEdgeEndPos3f;

    Vec3f m_startLeftPos3f;
    Vec3f m_startRightPos3f;

    Vec3f m_endLeftPos3f;
    Vec3f m_endRightPos3f;

    Vec3f m_edgeDir2D;
    Vec3f m_edgeExtentForTest;

    KyFloat32 m_ABxAC;
    KyFloat32 m_ABxCD;
    KyFloat32 m_ACxCD;
    KyFloat32 m_axisMultFactor;
    KyFloat32 m_edgeLenght2d;
    KyFloat32 m_minDistanceStep;
    KyFloat32 m_axisStepMin;
    KyFloat32 m_integerPrecision;
    KyFloat32 m_maxOrdinateOnLeft;
    KyFloat32 m_minOrdinateOnRight;

    VolumeType m_type;


    SharedPoolList<BorderEdge> m_borderEdgesOnLeft;
    SharedPoolList<BorderEdge> m_borderEdgesOnRight;
    SharedPoolList<BorderEdge>::NodePool m_borderEdgePool;
};

}

#endif //Navigation_PolylineCastIntersector_H