gwnavruntime/queries/utils/bestfirstsearchedgecollisionvisitor.h Source File

bestfirstsearchedgecollisionvisitor.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_BestFirstSearchEdgeCollisionVisitor_H
13 #define Navigation_BestFirstSearchEdgeCollisionVisitor_H
14 
16 
17 namespace Kaim
18 {
19 
20 /*
21 class BestFirstSearchEdgeCollisionVisitor
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 BestFirstSearchEdgeCollisionVisitor
34 {
35  KY_DEFINE_NEW_DELETE_OPERATORS(MemStat_Query)
36 
37 public:
38  BestFirstSearchEdgeCollisionVisitor(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  KyFloat32 m_lastCost;
61  bool m_shouldVisitNeighborTriangle[3];
62  NavTriangleRawPtr m_neighborTriangle[3];
63 };
64 
65 template<class TraverseLogic, class EdgeIntersector>
66 KY_INLINE BestFirstSearchEdgeCollisionVisitor<TraverseLogic, EdgeIntersector>::BestFirstSearchEdgeCollisionVisitor(void* traverseLogicUserData, EdgeIntersector& edgeIntersector) :
67 m_edgeIntersector(&edgeIntersector), m_traverseLogicUserData(traverseLogicUserData), m_collisionFound(false),
68  m_squareDistToCollisionPos(KyFloat32MAXVAL), m_lastCost(KyFloat32MAXVAL)
69 {
70  m_shouldVisitNeighborTriangle[0] = true;
71  m_shouldVisitNeighborTriangle[1] = true;
72  m_shouldVisitNeighborTriangle[2] = true;
73 }
74 
75 template<class TraverseLogic, class EdgeIntersector>
76 KY_INLINE bool BestFirstSearchEdgeCollisionVisitor<TraverseLogic, EdgeIntersector>::IsSearchFinished() { return m_lastCost > m_squareDistToCollisionPos; }
77 
78 template<class TraverseLogic, class EdgeIntersector>
79 KY_INLINE bool BestFirstSearchEdgeCollisionVisitor<TraverseLogic, EdgeIntersector>::ShouldVisitNeighborTriangle(const NavTriangleRawPtr& /*triangleRawPtr*/, KyUInt32 indexOfNeighborTriangle)
80 {
81  return m_shouldVisitNeighborTriangle[indexOfNeighborTriangle];
82 }
83 
84 template<class TraverseLogic, class EdgeIntersector>
85 KY_INLINE bool BestFirstSearchEdgeCollisionVisitor<TraverseLogic, EdgeIntersector>::ShouldVisitTriangle(const NavTriangleRawPtr& /*triangleRawPtr*/) { return true; }
86 
87 template<class TraverseLogic, class EdgeIntersector>
88 KY_INLINE NavTriangleRawPtr BestFirstSearchEdgeCollisionVisitor<TraverseLogic, EdgeIntersector>::GetNeighborTriangle(const NavTriangleRawPtr& /*triangleRawPtr*/, KyUInt32 indexOfNeighborTriangle)
89 {
90  return m_neighborTriangle[indexOfNeighborTriangle];
91 }
92 
93 template<class TraverseLogic, class EdgeIntersector>
94 void BestFirstSearchEdgeCollisionVisitor<TraverseLogic, EdgeIntersector>::ComputeTriangleCost(const NavTriangleRawPtr& triangleRawPtr, KyFloat32& cost)
95 {
96  CoordPos64 v0, v1, v2;
97  triangleRawPtr.GetVerticesCoordPos64(v0, v1, v2);
98  m_edgeIntersector->ComputeTriangleCost(v0, v1, v2, cost);
99 }
100 
101 template<class TraverseLogic, class EdgeIntersector>
102 void BestFirstSearchEdgeCollisionVisitor<TraverseLogic, EdgeIntersector>::Visit(const NavTriangleRawPtr& triangleRawPtr, const KyFloat32 triangleCost,
103  const TriangleStatusInGrid& triangleStatus)
104 {
105  CoordPos64 v0, v1, v2;
106  CoordPos64* vertex[4] = { &v0, &v1, &v2, &v0};
107  NavHalfEdgeRawPtr halfEdgeRawPtr[3];
108  NavHalfEdge halfEdge[3];
109  bool isACrossableEdges[3];
110  bool neighborTriangleAlreadyVisited[3];
111  bool doesIntersectsEdges[3];
112 
113  const NavHalfEdgeIdx firstNavHalfEdgeIdx = NavFloorBlob::NavTriangleIdxToFirstNavHalfEdgeIdx(triangleRawPtr.GetTriangleIdx());
114  NavFloor* navFloor = triangleRawPtr.GetNavFloor();
115 
116  for(KyUInt32 i = 0; i < 3; ++i)
117  halfEdgeRawPtr[i].Set(navFloor, firstNavHalfEdgeIdx + i);
118 
119  triangleRawPtr.GetVerticesCoordPos64(v0, v1, v2);
120 
121  const NavFloorBlob& navFloorBlob = *navFloor->GetNavFloorBlob();
122  const NavHalfEdge* m_navHalfEdges = navFloorBlob.m_navHalfEdges.GetValues();
123 
124  for(KyUInt32 i = 0; i < 3; ++i)
125  halfEdge[i] = m_navHalfEdges[firstNavHalfEdgeIdx + i];
126 
127  for(KyUInt32 i = 0; i < 3; ++i)
128  {
129  NavHalfEdgeRawPtr pairHalfEdgeRawPtr;
130  isACrossableEdges[i] = halfEdgeRawPtr[i].IsHalfEdgeCrossable<TraverseLogic>(m_traverseLogicUserData, halfEdge[i], &navFloorBlob, pairHalfEdgeRawPtr);
131 
132  if (isACrossableEdges[i])
133  {
134  bool inSameFloor = halfEdge[i].GetHalfEdgeType() == EDGETYPE_PAIRED || halfEdge[i].GetHalfEdgeType() == EDGETYPE_CONNEXBOUNDARY;
135  m_neighborTriangle[i].Set(pairHalfEdgeRawPtr.GetNavFloor(), NavFloorBlob::NavHalfEdgeIdxToTriangleIdx(pairHalfEdgeRawPtr.GetHalfEdgeIdx()));
136 
137  if (inSameFloor)
138  neighborTriangleAlreadyVisited[i] = triangleStatus.IsTriangleOpen_Unsafe(m_neighborTriangle[i]);
139  else
140  neighborTriangleAlreadyVisited[i] = triangleStatus.IsTriangleOpen(m_neighborTriangle[i]);
141  }
142  else
143  {
144  neighborTriangleAlreadyVisited[i] = false;
145  }
146  }
147 
148  for(KyUInt32 i = 0; i < 3; ++i)
149  doesIntersectsEdges[i] = neighborTriangleAlreadyVisited[i] || m_edgeIntersector->DoesIntersectEdge(*vertex[i], *vertex[i+1]);
150 
151  m_lastCost = triangleCost;
152 
153  if (isACrossableEdges[0] == false || isACrossableEdges[1] == false || isACrossableEdges[2] == false)
154  {
155  Vec3f collisionPos;
156  KyFloat32 squareDistToCollisionPos;
157 
158  bool aCollisionFoundIsThisTriangle = false;
159 
160  for(KyUInt32 i = 0; i < 3; ++i)
161  {
162  if (isACrossableEdges[i] == false && doesIntersectsEdges[i])
163  {
164  m_edgeIntersector->ComputeCollisionPosOnEdge(*vertex[i], *vertex[i+1], collisionPos, squareDistToCollisionPos);
165  if (squareDistToCollisionPos < m_squareDistToCollisionPos)
166  {
167  m_squareDistToCollisionPos = squareDistToCollisionPos;
168  aCollisionFoundIsThisTriangle = true;
169  m_collisionPos = collisionPos;
170  m_intersectedHalfEdgeRawPtr.Set(triangleRawPtr.m_navFloorRawPtr, NavFloorBlob::NavTriangleIdxToNavHalfEdgeIdx(triangleRawPtr.GetTriangleIdx(), i));
171  }
172  }
173  }
174 
175  m_collisionFound = m_collisionFound || aCollisionFoundIsThisTriangle;
176  }
177 
178  for(KyUInt32 i = 0; i < 3; ++i)
179  m_shouldVisitNeighborTriangle[i] = isACrossableEdges[i] && neighborTriangleAlreadyVisited[i] == false && doesIntersectsEdges[i];
180 }
181 
182 }
183 
184 
185 #endif //Navigation_BestFirstSearchEdgeCollisionVisitor_H
186 
#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
static NavHalfEdgeIdx NavTriangleIdxToNavHalfEdgeIdx(NavTriangleIdx idx, KyInt32 halfEdgeNumber)
Retrieves one edge from the specified triangle.
Definition: navfloorblob.inl:28
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