gwnavgeneration/boundary/boundarygraph.h Source File

boundarygraph.h
Go to the documentation of this file.
1 /*
2 * Copyright 2016 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 #pragma once
8 
9 #include "gwnavruntime/navmesh/celldesc.h"
10 #include "gwnavgeneration/boundary/boundarypixel.h"
11 #include "gwnavgeneration/boundary/boundaryedge.h"
12 #include "gwnavgeneration/boundary/boundaryvertex.h"
13 #include "gwnavgeneration/boundary/boundarysimplifypolyline.h"
14 #include "gwnavgeneration/boundary/boundarypolygon.h"
15 #include "gwnavgeneration/boundary/boundarysimplifiedpolygon.h"
16 #include "gwnavgeneration/boundary/connectedpattern.h"
17 #include "gwnavgeneration/common/boxofarrays.h"
18 #include "gwnavgeneration/common/boxoflists.h"
19 #include "gwnavgeneration/containers/tlsarray.h"
20 #include "gwnavruntime/base/types.h"
21 
22 
23 namespace Kaim
24 {
25 
26 class DynamicNavRasterCell;
27 class GeneratorSystem;
28 class ConnectionSquare;
29 
30 /*
31  exclusive_Max_X
32 exclusive_Min_X |
33  | |
34  v v
35  +---+---+---+---+---+---+
36  | | | | | | |
37  +---#################---+
38  | # | | | # | <-- exclusive_Max_Y
39  +---#---+---+---+---#---+
40  | # | | | # |
41  +---#---+---+---+---#---+
42  | # | | | # |
43  +---#---+---+---+---#---+
44  | # | | | # | <-- exclusive_Min_Y
45  +---#################---+
46  | | | | | | |
47  +---+---+---+---+---+---+
48 */
49 class BoundaryGraph
50 {
51  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
52 public:
53  BoundaryGraph(const DynamicNavRasterCell* navRaster);
54 
55  ~BoundaryGraph();
56 
57  KyResult Build();
58 
59  KyResult WriteIntermediateBoundaryGraphFile();
60 
61  KyUInt32 VerticesCount() const { return m_vertices.GetElementCount(); }
62  KyUInt32 EdgesCount() const { return m_edges.GetElementCount(); }
63  KyUInt32 ContoursCount() const { return m_contours.GetElementCount(); }
64  KyUInt32 PolygonsCount() const { return m_polygons.GetCount(); }
65  KyUInt32 SimplifyPolylinesCount() const { return m_simplifyPolylines.GetCount(); }
66  KyUInt32 SimplifiedEdgesCount() const { return m_simplifiedEdges.GetElementCount(); }
67  KyUInt32 SimplifiedContoursCount() const { return m_simplifiedContours.GetElementCount(); }
68  KyUInt32 SimplifiedPolygonsCount() const { return m_simplifiedPolygons.GetCount(); }
69 
70 private:
71  BoundaryEdge* AddEdge(CardinalDir dir, BoundaryEdgeType type, BoundaryPixel* leftPixel, KyUInt32 leftColor);
72 
73  // 1. Replicate navRaster structure with special treatment on corners
74  void BuildBoundaryPixelColumns();
75 
76  // 2. BuildEdges between south-north neighbors
77  void BuildEdgesBetweenSouthNorthNeighbors();
78 
79  // 3. BuildEdge between west-east neighbors
80  void BuildEdgesBetweenWestEastNeighbors();
81 
82  // 5. Based on the edges, analyse patterns and build vertices
83  KyResult BuildAllVerticesInAllColumns();
84 
85  // 6. Follow edges and build contours
86  void BuildAllContour();
87 
88  // 7. Group polylines in polygons
89  void BuildPolygons();
90 
91  // 8. Simplify polylines
92  void BuildSimplifyPolylinesFromContour();
93 
94  // 9. Do perform the polyline simplification
95  KyResult SimplifyAllPolylines();
96 
97  // 10. Reassociate simplified polygons
98  void BuildSimplifiedPolygons();
99 
100  KyUInt32 ProcessEdgeColumn(const PixelPos& currentPixelPos, const PixelPos& nextPos, CardinalDir dir);
101  KyUInt32 ProcessBirDirEdge(CardinalDir dir, const PixelPos& currentPos, const PixelPos& nextPos, BoundaryPixel* currentPixel, BoundaryPixel* nextPixel);
102  void AddObstacleEdge(BoundaryPixel* boundaryPixel, CardinalDir dir);
103  BoundaryEdge* AddEdgeInPixel(BoundaryPixel* boundaryPixel, CardinalDir dirLocationOfEdgeIdPixel, BoundaryEdgeType type);
104 
105  KyResult BuildVerticesColumn(ConnectionSquare& connectionSquare, const NavBoundaryPos& pos);
106  void AddVertexColumnToBuild(const NavBoundaryPos& pos);
107  void SetupSquarePixelColumn(ConnectionSquare& connectionSquare, KyUInt32 idxInSquare, const NavBoundaryPos& pos);
108  void BuildContour(BoundaryEdge* beginEdge);
109 
110  void BuildSimplifyPolylinesInContour(BoundaryContour& contour);
111  void BuildSimplifyPolyline_Cycle(BoundaryContour& contour);
112  void BuildSimplifyPolylines_NonCycle(BoundaryContour& contour, BoundaryEdge* firstEdgeWithStaticStart);
113  void BuildSimplifiedContour(const BoundaryContour& contour, BoundarySimplifiedContour& simplifiedContour);
114  BoundaryEdge* AddSimplifiedEdge(BoundarySimplifiedContour* simplifiedContour, const BoundaryVertexListIterator &firstEdgeIt, const BoundaryVertexListIterator &lastEdgeIt, bool isStraight);
115 
116  bool IsOutsideWest(NavPixelCoord x) const;
117  bool IsOutsideEast(NavPixelCoord x) const;
118  bool IsOutsideSouth(NavPixelCoord y) const;
119  bool IsOutsideNorth(NavPixelCoord y) const;
120  bool IsOutsideExclusiveBox(const PixelPos& pos) const;
121  bool IsOutsideExclusiveBox(NavPixelCoord x, NavPixelCoord y) const;
122 
123  bool IsInputNavRasterValid(); // for debug only
124 
125 public:
126  GeneratorSystem* m_sys;
127  const DynamicNavRasterCell* m_navRaster;
128  CellDesc m_cellDesc;
129  PixelBox m_navPixelBox; // navRaster PixelBox
130  PixelBox m_exclusivePixelBox; // exclusive PixelBox (without overlap)
131 
132  BoxOfArrays<BoundaryPixel> m_boxOfBoundaryPixelColumn; // association from NavPixels to BoundaryEdges
133 
134  GrowingPool<BoundaryEdge> m_edges;
135  GrowingPool<BoundaryEdge> m_outsideEdges;
136  GrowingPool<BoundaryVertex> m_vertices;
137  GrowingPool<BoundaryContour> m_contours;
138 
139  KyArrayTLS<BoundaryPolygon> m_polygons;
140 
141  BitFieldTLS m_registerVertexColumnsToBuild;
142  KyArrayTLS_POD<NavBoundaryPos> m_vertexColumnsToBuild;
143 
144  BoundaryVertexPool m_poolForBoundaryVertexList;
145  KyArrayTLS<BoundarySimplifyPolyline*> m_simplifyPolylines;
146 
147  GrowingPool<BoundarySimplifiedEdge> m_simplifiedEdges;
148  GrowingPool<BoundarySimplifiedContour> m_simplifiedContours;
149  KyArrayTLS<BoundarySimplifiedPolygon> m_simplifiedPolygons;
150 
151  KyArrayTLS<ConnectedPattern> m_connectPatterns;
152 };
153 
154 KY_INLINE bool BoundaryGraph::IsOutsideWest(NavPixelCoord x) const { return x == 0; }
155 KY_INLINE bool BoundaryGraph::IsOutsideEast(NavPixelCoord x) const { return x == m_navPixelBox.CountX() - 1; }
156 KY_INLINE bool BoundaryGraph::IsOutsideSouth(NavPixelCoord y) const { return y == 0; }
157 KY_INLINE bool BoundaryGraph::IsOutsideNorth(NavPixelCoord y) const { return y == m_navPixelBox.CountY() - 1; }
158 KY_INLINE bool BoundaryGraph::IsOutsideExclusiveBox(const PixelPos& pos) const { return IsOutsideExclusiveBox(pos.x, pos.y); }
159 KY_INLINE bool BoundaryGraph::IsOutsideExclusiveBox(NavPixelCoord x, NavPixelCoord y) const
160 {
161  return IsOutsideWest(x) || IsOutsideEast(x) || IsOutsideSouth(y) || IsOutsideNorth(y);
162 }
163 
164 KY_INLINE void BoundaryGraph::SetupSquarePixelColumn(ConnectionSquare& connectionSquare, KyUInt32 idxInSquare, const NavBoundaryPos& pos)
165 {
166  const BoxOfArrays<BoundaryPixel>::Column& boundaryPixelColumn = m_boxOfBoundaryPixelColumn.GetColumn(pos);
167  connectionSquare.SetupSquarePixelColumn(idxInSquare, pos, boundaryPixelColumn, IsOutsideExclusiveBox(pos));
168 }
169 
170 }
171 
172 
KyUInt32
std::uint32_t KyUInt32
uint32_t
Definition: types.h:29
Kaim::CardinalDir
KyUInt32 CardinalDir
Defines a type that refers to one of the cardinal points on the compass:
Definition: cardinaldir.h:15
KY_DEFINE_NEW_DELETE_OPERATORS
#define KY_DEFINE_NEW_DELETE_OPERATORS(MemStat)
This macro defines new and delete operators.
Definition: memory.h:132
Kaim::Result
Navigation return code class.
Definition: types.h:108
Kaim
The Autodesk Navigation namespace.
Definition: gamekitcrowddispersion.cpp:17
Please send us your comment about this page