gwnavruntime/dynamicnavmesh/dynamicnavmeshquerytypes.h Source File

dynamicnavmeshquerytypes.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 #ifndef Navigation_DynamicNavMeshQueryTypes_H
8 #define Navigation_DynamicNavMeshQueryTypes_H
9 
10 // primary contact: LASI - secondary contact: NONE
21 
22 
23 
24 namespace Kaim
25 {
26 
27 static const KyUInt32 SWEEPLINE_CLIPPING_EXTERIOR_POLYGON_BIT = 1 << 30;
28 static const KyUInt32 SWEEPLINE_CLIPPING_HOLE_POLYGON_BIT = 1 << 29;
29 
30 class EdgePoints
31 {
32  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
33 public:
34  EdgePoints() {}
35  EdgePoints(const Vec2i& start, const Vec2i& end) : m_start(start), m_end(end) {}
36 
37  bool operator==(const EdgePoints& rhs) const { return m_start == rhs.m_start && m_end == rhs.m_end; }
38  bool operator!=(const EdgePoints& rhs) const { return !operator==(rhs); }
39 
40  //return -1 below, 0 on and 1 above line
41  KyInt32 ComputePointLocation(const Vec2i& pt) const { return IntegerSegment::OnAboveOrBelow<KyInt64>(pt, m_start, m_end); }
42 
43  KY_INLINE bool IsAnExtremityWithThisXValue(KyInt32 xValue, KyInt32& correpondingYValue) const
44  {
45  if (m_start.x == xValue) { correpondingYValue = m_start.y; return true; }
46  if (m_end.x == xValue) { correpondingYValue = m_end.y; return true; }
47  return false;
48  }
49 
50  //idx = 0 or idx = 1
51  const Vec2i& operator[](KyUInt32 idx) const { KY_ASSERT(idx <= 1); return (&m_start)[idx]; }
52 public:
53  Vec2i m_start;
54  Vec2i m_end;
55 };
56 
57 class InputEdgeProperty
58 {
59  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
60 public:
61 
62  enum EdgeOrigin
63  {
64  EDGE_FROM_CELLBOUNDARY_EAST = EDGETYPE_CELLBOUNDARY_EAST /*0*/,
65  EDGE_FROM_CELLBOUNDARY_NORTH = EDGETYPE_CELLBOUNDARY_NORTH /*1*/,
66  EDGE_FROM_CELLBOUNDARY_WEST = EDGETYPE_CELLBOUNDARY_WEST /*2*/,
67  EDGE_FROM_CELLBOUNDARY_SOUTH = EDGETYPE_CELLBOUNDARY_SOUTH /*3*/,
68  EDGE_FROM_FLOORBOUNDARY = EDGETYPE_FLOORBOUNDARY /*4*/,
69  EDGE_FROM_OBSTACLE = EDGETYPE_OBSTACLE /*5*/,
70  EDGE_FROM_CONNEXBOUNDARY = EDGETYPE_CONNEXBOUNDARY /*6*/,
71  EDGE_FROM_TAGVOLUME = 7,
72  EDGE_FROM_UNKNOWN_ORIGIN
73  };
74 
75 public:
76  KY_INLINE InputEdgeProperty() { SetDefault(); }
77  KY_INLINE void SetDefault()
78  {
79  m_edgeOrigin = EDGE_FROM_UNKNOWN_ORIGIN;
80  m_ownerIndex = KyUInt32MAXVAL;
81  m_stitch1To1EdgeIdx = KyUInt32MAXVAL;
82  m_navTagIndex = KyUInt32MAXVAL;
83  m_index = KyUInt32MAXVAL;
84  m_coordinatesFlipped = false;
85  }
86 
87  bool IsConnexBoundary() const { return (m_ownerIndex & SWEEPLINE_CLIPPING_EXTERIOR_POLYGON_BIT) != 0; }
88  bool IsHole() const { return (m_ownerIndex & SWEEPLINE_CLIPPING_HOLE_POLYGON_BIT) != 0; }
89 
90  bool operator <(const InputEdgeProperty& rhs) const { return m_ownerIndex < rhs.m_ownerIndex; }
91  bool operator ==(const InputEdgeProperty& rhs) const { return m_ownerIndex == rhs.m_ownerIndex; }
92 
93 public:
94  EdgeOrigin m_edgeOrigin; // EDGE_FROM_NAVFLOOR_XXX or EDGE_FROM_TAGVOLUME
95  KyUInt32 m_ownerIndex; // index of the contour it belong to in Navfloor or TagVolumeIndex
96  KyUInt32 m_stitch1To1EdgeIdx;
97  KyUInt32 m_navTagIndex; // info regarding the navtag associated to this edge : index in the array of dynamicNavTag
98  // internal state
99  KyUInt32 m_index; // index of the edge, unique among edges for a particular polygon
100  bool m_coordinatesFlipped;
101 };
102 
103 class InputEdge
104 {
105  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
106 public:
107  InputEdge() {}
108 
109 public:
110  EdgePoints m_extremities;
111  InputEdgeProperty m_property;
112 };
113 
114 // simple "std::pair"-style comparator
115 struct BasicLessHalfEdge
116 {
117  KY_INLINE bool operator() (const InputEdge& edge1, const InputEdge& edge2) const
118  {
119  if(edge1.m_extremities.m_start != edge2.m_extremities.m_start)
120  return edge1.m_extremities.m_start < edge2.m_extremities.m_start;
121  else
122  return edge1.m_extremities.m_end < edge2.m_extremities.m_end;
123  }
124 };
125 
126 
127 class InputEdgePiece
128 {
129  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
130 public:
131  InputEdgePiece(): m_parentEdge(KY_NULL), m_count(0), m_index(0) {}
132  InputEdgePiece(const EdgePoints& subSegment, const InputEdge& parentEdge) :
133  m_extremities(subSegment), m_parentEdge(&parentEdge), m_count(0), m_index(0) {}
134 
135  const InputEdgeProperty& ParentProperty() const { return m_parentEdge->m_property; }
136  inline bool operator==(const InputEdgePiece& otherEdge) const
137  {
138  return GetEdgeStart() == otherEdge.GetEdgeStart() && GetEdgeEnd() == otherEdge.GetEdgeEnd() && GetCount() == otherEdge.GetCount();
139  }
140  inline bool operator<(const InputEdgePiece& otherEdge) const
141  {
142  if (GetEdgeStart().x != otherEdge.GetEdgeStart().x)
143  return GetEdgeStart().x < otherEdge.GetEdgeStart().x;
144 
145  if (GetEdgeStart().y != otherEdge.GetEdgeStart().y)
146  return GetEdgeStart().y < otherEdge.GetEdgeStart().y;
147 
148  // both edges have the same start points....
149  return IntegerSegment::LessSlope<KyInt32>(GetEdgeStart(), GetEdgeEnd(), otherEdge.GetEdgeEnd());
150  }
151  bool operator!=(const InputEdgePiece& edge) const { return !((*this) == edge); }
152  bool operator>=(const InputEdgePiece& edge) const { return !((*this) < edge); }
153 
154  KyFloat32 EvalAtX(KyInt32 xIn) const { return IntegerSegment::EvalAtXforY_float(xIn, GetEdgeStart(), GetEdgeEnd()); }
155 
156  bool IsVertical() const { return GetEdgeStart().x == GetEdgeEnd().x; }
157  KyInt32 GetCount() const { return m_count; }
158  const Vec2i& GetEdgeStart() const { return m_extremities.m_start; }
159  const Vec2i& GetEdgeEnd() const { return m_extremities.m_end; }
160 
161  const Vec2i& GetOriginalStart() const
162  {
163  // we know, by construction, that m_edgePiece.m_start.x <= m_edgePiece.m_end.x
164  // so m_edgePiece.m_start.x - m_edgePiece.m_end.x >= is the same as m_edgePiece.m_start.x == m_edgePiece.m_end.x
165  const KyInt32 swappedPropertyCount = Isel(m_extremities.m_start.x - m_extremities.m_end.x, -m_count , m_count);
166  const KyInt32 extremityIdx = Isel(swappedPropertyCount, 1, 0); // 0 for start, 1 for end
167  return m_extremities[extremityIdx];
168  }
169  const Vec2i& GetOriginalEnd() const
170  {
171  // we know, by construction, that m_edgePiece.m_start.x <= m_edgePiece.m_end.x
172  // so m_edgePiece.m_start.x - m_edgePiece.m_end.x >= 0 is the same as m_edgePiece.m_start.x == m_edgePiece.m_end.x
173  const KyInt32 swappedPropertyCount = Isel(m_extremities.m_start.x - m_extremities.m_end.x, -m_count , m_count);
174  const KyInt32 extremityIdx = Isel(swappedPropertyCount, 0, 1); // 0 for start , 1 for end
175  return m_extremities[extremityIdx];
176  }
177 public:
178  EdgePoints m_extremities;
179  const InputEdge* m_parentEdge;
180  // on construction in edge intersector,
181  // m_count == 1 means that m_edgePiece.m_start < m_edgePiece.end || (m_edgePiece is Vertical && m_edgePiece.m_start >= m_edgePiece.end)
182  // m_count == -1 means that m_edgePiece.m_start >= m_edgePiece.end || (m_edgePiece is Vertical && m_edgePiece.m_start < m_edgePiece.end)
183  KyInt32 m_count;
184  KyUInt32 m_index;
185 };
186 
187 class SweepLineOutputEdgePiece;
188 class MergedPolygon
189 {
190  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
191 public:
192  MergedPolygon() {}
193 public:
194  KyArrayPOD<Vec2i> m_points;
195  KyArrayPOD<const SweepLineOutputEdgePiece*> m_edges;
196 };
197 
198 class MergedPolygonWithHoles
199 {
200  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
201 public:
202  MergedPolygonWithHoles() {}
203 
204 public:
205  MergedPolygon m_exterior;
206  KyArray<MergedPolygon> m_holes;
207 };
208 
209 class TriangulatorOutput
210 {
211  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
212 
213 public:
214  KyUInt32 m_navTagIndex;
215  MergedPolygon m_referencePolygon;
216  KyArrayPOD<const SweepLineOutputEdgePiece*> m_inputEdgePiece; //GetCount == edgeCount
217  KyArrayPOD<KyUInt32> m_triangleEdgeIndices; // GetCount == edgeCount; for triangle I, indices 3i, 3i+1, 3i+2 are the edge ()
218  KyArrayPOD<KyUInt32> m_startVertexOfEdges; // GetCount == edgeCount; accesing from edgeIdx
219  KyArrayPOD<KyUInt32> m_pairEdgeIndices; // GetCount == edgeCount;
220 };
221 
222 
223 class IndexedPos
224 {
225 public:
226  IndexedPos() : m_index(KyUInt32MAXVAL) {}
227  IndexedPos(const Vec2i& pos, KyUInt32 index) : m_pos(pos), m_index(index) {}
228 public:
229  Vec2i m_pos;
230  KyUInt32 m_index;
231 };
232 
233 class IndexedPosSorter
234 {
235 public:
236  KY_INLINE bool operator() (const IndexedPos& hotPoint1, const IndexedPos& hotPoint2) const
237  {
238  return hotPoint1.m_pos < hotPoint2.m_pos;
239  }
240 };
241 
242 class EdgePointsComparatorAtX
243 {
244 public:
245  inline EdgePointsComparatorAtX() : m_x(KY_NULL), m_justBefore(KY_NULL){}
246  inline EdgePointsComparatorAtX(KyInt32 x, KyInt32 *justBefore = KY_NULL) : m_x(x), m_justBefore(justBefore){}
247 
248  inline bool operator () (const EdgePoints& edge1, const EdgePoints& edge2) const
249  {
250  KY_ASSERT(edge1.m_start != edge2.m_start || edge1.m_start.x == m_x);
251  KY_ASSERT(edge1.m_start.x <= m_x && edge1.m_end.x >= m_x); // We are sure that edge1 intersects the vertical axis x == m_x
252  KY_ASSERT(edge2.m_start.x <= m_x && edge2.m_end.x >= m_x); // We are sure that edge2 intersects the vertical axis x == m_x
253 
254  const KyInt32 edge1Miny = FastMin(edge1.m_start.y, edge1.m_end.y);
255  const KyInt32 edge1Maxy = FastMax(edge1.m_start.y, edge1.m_end.y);
256 
257  const KyInt32 edge2Miny = FastMin(edge2.m_start.y, edge2.m_end.y);
258  const KyInt32 edge2Maxy = FastMax(edge2.m_start.y, edge2.m_end.y);
259 
260  if (edge1Maxy < edge2Miny)
261  return true; // the edge1 interval on Y-axis is strictly "below" the edge2 interval on Y-axis.
262 
263  if (edge1Miny > edge2Maxy)
264  return false; // the edge1 interval on Y-axis is strictly "above" the edge2 interval on Y-axis.
265 
266  // here we know that there is an intersection between the edge1 and edge2 interval on Y-axis
267  // To know which edge is above the other on the m_x axis, we have to compute the y-value of both edges along this axis (edge1y and edge2y)
268 
269  //check if either x of elem1 is equal to x_
270  KyInt32 yValueOfPointAtXOnEdge1 = 0;
271  KyInt32 yValueOfPointAtXOnEdge2 = 0;
272 
273  bool edge1_at_x = edge1.IsAnExtremityWithThisXValue(m_x, yValueOfPointAtXOnEdge1);
274  bool edge2_at_x = edge2.IsAnExtremityWithThisXValue(m_x, yValueOfPointAtXOnEdge2);
275 
276  if (edge1_at_x == false || edge2_at_x == false)
277  {
278  KY_LOG_ERROR_IF(edge2.m_start == edge1.m_start, ("We know that should not happen when this function is called, except if both of them are on the m_x axis"));
279 
280  //at least one of the segments doesn't have an end point at the current x
281 
282  //return value of ComputePointLocationFromEdge is
283  // -1 below the edge ; 1 above the edge ; 0 on the edge
284  KyInt32 edge1StartPosFromEdge2 = edge2.ComputePointLocation(edge1.m_start);
285  KyInt32 edge1EndPosFromEdge2 = edge2.ComputePointLocation(edge1.m_end);
286  if (edge1StartPosFromEdge2 == edge1EndPosFromEdge2)
287  {
288  // the two extremity of edge1 are on the same side of edge2. if both of them are below, edge1<edge2 at this x
289  return edge1StartPosFromEdge2 == -1;
290  }
291 
292  // the two extremity of edge1 are not on the same side of edge2.
293  // we know by construction that the two edges cannot intersect except at their extremity.
294 
295  KyInt32 edge2StartPosFromEdge1 = edge1.ComputePointLocation(edge2.m_start);
296  // we know that edge2.m_start cannot be on the edge since if such an intersection exists, it can be only on one of the extremity
297  // edge2.m_start cannot be on the end point of edge1 because if it was, both of them should be
298  // on m_x axis (we checked if (edge1_at_x == false || edge2_at_x == false) )
299  // edge2.m_start cannot be on the start point of edge1 because we are sure of that when we call
300  // this function (this has to be checked). This only happen when edge1.m_start == edge2.m_start == m_x
301  KY_LOG_ERROR_IF(edge2StartPosFromEdge1 == 0, ("Error in comparator object"));
302 
303  return edge2StartPosFromEdge1 == 1; //edge1's point is above edge1
304  }
305 
306  // Here we know that the two edges have one of their extremity on the m_x axis
307 
308  if (yValueOfPointAtXOnEdge1 != yValueOfPointAtXOnEdge2)
309  return yValueOfPointAtXOnEdge1 < yValueOfPointAtXOnEdge2;
310 
311  if (edge1 == edge2) // the two edges are equals...
312  return false;
313 
314  bool edge1SlopeLessThanEdge2Slope = IntegerSegment::LessSlopeUnit<KyInt64>(
315  (KyInt64)(edge1.m_end.x - edge1.m_start.x),
316  (KyInt64)(edge1.m_end.y - edge1.m_start.y),
317  (KyInt64)(edge2.m_end.x - edge2.m_start.x),
318  (KyInt64)(edge2.m_end.y - edge2.m_start.y));
319 
320 /*
321  if (m_justBefore == KY_NULL || (*m_justBefore) == 0)
322  return edge1SlopeLessThanEdge2Slope;
323  else
324  return edge1SlopeLessThanEdge2Slope == false;*/
325  return edge1SlopeLessThanEdge2Slope == (m_justBefore == KY_NULL || (*m_justBefore) == 0);
326 
327  }
328 
329 private:
330  KyInt32 m_x; //x value at which to apply comparison
331  KyInt32* m_justBefore;
332 };
333 
334 class InputEdgePieceComp
335 {
336 public:
337  inline bool operator() (const InputEdgePiece& i1, const InputEdgePiece& i2) const
338  {
339  const EdgePoints& edge1 = i1.m_extremities;
340  const EdgePoints& edge2 = i2.m_extremities;
341 
342  if (edge1.m_start != edge2.m_start)
343  return edge1.m_start < edge2.m_start;
344 
345  EdgePointsComparatorAtX lhe(edge1.m_start.x);
346  return lhe(edge1, edge2);
347  }
348 };
349 
350 } // namespace Kaim
351 
352 
353 
354 #endif // Navigation_DynamicNavMeshQueryTypes_H
KyInt32 Isel(KyInt32 a, KyInt32 x, KyInt32 y)
If a is greater than 0, returns x. Otherwise, returns y.
Definition: fastmath.h:70
int KyInt32
Type used internally to represent a 32-bit integer.
Definition: types.h:35
#define KY_NULL
Null value.
Definition: types.h:247
Indicates that another NavHalfEdge in the same NavFloor but in different Connex lies adjacent to the ...
Definition: navmeshtypes.h:60
Indicates that this NavHalfEdge lies on the border of its NavFloor and its NavCell.
Definition: navmeshtypes.h:57
Indicates that this NavHalfEdge lies on the border of its NavFloor and its NavCell.
Definition: navmeshtypes.h:54
Definition: gamekitcrowddispersion.h:20
Indicates that this NavHalfEdge lies on the border of its NavFloor.
Definition: navmeshtypes.h:58
Indicates that this NavHalfEdge lies on an external border of the NavMesh.
Definition: navmeshtypes.h:59
#define KY_DEFINE_NEW_DELETE_OPERATORS(MemStat)
This macro defines new and delete operators.
Definition: memory.h:137
Indicates that this NavHalfEdge lies on the border of its NavFloor and its NavCell.
Definition: navmeshtypes.h:55
unsigned int KyUInt32
Type used internally to represent an unsigned 32-bit integer.
Definition: types.h:36
Indicates that this NavHalfEdge lies on the border of its NavFloor and its NavCell.
Definition: navmeshtypes.h:56
#define KyUInt32MAXVAL
The maximum value that can be stored in the KyUInt32 variable type.
Definition: types.h:226
__int64 KyInt64
Type used internally to represent a 64-bit integer.
Definition: types.h:37
float KyFloat32
Type used internally to represent a 32-bit floating-point number.
Definition: types.h:43