12 #ifndef GwNavGen_BoundarySimplifier_H
13 #define GwNavGen_BoundarySimplifier_H
23 class BoundaryVertexWithCost
27 BoundaryVertexWithCost() : m_cost(
KyFloat32MAXVAL), m_alreadyRemoved(false) {}
28 BoundaryVertexWithCost(BoundaryVertexListIterator vertex,
KyFloat32 cost) : m_cost(cost), m_alreadyRemoved(false)
30 m_vertexIterator = vertex;
33 KY_INLINE
bool operator<(
const BoundaryVertexWithCost& other)
const {
return m_cost > other.m_cost; }
36 BoundaryVertexListIterator m_vertexIterator;
38 bool m_alreadyRemoved;
41 class BoundarySimplifier
46 BoundarySimplifier(BoundaryGraph* boundaryGraph) : m_boundaryGraph(boundaryGraph)
59 KyResult SimplifyObstaclesAndConnexLinkBoundariesOfPolygon(
KyUInt32 polygonIdx);
64 KyResult DoSimplifyPolyline(BoundarySimplifyPolyline* polyline);
67 void RecursiveRDP(BoundarySimplifyPolyline* polyline,
68 BoundaryVertexListIterator begin,
69 BoundaryVertexListIterator last);
71 void ComputePolylineBoundingBox(
KyUInt32 polylineIdx);
73 KyResult SimplifyAllCellLinkAndFloorLinkBoundaries();
74 void RemoveVerticesIfPossible(BoundarySimplifyPolyline* polyline, BoundaryVertexListIterator begin,
75 BoundaryVertexListIterator last);
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);
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);
86 bool TestAgainstTheOtherPolylinesInFloor(BoundarySimplifyPolyline* polyline, BoundaryVertexListIterator previousVertex,
87 BoundaryVertexListIterator currentVertex, BoundaryVertexListIterator nextVertex,
const Vec2i& v0,
const Vec2i& v1,
const Vec2i& v2,
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);
94 bool TestAgainsPoint(
const Vec2i& v0,
const Vec2i& v1,
const Vec2i& v2,
const Vec2i& otherPos,
95 BoundaryVertexListIterator previousVertex, BoundaryVertexListIterator nextVertex, BoundaryVertexListIterator otherCurrent,
KyFloat32 squareDist);
97 void BuildBinaryHeap(BoundarySimplifyPolyline* polyline, BoundaryVertexListIterator begin,
98 BoundaryVertexListIterator last,
KyUInt32& insideVertexCount);
100 bool IsAxisAlignedElseGetCCW(
const Vec2i& previousPos,
const Vec2i& currentPos,
const Vec2i& nextPos, Vec2i& v0, Vec2i& v1, Vec2i& v2);
102 void MarkAsRemovedInTheHeap(BoundaryVertexListIterator iter, BoundaryVertexListIterator invalidIter);
103 void GetCyclicNext(BoundaryVertexList& vertices, BoundaryVertexListIterator& iter);
104 void GetCyclicPrev(BoundaryVertexList& vertices, BoundaryVertexListIterator& iter);
108 KyFloat32 m_exteriorSimplificationTolerance;
109 KyFloat32 m_interiorSimplificationTolerance;
113 BoundaryGraph* m_boundaryGraph;
115 KyArrayTLS_POD<BoundarySimplifyPolyline*> m_polylinesInPolygon;
116 KyArrayTLS_POD<BoundarySimplifyPolyline*> m_currentBoxIntersectingPolylines;
117 KyArrayTLS_POD<Box2f> m_polylineBoudingBox;
119 KyArrayTLS<BoundaryVertexListIterator> m_staticVertices;
120 BinaryHeapTLS_CPP<BoundaryVertexWithCost> m_binaryHeap;
123 KY_INLINE
void BoundarySimplifier::GetCyclicNext(BoundaryVertexList& vertices, BoundaryVertexListIterator& iter)
127 if (iter == vertices.End())
128 iter = vertices.Begin();
131 KY_INLINE
void BoundarySimplifier::GetCyclicPrev(BoundaryVertexList& vertices, BoundaryVertexListIterator& iter)
133 if (iter == vertices.Begin())
134 iter = vertices.End();
142 #endif //GwNavGen_BoundarySimplifier_H
#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