gwnavgeneration/boundary/connectedpattern.h Source File

connectedpattern.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 // primary contact: GUAL - secondary contact: LASI
10 #ifndef GwNavGen_ConnectedPattern_H
11 #define GwNavGen_ConnectedPattern_H
12 
17 
18 namespace Kaim
19 {
20 
21 static const KyUInt32 MaxVertexEdgeLinkCount = 8;
22 
23 
24 class VertexEdgeLink
25 {
26  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
27 public:
28  enum EdgeInOrOut { EDGE_IN = 0, EDGE_OUT = 1 };
29 
30  void Init(EdgeInOrOut edgeInOrOut, BoundaryEdge* edge)
31  {
32  m_edge = edge;
33  m_edgeInOrOut = edgeInOrOut;
34  m_vertexIdxInEdge = (edgeInOrOut == EDGE_IN) ? 1 : 0;
35  }
36 
37  void Apply(BoundaryVertex* center)
38  {
39  m_edge->m_vertex[m_vertexIdxInEdge] = center; // edge.vertex = center
40  KY_ASSERT(m_edge->m_orientation < 4);
41  if (m_edgeInOrOut == EDGE_OUT)
42  center->m_outs[m_edge->m_orientation] = m_edge; // center.edges = edge
43  else
44  center->m_ins[m_edge->m_orientation] = m_edge; // center.edges = edge
45  }
46 
47  BoundaryEdge* m_edge;
48  EdgeInOrOut m_edgeInOrOut;
49  KyUInt32 m_vertexIdxInEdge;
50 };
51 
52 
53 class SquarePixel
54 {
55  KY_DEFINE_NEW_DELETE_OPERATORS(MemStat_NavDataGen)
56 public:
57  SquarePixel() { Setup(KY_NULL, KY_NULL, false); }
58 
59  void Setup(BoundaryPixel* boundaryPixel, KyUInt32 pixelIdxInSquare, bool isOutsideCellBox)
60  {
61  m_boundaryPixel = boundaryPixel;
62  m_connected[0] = KY_NULL;
63  m_connected[1] = KY_NULL;
64  m_pixelIdxInSquare = pixelIdxInSquare;
65  m_isInPattern = false;
66  m_isOutsideCellBox = isOutsideCellBox;
67  }
68 
69  // ORTHOGONAL EDGES
70  // +-----------+-----------+ pixel_0.edgeIn edgeLocationInLeftPixel=0 edgeDir = North = 1
71  // | 1 | 1 | pixel_1.edgeIn edgeLocationInLeftPixel=1 edgeDir = West = 2
72  // | p3 | p2 | pixel_2.edgeIn edgeLocationInLeftPixel=2 edgeDir = South = 3
73  // |2 out=0|2=in 0| pixel_3.edgeIn edgeLocationInLeftPixel=3 edgeDir = East = 0
74  // | | |
75  // | in=3 N 3=out | pixel_0.edgeOut edgeLocationInLeftPixel=1 edgeDir = West = 2
76  // +---------W-V-E---------+ pixel_1.edgeOut edgeLocationInLeftPixel=2 edgeDir = South = 3
77  // | out=1 S in=1 | pixel_2.edgeOut edgeLocationInLeftPixel=3 edgeDir = East = 0
78  // | | | pixel_3.edgeOut edgeLocationInLeftPixel=0 edgeDir = North = 1
79  // |2 in=0|2=out 0|
80  // | p0 | p1 | edgeDirFromCenter:
81  // | 3 | 3 | E=East=0 N=North=1 W=West=2 S=South=3
82  // +-----------+-----------+
83 
84  void PushVertexEdgeLinks(VertexEdgeLink* vertexEdgeLinks, KyUInt32& vertexEdgeLinksCount) const
85  {
86  CardinalDir edgeIn_IdxInPixel = m_pixelIdxInSquare;
87  CardinalDir edgeOut_IdxInPixel = GetNextCardinalDir_CCW(edgeIn_IdxInPixel);
88 
89  BoundaryEdge* edgeIn = m_boundaryPixel->m_edges[edgeIn_IdxInPixel];
90  if (edgeIn != KY_NULL)
91  {
92  KY_ASSERT(vertexEdgeLinksCount < MaxVertexEdgeLinkCount);
93  VertexEdgeLink& link = vertexEdgeLinks[vertexEdgeLinksCount++];
94  link.Init(VertexEdgeLink::EDGE_IN, edgeIn);
95  }
96 
97  BoundaryEdge* edgeOut = m_boundaryPixel->m_edges[edgeOut_IdxInPixel];
98  if (edgeOut != KY_NULL)
99  {
100  KY_ASSERT(vertexEdgeLinksCount < MaxVertexEdgeLinkCount);
101  VertexEdgeLink& link = vertexEdgeLinks[vertexEdgeLinksCount++];
102  link.Init(VertexEdgeLink::EDGE_OUT, edgeOut);
103  }
104  }
105 
106  BoundaryPixel* m_boundaryPixel;
107  SquarePixel* m_connected[2];
108  KyUInt32 m_pixelIdxInSquare;
109  bool m_isInPattern;
110  bool m_isOutsideCellBox;
111 };
112 
113 
114 class SquarePixelColumn
115 {
116  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
117 public:
118  SquarePixelColumn(KyUInt32 squarePixelsCapacityAtInit = 50)
119  {
120  if (squarePixelsCapacityAtInit == 0)
121  squarePixelsCapacityAtInit = 50;
122  m_squarePixels.Resize(squarePixelsCapacityAtInit);
123  }
124 
125  ~SquarePixelColumn() {}
126 
127  void Setup(KyUInt32 idxInSquare, const NavBoundaryPos& pos, const BoxOfArrays<BoundaryPixel>::Column& boundaryPixelColumn, bool isOutsideNavBox)
128  {
129  m_pos = pos;
130  m_squarePixels.Clear();
131  m_squarePixels.Resize(boundaryPixelColumn.m_count);
132  for (NavRasterFloorIdx floorIdx = 0; floorIdx < boundaryPixelColumn.m_count; ++floorIdx)
133  m_squarePixels[floorIdx].Setup(&boundaryPixelColumn.m_values[floorIdx], idxInSquare, isOutsideNavBox);
134  }
135 
136  PixelPos m_pos;
137  KyArrayTLS_POD<SquarePixel> m_squarePixels;
138 };
139 
140 
141 class ConnectionSquare
142 {
143  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
144 public:
145  KY_INLINE void SetupSquarePixelColumn(KyUInt32 idxInSquare, const NavBoundaryPos& pos, const BoxOfArrays<BoundaryPixel>::Column& boundaryPixelColumn, bool isOutsideNavBox)
146  {
147  m_columns[idxInSquare].Setup(idxInSquare, pos, boundaryPixelColumn, isOutsideNavBox);
148  }
149 public:
150  SquarePixelColumn m_columns[4];
151 };
152 
153 
154 class ConnectedPattern
155 {
156  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
157 public:
158  enum { CCW = 0, CW = 1 };
159 
160  ConnectedPattern() : m_count(0)
161  {
162  for(KyUInt32 i = 0; i < 4; ++i)
163  m_pixels[i] = KY_NULL;
164  }
165 
166  void Init(SquarePixel* firstSquarePixel)
167  {
168  // push first
169  firstSquarePixel->m_isInPattern = true;
170  m_pixels[0] = firstSquarePixel;
171  m_count = 1;
172 
173  // propagate CCW and CW
174  for(KyUInt32 i = 0; i < 2; ++i)
175  {
176  SquarePixel* squarePixel = firstSquarePixel;
177  for (;;)
178  {
179  squarePixel = squarePixel->m_connected[i];
180  if (squarePixel == KY_NULL || squarePixel->m_isInPattern == true)
181  break;
182  squarePixel->m_isInPattern = true;
183  if (m_count < 4)
184  m_pixels[m_count] = squarePixel;
185  m_count++;
186  }
187  }
188  }
189 
190  KyFloat32 GetCenterAltitude()
191  {
192  KY_ASSERT(m_count != 0);
193  static const KyFloat32 florCountInv[4] = { 1.f, 0.5f, 0.333333333333f, 0.25f };
194 
195  KyFloat32 altitude = 0.0f;
196  for (KyUInt32 i = 0; i < m_count; ++i)
197  {
198  KY_ASSERT(m_pixels[i] != KY_NULL);
199  altitude += m_pixels[i]->m_boundaryPixel->m_navRasterPixel->m_altitude;
200  }
201  altitude *= florCountInv[m_count-1];
202  return altitude;
203  }
204 
205  bool IsFullyOutsideCellBox()
206  {
207  KY_ASSERT(m_count != 0);
208  for (KyUInt32 i = 0; i < m_count; ++i)
209  {
210  if (m_pixels[i]->m_isOutsideCellBox == false)
211  return false;
212  }
213  return true;
214  }
215 
216  bool IsNarrow()
217  {
218  bool isBlocked[4] = { false, false, false, false };
219  bool isDeadEnd[4] = { false, false, false, false };
220  for (KyUInt32 pixelIdx = 0; pixelIdx < m_count; ++pixelIdx)
221  {
222  SquarePixel* squarePixel = m_pixels[pixelIdx];
223  KY_ASSERT(squarePixel != KY_NULL);
224 
225  BoundaryPixel* boundaryPixel = squarePixel->m_boundaryPixel;
226  KY_ASSERT(boundaryPixel != KY_NULL);
227  // Dead end chedc
228  // Dead end == 3 consecutive orthogonal edges
229  for (CardinalDir dir = 0; dir < 4; ++dir)
230  {
231  // 3 consecutive orthogonal edges == dead end -> NOT necessarily narrow
232  const BoundaryEdge* edges[4] =
233  {
234  boundaryPixel->m_edges[ dir ], // current dir
235  boundaryPixel->m_edges[(dir+1)%4],
236  boundaryPixel->m_edges[(dir+2)%4],
237  boundaryPixel->m_edges[(dir+3)%4]
238  };
239 
240  if (edges[0] != KY_NULL && edges[1] != KY_NULL && edges[2] != KY_NULL)
241  {
242  isDeadEnd[pixelIdx] = true;
243  if (edges[3] != KY_NULL)
244  return true; // 4 consecutive edges: isolated pixel <=> narrow otherwise simplified polyline will fail
245 
246  break;
247  }
248  }
249 
250  if (isDeadEnd[pixelIdx] == false)
251  {
252  for (CardinalDir dir = 0; dir < 4; ++dir)
253  {
254  // 2 opposite orthogonal edges and not deadEnd == 1 pixel corridor -> narrow
255  // =====
256  // | p |
257  // =====
258  if (squarePixel->m_boundaryPixel->m_edges[ dir ] != KY_NULL &&
259  squarePixel->m_boundaryPixel->m_edges[GetOppositeCardinalDir(dir)]!= KY_NULL )
260  return true;
261  }
262  }
263 
264  // 2
265  // +--e2--+---e2-+ pixel 0: (right) e4 -> vertex 3 is blocked
266  // | | | (up) e6 -> vertex 0 is blocked
267  // e4 p3 | p2 e0 pixel 1: (right) e6 -> vertex 0 is blocked
268  // 3 +------+----- + 1 (up) e0 -> vertex 1 is blocked
269  // | p0 | p1 | pixel 2: (right) e0 -> vertex 1 is blocked
270  // e4 | e0 (up) e2 -> vertex 2 is blocked
271  // +---e6-+--e6--+ pixel 3: (right) e2 -> vertex 2 is blocked
272  // 0 (up) e4 -> vertex 3 is blocked
273 
274  KyUInt32 rightEdgeIdx = (squarePixel->m_pixelIdxInSquare + 2) % 4; // ~= opposite
275  KyUInt32 upEdgeIdx = (squarePixel->m_pixelIdxInSquare + 3) % 4;
276  KyUInt32 rightVtxIdx = (squarePixel->m_pixelIdxInSquare + 3) % 4;
277  KyUInt32 upVtxIdx = (squarePixel->m_pixelIdxInSquare);
278 
279  if (isBlocked[rightVtxIdx] == false && squarePixel->m_boundaryPixel->m_edges[rightEdgeIdx])
280  isBlocked[rightVtxIdx] = true;
281 
282  if (isBlocked[upVtxIdx] == false && squarePixel->m_boundaryPixel->m_edges[upEdgeIdx])
283  isBlocked[upVtxIdx] = true;
284  }
285 
286  // 2 U shaped pixels attached = narrow corridor !
287  // ==========
288  // | p0 - p1 |
289  // ==========
290  //
291  for (KyUInt32 j = 0; j < 4; ++j)
292  {
293  if (isDeadEnd[j] && isDeadEnd[(j+1)%4])
294  return true;
295  }
296 
297  //if a vertex is blocked but no edge links pattern center to it, we have a narrow pattern
298  for (KyUInt32 pixelIdx = 0; pixelIdx < m_count; ++pixelIdx)
299  {
300  if (isDeadEnd[pixelIdx])
301  continue;
302 
303  SquarePixel* squarePixel = m_pixels[pixelIdx];
304  KY_ASSERT(squarePixel != KY_NULL);
305 
306  SquarePixel* neighborCCW = squarePixel->m_connected[CCW];
307  if (neighborCCW != KY_NULL)
308  {
309  KyUInt32 ccwVtxIdx = (squarePixel->m_pixelIdxInSquare);
310  if (isBlocked[ccwVtxIdx] &&
311  neighborCCW->m_boundaryPixel->m_floorColor == squarePixel->m_boundaryPixel->m_floorColor &&
312  neighborCCW->m_boundaryPixel->m_connexIdx == squarePixel->m_boundaryPixel->m_connexIdx )
313  return true;
314  }
315 
316  SquarePixel* neighborCW = squarePixel->m_connected[CW];
317  if (neighborCW != KY_NULL)
318  {
319  KyUInt32 cwVtxIdx = (squarePixel->m_pixelIdxInSquare + 3) % 4;
320  if (isBlocked[cwVtxIdx] &&
321  neighborCW->m_boundaryPixel->m_floorColor == squarePixel->m_boundaryPixel->m_floorColor &&
322  neighborCW->m_boundaryPixel->m_connexIdx == squarePixel->m_boundaryPixel->m_connexIdx )
323  return true;
324  }
325  }
326  return false;
327  }
328 
329  KyUInt32 m_count; // in [0; 4]
330  SquarePixel* m_pixels[4];
331 };
332 }
333 
334 
335 #endif
CardinalDir GetOppositeCardinalDir(const CardinalDir dir)
Returns the CardinalDir that lies in the opposite direction from the specified CardinalDir.
Definition: cardinaldir.h:35
#define KY_NULL
Null value.
Definition: types.h:247
KyUInt32 CardinalDir
Defines a type that refers to one of the cardinal points on the compass:
Definition: cardinaldir.h:23
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
float KyFloat32
Type used internally to represent a 32-bit floating-point number.
Definition: types.h:43