gwnavruntime/queries/utils/breadthfirstsearchedgecollisioncollector.h Source File

breadthfirstsearchedgecollisioncollector.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: LAPA - secondary contact: NOBODY
12 #ifndef Navigation_BestFirstSearchEdgeCollisionCollector_H
13 #define Navigation_BestFirstSearchEdgeCollisionCollector_H
14 
18 
19 
20 namespace Kaim
21 {
22 
23 /*
24 class BreadthFirstSearchEdgeCollisionCollector
25 
26 EdgeIntersector must have the following functions :
27 
28  bool DoesIntersectEdge(const Vec3f& startEdgePos, const Vec3f& endEdgePos);
29 */
30 template<class TraverseLogic, class EdgeIntersector>
31 class BreadthFirstSearchEdgeCollisionCollector
32 {
33  KY_DEFINE_NEW_DELETE_OPERATORS(MemStat_Query)
34 
35 public:
36  BreadthFirstSearchEdgeCollisionCollector(void* traverseLogicUserData, EdgeIntersector& edgeIntersector, WorkingMemArray<NavHalfEdgeRawPtr>* nearbyEdges);
37 
38  bool IsSearchFinished();
39  bool ShouldVisitNeighborTriangle(const NavTriangleRawPtr& triangleRawPtr, KyUInt32 indexOfNeighborTriangle);
40  bool ShouldVisitTriangle(const NavTriangleRawPtr& triangleRawPtr);
41 
42  NavTriangleRawPtr GetNeighborTriangle(const NavTriangleRawPtr& triangleRawPtr, KyUInt32 indexOfNeighborTriangle);
43 
44  void Visit(const NavTriangleRawPtr& triangleRawPtr, const TriangleStatusInGrid& triangleStatus);
45 
46 public:
47  EdgeIntersector* m_edgeIntersector;
48  void* m_traverseLogicUserData;
49  bool m_collisionFound;
50 
51  WorkingMemArray<NavHalfEdgeRawPtr>* m_intersectedHalfEdgeRawPtrArray;
52 
53 private:
54  bool m_shouldVisitNeighborTriangle[3];
55  NavTriangleRawPtr m_neighborTriangle[3];
56 };
57 
58 template<class TraverseLogic, class EdgeIntersector>
59 KY_INLINE BreadthFirstSearchEdgeCollisionCollector<TraverseLogic, EdgeIntersector>::BreadthFirstSearchEdgeCollisionCollector(void* traverseLogicUserData, EdgeIntersector& edgeIntersector, WorkingMemArray<NavHalfEdgeRawPtr>* nearbyEdges)
60  : m_edgeIntersector(&edgeIntersector)
61  , m_traverseLogicUserData(traverseLogicUserData)
62  , m_collisionFound(false)
63  , m_intersectedHalfEdgeRawPtrArray(nearbyEdges)
64 {
65  m_shouldVisitNeighborTriangle[0] = true;
66  m_shouldVisitNeighborTriangle[1] = true;
67  m_shouldVisitNeighborTriangle[2] = true;
68 }
69 
70 template<class TraverseLogic, class EdgeIntersector>
71 KY_INLINE bool BreadthFirstSearchEdgeCollisionCollector<TraverseLogic, EdgeIntersector>::IsSearchFinished()
72 {
73  return false;
74 }
75 
76 template<class TraverseLogic, class EdgeIntersector>
77 KY_INLINE bool BreadthFirstSearchEdgeCollisionCollector<TraverseLogic, EdgeIntersector>::ShouldVisitNeighborTriangle(const NavTriangleRawPtr& /*triangleRawPtr*/, KyUInt32 indexOfNeighborTriangle)
78 {
79  return m_shouldVisitNeighborTriangle[indexOfNeighborTriangle];
80 }
81 
82 template<class TraverseLogic, class EdgeIntersector>
83 KY_INLINE bool BreadthFirstSearchEdgeCollisionCollector<TraverseLogic, EdgeIntersector>::ShouldVisitTriangle(const NavTriangleRawPtr& /*triangleRawPtr*/)
84 {
85  return true;
86 }
87 
88 template<class TraverseLogic, class EdgeIntersector>
89 KY_INLINE NavTriangleRawPtr BreadthFirstSearchEdgeCollisionCollector<TraverseLogic, EdgeIntersector>::GetNeighborTriangle(const NavTriangleRawPtr& /*triangleRawPtr*/, KyUInt32 indexOfNeighborTriangle)
90 {
91  return m_neighborTriangle[indexOfNeighborTriangle];
92 }
93 
94 template<class TraverseLogic, class EdgeIntersector>
95 void BreadthFirstSearchEdgeCollisionCollector<TraverseLogic, EdgeIntersector>::Visit(const NavTriangleRawPtr& triangleRawPtr,
96  const TriangleStatusInGrid& triangleStatus)
97 {
98  CoordPos64 v0, v1, v2;
99  CoordPos64* vertex[4] = { &v0, &v1, &v2, &v0};
100  NavHalfEdgeRawPtr halfEdgeRawPtr[3];
101  NavHalfEdge halfEdge[3];
102  bool isACrossableEdges[3];
103  bool neighborTriangleAlreadyVisited[3];
104  bool doesIntersectsEdges[3];
105 
106  const NavHalfEdgeIdx firstNavHalfEdgeIdx = NavFloorBlob::NavTriangleIdxToFirstNavHalfEdgeIdx(triangleRawPtr.GetTriangleIdx());
107  NavFloor* navFloor = triangleRawPtr.GetNavFloor();
108 
109  for(KyUInt32 i = 0; i < 3; ++i)
110  halfEdgeRawPtr[i].Set(navFloor, firstNavHalfEdgeIdx + i);
111 
112  triangleRawPtr.GetVerticesCoordPos64(v0, v1, v2);
113 
114  const NavFloorBlob& navFloorBlob = *navFloor->GetNavFloorBlob();
115  const NavHalfEdge* m_navHalfEdges = navFloorBlob.m_navHalfEdges.GetValues();
116 
117  for(KyUInt32 i = 0; i < 3; ++i)
118  halfEdge[i] = m_navHalfEdges[firstNavHalfEdgeIdx + i];
119 
120  for(KyUInt32 i = 0; i < 3; ++i)
121  {
122  NavHalfEdgeRawPtr pairHalfEdgeRawPtr;
123  isACrossableEdges[i] = halfEdgeRawPtr[i].IsHalfEdgeCrossable<TraverseLogic>(m_traverseLogicUserData, halfEdge[i], &navFloorBlob, pairHalfEdgeRawPtr);
124 
125  if (isACrossableEdges[i])
126  {
127  bool inSameFloor = halfEdge[i].GetHalfEdgeType() == EDGETYPE_PAIRED || halfEdge[i].GetHalfEdgeType() == EDGETYPE_CONNEXBOUNDARY;
128  m_neighborTriangle[i].Set(pairHalfEdgeRawPtr.GetNavFloor(), NavFloorBlob::NavHalfEdgeIdxToTriangleIdx(pairHalfEdgeRawPtr.GetHalfEdgeIdx()));
129 
130  if (inSameFloor)
131  neighborTriangleAlreadyVisited[i] = triangleStatus.IsTriangleOpen_Unsafe(m_neighborTriangle[i]);
132  else
133  neighborTriangleAlreadyVisited[i] = triangleStatus.IsTriangleOpen(m_neighborTriangle[i]);
134  }
135  else
136  {
137  neighborTriangleAlreadyVisited[i] = false;
138  }
139  }
140 
141  for(KyUInt32 i = 0; i < 3; ++i)
142  {
143  doesIntersectsEdges[i] = neighborTriangleAlreadyVisited[i] || m_edgeIntersector->DoesIntersectEdge(*vertex[i], *vertex[i+1]);
144  if (doesIntersectsEdges[i] && (isACrossableEdges[i] == false))
145  m_intersectedHalfEdgeRawPtrArray->PushBack(halfEdgeRawPtr[i]);
146  }
147 
148  m_collisionFound =
149  (isACrossableEdges[0] == false && doesIntersectsEdges[0]) ||
150  (isACrossableEdges[1] == false && doesIntersectsEdges[1]) ||
151  (isACrossableEdges[2] == false && doesIntersectsEdges[2]);
152 
153  for(KyUInt32 i = 0; i < 3; ++i)
154  m_shouldVisitNeighborTriangle[i] = isACrossableEdges[i] && neighborTriangleAlreadyVisited[i] == false && doesIntersectsEdges[i];
155 }
156 
157 }
158 
159 
160 #endif //Navigation_BestFirstSearchEdgeCollisionCollector_H
161 
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