diff options
author | Campbell Barton <ideasman42@gmail.com> | 2011-09-11 03:49:39 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2011-09-11 03:49:39 +0400 |
commit | 75b393612809252349bf4062bc45df14c1a5dfe5 (patch) | |
tree | 12650c13c6e927a9e084491aca3d09b77f4f4974 /source/blender/editors | |
parent | ceb9b237f224a480ef13ca151af07aa2d1e1ea60 (diff) | |
parent | fbf3a76f1d4b50b81334f55efbff7a1e6ba1f413 (diff) |
svn merge -r40075:40104 https://svn.blender.org/svnroot/bf-blender/trunk/blender
Diffstat (limited to 'source/blender/editors')
-rw-r--r-- | source/blender/editors/include/ED_navmesh_conversion.h | 96 | ||||
-rw-r--r-- | source/blender/editors/include/ED_object.h | 4 | ||||
-rw-r--r-- | source/blender/editors/interface/interface_widgets.c | 17 | ||||
-rw-r--r-- | source/blender/editors/object/CMakeLists.txt | 11 | ||||
-rw-r--r-- | source/blender/editors/object/SConscript | 6 | ||||
-rw-r--r-- | source/blender/editors/object/object_intern.h | 5 | ||||
-rw-r--r-- | source/blender/editors/object/object_navmesh.cpp | 628 | ||||
-rw-r--r-- | source/blender/editors/object/object_ops.c | 5 | ||||
-rw-r--r-- | source/blender/editors/space_logic/logic_window.c | 46 | ||||
-rw-r--r-- | source/blender/editors/space_view3d/drawarmature.c | 148 | ||||
-rw-r--r-- | source/blender/editors/util/CMakeLists.txt | 8 | ||||
-rw-r--r-- | source/blender/editors/util/SConscript | 8 | ||||
-rw-r--r-- | source/blender/editors/util/navmesh_conversion.cpp | 454 |
13 files changed, 1345 insertions, 91 deletions
diff --git a/source/blender/editors/include/ED_navmesh_conversion.h b/source/blender/editors/include/ED_navmesh_conversion.h new file mode 100644 index 00000000000..71b60cc4e4a --- /dev/null +++ b/source/blender/editors/include/ED_navmesh_conversion.h @@ -0,0 +1,96 @@ +/** +* $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 + +#ifdef __cplusplus +extern "C" { +#endif + +struct DerivedMesh; + +/* navmesh_conversion.cpp */ +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 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; +} + +#ifdef __cplusplus +} +#endif +#endif //NAVMESH_CONVERSION_H diff --git a/source/blender/editors/include/ED_object.h b/source/blender/editors/include/ED_object.h index 2cda5e070d3..5a2a4765c74 100644 --- a/source/blender/editors/include/ED_object.h +++ b/source/blender/editors/include/ED_object.h @@ -139,8 +139,8 @@ void ED_setflagsLatt(struct Object *obedit, int flag); /* object_modifier.c */ enum { MODIFIER_APPLY_DATA=1, - MODIFIER_APPLY_SHAPE, -} eModifier_Apply_Mode; + MODIFIER_APPLY_SHAPE +}; struct ModifierData *ED_object_modifier_add(struct ReportList *reports, struct Main *bmain, struct Scene *scene, struct Object *ob, const char *name, int type); int ED_object_modifier_remove(struct ReportList *reports, struct Main *bmain, struct Scene *scene, struct Object *ob, struct ModifierData *md); diff --git a/source/blender/editors/interface/interface_widgets.c b/source/blender/editors/interface/interface_widgets.c index c06e26eecaa..d9d75c34a94 100644 --- a/source/blender/editors/interface/interface_widgets.c +++ b/source/blender/editors/interface/interface_widgets.c @@ -79,10 +79,10 @@ /* it has outline, back, and two optional tria meshes */ typedef struct uiWidgetTrias { - int tot; + unsigned int tot; float vec[32][2]; - int (*index)[3]; + unsigned int (*index)[3]; } uiWidgetTrias; @@ -146,7 +146,7 @@ static float jit[8][2]= {{0.468813 , -0.481430}, {-0.155755 , -0.352820}, static float num_tria_vert[3][2]= { {-0.352077, 0.532607}, {-0.352077, -0.549313}, {0.330000, -0.008353}}; -static int num_tria_face[1][3]= { +static unsigned int num_tria_face[1][3]= { {0, 1, 2}}; static float scroll_circle_vert[16][2]= { @@ -155,7 +155,7 @@ static float scroll_circle_vert[16][2]= { {-0.382683, -0.923880}, {0.000000, -1.000000}, {0.382684, -0.923880}, {0.707107, -0.707107}, {0.923880, -0.382684}, {1.000000, -0.000000}, {0.923880, 0.382683}, {0.707107, 0.707107}}; -static int scroll_circle_face[14][3]= { +static unsigned int scroll_circle_face[14][3]= { {0, 1, 2}, {2, 0, 3}, {3, 0, 15}, {3, 15, 4}, {4, 15, 14}, {4, 14, 5}, {5, 14, 13}, {5, 13, 6}, {6, 13, 12}, {6, 12, 7}, {7, 12, 11}, {7, 11, 8}, {8, 11, 10}, {8, 10, 9}}; @@ -163,13 +163,13 @@ static float menu_tria_vert[6][2]= { {-0.41, 0.16}, {0.41, 0.16}, {0, 0.82}, {0, -0.82}, {-0.41, -0.16}, {0.41, -0.16}}; -static int menu_tria_face[2][3]= {{2, 0, 1}, {3, 5, 4}}; +static unsigned int menu_tria_face[2][3]= {{2, 0, 1}, {3, 5, 4}}; static float check_tria_vert[6][2]= { {-0.578579, 0.253369}, {-0.392773, 0.412794}, {-0.004241, -0.328551}, {-0.003001, 0.034320}, {1.055313, 0.864744}, {0.866408, 1.026895}}; -static int check_tria_face[4][3]= { +static unsigned int check_tria_face[4][3]= { {3, 2, 4}, {3, 4, 5}, {1, 0, 3}, {0, 2, 3}}; GLubyte checker_stipple_sml[32*32/8] = @@ -533,12 +533,9 @@ static void widget_scroll_circle(uiWidgetTrias *tria, rcti *rect, float triasize static void widget_trias_draw(uiWidgetTrias *tria) { glEnableClientState(GL_VERTEX_ARRAY); - glEnableClientState(GL_INDEX_ARRAY); - glIndexPointer(GL_INT, 0, tria->index); glVertexPointer(2, GL_FLOAT, 0, tria->vec); - glDrawArrays(GL_TRIANGLES, 0, tria->tot*3); + glDrawElements(GL_TRIANGLES, tria->tot*3, GL_UNSIGNED_INT, tria->index); glDisableClientState(GL_VERTEX_ARRAY); - glDisableClientState(GL_INDEX_ARRAY); } static void widget_menu_trias(uiWidgetTrias *tria, rcti *rect) diff --git a/source/blender/editors/object/CMakeLists.txt b/source/blender/editors/object/CMakeLists.txt index 58496a914cb..27308bc9e07 100644 --- a/source/blender/editors/object/CMakeLists.txt +++ b/source/blender/editors/object/CMakeLists.txt @@ -34,6 +34,7 @@ set(INC ../../render/extern/include ../../windowmanager ../../../../intern/guardedalloc + ../../../../extern/recastnavigation/Recast/Include ) set(INC_SYS @@ -59,8 +60,18 @@ set(SRC object_intern.h ) +if(WITH_GAMEENGINE) + list(APPEND SRC + object_navmesh.cpp + ) +endif() + if(WITH_PYTHON) add_definitions(-DWITH_PYTHON) endif() +if(WITH_GAMEENGINE) + add_definitions(-DWITH_GAMEENGINE) +endif() + blender_add_lib(bf_editor_object "${SRC}" "${INC}" "${INC_SYS}") diff --git a/source/blender/editors/object/SConscript b/source/blender/editors/object/SConscript index d3e7df92471..4607cc4b1bf 100644 --- a/source/blender/editors/object/SConscript +++ b/source/blender/editors/object/SConscript @@ -1,12 +1,13 @@ #!/usr/bin/python Import ('env') -sources = env.Glob('*.c') +sources = env.Glob('*.c') + env.Glob('*.cpp') incs = '../include ../../blenlib ../../blenkernel ../../makesdna ../../imbuf' incs += ' ../../windowmanager #/intern/guardedalloc ../../blenloader' incs += ' ../../makesrna ../../python ../../ikplugin ../../bmesh' incs += ' ../../render/extern/include ../../gpu' # for object_bake.c +incs += ' #extern/recastnavigation/Recast/Include' defs = [] @@ -19,5 +20,8 @@ if env['OURPLATFORM'] in ('win32-vc', 'win32-mingw', 'linuxcross', 'win64-vc'): if env['WITH_BF_PYTHON']: defs.append('WITH_PYTHON') + +if env['WITH_BF_GAMEENGINE']: + defs.append('WITH_GAMEENGINE') env.BlenderLib ( 'bf_editors_object', sources, Split(incs), defs, libtype=['core'], priority=[35] ) diff --git a/source/blender/editors/object/object_intern.h b/source/blender/editors/object/object_intern.h index efcb618b868..44cf3adcd32 100644 --- a/source/blender/editors/object/object_intern.h +++ b/source/blender/editors/object/object_intern.h @@ -224,5 +224,10 @@ void OBJECT_OT_group_remove(struct wmOperatorType *ot); /* object_bake.c */ void OBJECT_OT_bake_image(wmOperatorType *ot); +/* object_navmesh.cpp */ +void OBJECT_OT_create_navmesh(struct wmOperatorType *ot); +void OBJECT_OT_assign_navpolygon(struct wmOperatorType *ot); +void OBJECT_OT_assign_new_navpolygon(struct wmOperatorType *ot); + #endif /* ED_OBJECT_INTERN_H */ diff --git a/source/blender/editors/object/object_navmesh.cpp b/source/blender/editors/object/object_navmesh.cpp new file mode 100644 index 00000000000..d0768d30236 --- /dev/null +++ b/source/blender/editors/object/object_navmesh.cpp @@ -0,0 +1,628 @@ +/** +* $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) 2004 by Blender Foundation +* All rights reserved. +* +* The Original Code is: all of this file. +* +* Contributor(s): none yet. +* +* ***** END GPL LICENSE BLOCK ***** +*/ + +#include <math.h> +#include "Recast.h" + +extern "C" +{ +#include "MEM_guardedalloc.h" + +#include "DNA_scene_types.h" +#include "DNA_object_types.h" +#include "DNA_meshdata_types.h" +#include "DNA_modifier_types.h" +#include "DNA_ID.h" + +#include "BKE_library.h" +#include "BKE_depsgraph.h" +#include "BKE_context.h" +#include "BKE_mesh.h" +#include "BKE_modifier.h" +#include "BKE_scene.h" +#include "BKE_DerivedMesh.h" +#include "BKE_cdderivedmesh.h" +#include "BLI_editVert.h" +#include "BLI_listbase.h" +#include "BLI_utildefines.h" +#include "ED_object.h" +#include "BLI_math_vector.h" + +#include "RNA_access.h" + +#include "ED_mesh.h" + +/*mesh/mesh_intern.h */ +extern struct EditVert *addvertlist(EditMesh *em, float *vec, struct EditVert *example); +extern struct EditFace *addfacelist(EditMesh *em, struct EditVert *v1, struct EditVert *v2, struct EditVert *v3, struct EditVert *v4, struct EditFace *example, struct EditFace *exampleEdges); +extern void free_vertlist(EditMesh *em, ListBase *edve); +extern void free_edgelist(EditMesh *em, ListBase *lb); +extern void free_facelist(EditMesh *em, ListBase *lb); + +#include "WM_api.h" +#include "WM_types.h" + +static void createVertsTrisData(bContext *C, LinkNode* obs, int& nverts, float*& verts, int &ntris, int*& tris) +{ + MVert *mvert; + int nfaces = 0, *tri, i, curnverts, basenverts, curnfaces; + MFace *mface; + float co[3], wco[3]; + Object *ob; + LinkNode *oblink, *dmlink; + DerivedMesh *dm; + Scene* scene = CTX_data_scene(C); + LinkNode* dms = NULL; + + nverts = 0; + ntris = 0; + //calculate number of verts and tris + for (oblink = obs; oblink; oblink = oblink->next) + { + ob = (Object*) oblink->link; + DerivedMesh *dm = mesh_create_derived_no_virtual(scene, ob, NULL, CD_MASK_MESH); + BLI_linklist_append(&dms, (void*)dm); + + nverts += dm->getNumVerts(dm); + nfaces = dm->getNumFaces(dm); + ntris += nfaces; + + //resolve quad faces + mface = dm->getFaceArray(dm); + for (i=0; i<nfaces; i++) + { + MFace* mf = &mface[i]; + if (mf->v4) + ntris+=1; + } + } + + //create data + verts = (float*) MEM_mallocN(sizeof(float)*3*nverts, "verts"); + tris = (int*) MEM_mallocN(sizeof(int)*3*ntris, "faces"); + + basenverts = 0; + tri = tris; + for (oblink = obs, dmlink = dms; oblink && dmlink; + oblink = oblink->next, dmlink = dmlink->next) + { + ob = (Object*) oblink->link; + dm = (DerivedMesh*) dmlink->link; + + curnverts = dm->getNumVerts(dm); + mvert = dm->getVertArray(dm); + //copy verts + for (i=0; i<curnverts; i++) + { + MVert *v = &mvert[i]; + copy_v3_v3(co, v->co); + mul_v3_m4v3(wco, ob->obmat, co); + verts[3*(basenverts+i)+0] = wco[0]; + verts[3*(basenverts+i)+1] = wco[2]; + verts[3*(basenverts+i)+2] = wco[1]; + } + + //create tris + curnfaces = dm->getNumFaces(dm); + mface = dm->getFaceArray(dm); + for (i=0; i<curnfaces; i++) + { + MFace* mf = &mface[i]; + tri[0]= basenverts + mf->v1; tri[1]= basenverts + mf->v3; tri[2]= basenverts + mf->v2; + tri += 3; + if (mf->v4) + { + tri[0]= basenverts + mf->v1; tri[1]= basenverts + mf->v4; tri[2]= basenverts + mf->v3; + tri += 3; + } + } + basenverts += curnverts; + } + + //release derived mesh + for (dmlink = dms; dmlink; dmlink = dmlink->next) + { + dm = (DerivedMesh*) dmlink->link; + dm->release(dm); + } + BLI_linklist_free(dms, NULL); +} + +static bool buildNavMesh(const RecastData& recastParams, int nverts, float* verts, int ntris, int* tris, + rcPolyMesh*& pmesh, rcPolyMeshDetail*& dmesh) +{ + float bmin[3], bmax[3]; + rcHeightfield* solid; + unsigned char *triflags; + rcCompactHeightfield* chf; + rcContourSet *cset; + + rcCalcBounds(verts, nverts, bmin, bmax); + + // + // Step 1. Initialize build config. + // + rcConfig cfg; + memset(&cfg, 0, sizeof(cfg)); + { +/* + float cellsize = 0.3f; + float cellheight = 0.2f; + float agentmaxslope = M_PI/4; + float agentmaxclimb = 0.9f; + float agentheight = 2.0f; + float agentradius = 0.6f; + float edgemaxlen = 12.0f; + float edgemaxerror = 1.3f; + float regionminsize = 50.f; + float regionmergesize = 20.f; + int vertsperpoly = 6; + float detailsampledist = 6.0f; + float detailsamplemaxerror = 1.0f; + cfg.cs = cellsize; + cfg.ch = cellheight; + cfg.walkableSlopeAngle = agentmaxslope/M_PI*180.f; + cfg.walkableHeight = (int)ceilf(agentheight/ cfg.ch); + cfg.walkableClimb = (int)floorf(agentmaxclimb / cfg.ch); + cfg.walkableRadius = (int)ceilf(agentradius / cfg.cs); + cfg.maxEdgeLen = (int)(edgemaxlen/cellsize); + cfg.maxSimplificationError = edgemaxerror; + cfg.minRegionSize = (int)rcSqr(regionminsize); + cfg.mergeRegionSize = (int)rcSqr(regionmergesize); + cfg.maxVertsPerPoly = vertsperpoly; + cfg.detailSampleDist = detailsampledist< 0.9f ? 0 : cellsize * detailsampledist; + cfg.detailSampleMaxError = cellheight * detailsamplemaxerror; +*/ + cfg.cs = recastParams.cellsize; + cfg.ch = recastParams.cellheight; + cfg.walkableSlopeAngle = recastParams.agentmaxslope/((float)M_PI)*180.f; + cfg.walkableHeight = (int)ceilf(recastParams.agentheight/ cfg.ch); + cfg.walkableClimb = (int)floorf(recastParams.agentmaxclimb / cfg.ch); + cfg.walkableRadius = (int)ceilf(recastParams.agentradius / cfg.cs); + cfg.maxEdgeLen = (int)(recastParams.edgemaxlen/recastParams.cellsize); + cfg.maxSimplificationError = recastParams.edgemaxerror; + cfg.minRegionSize = (int)rcSqr(recastParams.regionminsize); + cfg.mergeRegionSize = (int)rcSqr(recastParams.regionmergesize); + cfg.maxVertsPerPoly = recastParams.vertsperpoly; + cfg.detailSampleDist = recastParams.detailsampledist< 0.9f ? 0 : + recastParams.cellsize * recastParams.detailsampledist; + cfg.detailSampleMaxError = recastParams.cellheight * recastParams.detailsamplemaxerror; + + } + + // Set the area where the navigation will be build. + vcopy(cfg.bmin, bmin); + vcopy(cfg.bmax, bmax); + rcCalcGridSize(cfg.bmin, cfg.bmax, cfg.cs, &cfg.width, &cfg.height); + + // + // Step 2. Rasterize input polygon soup. + // + // Allocate voxel heightfield where we rasterize our input data to. + solid = new rcHeightfield; + if (!solid) + return false; + + if (!rcCreateHeightfield(*solid, cfg.width, cfg.height, cfg.bmin, cfg.bmax, cfg.cs, cfg.ch)) + return false; + + // Allocate array that can hold triangle flags. + triflags = (unsigned char*) MEM_mallocN(sizeof(unsigned char)*ntris, "triflags"); + if (!triflags) + return false; + // Find triangles which are walkable based on their slope and rasterize them. + memset(triflags, 0, ntris*sizeof(unsigned char)); + rcMarkWalkableTriangles(cfg.walkableSlopeAngle, verts, nverts, tris, ntris, triflags); + rcRasterizeTriangles(verts, nverts, tris, triflags, ntris, *solid); + MEM_freeN(triflags); + MEM_freeN(verts); + MEM_freeN(tris); + + // + // Step 3. Filter walkables surfaces. + // + rcFilterLedgeSpans(cfg.walkableHeight, cfg.walkableClimb, *solid); + rcFilterWalkableLowHeightSpans(cfg.walkableHeight, *solid); + + // + // Step 4. Partition walkable surface to simple regions. + // + + chf = new rcCompactHeightfield; + if (!chf) + return false; + if (!rcBuildCompactHeightfield(cfg.walkableHeight, cfg.walkableClimb, RC_WALKABLE, *solid, *chf)) + return false; + + delete solid; + + // Prepare for region partitioning, by calculating distance field along the walkable surface. + if (!rcBuildDistanceField(*chf)) + return false; + + // Partition the walkable surface into simple regions without holes. + if (!rcBuildRegions(*chf, cfg.walkableRadius, cfg.borderSize, cfg.minRegionSize, cfg.mergeRegionSize)) + return false; + + // + // Step 5. Trace and simplify region contours. + // + // Create contours. + cset = new rcContourSet; + if (!cset) + return false; + + if (!rcBuildContours(*chf, cfg.maxSimplificationError, cfg.maxEdgeLen, *cset)) + return false; + + // + // Step 6. Build polygons mesh from contours. + // + pmesh = new rcPolyMesh; + if (!pmesh) + return false; + if (!rcBuildPolyMesh(*cset, cfg.maxVertsPerPoly, *pmesh)) + return false; + + + // + // Step 7. Create detail mesh which allows to access approximate height on each polygon. + // + + dmesh = new rcPolyMeshDetail; + if (!dmesh) + return false; + + if (!rcBuildPolyMeshDetail(*pmesh, *chf, cfg.detailSampleDist, cfg.detailSampleMaxError, *dmesh)) + return false; + + delete chf; + delete cset; + + return true; +} + +static Object* createRepresentation(bContext *C, rcPolyMesh*& pmesh, rcPolyMeshDetail*& dmesh, Base* base) +{ + float co[3], rot[3]; + EditMesh *em; + int i,j, k; + unsigned short* v; + int face[3]; + Main *bmain = CTX_data_main(C); + Scene *scene= CTX_data_scene(C); + Object* obedit; + int createob = base==NULL; + zero_v3(co); + zero_v3(rot); + if (createob) + { + //create new object + obedit = ED_object_add_type(C, OB_MESH, co, rot, FALSE, 1); + } + else + { + obedit = base->object; + scene_select_base(scene, base); + copy_v3_v3(obedit->loc, co); + copy_v3_v3(obedit->rot, rot); + } + + ED_object_enter_editmode(C, EM_DO_UNDO|EM_IGNORE_LAYER); + em = BKE_mesh_get_editmesh(((Mesh *)obedit->data)); + + if (!createob) + { + //clear + if(em->verts.first) free_vertlist(em, &em->verts); + if(em->edges.first) free_edgelist(em, &em->edges); + if(em->faces.first) free_facelist(em, &em->faces); + if(em->selected.first) BLI_freelistN(&(em->selected)); + } + + //create verts for polygon mesh + for(i = 0; i < pmesh->nverts; i++) { + v = &pmesh->verts[3*i]; + co[0] = pmesh->bmin[0] + v[0]*pmesh->cs; + co[1] = pmesh->bmin[1] + v[1]*pmesh->ch; + co[2] = pmesh->bmin[2] + v[2]*pmesh->cs; + SWAP(float, co[1], co[2]); + addvertlist(em, co, NULL); + } + + //create custom data layer to save polygon idx + CustomData_add_layer_named(&em->fdata, CD_RECAST, CD_CALLOC, NULL, 0, "recastData"); + + //create verts and faces for detailed mesh + for (i=0; i<dmesh->nmeshes; i++) + { + int uniquevbase = em->totvert; + unsigned short vbase = dmesh->meshes[4*i+0]; + unsigned short ndv = dmesh->meshes[4*i+1]; + unsigned short tribase = dmesh->meshes[4*i+2]; + unsigned short trinum = dmesh->meshes[4*i+3]; + const unsigned short* p = &pmesh->polys[i*pmesh->nvp*2]; + int nv = 0; + for (j = 0; j < pmesh->nvp; ++j) + { + if (p[j] == 0xffff) break; + nv++; + } + //create unique verts + for (j=nv; j<ndv; j++) + { + copy_v3_v3(co, &dmesh->verts[3*(vbase + j)]); + SWAP(float, co[1], co[2]); + addvertlist(em, co, NULL); + } + + EM_init_index_arrays(em, 1, 0, 0); + + //create faces + for (j=0; j<trinum; j++) + { + unsigned char* tri = &dmesh->tris[4*(tribase+j)]; + EditFace* newFace; + for (k=0; k<3; k++) + { + if (tri[k]<nv) + face[k] = p[tri[k]]; //shared vertex + else + face[k] = uniquevbase+tri[k]-nv; //unique vertex + } + newFace = addfacelist(em, EM_get_vert_for_index(face[0]), EM_get_vert_for_index(face[2]), + EM_get_vert_for_index(face[1]), NULL, NULL, NULL); + + //set navigation polygon idx to the custom layer + int* polygonIdx = (int*)CustomData_em_get(&em->fdata, newFace->data, CD_RECAST); + *polygonIdx = i+1; //add 1 to avoid zero idx + } + + EM_free_index_arrays(); + } + + delete pmesh; pmesh = NULL; + delete dmesh; dmesh = NULL; + + BKE_mesh_end_editmesh((Mesh*)obedit->data, em); + + DAG_id_tag_update((ID*)obedit->data, OB_RECALC_DATA); + WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data); + + + ED_object_exit_editmode(C, EM_FREEDATA); + WM_event_add_notifier(C, NC_OBJECT|ND_DRAW, obedit); + + if (createob) + { + obedit->gameflag &= ~OB_COLLISION; + obedit->gameflag |= OB_NAVMESH; + obedit->body_type = OB_BODY_TYPE_NAVMESH; + rename_id((ID *)obedit, "Navmesh"); + } + + ModifierData *md= modifiers_findByType(obedit, eModifierType_NavMesh); + if (!md) + { + ED_object_modifier_add(NULL, bmain, scene, obedit, NULL, eModifierType_NavMesh); + } + + return obedit; +} + +static int create_navmesh_exec(bContext *C, wmOperator *op) +{ + Scene* scene = CTX_data_scene(C); + int nverts, ntris; + float* verts; + int* tris; + rcPolyMesh* pmesh; + rcPolyMeshDetail* dmesh; + LinkNode* obs = NULL; + Base* navmeshBase = NULL; + //CTX_DATA_BEGIN(C, Base*, base, selected_editable_bases) //expand macros to avoid error in convertion from void* + { + ListBase ctx_data_list; + CollectionPointerLink *ctx_link; + CTX_data_selected_editable_bases(C, &ctx_data_list); + for(ctx_link = (CollectionPointerLink *)ctx_data_list.first; + ctx_link; ctx_link = (CollectionPointerLink *)ctx_link->next) { + Base* base= (Base*)ctx_link->ptr.data; + { + if (base->object->body_type==OB_BODY_TYPE_NAVMESH) + { + if (!navmeshBase || base==CTX_data_active_base(C)) + navmeshBase = base; + } + else + BLI_linklist_append(&obs, (void*)base->object); + } + CTX_DATA_END; + createVertsTrisData(C, obs, nverts, verts, ntris, tris); + BLI_linklist_free(obs, NULL); + buildNavMesh(scene->gm.recastData, nverts, verts, ntris, tris, pmesh, dmesh); + createRepresentation(C, pmesh, dmesh, navmeshBase); + + return OPERATOR_FINISHED; +} + +void OBJECT_OT_create_navmesh(wmOperatorType *ot) +{ + /* identifiers */ + ot->name= "Create navigation mesh"; + ot->description= "Create navigation mesh for selected objects"; + ot->idname= "OBJECT_OT_create_navmesh"; + + /* api callbacks */ + ot->exec= create_navmesh_exec; + + /* flags */ + ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO; +} + +static int assign_navpolygon_poll(bContext *C) +{ + Object *ob= (Object *)CTX_data_pointer_get_type(C, "object", &RNA_Object).data; + if (!ob || !ob->data) + return 0; + return (((Mesh*)ob->data)->edit_mesh != NULL); +} + +static int assign_navpolygon_exec(bContext *C, wmOperator *op) +{ + Object *obedit= CTX_data_edit_object(C); + EditMesh *em= BKE_mesh_get_editmesh((Mesh *)obedit->data); + + //do work here + int targetPolyIdx = -1; + EditFace *ef, *efa; + efa = EM_get_actFace(em, 0); + if (efa) + { + if (CustomData_has_layer(&em->fdata, CD_RECAST)) + { + targetPolyIdx = *(int*)CustomData_em_get(&em->fdata, efa->data, CD_RECAST); + targetPolyIdx = targetPolyIdx>=0? targetPolyIdx : -targetPolyIdx; + if (targetPolyIdx>0) + { + //set target poly idx to other selected faces + ef = (EditFace*)em->faces.last; + while(ef) + { + if((ef->f & SELECT )&& ef!=efa) + { + int* recastDataBlock = (int*)CustomData_em_get(&em->fdata, ef->data, CD_RECAST); + *recastDataBlock = targetPolyIdx; + } + ef = ef->prev; + } + } + } + } + + DAG_id_tag_update((ID*)obedit->data, OB_RECALC_DATA); + WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data); + + BKE_mesh_end_editmesh((Mesh*)obedit->data, em); + return OPERATOR_FINISHED; +} + +void OBJECT_OT_assign_navpolygon(struct wmOperatorType *ot) +{ + /* identifiers */ + ot->name= "Assign polygon index"; + ot->description= "Assign polygon index to face by active face"; + ot->idname= "OBJECT_OT_assign_navpolygon"; + + /* api callbacks */ + ot->poll = assign_navpolygon_poll; + ot->exec= assign_navpolygon_exec; + + /* flags */ + ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO; +} + +static int compare(const void * a, const void * b){ + return ( *(int*)a - *(int*)b ); +} +static int findFreeNavPolyIndex(EditMesh* em) +{ + //construct vector of indices + int numfaces = em->totface; + int* indices = new int[numfaces]; + EditFace* ef = (EditFace*)em->faces.last; + int idx = 0; + while(ef) + { + int polyIdx = *(int*)CustomData_em_get(&em->fdata, ef->data, CD_RECAST); + indices[idx] = polyIdx; + idx++; + ef = ef->prev; + } + qsort(indices, numfaces, sizeof(int), compare); + //search first free index + int freeIdx = 1; + for (int i=0; i<numfaces; i++) + { + if (indices[i]==freeIdx) + freeIdx++; + else if (indices[i]>freeIdx) + break; + } + delete indices; + return freeIdx; +} + +static int assign_new_navpolygon_exec(bContext *C, wmOperator *op) +{ + Object *obedit= CTX_data_edit_object(C); + EditMesh *em= BKE_mesh_get_editmesh((Mesh *)obedit->data); + + EditFace *ef; + if (CustomData_has_layer(&em->fdata, CD_RECAST)) + { + int targetPolyIdx = findFreeNavPolyIndex(em); + if (targetPolyIdx>0) + { + //set target poly idx to selected faces + ef = (EditFace*)em->faces.last; + while(ef) + { + if(ef->f & SELECT ) + { + int* recastDataBlock = (int*)CustomData_em_get(&em->fdata, ef->data, CD_RECAST); + *recastDataBlock = targetPolyIdx; + } + ef = ef->prev; + } + } + } + + DAG_id_tag_update((ID*)obedit->data, OB_RECALC_DATA); + WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data); + + BKE_mesh_end_editmesh((Mesh*)obedit->data, em); + return OPERATOR_FINISHED; +} + +void OBJECT_OT_assign_new_navpolygon(struct wmOperatorType *ot) +{ + /* identifiers */ + ot->name= "Assign new polygon index"; + ot->description= "Assign new polygon index to face"; + ot->idname= "OBJECT_OT_assign_new_navpolygon"; + + /* api callbacks */ + ot->poll = assign_navpolygon_poll; + ot->exec= assign_new_navpolygon_exec; + + /* flags */ + ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO; +} +} diff --git a/source/blender/editors/object/object_ops.c b/source/blender/editors/object/object_ops.c index 11d64882f29..7cfc7618415 100644 --- a/source/blender/editors/object/object_ops.c +++ b/source/blender/editors/object/object_ops.c @@ -215,6 +215,11 @@ void ED_operatortypes_object(void) WM_operatortype_append(OBJECT_OT_test_multires); +#ifdef WITH_GAMEENGINE + WM_operatortype_append(OBJECT_OT_create_navmesh); + WM_operatortype_append(OBJECT_OT_assign_navpolygon); + WM_operatortype_append(OBJECT_OT_assign_new_navpolygon); +#endif } void ED_operatormacros_object(void) diff --git a/source/blender/editors/space_logic/logic_window.c b/source/blender/editors/space_logic/logic_window.c index 20b001965aa..43a8747e942 100644 --- a/source/blender/editors/space_logic/logic_window.c +++ b/source/blender/editors/space_logic/logic_window.c @@ -718,6 +718,8 @@ static const char *actuator_name(int type) return "State"; case ACT_ARMATURE: return "Armature"; + case ACT_STEERING: + return "Steering"; } return "unknown"; } @@ -4345,6 +4347,48 @@ static void draw_actuator_visibility(uiLayout *layout, PointerRNA *ptr) uiItemR(row, ptr, "apply_to_children", 0, NULL, ICON_NONE); } +static void draw_actuator_steering(uiLayout *layout, PointerRNA *ptr) +{ + uiLayout *row; + uiLayout *col; + + uiItemR(layout, ptr, "mode", 0, NULL, 0); + uiItemR(layout, ptr, "target", 0, NULL, 0); + uiItemR(layout, ptr, "navmesh", 0, NULL, 0); + + row = uiLayoutRow(layout, 0); + uiItemR(row, ptr, "distance", 0, NULL, 0); + uiItemR(row, ptr, "velocity", 0, NULL, 0); + row = uiLayoutRow(layout, 0); + uiItemR(row, ptr, "acceleration", 0, NULL, 0); + uiItemR(row, ptr, "turn_speed", 0, NULL, 0); + + row = uiLayoutRow(layout, 0); + col = uiLayoutColumn(row, 0); + uiItemR(col, ptr, "facing", 0, NULL, 0); + col = uiLayoutColumn(row, 0); + uiItemR(col, ptr, "facing_axis", 0, NULL, 0); + if (!RNA_boolean_get(ptr, "facing")) + { + uiLayoutSetActive(col, 0); + } + col = uiLayoutColumn(row, 0); + uiItemR(col, ptr, "normal_up", 0, NULL, 0); + if (!RNA_pointer_get(ptr, "navmesh").data) + { + uiLayoutSetActive(col, 0); + } + + row = uiLayoutRow(layout, 0); + uiItemR(row, ptr, "self_terminated", 0, NULL, 0); + if (RNA_enum_get(ptr, "mode")==ACT_STEERING_PATHFOLLOWING) + { + uiItemR(row, ptr, "update_period", 0, NULL, 0); + row = uiLayoutRow(layout, 0); + } + uiItemR(row, ptr, "show_visualization", 0, NULL, 0); +} + static void draw_brick_actuator(uiLayout *layout, PointerRNA *ptr, bContext *C) { uiLayout *box; @@ -4406,6 +4450,8 @@ static void draw_brick_actuator(uiLayout *layout, PointerRNA *ptr, bContext *C) case ACT_VISIBILITY: draw_actuator_visibility(box, ptr); break; + case ACT_STEERING: + draw_actuator_steering(box, ptr); } } diff --git a/source/blender/editors/space_view3d/drawarmature.c b/source/blender/editors/space_view3d/drawarmature.c index ecf5df4af7c..4aec1a8e61c 100644 --- a/source/blender/editors/space_view3d/drawarmature.c +++ b/source/blender/editors/space_view3d/drawarmature.c @@ -85,7 +85,7 @@ enum { PCHAN_COLOR_SPHEREBONE_BASE, /* for the 'stick' of sphere (envelope) bones */ PCHAN_COLOR_SPHEREBONE_END, /* for the ends of sphere (envelope) bones */ PCHAN_COLOR_LINEBONE /* for the middle of line-bones */ -}; +}; /* This function sets the color-set for coloring a certain bone */ static void set_pchan_colorset (Object *ob, bPoseChannel *pchan) @@ -437,43 +437,64 @@ static void draw_bonevert_solid(void) glCallList(displist); } +static float bone_octahedral_verts[6][3]= { + { 0.0f, 0.0f, 0.0f}, + { 0.1f, 0.1f, 0.1f}, + { 0.1f, 0.1f, -0.1f}, + {-0.1f, 0.1f, -0.1f}, + {-0.1f, 0.1f, 0.1f}, + { 0.0f, 1.0f, 0.0f} +}; + +static unsigned int bone_octahedral_wire_sides[8]= {0, 1, 5, 3, 0, 4, 5, 2}; +static unsigned int bone_octahedral_wire_square[8]= {1, 2, 3, 4, 1}; + +static unsigned int bone_octahedral_solid_tris[8][3]= { + {2, 1, 0}, /* bottom */ + {3, 2, 0}, + {4, 3, 0}, + {1, 4, 0}, + + {5, 1, 2}, /* top */ + {5, 2, 3}, + {5, 3, 4}, + {5, 4, 1} +}; + +/* aligned with bone_octahedral_solid_tris */ +static float bone_octahedral_solid_normals[8][3]= { + { 0.70710683f, -0.70710683f, 0.00000000f}, + {-0.00000000f, -0.70710683f, -0.70710683f}, + {-0.70710683f, -0.70710683f, 0.00000000f}, + { 0.00000000f, -0.70710683f, 0.70710683f}, + { 0.99388373f, 0.11043154f, -0.00000000f}, + { 0.00000000f, 0.11043154f, -0.99388373f}, + {-0.99388373f, 0.11043154f, 0.00000000f}, + { 0.00000000f, 0.11043154f, 0.99388373f} +}; + static void draw_bone_octahedral(void) { static GLuint displist=0; if (displist == 0) { - float vec[6][3]; - displist= glGenLists(1); glNewList(displist, GL_COMPILE); - - vec[0][0]= vec[0][1]= vec[0][2]= 0.0f; - vec[5][0]= vec[5][2]= 0.0f; vec[5][1]= 1.0f; - - vec[1][0]= 0.1f; vec[1][2]= 0.1f; vec[1][1]= 0.1f; - vec[2][0]= 0.1f; vec[2][2]= -0.1f; vec[2][1]= 0.1f; - vec[3][0]= -0.1f; vec[3][2]= -0.1f; vec[3][1]= 0.1f; - vec[4][0]= -0.1f; vec[4][2]= 0.1f; vec[4][1]= 0.1f; - + /* Section 1, sides */ - glBegin(GL_LINE_LOOP); - glVertex3fv(vec[0]); - glVertex3fv(vec[1]); - glVertex3fv(vec[5]); - glVertex3fv(vec[3]); - glVertex3fv(vec[0]); - glVertex3fv(vec[4]); - glVertex3fv(vec[5]); - glVertex3fv(vec[2]); - glEnd(); - + glEnableClientState(GL_VERTEX_ARRAY); + glVertexPointer(3, GL_FLOAT, 0, bone_octahedral_verts); + glDrawElements(GL_LINE_LOOP, + sizeof(bone_octahedral_wire_sides)/sizeof(*bone_octahedral_wire_sides), + GL_UNSIGNED_INT, + bone_octahedral_wire_sides); + /* Section 1, square */ - glBegin(GL_LINE_LOOP); - glVertex3fv(vec[1]); - glVertex3fv(vec[2]); - glVertex3fv(vec[3]); - glVertex3fv(vec[4]); - glEnd(); + glDrawElements(GL_LINE_LOOP, + sizeof(bone_octahedral_wire_square)/sizeof(*bone_octahedral_wire_square), + GL_UNSIGNED_INT, + bone_octahedral_wire_square); + glDisableClientState(GL_VERTEX_ARRAY); glEndList(); } @@ -484,59 +505,34 @@ static void draw_bone_octahedral(void) static void draw_bone_solid_octahedral(void) { static GLuint displist=0; - + if (displist == 0) { - float vec[6][3], nor[3]; - + int i; + displist= glGenLists(1); glNewList(displist, GL_COMPILE); - - vec[0][0]= vec[0][1]= vec[0][2]= 0.0f; - vec[5][0]= vec[5][2]= 0.0f; vec[5][1]= 1.0f; - - vec[1][0]= 0.1f; vec[1][2]= 0.1f; vec[1][1]= 0.1f; - vec[2][0]= 0.1f; vec[2][2]= -0.1f; vec[2][1]= 0.1f; - vec[3][0]= -0.1f; vec[3][2]= -0.1f; vec[3][1]= 0.1f; - vec[4][0]= -0.1f; vec[4][2]= 0.1f; vec[4][1]= 0.1f; - - - glBegin(GL_TRIANGLES); - /* bottom */ - normal_tri_v3( nor,vec[2], vec[1], vec[0]); - glNormal3fv(nor); - glVertex3fv(vec[2]); glVertex3fv(vec[1]); glVertex3fv(vec[0]); - - normal_tri_v3( nor,vec[3], vec[2], vec[0]); - glNormal3fv(nor); - glVertex3fv(vec[3]); glVertex3fv(vec[2]); glVertex3fv(vec[0]); - - normal_tri_v3( nor,vec[4], vec[3], vec[0]); - glNormal3fv(nor); - glVertex3fv(vec[4]); glVertex3fv(vec[3]); glVertex3fv(vec[0]); - normal_tri_v3( nor,vec[1], vec[4], vec[0]); - glNormal3fv(nor); - glVertex3fv(vec[1]); glVertex3fv(vec[4]); glVertex3fv(vec[0]); +#if 1 + glBegin(GL_TRIANGLES); + for(i= 0; i < 8; i++) { + glNormal3fv(bone_octahedral_solid_normals[i]); + glVertex3fv(bone_octahedral_verts[bone_octahedral_solid_tris[i][0]]); + glVertex3fv(bone_octahedral_verts[bone_octahedral_solid_tris[i][1]]); + glVertex3fv(bone_octahedral_verts[bone_octahedral_solid_tris[i][2]]); + } - /* top */ - normal_tri_v3( nor,vec[5], vec[1], vec[2]); - glNormal3fv(nor); - glVertex3fv(vec[5]); glVertex3fv(vec[1]); glVertex3fv(vec[2]); - - normal_tri_v3( nor,vec[5], vec[2], vec[3]); - glNormal3fv(nor); - glVertex3fv(vec[5]); glVertex3fv(vec[2]); glVertex3fv(vec[3]); - - normal_tri_v3( nor,vec[5], vec[3], vec[4]); - glNormal3fv(nor); - glVertex3fv(vec[5]); glVertex3fv(vec[3]); glVertex3fv(vec[4]); - - normal_tri_v3( nor,vec[5], vec[4], vec[1]); - glNormal3fv(nor); - glVertex3fv(vec[5]); glVertex3fv(vec[4]); glVertex3fv(vec[1]); - glEnd(); - + +#else /* not working because each vert needs a different normal */ + glEnableClientState(GL_NORMAL_ARRAY); + glEnableClientState(GL_VERTEX_ARRAY); + glNormalPointer(GL_FLOAT, 0, bone_octahedral_solid_normals); + glVertexPointer(3, GL_FLOAT, 0, bone_octahedral_verts); + glDrawElements(GL_TRIANGLES, sizeof(bone_octahedral_solid_tris)/sizeof(unsigned int), GL_UNSIGNED_INT, bone_octahedral_solid_tris); + glDisableClientState(GL_NORMAL_ARRAY); + glDisableClientState(GL_VERTEX_ARRAY); +#endif + glEndList(); } diff --git a/source/blender/editors/util/CMakeLists.txt b/source/blender/editors/util/CMakeLists.txt index 843af272362..c1e618fd4cb 100644 --- a/source/blender/editors/util/CMakeLists.txt +++ b/source/blender/editors/util/CMakeLists.txt @@ -24,6 +24,7 @@ set(INC ../../blenkernel ../../blenlib ../../blenloader + ../../../../extern/recastnavigation/Recast/Include ../../bmesh ../../makesdna ../../makesrna @@ -63,6 +64,7 @@ set(SRC ../include/ED_markers.h ../include/ED_mball.h ../include/ED_mesh.h + ../include/ED_navmesh_conversion.h ../include/ED_node.h ../include/ED_numinput.h ../include/ED_object.h @@ -89,4 +91,10 @@ set(SRC ../include/UI_view2d.h ) +if(WITH_GAMEENGINE) + list(APPEND SRC + navmesh_conversion.cpp + ) +endif() + blender_add_lib(bf_editor_util "${SRC}" "${INC}" "${INC_SYS}") diff --git a/source/blender/editors/util/SConscript b/source/blender/editors/util/SConscript index 2d5ee84333b..04d783e1ee1 100644 --- a/source/blender/editors/util/SConscript +++ b/source/blender/editors/util/SConscript @@ -1,11 +1,15 @@ #!/usr/bin/python Import ('env') -sources = env.Glob('*.c') +sources = env.Glob('*.c') + env.Glob('*.cpp') incs = '../include ../../blenlib ../../blenkernel ../../makesdna ../../imbuf' incs += ' ../../windowmanager #/intern/guardedalloc #/extern/glew/include' incs += ' ../../makesrna ../../bmesh' +incs += ' #extern/recastnavigation/Recast/Include' incs += ' ../../blenloader' -env.BlenderLib ( 'bf_editors_util', sources, Split(incs), [], libtype=['core'], priority=[130] ) +if not env['WITH_BF_GAMEENGINE']: + sources.remove('navmesh_conversion.cpp') + +env.BlenderLib ( 'bf_editors_util', sources, Split(incs), [], libtype=['core','player'], priority=[330,210] ) diff --git a/source/blender/editors/util/navmesh_conversion.cpp b/source/blender/editors/util/navmesh_conversion.cpp new file mode 100644 index 00000000000..8b3fee59e1a --- /dev/null +++ b/source/blender/editors/util/navmesh_conversion.cpp @@ -0,0 +1,454 @@ +/** +* $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 <math.h> +#include "Recast.h" + + +extern "C"{ +#include "ED_navmesh_conversion.h" + +#include "DNA_meshdata_types.h" +#include "BKE_cdderivedmesh.h" +#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); + if (nverts>=0xffff) + { + printf("Converting navmesh: Error! Too many vertices. Max number of vertices %d\n", 0xffff); + return false; + } + 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] = (unsigned short) face->v1; + tri[3*triIdx+1] = (unsigned short) face->v3; + tri[3*triIdx+2] = (unsigned short) face->v2; + trisToFacesMap[triIdx++]=fi; + if (face->v4) + { + tri[3*triIdx+0] = (unsigned short) face->v1; + tri[3*triIdx+1] = (unsigned short) face->v4; + tri[3*triIdx+2] = (unsigned short) face->v3; + trisToFacesMap[triIdx++]=fi; + } + } + + //carefully, recast data is just reference to data in derived mesh + recastData = (int*)CustomData_get_layer(&dm->faceData, CD_RECAST); + 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) +{ + 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; + int dtrisNum = dmeshes[polyidx*4+3]; + int dtrisBase = dmeshes[polyidx*4+2]; + unsigned char *traversedTris = new unsigned char[dtrisNum]; + memset(traversedTris, 0, dtrisNum*sizeof(unsigned char)); + for (int j=0; j<dtrisNum && btri==-1;j++) + { + int curpolytri = dtrisBase+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; + traversedTris[tri-dtrisBase] = 1; + 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; + traversedTris[tri-dtrisBase] = 1; + } + } + + 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; + + bool allBorderTraversed = true; + for (size_t i=0; i<(size_t)dtrisNum; i++) + { + if (traversedTris[i]==0) + { + //check whether it has border edges + int curpolytri = dtrisBase+i; + for (int k=0; k<3; k++) + { + unsigned short neighbortri = dtris[curpolytri*3*2+3+k]; + if ( neighbortri==0xffff || dtrisToPolysMap[neighbortri]!=polyidx+1) + { + allBorderTraversed = false; + break; + } + } + } + } + + if (nv<=vertsPerPoly && allBorderTraversed) + { + for (int i=0; i<nv; i++) + { + polys[polyidx*vertsPerPoly*2+i] = newPoly[i]; + } + } + } + +returnLabel: + delete newPoly; + return true; +} + +struct SortContext +{ + const int* recastData; + const int* trisToFacesMap; +}; +#if defined(_MSC_VER) +static int compareByData(void* data, const void * a, const void * b) +#elif defined(__APPLE__) || defined(__FreeBSD__) +static int compareByData(void* data, const void * a, const void * b) +#else +static int compareByData(const void * a, const void * b, void* data) +#endif +{ + const SortContext* context = (const 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; +#if defined(_MSC_VER) + qsort_s(trisMapping, ntris, sizeof(int), compareByData, &context); +#elif defined(__APPLE__) || defined(__FreeBSD__) + qsort_r(trisMapping, ntris, sizeof(int), &context, compareByData); +#else + qsort_r(trisMapping, ntris, sizeof(int), compareByData, &context); +#endif + //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 and renumber for continuous indices + int prevPolyIdx=-1, curPolyIdx, newPolyIdx=0; + dtrisToPolysMap = new int[ndtris]; + for (int i=0; i<ndtris; i++) + { + curPolyIdx = recastData[trisToFacesMap[dtrisToTrisMap[i]]]; + if (curPolyIdx!=prevPolyIdx) + { + newPolyIdx++; + prevPolyIdx=curPolyIdx; + } + dtrisToPolysMap[i] = newPolyIdx; + } + + + //build adjacency info for detailed mesh triangles + buildMeshAdjacency(dtris, ndtris, 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] = (unsigned short)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; +} |