gwnavruntime/queries/utils/breadthfirstsearchedgecollisionvisitor.h Source File

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