polylinecastintersector.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/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_endO - m_startO, pos - m_startO); }

    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_startO;
    Vec3f m_endO;

    Vec3f m_startL;
    Vec3f m_startR;

    Vec3f m_endL;
    Vec3f m_endR;

    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;
};

}