8 #ifndef Navigation_DynamicTriangulation_Integer_H
9 #define Navigation_DynamicTriangulation_Integer_H
19 class IndexedTriangleSoup2i;
24 enum DynamicVertexIntUserDataContent
26 DTI_UNKNOWN_VERTEX_USERDATA,
27 DTI_TRIANGLE_SOUP_VERTEX_TAG_DATA
38 m_outGoingEdgeIdx.Reserve(12);
42 KY_INLINE
void InsertInOutGoingEdges(
KyUInt32 dynamicHalfEdgeIdx)
44 KY_ASSERT(m_outGoingEdgeIdx.DoesContain(dynamicHalfEdgeIdx) ==
false);
45 m_outGoingEdgeIdx.PushBack(dynamicHalfEdgeIdx);
46 KY_ASSERT(m_outGoingEdgeIdx.DoesContain(dynamicHalfEdgeIdx));
49 KY_INLINE
void RemoveFromOutGoingEdges(
KyUInt32 dynamicHalfEdgeIdx)
51 KY_ASSERT(m_outGoingEdgeIdx.DoesContain(dynamicHalfEdgeIdx));
52 m_outGoingEdgeIdx.RemoveFirstOccurrence(dynamicHalfEdgeIdx);
53 KY_ASSERT(m_outGoingEdgeIdx.DoesContain(dynamicHalfEdgeIdx) ==
false);
58 AlignedCoordPos m_coordPos;
60 Collection<KyUInt32> m_outGoingEdgeIdx;
72 DynTriTriangle() : m_idx(KyUInt32MAXVAL), m_edgeIdx(KyUInt32MAXVAL), m_userData(KY_NULL) {}
74 void GetLocalTriangle3i(
KyUInt32 pixelSize,
KyFloat32 rasterPrecision, Triangle3i& triangle3i)
const;
89 DynTriHalfEdge() : m_idx(KyUInt32MAXVAL), m_startVertexIdx(KyUInt32MAXVAL), m_triangleIdx(KyUInt32MAXVAL),
90 m_nextEdgeIdx(KyUInt32MAXVAL), m_pairEdgeIdx(KyUInt32MAXVAL), m_status(HalfEdgeStatus_NotOpen), m_userData(KY_NULL) {}
94 HalfEdgeStatus_Open = 0,
95 HalfEdgeStatus_NotOpen = 1,
96 HalfEdgeStatus_Locked = 2,
98 HalfEdgeStatus_FORCE32 = 0xFFFFFFFF
101 KY_INLINE
bool IsABorder()
const {
return m_pairEdgeIdx ==
KyUInt32MAXVAL; }
102 KY_INLINE
bool IsLocked()
const {
return m_status == HalfEdgeStatus_Locked; }
110 HalfEdgeStatus m_status;
122 class DynTriangulationInsertionResult
128 DynTriangulationInsertionResult() : m_result(RESULT_FORCE32), m_vertexIdx(KyUInt32MAXVAL), m_halfEdgeIdx(KyUInt32MAXVAL) {}
132 RESULT_NEW_VERTEX_CREATED = 0,
133 RESULT_EXISTING_VERTEX = 1,
134 RESULT_ON_A_BORDER_EDGE = 2,
135 RESULT_NOT_IN_TRIANGLE = 3,
137 RESULT_FORCE32 = 0xFFFFFFFF
149 class DynamicTriangulation
154 KY_INLINE DynamicTriangulation(MemoryHeap* heap) :
158 m_edgeIdxToProcess(heap),
159 m_userDataContent(DTI_UNKNOWN_VERTEX_USERDATA)
162 ~DynamicTriangulation() { Clear(); }
168 KyUInt32 AddVertex(
const AlignedCoordPos& coordPos,
KyFloat32 altitude = KyFloat32MAXVAL);
172 void AddVertex(
KyUInt32 vertexIdx,
const AlignedCoordPos& coordPos,
KyFloat32 altitude = KyFloat32MAXVAL);
176 KyResult BuildFromIndexedTriangleSoup(
const IndexedTriangleSoup2i* triangulation);
177 KyResult BuildIndexedTriangleSoup(IndexedTriangleSoup2i* triangulation);
181 void GetABetterTriangulation();
191 KyUInt32 InsertANewVertexInMesh(
const CoordPos& position, DynTriangulationInsertionResult& result);
195 DynTriangulationInsertionResult InsertANewVertexInMeshAndUpdateTriangulation(
196 const CoordPos& position, KyArrayDH_POD<KyUInt32>* impactedTrianglesIndices = KY_NULL);
198 KY_INLINE
void LockEdge(
KyUInt32 halfEdgeIdx)
200 DynTriHalfEdge& edge = m_edges[halfEdgeIdx];
202 if (edge.m_status != DynTriHalfEdge::HalfEdgeStatus_Locked)
204 KY_DEBUG_ASSERTN(edge.m_status == DynTriHalfEdge::HalfEdgeStatus_NotOpen ,(
"Don't change edge status during process"));
205 edge.m_status = DynTriHalfEdge::HalfEdgeStatus_Locked;
208 if (edge.IsABorder() ==
false && m_edges[edge.m_pairEdgeIdx].m_status != DynTriHalfEdge::HalfEdgeStatus_Locked)
210 KY_DEBUG_ASSERTN(m_edges[edge.m_pairEdgeIdx].m_status == DynTriHalfEdge::HalfEdgeStatus_NotOpen ,(
"Don't change edge status during process"));
211 m_edges[edge.m_pairEdgeIdx].m_status = DynTriHalfEdge::HalfEdgeStatus_Locked;
216 void GetLocalTriangle3i(
KyUInt32 triangleIdx,
KyUInt32 pixelSize,
KyFloat32 rasterPrecision, Triangle3i& triangle3i)
const;
221 void UpdateTriangulationAfterVertexInsertion(
KyUInt32 newVertexIdx);
223 bool IsEdgeLegal(
KyUInt32 halfEdgeIdx);
224 bool IsEdgeLegalAfterPointInsertion(
KyUInt32 halfEdgeIdx,
KyUInt32 newVertexIdx);
227 KyUInt32 FindTriangleThatContainsAPosition(
const CoordPos& position, DynTriangulationInsertionResult& result);
229 void InsertANewVertexInsideATriangle(
KyUInt32 newVertexIdx,
KyUInt32 triangleIdx);
230 void InsertANewVertexInTheMiddleOfAnEdge(
KyUInt32 newVertexIdx,
KyUInt32 halfEdgeIdx);
231 void InsertANewVertexInTheMiddleOfABorderEdge(
KyUInt32 newVertexIdx,
KyUInt32 halfEdgeIdx);
233 void AddToEdgeToProcessIfNotOpen(
KyUInt32 halfEdgeIdx);
234 void AddToEdgeToProcessIfIllegalAndNotOpen(
KyUInt32 halfEdgeIdx);
236 static bool IsQuadrilateralConvex(
const AlignedCoordPos& a,
const AlignedCoordPos& b,
const AlignedCoordPos& c,
const AlignedCoordPos& d);
243 KyArrayDH<DynTriTriangle> m_triangles;
244 KyArrayDH<DynTriVertex> m_vertices;
245 KyArrayDH<DynTriHalfEdge> m_edges;
247 KyArrayDH_POD<KyUInt32> m_edgeIdxToProcess;
249 DynamicVertexIntUserDataContent m_userDataContent;
253 KY_INLINE
void DynamicTriangulation::AddVertex(
KyUInt32 vertexIdx,
const AlignedCoordPos& coordPos,
KyFloat32 altitude)
255 KY_ASSERT(vertexIdx < m_vertices.GetCount());
256 KY_LOG_ERROR_IF(((coordPos.x & 0xFFFFFF00) != 0 || (coordPos.y & 0xFFFFFF00) != 0), (
"Invalid coordinates : %d - %d", coordPos.x, coordPos.y));
257 DynTriVertex& vertex = m_vertices[vertexIdx];
259 vertex.m_idx = vertexIdx;
260 vertex.m_coordPos = coordPos;
261 vertex.m_altitude = altitude;
266 #endif //Navigation_DynamicTriangulation_Integer_H
#define KyFloat32MAXVAL
The maximum value that can be stored in the KyFloat32 variable type.
Definition: types.h:227
KyInt32 KyResult
Defines a type that can be returned by methods or functions in the Gameware Navigation SDK to indicat...
Definition: types.h:254
#define KY_NULL
Null value.
Definition: types.h:247
#define KY_CLASS_WITHOUT_COPY(ClassName)
Define to forbid copy constructor and copy assignment.
Definition: types.h:387
Vec2i CoordPos
A type that represents the position of a point within the 2D integer grid.
Definition: navmeshtypes.h:23
#define KyInt32MAXVAL
The maximum value that can be stored in the KyInt32 variable type.
Definition: types.h:224
Definition: gamekitcrowddispersion.h:20
#define KY_DEFINE_NEW_DELETE_OPERATORS(MemStat)
This macro defines new and delete operators.
Definition: memory.h:137
unsigned int KyUInt32
Type used internally to represent an unsigned 32-bit integer.
Definition: types.h:36
#define KyUInt32MAXVAL
The maximum value that can be stored in the KyUInt32 variable type.
Definition: types.h:226
float KyFloat32
Type used internally to represent a 32-bit floating-point number.
Definition: types.h:43