7 #ifndef Navigation_DynamicNavMeshQueryTypes_H
8 #define Navigation_DynamicNavMeshQueryTypes_H
27 static const KyUInt32 SWEEPLINE_CLIPPING_EXTERIOR_POLYGON_BIT = 1 << 30;
28 static const KyUInt32 SWEEPLINE_CLIPPING_HOLE_POLYGON_BIT = 1 << 29;
35 EdgePoints(
const Vec2i& start,
const Vec2i& end) : m_start(start), m_end(end) {}
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); }
41 KyInt32 ComputePointLocation(
const Vec2i& pt)
const {
return IntegerSegment::OnAboveOrBelow<KyInt64>(pt, m_start, m_end); }
43 KY_INLINE
bool IsAnExtremityWithThisXValue(
KyInt32 xValue,
KyInt32& correpondingYValue)
const
45 if (m_start.x == xValue) { correpondingYValue = m_start.y;
return true; }
46 if (m_end.x == xValue) { correpondingYValue = m_end.y;
return true; }
51 const Vec2i& operator[](
KyUInt32 idx)
const { KY_ASSERT(idx <= 1);
return (&m_start)[idx]; }
57 class InputEdgeProperty
71 EDGE_FROM_TAGVOLUME = 7,
72 EDGE_FROM_UNKNOWN_ORIGIN
76 KY_INLINE InputEdgeProperty() { SetDefault(); }
77 KY_INLINE
void SetDefault()
79 m_edgeOrigin = EDGE_FROM_UNKNOWN_ORIGIN;
84 m_coordinatesFlipped =
false;
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; }
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; }
94 EdgeOrigin m_edgeOrigin;
100 bool m_coordinatesFlipped;
110 EdgePoints m_extremities;
111 InputEdgeProperty m_property;
115 struct BasicLessHalfEdge
117 KY_INLINE
bool operator() (
const InputEdge& edge1,
const InputEdge& edge2)
const
119 if(edge1.m_extremities.m_start != edge2.m_extremities.m_start)
120 return edge1.m_extremities.m_start < edge2.m_extremities.m_start;
122 return edge1.m_extremities.m_end < edge2.m_extremities.m_end;
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) {}
135 const InputEdgeProperty& ParentProperty()
const {
return m_parentEdge->m_property; }
136 inline bool operator==(
const InputEdgePiece& otherEdge)
const
138 return GetEdgeStart() == otherEdge.GetEdgeStart() && GetEdgeEnd() == otherEdge.GetEdgeEnd() && GetCount() == otherEdge.GetCount();
140 inline bool operator<(
const InputEdgePiece& otherEdge)
const
142 if (GetEdgeStart().x != otherEdge.GetEdgeStart().x)
143 return GetEdgeStart().x < otherEdge.GetEdgeStart().x;
145 if (GetEdgeStart().y != otherEdge.GetEdgeStart().y)
146 return GetEdgeStart().y < otherEdge.GetEdgeStart().y;
149 return IntegerSegment::LessSlope<KyInt32>(GetEdgeStart(), GetEdgeEnd(), otherEdge.GetEdgeEnd());
151 bool operator!=(
const InputEdgePiece& edge)
const {
return !((*this) == edge); }
152 bool operator>=(
const InputEdgePiece& edge)
const {
return !((*this) < edge); }
154 KyFloat32 EvalAtX(
KyInt32 xIn)
const {
return IntegerSegment::EvalAtXforY_float(xIn, GetEdgeStart(), GetEdgeEnd()); }
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; }
161 const Vec2i& GetOriginalStart()
const
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);
167 return m_extremities[extremityIdx];
169 const Vec2i& GetOriginalEnd()
const
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);
175 return m_extremities[extremityIdx];
178 EdgePoints m_extremities;
179 const InputEdge* m_parentEdge;
187 class SweepLineOutputEdgePiece;
194 KyArrayPOD<Vec2i> m_points;
195 KyArrayPOD<const SweepLineOutputEdgePiece*> m_edges;
198 class MergedPolygonWithHoles
202 MergedPolygonWithHoles() {}
205 MergedPolygon m_exterior;
206 KyArray<MergedPolygon> m_holes;
209 class TriangulatorOutput
215 MergedPolygon m_referencePolygon;
216 KyArrayPOD<const SweepLineOutputEdgePiece*> m_inputEdgePiece;
217 KyArrayPOD<
KyUInt32> m_triangleEdgeIndices;
218 KyArrayPOD<
KyUInt32> m_startVertexOfEdges;
219 KyArrayPOD<
KyUInt32> m_pairEdgeIndices;
227 IndexedPos(
const Vec2i& pos,
KyUInt32 index) : m_pos(pos), m_index(index) {}
233 class IndexedPosSorter
236 KY_INLINE
bool operator() (
const IndexedPos& hotPoint1,
const IndexedPos& hotPoint2)
const
238 return hotPoint1.m_pos < hotPoint2.m_pos;
242 class EdgePointsComparatorAtX
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){}
248 inline bool operator () (
const EdgePoints& edge1,
const EdgePoints& edge2)
const
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);
252 KY_ASSERT(edge2.m_start.x <= m_x && edge2.m_end.x >= m_x);
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);
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);
260 if (edge1Maxy < edge2Miny)
263 if (edge1Miny > edge2Maxy)
270 KyInt32 yValueOfPointAtXOnEdge1 = 0;
271 KyInt32 yValueOfPointAtXOnEdge2 = 0;
273 bool edge1_at_x = edge1.IsAnExtremityWithThisXValue(m_x, yValueOfPointAtXOnEdge1);
274 bool edge2_at_x = edge2.IsAnExtremityWithThisXValue(m_x, yValueOfPointAtXOnEdge2);
276 if (edge1_at_x ==
false || edge2_at_x ==
false)
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"));
284 KyInt32 edge1StartPosFromEdge2 = edge2.ComputePointLocation(edge1.m_start);
285 KyInt32 edge1EndPosFromEdge2 = edge2.ComputePointLocation(edge1.m_end);
286 if (edge1StartPosFromEdge2 == edge1EndPosFromEdge2)
289 return edge1StartPosFromEdge2 == -1;
295 KyInt32 edge2StartPosFromEdge1 = edge1.ComputePointLocation(edge2.m_start);
301 KY_LOG_ERROR_IF(edge2StartPosFromEdge1 == 0, (
"Error in comparator object"));
303 return edge2StartPosFromEdge1 == 1;
308 if (yValueOfPointAtXOnEdge1 != yValueOfPointAtXOnEdge2)
309 return yValueOfPointAtXOnEdge1 < yValueOfPointAtXOnEdge2;
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));
325 return edge1SlopeLessThanEdge2Slope == (m_justBefore ==
KY_NULL || (*m_justBefore) == 0);
334 class InputEdgePieceComp
337 inline bool operator() (
const InputEdgePiece& i1,
const InputEdgePiece& i2)
const
339 const EdgePoints& edge1 = i1.m_extremities;
340 const EdgePoints& edge2 = i2.m_extremities;
342 if (edge1.m_start != edge2.m_start)
343 return edge1.m_start < edge2.m_start;
345 EdgePointsComparatorAtX lhe(edge1.m_start.x);
346 return lhe(edge1, edge2);
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