gwnavruntime/navmesh/dynamictriangulation_int.h Source File

dynamictriangulation_int.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 // Primary contact: JUBA - secondary contact: LASI
8 #ifndef Navigation_DynamicTriangulation_Integer_H
9 #define Navigation_DynamicTriangulation_Integer_H
10 
14 
15 namespace Kaim
16 {
17 
18 class DynTriHalfEdge;
19 class IndexedTriangleSoup2i;
20 class Triangle3i;
21 
22 typedef CoordPos AlignedCoordPos;
23 
24 enum DynamicVertexIntUserDataContent
25 {
26  DTI_UNKNOWN_VERTEX_USERDATA,
27  DTI_TRIANGLE_SOUP_VERTEX_TAG_DATA
28 };
29 // ----------------------------
30 // ----- DynamicVertex_Int --------
31 // ----------------------------
32 class DynTriVertex
33 {
34  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
35 public:
36  DynTriVertex() : m_idx(KyUInt32MAXVAL), m_coordPos(KyInt32MAXVAL, KyInt32MAXVAL), m_altitude(KyFloat32MAXVAL), m_userData(KY_NULL)
37  {
38  m_outGoingEdgeIdx.Reserve(12);
39  }
40 
41 
42  KY_INLINE void InsertInOutGoingEdges(KyUInt32 dynamicHalfEdgeIdx)
43  {
44  KY_ASSERT(m_outGoingEdgeIdx.DoesContain(dynamicHalfEdgeIdx) == false);
45  m_outGoingEdgeIdx.PushBack(dynamicHalfEdgeIdx);
46  KY_ASSERT(m_outGoingEdgeIdx.DoesContain(dynamicHalfEdgeIdx));
47  }
48 
49  KY_INLINE void RemoveFromOutGoingEdges(KyUInt32 dynamicHalfEdgeIdx)
50  {
51  KY_ASSERT(m_outGoingEdgeIdx.DoesContain(dynamicHalfEdgeIdx));
52  m_outGoingEdgeIdx.RemoveFirstOccurrence(dynamicHalfEdgeIdx);
53  KY_ASSERT(m_outGoingEdgeIdx.DoesContain(dynamicHalfEdgeIdx) == false);
54  }
55 
56 public:
57  KyUInt32 m_idx;
58  AlignedCoordPos m_coordPos;
59  KyFloat32 m_altitude;
60  Collection<KyUInt32> m_outGoingEdgeIdx;
61 
62  void* m_userData;
63 };
64 
65 // ------------------------------
66 // ----- DynamicTriangle_Int --------
67 // ------------------------------
68 class DynTriTriangle
69 {
70  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
71 public:
72  DynTriTriangle() : m_idx(KyUInt32MAXVAL), m_edgeIdx(KyUInt32MAXVAL), m_userData(KY_NULL) {}
73 
74  void GetLocalTriangle3i(KyUInt32 pixelSize, KyFloat32 rasterPrecision, Triangle3i& triangle3i) const;
75 public:
76  KyUInt32 m_idx;
77  KyUInt32 m_edgeIdx; // one edge around the face
78 
79  void* m_userData;
80 };
81 
82 // ---------------------------
83 // ----- DynamicHalfEdge_Int -----
84 // ---------------------------
85 class DynTriHalfEdge
86 {
87  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
88 public:
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) {}
91 
92  enum HalfEdgeStatus
93  {
94  HalfEdgeStatus_Open = 0,
95  HalfEdgeStatus_NotOpen = 1,
96  HalfEdgeStatus_Locked = 2,
97 
98  HalfEdgeStatus_FORCE32 = 0xFFFFFFFF
99  };
100 
101  KY_INLINE bool IsABorder() const { return m_pairEdgeIdx == KyUInt32MAXVAL; }
102  KY_INLINE bool IsLocked() const { return m_status == HalfEdgeStatus_Locked; }
103 
104 public:
105  KyUInt32 m_idx;
106  KyUInt32 m_startVertexIdx;
107  KyUInt32 m_triangleIdx;
108  KyUInt32 m_nextEdgeIdx;
109  KyUInt32 m_pairEdgeIdx;
110  HalfEdgeStatus m_status;
111  void* m_userData;
112 };
113 
114 /* Instance of this class are returned by DynamicTriangulation_Int::InsertANewVertexInMeshAndUpdateTriangulation
115  if m_result == RESULT_NEW_VERTEX_CREATED => m_vertex refers to the new created vertex
116  if m_result == RESULT_CLOSE_TO_EXISTING_VERTEX => m_vertex refers to the vertex we are close to
117  if m_result == RESULT_CLOSE_TO_BORDER_EDGE => m_ halfEdge refers to the border HalfEdge we are close to
118  if m_result == RESULT_NOT_IN_TRIANGLE => no triangle contains input position. No usefull datan, m_vertex and m_halfEdge remains to KY_NULL
119  if m_result == RESULT_REFUSED => position refused becaus of floating precision issue (we don't want to create reverse face). No usefull data, m_vertex and m_halfEdge remains to KY_NULL
120 */
121 
122 class DynTriangulationInsertionResult
123 {
124  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
125 
126 public:
127 
128  DynTriangulationInsertionResult() : m_result(RESULT_FORCE32), m_vertexIdx(KyUInt32MAXVAL), m_halfEdgeIdx(KyUInt32MAXVAL) {}
129 
130  enum Result
131  {
132  RESULT_NEW_VERTEX_CREATED = 0,
133  RESULT_EXISTING_VERTEX = 1,
134  RESULT_ON_A_BORDER_EDGE = 2,
135  RESULT_NOT_IN_TRIANGLE = 3,
136  RESULT_REFUSED = 4,
137  RESULT_FORCE32 = 0xFFFFFFFF
138  };
139 
140  Result m_result;
141  KyUInt32 m_vertexIdx;
142  KyUInt32 m_halfEdgeIdx;
143 };
144 
145 
146 // --------------------------------
147 // ----- DynamicTriangulation_Int -----
148 // --------------------------------
149 class DynamicTriangulation
150 {
151  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
152  KY_CLASS_WITHOUT_COPY(DynamicTriangulation)
153 public:
154  KY_INLINE DynamicTriangulation(MemoryHeap* heap) :
155  m_triangles(heap),
156  m_vertices(heap),
157  m_edges(heap),
158  m_edgeIdxToProcess(heap),
159  m_userDataContent(DTI_UNKNOWN_VERTEX_USERDATA)
160  {}
161 
162  ~DynamicTriangulation() { Clear(); }
163 
164  void Clear();
165 
166 
167  // mesh Creation
168  KyUInt32 AddVertex(const AlignedCoordPos& coordPos, KyFloat32 altitude = KyFloat32MAXVAL);
169  KyUInt32 AddTriangle(KyUInt32 v0Idx, KyUInt32 v1Idx, KyUInt32 v2Idx);
170 
171  // Use this after calling Resize with good value on m_vertices and m_edges
172  void AddVertex(KyUInt32 vertexIdx, const AlignedCoordPos& coordPos, KyFloat32 altitude = KyFloat32MAXVAL);
173  //KyUInt32 AddTriangle(KyUInt32 triangleIdx, KyUInt32 v0Idx, KyUInt32 v1Idx, KyUInt32 v2Idx);
174 
175 
176  KyResult BuildFromIndexedTriangleSoup(const IndexedTriangleSoup2i* triangulation);
177  KyResult BuildIndexedTriangleSoup(IndexedTriangleSoup2i* triangulation);
178 
179  // Process the triangulation to get a "Delaunay Like" triangulation
180  // This function should be called before inserting new vertices and Updating Triangulation
181  void GetABetterTriangulation();
182 
183  /*-------------- Functions used for better altitude approximation -------------- */
184 
185  // Add a new vertex in the Mesh and triangulate around him
186  // return KyUInt32MAXVAL if
187  // - the position isn't in any triangle
188  // - the position is too close to one of the three vertices of the triangle (according to m_squareMinDistFromExistingPoint, distances are in 2D)
189  // - the position is too close to a border edge (according to m_squareMinDistFromBorder, distances are in 2D)
190  // If the position is close to an edge (according to m_maxSquareDistToConsiderAPointOnAnEdge, distances are in 2D), the vertex is snapped on the edge
191  KyUInt32 InsertANewVertexInMesh(const CoordPos& position, DynTriangulationInsertionResult& result);
192 
193  // perform an InsertANewVertexInMesh and update the triangulation to get a "Delauney Like" triangulation
194  // if impactedTrianglesIndices is not null, fill it with the indices of modified triangles
195  DynTriangulationInsertionResult InsertANewVertexInMeshAndUpdateTriangulation(
196  const CoordPos& position, KyArrayDH_POD<KyUInt32>* impactedTrianglesIndices = KY_NULL);
197 
198  KY_INLINE void LockEdge(KyUInt32 halfEdgeIdx)
199  {
200  DynTriHalfEdge& edge = m_edges[halfEdgeIdx];
201 
202  if (edge.m_status != DynTriHalfEdge::HalfEdgeStatus_Locked)
203  {
204  KY_DEBUG_ASSERTN(edge.m_status == DynTriHalfEdge::HalfEdgeStatus_NotOpen ,("Don't change edge status during process"));
205  edge.m_status = DynTriHalfEdge::HalfEdgeStatus_Locked;
206  }
207 
208  if (edge.IsABorder() == false && m_edges[edge.m_pairEdgeIdx].m_status != DynTriHalfEdge::HalfEdgeStatus_Locked)
209  {
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;
212  }
213  }
214 
215 
216  void GetLocalTriangle3i(KyUInt32 triangleIdx, KyUInt32 pixelSize, KyFloat32 rasterPrecision, Triangle3i& triangle3i) const;
217 
218 public: // internal
219  KyResult FlipEdge(KyUInt32 halfEdgeIdx);
220 
221  void UpdateTriangulationAfterVertexInsertion(KyUInt32 newVertexIdx);
222 
223  bool IsEdgeLegal(KyUInt32 halfEdgeIdx);
224  bool IsEdgeLegalAfterPointInsertion(KyUInt32 halfEdgeIdx, KyUInt32 newVertexIdx);
225 
226  // dynamic mesh modification
227  KyUInt32 FindTriangleThatContainsAPosition(const CoordPos& position, DynTriangulationInsertionResult& result);
228 
229  void InsertANewVertexInsideATriangle(KyUInt32 newVertexIdx, KyUInt32 triangleIdx);
230  void InsertANewVertexInTheMiddleOfAnEdge(KyUInt32 newVertexIdx, KyUInt32 halfEdgeIdx);
231  void InsertANewVertexInTheMiddleOfABorderEdge(KyUInt32 newVertexIdx, KyUInt32 halfEdgeIdx);
232 
233  void AddToEdgeToProcessIfNotOpen(KyUInt32 halfEdgeIdx);
234  void AddToEdgeToProcessIfIllegalAndNotOpen(KyUInt32 halfEdgeIdx);
235 
236  static bool IsQuadrilateralConvex(const AlignedCoordPos& a, const AlignedCoordPos& b, const AlignedCoordPos& c, const AlignedCoordPos& d);
237 private :
238  KyUInt32 GetNewDynamicVertex();
239  KyUInt32 GetNewDynamicHalfEdge();
240  KyUInt32 GetNewDynamicTriangle();
241 
242 public:
243  KyArrayDH<DynTriTriangle> m_triangles;
244  KyArrayDH<DynTriVertex> m_vertices;
245  KyArrayDH<DynTriHalfEdge> m_edges;
246 
247  KyArrayDH_POD<KyUInt32> m_edgeIdxToProcess;
248 
249  DynamicVertexIntUserDataContent m_userDataContent;
250 };
251 
252 
253 KY_INLINE void DynamicTriangulation::AddVertex(KyUInt32 vertexIdx, const AlignedCoordPos& coordPos, KyFloat32 altitude)
254 {
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];
258 
259  vertex.m_idx = vertexIdx;
260  vertex.m_coordPos = coordPos;
261  vertex.m_altitude = altitude;
262 }
263 }
264 
265 
266 #endif //Navigation_DynamicTriangulation_Integer_H
267 
#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