Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/extern/recastnavigation/Detour/Source/DetourStatNavMeshBuilder.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'extern/recastnavigation/Detour/Source/DetourStatNavMeshBuilder.cpp')
-rw-r--r--extern/recastnavigation/Detour/Source/DetourStatNavMeshBuilder.cpp346
1 files changed, 0 insertions, 346 deletions
diff --git a/extern/recastnavigation/Detour/Source/DetourStatNavMeshBuilder.cpp b/extern/recastnavigation/Detour/Source/DetourStatNavMeshBuilder.cpp
deleted file mode 100644
index 2ca455fb53d..00000000000
--- a/extern/recastnavigation/Detour/Source/DetourStatNavMeshBuilder.cpp
+++ /dev/null
@@ -1,346 +0,0 @@
-//
-// Copyright (c) 2009 Mikko Mononen memon@inside.org
-//
-// This software is provided 'as-is', without any express or implied
-// warranty. In no event will the authors be held liable for any damages
-// arising from the use of this software.
-// Permission is granted to anyone to use this software for any purpose,
-// including commercial applications, and to alter it and redistribute it
-// freely, subject to the following restrictions:
-// 1. The origin of this software must not be misrepresented; you must not
-// claim that you wrote the original software. If you use this software
-// in a product, an acknowledgment in the product documentation would be
-// appreciated but is not required.
-// 2. Altered source versions must be plainly marked as such, and must not be
-// misrepresented as being the original software.
-// 3. This notice may not be removed or altered from any source distribution.
-//
-
-#include <math.h>
-#include <stdlib.h>
-#include <string.h>
-#include "DetourStatNavMesh.h"
-
-struct BVItem
-{
- unsigned short bmin[3];
- unsigned short bmax[3];
- int i;
-};
-
-static int compareItemX(const void* va, const void* vb)
-{
- const BVItem* a = (const BVItem*)va;
- const BVItem* b = (const BVItem*)vb;
- if (a->bmin[0] < b->bmin[0])
- return -1;
- if (a->bmin[0] > b->bmin[0])
- return 1;
- return 0;
-}
-
-static int compareItemY(const void* va, const void* vb)
-{
- const BVItem* a = (const BVItem*)va;
- const BVItem* b = (const BVItem*)vb;
- if (a->bmin[1] < b->bmin[1])
- return -1;
- if (a->bmin[1] > b->bmin[1])
- return 1;
- return 0;
-}
-
-static int compareItemZ(const void* va, const void* vb)
-{
- const BVItem* a = (const BVItem*)va;
- const BVItem* b = (const BVItem*)vb;
- if (a->bmin[2] < b->bmin[2])
- return -1;
- if (a->bmin[2] > b->bmin[2])
- return 1;
- return 0;
-}
-
-static void calcExtends(BVItem* items, int nitems, int imin, int imax,
- unsigned short* bmin, unsigned short* bmax)
-{
- bmin[0] = items[imin].bmin[0];
- bmin[1] = items[imin].bmin[1];
- bmin[2] = items[imin].bmin[2];
-
- bmax[0] = items[imin].bmax[0];
- bmax[1] = items[imin].bmax[1];
- bmax[2] = items[imin].bmax[2];
-
- for (int i = imin+1; i < imax; ++i)
- {
- const BVItem& it = items[i];
- if (it.bmin[0] < bmin[0]) bmin[0] = it.bmin[0];
- if (it.bmin[1] < bmin[1]) bmin[1] = it.bmin[1];
- if (it.bmin[2] < bmin[2]) bmin[2] = it.bmin[2];
-
- if (it.bmax[0] > bmax[0]) bmax[0] = it.bmax[0];
- if (it.bmax[1] > bmax[1]) bmax[1] = it.bmax[1];
- if (it.bmax[2] > bmax[2]) bmax[2] = it.bmax[2];
- }
-}
-
-inline int longestAxis(unsigned short x, unsigned short y, unsigned short z)
-{
- int axis = 0;
- unsigned short maxVal = x;
- if (y > maxVal)
- {
- axis = 1;
- maxVal = y;
- }
- if (z > maxVal)
- {
- axis = 2;
- maxVal = z;
- }
- return axis;
-}
-
-static void subdivide(BVItem* items, int nitems, int imin, int imax, int& curNode, dtStatBVNode* nodes)
-{
- int inum = imax - imin;
- int icur = curNode;
-
- dtStatBVNode& node = nodes[curNode++];
-
- if (inum == 1)
- {
- // Leaf
- node.bmin[0] = items[imin].bmin[0];
- node.bmin[1] = items[imin].bmin[1];
- node.bmin[2] = items[imin].bmin[2];
-
- node.bmax[0] = items[imin].bmax[0];
- node.bmax[1] = items[imin].bmax[1];
- node.bmax[2] = items[imin].bmax[2];
-
- node.i = items[imin].i;
- }
- else
- {
- // Split
- calcExtends(items, nitems, imin, imax, node.bmin, node.bmax);
-
- int axis = longestAxis(node.bmax[0] - node.bmin[0],
- node.bmax[1] - node.bmin[1],
- node.bmax[2] - node.bmin[2]);
-
- if (axis == 0)
- {
- // Sort along x-axis
- qsort(items+imin, inum, sizeof(BVItem), compareItemX);
- }
- else if (axis == 1)
- {
- // Sort along y-axis
- qsort(items+imin, inum, sizeof(BVItem), compareItemY);
- }
- else
- {
- // Sort along z-axis
- qsort(items+imin, inum, sizeof(BVItem), compareItemZ);
- }
-
- int isplit = imin+inum/2;
-
- // Left
- subdivide(items, nitems, imin, isplit, curNode, nodes);
- // Right
- subdivide(items, nitems, isplit, imax, curNode, nodes);
-
- int iescape = curNode - icur;
- // Negative index means escape.
- node.i = -iescape;
- }
-}
-
-/*static*/ int createBVTree(const unsigned short* verts, const int nverts,
- const unsigned short* polys, const int npolys, const int nvp,
- float cs, float ch,
- int nnodes, dtStatBVNode* nodes)
-{
- // Build tree
- BVItem* items = new BVItem[npolys];
- for (int i = 0; i < npolys; i++)
- {
- BVItem& it = items[i];
- it.i = i+1;
- // Calc polygon bounds.
- const unsigned short* p = &polys[i*nvp*2];
- it.bmin[0] = it.bmax[0] = verts[p[0]*3+0];
- it.bmin[1] = it.bmax[1] = verts[p[0]*3+1];
- it.bmin[2] = it.bmax[2] = verts[p[0]*3+2];
-
- for (int j = 1; j < nvp; ++j)
- {
- if (p[j] == 0xffff) break;
- unsigned short x = verts[p[j]*3+0];
- unsigned short y = verts[p[j]*3+1];
- unsigned short z = verts[p[j]*3+2];
-
- if (x < it.bmin[0]) it.bmin[0] = x;
- if (y < it.bmin[1]) it.bmin[1] = y;
- if (z < it.bmin[2]) it.bmin[2] = z;
-
- if (x > it.bmax[0]) it.bmax[0] = x;
- if (y > it.bmax[1]) it.bmax[1] = y;
- if (z > it.bmax[2]) it.bmax[2] = z;
- }
- // Remap y
- it.bmin[1] = (unsigned short)floorf((float)it.bmin[1]*ch/cs);
- it.bmax[1] = (unsigned short)ceilf((float)it.bmax[1]*ch/cs);
- }
-
- int curNode = 0;
- subdivide(items, npolys, 0, npolys, curNode, nodes);
-
- delete [] items;
-
- return curNode;
-}
-
-
-bool dtCreateNavMeshData(const unsigned short* verts, const int nverts,
- const unsigned short* polys, const int npolys, const int nvp,
- const float* bmin, const float* bmax, float cs, float ch,
- const unsigned short* dmeshes, const float* dverts, const int ndverts,
- const unsigned char* dtris, const int ndtris,
- unsigned char** outData, int* outDataSize)
-{
- if (nvp > DT_STAT_VERTS_PER_POLYGON)
- return false;
- if (nverts >= 0xffff)
- return false;
-
- if (!nverts)
- return false;
- if (!npolys)
- return false;
- if (!dmeshes || !dverts || ! dtris)
- return false;
-
- // Find unique detail vertices.
- int uniqueDetailVerts = 0;
- if (dmeshes)
- {
- for (int i = 0; i < npolys; ++i)
- {
- const unsigned short* p = &polys[i*nvp*2];
- int ndv = dmeshes[i*4+1];
- int nv = 0;
- for (int j = 0; j < nvp; ++j)
- {
- if (p[j] == 0xffff) break;
- nv++;
- }
- ndv -= nv;
- uniqueDetailVerts += ndv;
- }
- }
-
- // Calculate data size
- const int headerSize = sizeof(dtStatNavMeshHeader);
- const int vertsSize = sizeof(float)*3*nverts;
- const int polysSize = sizeof(dtStatPoly)*npolys;
- const int nodesSize = sizeof(dtStatBVNode)*npolys*2;
- const int detailMeshesSize = sizeof(dtStatPolyDetail)*npolys;
- const int detailVertsSize = sizeof(float)*3*uniqueDetailVerts;
- const int detailTrisSize = sizeof(unsigned char)*4*ndtris;
-
- const int dataSize = headerSize + vertsSize + polysSize + nodesSize +
- detailMeshesSize + detailVertsSize + detailTrisSize;
- unsigned char* data = new unsigned char[dataSize];
- if (!data)
- return false;
- memset(data, 0, dataSize);
-
- unsigned char* d = data;
- dtStatNavMeshHeader* header = (dtStatNavMeshHeader*)d; d += headerSize;
- float* navVerts = (float*)d; d += vertsSize;
- dtStatPoly* navPolys = (dtStatPoly*)d; d += polysSize;
- dtStatBVNode* navNodes = (dtStatBVNode*)d; d += nodesSize;
- dtStatPolyDetail* navDMeshes = (dtStatPolyDetail*)d; d += detailMeshesSize;
- float* navDVerts = (float*)d; d += detailVertsSize;
- unsigned char* navDTris = (unsigned char*)d; d += detailTrisSize;
-
- // Store header
- header->magic = DT_STAT_NAVMESH_MAGIC;
- header->version = DT_STAT_NAVMESH_VERSION;
- header->npolys = npolys;
- header->nverts = nverts;
- header->cs = cs;
- header->bmin[0] = bmin[0];
- header->bmin[1] = bmin[1];
- header->bmin[2] = bmin[2];
- header->bmax[0] = bmax[0];
- header->bmax[1] = bmax[1];
- header->bmax[2] = bmax[2];
- header->ndmeshes = dmeshes ? npolys : 0;
- header->ndverts = dmeshes ? uniqueDetailVerts : 0;
- header->ndtris = dmeshes ? ndtris : 0;
-
- // Store vertices
- for (int i = 0; i < nverts; ++i)
- {
- const unsigned short* iv = &verts[i*3];
- float* v = &navVerts[i*3];
- v[0] = bmin[0] + iv[0] * cs;
- v[1] = bmin[1] + iv[1] * ch;
- v[2] = bmin[2] + iv[2] * cs;
- }
-
- // Store polygons
- const unsigned short* src = polys;
- for (int i = 0; i < npolys; ++i)
- {
- dtStatPoly* p = &navPolys[i];
- p->nv = 0;
- for (int j = 0; j < nvp; ++j)
- {
- if (src[j] == 0xffff) break;
- p->v[j] = src[j];
- p->n[j] = src[nvp+j]+1;
- p->nv++;
- }
- src += nvp*2;
- }
-
- header->nnodes = createBVTree(verts, nverts, polys, npolys, nvp,
- cs, ch, npolys*2, navNodes);
-
-
- // Store detail meshes and vertices.
- // The nav polygon vertices are stored as the first vertices on each mesh.
- // We compress the mesh data by skipping them and using the navmesh coordinates.
- unsigned short vbase = 0;
- for (int i = 0; i < npolys; ++i)
- {
- dtStatPolyDetail& dtl = navDMeshes[i];
- const int vb = dmeshes[i*4+0];
- const int ndv = dmeshes[i*4+1];
- const int nv = navPolys[i].nv;
- dtl.vbase = vbase;
- dtl.nverts = ndv-nv;
- dtl.tbase = dmeshes[i*4+2];
- dtl.ntris = dmeshes[i*4+3];
- // Copy vertices except the first 'nv' verts which are equal to nav poly verts.
- if (ndv-nv)
- {
- memcpy(&navDVerts[vbase*3], &dverts[(vb+nv)*3], sizeof(float)*3*(ndv-nv));
- vbase += ndv-nv;
- }
- }
- // Store triangles.
- memcpy(navDTris, dtris, sizeof(unsigned char)*4*ndtris);
-
- *outData = data;
- *outDataSize = dataSize;
-
- return true;
-}
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-14 10:06:46 +0300