← Back to branch summary

~ubuntu-branches/ubuntu/saucy/blender/saucy-proposed

« back to all changes in this revision

Viewing changes to source/blender/blenkernel/intern/navmesh_conversion.c

  • Committer: Package Import Robot
  • Author(s): Jeremy Bicha
  • Date: 2013-03-06 12:08:47 UTC
  • mfrom: (1.5.1) (14.1.8 experimental)
  • Revision ID: package-import@ubuntu.com-20130306120847-frjfaryb2zrotwcg
Tags: 2.66a-1ubuntu1
https://launchpad.net/bugs/1076930
https://launchpad.net/bugs/1089256
https://launchpad.net/bugs/1052743
https://launchpad.net/bugs/999024
* Resynchronize with Debian (LP: #1076930, #1089256, #1052743, #999024,
  #1122888, #1147084)
* debian/control:
  - Lower build-depends on libavcodec-dev since we're not
    doing the libav9 transition in Ubuntu yet

Show diffs side-by-side

added added

removed removed

Lines of Context:
source/blender/blenkernel/intern/navmesh_conversion.c
36
36
 
37
37
#include "DNA_meshdata_types.h"
38
38
 
 
39
#include "BLI_utildefines.h"
 
40
#include "BLI_math.h"
 
41
 
39
42
#include "BKE_navmesh_conversion.h"
40
43
#include "BKE_cdderivedmesh.h"
41
44
 
42
 
#include "BLI_utildefines.h"
43
 
#include "BLI_math.h"
44
 
 
45
45
#include "recast-capi.h"
46
46
 
47
 
BLI_INLINE float area2(const float* a, const float* b, const float* c)
 
47
BLI_INLINE float area2(const float *a, const float *b, const float *c)
48
48
{
49
49
        return (b[0] - a[0]) * (c[2] - a[2]) - (c[0] - a[0]) * (b[2] - a[2]);
50
50
}
51
51
 
52
 
BLI_INLINE int left(const float* a, const float* b, const float* c)
 
52
BLI_INLINE int left(const float *a, const float *b, const float *c)
53
53
{
54
54
        return area2(a, b, c) < 0;
55
55
}
56
56
 
57
 
int polyNumVerts(const unsigned short* p, const int vertsPerPoly)
 
57
int polyNumVerts(const unsigned short *p, const int vertsPerPoly)
58
58
{
59
59
        int i, nv = 0;
60
 
        for (i=0; i<vertsPerPoly; i++)
61
 
        {
62
 
                if (p[i]==0xffff)
 
60
        for (i = 0; i < vertsPerPoly; i++) {
 
61
                if (p[i] == 0xffff)
63
62
                        break;
64
63
                nv++;
65
64
        }
66
65
        return nv;
67
66
}
68
67
 
69
 
int polyIsConvex(const unsigned short* p, const int vertsPerPoly, const float* verts)
 
68
int polyIsConvex(const unsigned short *p, const int vertsPerPoly, const float *verts)
70
69
{
71
70
        int j, nv = polyNumVerts(p, vertsPerPoly);
72
 
        if (nv<3)
 
71
        if (nv < 3)
73
72
                return 0;
74
 
        for (j=0; j<nv; j++)
75
 
        {
76
 
                const float* v = &verts[3*p[j]];
77
 
                const float* v_next = &verts[3*p[(j+1)%nv]];
78
 
                const float* v_prev = &verts[3*p[(nv+j-1)%nv]];
 
73
        for (j = 0; j < nv; j++) {
 
74
                const float *v = &verts[3 * p[j]];
 
75
                const float *v_next = &verts[3 * p[(j + 1) % nv]];
 
76
                const float *v_prev = &verts[3 * p[(nv + j - 1) % nv]];
79
77
                if (!left(v_prev, v, v_next))
80
78
                        return 0;
81
79
 
83
81
        return 1;
84
82
}
85
83
 
86
 
float distPointToSegmentSq(const float* point, const float* a, const float* b)
 
84
/* XXX, could replace with #dist_to_line_segment_v3(), or add a squared version */
 
85
float distPointToSegmentSq(const float point[3], const float a[3], const float b[3])
87
86
{
88
87
        float abx[3], dx[3];
89
88
        float d, t;
90
89
 
91
 
        sub_v3_v3v3(abx, b,a);
92
 
        sub_v3_v3v3(dx, point,a);
93
 
 
94
 
        d = abx[0]*abx[0]+abx[2]*abx[2];
95
 
        t = abx[0]*dx[0]+abx[2]*dx[2];
96
 
 
97
 
        if (d > 0)
 
90
        sub_v3_v3v3(abx, b, a);
 
91
        sub_v3_v3v3(dx, point, a);
 
92
 
 
93
        d = abx[0] * abx[0] + abx[2] * abx[2];
 
94
        t = abx[0] * dx[0] + abx[2] * dx[2];
 
95
 
 
96
        if (d > 0.0f)
98
97
                t /= d;
99
 
        if (t < 0)
100
 
                t = 0;
101
 
        else if (t > 1)
102
 
                t = 1;
103
 
        dx[0] = a[0] + t*abx[0] - point[0];
104
 
        dx[2] = a[2] + t*abx[2] - point[2];
 
98
        if (t < 0.0f)
 
99
                t = 0.0f;
 
100
        else if (t > 1.0f)
 
101
                t = 1.0f;
 
102
        dx[0] = a[0] + t * abx[0] - point[0];
 
103
        dx[2] = a[2] + t * abx[2] - point[2];
105
104
 
106
 
        return dx[0]*dx[0] + dx[2]*dx[2];
 
105
        return dx[0] * dx[0] + dx[2] * dx[2];
107
106
}
108
107
 
109
 
int buildRawVertIndicesData(DerivedMesh* dm, int *nverts_r, float **verts_r, 
110
 
                                                                        int *ntris_r, unsigned short **tris_r, int **trisToFacesMap_r,
111
 
                                                                        int **recastData)
 
108
int buildRawVertIndicesData(DerivedMesh *dm, int *nverts_r, float **verts_r,
 
109
                            int *ntris_r, unsigned short **tris_r, int **trisToFacesMap_r,
 
110
                            int **recastData)
112
111
{
113
112
        int vi, fi, triIdx;
114
113
        int nverts, ntris;
119
118
        MFace *faces;
120
119
 
121
120
        nverts = dm->getNumVerts(dm);
122
 
        if (nverts>=0xffff)
123
 
        {
 
121
        if (nverts >= 0xffff) {
124
122
                printf("Converting navmesh: Error! Too many vertices. Max number of vertices %d\n", 0xffff);
125
123
                return 0;
126
124
        }
127
 
        verts = MEM_callocN(sizeof(float)*3*nverts, "buildRawVertIndicesData verts");
 
125
        verts = MEM_callocN(sizeof(float) * 3 * nverts, "buildRawVertIndicesData verts");
128
126
        dm->getVertCos(dm, (float(*)[3])verts);
129
127
 
130
 
        //flip coordinates
131
 
        for (vi=0; vi<nverts; vi++)
132
 
        {
133
 
                SWAP(float, verts[3*vi+1], verts[3*vi+2]);
 
128
        /* flip coordinates */
 
129
        for (vi = 0; vi < nverts; vi++) {
 
130
                SWAP(float, verts[3 * vi + 1], verts[3 * vi + 2]);
134
131
        }
135
132
 
136
 
        //calculate number of tris
 
133
        /* calculate number of tris */
137
134
        nfaces = dm->getNumTessFaces(dm);
138
135
        faces = dm->getTessFaceArray(dm);
139
136
        ntris = nfaces;
140
 
        for (fi=0; fi<nfaces; fi++)
141
 
        {
142
 
                MFace* face = &faces[fi];
 
137
        for (fi = 0; fi < nfaces; fi++) {
 
138
                MFace *face = &faces[fi];
143
139
                if (face->v4)
144
140
                        ntris++;
145
141
        }
146
142
 
147
 
        //copy and transform to triangles (reorder on the run)
148
 
        trisToFacesMap = MEM_callocN(sizeof(int)*ntris, "buildRawVertIndicesData trisToFacesMap");
149
 
        tris = MEM_callocN(sizeof(unsigned short)*3*ntris, "buildRawVertIndicesData tris");
 
143
        /* copy and transform to triangles (reorder on the run) */
 
144
        trisToFacesMap = MEM_callocN(sizeof(int) * ntris, "buildRawVertIndicesData trisToFacesMap");
 
145
        tris = MEM_callocN(sizeof(unsigned short) * 3 * ntris, "buildRawVertIndicesData tris");
150
146
        tri = tris;
151
147
        triIdx = 0;
152
 
        for (fi=0; fi<nfaces; fi++)
153
 
        {
154
 
                MFace* face = &faces[fi];
155
 
                tri[3*triIdx+0] = (unsigned short) face->v1;
156
 
                tri[3*triIdx+1] = (unsigned short) face->v3;
157
 
                tri[3*triIdx+2] = (unsigned short) face->v2;
158
 
                trisToFacesMap[triIdx++]=fi;
159
 
                if (face->v4)
160
 
                {
161
 
                        tri[3*triIdx+0] = (unsigned short) face->v1;
162
 
                        tri[3*triIdx+1] = (unsigned short) face->v4;
163
 
                        tri[3*triIdx+2] = (unsigned short) face->v3;
164
 
                        trisToFacesMap[triIdx++]=fi;
 
148
        for (fi = 0; fi < nfaces; fi++) {
 
149
                MFace *face = &faces[fi];
 
150
                tri[3 * triIdx + 0] = (unsigned short) face->v1;
 
151
                tri[3 * triIdx + 1] = (unsigned short) face->v3;
 
152
                tri[3 * triIdx + 2] = (unsigned short) face->v2;
 
153
                trisToFacesMap[triIdx++] = fi;
 
154
                if (face->v4) {
 
155
                        tri[3 * triIdx + 0] = (unsigned short) face->v1;
 
156
                        tri[3 * triIdx + 1] = (unsigned short) face->v4;
 
157
                        tri[3 * triIdx + 2] = (unsigned short) face->v3;
 
158
                        trisToFacesMap[triIdx++] = fi;
165
159
                }
166
160
        }
167
161
 
168
 
        //carefully, recast data is just reference to data in derived mesh
169
 
        *recastData = (int*)CustomData_get_layer(&dm->polyData, CD_RECAST);
 
162
        /* carefully, recast data is just reference to data in derived mesh */
 
163
        *recastData = (int *)CustomData_get_layer(&dm->polyData, CD_RECAST);
170
164
 
171
165
        *nverts_r = nverts;
172
166
        *verts_r = verts;
177
171
        return 1;
178
172
}
179
173
 
180
 
int buildPolygonsByDetailedMeshes(const int vertsPerPoly, const int npolys, 
181
 
                                                                                  unsigned short* polys, const unsigned short* dmeshes, 
182
 
                                                                                  const float* verts, const unsigned short* dtris, 
183
 
                                                                                  const int* dtrisToPolysMap)
 
174
int buildPolygonsByDetailedMeshes(const int vertsPerPoly, const int npolys,
 
175
                                  unsigned short *polys, const unsigned short *dmeshes,
 
176
                                  const float *verts, const unsigned short *dtris,
 
177
                                  const int *dtrisToPolysMap)
184
178
{
185
179
        int polyidx;
186
180
        int capacity = vertsPerPoly;
187
 
        unsigned short* newPoly = MEM_callocN(sizeof(unsigned short)*capacity, "buildPolygonsByDetailedMeshes newPoly");
188
 
        memset(newPoly, 0xff, sizeof(unsigned short)*capacity);
 
181
        unsigned short *newPoly = MEM_callocN(sizeof(unsigned short) * capacity, "buildPolygonsByDetailedMeshes newPoly");
 
182
        memset(newPoly, 0xff, sizeof(unsigned short) * capacity);
189
183
 
190
 
        for (polyidx=0; polyidx<npolys; polyidx++)
191
 
        {
 
184
        for (polyidx = 0; polyidx < npolys; polyidx++) {
192
185
                size_t i;
193
186
                int j, k;
194
187
                int nv = 0;
195
 
                //search border 
 
188
                /* search border */
196
189
                int tri, btri = -1;
197
190
                int edge, bedge = -1;
198
 
                int dtrisNum = dmeshes[polyidx*4+3];
199
 
                int dtrisBase = dmeshes[polyidx*4+2];
200
 
                unsigned char *traversedTris = MEM_callocN(sizeof(unsigned char)*dtrisNum, "buildPolygonsByDetailedMeshes traversedTris");
201
 
                unsigned short* adjustedPoly;
 
191
                int dtrisNum = dmeshes[polyidx * 4 + 3];
 
192
                int dtrisBase = dmeshes[polyidx * 4 + 2];
 
193
                unsigned char *traversedTris = MEM_callocN(sizeof(unsigned char) * dtrisNum, "buildPolygonsByDetailedMeshes traversedTris");
 
194
                unsigned short *adjustedPoly;
202
195
                int adjustedNv;
203
196
                int allBorderTraversed;
204
197
 
205
 
                for (j=0; j<dtrisNum && btri==-1;j++)
206
 
                {
207
 
                        int curpolytri = dtrisBase+j;
208
 
                        for (k=0; k<3; k++)
209
 
                        {
210
 
                                unsigned short neighbortri = dtris[curpolytri*3*2+3+k];
211
 
                                if ( neighbortri==0xffff || dtrisToPolysMap[neighbortri]!=polyidx+1)
212
 
                                {
 
198
                for (j = 0; j < dtrisNum && btri == -1; j++) {
 
199
                        int curpolytri = dtrisBase + j;
 
200
                        for (k = 0; k < 3; k++) {
 
201
                                unsigned short neighbortri = dtris[curpolytri * 3 * 2 + 3 + k];
 
202
                                if (neighbortri == 0xffff || dtrisToPolysMap[neighbortri] != polyidx + 1) {
213
203
                                        btri = curpolytri;
214
204
                                        bedge = k;
215
205
                                        break;
216
206
                                }
217
 
                        }                                                       
 
207
                        }
218
208
                }
219
 
                if (btri==-1 || bedge==-1)
220
 
                {
221
 
                        //can't find triangle with border edge
 
209
                if (btri == -1 || bedge == -1) {
 
210
                        /* can't find triangle with border edge */
222
211
                        MEM_freeN(traversedTris);
223
212
                        MEM_freeN(newPoly);
224
213
 
225
214
                        return 0;
226
215
                }
227
216
 
228
 
                newPoly[nv++] = dtris[btri*3*2+bedge];
 
217
                newPoly[nv++] = dtris[btri * 3 * 2 + bedge];
229
218
                tri = btri;
230
 
                edge = (bedge+1)%3;
231
 
                traversedTris[tri-dtrisBase] = 1;
232
 
                while (tri!=btri || edge!=bedge)
233
 
                {
234
 
                        int neighbortri = dtris[tri*3*2+3+edge];
235
 
                        if (neighbortri==0xffff || dtrisToPolysMap[neighbortri]!=polyidx+1)
236
 
                        {
237
 
                                if (nv==capacity)
238
 
                                {
239
 
                                        unsigned short* newPolyBig;
 
219
                edge = (bedge + 1) % 3;
 
220
                traversedTris[tri - dtrisBase] = 1;
 
221
                while (tri != btri || edge != bedge) {
 
222
                        int neighbortri = dtris[tri * 3 * 2 + 3 + edge];
 
223
                        if (neighbortri == 0xffff || dtrisToPolysMap[neighbortri] != polyidx + 1) {
 
224
                                if (nv == capacity) {
 
225
                                        unsigned short *newPolyBig;
240
226
                                        capacity += vertsPerPoly;
241
 
                                        newPolyBig = MEM_callocN(sizeof(unsigned short)*capacity, "buildPolygonsByDetailedMeshes newPolyBig");
242
 
                                        memset(newPolyBig, 0xff, sizeof(unsigned short)*capacity);
243
 
                                        memcpy(newPolyBig, newPoly, sizeof(unsigned short)*nv);
 
227
                                        newPolyBig = MEM_callocN(sizeof(unsigned short) * capacity, "buildPolygonsByDetailedMeshes newPolyBig");
 
228
                                        memset(newPolyBig, 0xff, sizeof(unsigned short) * capacity);
 
229
                                        memcpy(newPolyBig, newPoly, sizeof(unsigned short) * nv);
244
230
                                        MEM_freeN(newPoly);
245
 
                                        newPoly = newPolyBig;                   
 
231
                                        newPoly = newPolyBig;
246
232
                                }
247
 
                                newPoly[nv++] = dtris[tri*3*2+edge];
248
 
                                //move to next edge                                     
249
 
                                edge = (edge+1)%3;
 
233
                                newPoly[nv++] = dtris[tri * 3 * 2 + edge];
 
234
                                /* move to next edge */
 
235
                                edge = (edge + 1) % 3;
250
236
                        }
251
237
                        else {
252
 
                                //move to next tri
 
238
                                /* move to next tri */
253
239
                                int twinedge = -1;
254
 
                                for (k=0; k<3; k++)
255
 
                                {
256
 
                                        if (dtris[neighbortri*3*2+3+k] == tri)
257
 
                                        {
 
240
                                for (k = 0; k < 3; k++) {
 
241
                                        if (dtris[neighbortri * 3 * 2 + 3 + k] == tri) {
258
242
                                                twinedge = k;
259
243
                                                break;
260
244
                                        }
261
245
                                }
262
 
                                if (twinedge==-1)
263
 
                                {
 
246
                                if (twinedge == -1) {
264
247
                                        printf("Converting navmesh: Error! Can't find neighbor edge - invalid adjacency info\n");
265
248
                                        MEM_freeN(traversedTris);
266
249
                                        goto returnLabel;
267
250
                                }
268
251
                                tri = neighbortri;
269
 
                                edge = (twinedge+1)%3;
270
 
                                traversedTris[tri-dtrisBase] = 1;
 
252
                                edge = (twinedge + 1) % 3;
 
253
                                traversedTris[tri - dtrisBase] = 1;
271
254
                        }
272
255
                }
273
256
 
274
 
                adjustedPoly = MEM_callocN(sizeof(unsigned short)*nv, "buildPolygonsByDetailedMeshes adjustedPoly");
 
257
                adjustedPoly = MEM_callocN(sizeof(unsigned short) * nv, "buildPolygonsByDetailedMeshes adjustedPoly");
275
258
                adjustedNv = 0;
276
 
                for (i=0; i<nv; i++)
277
 
                {
278
 
                        unsigned short prev = newPoly[(nv+i-1)%nv];
 
259
                for (i = 0; i < nv; i++) {
 
260
                        unsigned short prev = newPoly[(nv + i - 1) % nv];
279
261
                        unsigned short cur = newPoly[i];
280
 
                        unsigned short next = newPoly[(i+1)%nv];
281
 
                        float distSq = distPointToSegmentSq(&verts[3*cur], &verts[3*prev], &verts[3*next]);
 
262
                        unsigned short next = newPoly[(i + 1) % nv];
 
263
                        float distSq = distPointToSegmentSq(&verts[3 * cur], &verts[3 * prev], &verts[3 * next]);
282
264
                        static const float tolerance = 0.001f;
283
 
                        if (distSq>tolerance)
 
265
                        if (distSq > tolerance)
284
266
                                adjustedPoly[adjustedNv++] = cur;
285
267
                }
286
 
                memcpy(newPoly, adjustedPoly, adjustedNv*sizeof(unsigned short));
 
268
                memcpy(newPoly, adjustedPoly, adjustedNv * sizeof(unsigned short));
287
269
                MEM_freeN(adjustedPoly);
288
270
                nv = adjustedNv;
289
271
 
290
272
                allBorderTraversed = 1;
291
 
                for (i=0; i<dtrisNum; i++)
292
 
                {
293
 
                        if (traversedTris[i]==0)
294
 
                        {
295
 
                                //check whether it has border edges
296
 
                                int curpolytri = dtrisBase+i;
297
 
                                for (k=0; k<3; k++)
298
 
                                {
299
 
                                        unsigned short neighbortri = dtris[curpolytri*3*2+3+k];
300
 
                                        if ( neighbortri==0xffff || dtrisToPolysMap[neighbortri]!=polyidx+1)
301
 
                                        {
 
273
                for (i = 0; i < dtrisNum; i++) {
 
274
                        if (traversedTris[i] == 0) {
 
275
                                /* check whether it has border edges */
 
276
                                int curpolytri = dtrisBase + i;
 
277
                                for (k = 0; k < 3; k++) {
 
278
                                        unsigned short neighbortri = dtris[curpolytri * 3 * 2 + 3 + k];
 
279
                                        if (neighbortri == 0xffff || dtrisToPolysMap[neighbortri] != polyidx + 1) {
302
280
                                                allBorderTraversed = 0;
303
281
                                                break;
304
282
                                        }
305
283
                                }
306
 
                        }                               
 
284
                        }
307
285
                }
308
286
 
309
 
                if (nv<=vertsPerPoly && allBorderTraversed)
310
 
                {
311
 
                        for (i=0; i<nv; i++)
312
 
                        {
313
 
                                polys[polyidx*vertsPerPoly*2+i] = newPoly[i];
 
287
                if (nv <= vertsPerPoly && allBorderTraversed) {
 
288
                        for (i = 0; i < nv; i++) {
 
289
                                polys[polyidx * vertsPerPoly * 2 + i] = newPoly[i];
314
290
                        }
315
291
                }
316
292
 
323
299
        return 1;
324
300
}
325
301
 
326
 
struct SortContext
327
 
{
328
 
        const int* recastData;
329
 
        const int* trisToFacesMap;
 
302
struct SortContext {
 
303
        const int *recastData;
 
304
        const int *trisToFacesMap;
330
305
};
331
306
 
332
 
static int compareByData(void *ctx, const void * a, const void * b)
 
307
static int compareByData(void *ctx, const void *a, const void *b)
333
308
{
334
 
        return (((struct SortContext *)ctx)->recastData[((struct SortContext *)ctx)->trisToFacesMap[*(int*)a]] -
335
 
                        ((struct SortContext *)ctx)->recastData[((struct SortContext *)ctx)->trisToFacesMap[*(int*)b]] );
 
309
        return (((struct SortContext *)ctx)->recastData[((struct SortContext *)ctx)->trisToFacesMap[*(int *)a]] -
 
310
                ((struct SortContext *)ctx)->recastData[((struct SortContext *)ctx)->trisToFacesMap[*(int *)b]]);
336
311
}
337
312
 
338
 
int buildNavMeshData(const int nverts, const float* verts, 
339
 
                                                         const int ntris, const unsigned short *tris, 
340
 
                                                         const int* recastData, const int* trisToFacesMap,
341
 
                                                         int *ndtris_r, unsigned short **dtris_r,
342
 
                                                         int *npolys_r, unsigned short **dmeshes_r, unsigned short **polys_r,
343
 
                                                         int *vertsPerPoly_r, int **dtrisToPolysMap_r, int **dtrisToTrisMap_r)
 
313
int buildNavMeshData(const int nverts, const float *verts,
 
314
                     const int ntris, const unsigned short *tris,
 
315
                     const int *recastData, const int *trisToFacesMap,
 
316
                     int *ndtris_r, unsigned short **dtris_r,
 
317
                     int *npolys_r, unsigned short **dmeshes_r, unsigned short **polys_r,
 
318
                     int *vertsPerPoly_r, int **dtrisToPolysMap_r, int **dtrisToTrisMap_r)
344
319
 
345
320
{
346
321
        int *trisMapping;
353
328
        unsigned short *dtris, *dmeshes, *polys;
354
329
        int *dtrisToPolysMap, *dtrisToTrisMap;
355
330
 
356
 
        if (!recastData)
357
 
        {
 
331
        if (!recastData) {
358
332
                printf("Converting navmesh: Error! Can't find recast custom data\n");
359
333
                return 0;
360
334
        }
361
335
 
362
 
        trisMapping = MEM_callocN(sizeof(int)*ntris, "buildNavMeshData trisMapping");
 
336
        trisMapping = MEM_callocN(sizeof(int) * ntris, "buildNavMeshData trisMapping");
363
337
 
364
 
        //sort the triangles by polygon idx
365
 
        for (i=0; i<ntris; i++)
366
 
                trisMapping[i]=i;
 
338
        /* sort the triangles by polygon idx */
 
339
        for (i = 0; i < ntris; i++)
 
340
                trisMapping[i] = i;
367
341
        context.recastData = recastData;
368
342
        context.trisToFacesMap = trisToFacesMap;
369
343
        recast_qsort(trisMapping, ntris, sizeof(int), &context, compareByData);
370
344
 
371
 
        //search first valid triangle - triangle of convex polygon
 
345
        /* search first valid triangle - triangle of convex polygon */
372
346
        validTriStart = -1;
373
 
        for (i=0; i< ntris; i++)
374
 
        {
375
 
                if (recastData[trisToFacesMap[trisMapping[i]]]>0)
376
 
                {
 
347
        for (i = 0; i < ntris; i++) {
 
348
                if (recastData[trisToFacesMap[trisMapping[i]]] > 0) {
377
349
                        validTriStart = i;
378
350
                        break;
379
351
                }
380
352
        }
381
353
 
382
 
        if (validTriStart<0)
383
 
        {
 
354
        if (validTriStart < 0) {
384
355
                printf("Converting navmesh: Error! No valid polygons in mesh\n");
385
356
                MEM_freeN(trisMapping);
386
357
                return 0;
387
358
        }
388
359
 
389
 
        ndtris = ntris-validTriStart;
390
 
        //fill dtris to faces mapping
391
 
        dtrisToTrisMap = MEM_callocN(sizeof(int)*ndtris, "buildNavMeshData dtrisToTrisMap");
392
 
        memcpy(dtrisToTrisMap, &trisMapping[validTriStart], ndtris*sizeof(int));
 
360
        ndtris = ntris - validTriStart;
 
361
        /* fill dtris to faces mapping */
 
362
        dtrisToTrisMap = MEM_callocN(sizeof(int) * ndtris, "buildNavMeshData dtrisToTrisMap");
 
363
        memcpy(dtrisToTrisMap, &trisMapping[validTriStart], ndtris * sizeof(int));
393
364
        MEM_freeN(trisMapping);
394
365
 
395
 
        //create detailed mesh triangles  - copy only valid triangles
396
 
        //and reserve memory for adjacency info
397
 
        dtris = MEM_callocN(sizeof(unsigned short)*3*2*ndtris, "buildNavMeshData dtris");
398
 
        memset(dtris, 0xffff, sizeof(unsigned short)*3*2*ndtris);
399
 
        for (i=0; i<ndtris; i++)
400
 
        {
401
 
                memcpy(dtris+3*2*i, tris+3*dtrisToTrisMap[i], sizeof(unsigned short)*3);
 
366
        /* create detailed mesh triangles  - copy only valid triangles
 
367
         * and reserve memory for adjacency info */
 
368
        dtris = MEM_callocN(sizeof(unsigned short) * 3 * 2 * ndtris, "buildNavMeshData dtris");
 
369
        memset(dtris, 0xffff, sizeof(unsigned short) * 3 * 2 * ndtris);
 
370
        for (i = 0; i < ndtris; i++) {
 
371
                memcpy(dtris + 3 * 2 * i, tris + 3 * dtrisToTrisMap[i], sizeof(unsigned short) * 3);
402
372
        }
403
373
 
404
 
        //create new recast data corresponded to dtris and renumber for continuous indices
 
374
        /* create new recast data corresponded to dtris and renumber for continuous indices */
405
375
        prevPolyIdx = -1;
406
376
        newPolyIdx = 0;
407
 
        dtrisToPolysMap = MEM_callocN(sizeof(int)*ndtris, "buildNavMeshData dtrisToPolysMap");
408
 
        for (i=0; i<ndtris; i++)
409
 
        {
 
377
        dtrisToPolysMap = MEM_callocN(sizeof(int) * ndtris, "buildNavMeshData dtrisToPolysMap");
 
378
        for (i = 0; i < ndtris; i++) {
410
379
                curPolyIdx = recastData[trisToFacesMap[dtrisToTrisMap[i]]];
411
 
                if (curPolyIdx!=prevPolyIdx)
412
 
                {
 
380
                if (curPolyIdx != prevPolyIdx) {
413
381
                        newPolyIdx++;
414
 
                        prevPolyIdx=curPolyIdx;
 
382
                        prevPolyIdx = curPolyIdx;
415
383
                }
416
384
                dtrisToPolysMap[i] = newPolyIdx;
417
385
        }
418
386
 
419
387
 
420
 
        //build adjacency info for detailed mesh triangles
 
388
        /* build adjacency info for detailed mesh triangles */
421
389
        recast_buildMeshAdjacency(dtris, ndtris, nverts, 3);
422
390
 
423
 
        //create detailed mesh description for each navigation polygon
424
 
        npolys = dtrisToPolysMap[ndtris-1];
425
 
        dmeshes = MEM_callocN(sizeof(unsigned short)*npolys*4, "buildNavMeshData dmeshes");
426
 
        memset(dmeshes, 0, npolys*4*sizeof(unsigned short));
 
391
        /* create detailed mesh description for each navigation polygon */
 
392
        npolys = dtrisToPolysMap[ndtris - 1];
 
393
        dmeshes = MEM_callocN(sizeof(unsigned short) * npolys * 4, "buildNavMeshData dmeshes");
 
394
        memset(dmeshes, 0, npolys * 4 * sizeof(unsigned short));
427
395
        dmesh = NULL;
428
396
        prevpolyidx = 0;
429
 
        for (i=0; i<ndtris; i++)
430
 
        {
 
397
        for (i = 0; i < ndtris; i++) {
431
398
                int curpolyidx = dtrisToPolysMap[i];
432
 
                if (curpolyidx!=prevpolyidx)
433
 
                {
434
 
                        if (curpolyidx!=prevpolyidx+1)
435
 
                        {
 
399
                if (curpolyidx != prevpolyidx) {
 
400
                        if (curpolyidx != prevpolyidx + 1) {
436
401
                                printf("Converting navmesh: Error! Wrong order of detailed mesh faces\n");
437
402
                                return 0;
438
403
                        }
439
 
                        dmesh = dmesh==NULL ? dmeshes : dmesh+4;
440
 
                        dmesh[2] = (unsigned short)i;   //tbase
441
 
                        dmesh[3] = 0;   //tnum
 
404
                        dmesh = dmesh == NULL ? dmeshes : dmesh + 4;
 
405
                        dmesh[2] = (unsigned short)i;  /* tbase */
 
406
                        dmesh[3] = 0;  /* tnum */
442
407
                        prevpolyidx = curpolyidx;
443
408
                }
444
409
                dmesh[3]++;
445
410
        }
446
411
 
447
 
        //create navigation polygons
 
412
        /* create navigation polygons */
448
413
        vertsPerPoly = 6;
449
 
        polys = MEM_callocN(sizeof(unsigned short)*npolys*vertsPerPoly*2, "buildNavMeshData polys");
450
 
        memset(polys, 0xff, sizeof(unsigned short)*vertsPerPoly*2*npolys);
 
414
        polys = MEM_callocN(sizeof(unsigned short) * npolys * vertsPerPoly * 2, "buildNavMeshData polys");
 
415
        memset(polys, 0xff, sizeof(unsigned short) * vertsPerPoly * 2 * npolys);
451
416
 
452
417
        buildPolygonsByDetailedMeshes(vertsPerPoly, npolys, polys, dmeshes, verts, dtris, dtrisToPolysMap);
453
418
 
464
429
}
465
430
 
466
431
 
467
 
int buildNavMeshDataByDerivedMesh(DerivedMesh *dm, int *vertsPerPoly, 
468
 
                                                                                  int *nverts, float **verts,
469
 
                                                                                  int *ndtris, unsigned short **dtris,
470
 
                                                                                  int *npolys, unsigned short **dmeshes,
471
 
                                                                                  unsigned short **polys, int **dtrisToPolysMap,
472
 
                                                                                  int **dtrisToTrisMap, int **trisToFacesMap)
 
432
int buildNavMeshDataByDerivedMesh(DerivedMesh *dm, int *vertsPerPoly,
 
433
                                  int *nverts, float **verts,
 
434
                                  int *ndtris, unsigned short **dtris,
 
435
                                  int *npolys, unsigned short **dmeshes,
 
436
                                  unsigned short **polys, int **dtrisToPolysMap,
 
437
                                  int **dtrisToTrisMap, int **trisToFacesMap)
473
438
{
474
439
        int res = 1;
475
 
        int ntris = 0, *recastData=NULL;
476
 
        unsigned short *tris=NULL;
 
440
        int ntris = 0, *recastData = NULL;
 
441
        unsigned short *tris = NULL;
477
442
 
478
443
        res = buildRawVertIndicesData(dm, nverts, verts, &ntris, &tris, trisToFacesMap, &recastData);
479
 
        if (!res)
480
 
        {
 
444
        if (!res) {
481
445
                printf("Converting navmesh: Error! Can't get vertices and indices from mesh\n");
482
446
                goto exit;
483
447
        }
484
448
 
485
449
        res = buildNavMeshData(*nverts, *verts, ntris, tris, recastData, *trisToFacesMap,
486
 
                ndtris, dtris, npolys, dmeshes,polys, vertsPerPoly, 
487
 
                dtrisToPolysMap, dtrisToTrisMap);
488
 
        if (!res)
489
 
        {
 
450
                               ndtris, dtris, npolys, dmeshes, polys, vertsPerPoly,
 
451
                               dtrisToPolysMap, dtrisToTrisMap);
 
452
        if (!res) {
490
453
                printf("Converting navmesh: Error! Can't get vertices and indices from mesh\n");
491
454
                goto exit;
492
455
        }
498
461
        return res;
499
462
}
500
463
 
501
 
int polyFindVertex(const unsigned short* p, const int vertsPerPoly, unsigned short vertexIdx)
 
464
int polyFindVertex(const unsigned short *p, const int vertsPerPoly, unsigned short vertexIdx)
502
465
{
503
466
        int i, res = -1;
504
 
        for (i=0; i<vertsPerPoly; i++)
505
 
        {
506
 
                if (p[i]==0xffff)
 
467
        for (i = 0; i < vertsPerPoly; i++) {
 
468
                if (p[i] == 0xffff)
507
469
                        break;
508
 
                if (p[i]==vertexIdx)
509
 
                {
 
470
                if (p[i] == vertexIdx) {
510
471
                        res = i;
511
472
                        break;
512
473
                }