- reworked conversion to dtStatNavMesh in KX_NavMeshObject to support navigation...
authorNick Samarin <nicks1987@bigmir.net>
Wed, 28 Jul 2010 19:43:05 +0000 (19:43 +0000)
committerNick Samarin <nicks1987@bigmir.net>
Wed, 28 Jul 2010 19:43:05 +0000 (19:43 +0000)
extern/recastnavigation/BlenderNavMesh/NavMeshConversion.cpp [new file with mode: 0644]
extern/recastnavigation/BlenderNavMesh/NavMeshConversion.h [new file with mode: 0644]
extern/recastnavigation/make/msvc_9_0/recastnavigation.vcproj
projectfiles_vc9/blender/blender.sln
projectfiles_vc9/blender/modifiers/modifiers.vcproj
projectfiles_vc9/gameengine/ketsji/KX_ketsji.vcproj
source/blender/modifiers/intern/MOD_navmesh.cpp
source/gameengine/Ketsji/KX_NavMeshObject.cpp

diff --git a/extern/recastnavigation/BlenderNavMesh/NavMeshConversion.cpp b/extern/recastnavigation/BlenderNavMesh/NavMeshConversion.cpp
new file mode 100644 (file)
index 0000000..ed02a27
--- /dev/null
@@ -0,0 +1,406 @@
+/**
+* $Id$ 
+*
+* ***** BEGIN GPL LICENSE BLOCK *****
+*
+* This program is free software; you can redistribute it and/or
+* modify it under the terms of the GNU General Public License
+* as published by the Free Software Foundation; either version 2
+* of the License, or (at your option) any later version.
+*
+* This program is distributed in the hope that it will be useful,
+* but WITHOUT ANY WARRANTY; without even the implied warranty of
+* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+* GNU General Public License for more details.
+*
+* You should have received a copy of the GNU General Public License
+* along with this program; if not, write to the Free Software Foundation,
+* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+*
+* The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
+* All rights reserved.
+*
+* The Original Code is: all of this file.
+*
+* Contributor(s): none yet.
+*
+* ***** END GPL LICENSE BLOCK *****
+*/
+
+#include "NavMeshConversion.h"
+extern "C"{
+#include "BLI_math.h"
+}
+
+int polyNumVerts(const unsigned short* p, const int vertsPerPoly)
+{
+       int nv = 0;
+       for (int i=0; i<vertsPerPoly; i++)
+       {
+               if (p[i]==0xffff)
+                       break;
+               nv++;
+       }
+       return nv;
+}
+
+bool polyIsConvex(const unsigned short* p, const int vertsPerPoly, const float* verts)
+{
+       int nv = polyNumVerts(p, vertsPerPoly);
+       if (nv<3)
+               return false;
+       for (int j=0; j<nv; j++)
+       {
+               const float* v = &verts[3*p[j]];
+               const float* v_next = &verts[3*p[(j+1)%nv]];
+               const float* v_prev = &verts[3*p[(nv+j-1)%nv]];
+               if (!left(v_prev, v, v_next))
+                       return false;
+
+       }
+       return true;
+}
+
+float distPointToSegmentSq(const float* point, const float* a, const float* b)
+{
+       float abx[3], dx[3];
+       vsub(abx, b,a);
+       vsub(dx, point,a);
+       float d = abx[0]*abx[0]+abx[2]*abx[2];
+       float t = abx[0]*dx[0]+abx[2]*dx[2];
+       if (d > 0)
+               t /= d;
+       if (t < 0)
+               t = 0;
+       else if (t > 1)
+               t = 1;
+       dx[0] = a[0] + t*abx[0] - point[0];
+       dx[2] = a[2] + t*abx[2] - point[2];
+       return dx[0]*dx[0] + dx[2]*dx[2];
+}
+
+bool buildRawVertIndicesData(DerivedMesh* dm, int &nverts, float *&verts, 
+                                                                       int &ntris, unsigned short *&tris, int *&trisToFacesMap,
+                                                                       int *&recastData)
+{
+       nverts = dm->getNumVerts(dm);
+       verts = new float[3*nverts];
+       dm->getVertCos(dm, (float(*)[3])verts);
+
+       //flip coordinates
+       for (int vi=0; vi<nverts; vi++)
+       {
+               SWAP(float, verts[3*vi+1], verts[3*vi+2]);
+       }
+
+       //calculate number of tris
+       int nfaces = dm->getNumFaces(dm);
+       MFace *faces = dm->getFaceArray(dm);
+       ntris = nfaces;
+       for (int fi=0; fi<nfaces; fi++)
+       {
+               MFace* face = &faces[fi];
+               if (face->v4)
+                       ntris++;
+       }
+
+       //copy and transform to triangles (reorder on the run)
+       trisToFacesMap = new int[ntris];
+       tris = new unsigned short[3*ntris];
+       unsigned short* tri = tris;
+       int triIdx = 0;
+       for (int fi=0; fi<nfaces; fi++)
+       {
+               MFace* face = &faces[fi];
+               tri[3*triIdx+0] = face->v1;
+               tri[3*triIdx+1] = face->v3;
+               tri[3*triIdx+2] = face->v2;
+               trisToFacesMap[triIdx++]=fi;
+               if (face->v4)
+               {
+                       tri[3*triIdx+0] = face->v1;
+                       tri[3*triIdx+1] = face->v4;
+                       tri[3*triIdx+2] = face->v3;
+                       trisToFacesMap[triIdx++]=fi;
+               }
+       }
+
+       //carefully, recast data is just reference to data in derived mesh
+       recastData = (int*)CustomData_get_layer(&dm->faceData, CD_PROP_INT);
+       return true;
+}
+
+bool buildPolygonsByDetailedMeshes(const int vertsPerPoly, const int npolys, 
+                                                                                 unsigned short* polys, const unsigned short* dmeshes, 
+                                                                                 const float* verts, const unsigned short* dtris, 
+                                                                                 const int* dtrisToPolysMap)
+{
+       bool res = false;
+       int capacity = vertsPerPoly;
+       unsigned short* newPoly =  new unsigned short[capacity];
+       memset(newPoly, 0xff, sizeof(unsigned short)*capacity);
+       for (int polyidx=0; polyidx<npolys; polyidx++)
+       {
+               int nv = 0;
+               //search border 
+               int btri = -1;
+               int bedge = -1;
+               for (int j=0; j<dmeshes[polyidx*4+3] && btri==-1;j++)
+               {
+                       int curpolytri = dmeshes[polyidx*4+2]+j;
+                       for (int k=0; k<3; k++)
+                       {
+                               unsigned short neighbortri = dtris[curpolytri*3*2+3+k];
+                               if ( neighbortri==0xffff || dtrisToPolysMap[neighbortri]!=polyidx+1)
+                               {
+                                       btri = curpolytri;
+                                       bedge = k;
+                                       break;
+                               }
+                       }                                                       
+               }
+               if (btri==-1 || bedge==-1)
+               {
+                       //can't find triangle with border edge
+                       return false;
+               }
+
+               newPoly[nv++] = dtris[btri*3*2+bedge];
+
+               int tri = btri;
+               int edge = (bedge+1)%3;
+               while (tri!=btri || edge!=bedge)
+               {
+                       int neighbortri = dtris[tri*3*2+3+edge];
+                       if (neighbortri==0xffff || dtrisToPolysMap[neighbortri]!=polyidx+1)
+                       {
+                               if (nv==capacity)
+                               {
+                                       capacity += vertsPerPoly;
+                                       unsigned short* newPolyBig =  new unsigned short[capacity];
+                                       memset(newPolyBig, 0xff, sizeof(unsigned short)*capacity);
+                                       memcpy(newPolyBig, newPoly, sizeof(unsigned short)*nv);
+                                       delete newPoly;
+                                       newPoly = newPolyBig;                   
+                               }
+                               newPoly[nv++] = dtris[tri*3*2+edge];
+                               //move to next edge                                     
+                               edge = (edge+1)%3;
+                       }
+                       else
+                       {
+                               //move to next tri
+                               int twinedge = -1;
+                               for (int k=0; k<3; k++)
+                               {
+                                       if (dtris[neighbortri*3*2+3+k] == tri)
+                                       {
+                                               twinedge = k;
+                                               break;
+                                       }
+                               }
+                               if (twinedge==-1)
+                               {
+                                       printf("Converting navmesh: Error! Can't find neighbor edge - invalid adjacency info\n");
+                                       goto returnLabel;                                       
+                               }
+                               tri = neighbortri;
+                               edge = (twinedge+1)%3;
+                       }
+               }
+
+               unsigned short* adjustedPoly = new unsigned short[nv];
+               int adjustedNv = 0;
+               for (size_t i=0; i<(size_t)nv; i++)
+               {
+                       unsigned short prev = newPoly[(nv+i-1)%nv];
+                       unsigned short cur = newPoly[i];
+                       unsigned short next = newPoly[(i+1)%nv];
+                       float distSq = distPointToSegmentSq(&verts[3*cur], &verts[3*prev], &verts[3*next]);
+                       static const float tolerance = 0.001f;
+                       if (distSq>tolerance)
+                               adjustedPoly[adjustedNv++] = cur;
+               }
+               memcpy(newPoly, adjustedPoly, adjustedNv*sizeof(unsigned short));
+               delete adjustedPoly;
+               nv = adjustedNv;
+
+               if (nv<=vertsPerPoly)
+               {
+                       for (int i=0; i<nv; i++)
+                       {
+                               polys[polyidx*vertsPerPoly*2+i] = newPoly[i];
+                       }
+               }
+               else
+               {
+                       int a=0;
+               }
+       }
+       res = true;
+
+returnLabel:
+       delete newPoly;
+       return true;
+}
+
+struct SortContext
+{
+       const int* recastData;
+       const int* trisToFacesMap;
+};
+static int compareByData(void* data, const void * a, const void * b){
+       SortContext* context = (SortContext*)data;
+       return ( context->recastData[context->trisToFacesMap[*(int*)a]] - 
+               context->recastData[context->trisToFacesMap[*(int*)b]] );
+}
+
+bool buildNavMeshData(const int nverts, const float* verts, 
+                                                        const int ntris, const unsigned short *tris, 
+                                                        const int* recastData, const int* trisToFacesMap,
+                                                        int &ndtris, unsigned short *&dtris,
+                                                        int &npolys, unsigned short *&dmeshes, unsigned short *&polys,
+                                                        int &vertsPerPoly, int *&dtrisToPolysMap, int *&dtrisToTrisMap)
+
+{
+       if (!recastData)
+       {
+               printf("Converting navmesh: Error! Can't find recast custom data\n");
+               return false;
+       }
+
+       //sort the triangles by polygon idx
+       int* trisMapping = new int[ntris];
+       for (int i=0; i<ntris; i++)
+               trisMapping[i]=i;
+       SortContext context;
+       context.recastData = recastData;
+       context.trisToFacesMap = trisToFacesMap;
+       qsort_s(trisMapping, ntris, sizeof(int), compareByData, &context);
+
+       //search first valid triangle - triangle of convex polygon
+       int validTriStart = -1;
+       for (int i=0; i< ntris; i++)
+       {
+               if (recastData[trisToFacesMap[trisMapping[i]]]>0)
+               {
+                       validTriStart = i;
+                       break;
+               }
+       }
+
+       if (validTriStart<0)
+       {
+               printf("Converting navmesh: Error! No valid polygons in mesh\n");
+               delete trisMapping;
+               return false;
+       }
+
+       ndtris = ntris-validTriStart;
+       //fill dtris to faces mapping
+       dtrisToTrisMap = new int[ndtris];
+       memcpy(dtrisToTrisMap, &trisMapping[validTriStart], ndtris*sizeof(int));
+       delete trisMapping; trisMapping=NULL;
+
+       //create detailed mesh triangles  - copy only valid triangles
+       //and reserve memory for adjacency info
+       dtris = new unsigned short[3*2*ndtris];
+       memset(dtris, 0xffff, sizeof(unsigned short)*3*2*ndtris);
+       for (int i=0; i<ndtris; i++)
+       {
+               memcpy(dtris+3*2*i, tris+3*dtrisToTrisMap[i], sizeof(unsigned short)*3);
+       }
+       //create new recast data corresponded to dtris
+       dtrisToPolysMap = new int[ndtris];
+       for (int i=0; i<ndtris; i++)
+       {
+               dtrisToPolysMap[i] = recastData[trisToFacesMap[dtrisToTrisMap[i]]];
+       }
+
+
+       //build adjacency info for detailed mesh triangles
+       buildMeshAdjacency(dtris, ntris, nverts, 3);
+
+       //create detailed mesh description for each navigation polygon
+       npolys = dtrisToPolysMap[ndtris-1];
+       dmeshes = new unsigned short[npolys*4];
+       memset(dmeshes, 0, npolys*4*sizeof(unsigned short));
+       unsigned short *dmesh = NULL;
+       int prevpolyidx = 0;
+       for (int i=0; i<ndtris; i++)
+       {
+               int curpolyidx = dtrisToPolysMap[i];
+               if (curpolyidx!=prevpolyidx)
+               {
+                       if (curpolyidx!=prevpolyidx+1)
+                       {
+                               printf("Converting navmesh: Error! Wrong order of detailed mesh faces\n");
+                               return false;
+                       }
+                       dmesh = dmesh==NULL ? dmeshes : dmesh+4;
+                       dmesh[2] = i;   //tbase
+                       dmesh[3] = 0;   //tnum
+                       prevpolyidx = curpolyidx;
+               }
+               dmesh[3]++;
+       }
+
+       //create navigation polygons
+       vertsPerPoly = 6;
+       polys = new unsigned short[npolys*vertsPerPoly*2];
+       memset(polys, 0xff, sizeof(unsigned short)*vertsPerPoly*2*npolys);
+
+       buildPolygonsByDetailedMeshes(vertsPerPoly, npolys, polys, dmeshes, verts, dtris, dtrisToPolysMap);
+
+       return true;
+}
+
+
+bool buildNavMeshDataByDerivedMesh(DerivedMesh *dm, int& vertsPerPoly, 
+                                                                                 int &nverts, float *&verts,
+                                                                                 int &ndtris, unsigned short *&dtris,
+                                                                                 int& npolys, unsigned short *&dmeshes,
+                                                                                 unsigned short*& polys, int *&dtrisToPolysMap,
+                                                                                 int *&dtrisToTrisMap, int *&trisToFacesMap)
+{
+       bool res = true;
+       int ntris =0, *recastData=NULL;
+       unsigned short *tris=NULL;
+       res = buildRawVertIndicesData(dm, nverts, verts, ntris, tris, trisToFacesMap, recastData);
+       if (!res)
+       {
+               printf("Converting navmesh: Error! Can't get vertices and indices from mesh\n");
+               goto exit;
+       }
+
+       res = buildNavMeshData(nverts, verts, ntris, tris, recastData, trisToFacesMap,
+               ndtris, dtris, npolys, dmeshes,polys, vertsPerPoly, 
+               dtrisToPolysMap, dtrisToTrisMap);
+       if (!res)
+       {
+               printf("Converting navmesh: Error! Can't get vertices and indices from mesh\n");
+               goto exit;
+       }
+
+exit:
+       if (tris)
+               delete tris;
+
+       return res;
+}
+
+int polyFindVertex(const unsigned short* p, const int vertsPerPoly, unsigned short vertexIdx)
+{
+       int res = -1;
+       for(int i=0; i<vertsPerPoly; i++)
+       {
+               if (p[i]==0xffff)
+                       break;
+               if (p[i]==vertexIdx)
+               {
+                       res = i;
+                       break;
+               }
+       }
+       return res;
+}
\ No newline at end of file
diff --git a/extern/recastnavigation/BlenderNavMesh/NavMeshConversion.h b/extern/recastnavigation/BlenderNavMesh/NavMeshConversion.h
new file mode 100644 (file)
index 0000000..5a30d92
--- /dev/null
@@ -0,0 +1,98 @@
+/**
+* $Id$ 
+*
+* ***** BEGIN GPL LICENSE BLOCK *****
+*
+* This program is free software; you can redistribute it and/or
+* modify it under the terms of the GNU General Public License
+* as published by the Free Software Foundation; either version 2
+* of the License, or (at your option) any later version.
+*
+* This program is distributed in the hope that it will be useful,
+* but WITHOUT ANY WARRANTY; without even the implied warranty of
+* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+* GNU General Public License for more details.
+*
+* You should have received a copy of the GNU General Public License
+* along with this program; if not, write to the Free Software Foundation,
+* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+*
+* The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
+* All rights reserved.
+*
+* The Original Code is: all of this file.
+*
+* Contributor(s): none yet.
+*
+* ***** END GPL LICENSE BLOCK *****
+*/
+
+#ifndef NAVMESH_CONVERSION_H
+#define NAVMESH_CONVERSION_H
+
+#include <math.h>
+#include "Recast.h"
+extern "C"{
+#include "DNA_meshdata_types.h"
+#include "BKE_cdderivedmesh.h"
+}
+
+bool buildNavMeshDataByDerivedMesh(DerivedMesh *dm, int& vertsPerPoly, 
+                                                                  int &nverts, float *&verts,
+                                                                  int &ndtris, unsigned short *&dtris,
+                                                                  int& npolys, unsigned short *&dmeshes,
+                                                                  unsigned short*& polys, int *&dtrisToPolysMap,
+                                                                  int *&dtrisToTrisMap, int *&trisToFacesMap);
+
+bool buildRawVertIndicesData(DerivedMesh* dm, int &nverts, float *&verts, 
+                               int &ntris, unsigned short *&tris, int *&trisToFacesMap,
+                               int *&recastData);
+
+bool buildNavMeshData(const int nverts, const float* verts, 
+                                         const int ntris, const unsigned short *tris, 
+                                         const int* recastData, const int* trisToFacesMap,
+                                         int &ndtris, unsigned short *&dtris,
+                                         int &npolys, unsigned short *&dmeshes, unsigned short *&polys,
+                                         int &vertsPerPoly, int *&dtrisToPolysMap, int *&dtrisToTrisMap);
+
+bool buildPolygonsByDetailedMeshes(const int vertsPerPoly, const int npolys, 
+                               unsigned short* polys, const unsigned short* dmeshes, 
+                               const float* verts, const unsigned short* dtris, 
+                               const int* dtrisToPolysMap);
+
+int polyNumVerts(const unsigned short* p, const int vertsPerPoly);
+bool polyIsConvex(const unsigned short* p, const int vertsPerPoly, const float* verts);
+int polyFindVertex(const unsigned short* p, const int vertsPerPoly, unsigned short vertexIdx);
+float distPointToSegmentSq(const float* point, const float* a, const float* b);
+
+
+inline int abs2(int a)
+{
+       return a>=0 ? a: -a;
+}
+
+inline int bit(int a, int b)
+{
+       return (a & (1 << b)) >> b;
+}
+
+inline void intToCol(int i, float* col)
+{
+       int     r = bit(i, 0) + bit(i, 3) * 2 + 1;
+       int     g = bit(i, 1) + bit(i, 4) * 2 + 1;
+       int     b = bit(i, 2) + bit(i, 5) * 2 + 1;
+       col[0] = 1 - r*63.0f/255.0f;
+       col[1] = 1 - g*63.0f/255.0f;
+       col[2] = 1 - b*63.0f/255.0f;
+}
+
+inline float area2(const float* a, const float* b, const float* c)
+{
+       return (b[0] - a[0]) * (c[2] - a[2]) - (c[0] - a[0]) * (b[2] - a[2]);
+}
+inline bool left(const float* a, const float* b, const float* c)
+{
+       return area2(a, b, c) < 0;
+}
+
+#endif //NAVMESH_CONVERSION_H
\ No newline at end of file
index c0f451176c6e9cebed822e3c83e02a7be72b6499..5dfa123e471ef9256180d78fe7c0c83b6b9a66f6 100644 (file)
@@ -41,7 +41,7 @@
                        <Tool\r
                                Name="VCCLCompilerTool"\r
                                Optimization="0"\r
-                               AdditionalIncludeDirectories="../../Recast/Include; ../../Detour/Include"\r
+                               AdditionalIncludeDirectories="../../Recast/Include;../../Detour/Include;../../../../source/blender/makesdna;../../../../source/blender/blenkernel;../../../../source/blender/blenlib"\r
                                PreprocessorDefinitions="WIN32;_DEBUG;_WINDOWS"\r
                                MinimalRebuild="true"\r
                                BasicRuntimeChecks="3"\r
@@ -77,7 +77,7 @@
                        />\r
                        <Tool\r
                                Name="VCPostBuildEventTool"\r
-                               CommandLine="ECHO Copying header files&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\ MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include&#x0D;&#x0A;&#x0D;&#x0A;XCOPY /Y ..\..\Detour\Include\*.h ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include&#x0D;&#x0A;XCOPY /Y ..\..\Recast\Include\*.h ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include&#x0D;&#x0A;&#x0D;&#x0A;ECHO Done"\r
+                               CommandLine="ECHO Copying header files&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\ MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\BlenderNavMesh MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\BlenderNavMesh&#x0D;&#x0A;&#x0D;&#x0A;XCOPY /Y ..\..\Detour\Include\*.h ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include&#x0D;&#x0A;XCOPY /Y ..\..\Recast\Include\*.h ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include&#x0D;&#x0A;XCOPY /Y ..\..\BlenderNavMesh\*.h ..\..\..\..\..\build\msvc_9\extern\recastnavigation\BlenderNavMesh&#x0D;&#x0A;&#x0D;&#x0A;ECHO Done&#x0D;&#x0A;"\r
                        />\r
                </Configuration>\r
                <Configuration\r
                        <Tool\r
                                Name="VCCLCompilerTool"\r
                                Optimization="2"\r
-                               EnableIntrinsicFunctions="true"\r
-                               AdditionalIncludeDirectories="../../Recast/Include; ../../Detour/Include"\r
+                               EnableIntrinsicFunctions="false"\r
+                               AdditionalIncludeDirectories="../../Recast/Include;../../Detour/Include;../../../../source/blender/makesdna;../../../../source/blender/blenkernel;../../../../source/blender/blenlib"\r
                                PreprocessorDefinitions="WIN32;NDEBUG;_WINDOWS"\r
                                RuntimeLibrary="0"\r
                                EnableFunctionLevelLinking="true"\r
                        />\r
                        <Tool\r
                                Name="VCPostBuildEventTool"\r
-                               CommandLine="ECHO Copying header files&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\ MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include&#x0D;&#x0A;&#x0D;&#x0A;XCOPY /Y ..\..\Detour\Include\*.h ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include&#x0D;&#x0A;XCOPY /Y ..\..\Recast\Include\*.h ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include&#x0D;&#x0A;&#x0D;&#x0A;ECHO Done"\r
+                               CommandLine="ECHO Copying header files&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\ MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\BlenderNavMesh MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\BlenderNavMesh&#x0D;&#x0A;&#x0D;&#x0A;XCOPY /Y ..\..\Detour\Include\*.h ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include&#x0D;&#x0A;XCOPY /Y ..\..\Recast\Include\*.h ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include&#x0D;&#x0A;XCOPY /Y ..\..\BlenderNavMesh\*.h ..\..\..\..\..\build\msvc_9\extern\recastnavigation\BlenderNavMesh&#x0D;&#x0A;&#x0D;&#x0A;ECHO Done&#x0D;&#x0A;"\r
                        />\r
                </Configuration>\r
        </Configurations>\r
                                </File>\r
                        </Filter>\r
                </Filter>\r
+               <Filter\r
+                       Name="BlenderNavMesh"\r
+                       >\r
+                       <File\r
+                               RelativePath="..\..\BlenderNavMesh\NavMeshConversion.cpp"\r
+                               >\r
+                       </File>\r
+                       <File\r
+                               RelativePath="..\..\BlenderNavMesh\NavMeshConversion.h"\r
+                               >\r
+                       </File>\r
+               </Filter>\r
        </Files>\r
        <Globals>\r
        </Globals>\r
index c9cc7fa20b4378687a805060f720458d6a641250..5051332afc1b406814e63e63d187a66e940143e1 100644 (file)
@@ -185,6 +185,9 @@ EndProject
 Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "KX_converter", "..\gameengine\converter\KX_converter.vcproj", "{F90BD995-FFA4-4B18-81E8-FA4322C939E8}"\r
 EndProject\r
 Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "KX_ketsji", "..\gameengine\ketsji\KX_ketsji.vcproj", "{E645CC32-4823-463E-82F0-46ADDE664018}"\r
+       ProjectSection(ProjectDependencies) = postProject\r
+               {FB55B14E-D38E-4D04-BA7B-748EBC97FDB6} = {FB55B14E-D38E-4D04-BA7B-748EBC97FDB6}\r
+       EndProjectSection\r
 EndProject\r
 Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "KX_network", "..\gameengine\ketsji\network\KX_network.vcproj", "{6E24BF09-9653-4166-A871-F65CC9E98A9B}"\r
 EndProject\r
@@ -340,6 +343,9 @@ EndProject
 Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "BF_collada", "collada\BF_collada.vcproj", "{76D3102B-7DD2-8BA1-034A-8B19FE2897C2}"\r
 EndProject\r
 Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "BL_modifiers", "modifiers\modifiers.vcproj", "{7CB0C521-91E0-40CE-A7C4-45FEA7ABE8BC}"\r
+       ProjectSection(ProjectDependencies) = postProject\r
+               {FB55B14E-D38E-4D04-BA7B-748EBC97FDB6} = {FB55B14E-D38E-4D04-BA7B-748EBC97FDB6}\r
+       EndProjectSection\r
 EndProject\r
 Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "EXT_recastnavigation", "..\..\extern\recastnavigation\make\msvc_9_0\recastnavigation.vcproj", "{FB55B14E-D38E-4D04-BA7B-748EBC97FDB6}"\r
 EndProject\r
index f47c3ec00ca59e79ea212fb7fba90b5e06a5e6b7..c994e838dc98cd1ee38f43e91ce865c3a0dcc476 100644 (file)
                        <Tool\r
                                Name="VCCLCompilerTool"\r
                                Optimization="0"\r
-                               AdditionalIncludeDirectories="..\..\..\..\lib\windows\zlib\include;..\..\..\..\build\msvc_9\intern\bsp\include;..\..\..\..\build\msvc_9\intern\guardedalloc\include;..\..\..\..\build\msvc_9\intern\decimation\include;..\..\..\..\build\msvc_9\intern\elbeem\include;..\..\..\..\build\msvc_9\intern\iksolver\include;..\..\..\source\blender\blenlib;..\..\..\source\blender\blenkernel;..\..\..\source\blender\blenkernel\intern;..\..\..\source\blender\makesdna;..\..\..\source\blender\editors\include;..\..\..\source\blender\gpu;..\..\..\source\blender\modifiers;..\..\..\source\blender\render\extern\include;..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include"\r
+                               AdditionalIncludeDirectories="..\..\..\..\lib\windows\zlib\include;..\..\..\..\build\msvc_9\intern\bsp\include;..\..\..\..\build\msvc_9\intern\guardedalloc\include;..\..\..\..\build\msvc_9\intern\decimation\include;..\..\..\..\build\msvc_9\intern\elbeem\include;..\..\..\..\build\msvc_9\intern\iksolver\include;..\..\..\source\blender\blenlib;..\..\..\source\blender\blenkernel;..\..\..\source\blender\blenkernel\intern;..\..\..\source\blender\makesdna;..\..\..\source\blender\editors\include;..\..\..\source\blender\gpu;..\..\..\source\blender\modifiers;..\..\..\source\blender\render\extern\include;..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include;..\..\..\..\build\msvc_9\extern\recastnavigation\BlenderNavMesh"\r
                                PreprocessorDefinitions="_DEBUG;WIN32;_LIB;WITH_LZO;WITH_LZMA"\r
                                MinimalRebuild="false"\r
                                BasicRuntimeChecks="3"\r
                        <Tool\r
                                Name="VCCLCompilerTool"\r
                                Optimization="2"\r
-                               AdditionalIncludeDirectories="..\..\..\..\lib\windows\zlib\include;..\..\..\..\build\msvc_9\intern\bsp\include;..\..\..\..\build\msvc_9\intern\guardedalloc\include;..\..\..\..\build\msvc_9\intern\decimation\include;..\..\..\..\build\msvc_9\intern\elbeem\include;..\..\..\..\build\msvc_9\intern\iksolver\include;..\..\..\source\blender\blenlib;..\..\..\source\blender\blenkernel;..\..\..\source\blender\blenkernel\intern;..\..\..\source\blender\makesdna;..\..\..\source\blender\modifiers;..\..\..\source\blender\render\extern\include;..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include;..\..\..\source\blender\editors\include;..\..\..\source\blender\gpu"\r
+                               AdditionalIncludeDirectories="..\..\..\..\lib\windows\zlib\include;..\..\..\..\build\msvc_9\intern\bsp\include;..\..\..\..\build\msvc_9\intern\guardedalloc\include;..\..\..\..\build\msvc_9\intern\decimation\include;..\..\..\..\build\msvc_9\intern\elbeem\include;..\..\..\..\build\msvc_9\intern\iksolver\include;..\..\..\source\blender\blenlib;..\..\..\source\blender\blenkernel;..\..\..\source\blender\blenkernel\intern;..\..\..\source\blender\makesdna;..\..\..\source\blender\modifiers;..\..\..\source\blender\render\extern\include;..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include;..\..\..\..\build\msvc_9\extern\recastnavigation\BlenderNavMesh;..\..\..\source\blender\editors\include;..\..\..\source\blender\gpu"\r
                                PreprocessorDefinitions="NDEBUG;WIN32;_LIB;WITH_LZO;WITH_LZMA"\r
                                BasicRuntimeChecks="0"\r
                                RuntimeLibrary="0"\r
index a4d33fd9d2171ff432df81cacff8a23dc70424e2..28ba0b332fc111e5b91fefb0eff61206df2afd8e 100644 (file)
                        <Tool\r
                                Name="VCCLCompilerTool"\r
                                Optimization="0"\r
-                               AdditionalIncludeDirectories="..\..\..\..\build\msvc_9\intern\string\include;..\..\..\..\build\msvc_9\intern\moto\include;..\..\..\..\build\msvc_9\intern\soundsystem\include;..\..\..\..\build\msvc_9\intern\guardedalloc\include;..\..\..\..\build\msvc_9\extern\bullet\include;..\..\..\..\build\msvc_9\extern\solid\include;..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include;..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include;..\..\..\..\build\msvc_9\extern\glew\include;..\..\..\..\lib\windows\python\include\python3.1;..\..\..\..\lib\windows\sdl\include;..\..\..\source\blender\imbuf;..\..\..\source\blender\include;..\..\..\source\blender\blenlib;..\..\..\source\blender\python;..\..\..\source\blender\python\generic;..\..\..\source\blender\makesdna;..\..\..\source\blender\blenloader;..\..\..\source\blender\blenkernel;..\..\..\source\kernel\gen_system;..\..\..\source\gameengine\physics;..\..\..\source\gameengine\rasterizer;..\..\..\source\gameengine\network;..\..\..\source\gameengine\Converter;..\..\..\source\gameengine\gamelogic;..\..\..\source\gameengine\scenegraph;..\..\..\source\gameengine\expressions;..\..\..\source\gameengine\physics\sumo;..\..\..\source\gameengine\physics\dummy;..\..\..\source\gameengine\physics\BlOde;..\..\..\source\gameengine\ketsji\kxnetwork;..\..\..\source\gameengine\physics\common;..\..\..\source\gameengine\physics\sumo\include;..\..\..\source\gameengine\physics\common\dummy;..\..\..\source\gameengine\Rasterizer\RAS_OpenGLRasterizer;..\..\..\source\gameengine\physics\sumo\fuzzics\include;..\..\..\source\sumo\include;..\..\..\source\sumo\fuzzics\include;..\..\..\source\gameengine\physics\bullet;..\..\..\source\blender\python\api2_2x;..\..\..\source\blender\gpu;..\..\..\intern\audaspace\intern"\r
+                               AdditionalIncludeDirectories="..\..\..\..\build\msvc_9\intern\string\include;..\..\..\..\build\msvc_9\intern\moto\include;..\..\..\..\build\msvc_9\intern\soundsystem\include;..\..\..\..\build\msvc_9\intern\guardedalloc\include;..\..\..\..\build\msvc_9\extern\bullet\include;..\..\..\..\build\msvc_9\extern\solid\include;..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include;..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include;..\..\..\..\build\msvc_9\extern\recastnavigation\BlenderNavMesh;..\..\..\..\build\msvc_9\extern\glew\include;..\..\..\..\lib\windows\python\include\python3.1;..\..\..\..\lib\windows\sdl\include;..\..\..\source\blender\imbuf;..\..\..\source\blender\include;..\..\..\source\blender\blenlib;..\..\..\source\blender\python;..\..\..\source\blender\python\generic;..\..\..\source\blender\makesdna;..\..\..\source\blender\blenloader;..\..\..\source\blender\blenkernel;..\..\..\source\kernel\gen_system;..\..\..\source\gameengine\physics;..\..\..\source\gameengine\rasterizer;..\..\..\source\gameengine\network;..\..\..\source\gameengine\Converter;..\..\..\source\gameengine\gamelogic;..\..\..\source\gameengine\scenegraph;..\..\..\source\gameengine\expressions;..\..\..\source\gameengine\physics\sumo;..\..\..\source\gameengine\physics\dummy;..\..\..\source\gameengine\physics\BlOde;..\..\..\source\gameengine\ketsji\kxnetwork;..\..\..\source\gameengine\physics\common;..\..\..\source\gameengine\physics\sumo\include;..\..\..\source\gameengine\physics\common\dummy;..\..\..\source\gameengine\Rasterizer\RAS_OpenGLRasterizer;..\..\..\source\gameengine\physics\sumo\fuzzics\include;..\..\..\source\sumo\include;..\..\..\source\sumo\fuzzics\include;..\..\..\source\gameengine\physics\bullet;..\..\..\source\blender\python\api2_2x;..\..\..\source\blender\gpu;..\..\..\intern\audaspace\intern"\r
                                PreprocessorDefinitions="JANCODEPANCO;WIN32;_LIB;EXP_PYTHON_EMBEDDING;_DEBUG;USE_SUMO_SOLID;WITH_GLEXT;GLEW_STATIC;WITH_FFMPEG"\r
                                BasicRuntimeChecks="3"\r
                                RuntimeLibrary="1"\r
                                Name="VCCLCompilerTool"\r
                                Optimization="2"\r
                                InlineFunctionExpansion="1"\r
-                               AdditionalIncludeDirectories="..\..\..\..\build\msvc_9\intern\string\include;..\..\..\..\build\msvc_9\intern\moto\include;..\..\..\..\build\msvc_9\intern\soundsystem\include;..\..\..\..\build\msvc_9\intern\guardedalloc\include;..\..\..\..\build\msvc_9\extern\bullet\include;..\..\..\..\build\msvc_9\extern\solid\include;..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include;..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include;..\..\..\..\build\msvc_9\extern\glew\include;..\..\..\..\lib\windows\python\include\python3.1;..\..\..\..\lib\windows\sdl\include;..\..\..\source\blender\imbuf;..\..\..\source\blender\include;..\..\..\source\blender\blenlib;..\..\..\source\blender\python;..\..\..\source\blender\python\generic;..\..\..\source\blender\makesdna;..\..\..\source\blender\blenloader;..\..\..\source\blender\blenkernel;..\..\..\source\kernel\gen_system;..\..\..\source\gameengine\physics;..\..\..\source\gameengine\rasterizer;..\..\..\source\gameengine\network;..\..\..\source\gameengine\Converter;..\..\..\source\gameengine\gamelogic;..\..\..\source\gameengine\scenegraph;..\..\..\source\gameengine\expressions;..\..\..\source\gameengine\physics\sumo;..\..\..\source\gameengine\physics\dummy;..\..\..\source\gameengine\physics\BlOde;..\..\..\source\gameengine\ketsji\kxnetwork;..\..\..\source\gameengine\physics\common;..\..\..\source\gameengine\physics\sumo\include;..\..\..\source\gameengine\physics\common\dummy;..\..\..\source\gameengine\Rasterizer\RAS_OpenGLRasterizer;..\..\..\source\gameengine\physics\sumo\fuzzics\include;..\..\..\source\sumo\include;..\..\..\source\sumo\fuzzics\include;..\..\..\source\gameengine\physics\bullet;..\..\..\source\blender\python\api2_2x;..\..\..\source\blender\gpu;..\..\..\intern\audaspace\intern"\r
+                               AdditionalIncludeDirectories="..\..\..\..\build\msvc_9\intern\string\include;..\..\..\..\build\msvc_9\intern\moto\include;..\..\..\..\build\msvc_9\intern\soundsystem\include;..\..\..\..\build\msvc_9\intern\guardedalloc\include;..\..\..\..\build\msvc_9\extern\bullet\include;..\..\..\..\build\msvc_9\extern\solid\include;..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include;..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include;..\..\..\..\build\msvc_9\extern\recastnavigation\BlenderNavMesh;..\..\..\..\build\msvc_9\extern\glew\include;..\..\..\..\lib\windows\python\include\python3.1;..\..\..\..\lib\windows\sdl\include;..\..\..\source\blender\imbuf;..\..\..\source\blender\include;..\..\..\source\blender\blenlib;..\..\..\source\blender\python;..\..\..\source\blender\python\generic;..\..\..\source\blender\makesdna;..\..\..\source\blender\blenloader;..\..\..\source\blender\blenkernel;..\..\..\source\kernel\gen_system;..\..\..\source\gameengine\physics;..\..\..\source\gameengine\rasterizer;..\..\..\source\gameengine\network;..\..\..\source\gameengine\Converter;..\..\..\source\gameengine\gamelogic;..\..\..\source\gameengine\scenegraph;..\..\..\source\gameengine\expressions;..\..\..\source\gameengine\physics\sumo;..\..\..\source\gameengine\physics\dummy;..\..\..\source\gameengine\physics\BlOde;..\..\..\source\gameengine\ketsji\kxnetwork;..\..\..\source\gameengine\physics\common;..\..\..\source\gameengine\physics\sumo\include;..\..\..\source\gameengine\physics\common\dummy;..\..\..\source\gameengine\Rasterizer\RAS_OpenGLRasterizer;..\..\..\source\gameengine\physics\sumo\fuzzics\include;..\..\..\source\sumo\include;..\..\..\source\sumo\fuzzics\include;..\..\..\source\gameengine\physics\bullet;..\..\..\source\blender\python\api2_2x;..\..\..\source\blender\gpu;..\..\..\intern\audaspace\intern"\r
                                PreprocessorDefinitions="NDEBUG;WIN32;_LIB;USE_SUMO_SOLID;WITH_GLEXT;GLEW_STATIC;WITH_FFMPEG"\r
                                StringPooling="true"\r
                                RuntimeLibrary="0"\r
index 6bf2400b3f626a31f2666d93f895b71f5c0bdbbe..8f9142458883ee599bb2dbcc4acc38ce22d67eac 100644 (file)
@@ -27,6 +27,7 @@
 */
 #include <math.h>
 #include "Recast.h"
+#include "NavMeshConversion.h"
 
 extern "C"{
 
@@ -36,399 +37,13 @@ extern "C"{
 #include "BKE_mesh.h"
 #include "BKE_modifier.h"
 #include "BKE_particle.h"
+#include "BKE_customdata.h"
 #include "MEM_guardedalloc.h"
 #include "BIF_gl.h"
 #include "gpu_buffers.h"
 #include "GPU_draw.h"
 #include "UI_resources.h"
 
-//service function
-inline int abs(int a)
-{
-       return a>=0 ? a: -a;
-}
-inline int bit(int a, int b)
-{
-       return (a & (1 << b)) >> b;
-}
-
-inline void intToCol(int i, float* col)
-{
-       int     r = bit(i, 0) + bit(i, 3) * 2 + 1;
-       int     g = bit(i, 1) + bit(i, 4) * 2 + 1;
-       int     b = bit(i, 2) + bit(i, 5) * 2 + 1;
-       col[0] = 1 - r*63.0f/255.0f;
-       col[1] = 1 - g*63.0f/255.0f;
-       col[2] = 1 - b*63.0f/255.0f;
-}
-
-inline float area2(const float* a, const float* b, const float* c)
-{
-       return (b[0] - a[0]) * (c[2] - a[2]) - (c[0] - a[0]) * (b[2] - a[2]);
-}
-inline bool left(const float* a, const float* b, const float* c)
-{
-       return area2(a, b, c) < 0;
-}
-
-inline int polyNumVerts(const unsigned short* p, const int vertsPerPoly)
-{
-       int nv = 0;
-       for (int i=0; i<vertsPerPoly; i++)
-       {
-               if (p[i]==0xffff)
-                       break;
-               nv++;
-       }
-       return nv;
-}
-
-inline bool polyIsConvex(const unsigned short* p, const int vertsPerPoly, const float* verts)
-{
-       int nv = polyNumVerts(p, vertsPerPoly);
-       if (nv<3)
-               return false;
-       for (int j=0; j<nv; j++)
-       {
-               const float* v = &verts[3*p[j]];
-               const float* v_next = &verts[3*p[(j+1)%nv]];
-               const float* v_prev = &verts[3*p[(nv+j-1)%nv]];
-               if (!left(v_prev, v, v_next))
-                       return false;
-
-       }
-       return true;
-}
-
-static float distPointToSegmentSq(const float* point, const float* a, const float* b)
-{
-       float abx[3], dx[3];
-       vsub(abx, b,a);
-       vsub(dx, point,a);
-       float d = abx[0]*abx[0]+abx[2]*abx[2];
-       float t = abx[0]*dx[0]+abx[2]*dx[2];
-       if (d > 0)
-               t /= d;
-       if (t < 0)
-               t = 0;
-       else if (t > 1)
-               t = 1;
-       dx[0] = a[0] + t*abx[0] - point[0];
-       dx[2] = a[2] + t*abx[2] - point[2];
-       return dx[0]*dx[0] + dx[2]*dx[2];
-}
-
-static bool buildRawVertIndicesData(DerivedMesh* dm, int &nverts, float *&verts, 
-                                                                       int &ntris, unsigned short *&tris, int *&trisToFacesMap,
-                                                                       int *&recastData)
-{
-       nverts = dm->getNumVerts(dm);
-       verts = new float[3*nverts];
-       dm->getVertCos(dm, (float(*)[3])verts);
-       
-       //flip coordinates
-       for (int vi=0; vi<nverts; vi++)
-       {
-               SWAP(float, verts[3*vi+1], verts[3*vi+2]);
-       }
-
-       //calculate number of tris
-       int nfaces = dm->getNumFaces(dm);
-       MFace *faces = dm->getFaceArray(dm);
-       ntris = nfaces;
-       for (int fi=0; fi<nfaces; fi++)
-       {
-               MFace* face = &faces[fi];
-               if (face->v4)
-                       ntris++;
-       }
-
-       //copy and transform to triangles (reorder on the run)
-       trisToFacesMap = new int[ntris];
-       tris = new unsigned short[3*ntris];
-       unsigned short* tri = tris;
-       int triIdx = 0;
-       for (int fi=0; fi<nfaces; fi++)
-       {
-               MFace* face = &faces[fi];
-               tri[3*triIdx+0] = face->v1;
-               tri[3*triIdx+1] = face->v3;
-               tri[3*triIdx+2] = face->v2;
-               trisToFacesMap[triIdx++]=fi;
-               if (face->v4)
-               {
-                       tri[3*triIdx+0] = face->v1;
-                       tri[3*triIdx+1] = face->v4;
-                       tri[3*triIdx+2] = face->v2;
-                       trisToFacesMap[triIdx++]=fi;
-               }
-       }
-
-       //carefully, recast data is just reference to data in derived mesh
-       recastData = (int*)CustomData_get_layer(&dm->faceData, CD_PROP_INT);
-       return true;
-}
-
-static bool buildPolygonsByDetailedMeshes(const int vertsPerPoly, const int npolys, 
-                                                                                 unsigned short* polys, const unsigned short* dmeshes, 
-                                                                                 const float* verts, const unsigned short* dtris, 
-                                                                                 const int* dtrisToPolysMap)
-{
-       bool res = false;
-       int capacity = vertsPerPoly;
-       unsigned short* newPoly =  new unsigned short[capacity];
-       memset(newPoly, 0xff, sizeof(unsigned short)*capacity);
-       for (int polyidx=0; polyidx<npolys; polyidx++)
-       {
-               int nv = 0;
-               //search border 
-               int btri = -1;
-               int bedge = -1;
-               for (int j=0; j<dmeshes[polyidx*4+3] && btri==-1;j++)
-               {
-                       int curpolytri = dmeshes[polyidx*4+2]+j;
-                       for (int k=0; k<3; k++)
-                       {
-                               unsigned short neighbortri = dtris[curpolytri*3*2+3+k];
-                               if ( neighbortri==0xffff || dtrisToPolysMap[neighbortri]!=polyidx+1)
-                               {
-                                       btri = curpolytri;
-                                       bedge = k;
-                                       break;
-                               }
-                       }                                                       
-               }
-               if (btri==-1 || bedge==-1)
-               {
-                       //can't find triangle with border edge
-                       return false;
-               }
-
-               newPoly[nv++] = dtris[btri*3*2+bedge];
-
-               int tri = btri;
-               int edge = (bedge+1)%3;
-               while (tri!=btri || edge!=bedge)
-               {
-                       int neighbortri = dtris[tri*3*2+3+edge];
-                       if (neighbortri==0xffff || dtrisToPolysMap[neighbortri]!=polyidx+1)
-                       {
-                               if (nv==capacity)
-                               {
-                                       capacity += vertsPerPoly;
-                                       unsigned short* newPolyBig =  new unsigned short[capacity];
-                                       memset(newPolyBig, 0xff, sizeof(unsigned short)*capacity);
-                                       memcpy(newPolyBig, newPoly, sizeof(unsigned short)*nv);
-                                       delete newPoly;
-                                       newPoly = newPolyBig;                   
-                               }
-                               newPoly[nv++] = dtris[tri*3*2+edge];
-                               //move to next edge                                     
-                               edge = (edge+1)%3;
-                       }
-                       else
-                       {
-                               //move to next tri
-                               int twinedge = -1;
-                               for (int k=0; k<3; k++)
-                               {
-                                       if (dtris[neighbortri*3*2+3+k] == tri)
-                                       {
-                                               twinedge = k;
-                                               break;
-                                       }
-                               }
-                               if (twinedge==-1)
-                               {
-                                       printf("Converting navmesh: Error! Can't find neighbor edge - invalid adjacency info\n");
-                                       goto returnLabel;                                       
-                               }
-                               tri = neighbortri;
-                               edge = (twinedge+1)%3;
-                       }
-               }
-
-               unsigned short* adjustedPoly = new unsigned short[nv];
-               int adjustedNv = 0;
-               for (size_t i=0; i<(size_t)nv; i++)
-               {
-                       unsigned short prev = newPoly[(nv+i-1)%nv];
-                       unsigned short cur = newPoly[i];
-                       unsigned short next = newPoly[(i+1)%nv];
-                       float distSq = distPointToSegmentSq(&verts[3*cur], &verts[3*prev], &verts[3*next]);
-                       static const float tolerance = 0.001f;
-                       if (distSq>tolerance)
-                               adjustedPoly[adjustedNv++] = cur;
-               }
-               memcpy(newPoly, adjustedPoly, adjustedNv*sizeof(unsigned short));
-               delete adjustedPoly;
-               nv = adjustedNv;
-
-               if (nv<=vertsPerPoly)
-               {
-                       for (int i=0; i<nv; i++)
-                       {
-                               polys[polyidx*vertsPerPoly*2+i] = newPoly[i];
-                       }
-               }
-               else
-               {
-                       int a=0;
-               }
-       }
-       res = true;
-
-returnLabel:
-       delete newPoly;
-       return true;
-}
-
-struct SortContext
-{
-       const int* recastData;
-       const int* trisToFacesMap;
-};
-static int compareByData(void* data, const void * a, const void * b){
-       SortContext* context = (SortContext*)data;
-       return ( context->recastData[context->trisToFacesMap[*(int*)a]] - 
-                               context->recastData[context->trisToFacesMap[*(int*)b]] );
-}
-
-static bool buildNavMeshData(const int nverts, const float* verts, 
-                                                       const int ntris, const unsigned short *tris, 
-                                                       const int* recastData, const int* trisToFacesMap,
-                                                       int &ndtris, unsigned short *&dtris,
-                                                       int &npolys, unsigned short *&dmeshes, unsigned short *&polys,
-                                                       int &vertsPerPoly, int *&dtrisToPolysMap, int *&dtrisToTrisMap)
-
-{
-       if (!recastData)
-       {
-               printf("Converting navmesh: Error! Can't find recast custom data\n");
-               return false;
-       }
-
-       //sort the triangles by polygon idx
-       int* trisMapping = new int[ntris];
-       for (int i=0; i<ntris; i++)
-               trisMapping[i]=i;
-       SortContext context;
-       context.recastData = recastData;
-       context.trisToFacesMap = trisToFacesMap;
-       qsort_s(trisMapping, ntris, sizeof(int), compareByData, &context);
-       
-       //search first valid triangle - triangle of convex polygon
-       int validTriStart = -1;
-       for (int i=0; i< ntris; i++)
-       {
-               if (recastData[trisToFacesMap[trisMapping[i]]]>0)
-               {
-                       validTriStart = i;
-                       break;
-               }
-       }
-
-       if (validTriStart<0)
-       {
-               printf("Converting navmesh: Error! No valid polygons in mesh\n");
-               delete trisMapping;
-               return false;
-       }
-
-       ndtris = ntris-validTriStart;
-       //fill dtris to faces mapping
-       dtrisToTrisMap = new int[ndtris];
-       memcpy(dtrisToTrisMap, &trisMapping[validTriStart], ndtris*sizeof(int));
-       delete trisMapping; trisMapping=NULL;
-
-       //create detailed mesh triangles  - copy only valid triangles
-       //and reserve memory for adjacency info
-       dtris = new unsigned short[3*2*ndtris];
-       memset(dtris, 0xffff, sizeof(unsigned short)*3*2*ndtris);
-       for (int i=0; i<ndtris; i++)
-       {
-               memcpy(dtris+3*2*i, tris+3*dtrisToTrisMap[i], sizeof(unsigned short)*3);
-       }
-       //create new recast data corresponded to dtris
-       dtrisToPolysMap = new int[ndtris];
-       for (int i=0; i<ndtris; i++)
-       {
-               dtrisToPolysMap[i] = recastData[trisToFacesMap[dtrisToTrisMap[i]]];
-       }
-       
-       
-       //build adjacency info for detailed mesh triangles
-       buildMeshAdjacency(dtris, ntris, nverts, 3);
-
-       //create detailed mesh description for each navigation polygon
-       npolys = dtrisToPolysMap[ndtris-1];
-       dmeshes = new unsigned short[npolys*4];
-       memset(dmeshes, 0, npolys*4*sizeof(unsigned short));
-       unsigned short *dmesh = NULL;
-       int prevpolyidx = 0;
-       for (int i=0; i<ndtris; i++)
-       {
-               int curpolyidx = dtrisToPolysMap[i];
-               if (curpolyidx!=prevpolyidx)
-               {
-                       if (curpolyidx!=prevpolyidx+1)
-                       {
-                               printf("Converting navmesh: Error! Wrong order of detailed mesh faces\n");
-                               return false;
-                       }
-                       dmesh = dmesh==NULL ? dmeshes : dmesh+4;
-                       dmesh[2] = i;   //tbase
-                       dmesh[3] = 0;   //tnum
-                       prevpolyidx = curpolyidx;
-               }
-               dmesh[3]++;
-       }
-
-       //create navigation polygons
-       vertsPerPoly = 6;
-       polys = new unsigned short[npolys*vertsPerPoly*2];
-       memset(polys, 0xff, sizeof(unsigned short)*vertsPerPoly*2*npolys);
-
-       buildPolygonsByDetailedMeshes(vertsPerPoly, npolys, polys, dmeshes, verts, dtris, dtrisToPolysMap);
-
-       return true;
-}
-
-
-static bool buildNavMeshDataByDerivedMesh(DerivedMesh *dm, int& vertsPerPoly, 
-                                                                                       int &nverts, float *&verts,
-                                                                                       int &ndtris, unsigned short *&dtris,
-                                                                                       int& npolys, unsigned short *&dmeshes,
-                                                                                       unsigned short*& polys, int *&dtrisToPolysMap,
-                                                                                       int *&dtrisToTrisMap, int *&trisToFacesMap)
-{
-       bool res = true;
-       int ntris =0, *recastData=NULL;
-       unsigned short *tris=NULL;
-       res = buildRawVertIndicesData(dm, nverts, verts, ntris, tris, trisToFacesMap, recastData);
-       if (!res)
-       {
-               printf("Converting navmesh: Error! Can't get vertices and indices from mesh\n");
-               goto exit;
-       }
-
-       res = buildNavMeshData(nverts, verts, ntris, tris, recastData, trisToFacesMap,
-                                                       ndtris, dtris, npolys, dmeshes,polys, vertsPerPoly, 
-                                                       dtrisToPolysMap, dtrisToTrisMap);
-       if (!res)
-       {
-               printf("Converting navmesh: Error! Can't get vertices and indices from mesh\n");
-               goto exit;
-       }
-
-exit:
-       if (tris)
-               delete tris;
-
-       return res;
-}
-
-
 static void initData(ModifierData *md)
 {
        NavMeshModifierData *nmmd = (NavMeshModifierData*) md;
index 3d4dcb928a66aaccdc3bb6f435be01827f14b0b6..8ba2f78958bca1c4223b6efeecf99c0ecf9c2d77 100644 (file)
@@ -43,6 +43,7 @@ extern "C" {
 #include "Value.h"
 #include "Recast.h"
 #include "DetourStatNavMeshBuilder.h"
+#include "NavMeshConversion.h"
 #include "KX_ObstacleSimulation.h"
 
 static const int MAX_PATH_LEN = 256;
@@ -69,25 +70,6 @@ inline void flipAxes(float* vec)
 {
        std::swap(vec[1],vec[2]);
 }
-
-static float distPointToSegmentSq(const float* point, const float* a, const float* b)
-{
-       float abx[3], dx[3];
-       vsub(abx, b,a);
-       vsub(dx, point,a);
-       float d = abx[0]*abx[0]+abx[1]*abx[1];
-       float t = abx[0]*dx[0]+abx[1]*dx[1];
-       if (d > 0)
-               t /= d;
-       if (t < 0)
-               t = 0;
-       else if (t > 1)
-               t = 1;
-       dx[0] = a[0] + t*abx[0] - point[0];
-       dx[1] = a[1] + t*abx[1] - point[1];
-       return dx[0]*dx[0] + dx[1]*dx[1];
-}
-
 KX_NavMeshObject::KX_NavMeshObject(void* sgReplicationInfo, SG_Callbacks callbacks)
 :      KX_GameObject(sgReplicationInfo, callbacks)
 ,      m_navMesh(NULL)
@@ -130,253 +112,98 @@ bool KX_NavMeshObject::BuildVertIndArrays(float *&vertices, int& nverts,
        int* recastData = (int*) dm->getFaceDataArray(dm, CD_PROP_INT);
        if (recastData)
        {
-               //create from blender mesh using recast data to build navigation 
-               //polygon mesh from detailed triangle mesh
-               MVert *mvert = dm->getVertArray(dm);
-               MFace *mface = dm->getFaceArray(dm);
-               int numfaces = dm->getNumFaces(dm);
-               int numverts = dm->getNumVerts(dm);
-
-               if (numfaces==0)
-               {
-                       return true;
-               }
-
-               //build detailed mesh adjacency (with triangle reordering)
-               ndtris = numfaces;
-               dtris = new unsigned short[numfaces*3*2];
-               memset(dtris, 0xffff, sizeof(unsigned short)*3*2*numfaces);
-               for (int i=0; i<numfaces;i++)
-               {
-                       MFace* mf = &mface[i];
-                       dtris[i*3*2+0] = mf->v1;
-                       dtris[i*3*2+1] = mf->v3;
-                       dtris[i*3*2+2] = mf->v2;
-                       
-               }
-               buildMeshAdjacency(dtris, numfaces, numverts, 3);
-
-
-               //assumption: detailed mesh triangles are sorted by polygon idx
-               npolys = recastData[numfaces-1]/* + 1*/; //stored indices start from 1
-               
-               dmeshes = new unsigned short[npolys*4];
-               memset(dmeshes, 0, npolys*4*sizeof(unsigned short));
-               unsigned short *dmesh = NULL;
-               int prevpolyidx = -1;
-               for (int i=0; i<numfaces; i++)
+               int *dtrisToPolysMap=NULL, *dtrisToTrisMap=NULL, *trisToFacesMap=NULL;
+               int nAllVerts = 0;
+               float *allVerts = NULL;
+               buildNavMeshDataByDerivedMesh(dm, vertsPerPoly, nAllVerts, allVerts, ndtris, dtris,
+                       npolys, dmeshes, polys, dtrisToPolysMap, dtrisToTrisMap, trisToFacesMap);
+
+               unsigned short *verticesMap = new unsigned short[nAllVerts];
+               memset(verticesMap, 0xffff, sizeof(unsigned short)*nAllVerts);
+               int curIdx = 0;
+               //vertices - mesh verts
+               //iterate over all polys and create map for their vertices first...
+               for (int polyidx=0; polyidx<npolys; polyidx++)
                {
-                       int curpolyidx = recastData[i];
-                       if (curpolyidx!=prevpolyidx)
+                       unsigned short* poly = &polys[polyidx*vertsPerPoly*2];
+                       for (int i=0; i<vertsPerPoly; i++)
                        {
-                               if (curpolyidx!=prevpolyidx+1)
+                               unsigned short idx = poly[i];
+                               if (idx==0xffff)
+                                       break;
+                               if (verticesMap[idx]==0xffff)
                                {
-                                       //error - wrong order of detailed mesh faces
-                                       printf("Converting navmesh: Error! Wrong order of detailed mesh faces\n");
-                                       return false;
+                                       verticesMap[idx] = curIdx++;
                                }
-                               dmesh = dmesh==NULL ? dmeshes : dmesh+4;
-                               dmesh[2] = i;   //tbase
-                               dmesh[3] = 0;   //tnum
-                               prevpolyidx = curpolyidx;
+                               poly[i] = verticesMap[idx];
                        }
-                       dmesh[3]++;
                }
-
-               vertsPerPoly = 6;
-               polys = new unsigned short[npolys*vertsPerPoly*2];
-               memset(polys, 0xff, sizeof(unsigned short)*vertsPerPoly*2*npolys);
-               
-               int curpolytri = 0;
-               
+               nverts = curIdx;
+               //...then iterate over detailed meshes
+               //transform indices to local ones (for each navigation polygon)
                for (int polyidx=0; polyidx<npolys; polyidx++)
                {
-                       vector<unsigned short> poly, tempPoly;
-                       //search border 
-                       int btri = -1;
-                       int bedge = -1;
-                       
-                       for (int j=0; j<dmeshes[polyidx*4+3] && btri==-1;j++)
+                       unsigned short *poly = &polys[polyidx*vertsPerPoly*2];
+                       int nv = polyNumVerts(poly, vertsPerPoly);
+                       unsigned short *dmesh = &dmeshes[4*polyidx];
+                       unsigned short tribase = dmesh[2];
+                       unsigned short trinum = dmesh[3];
+                       unsigned short vbase = curIdx;
+                       for (int j=0; j<trinum; j++)
                        {
-                               int curpolytri = dmeshes[polyidx*4+2]+j;
+                               unsigned short* dtri = &dtris[(tribase+j)*3*2];
                                for (int k=0; k<3; k++)
                                {
-                                       unsigned short neighbortri = dtris[curpolytri*3*2+3+k];
-                                       if ( neighbortri==0xffff || recastData[neighbortri]!=polyidx)
+                                       int newVertexIdx = verticesMap[dtri[k]];
+                                       if (newVertexIdx==0xffff)
                                        {
-                                               btri = curpolytri;
-                                               bedge = k;
-                                               break;
+                                               newVertexIdx = curIdx++;
+                                               verticesMap[dtri[k]] = newVertexIdx;
                                        }
-                               }                                                       
-                       }
-                       if (btri==-1 || bedge==-1)
-                       {
-                               //can't find triangle with border edge
-                               return false;
-                       }
-
-                       poly.push_back(dtris[btri*3*2+bedge]);
-                       //poly.push_back(detailedpolys[btri*3*2+(bedge+1)%3]);
 
-                       int tri = btri;
-                       int edge = (bedge+1)%3;
-                       while (tri!=btri || edge!=bedge)
-                       {
-                               int neighbortri = dtris[tri*3*2+3+edge];
-                               if (neighbortri==0xffff || recastData[neighbortri]!=polyidx)
-                               {
-                                       //add vertex to current edge
-                                       poly.push_back(dtris[tri*3*2+edge]);
-                                       //move to next edge                                     
-                                       edge = (edge+1)%3;
-                               }
-                               else
-                               {
-                                       //move to next tri
-                                       int twinedge = -1;
-                                       for (int k=0; k<3; k++)
+                                       if (newVertexIdx<nverts)
                                        {
-                                               if (dtris[neighbortri*3*2+3+k] == tri)
+                                               //it's polygon vertex ("shared")
+                                               int idxInPoly = polyFindVertex(poly, vertsPerPoly, newVertexIdx);
+                                               if (idxInPoly==-1)
                                                {
-                                                       twinedge = k;
-                                                       break;
+                                                       printf("Building NavMeshObject: Error! Can't find vertex in polygon\n");
+                                                       return false;
                                                }
+                                               dtri[k] = idxInPoly;
                                        }
-                                       if (twinedge==-1)
+                                       else
                                        {
-                                               //can't find neighbor edge - invalid adjacency info
-                                               return false;
+                                               dtri[k] = newVertexIdx - vbase + nv;
                                        }
-                                       tri = neighbortri;
-                                       edge = (twinedge+1)%3;
                                }
                        }
-                       
-                       size_t nv = poly.size();
-                       for (size_t i=0; i<nv; i++)
-                       {
-                               unsigned short prev = poly[(poly.size()+i-1)%nv];
-                               unsigned short cur = poly[i];
-                               unsigned short next = poly[(i+1)%nv];
-                               float distSq = distPointToSegmentSq(mvert[cur].co, mvert[prev].co, mvert[next].co);
-                               static const float tolerance = 0.001f;
-                               if (distSq>tolerance)
-                                       tempPoly.push_back(cur);
-                       }
-                       poly = tempPoly;
-
-                       if (poly.size()>vertsPerPoly)
-                       {
-                               printf("Error! Polygon size exceeds max verts count");
-                               return false;
-                       }
-
-                       for (int i=0; i<poly.size(); i++)
-                       {
-                               polys[polyidx*vertsPerPoly*2+i] = poly[i];
-                       }
+                       dmesh[0] = vbase-nverts; //verts base
+                       dmesh[1] = curIdx-vbase; //verts num
                }
 
-               //assumption: vertices in mesh are stored in following order: 
-               //navigation mesh vertices - unique detailed mesh vertex
-               unsigned short  maxidx = 0;
-               for (int polyidx=0; polyidx<npolys; polyidx++)
-               {
-                       for (int i=0; i<vertsPerPoly; i++)
-                       {
-                               unsigned short idx = polys[polyidx*vertsPerPoly*2+i];
-                               if (idx==0xffff)
-                                       break;
-                               if (idx>maxidx)
-                                       maxidx=idx;
-                       }
-               }
-               
-               //create navigation mesh verts
-               nverts = maxidx+1;
                vertices = new float[nverts*3];
-               for (int vi=0; vi<nverts; vi++)
-               {
-                       MVert *v = &mvert[vi];
-                       copy_v3_v3(&vertices[3*vi], v->co);
-               }
-               
-               //create unique detailed mesh verts
-               ndvertsuniq = numverts - nverts;
+               ndvertsuniq = curIdx - nverts;
                if (ndvertsuniq>0)
                {
                        dvertices = new float[ndvertsuniq*3];
-                       for (int vi=0; vi<ndvertsuniq; vi++)
-                       {
-                               MVert *v = &mvert[nverts+vi];
-                               copy_v3_v3(&dvertices[3*vi], v->co);
-                       }
                }
-
-               for (int polyIdx=0; polyIdx<npolys; polyIdx++)
+               for (int vi=0; vi<nAllVerts; vi++)
                {
-                       unsigned short *dmesh = &dmeshes[4*polyIdx];
-                       unsigned short minvert = 0xffff, maxvert = 0;
-                       for (int j=0; j<dmesh[3]; j++)
+                       int newIdx = verticesMap[vi];
+                       if (newIdx!=0xffff)
                        {
-                               unsigned short* dtri = &dtris[(dmesh[2]+j)*3*2];
-                               for (int k=0; k<3; k++)
+                               if (newIdx<nverts)
                                {
-                                       if (dtri[k]<nverts)
-                                               continue;
-                                       minvert = std::min(minvert, dtri[k]);
-                                       maxvert = std::max(maxvert, dtri[k]);
+                                       //navigation mesh vertex
+                                       memcpy(vertices+3*newIdx, allVerts+3*vi, 3*sizeof(float));
                                }
-                       }
-                       dmesh[0] = minvert; //vbase
-                       dmesh[1] = minvert != 0xffff ? maxvert - minvert + 1 : 0; //vnum
-               }
-
-               //recalculate detailed mesh indices (they must be local)
-               for (int polyIdx=0; polyIdx<npolys; polyIdx++)
-               {
-                       unsigned short * poly = &polys[polyIdx*vertsPerPoly*2];
-                       int nv=0;
-                       for (int vi=0; vi<vertsPerPoly; vi++)
-                       {
-                               if (poly[vi]==0xffff)
-                                       break;
-                               nv++;
-                       }
-                       unsigned short *dmesh = &dmeshes[4*polyIdx];
-                       for (int j=0; j<dmesh[3]; j++)
-                       {
-                               unsigned short* dtri = &dtris[(dmesh[2]+j)*3*2];
-                               for (int k=0; k<3; k++)
+                               else
                                {
-                                       if (dtri[k]<nverts)
-                                       {
-                                               //shared vertex from polygon
-                                               unsigned short idx = 0xffff;
-                                               for (int vi=0; vi<nv; vi++)
-                                               {
-                                                       if (poly[vi]==dtri[k])
-                                                       {
-                                                               idx = vi;
-                                                               break;
-                                                       }
-                                               }
-                                               if (idx==0xffff)
-                                               {
-                                                       printf("Can't find vertex in navigation polygon");
-                                                       return false;
-                                               }
-                                               dtri[k] = idx;
-                                       }
-                                       else
-                                       {
-                                               dtri[k] = dtri[k]-dmesh[0]+nv;
-                                       }
-                               }
+                                       //detailed mesh vertex
+                                       memcpy(dvertices+3*(newIdx-nverts), allVerts+3*vi, 3*sizeof(float));
+                               }                               
                        }
-                       if (dmesh[1]>0)
-                               dmesh[0] -= nverts;
                }
        }
        else
@@ -468,13 +295,16 @@ bool KX_NavMeshObject::BuildNavMesh()
        }
        
        MT_Point3 pos;
-       for (int i=0; i<nverts; i++)
-       {
-               flipAxes(&vertices[i*3]);
-       }
-       for (int i=0; i<ndvertsuniq; i++)
+       if (dmeshes==NULL)
        {
-               flipAxes(&dvertices[i*3]);
+               for (int i=0; i<nverts; i++)
+               {
+                       flipAxes(&vertices[i*3]);
+               }
+               for (int i=0; i<ndvertsuniq; i++)
+               {
+                       flipAxes(&dvertices[i*3]);
+               }
        }
 
        buildMeshAdjacency(polys, npolys, nverts, vertsPerPoly);