gwnavruntime/dynamicnavmesh/navfloorsweepline.h Source File

navfloorsweepline.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 
13 
14 namespace Kaim
15 {
16 class DynamicNavTag;
17 class DisplayList;
18 
19 // This object is used to sweep a plane containing edges belonging to polygons and determine
20 // what's left and right of each edge in terms of polygons.
21 // This algorithm is based on boost polygon approach (http://www.boost.org/doc/libs/1_47_0/libs/polygon/doc/index.htm)
22 // and vatti clipping algorithm (http://en.wikipedia.org/wiki/Vatti_clipping_algorithm)
23 // In order to work properly this algorithm requires that:
24 // 1) Input edges DO NOT intersect except at their endpoints
25 
26 class NavFloorSweepline
27 {
28  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
29 
30 public:
31  typedef SharedPoolList<ScanDataElement>::Iterator ScanDataIterator;
32  typedef SharedPoolList<SweeplineProperty> PropertyList;
33  typedef Pool<PropertyList>::Key PropertyListKey;
34 
35 public:
36  NavFloorSweepline(KyArray<InputEdgePiece>& input, SweepLineOutput& result);
37  ~NavFloorSweepline();
38 
39  KyResult Scan();
40  void SetDebugDisplayList(KyFloat32 rasterPrecision, const Vec2i& cellOffset, DisplayList* displayList)
41  {
42  m_rasterPrecision = rasterPrecision;
43  m_cellOriginOffset = Vec3i(cellOffset.x, cellOffset.y, 0);
44  m_displayList = displayList;
45  }
46 
47  void MergePropertyMaps(PropertyList& mp1, const PropertyList& mp2);
48  void UpdatePropertyList(PropertyList& propertyList, SweeplineProperty& prop_data);
49  KyUInt32 ComputeNavTagIndexFromPropertyList(const PropertyList& propertySet);
50  bool AreListsEquals(const PropertyList& list1, const PropertyList& list2);
51  void TransferContent(PropertyList& list1, PropertyList& list2, bool clearList2 = true);
52 
53 private:
54  void EraseEndEvent(SharedPoolList<Vec2i>::Iterator epqi);
55  void RemoveRetiredEdges();
56 
57  void InsertSortedInScandata(const ScanDataElement& elem);
58  void InsertSortedIfUniqueInEndPointQueue(const Vec2i& elem);
59  ScanDataIterator LowerBoundInScandata(const EdgePoints& refElem);
60 
61  void HandleInputEvents(KyUInt32& currentInputIdx);
62  void InsertAllTheEdgesOfInsertionSetInScanDataListAndEndPointQueue();
63  void WriteOutEdge(const InputEdgePiece& he, const PropertyList& pm_left, const PropertyList& pm_right);
64 
65  void VisualDebugWriteOutEdges(const InputEdgePiece &he, const PropertyList &pm_left, const PropertyList &pm_right);
66 
67  void FilterOutlineEdge(const InputEdgePiece& edge, const PropertyList& left, const PropertyList& right);
68  bool IsEdgeFullyInsideHole(const PropertyList& leftSet, const PropertyList& rightSet);
69  bool IsEdgeInsideFloor(const PropertyList& propertySet);
70  bool IsHalfEdgeInHole(const PropertyList& propertySet);
71  void DebugRender_Scan();
72 
73 
74 private:
75  KyArray<InputEdgePiece>* m_input;
76  SweepLineOutput* m_result;
77 
78  Pool<PropertyList> m_propertyListPool;
79  KyArray<PropertyListKey> m_propertyListKeys;
80  PropertyList::NodePool m_propertyListNodePool;
81 
82  SharedPoolList<ScanDataElement> m_scanData;
83  SharedPoolList<ScanDataElement>::NodePool m_scanDataElementPool;
84 
85  KyInt32 m_currentX;
86  KyInt32 m_justBefore;
87 
88  SharedPoolList<Vec2i> m_endpointQueue;
89  SharedPoolList<Vec2i>::NodePool m_endPointPool;
90 
91  SharedPoolList<ScanDataElement> m_insertionSet; //edge to be inserted after current NavFloorSweepline stop
92 
93  KyArray<ScanDataElement> m_insertion_elements; //edge to be inserted after current NavFloorSweepline stop
94 
95  SharedPoolList<EdgePoints> m_removalSet;
96  SharedPoolList<EdgePoints>::NodePool m_removalSetPool;
97 
98  // For debug draw
99  KyFloat32 m_rasterPrecision;
100  Vec3i m_cellOriginOffset; // retrieved from input when Scan() is called. Used for debug Render
101  DisplayList* m_displayList;
102 };
103 
104 } // namespace Kaim
105 
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
Navigation return code class.
Definition: types.h:108
The Autodesk Navigation namespace.
Definition: gamekitcrowddispersion.cpp:17
std::int32_t KyInt32
int32_t
Definition: types.h:24
float KyFloat32
float
Definition: types.h:32