Another set of fixes for recats: osx uses different order of arguments for sort_r
[blender.git] / extern / recastnavigation / Detour / Include / DetourStatNavMesh.h
1 //
2 // Copyright (c) 2009 Mikko Mononen memon@inside.org
3 //
4 // This software is provided 'as-is', without any express or implied
5 // warranty.  In no event will the authors be held liable for any damages
6 // arising from the use of this software.
7 // Permission is granted to anyone to use this software for any purpose,
8 // including commercial applications, and to alter it and redistribute it
9 // freely, subject to the following restrictions:
10 // 1. The origin of this software must not be misrepresented; you must not
11 //    claim that you wrote the original software. If you use this software
12 //    in a product, an acknowledgment in the product documentation would be
13 //    appreciated but is not required.
14 // 2. Altered source versions must be plainly marked as such, and must not be
15 //    misrepresented as being the original software.
16 // 3. This notice may not be removed or altered from any source distribution.
17 //
18
19 #ifndef DETOURSTATNAVMESH_H
20 #define DETOURSTATNAVMESH_H
21
22 // Reference to navigation polygon.
23 typedef unsigned short dtStatPolyRef;
24
25 // Maximum number of vertices per navigation polygon.
26 static const int DT_STAT_VERTS_PER_POLYGON = 6;
27
28 // Structure holding the navigation polygon data.
29 struct dtStatPoly
30 {
31         unsigned short v[DT_STAT_VERTS_PER_POLYGON];    // Indices to vertices of the poly.
32         dtStatPolyRef n[DT_STAT_VERTS_PER_POLYGON];             // Refs to neighbours of the poly.
33         unsigned char nv;                                                               // Number of vertices.
34         unsigned char flags;                                                    // Flags (not used).
35 };
36
37 struct dtStatPolyDetail
38 {
39         unsigned short vbase;   // Offset to detail vertex array.
40         unsigned short nverts;  // Number of vertices in the detail mesh.
41         unsigned short tbase;   // Offset to detail triangle array.
42         unsigned short ntris;   // Number of triangles.
43 };
44
45 const int DT_STAT_NAVMESH_MAGIC = (('N'<<24) | ('A'<<16) | ('V'<<8) | 'M');
46 const int DT_STAT_NAVMESH_VERSION = 3;
47
48 struct dtStatBVNode
49 {
50         unsigned short bmin[3], bmax[3];
51         int i;
52 };
53
54 struct dtStatNavMeshHeader
55 {
56         int magic;
57         int version;
58         int npolys;
59         int nverts;
60         int nnodes;
61         int ndmeshes;
62         int ndverts;
63         int ndtris;
64         float cs;
65         float bmin[3], bmax[3];
66         dtStatPoly* polys;
67         float* verts;
68         dtStatBVNode* bvtree;
69         dtStatPolyDetail* dmeshes;
70         float* dverts;
71         unsigned char* dtris;
72 };
73
74 class dtStatNavMesh
75 {
76 public:
77         
78         dtStatNavMesh();
79         ~dtStatNavMesh();
80
81         // Initializes the navmesh with data.
82         // Params:
83         //      data - (in) Pointer to navmesh data.
84         //      dataSize - (in) size of the navmesh data.
85         //      ownsData - (in) Flag indicating if the navmesh should own and delete the data.
86         bool init(unsigned char* data, int dataSize, bool ownsData);
87
88         // Finds the nearest navigation polygon around the center location.
89         // Params:
90         //      center - (in) The center of the search box.
91         //      extents - (in) The extents of the search box.
92         // Returns: Reference identifier for the polygon, or 0 if no polygons found.
93         dtStatPolyRef findNearestPoly(const float* center, const float* extents);
94
95         // Returns polygons which touch the query box.
96         // Params:
97         //      center - (in) the center of the search box.
98         //      extents - (in) the extents of the search box.
99         //      polys - (out) array holding the search result.
100         //      maxPolys - (in) The max number of polygons the polys array can hold.
101         // Returns: Number of polygons in search result array.
102         int queryPolygons(const float* center, const float* extents,
103                                           dtStatPolyRef* polys, const int maxPolys);
104         
105         // Finds path from start polygon to end polygon.
106         // If target polygon canno be reached through the navigation graph,
107         // the last node on the array is nearest node to the end polygon.
108         // Params:
109         //      startRef - (in) ref to path start polygon.
110         //      endRef - (in) ref to path end polygon.
111         //      path - (out) array holding the search result.
112         //      maxPathSize - (in) The max number of polygons the path array can hold.
113         // Returns: Number of polygons in search result array.
114         int findPath(dtStatPolyRef startRef, dtStatPolyRef endRef,
115                                  const float* startPos, const float* endPos,
116                                  dtStatPolyRef* path, const int maxPathSize);
117
118         // Finds a straight path from start to end locations within the corridor
119         // described by the path polygons.
120         // Start and end locations will be clamped on the corridor.
121         // Params:
122         //      startPos - (in) Path start location.
123         //      endPos - (in) Path end location.
124         //      path - (in) Array of connected polygons describing the corridor.
125         //      pathSize - (in) Number of polygons in path array.
126         //      straightPath - (out) Points describing the straight path.
127         //      maxStraightPathSize - (in) The max number of points the straight path array can hold.
128         // Returns: Number of points in the path.
129         int findStraightPath(const float* startPos, const float* endPos,
130                                                  const dtStatPolyRef* path, const int pathSize,
131                                                  float* straightPath, const int maxStraightPathSize);
132
133         // Finds intersection againts walls starting from start pos.
134         // Params:
135         //      startRef - (in) ref to the polygon where the start lies.
136         //      startPos - (in) start position of the query.
137         //      endPos - (in) end position of the query.
138         //      t - (out) hit parameter along the segment, 0 if no hit.
139         //      endRef - (out) ref to the last polygon which was processed.
140         // Returns: Number of polygons in path or 0 if failed.
141         int raycast(dtStatPolyRef startRef, const float* startPos, const float* endPos,
142                                  float& t, dtStatPolyRef* path, const int pathSize);
143         
144         // Returns distance to nearest wall from the specified location.
145         // Params:
146         //      centerRef - (in) ref to the polygon where the center lies.
147         //      centerPos - (in) center if the query circle.
148         //      maxRadius - (in) max search radius.
149         //      hitPos - (out) location of the nearest hit.
150         //      hitNormal - (out) normal of the nearest hit.
151         // Returns: Distance to nearest wall from the test location.
152         float findDistanceToWall(dtStatPolyRef centerRef, const float* centerPos, float maxRadius,
153                                                          float* hitPos, float* hitNormal);
154         
155         // Finds polygons found along the navigation graph which touch the specified circle.
156         // Params:
157         //      centerRef - (in) ref to the polygon where the center lies.
158         //      centerPos - (in) center if the query circle
159         //      radius - (in) radius of the query circle
160         //      resultRef - (out, opt) refs to the polygons touched by the circle.
161         //      resultParent - (out, opt) parent of each result polygon.
162         //      resultCost - (out, opt) search cost at each result polygon.
163         //      maxResult - (int) maximum capacity of search results.
164         // Returns: Number of results.
165         int     findPolysAround(dtStatPolyRef centerRef, const float* centerPos, float radius,
166                                                 dtStatPolyRef* resultRef, dtStatPolyRef* resultParent, float* resultCost,
167                                                 const int maxResult);
168
169         // Returns closest point on navigation polygon.
170         // Params:
171         //      ref - (in) ref to the polygon.
172         //      pos - (in) the point to check.
173         //      closest - (out) closest point.
174         // Returns: true if closest point found.
175         bool closestPointToPoly(dtStatPolyRef ref, const float* pos, float* closest) const;
176
177         // Returns height of the polygon at specified location.
178         // Params:
179         //      ref - (in) ref to the polygon.
180         //      pos - (in) the point where to locate the height.
181         //      height - (out) height at the location.
182         // Returns: true if oer polygon.
183         bool getPolyHeight(dtStatPolyRef ref, const float* pos, float* height) const;
184
185         // Returns pointer to a polygon based on ref.
186         const dtStatPoly* getPolyByRef(dtStatPolyRef ref) const;
187         // Returns polygon index based on ref, or -1 if failed.
188         int getPolyIndexByRef(dtStatPolyRef ref) const;
189         // Returns number of navigation polygons.
190         inline int getPolyCount() const { return m_header ? m_header->npolys : 0; }
191         // Rerturns pointer to specified navigation polygon.
192         inline const dtStatPoly* getPoly(int i) const { return &m_header->polys[i]; }
193         // Returns number of vertices.
194         inline int getVertexCount() const { return m_header ? m_header->nverts : 0; }
195         // Returns pointer to specified vertex.
196         inline const float* getVertex(int i) const { return &m_header->verts[i*3]; }
197         // Returns number of navigation polygons details.
198         inline int getPolyDetailCount() const { return m_header ? m_header->ndmeshes : 0; }
199         // Rerturns pointer to specified navigation polygon detail.
200         const dtStatPolyDetail* getPolyDetail(int i) const { return &m_header->dmeshes[i]; }
201         // Returns pointer to specified vertex.
202         inline const float* getDetailVertex(int i) const { return &m_header->dverts[i*3]; }
203         // Returns pointer to specified vertex.
204         inline const unsigned char* getDetailTri(int i) const { return &m_header->dtris[i*4]; }
205
206         bool isInClosedList(dtStatPolyRef ref) const;
207         
208         int getMemUsed() const;
209
210         inline unsigned char* getData() const { return m_data; }
211         inline int getDataSize() const { return m_dataSize; }
212         inline const dtStatNavMeshHeader* getHeader() const { return m_header; }
213         inline const dtStatBVNode* getBvTreeNodes() const { return m_header ? m_header->bvtree : 0; }
214         inline int getBvTreeNodeCount() const { return m_header ? m_header->nnodes : 0; }
215         
216 private:
217
218         // Copies the locations of vertices of a polygon to an array.
219         int getPolyVerts(dtStatPolyRef ref, float* verts) const;
220         // Returns portal points between two polygons.
221         bool getPortalPoints(dtStatPolyRef from, dtStatPolyRef to, float* left, float* right) const;
222         // Returns edge mid point between two polygons.
223         bool getEdgeMidPoint(dtStatPolyRef from, dtStatPolyRef to, float* mid) const;
224
225         unsigned char* m_data;
226         int m_dataSize;
227         
228         dtStatNavMeshHeader* m_header;
229
230         class dtNodePool* m_nodePool;
231         class dtNodeQueue* m_openList;
232 };
233
234 #endif // DETOURSTATNAVMESH_H