gwnavruntime/dynamicnavmesh/earclippingtriangulator.h Source File

earclippingtriangulator.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 
11 
12 
13 namespace Kaim
14 {
15 
16 class DynamicTriangulation;
17 class WorkingMemory;
18 
19 class EarClippingTriangulatorInputPolygon
20 {
21  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
22 public:
23  EarClippingTriangulatorInputPolygon(MemoryHeap* heap = nullptr) : m_pointIndices(heap), m_edgeUserData(heap) {}
24 public:
25  KyArrayDH_POD<KyUInt32> m_pointIndices;
26  KyArrayDH_POD<void*> m_edgeUserData;
27 };
28 
29 class EarClippingTriangulatorInputPolygonWithHoles
30 {
31  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
32 public:
33  EarClippingTriangulatorInputPolygonWithHoles(MemoryHeap* heap = Memory::GetGlobalHeap()) : m_points(heap), m_exterior(heap), m_holes(heap) {}
34  void Clear()
35  {
36  m_points.Clear();
37  m_holes.Clear();
38  m_exterior.m_pointIndices.Clear();
39  m_exterior.m_edgeUserData.Clear();
40  }
41 public:
42  KyArrayDH_POD<Vec2i> m_points;
43  EarClippingTriangulatorInputPolygon m_exterior;
44  KyArrayDH<EarClippingTriangulatorInputPolygon> m_holes;
45 };
46 
47 class EarClippingTriangulator
48 {
49  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
50 public:
51  typedef KyUInt16 PolygonVertexIdx;
52  static const PolygonVertexIdx PolygonVertexIdx_Invalid = KyUInt16MAXVAL;
53 
54  class PolygonVertex
55  {
56  public:
57  enum Type
58  {
59  TYPE_CONVEX = 0,
60  TYPE_REFLEX = 1,
61  TYPE_EAR = 2,
62  TYPE_UNKNOWN
63  };
64 
65  PolygonVertex() :
66  m_posIdx(KyUInt16MAXVAL),
67  m_vertexType((KyUInt16)TYPE_UNKNOWN),
68  m_nextPolygonVertexIdx(PolygonVertexIdx_Invalid),
69  m_prevPolygonVertexIdx(PolygonVertexIdx_Invalid),
70  m_duplicateVertexIdx(PolygonVertexIdx_Invalid),
71  m_edgeGoingFromNextToMe(nullptr)
72  {}
73 
74  Type GetVertexType() const { return (Type)m_vertexType; }
75  void SetVertexType(Type vertexType) { m_vertexType = KyUInt16(vertexType); }
76  KyUInt16 m_posIdx;
77  KyUInt16 m_vertexType;
78  PolygonVertexIdx m_nextPolygonVertexIdx;
79  PolygonVertexIdx m_prevPolygonVertexIdx;
80  PolygonVertexIdx m_duplicateVertexIdx;
81  void* m_edgeGoingFromNextToMe;
82  };
83 
84 
85 public:
86  EarClippingTriangulator(const EarClippingTriangulatorInputPolygonWithHoles& input, KyArrayDH<PolygonVertex>& workingArray,
87  DynamicTriangulation& output, MemoryHeap* heap = Memory::GetGlobalHeap()) :
88  m_heap(heap),
89  m_input(&input),
90  m_output(&output),
91  m_polygonVertices(&workingArray) {}
92 
93  KyResult BuildPolygonAndLinkHolesToExterior();
94  KyResult Triangulate();
95 
96  enum TriangulateStepResult { TriangulateStepResult_Finish, TriangulateStepResult_GoOn };
97  KyResult TriangulateStep(TriangulateStepResult& triangulateStepResult, KyUInt16& currentVertexCountInPolygon,
98  PolygonVertexIdx& firstValidVertexIdx, KyUInt32 maxTestCount);
99 public:
100 
101  class HoleIdxWithMaxXVertexIdx
102  {
103  public:
104  HoleIdxWithMaxXVertexIdx() : m_toConnectIdx(PolygonVertexIdx_Invalid) {}
105  Vec2i m_posToConnect;
106  PolygonVertexIdx m_toConnectIdx;
107  };
108 
109  class FindVertexIdxResult
110  {
111  public:
112  enum ResultType { NOTFOUND, INTERSECTION_ON_VERTEX, INTERSECTION_ON_EDGE };
113 
114  FindVertexIdxResult () : m_resultType(NOTFOUND), m_intersectionPolygonVertexIdx(PolygonVertexIdx_Invalid), m_xIntersection(KyInt32MAXVAL) {}
115 
116  void SetVertexIntersection(KyInt32 xIntersection, PolygonVertexIdx intersectionPolygonVertexIdx)
117  {
118  m_resultType = INTERSECTION_ON_VERTEX;
119  m_xIntersection = xIntersection;
120  m_intersectionPolygonVertexIdx = intersectionPolygonVertexIdx;
121  }
122 
123  void SetEdgeIntersection(const Vec2i& edgeStart, const Vec2i& edgeEnd, PolygonVertexIdx intersectionPolygonVertexIdx)
124  {
125  m_resultType = INTERSECTION_ON_EDGE;
126  m_edgeStart = edgeStart;
127  m_edgeEnd = edgeEnd;
128  m_intersectionPolygonVertexIdx = intersectionPolygonVertexIdx;
129  }
130 
131  ResultType m_resultType;
132  PolygonVertexIdx m_intersectionPolygonVertexIdx;
133  KyInt32 m_xIntersection;
134  Vec2i m_edgeStart;
135  Vec2i m_edgeEnd;
136  };
137 
138  KY_INLINE bool HasDuplicate(PolygonVertexIdx polygonVertexIdx) const { return (*m_polygonVertices)[polygonVertexIdx].m_duplicateVertexIdx != polygonVertexIdx; }
139  KY_INLINE PolygonVertex::Type GetPolygonVertexType(const Vec2i& prevPos, const Vec2i& currentPos, const Vec2i& nextPos) const
140  {
141  const KyInt32 crossProduct = CrossProduct_15bits(nextPos - currentPos, prevPos - currentPos);
142  return crossProduct > 0 ? PolygonVertex::TYPE_CONVEX : PolygonVertex::TYPE_REFLEX;
143  }
144 
145  void FillPolygonVerticesForExterior(PolygonVertexIdx& currentNewPolygonVertexIdx);
146  void FillPolygonVerticesForHole(const EarClippingTriangulatorInputPolygon& holePolygon, HoleIdxWithMaxXVertexIdx& currentHoleMinX, PolygonVertexIdx& currentNewPolygonVertexIdx);
147 
148  KyResult LinkHoleToExterior(HoleIdxWithMaxXVertexIdx& currentHoleMinX, PolygonVertexIdx& currentNewPolygonVertexIdx);
149  KyUInt32 FindAndClipEar(PolygonVertexIdx& firstValidVertexIdx, KyUInt32& vertexTestedCount); // return the number of removed PolygonVertices
150 
151  void FindPolygonVertexIdxToLinkTo(KyUInt32 posToConnectIdx, FindVertexIdxResult& result);
152  void FindPolygonVertexIdxToLinkToForEdgeIntersection(KyUInt32 posToConnectIdx, FindVertexIdxResult& result);
153  PolygonVertexIdx FindBestCandidateForHoleConnection(KyUInt32 posToConnectIdx);
154  bool IsInAngularSectorOfVertex(const Vec2i& posToConnect, const PolygonVertex* polygonVertex) const;
155 
156 
157  bool IsPolygonVertexAnEar(const PolygonVertex* polygonVertex, KyUInt32& vertexTestedCount) const;
158  void UpdateVertexConvexStatus(PolygonVertex* polygonVertex);
159 
160  void PrintInputPolygonForDebug();
161 
162  static bool DoesPreviousEdgeIntersectsXAxisBeforeCurrentEdge(const Vec2i& prevEdgeStart, const Vec2i& prevEdgeEnd, const Vec2i& currEdgeStart, const Vec2i& currEdgeEnd);
163 public:
164  MemoryHeap* m_heap;
165  const EarClippingTriangulatorInputPolygonWithHoles* m_input;
166  DynamicTriangulation* m_output;
167  KyArrayDH<PolygonVertex>* m_polygonVertices; // the "linked" polygon structure
168 };
169 
170 } // namespace Kaim
171 
std::uint32_t KyUInt32
uint32_t
Definition: types.h:29
#define KY_DEFINE_NEW_DELETE_OPERATORS(MemStat)
This macro defines new and delete operators.
Definition: memory.h:132
std::uint16_t KyUInt16
uint16_t
Definition: types.h:28
#define KyInt32MAXVAL
KyInt32 max value
Definition: types.h:60
Navigation return code class.
Definition: types.h:108
The Autodesk Navigation namespace.
Definition: gamekitcrowddispersion.cpp:17
#define KyUInt16MAXVAL
KyUInt16 max value
Definition: types.h:67
std::int32_t KyInt32
int32_t
Definition: types.h:24