gwnavgeneration/boundary/boundarygraph.h Source File

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