---

---

AI_NavigationMesh.h

Go to the documentation of this file.

#ifndef AI_NAVIGATION_MESH_H
#define AI_NAVIGATION_MESH_H

#include "AI_Global.h"
#include "spatialdb/AI_SDB_VisitorBase.h"
#include "spatialdb/AI_SDB_SpatialAABBTree.h"
#include "./math/AI_Line.h"
#include "AI_AStar.h"

class AI_NavigationMesh
{
public:
    class Vertex;
    class Triangle;
    class Edge;
    class Corner;
    class Session;

//*** Embedded
private:
    struct Bundle {
        Triangle *ptr_tri;
        Edge *ptr_edge;

        Bundle ();
        Bundle (Triangle *ptr_tri, Edge *ptr_edge);
    };

    typedef AI_Array<Bundle> BundleArray;
    typedef BundleArray::iterator BundleArrayIt;

    enum INTERSECTION {NO_CROSS, CROSS, CROSS_BORDER};

public:
    typedef AI_Array<Vertex*> VertexArray;
    typedef VertexArray::iterator VertexArrayIt;
    typedef AI_Array<Edge*> EdgeArray;
    typedef EdgeArray::iterator EdgeArrayIt;
    typedef AI_Array<Triangle*> TriangleArray;
    typedef TriangleArray::iterator TriangleArrayIt;
    typedef AI_Array<Corner*> CornerArray;
    typedef CornerArray::iterator CornerArrayIt;


    class Vertex {
        friend AI_NavigationMesh;
        friend Session;

    protected:
        AI_Vector3 m_v_coord;
        AI_Vector2 m_v_coord2d;
        Corner *m_ptr_corner;

    public:
        Vertex();
        const AI_Vector3 &getCoord( void ) const;
        Corner *getCorner( void ) const;
    };


    class Triangle {
        friend AI_NavigationMesh;

    protected:
        Vertex *m_ptr_vertices[3];
        Edge *m_ptr_edges[3];
        CornerArray m_arr_pvs_corners;

    public:
        Triangle ();
        bool addEdge( Edge *ptr_edge );
        void addPVS( Corner *ptr_corner );
        Edge *getEdgeOposedTo( const Vertex *ptr_vertex );
        Edge *getEdgeSharedVertex( const Vertex *ptr_vertex, const Edge *ptr_edge );
        void getOtherEdges( const Edge *ptr_edge, Edge *ptr_edges[] );
    };


    class Edge {
        friend AI_NavigationMesh;
        friend Triangle;

    protected:
        AI_Line2 m_line2d;
        Triangle *m_ptr_triangles[2];
        Vertex *m_ptr_vertex1;
        Vertex *m_ptr_vertex2;
        AI_Vector2 m_v_normal;
        void *m_ptr_user_data;

    public:
        Edge ();
        bool isBorder( void ) const;
        bool isVertexContained( const Vertex *ptr_vertex ) const;
        Triangle *getOppositeTriangle( const Triangle *ptr_triangle ) const;
    };


    class Corner {
        friend AI_NavigationMesh;
        friend Session;

    protected:
        Vertex *m_ptr_vertex;
        Edge *m_ptr_edges[2];
        AI_Vector2 m_v_shift;
        float m_f_width;
        bool m_b_concave;
        CornerArray m_arr_visible_corners;
        AI_AStar::Node *m_ptr_astar_node;

    protected:
        void addVisibleConcaveCorner( Corner *ptr_corner );
        void adjustWidth(float f);

    public:
        Corner();
        Vertex *getVertex( void );
    };


    class PointVisitor : public AI_SDB_VisibilityVisitor {
    private:
        AI_SDB_VisibilityVisitor::VisibleElements &m_visarray;

    public:
        PointVisitor(const AI_Vector3 &v_position, VisibleElements &foundarray);
        virtual AI_SDB_VisitorFlags VisibilityTest(const AI_BBox &testbox, AI_SDB_VisitorFlags flags);
        virtual AI_SDB_VisitorFlags VisibilityTest(const AI_Sphere &testsphere, AI_SDB_VisitorFlags flags);
        virtual void Visit(AI_SDB_SpatialElement *visitee);
        AI_SDB_SpatialElement *getNearestElement(void);
    };


    class Informator : public AI_AStar::Informator {
    protected:
        AI_NavigationMesh *m_ptr_navmesh;

    public:
        void setNavigationMesh ( AI_NavigationMesh *ptr_navmesh );
        virtual float getHeuristic ( AI_AStar::Node *ptr_node1, AI_AStar::Node *ptr_node2 );
    };

    enum { 
        INVALID_INDEX = 0xffff 
    };


    class Session {
        friend AI_NavigationMesh;

    protected:
        Corner m_corner_start;
        Corner m_corner_final;
        Vertex m_vertex_start;
        Vertex m_vertex_final;
        AI_AStar::Session m_session_astar;
        float m_f_width;
        bool m_b_direct_way;

    public:
        Session();
        void setMission(const AI_Vector3 &v_start, const AI_Vector3 &v_final);
        void setWidth(const float f_width);
        void getWay(AI_Array<AI_Vector3> &arr_way);

    protected:
        void reset( void );
        void resetCorner( Corner &corner );
    };

//*** Attributes
protected:
    VertexArray m_arr_vertices;
    TriangleArray m_arr_triangles;
    EdgeArray m_arr_edges;
    CornerArray m_arr_corners;
    AI_SDB_SpatialAABBTree m_spatial_tree;
    AI_SDB_VisibilityVisitor::VisibleElements m_spatial_elements;
    AI_SDB_VisibilityVisitor::VisibleElements m_visible_elements;
    AI_AStar m_astar;
    Informator m_astar_informator;
    bool m_b_preprocessed;
    bool m_b_wide_agents;

//*** Methods
private:
    bool findCorners(void);
    void findVisibleConcaveCorners(void);
    void getBundles( AI_Array< BundleArray > &arr_vert2edge );
    void adjustCornersWidth( AI_Array< EdgeArray > &arr_corner2edges );
    void buildVisibilityGraph(void);
    void buildSpatialTree(void);
    void updateLinkWidths(void);
    bool isCCW(const AI_Vector2 &v_1, const AI_Vector2 &v_2, const AI_Vector2 &v_3) const;
    float getHalfLinkMinWidth(const Corner *ptr_corner1, const Corner *ptr_corner2) const;
    float getLinkMaxWidth(const Corner *ptr_corner1, const Corner *ptr_corner2) const;
    float getStaticLinkMaxWidth(const Corner *ptr_corner1, const Corner *ptr_corner2) const;
    float getShiftToCollinearSimple(const Edge *ptr_edge, const Corner *ptr_corner) const;
    float getShiftToCollinear(const Corner *ptr_corner_a, const Corner *ptr_corner_b, const Corner *ptr_corner_c) const;
    float getShiftToCollinearStatic(const Corner *ptr_corner1, const Corner *ptr_corner2, const Corner *ptr_corner3) const;
    bool isCornerVisible(const AI_Line2 &l_ray, const Vertex *ptr_v_final, Triangle *ptr_tri_in, Edge *ptr_edges[], int i_num_edges) const;
    bool isPointVisible (const AI_Line2 &l_ray, const Triangle *ptr_tri_final, Triangle *ptr_tri_in, Edge *ptr_edges[], int i_num_edges) const;
    bool isMeaningfulLink( const Corner *ptr_corner_start, const Corner *ptr_corner_final ) const;
    bool isMeaningfulBend( const Vertex *ptr_v_start, const Corner *ptr_corner, const Vertex *ptr_v_end ) const;
    void findTemporaryVisibleCorners( Corner *ptr_corner_start, Triangle *ptr_tri );
    void addTemporarySubgraph( Corner *ptr_corner_start, AI_AStar::Session &session );
    ai_index addCorner( Edge *ptr_edge1, Edge *ptr_edge2 );
    Corner *getCorner( ai_index i ) const;
    int getCornersNumber(void) const;
    void addAStarLink (Corner *ptr_corner1, Corner *ptr_corner2);
    float getCornerWidth(const Corner *ptr_corner, const Edge *ptr_edge) const;
    float getLinkWidth(const Corner *ptr_corner_a, const Corner *ptr_corner_b, const Corner *ptr_corner_c) const;
    float getStaticLinkWidth(const Corner *ptr_corner_a, const Corner *ptr_corner_b, const Corner *ptr_corner_c) const;
    bool isOnShiftedEdge(const Corner *ptr_corner_a, const Corner *ptr_corner_b, const Corner *ptr_corner_c, const float f_k) const;

public:
    AI_NavigationMesh(void);
    ~AI_NavigationMesh(void);

    ai_index addVertex( const AI_Vector3 &v_vertex );
    ai_index addTriangle( ai_index i_v1, ai_index i_v2, ai_index i_v3 );
    ai_index addEdge( ai_index i_t1, ai_index i_t2, ai_index i_v1, ai_index i_v2 );
    Vertex *getVertex( ai_index i ) const;
    Triangle *getTriangle( ai_index i ) const;
    Edge *getEdge( ai_index i ) const;
    bool preprocess( void );
    bool findWay( Session &session );
    bool testVisibility( const AI_Vector3 &v_first, const AI_Vector3 &v_second );
    const bool testBorderIntersection( const AI_Vector3 &v_first, const AI_Vector3 &v_second, float &f_distance );
    void clear( void );
    const AI_AStar &getVisibilityGraph( void ) const;
    void setWideAgents( bool b_support = true );
    bool isWideAgents( void ) const;
    bool isPreprocessed( void ) const;
    Triangle *identifyTriangle( const AI_Vector3 &v_coord );
    bool getNearestPosition( const AI_Vector3 &v_position,float width,bool cylinder,AI_Vector3 &v_nearest_position);
};


inline
AI_NavigationMesh::Bundle::Bundle()
{
}


inline
AI_NavigationMesh::Bundle::Bundle (Triangle *ptr_tri, Edge *ptr_edge) : 
    ptr_tri(ptr_tri), 
    ptr_edge(ptr_edge)
{
}


inline
AI_NavigationMesh::Vertex::Vertex() : 
    m_ptr_corner(NULL)
{
}


inline
const AI_Vector3 &AI_NavigationMesh::Vertex::getCoord( void ) const
{
    return m_v_coord;
}


inline
AI_NavigationMesh::Corner *AI_NavigationMesh::Vertex::getCorner( void ) const
{
    return m_ptr_corner;
}


inline
AI_NavigationMesh::Triangle::Triangle ()
{
    memset (m_ptr_edges, NULL, 3*sizeof(void*));
    memset (m_ptr_vertices, NULL, 3*sizeof(void*));
}


inline
bool AI_NavigationMesh::Triangle::addEdge( Edge *ptr_edge )
{
    int i = 0;
    while (i<3)
    {
        if ( m_ptr_edges[i]==NULL )
        {   m_ptr_edges[i]=ptr_edge;  
            return true;    
        }

        i++;
    }

    ai_log (AI_STR_TOO_MANY_TRI_EDGES);
    return false;
}


inline
void AI_NavigationMesh::Triangle::addPVS( Corner *ptr_corner )
{
    for (CornerArrayIt it=m_arr_pvs_corners.Begin(); it!=m_arr_pvs_corners.End(); it++)
    {
        if (*it==ptr_corner)
        {
            return;
        }
    }

    m_arr_pvs_corners.PushBack( ptr_corner );
}


inline
AI_NavigationMesh::Edge *AI_NavigationMesh::Triangle::getEdgeOposedTo( const Vertex *ptr_vertex )
{
    for (int i=0; i<3; i++)
    {
        Edge *ptr_edge = m_ptr_edges[i];

        if ( !(ptr_edge->m_ptr_vertex1==ptr_vertex || ptr_edge->m_ptr_vertex2==ptr_vertex) )
            return ptr_edge;
    }

    return NULL;
}


inline
AI_NavigationMesh::Edge *AI_NavigationMesh::Triangle::getEdgeSharedVertex( const Vertex *ptr_vertex, const Edge *ptr_edge )
{
    for (int i=0; i<3; i++)
    {
        Edge *ptr_edge_new = m_ptr_edges[i];

        if ( ptr_edge!=ptr_edge_new && (ptr_edge_new->m_ptr_vertex1==ptr_vertex || ptr_edge_new->m_ptr_vertex2==ptr_vertex) )
            return ptr_edge_new;
    }

    return NULL;
}


inline
void AI_NavigationMesh::Triangle::getOtherEdges( const Edge *ptr_edge, Edge *ptr_edges[] )
{
    int i2=0;
    for (int i=0; i<3; i++)
    {
        Edge *ptr_edge_new = m_ptr_edges[i];

        if ( ptr_edge!=ptr_edge_new )
        {   ptr_edges[i2] = ptr_edge_new;
            i2++;
        }
    }
}


inline
AI_NavigationMesh::Edge::Edge () :
    m_ptr_vertex1(NULL),
    m_ptr_vertex2(NULL),
    m_ptr_user_data(NULL)
{
    memset(m_ptr_triangles, 0, 2*sizeof(void*));
}


inline
bool AI_NavigationMesh::Edge::isBorder ( void ) const
{
    if (m_ptr_triangles[0]==NULL || m_ptr_triangles[1]==NULL)
        return true;
    return false;
}


inline
bool AI_NavigationMesh::Edge::isVertexContained( const Vertex *ptr_vertex ) const
{
    if (ptr_vertex==m_ptr_vertex1 || ptr_vertex==m_ptr_vertex2)
        return true;
    return false;
}


inline
AI_NavigationMesh::Triangle *AI_NavigationMesh::Edge::getOppositeTriangle( const Triangle *ptr_triangle ) const
{
    if (m_ptr_triangles[0]==ptr_triangle)   
        return m_ptr_triangles[1];
    else
        return m_ptr_triangles[0];
}


inline
AI_NavigationMesh::Corner::Corner() : 
    m_f_width(AI_INFINITY), 
    m_ptr_astar_node(NULL), 
    m_b_concave(false)
{
}


inline
void AI_NavigationMesh::Corner::addVisibleConcaveCorner( Corner *ptr_corner )
{
    CornerArrayIt it;
    for (it=m_arr_visible_corners.Begin(); it!=m_arr_visible_corners.End(); it++)
    {
        if (*it==ptr_corner)
        {
            return;
        }
    }

    m_arr_visible_corners.PushBack( ptr_corner );
}


inline
void AI_NavigationMesh::Corner::adjustWidth(float f_width)
{ 
    if (f_width < m_f_width) 
    {
        m_f_width = f_width; 
    }
}


inline
AI_NavigationMesh::Vertex *AI_NavigationMesh::Corner::getVertex( void )
{
    return m_ptr_vertex;
}


inline
void AI_NavigationMesh::Informator::setNavigationMesh( AI_NavigationMesh *ptr_navmesh )
{
    m_ptr_navmesh = ptr_navmesh;
}


inline
float AI_NavigationMesh::Informator::getHeuristic ( AI_AStar::Node *ptr_node1, AI_AStar::Node *ptr_node2 )
{
    Vertex *ptr_vertex1 = ((Corner*)ptr_node1->getUserData())->getVertex();
    Vertex *ptr_vertex2 = ((Corner*)ptr_node2->getUserData())->getVertex();

    return (ptr_vertex1->getCoord() - ptr_vertex2->getCoord()).len();
}


inline
AI_NavigationMesh::Session::Session() :
    m_f_width(0),
    m_b_direct_way(false)
{
    m_corner_start.m_ptr_vertex = &m_vertex_start;
    m_corner_final.m_ptr_vertex = &m_vertex_final;
}


inline
void AI_NavigationMesh::Session::setMission(const AI_Vector3 &v_start, const AI_Vector3 &v_final)
{
    m_vertex_start.m_v_coord = v_start;
    m_vertex_final.m_v_coord = v_final;
}


inline
void AI_NavigationMesh::Session::setWidth(const float f_width)
{
    m_f_width = f_width;
}


inline
void AI_NavigationMesh::Session::reset( void )
{
    resetCorner( m_corner_start );
    resetCorner( m_corner_final );

    m_b_direct_way = false;
}


inline
void AI_NavigationMesh::Session::resetCorner( Corner &corner )
{
    corner.m_ptr_astar_node = NULL;
    corner.m_arr_visible_corners.Reset();

    corner.m_ptr_vertex->m_v_coord2d.x = corner.m_ptr_vertex->m_v_coord.x; 
    corner.m_ptr_vertex->m_v_coord2d.y = corner.m_ptr_vertex->m_v_coord.z;
}


inline
AI_NavigationMesh::Vertex *AI_NavigationMesh::getVertex( ai_index i ) const
{
    return m_arr_vertices[i];
}


inline
AI_NavigationMesh::Triangle *AI_NavigationMesh::getTriangle( ai_index i ) const
{
    return m_arr_triangles[i];
}


inline
AI_NavigationMesh::Edge *AI_NavigationMesh::getEdge( ai_index i ) const
{
    return m_arr_edges[i];
}


inline
AI_NavigationMesh::Corner *AI_NavigationMesh::getCorner( ai_index i ) const
{
    return m_arr_corners[i];
}


inline
int AI_NavigationMesh::getCornersNumber( void ) const
{
    return m_arr_corners.Size();
}


inline
AI_NavigationMesh::PointVisitor::PointVisitor(const AI_Vector3 &v_position, VisibleElements &foundarray) :
    AI_SDB_VisibilityVisitor(v_position),
    m_visarray(foundarray)
{
}


inline
AI_SDB_VisitorFlags AI_NavigationMesh::PointVisitor::VisibilityTest(const AI_BBox &testbox, AI_SDB_VisitorFlags flags)
{
    AI_Vector3 v_pos = GetViewPoint();

    if ((testbox.vmin.x < v_pos.x) && (testbox.vmax.x >= v_pos.x) &&
        (testbox.vmin.z < v_pos.z) && (testbox.vmax.z >= v_pos.z))
    {
        return AI_SDB_VisitorFlags(true,false);
    }

    return AI_SDB_VisitorFlags(false,true);
}


inline
AI_SDB_VisitorFlags AI_NavigationMesh::PointVisitor::VisibilityTest(const AI_Sphere &testsphere, AI_SDB_VisitorFlags flags)
{
    return flags;
}


inline
void AI_NavigationMesh::PointVisitor::Visit(AI_SDB_SpatialElement *visitee)
{
    m_visarray.Append( visitee );
}


inline
const AI_AStar &AI_NavigationMesh::getVisibilityGraph( void ) const
{
    return m_astar;
}


inline
void AI_NavigationMesh::setWideAgents( bool b_support )
{
    m_b_wide_agents = b_support;
}


inline
bool AI_NavigationMesh::isWideAgents( void ) const
{
    return m_b_wide_agents;
}


inline
bool AI_NavigationMesh::isPreprocessed( void ) const
{
    return m_b_preprocessed;
}


#endif

---

InExIn pages are hosted by
InExIn documentation generated by doxygen at Tue Dec 18 12:55:27 2007