16 class DynamicTriangulation;
19 class EarClippingTriangulatorInputPolygon
23 EarClippingTriangulatorInputPolygon(MemoryHeap* heap =
nullptr) : m_pointIndices(heap), m_edgeUserData(heap) {}
25 KyArrayDH_POD<KyUInt32> m_pointIndices;
26 KyArrayDH_POD<void*> m_edgeUserData;
29 class EarClippingTriangulatorInputPolygonWithHoles
33 EarClippingTriangulatorInputPolygonWithHoles(MemoryHeap* heap = Memory::GetGlobalHeap()) : m_points(heap), m_exterior(heap), m_holes(heap) {}
38 m_exterior.m_pointIndices.Clear();
39 m_exterior.m_edgeUserData.Clear();
42 KyArrayDH_POD<Vec2i> m_points;
43 EarClippingTriangulatorInputPolygon m_exterior;
44 KyArrayDH<EarClippingTriangulatorInputPolygon> m_holes;
47 class EarClippingTriangulator
52 static const PolygonVertexIdx PolygonVertexIdx_Invalid =
KyUInt16MAXVAL;
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)
74 Type GetVertexType()
const {
return (Type)m_vertexType; }
75 void SetVertexType(Type vertexType) { m_vertexType =
KyUInt16(vertexType); }
78 PolygonVertexIdx m_nextPolygonVertexIdx;
79 PolygonVertexIdx m_prevPolygonVertexIdx;
80 PolygonVertexIdx m_duplicateVertexIdx;
81 void* m_edgeGoingFromNextToMe;
86 EarClippingTriangulator(
const EarClippingTriangulatorInputPolygonWithHoles& input, KyArrayDH<PolygonVertex>& workingArray,
87 DynamicTriangulation& output, MemoryHeap* heap = Memory::GetGlobalHeap()) :
91 m_polygonVertices(&workingArray) {}
93 KyResult BuildPolygonAndLinkHolesToExterior();
96 enum TriangulateStepResult { TriangulateStepResult_Finish, TriangulateStepResult_GoOn };
97 KyResult TriangulateStep(TriangulateStepResult& triangulateStepResult,
KyUInt16& currentVertexCountInPolygon,
98 PolygonVertexIdx& firstValidVertexIdx,
KyUInt32 maxTestCount);
101 class HoleIdxWithMaxXVertexIdx
104 HoleIdxWithMaxXVertexIdx() : m_toConnectIdx(PolygonVertexIdx_Invalid) {}
105 Vec2i m_posToConnect;
106 PolygonVertexIdx m_toConnectIdx;
109 class FindVertexIdxResult
112 enum ResultType { NOTFOUND, INTERSECTION_ON_VERTEX, INTERSECTION_ON_EDGE };
114 FindVertexIdxResult () : m_resultType(NOTFOUND), m_intersectionPolygonVertexIdx(PolygonVertexIdx_Invalid), m_xIntersection(
KyInt32MAXVAL) {}
116 void SetVertexIntersection(
KyInt32 xIntersection, PolygonVertexIdx intersectionPolygonVertexIdx)
118 m_resultType = INTERSECTION_ON_VERTEX;
119 m_xIntersection = xIntersection;
120 m_intersectionPolygonVertexIdx = intersectionPolygonVertexIdx;
123 void SetEdgeIntersection(
const Vec2i& edgeStart,
const Vec2i& edgeEnd, PolygonVertexIdx intersectionPolygonVertexIdx)
125 m_resultType = INTERSECTION_ON_EDGE;
126 m_edgeStart = edgeStart;
128 m_intersectionPolygonVertexIdx = intersectionPolygonVertexIdx;
131 ResultType m_resultType;
132 PolygonVertexIdx m_intersectionPolygonVertexIdx;
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
141 const KyInt32 crossProduct = CrossProduct_15bits(nextPos - currentPos, prevPos - currentPos);
142 return crossProduct > 0 ? PolygonVertex::TYPE_CONVEX : PolygonVertex::TYPE_REFLEX;
145 void FillPolygonVerticesForExterior(PolygonVertexIdx& currentNewPolygonVertexIdx);
146 void FillPolygonVerticesForHole(
const EarClippingTriangulatorInputPolygon& holePolygon, HoleIdxWithMaxXVertexIdx& currentHoleMinX, PolygonVertexIdx& currentNewPolygonVertexIdx);
148 KyResult LinkHoleToExterior(HoleIdxWithMaxXVertexIdx& currentHoleMinX, PolygonVertexIdx& currentNewPolygonVertexIdx);
149 KyUInt32 FindAndClipEar(PolygonVertexIdx& firstValidVertexIdx,
KyUInt32& vertexTestedCount);
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;
157 bool IsPolygonVertexAnEar(
const PolygonVertex* polygonVertex,
KyUInt32& vertexTestedCount)
const;
158 void UpdateVertexConvexStatus(PolygonVertex* polygonVertex);
160 void PrintInputPolygonForDebug();
162 static bool DoesPreviousEdgeIntersectsXAxisBeforeCurrentEdge(
const Vec2i& prevEdgeStart,
const Vec2i& prevEdgeEnd,
const Vec2i& currEdgeStart,
const Vec2i& currEdgeEnd);
165 const EarClippingTriangulatorInputPolygonWithHoles* m_input;
166 DynamicTriangulation* m_output;
167 KyArrayDH<PolygonVertex>* m_polygonVertices;
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