gwnavgeneration/boundary/boundarysimplifier.h Source File

boundarysimplifier.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 
10 
11 // primary contact: LASI - secondary contact: NOBODY
12 #ifndef GwNavGen_BoundarySimplifier_H
13 #define GwNavGen_BoundarySimplifier_H
14 
17 
19 
20 namespace Kaim
21 {
22 
23 class BoundaryVertexWithCost
24 {
25  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
26 public:
27  BoundaryVertexWithCost() : m_cost(KyFloat32MAXVAL), m_alreadyRemoved(false) {}
28  BoundaryVertexWithCost(BoundaryVertexListIterator vertex, KyFloat32 cost) : m_cost(cost), m_alreadyRemoved(false)
29  {
30  m_vertexIterator = vertex;
31  }
32 
33  KY_INLINE bool operator<(const BoundaryVertexWithCost& other) const { return m_cost > other.m_cost; }
34 
35 public:
36  BoundaryVertexListIterator m_vertexIterator;
37  KyFloat32 m_cost;
38  bool m_alreadyRemoved;
39 };
40 
41 class BoundarySimplifier
42 {
43  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
44 public:
45 
46  BoundarySimplifier(BoundaryGraph* boundaryGraph) : m_boundaryGraph(boundaryGraph)
47  {}
48 
49  //Smooth all the polylines of the input BoundaryGraph with a certain tolerance
50  //Tolerance measures the maximum error allowed between a vertex of BoundaryGraph
51  //and the corresponding simplified output polyline
52  //Units of tolerance depends on Boundary vertex coordinates system.
53  //Tolerance can be interpreted in terms of "percentage" of pixelSize
54  //for example, a tolerance of 0.5f means we accept an error of 0.5f * pixelSize
55  //Vertical tolerance defines the maximum error along the up Axis. Its in meters and
56  //the value is ignored if it is negative.
57  KyResult SimplifyBoundaries();
58 
59  KyResult SimplifyObstaclesAndConnexLinkBoundariesOfPolygon(KyUInt32 polygonIdx);
60 private:
61 
62  //based on Ramer Douglas Peucker approach
63  //see: http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm
64  KyResult DoSimplifyPolyline(BoundarySimplifyPolyline* polyline);
65 
66  //recursive algo. Max depth = log(polyline.size())
67  void RecursiveRDP(BoundarySimplifyPolyline* polyline,
68  BoundaryVertexListIterator begin,
69  BoundaryVertexListIterator last);
70 
71  void ComputePolylineBoundingBox(KyUInt32 polylineIdx);
72 
73  KyResult SimplifyAllCellLinkAndFloorLinkBoundaries();
74  void RemoveVerticesIfPossible(BoundarySimplifyPolyline* polyline, BoundaryVertexListIterator begin,
75  BoundaryVertexListIterator last);
76 
77  bool TestSimplificationAgainstOtherPolylinesAndSections(BoundarySimplifyPolyline* polyline,
78  BoundaryVertexListIterator begin, BoundaryVertexListIterator last,
79  BoundaryVertexListIterator previousVertex,BoundaryVertexListIterator currentVertex, BoundaryVertexListIterator nextVertex,
80  const Vec2i& v0, const Vec2i& v1, const Vec2i& v2, KyFloat32 squareDist, KyUInt32 insideVertexCount, bool canCollapse);
81 
82  bool TestAgainstTheOtherSectionsOfPolyline(BoundarySimplifyPolyline* polyline, BoundaryVertexListIterator begin, BoundaryVertexListIterator last,
83  BoundaryVertexListIterator previousVertex, BoundaryVertexListIterator currentVertex, BoundaryVertexListIterator nextVertex,
84  const Vec2i& v0, const Vec2i& v1, const Vec2i& v2, KyFloat32 squareDist);
85 
86  bool TestAgainstTheOtherPolylinesInFloor(BoundarySimplifyPolyline* polyline, BoundaryVertexListIterator previousVertex,
87  BoundaryVertexListIterator currentVertex, BoundaryVertexListIterator nextVertex, const Vec2i& v0, const Vec2i& v1, const Vec2i& v2,
88  KyFloat32 squareDist, KyUInt32 insideVertexCount, bool canCollapse);
89 
90  bool TestAgainstTheOtherPointsOfPolylineSection(BoundarySimplifyPolyline* polyline,
91  BoundaryVertexListIterator begin, BoundaryVertexListIterator last, BoundaryVertexListIterator previousVertex,
92  BoundaryVertexListIterator currentVertex, BoundaryVertexListIterator nextVertex, const Vec2i& v0, const Vec2i& v1, const Vec2i& v2, KyFloat32 squareDist);
93 
94  bool TestAgainsPoint(const Vec2i& v0, const Vec2i& v1, const Vec2i& v2, const Vec2i& otherPos,
95  BoundaryVertexListIterator previousVertex, BoundaryVertexListIterator nextVertex, BoundaryVertexListIterator otherCurrent, KyFloat32 squareDist);
96 
97  void BuildBinaryHeap(BoundarySimplifyPolyline* polyline, BoundaryVertexListIterator begin,
98  BoundaryVertexListIterator last, KyUInt32& insideVertexCount);
99 
100  bool IsAxisAlignedElseGetCCW(const Vec2i& previousPos, const Vec2i& currentPos, const Vec2i& nextPos, Vec2i& v0, Vec2i& v1, Vec2i& v2);
101 
102  void MarkAsRemovedInTheHeap(BoundaryVertexListIterator iter, BoundaryVertexListIterator invalidIter);
103  void GetCyclicNext(BoundaryVertexList& vertices, BoundaryVertexListIterator& iter);
104  void GetCyclicPrev(BoundaryVertexList& vertices, BoundaryVertexListIterator& iter);
105 
106 public:
107  KyFloat32 m_verticalTolerance;
108  KyFloat32 m_exteriorSimplificationTolerance;
109  KyFloat32 m_interiorSimplificationTolerance;
110  KyFloat32 m_toleranceForConnexLink;
111 
112 private:
113  BoundaryGraph* m_boundaryGraph;
114 
115  KyArrayTLS_POD<BoundarySimplifyPolyline*> m_polylinesInPolygon;
116  KyArrayTLS_POD<BoundarySimplifyPolyline*> m_currentBoxIntersectingPolylines;
117  KyArrayTLS_POD<Box2f> m_polylineBoudingBox;
118 
119  KyArrayTLS<BoundaryVertexListIterator> m_staticVertices; // used in cycled polyline to extract p
120  BinaryHeapTLS_CPP<BoundaryVertexWithCost> m_binaryHeap;
121 };
122 
123 KY_INLINE void BoundarySimplifier::GetCyclicNext(BoundaryVertexList& vertices, BoundaryVertexListIterator& iter)
124 {
125  ++iter;
126 
127  if (iter == vertices.End())
128  iter = vertices.Begin();
129 }
130 
131 KY_INLINE void BoundarySimplifier::GetCyclicPrev(BoundaryVertexList& vertices, BoundaryVertexListIterator& iter)
132 {
133  if (iter == vertices.Begin())
134  iter = vertices.End();
135 
136  --iter;
137 }
138 
139 }
140 
141 
142 #endif //GwNavGen_BoundarySimplifier_H
143 
#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
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