gwnavruntime/queries/utils/bestfirstsearch2dbordercollector.h Source File

bestfirstsearch2dbordercollector.h
Go to the documentation of this file.
1 /*
2 * Copyright 2015 Autodesk, Inc. All rights reserved.
3 * 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,
4 * or which otherwise accompanies this software in either electronic or hard copy form, or which is signed by you and accepted by Autodesk.
5 */
6 
7 
8 
9 
10 
11 // Primary contact: JUBA - secondary contact: NOBODY
12 #ifndef Navigation_BestFirstSearch2dBorderCollector_H
13 #define Navigation_BestFirstSearch2dBorderCollector_H
14 
16 
17 namespace Kaim
18 {
19 
20 /*
21 class BestFirstSearch2dBorderCollector
22 
23 EdgeIntersector must have the following functions :
24 
25  bool DoesIntersectEdge(const Vec3f& startEdgePos, const Vec3f& endEdgePos);
26 
27  void ComputeCollisionPosOnEdge(const Vec3f& startEdgePos, const Vec3f& endEdgePos, Vec3f& collisionPos, KyFloat32& squareDistToCollisionPos)
28 
29  void ComputeTriangleCost(const Vec3f& v0, const Vec3f& v1, const Vec3f& v2, KyFloat32& cost)
30 
31 */
32 template<class TraverseLogic, class EdgeIntersector>
33 class BestFirstSearch2dBorderCollector
34 {
35  KY_DEFINE_NEW_DELETE_OPERATORS(MemStat_Query)
36 
37 public:
38  BestFirstSearch2dBorderCollector(void* traverseLogicUserData, EdgeIntersector& edgeIntersector);
39 
40  bool IsSearchFinished();
41 
42  bool ShouldVisitNeighborTriangle(const NavTriangleRawPtr& triangleRawPtr, KyUInt32 indexOfNeighborTriangle);
43  bool ShouldVisitTriangle(const NavTriangleRawPtr& triangleRawPtr);
44  void ComputeTriangleCost(const NavTriangleRawPtr& triangleRawPtr, KyFloat32& cost);
45 
46  NavTriangleRawPtr GetNeighborTriangle(const NavTriangleRawPtr& triangleRawPtr, KyUInt32 indexOfNeighborTriangle);
47 
48  void Visit(const NavTriangleRawPtr& triangleRawPtr, KyFloat32 cost, const TriangleStatusInGrid& triangleStatus);
49 
50 public:
51  EdgeIntersector* m_edgeIntersector;
52  void* m_traverseLogicUserData;
53  bool m_collisionFound;
54 
55  KyFloat32 m_squareDistToCollisionPos;
56  Vec3f m_collisionPos;
57  NavHalfEdgeRawPtr m_intersectedHalfEdgeRawPtr;
58 
59 private:
60  bool m_shouldVisitNeighborTriangle[3];
61  NavTriangleRawPtr m_neighborTriangle[3];
62 };
63 
64 template<class TraverseLogic, class EdgeIntersector>
65 KY_INLINE BestFirstSearch2dBorderCollector<TraverseLogic, EdgeIntersector>::BestFirstSearch2dBorderCollector(void* traverseLogicUserData, EdgeIntersector& edgeIntersector) :
66 m_edgeIntersector(&edgeIntersector), m_traverseLogicUserData(traverseLogicUserData), m_collisionFound(false),
67  m_squareDistToCollisionPos(KyFloat32MAXVAL)
68 {
69  m_shouldVisitNeighborTriangle[0] = true;
70  m_shouldVisitNeighborTriangle[1] = true;
71  m_shouldVisitNeighborTriangle[2] = true;
72 }
73 
74 template<class TraverseLogic, class EdgeIntersector>
75 KY_INLINE bool BestFirstSearch2dBorderCollector<TraverseLogic, EdgeIntersector>::IsSearchFinished() { return false; }
76 
77 template<class TraverseLogic, class EdgeIntersector>
78 KY_INLINE bool BestFirstSearch2dBorderCollector<TraverseLogic, EdgeIntersector>::ShouldVisitNeighborTriangle(const NavTriangleRawPtr& /*triangleRawPtr*/, KyUInt32 indexOfNeighborTriangle)
79 {
80  return m_shouldVisitNeighborTriangle[indexOfNeighborTriangle];
81 }
82 
83 template<class TraverseLogic, class EdgeIntersector>
84 KY_INLINE bool BestFirstSearch2dBorderCollector<TraverseLogic, EdgeIntersector>::ShouldVisitTriangle(const NavTriangleRawPtr& /*triangleRawPtr*/) { return true; }
85 
86 template<class TraverseLogic, class EdgeIntersector>
87 KY_INLINE NavTriangleRawPtr BestFirstSearch2dBorderCollector<TraverseLogic, EdgeIntersector>::GetNeighborTriangle(const NavTriangleRawPtr& /*triangleRawPtr*/, KyUInt32 indexOfNeighborTriangle)
88 {
89  return m_neighborTriangle[indexOfNeighborTriangle];
90 }
91 
92 template<class TraverseLogic, class EdgeIntersector>
93 void BestFirstSearch2dBorderCollector<TraverseLogic, EdgeIntersector>::ComputeTriangleCost(const NavTriangleRawPtr& triangleRawPtr, KyFloat32& cost)
94 {
95  CoordPos64 v0, v1, v2;
96  triangleRawPtr.GetVerticesCoordPos64(v0, v1, v2);
97  m_edgeIntersector->ComputeTriangleCost(v0, v1, v2, cost);
98 }
99 
100 template<class TraverseLogic, class EdgeIntersector>
101 void BestFirstSearch2dBorderCollector<TraverseLogic, EdgeIntersector>::Visit(const NavTriangleRawPtr& triangleRawPtr, const KyFloat32 /*triangleCost*/,
102  const TriangleStatusInGrid& triangleStatus)
103 {
104  CoordPos64 v0, v1, v2;
105  CoordPos64* vertex[4] = { &v0, &v1, &v2, &v0};
106  NavHalfEdgeRawPtr halfEdgeRawPtr[3];
107  NavHalfEdge halfEdge[3];
108  bool isACrossableEdges[3];
109  bool isVisibleEdges[3];
110  bool neighborTriangleAlreadyVisited[3];
111 
112  const NavHalfEdgeIdx firstNavHalfEdgeIdx = NavFloorBlob::NavTriangleIdxToFirstNavHalfEdgeIdx(triangleRawPtr.GetTriangleIdx());
113  NavFloor* navFloor = triangleRawPtr.GetNavFloor();
114 
115  for(KyUInt32 i = 0; i < 3; ++i)
116  halfEdgeRawPtr[i].Set(navFloor, firstNavHalfEdgeIdx + i);
117 
118  triangleRawPtr.GetVerticesCoordPos64(v0, v1, v2);
119 
120  const NavFloorBlob& navFloorBlob = *navFloor->GetNavFloorBlob();
121  const NavHalfEdge* m_navHalfEdges = navFloorBlob.m_navHalfEdges.GetValues();
122 
123  for(KyUInt32 i = 0; i < 3; ++i)
124  halfEdge[i] = m_navHalfEdges[firstNavHalfEdgeIdx + i];
125 
126  NavHalfEdgeRawPtr pairHalfEdgeRawPtr;
127  for(KyUInt32 i = 0; i < 3; ++i)
128  {
129  isACrossableEdges[i] = halfEdgeRawPtr[i].IsHalfEdgeCrossable<TraverseLogic>(m_traverseLogicUserData, halfEdge[i], &navFloorBlob, pairHalfEdgeRawPtr);
130  if (isACrossableEdges[i])
131  {
132  bool inSameFloor = halfEdge[i].GetHalfEdgeType() == EDGETYPE_PAIRED || halfEdge[i].GetHalfEdgeType() == EDGETYPE_CONNEXBOUNDARY;
133  m_neighborTriangle[i].Set(pairHalfEdgeRawPtr.GetNavFloor(), NavFloorBlob::NavHalfEdgeIdxToTriangleIdx(pairHalfEdgeRawPtr.GetHalfEdgeIdx()));
134 
135  if (inSameFloor)
136  neighborTriangleAlreadyVisited[i] = triangleStatus.IsTriangleOpen_Unsafe(m_neighborTriangle[i]);
137  else
138  neighborTriangleAlreadyVisited[i] = triangleStatus.IsTriangleOpen(m_neighborTriangle[i]);
139  }
140  else
141  {
142  neighborTriangleAlreadyVisited[i] = false;
143  }
144  }
145 
146  for(KyUInt32 i = 0; i < 3; ++i)
147  isVisibleEdges[i] = neighborTriangleAlreadyVisited[i] || m_edgeIntersector->IsEdgeVisible(*vertex[i], *vertex[i+1], halfEdgeRawPtr[i], isACrossableEdges[i]);
148 
149  for(KyUInt32 i = 0; i < 3; ++i)
150  {
151  m_shouldVisitNeighborTriangle[i] = neighborTriangleAlreadyVisited[i]==false && isVisibleEdges[i] && isACrossableEdges[i];
152  }
153 }
154 
155 }
156 
157 
158 #endif //Navigation_BestFirstSearch2dBorderCollector_H
159 
#define KyFloat32MAXVAL
The maximum value that can be stored in the KyFloat32 variable type.
Definition: types.h:227
KyUInt32 NavHalfEdgeIdx
An index that uniquely identifies a single edge of a triangle within the set of edges owned by a NavF...
Definition: navmeshtypes.h:87
Indicates that another NavHalfEdge in the same NavFloor but in different Connex lies adjacent to the ...
Definition: navmeshtypes.h:60
static NavHalfEdgeIdx NavTriangleIdxToFirstNavHalfEdgeIdx(NavTriangleIdx idx)
Retrieves the first NavHalfEdgeIdx of NavTriangle specified by the input NavTriangleIdx.
Definition: navfloorblob.inl:26
Vec2LL CoordPos64
A type that represents the position of a point within the 2D integer grid.
Definition: navmeshtypes.h:19
Definition: gamekitcrowddispersion.h:20
static NavTriangleIdx NavHalfEdgeIdxToTriangleIdx(NavHalfEdgeIdx idx)
Retrieves the index of the triangle that contains the edge specified the input NavHalfEdgeIdx.
Definition: navfloorblob.inl:25
#define KY_DEFINE_NEW_DELETE_OPERATORS(MemStat)
This macro defines new and delete operators.
Definition: memory.h:137
Indicates that another NavHalfEdge in the same Connex lies adjacent to the NavHalfEdge.
Definition: navmeshtypes.h:61
unsigned int KyUInt32
Type used internally to represent an unsigned 32-bit integer.
Definition: types.h:36
float KyFloat32
Type used internally to represent a 32-bit floating-point number.
Definition: types.h:43