gwnavruntime/dynamicnavmesh/tagvolumeslicer.h Source File

tagvolumeslicer.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 
16 #include "../containers/bitfield.h"
17 
18 namespace Kaim
19 {
20 
21 class WorkingMemory;
22 class NavFloor;
23 class Database;
24 class NavFloorBlob;
25 class TagVolume;
26 class DisplayList;
27 
28 enum TagVolumeSlicerResult
29 {
30  TAG_VOLUME_SLICE_RESULT_SKIPPED,
31  TAG_VOLUME_SLICE_RESULT_SUCCESS,
32  TAG_VOLUME_SLICE_RESULT_FAILURE
33 };
34 
35 
36 class ContourLineEdgePiece
37 {
38  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
39 public:
40  ContourLineEdgePiece() : m_parentEdge(nullptr), m_swap(false), m_canceled(false), m_inPolygon(false), m_currentPolygonIdx(0) {}
41 public:
42  EdgePoints m_edgePiece;
43  const ContourLineEdge* m_parentEdge;
44  bool m_swap;
45  bool m_canceled;
46  bool m_inPolygon;
47  KyUInt16 m_currentPolygonIdx;
48 };
49 
50 class TypedIndexedPos
51 {
52 public:
53  enum PointType
54  {
55  TagVolumeEdgeExtremity = /*1 <<*/ 0,
56  LevelLineEdgeExtremity = /*1 <<*/ 1,
57  DiagonalEdgeExtremity = /*1 <<*/ 2,
58  IntersectionWithLevelLineDiagonal = /*1 <<*/ 3,
59  IntersectionWithFloorLink = /*1 <<*/ 4,
60  IntersectionWithBorder = /*1 <<*/ 5,
61 
62  InvalidPointType
63  };
64 
65  TypedIndexedPos() : m_index(KyUInt32MAXVAL), m_pointType(InvalidPointType) {}
66  TypedIndexedPos(const Vec2i& pos, KyUInt32 index, PointType pointType) :
67  m_pos(pos), m_index(index), m_pointType(pointType) {}
68 
69 public:
70  Vec2i m_pos;
71  KyUInt32 m_index;
72  PointType m_pointType;
73 };
74 
75 class TypedIndexedPosSorter
76 {
77 public:
78  bool operator() (const TypedIndexedPos& hotPoint1, const TypedIndexedPos& hotPoint2) const
79  {
80  return hotPoint1.m_pos < hotPoint2.m_pos;
81  }
82 };
83 
84 class UniqueHotPoint
85 {
86 public:
87  UniqueHotPoint() {}
88  UniqueHotPoint(const Vec2i& pos) : m_pos(pos) {}
89 public:
90  Vec2i m_pos;
91 };
92 
93 class TagVolumeSlicer
94 {
95  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
96 
97 public:
98  TagVolumeSlicer(Database* db, NavFloor* navFloor, WorkingMemory* workingMemory) :
99  m_database(db), m_navFloor(navFloor), m_workingMemory(workingMemory), m_slicedTagVolumes(nullptr) {}
100 
101 public:
102  TagVolumeSlicerResult SliceTagVolumeAccordingToAltitudes(const TagVolume* tagVolume, KyArray<KyArrayPOD<Vec2i> >& slicedTagVolumes, DisplayList* displayList);
103 
104 private:
105  enum InternalResult
106  {
107  Stop_Failure,
108  Stop_SkipTagVolume,
109  Stop_KeepTagVolumeContour,
110  KeppGoingOn
111  };
112  void Clear();
113 
114  KyResult ComputeTagVolumeContour(const TagVolume& tagVolume);
115 
116  KyResult ComputeNavFloorData(WorkingMemArray<PixelBox>& trianglePixelBoxArray, WorkingMemArray<Vec3f>& staticFloatVertices,
117  WorkingMemBitField& triangleVsTagVolumeBoxIntersection);
118 
119  KyResult ExtractLevelLines(const WorkingMemBitField& triangleVsTagVolumeBoxIntersection, const WorkingMemArray<Vec3f>& staticFloatVertices);
120 
121  void ComputeTriangleIndexAndVertexStatusOfTagVolumeVertices(const WorkingMemArray<PixelBox>& trianglePixelBoxArray, const WorkingMemArray<Vec3f>& staticFloatVertices);
122 
123  InternalResult IntersectContourLineWithTagVolume();
124 
125  KyResult BuildPolygons(KyArray<KyArrayPOD<Vec2i> >& result);
126  KyResult BuildPolygonFromTagVolume(KyArray<KyArray<Vec2i> >& result);
127 
128  KyResult MarkAsTreatedPairedLevelLineEdges(BitField& levelLinesIsPaired, KyUInt32& firstNonTVEdge);
129  KyFloat32 GetAltitudeOfPointInTriangle(const Vec2i& tVpixelPos, const WorkingMemArray<Vec3f>& staticFloatVertices, NavTriangleIdx triangleIdx);
130  bool ProjectTagVolumePixelPosInStaticFloor(const WorkingMemArray<PixelBox>& trianglePixelBoxArray, const Vec2i& tVpixelPos,
131  NavTriangleIdx& triangleIdx);
132 
133  void AddTagVolumeEdgesToContourLines();
134  KyResult ComputeAllContourEdgeBBox(WorkingMemArray<Box2i>& edgeBoundingBoxes);
135  void AddAllEdgeExtremitiesToHotPoints(WorkingMemArray<TypedIndexedPos>& hotPoints);
136  KyResult ComputeIntersections(const WorkingMemArray<Box2i>& edgeBoundingBoxes, KyArray<KyArrayPOD<KyUInt32> >& cuts,
137  WorkingMemArray<TypedIndexedPos>& hotPoints);
138 
139  TypedIndexedPos::PointType GetIntersectionPointType(ContourLineEdgeType nonTvEdgeType);
140 
141  KyResult RemoveDuplicatedHotPoints(WorkingMemArray<TypedIndexedPos>& hotPoints, WorkingMemArray<UniqueHotPoint>& uniqueHotPoints, KyArray<KyArrayPOD<KyUInt32> >& cuts);
142  void BreakEdgesOnHotPoints(const WorkingMemArray<Box2i>& edgeBoundingBoxes, WorkingMemArray<UniqueHotPoint>& uniqueHotPoints, KyArray<KyArrayPOD<KyUInt32> >& cuts);
143  void SortCuts(const WorkingMemArray<UniqueHotPoint>& uniqueHotPoints, KyArray<KyArrayPOD<KyUInt32> >& cuts);
144  void BuildFinalTagVolumeBrokenContour(const WorkingMemArray<UniqueHotPoint>& uniqueHotPoints, KyArray<KyArrayPOD<KyUInt32> >& cuts);
145  void BuildContourEdgePiece(const WorkingMemArray<UniqueHotPoint>& uniqueHotPoints, KyArray<KyArrayPOD<KyUInt32> >& cuts);
146 
147  KyResult BuildPolygonsStartingFromTagVolumeEdges(KyUInt32 firstNonTVEdge, KyArray<KyArrayPOD<Vec2i> >& result, BitField& treatedEdges);
148  KyResult BuildOtherPolygons(KyUInt32 firstNonTVEdge, KyArray<KyArrayPOD<Vec2i> >& result, BitField& treatedEdges);
149 
150  void RenderLevelLines(DisplayList* displayList);
151  void RenderBrokenEdges(DisplayList* displayList);
152  void RenderSlicedTagVolumes(const KyArray<KyArrayPOD<Vec2i> >& result, DisplayList* displayList);
153 
154  void PrintTagVolumeForDebug(const TagVolume* tagVolume);
155 private:
156  Database* m_database;
157  NavFloor* m_navFloor;
158  WorkingMemory* m_workingMemory;
159 
160  KyFloat32 m_altMin;
161  KyFloat32 m_altMax;
162  PixelBox m_tagVolumePixelBox;
163  PixelBox m_tagVolumePixelBoxEnlargeOf1;
164  // internal
165  KyArrayPOD<Vec2i> m_tagVolumePixelPos;
166  enum TvAltStatus
167  {
168  TVALTSTATUS_INSIDE,
169  TVALTSTATUS_OUTSIDE,
170  TVALTSTATUS_UNSET
171  };
172 
173  KyArrayPOD<TvAltStatus> m_verticesAltStatus;
174 
175  KyArrayPOD<Vec2i> m_brokenTagVolumePixelPos;
176  KyArray<ContourLineEdge> m_contourLineEdges;
177  KyArray<ContourLineEdgePiece> m_contourLineEdgePiece;
178  KyArray<KyArrayPOD<Vec2i> >* m_slicedTagVolumes;
179  KyUInt16 m_polygonCount;
180 };
181 
182 }
183 
KyUInt32 NavTriangleIdx
An index that uniquely identifies a single triangle within the set of triangles owned by a NavFloor...
Definition: navmeshtypes.h:97
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
Navigation return code class.
Definition: types.h:108
The Autodesk Navigation namespace.
Definition: gamekitcrowddispersion.cpp:17
#define KyUInt32MAXVAL
KyUInt32 max value
Definition: types.h:68
float KyFloat32
float
Definition: types.h:32