fix in DM_to_mesh() for bmesh - would crash rendering NGons with cycles
[blender.git] / source / blender / blenkernel / intern / DerivedMesh.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2005 Blender Foundation.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/blenkernel/intern/DerivedMesh.c
29  *  \ingroup bke
30  */
31
32
33 #include <string.h>
34 #include "limits.h"
35
36 #include "MEM_guardedalloc.h"
37
38 #include "DNA_cloth_types.h"
39 #include "DNA_key_types.h"
40 #include "DNA_meshdata_types.h"
41 #include "DNA_armature_types.h"
42 #include "DNA_object_types.h"
43 #include "DNA_scene_types.h" // N_T
44
45 #include "BLI_blenlib.h"
46 #include "BLI_editVert.h"
47 #include "BLI_math.h"
48 #include "BLI_memarena.h"
49 #include "BLI_array.h"
50 #include "BLI_pbvh.h"
51 #include "BLI_utildefines.h"
52 #include "BLI_linklist.h"
53
54 #include "BKE_cdderivedmesh.h"
55 #include "BKE_displist.h"
56 #include "BKE_key.h"
57 #include "BKE_modifier.h"
58 #include "BKE_mesh.h"
59 #include "BKE_object.h"
60 #include "BKE_paint.h"
61 #include "BKE_texture.h"
62 #include "BKE_multires.h"
63 #include "BKE_armature.h"
64 #include "BKE_particle.h"
65 #include "BKE_tessmesh.h"
66 #include "BKE_bvhutils.h"
67
68 #ifdef WITH_GAMEENGINE
69 #include "BKE_navmesh_conversion.h"
70 static DerivedMesh *navmesh_dm_createNavMeshForVisualization(DerivedMesh *dm);
71 #endif
72
73 #include "BLO_sys_types.h" // for intptr_t support
74
75 #include "GL/glew.h"
76
77 #include "GPU_buffers.h"
78 #include "GPU_draw.h"
79 #include "GPU_extensions.h"
80 #include "GPU_material.h"
81
82 extern GLubyte stipple_quarttone[128]; /* glutil.c, bad level data */
83
84 static void add_shapekey_layers(DerivedMesh *dm, Mesh *me, Object *ob);
85 static void shapekey_layers_to_keyblocks(DerivedMesh *dm, Mesh *me, int actshape_uid);
86
87 ///////////////////////////////////
88 ///////////////////////////////////
89
90 static MVert *dm_getVertArray(DerivedMesh *dm)
91 {
92         MVert *mvert = CustomData_get_layer(&dm->vertData, CD_MVERT);
93
94         if (!mvert) {
95                 mvert = CustomData_add_layer(&dm->vertData, CD_MVERT, CD_CALLOC, NULL,
96                         dm->getNumVerts(dm));
97                 CustomData_set_layer_flag(&dm->vertData, CD_MVERT, CD_FLAG_TEMPORARY);
98                 dm->copyVertArray(dm, mvert);
99         }
100
101         return mvert;
102 }
103
104 static MEdge *dm_getEdgeArray(DerivedMesh *dm)
105 {
106         MEdge *medge = CustomData_get_layer(&dm->edgeData, CD_MEDGE);
107
108         if (!medge) {
109                 medge = CustomData_add_layer(&dm->edgeData, CD_MEDGE, CD_CALLOC, NULL,
110                         dm->getNumEdges(dm));
111                 CustomData_set_layer_flag(&dm->edgeData, CD_MEDGE, CD_FLAG_TEMPORARY);
112                 dm->copyEdgeArray(dm, medge);
113         }
114
115         return medge;
116 }
117
118 static MFace *dm_getFaceArray(DerivedMesh *dm)
119 {
120         MFace *mface = CustomData_get_layer(&dm->faceData, CD_MFACE);
121
122         if (!mface) {
123                 mface = CustomData_add_layer(&dm->faceData, CD_MFACE, CD_CALLOC, NULL,
124                         dm->getNumTessFaces(dm));
125                 CustomData_set_layer_flag(&dm->faceData, CD_MFACE, CD_FLAG_TEMPORARY);
126                 dm->copyTessFaceArray(dm, mface);
127         }
128
129         return mface;
130 }
131
132 static MLoop *dm_getLoopArray(DerivedMesh *dm)
133 {
134         MLoop *mloop = CustomData_get_layer(&dm->loopData, CD_MLOOP);
135
136         if (!mloop) {
137                 mloop = CustomData_add_layer(&dm->loopData, CD_MLOOP, CD_CALLOC, NULL,
138                         dm->numLoopData);
139                 CustomData_set_layer_flag(&dm->loopData, CD_MLOOP, CD_FLAG_TEMPORARY);
140                 dm->copyLoopArray(dm, mloop);
141         }
142
143         return mloop;
144 }
145
146 static MPoly *dm_getPolyArray(DerivedMesh *dm)
147 {
148         MPoly *mpoly = CustomData_get_layer(&dm->polyData, CD_MPOLY);
149
150         if (!mpoly) {
151                 mpoly = CustomData_add_layer(&dm->polyData, CD_MPOLY, CD_CALLOC, NULL,
152                         dm->getNumFaces(dm));
153                 CustomData_set_layer_flag(&dm->polyData, CD_MPOLY, CD_FLAG_TEMPORARY);
154                 dm->copyPolyArray(dm, mpoly);
155         }
156
157         return mpoly;
158 }
159
160 static MVert *dm_dupVertArray(DerivedMesh *dm)
161 {
162         MVert *tmp = MEM_callocN(sizeof(*tmp) * dm->getNumVerts(dm),
163                                                          "dm_dupVertArray tmp");
164
165         if(tmp) dm->copyVertArray(dm, tmp);
166
167         return tmp;
168 }
169
170 static MEdge *dm_dupEdgeArray(DerivedMesh *dm)
171 {
172         MEdge *tmp = MEM_callocN(sizeof(*tmp) * dm->getNumEdges(dm),
173                                                          "dm_dupEdgeArray tmp");
174
175         if(tmp) dm->copyEdgeArray(dm, tmp);
176
177         return tmp;
178 }
179
180 static MFace *dm_dupFaceArray(DerivedMesh *dm)
181 {
182         MFace *tmp = MEM_callocN(sizeof(*tmp) * dm->getNumTessFaces(dm),
183                                                          "dm_dupFaceArray tmp");
184
185         if(tmp) dm->copyTessFaceArray(dm, tmp);
186
187         return tmp;
188 }
189
190 static MLoop *dm_dupLoopArray(DerivedMesh *dm)
191 {
192         MLoop *tmp = MEM_callocN(sizeof(*tmp) * dm->numLoopData,
193                                                          "dm_dupLoopArray tmp");
194
195         if(tmp) dm->copyLoopArray(dm, tmp);
196
197         return tmp;
198 }
199
200 static MPoly *dm_dupPolyArray(DerivedMesh *dm)
201 {
202         MPoly *tmp = MEM_callocN(sizeof(*tmp) * dm->numFaceData,
203                                                          "dm_dupPolyArray tmp");
204
205         if(tmp) dm->copyPolyArray(dm, tmp);
206
207         return tmp;
208 }
209
210 static CustomData *dm_getVertCData(DerivedMesh *dm)
211 {
212         return &dm->vertData;
213 }
214
215 static CustomData *dm_getEdgeCData(DerivedMesh *dm)
216 {
217         return &dm->edgeData;
218 }
219
220 static CustomData *dm_getFaceCData(DerivedMesh *dm)
221 {
222         return &dm->faceData;
223 }
224
225 static CustomData *dm_getLoopCData(DerivedMesh *dm)
226 {
227         return &dm->loopData;
228 }
229
230 static CustomData *dm_getPolyCData(DerivedMesh *dm)
231 {
232         return &dm->polyData;
233 }
234
235 void DM_init_funcs(DerivedMesh *dm)
236 {
237         /* default function implementations */
238         dm->getVertArray = dm_getVertArray;
239         dm->getEdgeArray = dm_getEdgeArray;
240         dm->getTessFaceArray = dm_getFaceArray;
241         dm->getLoopArray = dm_getLoopArray;
242         dm->getPolyArray = dm_getPolyArray;
243         dm->dupVertArray = dm_dupVertArray;
244         dm->dupEdgeArray = dm_dupEdgeArray;
245         dm->dupTessFaceArray = dm_dupFaceArray;
246         dm->dupLoopArray = dm_dupLoopArray;
247         dm->dupPolyArray = dm_dupPolyArray;
248
249         dm->getVertDataLayout = dm_getVertCData;
250         dm->getEdgeDataLayout = dm_getEdgeCData;
251         dm->getTessFaceDataLayout = dm_getFaceCData;
252         dm->getLoopDataLayout = dm_getLoopCData;
253         dm->getFaceDataLayout = dm_getPolyCData;
254
255         dm->getVertData = DM_get_vert_data;
256         dm->getEdgeData = DM_get_edge_data;
257         dm->getTessFaceData = DM_get_face_data;
258         dm->getVertDataArray = DM_get_vert_data_layer;
259         dm->getEdgeDataArray = DM_get_edge_data_layer;
260         dm->getTessFaceDataArray = DM_get_tessface_data_layer;
261
262         bvhcache_init(&dm->bvhCache);
263 }
264
265 void DM_init(DerivedMesh *dm, DerivedMeshType type, int numVerts, int numEdges,
266              int numFaces, int numLoops, int numPoly)
267 {
268         dm->type = type;
269         dm->numVertData = numVerts;
270         dm->numEdgeData = numEdges;
271         dm->numFaceData = numFaces;
272         dm->numLoopData = numLoops;
273         dm->numPolyData = numPoly;
274
275         DM_init_funcs(dm);
276         
277         dm->needsFree = 1;
278 }
279
280 void DM_from_template(DerivedMesh *dm, DerivedMesh *source, DerivedMeshType type,
281                       int numVerts, int numEdges, int numFaces,
282                       int numLoops, int numPolys)
283 {
284         CustomData_copy(&source->vertData, &dm->vertData, CD_MASK_DERIVEDMESH,
285                                         CD_CALLOC, numVerts);
286         CustomData_copy(&source->edgeData, &dm->edgeData, CD_MASK_DERIVEDMESH,
287                                         CD_CALLOC, numEdges);
288         CustomData_copy(&source->faceData, &dm->faceData, CD_MASK_DERIVEDMESH,
289                                         CD_CALLOC, numFaces);
290         CustomData_copy(&source->loopData, &dm->loopData, CD_MASK_DERIVEDMESH,
291                         CD_CALLOC, numLoops);
292         CustomData_copy(&source->polyData, &dm->polyData, CD_MASK_DERIVEDMESH,
293                         CD_CALLOC, numPolys);
294
295         dm->type = type;
296         dm->numVertData = numVerts;
297         dm->numEdgeData = numEdges;
298         dm->numFaceData = numFaces;
299         dm->numLoopData = numLoops;
300         dm->numPolyData = numPolys;
301
302         DM_init_funcs(dm);
303
304         dm->needsFree = 1;
305 }
306
307 int DM_release(DerivedMesh *dm)
308 {
309         if (dm->needsFree) {
310                 bvhcache_free(&dm->bvhCache);
311                 GPU_drawobject_free( dm );
312                 CustomData_free(&dm->vertData, dm->numVertData);
313                 CustomData_free(&dm->edgeData, dm->numEdgeData);
314                 CustomData_free(&dm->faceData, dm->numFaceData);
315                 CustomData_free(&dm->loopData, dm->numLoopData);
316                 CustomData_free(&dm->polyData, dm->numPolyData);
317
318                 return 1;
319         }
320         else {
321                 CustomData_free_temporary(&dm->vertData, dm->numVertData);
322                 CustomData_free_temporary(&dm->edgeData, dm->numEdgeData);
323                 CustomData_free_temporary(&dm->faceData, dm->numFaceData);
324                 CustomData_free_temporary(&dm->loopData, dm->numLoopData);
325                 CustomData_free_temporary(&dm->polyData, dm->numPolyData);
326
327                 return 0;
328         }
329 }
330
331 void DM_DupPolys(DerivedMesh *source, DerivedMesh *target)
332 {
333         CustomData_free(&target->loopData, source->numLoopData);
334         CustomData_free(&target->polyData, source->numPolyData);
335
336         CustomData_copy(&source->loopData, &target->loopData, CD_MASK_DERIVEDMESH, CD_DUPLICATE, source->numLoopData);
337         CustomData_copy(&source->polyData, &target->polyData, CD_MASK_DERIVEDMESH, CD_DUPLICATE, source->numPolyData);
338
339         target->numLoopData = source->numLoopData;
340         target->numPolyData = source->numPolyData;
341
342         if (!CustomData_has_layer(&target->polyData, CD_MPOLY)) {
343                 MPoly *mpoly;
344                 MLoop *mloop;
345
346                 mloop = source->dupLoopArray(source);
347                 mpoly = source->dupPolyArray(source);
348                 CustomData_add_layer(&target->loopData, CD_MLOOP, CD_ASSIGN, mloop, source->numLoopData);
349                 CustomData_add_layer(&target->polyData, CD_MPOLY, CD_ASSIGN, mpoly, source->numPolyData);
350         }
351 }
352
353 void DM_to_mesh(DerivedMesh *dm, Mesh *me, Object *ob)
354 {
355         /* dm might depend on me, so we need to do everything with a local copy */
356         Mesh tmp = *me;
357         int totvert, totedge /*, totface */ /* UNUSED */, totloop, totpoly;
358         int did_shapekeys=0;
359         
360         memset(&tmp.vdata, 0, sizeof(tmp.vdata));
361         memset(&tmp.edata, 0, sizeof(tmp.edata));
362         memset(&tmp.fdata, 0, sizeof(tmp.fdata));
363         memset(&tmp.ldata, 0, sizeof(tmp.ldata));
364         memset(&tmp.pdata, 0, sizeof(tmp.pdata));
365
366         totvert = tmp.totvert = dm->getNumVerts(dm);
367         totedge = tmp.totedge = dm->getNumEdges(dm);
368         totpoly = tmp.totpoly = dm->getNumFaces(dm);
369         totloop = tmp.totloop = dm->numLoopData;
370
371         CustomData_copy(&dm->vertData, &tmp.vdata, CD_MASK_MESH, CD_DUPLICATE, totvert);
372         CustomData_copy(&dm->edgeData, &tmp.edata, CD_MASK_MESH, CD_DUPLICATE, totedge);
373         CustomData_copy(&dm->loopData, &tmp.ldata, CD_MASK_MESH, CD_DUPLICATE, totloop);
374         CustomData_copy(&dm->polyData, &tmp.pdata, CD_MASK_MESH, CD_DUPLICATE, totpoly);
375
376         if (CustomData_has_layer(&dm->vertData, CD_SHAPEKEY)) {
377                 KeyBlock *kb;
378                 int i=0;
379                 
380                 if (ob) {
381                         for (kb=me->key->block.first; kb; kb=kb->next, i++) {
382                                 if (i == ob->shapenr-1) {
383                                         i = kb->uid;
384                                         break;
385                                 }
386                         }
387                         
388                         if (!kb) {
389                                 printf("%s: error - could not find active shapekey %d!\n",
390                                        __func__, ob->shapenr-1);
391
392                                 i = INT_MAX;
393                         }
394                 } else {
395                         /*if no object, set to INT_MAX so we don't mess up any shapekey layers*/
396                         i = INT_MAX;
397                 }
398                 
399                 shapekey_layers_to_keyblocks(dm, me, i);
400                 did_shapekeys = 1;
401         }
402         
403         /* not all DerivedMeshes store their verts/edges/faces in CustomData, so
404            we set them here in case they are missing */
405         if(!CustomData_has_layer(&tmp.vdata, CD_MVERT))
406                 CustomData_add_layer(&tmp.vdata, CD_MVERT, CD_ASSIGN, dm->dupVertArray(dm), totvert);
407         if(!CustomData_has_layer(&tmp.edata, CD_MEDGE))
408                 CustomData_add_layer(&tmp.edata, CD_MEDGE, CD_ASSIGN, dm->dupEdgeArray(dm), totedge);
409         if(!CustomData_has_layer(&tmp.pdata, CD_MPOLY)) {
410                 tmp.mloop = dm->dupLoopArray(dm);
411                 tmp.mpoly = dm->dupPolyArray(dm);
412
413                 CustomData_add_layer(&tmp.ldata, CD_MLOOP, CD_ASSIGN, tmp.mloop, tmp.totloop);
414                 CustomData_add_layer(&tmp.pdata, CD_MPOLY, CD_ASSIGN, tmp.mpoly, tmp.totpoly);
415         }
416
417         /* object had got displacement layer, should copy this layer to save sculpted data */
418         /* NOTE: maybe some other layers should be copied? nazgul */
419         if(CustomData_has_layer(&me->ldata, CD_MDISPS)) {
420                 if (totloop == me->totloop) {
421                         MDisps *mdisps = CustomData_get_layer(&me->ldata, CD_MDISPS);
422                         CustomData_add_layer(&tmp.ldata, CD_MDISPS, CD_DUPLICATE, mdisps, totloop);
423                 }
424         }
425
426         /* yes, must be before _and_ after tesselate */
427         mesh_update_customdata_pointers(&tmp);
428
429         tmp.totface = mesh_recalcTesselation(&tmp.fdata, &tmp.ldata, &tmp.pdata, tmp.mvert, tmp.totface, tmp.totloop, tmp.totpoly);
430
431         mesh_update_customdata_pointers(&tmp);
432
433
434         CustomData_free(&me->vdata, me->totvert);
435         CustomData_free(&me->edata, me->totedge);
436         CustomData_free(&me->fdata, me->totface);
437         CustomData_free(&me->ldata, me->totloop);
438         CustomData_free(&me->pdata, me->totpoly);
439
440         /*  ok, this should now use new CD shapekey data,
441             which shouuld be fed through the modifier 
442                 stack*/
443         if(tmp.totvert != me->totvert && !did_shapekeys && me->key) {
444                 printf("YEEK! this should be recoded! Shape key loss!!!\n");
445                 if(tmp.key) tmp.key->id.us--;
446                 tmp.key = NULL;
447         }
448
449         *me = tmp;
450 }
451
452 void DM_to_meshkey(DerivedMesh *dm, Mesh *me, KeyBlock *kb)
453 {
454         int a, totvert = dm->getNumVerts(dm);
455         float *fp;
456         MVert *mvert;
457         
458         if(totvert==0 || me->totvert==0 || me->totvert!=totvert) return;
459         
460         if(kb->data) MEM_freeN(kb->data);
461         kb->data= MEM_callocN(me->key->elemsize*me->totvert, "kb->data");
462         kb->totelem= totvert;
463         
464         fp= kb->data;
465         mvert=dm->getVertDataArray(dm, CD_MVERT);
466         
467         for(a=0; a<kb->totelem; a++, fp+=3, mvert++) {
468                 copy_v3_v3(fp, mvert->co);
469         }
470 }
471
472 void DM_set_only_copy(DerivedMesh *dm, CustomDataMask mask)
473 {
474         CustomData_set_only_copy(&dm->vertData, mask);
475         CustomData_set_only_copy(&dm->edgeData, mask);
476         CustomData_set_only_copy(&dm->faceData, mask);
477 }
478
479 void DM_add_vert_layer(DerivedMesh *dm, int type, int alloctype, void *layer)
480 {
481         CustomData_add_layer(&dm->vertData, type, alloctype, layer, dm->numVertData);
482 }
483
484 void DM_add_edge_layer(DerivedMesh *dm, int type, int alloctype, void *layer)
485 {
486         CustomData_add_layer(&dm->edgeData, type, alloctype, layer, dm->numEdgeData);
487 }
488
489 void DM_add_tessface_layer(DerivedMesh *dm, int type, int alloctype, void *layer)
490 {
491         CustomData_add_layer(&dm->faceData, type, alloctype, layer, dm->numFaceData);
492 }
493
494 void DM_add_loop_layer(DerivedMesh *dm, int type, int alloctype, void *layer)
495 {
496         CustomData_add_layer(&dm->loopData, type, alloctype, layer, dm->numLoopData);
497 }
498
499 void DM_add_face_layer(DerivedMesh *dm, int type, int alloctype, void *layer)
500 {
501         CustomData_add_layer(&dm->polyData, type, alloctype, layer, dm->numPolyData);
502 }
503
504 void *DM_get_vert_data(DerivedMesh *dm, int index, int type)
505 {
506         return CustomData_get(&dm->vertData, index, type);
507 }
508
509 void *DM_get_edge_data(DerivedMesh *dm, int index, int type)
510 {
511         return CustomData_get(&dm->edgeData, index, type);
512 }
513
514 void *DM_get_face_data(DerivedMesh *dm, int index, int type)
515 {
516         return CustomData_get(&dm->faceData, index, type);
517 }
518
519 void *DM_get_vert_data_layer(DerivedMesh *dm, int type)
520 {
521         if(type == CD_MVERT)
522                 return dm->getVertArray(dm);
523
524         return CustomData_get_layer(&dm->vertData, type);
525 }
526
527 void *DM_get_edge_data_layer(DerivedMesh *dm, int type)
528 {
529         if(type == CD_MEDGE)
530                 return dm->getEdgeArray(dm);
531
532         return CustomData_get_layer(&dm->edgeData, type);
533 }
534
535 void *DM_get_tessface_data_layer(DerivedMesh *dm, int type)
536 {
537         if (type == CD_MFACE)
538                 return dm->getTessFaceArray(dm);
539
540         return CustomData_get_layer(&dm->faceData, type);
541 }
542
543 void *DM_get_face_data_layer(DerivedMesh *dm, int type)
544 {
545         return CustomData_get_layer(&dm->polyData, type);
546 }
547
548 void DM_set_vert_data(DerivedMesh *dm, int index, int type, void *data)
549 {
550         CustomData_set(&dm->vertData, index, type, data);
551 }
552
553 void DM_set_edge_data(DerivedMesh *dm, int index, int type, void *data)
554 {
555         CustomData_set(&dm->edgeData, index, type, data);
556 }
557
558 void DM_set_face_data(DerivedMesh *dm, int index, int type, void *data)
559 {
560         CustomData_set(&dm->faceData, index, type, data);
561 }
562
563 void DM_copy_vert_data(DerivedMesh *source, DerivedMesh *dest,
564                                            int source_index, int dest_index, int count)
565 {
566         CustomData_copy_data(&source->vertData, &dest->vertData,
567                                                  source_index, dest_index, count);
568 }
569
570 void DM_copy_edge_data(DerivedMesh *source, DerivedMesh *dest,
571                                            int source_index, int dest_index, int count)
572 {
573         CustomData_copy_data(&source->edgeData, &dest->edgeData,
574                                                  source_index, dest_index, count);
575 }
576
577 void DM_copy_tessface_data(DerivedMesh *source, DerivedMesh *dest,
578                                            int source_index, int dest_index, int count)
579 {
580         CustomData_copy_data(&source->faceData, &dest->faceData,
581                                                  source_index, dest_index, count);
582 }
583
584 void DM_copy_loop_data(DerivedMesh *source, DerivedMesh *dest,
585                        int source_index, int dest_index, int count)
586 {
587         CustomData_copy_data(&source->loopData, &dest->loopData,
588                              source_index, dest_index, count);
589 }
590
591 void DM_copy_face_data(DerivedMesh *source, DerivedMesh *dest,
592                        int source_index, int dest_index, int count)
593 {
594         CustomData_copy_data(&source->polyData, &dest->polyData,
595                              source_index, dest_index, count);
596 }
597
598 void DM_free_vert_data(struct DerivedMesh *dm, int index, int count)
599 {
600         CustomData_free_elem(&dm->vertData, index, count);
601 }
602
603 void DM_free_edge_data(struct DerivedMesh *dm, int index, int count)
604 {
605         CustomData_free_elem(&dm->edgeData, index, count);
606 }
607
608 void DM_free_tessface_data(struct DerivedMesh *dm, int index, int count)
609 {
610         CustomData_free_elem(&dm->faceData, index, count);
611 }
612
613 void DM_free_loop_data(struct DerivedMesh *dm, int index, int count)
614 {
615         CustomData_free_elem(&dm->loopData, index, count);
616 }
617
618 void DM_free_face_data(struct DerivedMesh *dm, int index, int count)
619 {
620         CustomData_free_elem(&dm->polyData, index, count);
621 }
622
623 void DM_interp_vert_data(DerivedMesh *source, DerivedMesh *dest,
624                                                  int *src_indices, float *weights,
625                                                  int count, int dest_index)
626 {
627         CustomData_interp(&source->vertData, &dest->vertData, src_indices,
628                                           weights, NULL, count, dest_index);
629 }
630
631 void DM_interp_edge_data(DerivedMesh *source, DerivedMesh *dest,
632                                                  int *src_indices,
633                                                  float *weights, EdgeVertWeight *vert_weights,
634                                                  int count, int dest_index)
635 {
636         CustomData_interp(&source->edgeData, &dest->edgeData, src_indices,
637                                           weights, (float*)vert_weights, count, dest_index);
638 }
639
640 void DM_interp_tessface_data(DerivedMesh *source, DerivedMesh *dest,
641                                                  int *src_indices,
642                                                  float *weights, FaceVertWeight *vert_weights,
643                                                  int count, int dest_index)
644 {
645         CustomData_interp(&source->faceData, &dest->faceData, src_indices,
646                                           weights, (float*)vert_weights, count, dest_index);
647 }
648
649 void DM_swap_tessface_data(DerivedMesh *dm, int index, const int *corner_indices)
650 {
651         CustomData_swap(&dm->faceData, index, corner_indices);
652 }
653
654 void DM_interp_loop_data(DerivedMesh *source, DerivedMesh *dest,
655                          int *src_indices,
656                          float *weights, int count, int dest_index)
657 {
658         CustomData_interp(&source->loopData, &dest->loopData, src_indices,
659                           weights, NULL, count, dest_index);
660 }
661
662 void DM_interp_face_data(DerivedMesh *source, DerivedMesh *dest,
663                          int *src_indices,
664                          float *weights, int count, int dest_index)
665 {
666         CustomData_interp(&source->polyData, &dest->polyData, src_indices,
667                           weights, NULL, count, dest_index);
668 }
669
670 ///
671 DerivedMesh *mesh_create_derived(Mesh *me, Object *ob, float (*vertCos)[3])
672 {
673         DerivedMesh *dm = CDDM_from_mesh(me, ob);
674         
675         if(!dm)
676                 return NULL;
677         
678         if (vertCos)
679                 CDDM_apply_vert_coords(dm, vertCos);
680
681         CDDM_calc_normals(dm);
682
683         return dm;
684 }
685
686 /***/
687
688 DerivedMesh *mesh_create_derived_for_modifier(Scene *scene, Object *ob, 
689         ModifierData *md, int build_shapekey_layers)
690 {
691         Mesh *me = ob->data;
692         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
693         DerivedMesh *dm;
694
695         md->scene= scene;
696         
697         if (!(md->mode&eModifierMode_Realtime)) return NULL;
698         if (mti->isDisabled && mti->isDisabled(md, 0)) return NULL;
699         
700         if (build_shapekey_layers && me->key && ob->shapenr <= BLI_countlist(&me->key->block)) {
701                 key_to_mesh(BLI_findlink(&me->key->block, ob->shapenr-1), me);
702         }
703         
704         if (mti->type==eModifierTypeType_OnlyDeform) {
705                 int numVerts;
706                 float (*deformedVerts)[3] = mesh_getVertexCos(me, &numVerts);
707
708                 mti->deformVerts(md, ob, NULL, deformedVerts, numVerts, 0, 0);
709                 dm = mesh_create_derived(me, ob, deformedVerts);
710
711                 if (build_shapekey_layers)
712                         add_shapekey_layers(dm, me, ob);
713                 
714                 MEM_freeN(deformedVerts);
715         } else {
716                 DerivedMesh *tdm = mesh_create_derived(me, ob, NULL);
717
718                 if (build_shapekey_layers)
719                         add_shapekey_layers(tdm, me, ob);
720                 
721                 dm = mti->applyModifier(md, ob, tdm, 0, 0);
722
723                 if(tdm != dm) tdm->release(tdm);
724         }
725
726         return dm;
727 }
728
729 static float *get_editbmesh_orco_verts(BMEditMesh *em)
730 {
731         BMIter iter;
732         BMVert *eve;
733         float *orco;
734         int a, totvert;
735
736         /* these may not really be the orco's, but it's only for preview.
737          * could be solver better once, but isn't simple */
738
739         totvert= em->bm->totvert;
740         
741         orco = MEM_mallocN(sizeof(float)*3*totvert, "EditMesh Orco");
742
743         eve = BMIter_New(&iter, em->bm, BM_VERTS_OF_MESH, NULL);
744         for (a=0; eve; eve=BMIter_Step(&iter), a+=3) {
745                 copy_v3_v3(orco+a, eve->co);
746         }
747         
748         return orco;
749 }
750
751 /* orco custom data layer */
752 static void *get_orco_coords_dm(Object *ob, BMEditMesh *em, int layer, int *free)
753 {
754         *free= 0;
755
756         if(layer == CD_ORCO) {
757                 /* get original coordinates */
758                 *free= 1;
759
760                 if(em)
761                         return (float(*)[3])get_editbmesh_orco_verts(em);
762                 else
763                         return (float(*)[3])get_mesh_orco_verts(ob);
764         }
765         else if(layer == CD_CLOTH_ORCO) {
766                 /* apply shape key for cloth, this should really be solved
767                    by a more flexible customdata system, but not simple */
768                 if(!em) {
769                         ClothModifierData *clmd = (ClothModifierData *)modifiers_findByType(ob, eModifierType_Cloth);
770                         if (clmd) {
771                                 KeyBlock *kb= key_get_keyblock(ob_get_key(ob), clmd->sim_parms->shapekey_rest);
772         
773                                 if(kb->data)
774                                         return kb->data;
775                         }
776                 }
777
778                 return NULL;
779         }
780
781         return NULL;
782 }
783
784 static DerivedMesh *create_orco_dm(Object *ob, Mesh *me, BMEditMesh *em, int layer)
785 {
786         DerivedMesh *dm;
787         float (*orco)[3];
788         int free;
789
790         if(em) dm= CDDM_from_BMEditMesh(em, me, 0);
791         else dm= CDDM_from_mesh(me, ob);
792
793         orco= get_orco_coords_dm(ob, em, layer, &free);
794
795         if(orco) {
796                 CDDM_apply_vert_coords(dm, orco);
797                 if(free) MEM_freeN(orco);
798         }
799
800         CDDM_calc_normals(dm);
801
802         return dm;
803 }
804
805 static void add_orco_dm(Object *ob, BMEditMesh *em, DerivedMesh *dm,
806                                                 DerivedMesh *orcodm, int layer)
807 {
808         float (*orco)[3], (*layerorco)[3];
809         int totvert, free;
810
811         totvert= dm->getNumVerts(dm);
812
813         if(orcodm) {
814                 orco= MEM_callocN(sizeof(float)*3*totvert, "dm orco");
815                 free= 1;
816
817                 if(orcodm->getNumVerts(orcodm) == totvert)
818                         orcodm->getVertCos(orcodm, orco);
819                 else
820                         dm->getVertCos(dm, orco);
821         }
822         else
823                 orco= get_orco_coords_dm(ob, em, layer, &free);
824
825         if(orco) {
826                 if(layer == CD_ORCO)
827                         transform_mesh_orco_verts(ob->data, orco, totvert, 0);
828
829                 if(!(layerorco = DM_get_vert_data_layer(dm, layer))) {
830                         DM_add_vert_layer(dm, layer, CD_CALLOC, NULL);
831                         layerorco = DM_get_vert_data_layer(dm, layer);
832                 }
833
834                 memcpy(layerorco, orco, sizeof(float)*3*totvert);
835                 if(free) MEM_freeN(orco);
836         }
837 }
838
839 /* weight paint colors */
840
841 /* Something of a hack, at the moment deal with weightpaint
842  * by tucking into colors during modifier eval, only in
843  * wpaint mode. Works ok but need to make sure recalc
844  * happens on enter/exit wpaint.
845  */
846
847 void weight_to_rgb(float input, float *fr, float *fg, float *fb)
848 {
849         float blend;
850         
851         blend= ((input/2.0f)+0.5f);
852         
853         if (input<=0.25f){      // blue->cyan
854                 *fr= 0.0f;
855                 *fg= blend*input*4.0f;
856                 *fb= blend;
857         }
858         else if (input<=0.50f){ // cyan->green
859                 *fr= 0.0f;
860                 *fg= blend;
861                 *fb= blend*(1.0f-((input-0.25f)*4.0f)); 
862         }
863         else if (input <= 0.75f){       // green->yellow
864                 *fr= blend * ((input-0.50f)*4.0f);
865                 *fg= blend;
866                 *fb= 0.0f;
867         }
868         else if (input <= 1.0f){ // yellow->red
869                 *fr= blend;
870                 *fg= blend * (1.0f-((input-0.75f)*4.0f)); 
871                 *fb= 0.0f;
872         }
873 }
874
875 /* draw_flag's for calc_weightpaint_vert_color */
876 enum {
877         CALC_WP_MULTIPAINT= (1<<0),
878         CALC_WP_AUTO_NORMALIZE= (1<<1),
879 };
880
881 static void calc_weightpaint_vert_color(Object *ob, ColorBand *coba, int vert, unsigned char *col, char *dg_flags, int selected, int UNUSED(unselected), const int draw_flag)
882 {
883         Mesh *me = ob->data;
884         float colf[4], input = 0.0f;
885         int i;
886
887         
888         int make_black= FALSE;
889
890         if (me->dvert) {
891                 if ((selected > 1) && (draw_flag & CALC_WP_MULTIPAINT)) {
892                         
893                         int was_a_nonzero= FALSE;
894                         for (i=0; i<me->dvert[vert].totweight; i++) {
895                                 /* in multipaint, get the average if auto normalize is inactive
896                                  * get the sum if it is active */
897                                 if(dg_flags[me->dvert[vert].dw[i].def_nr]) {
898                                         if(me->dvert[vert].dw[i].weight) {
899                                                 input+= me->dvert[vert].dw[i].weight;
900                                                 was_a_nonzero= TRUE;
901                                         }
902                                 }
903                         }
904
905                         /* make it black if the selected groups have no weight on a vertex */
906                         if(was_a_nonzero == FALSE) {
907                                 make_black = TRUE;
908                         }
909                         else if ((draw_flag & CALC_WP_AUTO_NORMALIZE) == FALSE) {
910                                 input /= selected; /* get the average */
911                         }
912                 }
913                 else {
914                         /* default, non tricky behavior */
915                         for (i=0; i<me->dvert[vert].totweight; i++) {
916                                 if (me->dvert[vert].dw[i].def_nr==ob->actdef-1) {
917                                         input+=me->dvert[vert].dw[i].weight;
918                                 }
919                         }
920                 }
921         }
922         
923         if (make_black) {
924                 col[3] = 0;
925                 col[2] = 0;
926                 col[1] = 0;
927                 col[0] = 255;
928                 return;
929         }
930
931         CLAMP(input, 0.0f, 1.0f);       
932
933         if(coba)
934                 do_colorband(coba, input, colf);
935         else
936                 weight_to_rgb(input, colf, colf+1, colf+2);
937         
938         col[3] = (unsigned char)(colf[0] * 255.0f);
939         col[2] = (unsigned char)(colf[1] * 255.0f);
940         col[1] = (unsigned char)(colf[2] * 255.0f);
941         col[0] = 255;
942 }
943
944 static ColorBand *stored_cb= NULL;
945
946 void vDM_ColorBand_store(ColorBand *coba)
947 {
948         stored_cb= coba;
949 }
950
951 static void add_weight_mcol_dm(Object *ob, DerivedMesh *dm, int const draw_flag)
952 {
953         // Mesh *me = ob->data; // UNUSED
954         MFace *mf = dm->getTessFaceArray(dm);
955         MLoop *mloop = dm->getLoopArray(dm), *ml;
956         MPoly *mp = dm->getPolyArray(dm);
957         ColorBand *coba= stored_cb;     /* warning, not a local var */
958         unsigned char *wtcol;
959         unsigned char(*wlcol)[4] = NULL;
960         BLI_array_declare(wlcol);
961         int i, j, totface=dm->getNumTessFaces(dm), totloop;
962         int *origIndex = dm->getVertDataArray(dm, CD_ORIGINDEX);
963
964         int defbase_len = BLI_countlist(&ob->defbase);
965         char *defbase_sel = MEM_mallocN(defbase_len * sizeof(char), __func__);
966         int selected = get_selected_defgroups(ob, defbase_sel, defbase_len);
967         int unselected = defbase_len - selected;
968
969         wtcol = MEM_callocN (sizeof (unsigned char) * totface*4*4, "weightmap");
970         
971         /*first add colors to the tesselation faces*/
972         memset(wtcol, 0x55, sizeof (unsigned char) * totface*4*4);
973         for (i=0; i<totface; i++, mf++) {
974                 /*origindex being NULL means we're operating on original mesh data*/
975                 calc_weightpaint_vert_color(ob, coba, mf->v1, &wtcol[(i*4 + 0)*4], defbase_sel, selected, unselected, draw_flag);
976                 calc_weightpaint_vert_color(ob, coba, mf->v2, &wtcol[(i*4 + 1)*4], defbase_sel, selected, unselected, draw_flag);
977                 calc_weightpaint_vert_color(ob, coba, mf->v3, &wtcol[(i*4 + 2)*4], defbase_sel, selected, unselected, draw_flag);
978                 if (mf->v4)
979                         calc_weightpaint_vert_color(ob, coba, mf->v4, &wtcol[(i*4 + 3)*4], defbase_sel, selected, unselected, draw_flag);
980         }
981         
982         CustomData_add_layer(&dm->faceData, CD_WEIGHT_MCOL, CD_ASSIGN, wtcol, totface);
983
984         /*now add to loops, so the data can be passed through the modifier stack*/
985         totloop = 0;
986         for (i=0; i<dm->numPolyData; i++, mp++) {
987                 ml = mloop + mp->loopstart;
988
989                 for (j=0; j<mp->totloop; j++, ml++, totloop++) {
990                         BLI_array_growone(wlcol);
991
992                         calc_weightpaint_vert_color(ob, coba, origIndex ? origIndex[ml->v] : ml->v,
993                                                                                 (unsigned char *)&wlcol[totloop], defbase_sel, selected, unselected, draw_flag);
994                 }
995         }
996
997         MEM_freeN(defbase_sel);
998
999         CustomData_add_layer(&dm->loopData, CD_WEIGHT_MLOOPCOL, CD_ASSIGN, wlcol, totloop);
1000 }
1001
1002
1003 static void shapekey_layers_to_keyblocks(DerivedMesh *dm, Mesh *me, int actshape_uid)
1004 {
1005         KeyBlock *kb;
1006         int i, j, tot;
1007         
1008         if (!me->key)
1009                 return; 
1010         
1011         tot = CustomData_number_of_layers(&dm->vertData, CD_SHAPEKEY);
1012         for (i=0; i<tot; i++) {
1013                 CustomDataLayer *layer = &dm->vertData.layers[CustomData_get_layer_index_n(&dm->vertData, CD_SHAPEKEY, i)];
1014                 float (*cos)[3], (*kbcos)[3];
1015                 
1016                 for (kb=me->key->block.first; kb; kb=kb->next) {
1017                         if (kb->uid == layer->uid)
1018                                 break;
1019                 }
1020                 
1021                 if (!kb) {
1022                         kb = add_keyblock(me->key, layer->name);
1023                         kb->uid = layer->uid;
1024                 }
1025                 
1026                 if (kb->data)
1027                         MEM_freeN(kb->data);
1028                 
1029                 cos = CustomData_get_layer_n(&dm->vertData, CD_SHAPEKEY, i);
1030                 kb->totelem = dm->numVertData;
1031
1032                 kb->data = kbcos = MEM_mallocN(sizeof(float)*3*kb->totelem, "kbcos DerivedMesh.c");
1033                 if (kb->uid == actshape_uid) {
1034                         MVert *mvert = dm->getVertArray(dm);
1035                         
1036                         for (j=0; j<dm->numVertData; j++, kbcos++, mvert++) {
1037                                 copy_v3_v3(*kbcos, mvert->co);
1038                         }
1039                 } else {
1040                         for (j=0; j<kb->totelem; j++, cos++, kbcos++) {
1041                                 copy_v3_v3(*kbcos, *cos);
1042                         }
1043                 }
1044         }
1045         
1046         for (kb=me->key->block.first; kb; kb=kb->next) {
1047                 if (kb->totelem != dm->numVertData) {
1048                         if (kb->data)
1049                                 MEM_freeN(kb->data);
1050                         
1051                         kb->totelem = dm->numVertData;
1052                         kb->data = MEM_callocN(sizeof(float)*3*kb->totelem, "kb->data derivedmesh.c");
1053                         fprintf(stderr, "%s: lost a shapekey layer! (bmesh internal error)\n", __func__);
1054                 }
1055         }
1056 }
1057
1058 static void add_shapekey_layers(DerivedMesh *dm, Mesh *me, Object *UNUSED(ob))
1059 {
1060         KeyBlock *kb;
1061         Key *key = me->key;
1062         int a, b;
1063         
1064         if (!me->key)
1065                 return;
1066         
1067         if (dm->numVertData != me->totvert) {
1068                 printf("error in add_shapekey_layers: dm isn't the same size as me\n");
1069                 return;
1070         }
1071                 
1072         for (a=0, kb=key->block.first; kb; kb=kb->next, a++) {
1073                 float (*cos)[3] = CustomData_add_layer_named(&dm->vertData, CD_SHAPEKEY, CD_CALLOC, NULL, dm->numVertData, kb->name);
1074                 int ci = CustomData_get_layer_index_n(&dm->vertData, CD_SHAPEKEY, a);
1075                 
1076                 dm->vertData.layers[ci].uid = kb->uid;
1077                 if (kb->totelem != dm->numVertData) {
1078                         printf("error in add_shapekey_layers: totelem and totvert don't match");
1079                         continue;
1080                 }
1081                 
1082                 for (b=0; b<kb->totelem; b++, cos++) {
1083                         copy_v3_v3((float *)cos, ((float*)kb->data)+b*3);
1084                 }
1085         }
1086 }
1087
1088 /* new value for useDeform -1  (hack for the gameengine):
1089  * - apply only the modifier stack of the object, skipping the virtual modifiers,
1090  * - don't apply the key
1091  * - apply deform modifiers and input vertexco
1092  */
1093 static void mesh_calc_modifiers(Scene *scene, Object *ob, float (*inputVertexCos)[3],
1094                                                                 DerivedMesh **deform_r, DerivedMesh **final_r,
1095                                                                 int useRenderParams, int useDeform,
1096                                                                 int needMapping, CustomDataMask dataMask, 
1097                                                                 int index, int useCache, int build_shapekey_layers)
1098 {
1099         Mesh *me = ob->data;
1100         ModifierData *firstmd, *md;
1101         LinkNode *datamasks, *curr;
1102         CustomDataMask mask, nextmask, append_mask = 0;
1103         float (*deformedVerts)[3] = NULL;
1104         DerivedMesh *dm=NULL, *orcodm, *clothorcodm, *finaldm;
1105         int numVerts = me->totvert;
1106         int required_mode;
1107         int isPrevDeform= FALSE;
1108         int skipVirtualArmature = (useDeform < 0);
1109         MultiresModifierData *mmd= get_multires_modifier(scene, ob, 0);
1110         int has_multires = mmd != NULL, multires_applied = 0;
1111         int sculpt_mode = ob->mode & OB_MODE_SCULPT && ob->sculpt;
1112
1113         int draw_flag= ((scene->toolsettings->multipaint ? CALC_WP_MULTIPAINT : 0) |
1114                         (scene->toolsettings->auto_normalize ? CALC_WP_AUTO_NORMALIZE : 0));
1115
1116         if(mmd && !mmd->sculptlvl)
1117                 has_multires = 0;
1118
1119         if(!skipVirtualArmature) {
1120                 firstmd = modifiers_getVirtualModifierList(ob);
1121         }
1122         else {
1123                 /* game engine exception */
1124                 firstmd = ob->modifiers.first;
1125                 if(firstmd && firstmd->type == eModifierType_Armature)
1126                         firstmd = firstmd->next;
1127         }
1128
1129         md = firstmd;
1130
1131         modifiers_clearErrors(ob);
1132
1133         if(useRenderParams) required_mode = eModifierMode_Render;
1134         else required_mode = eModifierMode_Realtime;
1135
1136         datamasks = modifiers_calcDataMasks(scene, ob, md, dataMask, required_mode);
1137         curr = datamasks;
1138
1139         if(deform_r) *deform_r = NULL;
1140         *final_r = NULL;
1141
1142         if(useDeform) {
1143                 if(inputVertexCos)
1144                         deformedVerts = inputVertexCos;
1145                 
1146                 /* Apply all leading deforming modifiers */
1147                 for(;md; md = md->next, curr = curr->next) {
1148                         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
1149
1150                         md->scene= scene;
1151                         
1152                         if(!modifier_isEnabled(scene, md, required_mode)) continue;
1153                         if(useDeform < 0 && mti->dependsOnTime && mti->dependsOnTime(md)) continue;
1154
1155                         if(mti->type == eModifierTypeType_OnlyDeform) {
1156                                 if(!deformedVerts)
1157                                         deformedVerts = mesh_getVertexCos(me, &numVerts);
1158
1159                                 mti->deformVerts(md, ob, NULL, deformedVerts, numVerts, useRenderParams, useDeform);
1160                         } else {
1161                                 break;
1162                         }
1163                         
1164                         /* grab modifiers until index i */
1165                         if((index >= 0) && (modifiers_indexInObject(ob, md) >= index))
1166                                 break;
1167                 }
1168
1169                 /* Result of all leading deforming modifiers is cached for
1170                  * places that wish to use the original mesh but with deformed
1171                  * coordinates (vpaint, etc.)
1172                  */
1173                 if (deform_r) {
1174                         *deform_r = CDDM_from_mesh(me, ob);
1175                         
1176                         if (build_shapekey_layers)
1177                                 add_shapekey_layers(dm, me, ob);
1178                         
1179                         if(deformedVerts) {
1180                                 CDDM_apply_vert_coords(*deform_r, deformedVerts);
1181                                 CDDM_calc_normals(*deform_r);
1182                         }
1183                 }
1184         } else {
1185                 /* default behaviour for meshes */
1186                 if(inputVertexCos)
1187                         deformedVerts = inputVertexCos;
1188                 else
1189                         deformedVerts = mesh_getVertexCos(me, &numVerts);
1190         }
1191
1192
1193         /* Now apply all remaining modifiers. If useDeform is off then skip
1194          * OnlyDeform ones. 
1195          */
1196         dm = NULL;
1197         orcodm = NULL;
1198         clothorcodm = NULL;
1199
1200         for(;md; md = md->next, curr = curr->next) {
1201                 ModifierTypeInfo *mti = modifierType_getInfo(md->type);
1202
1203                 md->scene= scene;
1204
1205                 if(!modifier_isEnabled(scene, md, required_mode)) continue;
1206                 if(mti->type == eModifierTypeType_OnlyDeform && !useDeform) continue;
1207                 if((mti->flags & eModifierTypeFlag_RequiresOriginalData) && dm) {
1208                         modifier_setError(md, "Modifier requires original data, bad stack position.");
1209                         continue;
1210                 }
1211                 if(sculpt_mode && (!has_multires || multires_applied)) {
1212                         int unsupported= 0;
1213
1214                         if(scene->toolsettings->sculpt->flags & SCULPT_ONLY_DEFORM)
1215                                 unsupported|= mti->type != eModifierTypeType_OnlyDeform;
1216
1217                         unsupported|= md->type == eModifierType_Multires && ((MultiresModifierData*)md)->sculptlvl==0;
1218                         unsupported|= multires_applied;
1219
1220                         if(unsupported) {
1221                                 modifier_setError(md, "Not supported in sculpt mode.");
1222                                 continue;
1223                         }
1224                 }
1225                 if(needMapping && !modifier_supportsMapping(md)) continue;
1226                 if(useDeform < 0 && mti->dependsOnTime && mti->dependsOnTime(md)) continue;
1227
1228                 /* add an orco layer if needed by this modifier */
1229                 if(mti->requiredDataMask)
1230                         mask = mti->requiredDataMask(ob, md);
1231                 else
1232                         mask = 0;
1233
1234                 if(dm && (mask & CD_MASK_ORCO))
1235                         add_orco_dm(ob, NULL, dm, orcodm, CD_ORCO);
1236
1237                 /* How to apply modifier depends on (a) what we already have as
1238                  * a result of previous modifiers (could be a DerivedMesh or just
1239                  * deformed vertices) and (b) what type the modifier is.
1240                  */
1241
1242                 if(mti->type == eModifierTypeType_OnlyDeform) {
1243                         /* No existing verts to deform, need to build them. */
1244                         if(!deformedVerts) {
1245                                 if(dm) {
1246                                         /* Deforming a derived mesh, read the vertex locations
1247                                          * out of the mesh and deform them. Once done with this
1248                                          * run of deformers verts will be written back.
1249                                          */
1250                                         numVerts = dm->getNumVerts(dm);
1251                                         deformedVerts =
1252                                                 MEM_mallocN(sizeof(*deformedVerts) * numVerts, "dfmv");
1253                                         dm->getVertCos(dm, deformedVerts);
1254                                 } else {
1255                                         deformedVerts = mesh_getVertexCos(me, &numVerts);
1256                                 }
1257                         }
1258
1259                         /* if this is not the last modifier in the stack then recalculate the normals
1260                          * to avoid giving bogus normals to the next modifier see: [#23673] */
1261                         if(dm && isPrevDeform &&  mti->dependsOnNormals && mti->dependsOnNormals(md)) {
1262                                 /* XXX, this covers bug #23673, but we may need normal calc for other types */
1263                                 if(dm && dm->type == DM_TYPE_CDDM) {
1264                                         CDDM_apply_vert_coords(dm, deformedVerts);
1265                                         CDDM_calc_normals(dm);
1266                                 }
1267                         }
1268
1269                         mti->deformVerts(md, ob, dm, deformedVerts, numVerts, useRenderParams, useDeform);
1270                 } else {
1271                         DerivedMesh *ndm;
1272
1273                         /* determine which data layers are needed by following modifiers */
1274                         if(curr->next)
1275                                 nextmask= (CustomDataMask)GET_INT_FROM_POINTER(curr->next->link);
1276                         else
1277                                 nextmask= dataMask;
1278
1279                         /* apply vertex coordinates or build a DerivedMesh as necessary */
1280                         if(dm) {
1281                                 if(deformedVerts) {
1282                                         DerivedMesh *tdm = CDDM_copy(dm, 0);
1283                                         dm->release(dm);
1284                                         dm = tdm;
1285
1286                                         CDDM_apply_vert_coords(dm, deformedVerts);
1287                                         CDDM_calc_normals(dm);
1288                                 }
1289                         } else {
1290                                 dm = CDDM_from_mesh(me, ob);
1291
1292                                 if (build_shapekey_layers)
1293                                         add_shapekey_layers(dm, me, ob);
1294
1295                                 if(deformedVerts) {
1296                                         CDDM_apply_vert_coords(dm, deformedVerts);
1297                                         CDDM_calc_normals(dm);
1298                                 }
1299
1300                                 /* Constructive modifiers need to have an origindex
1301                                  * otherwise they wont have anywhere to copy the data from.
1302                                  *
1303                                  * Also create ORIGINDEX data if any of the following modifiers
1304                                  * requests it, this way Mirror, Solidify etc will keep ORIGINDEX
1305                                  * data by using generic DM_copy_vert_data() functions.
1306                                  */
1307                                 if(needMapping || (nextmask & CD_MASK_ORIGINDEX)) {
1308                                         /* calc */
1309                                         DM_add_vert_layer(dm, CD_ORIGINDEX, CD_CALLOC, NULL);
1310                                         DM_add_edge_layer(dm, CD_ORIGINDEX, CD_CALLOC, NULL);
1311                                         DM_add_face_layer(dm, CD_ORIGINDEX, CD_CALLOC, NULL);
1312
1313                                         range_vn_i(DM_get_vert_data_layer(dm, CD_ORIGINDEX), dm->numVertData, 0);
1314                                         range_vn_i(DM_get_edge_data_layer(dm, CD_ORIGINDEX), dm->numEdgeData, 0);
1315                                         range_vn_i(DM_get_face_data_layer(dm, CD_ORIGINDEX), dm->numPolyData, 0);
1316                                 }
1317
1318                                 if((dataMask & CD_MASK_WEIGHT_MCOL) && (ob->mode & OB_MODE_WEIGHT_PAINT))
1319                                         add_weight_mcol_dm(ob, dm, draw_flag);
1320
1321                         }
1322
1323                         
1324                         /* set the DerivedMesh to only copy needed data */
1325                         mask= (CustomDataMask)GET_INT_FROM_POINTER(curr->link);
1326                         /* needMapping check here fixes bug [#28112], otherwise its
1327                          * possible that it wont be copied */
1328                         mask |= append_mask;
1329                         DM_set_only_copy(dm, mask | (needMapping ? CD_MASK_ORIGINDEX : 0));
1330                         
1331                         /* add cloth rest shape key if need */
1332                         if(mask & CD_MASK_CLOTH_ORCO)
1333                                 add_orco_dm(ob, NULL, dm, clothorcodm, CD_CLOTH_ORCO);
1334
1335                         /* add an origspace layer if needed */
1336                         if(((CustomDataMask)GET_INT_FROM_POINTER(curr->link)) & CD_MASK_ORIGSPACE)
1337                                 if(!CustomData_has_layer(&dm->faceData, CD_ORIGSPACE))
1338                                         DM_add_tessface_layer(dm, CD_ORIGSPACE, CD_DEFAULT, NULL);
1339
1340                         ndm = mti->applyModifier(md, ob, dm, useRenderParams, useCache);
1341
1342                         if(ndm) {
1343                                 /* if the modifier returned a new dm, release the old one */
1344                                 if(dm && dm != ndm) dm->release(dm);
1345
1346                                 dm = ndm;
1347
1348                                 if(deformedVerts) {
1349                                         if(deformedVerts != inputVertexCos)
1350                                                 MEM_freeN(deformedVerts);
1351
1352                                         deformedVerts = NULL;
1353                                 }
1354                         } 
1355
1356                         /* create an orco derivedmesh in parallel */
1357                         if(nextmask & CD_MASK_ORCO) {
1358                                 if(!orcodm)
1359                                         orcodm= create_orco_dm(ob, me, NULL, CD_ORCO);
1360
1361                                 nextmask &= ~CD_MASK_ORCO;
1362                                 DM_set_only_copy(orcodm, nextmask | CD_MASK_ORIGINDEX);
1363                                 ndm = mti->applyModifier(md, ob, orcodm, useRenderParams, 0);
1364
1365                                 if(ndm) {
1366                                         /* if the modifier returned a new dm, release the old one */
1367                                         if(orcodm && orcodm != ndm) orcodm->release(orcodm);
1368                                         orcodm = ndm;
1369                                 }
1370                         }
1371
1372                         /* create cloth orco derivedmesh in parallel */
1373                         if(nextmask & CD_MASK_CLOTH_ORCO) {
1374                                 if(!clothorcodm)
1375                                         clothorcodm= create_orco_dm(ob, me, NULL, CD_CLOTH_ORCO);
1376
1377                                 nextmask &= ~CD_MASK_CLOTH_ORCO;
1378                                 DM_set_only_copy(clothorcodm, nextmask | CD_MASK_ORIGINDEX);
1379                                 ndm = mti->applyModifier(md, ob, clothorcodm, useRenderParams, 0);
1380
1381                                 if(ndm) {
1382                                         /* if the modifier returned a new dm, release the old one */
1383                                         if(clothorcodm && clothorcodm != ndm) clothorcodm->release(clothorcodm);
1384                                         clothorcodm = ndm;
1385                                 }
1386                         }
1387
1388                         /* in case of dynamic paint, make sure preview mask remains for following modifiers */
1389                         if (md->type == eModifierType_DynamicPaint)
1390                                 append_mask |= CD_MASK_WEIGHT_MCOL;
1391                 }
1392
1393                 isPrevDeform= (mti->type == eModifierTypeType_OnlyDeform);
1394
1395                 /* grab modifiers until index i */
1396                 if((index >= 0) && (modifiers_indexInObject(ob, md) >= index))
1397                         break;
1398
1399                 if(sculpt_mode && md->type == eModifierType_Multires)
1400                         multires_applied = 1;
1401         }
1402
1403         for(md=firstmd; md; md=md->next)
1404                 modifier_freeTemporaryData(md);
1405
1406         /* Yay, we are done. If we have a DerivedMesh and deformed vertices
1407          * need to apply these back onto the DerivedMesh. If we have no
1408          * DerivedMesh then we need to build one.
1409          */
1410         if(dm && deformedVerts) {
1411                 finaldm = CDDM_copy(dm, 0);
1412
1413                 dm->release(dm);
1414
1415                 CDDM_apply_vert_coords(finaldm, deformedVerts);
1416                 CDDM_calc_normals(finaldm);
1417
1418                 if((dataMask & CD_MASK_WEIGHT_MCOL) && (ob->mode & OB_MODE_WEIGHT_PAINT))
1419                         add_weight_mcol_dm(ob, finaldm, draw_flag);
1420         } else if(dm) {
1421                 finaldm = dm;
1422         } else {
1423                 int recalc_normals= 0;
1424
1425                 finaldm = CDDM_from_mesh(me, ob);
1426                 
1427                 if(build_shapekey_layers) {
1428                         add_shapekey_layers(finaldm, me, ob);
1429                         recalc_normals= 1;
1430                 }
1431                 
1432                 if(deformedVerts) {
1433                         CDDM_apply_vert_coords(finaldm, deformedVerts);
1434                         recalc_normals= 1;
1435                 }
1436
1437                 if(recalc_normals)
1438                         CDDM_calc_normals(finaldm);
1439                 
1440                 if((dataMask & CD_MASK_WEIGHT_MCOL) && (ob->mode & OB_MODE_WEIGHT_PAINT))
1441                         add_weight_mcol_dm(ob, finaldm, draw_flag);
1442         }
1443
1444         /* add an orco layer if needed */
1445         if(dataMask & CD_MASK_ORCO) {
1446                 add_orco_dm(ob, NULL, finaldm, orcodm, CD_ORCO);
1447
1448                 if(deform_r && *deform_r)
1449                         add_orco_dm(ob, NULL, *deform_r, NULL, CD_ORCO);
1450         }
1451
1452 #ifdef WITH_GAMEENGINE
1453         /* NavMesh - this is a hack but saves having a NavMesh modifier */
1454         if ((ob->gameflag & OB_NAVMESH) && (finaldm->type == DM_TYPE_CDDM)) {
1455                 DerivedMesh *tdm;
1456                 tdm= navmesh_dm_createNavMeshForVisualization(finaldm);
1457                 if (finaldm != tdm) {
1458                         finaldm->release(finaldm);
1459                         finaldm= tdm;
1460                 }
1461         }
1462 #endif /* WITH_GAMEENGINE */
1463
1464         /* Re-tesselation is necessary to push render data (uvs, textures, colors)
1465            from loops and polys onto the tessfaces. This may be currently be redundant
1466            in cases where the render mode doesn't use these inputs, but ideally
1467            eventually tesselation would happen on-demand, and this is one of the primary
1468            places it would be needed. */
1469         finaldm->recalcTesselation(finaldm);
1470         finaldm->calcNormals(finaldm);
1471
1472         *final_r = finaldm;
1473
1474         if(orcodm)
1475                 orcodm->release(orcodm);
1476         if(clothorcodm)
1477                 clothorcodm->release(clothorcodm);
1478
1479         if(deformedVerts && deformedVerts != inputVertexCos)
1480                 MEM_freeN(deformedVerts);
1481
1482         BLI_linklist_free(datamasks, NULL);
1483 }
1484
1485 float (*editbmesh_get_vertex_cos(BMEditMesh *em, int *numVerts_r))[3]
1486 {
1487         int i, numVerts = *numVerts_r = em->bm->totvert;
1488         float (*cos)[3];
1489         BMIter iter;
1490         BMVert *eve;
1491
1492         cos = MEM_mallocN(sizeof(float)*3*numVerts, "vertexcos");
1493
1494         eve = BMIter_New(&iter, em->bm, BM_VERTS_OF_MESH, NULL);
1495         for (i=0; eve; eve=BMIter_Step(&iter), i++) {
1496                 copy_v3_v3(cos[i], eve->co);
1497         }
1498
1499         return cos;
1500 }
1501
1502 int editbmesh_modifier_is_enabled(Scene *scene, ModifierData *md, DerivedMesh *dm)
1503 {
1504         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
1505         int required_mode = eModifierMode_Realtime | eModifierMode_Editmode;
1506
1507         if(!modifier_isEnabled(scene, md, required_mode)) return 0;
1508         if((mti->flags & eModifierTypeFlag_RequiresOriginalData) && dm) {
1509                 modifier_setError(md, "Modifier requires original data, bad stack position.");
1510                 return 0;
1511         }
1512         
1513         return 1;
1514 }
1515
1516 static void editbmesh_calc_modifiers(Scene *scene, Object *ob, BMEditMesh *em, DerivedMesh **cage_r,
1517                                                                         DerivedMesh **final_r,
1518                                                                         CustomDataMask dataMask)
1519 {
1520         ModifierData *md;
1521         float (*deformedVerts)[3] = NULL;
1522         CustomDataMask mask;
1523         DerivedMesh *dm = NULL, *orcodm = NULL, *finaldm = NULL;
1524         int i, numVerts = 0, cageIndex = modifiers_getCageIndex(scene, ob, NULL, 1);
1525         LinkNode *datamasks, *curr;
1526         int required_mode = eModifierMode_Realtime | eModifierMode_Editmode;
1527
1528         modifiers_clearErrors(ob);
1529
1530         if(cage_r && cageIndex == -1) {
1531                 *cage_r = getEditDerivedBMesh(em, ob, NULL);
1532         }
1533
1534         md = modifiers_getVirtualModifierList(ob);
1535
1536         datamasks = modifiers_calcDataMasks(scene, ob, md, dataMask, required_mode);
1537
1538         curr = datamasks;
1539         for(i = 0; md; i++, md = md->next, curr = curr->next) {
1540                 ModifierTypeInfo *mti = modifierType_getInfo(md->type);
1541
1542                 md->scene= scene;
1543                 
1544                 if(!editbmesh_modifier_is_enabled(scene, md, dm))
1545                         continue;
1546
1547                 /* add an orco layer if needed by this modifier */
1548                 if(dm && mti->requiredDataMask) {
1549                         mask = mti->requiredDataMask(ob, md);
1550                         if(mask & CD_MASK_ORCO)
1551                                 add_orco_dm(ob, em, dm, orcodm, CD_ORCO);
1552                 }
1553
1554                 /* How to apply modifier depends on (a) what we already have as
1555                  * a result of previous modifiers (could be a DerivedMesh or just
1556                  * deformed vertices) and (b) what type the modifier is.
1557                  */
1558
1559                 if(mti->type == eModifierTypeType_OnlyDeform) {
1560                         /* No existing verts to deform, need to build them. */
1561                         if(!deformedVerts) {
1562                                 if(dm) {
1563                                         /* Deforming a derived mesh, read the vertex locations
1564                                          * out of the mesh and deform them. Once done with this
1565                                          * run of deformers verts will be written back.
1566                                          */
1567                                         numVerts = dm->getNumVerts(dm);
1568                                         deformedVerts =
1569                                                 MEM_mallocN(sizeof(*deformedVerts) * numVerts, "dfmv");
1570                                         dm->getVertCos(dm, deformedVerts);
1571                                 } else {
1572                                         deformedVerts = editbmesh_get_vertex_cos(em, &numVerts);
1573                                 }
1574                         }
1575
1576                         if (mti->deformVertsEM)
1577                                 mti->deformVertsEM(md, ob, em, dm, deformedVerts, numVerts);
1578                         else mti->deformVerts(md, ob, dm, deformedVerts, numVerts, 0, 0);
1579                 } else {
1580                         DerivedMesh *ndm;
1581
1582                         /* apply vertex coordinates or build a DerivedMesh as necessary */
1583                         if(dm) {
1584                                 if(deformedVerts) {
1585                                         DerivedMesh *tdm = CDDM_copy(dm, 0);
1586                                         if(!(cage_r && dm == *cage_r)) dm->release(dm);
1587                                         dm = tdm;
1588
1589                                         CDDM_apply_vert_coords(dm, deformedVerts);
1590                                         CDDM_calc_normals(dm);
1591                                 } else if(cage_r && dm == *cage_r) {
1592                                         /* dm may be changed by this modifier, so we need to copy it
1593                                          */
1594                                         dm = CDDM_copy(dm, 0);
1595                                 }
1596
1597                         } else {
1598                                 dm = CDDM_from_BMEditMesh(em, ob->data, 0);
1599
1600                                 if(deformedVerts) {
1601                                         CDDM_apply_vert_coords(dm, deformedVerts);
1602                                         CDDM_calc_normals(dm);
1603                                 }
1604                         }
1605
1606                         /* create an orco derivedmesh in parallel */
1607                         mask= (CustomDataMask)GET_INT_FROM_POINTER(curr->link);
1608                         if(mask & CD_MASK_ORCO) {
1609                                 if(!orcodm)
1610                                         orcodm= create_orco_dm(ob, ob->data, em, CD_ORCO);
1611
1612                                 mask &= ~CD_MASK_ORCO;
1613                                 DM_set_only_copy(orcodm, mask | CD_MASK_ORIGINDEX);
1614
1615                                 if (mti->applyModifierEM)
1616                                         ndm = mti->applyModifierEM(md, ob, em, orcodm);
1617                                 else
1618                                         ndm = mti->applyModifier(md, ob, orcodm, 0, 0);
1619
1620                                 if(ndm) {
1621                                         /* if the modifier returned a new dm, release the old one */
1622                                         if(orcodm && orcodm != ndm) orcodm->release(orcodm);
1623                                         orcodm = ndm;
1624                                 }
1625                         }
1626
1627                         /* set the DerivedMesh to only copy needed data */
1628                         mask= (CustomDataMask)GET_INT_FROM_POINTER(curr->link); /* CD_MASK_ORCO may have been cleared above */
1629
1630                         DM_set_only_copy(dm, mask | CD_MASK_ORIGINDEX);
1631
1632                         if(mask & CD_MASK_ORIGSPACE)
1633                                 if(!CustomData_has_layer(&dm->faceData, CD_ORIGSPACE))
1634                                         DM_add_tessface_layer(dm, CD_ORIGSPACE, CD_DEFAULT, NULL);
1635                         
1636                         if (mti->applyModifierEM)
1637                                 ndm = mti->applyModifierEM(md, ob, em, dm);
1638                         else
1639                                 ndm = mti->applyModifier(md, ob, dm, 0, 0);
1640
1641                         if (ndm) {
1642                                 if(dm && dm != ndm)
1643                                         dm->release(dm);
1644
1645                                 dm = ndm;
1646
1647                                 if (deformedVerts) {
1648                                         MEM_freeN(deformedVerts);
1649                                         deformedVerts = NULL;
1650                                 }
1651                         }
1652                 }
1653
1654                 if(cage_r && i == cageIndex) {
1655                         if(dm && deformedVerts) {
1656                                 *cage_r = CDDM_copy(dm, 0);
1657                                 CDDM_apply_vert_coords(*cage_r, deformedVerts);
1658                         } else if(dm) {
1659                                 *cage_r = dm;
1660                         } else {
1661                                 *cage_r =
1662                                         getEditDerivedBMesh(em, ob,
1663                                                 deformedVerts ? MEM_dupallocN(deformedVerts) : NULL);
1664                         }
1665                 }
1666         }
1667
1668         BLI_linklist_free(datamasks, NULL);
1669
1670         /* Yay, we are done. If we have a DerivedMesh and deformed vertices need
1671          * to apply these back onto the DerivedMesh. If we have no DerivedMesh
1672          * then we need to build one.
1673          */
1674         if(dm && deformedVerts) {
1675                 finaldm = CDDM_copy(dm, 0);
1676
1677                 if(!(cage_r && dm == *cage_r)) dm->release(dm);
1678
1679                 CDDM_apply_vert_coords(*final_r, deformedVerts);
1680         } else if (dm) {
1681                 finaldm = dm;
1682         } else if (!deformedVerts && cage_r && *cage_r) {
1683                 finaldm = *cage_r;
1684         } else {
1685                 finaldm = getEditDerivedBMesh(em, ob, deformedVerts);
1686                 deformedVerts = NULL;
1687         }
1688
1689         finaldm->calcNormals(finaldm);
1690
1691         *final_r = finaldm;
1692
1693         /* add an orco layer if needed */
1694         if(dataMask & CD_MASK_ORCO)
1695                 add_orco_dm(ob, em, *final_r, orcodm, CD_ORCO);
1696
1697         if(orcodm)
1698                 orcodm->release(orcodm);
1699
1700         if(deformedVerts)
1701                 MEM_freeN(deformedVerts);
1702 }
1703
1704 static void clear_mesh_caches(Object *ob)
1705 {
1706         Mesh *me= ob->data;
1707
1708                 /* also serves as signal to remake texspace */
1709         if (ob->bb) {
1710                 MEM_freeN(ob->bb);
1711                 ob->bb = NULL;
1712         }
1713         if (me->bb) {
1714                 MEM_freeN(me->bb);
1715                 me->bb = NULL;
1716         }
1717
1718         freedisplist(&ob->disp);
1719
1720         if (ob->derivedFinal) {
1721                 ob->derivedFinal->needsFree = 1;
1722                 ob->derivedFinal->release(ob->derivedFinal);
1723                 ob->derivedFinal= NULL;
1724         }
1725         if (ob->derivedDeform) {
1726                 ob->derivedDeform->needsFree = 1;
1727                 ob->derivedDeform->release(ob->derivedDeform);
1728                 ob->derivedDeform= NULL;
1729         }
1730
1731         if(ob->sculpt) {
1732                 object_sculpt_modifiers_changed(ob);
1733         }
1734 }
1735
1736 static void mesh_build_data(Scene *scene, Object *ob, CustomDataMask dataMask,
1737         int build_shapekey_layers)
1738 {
1739         Object *obact = scene->basact?scene->basact->object:NULL;
1740         int editing = paint_facesel_test(ob);
1741         /* weight paint and face select need original indices because of selection buffer drawing */
1742         int needMapping = (ob==obact) && (editing || (ob->mode & (OB_MODE_WEIGHT_PAINT|OB_MODE_VERTEX_PAINT|OB_MODE_TEXTURE_PAINT)));
1743
1744         clear_mesh_caches(ob);
1745
1746         mesh_calc_modifiers(scene, ob, NULL, &ob->derivedDeform,
1747                                                 &ob->derivedFinal, 0, 1,
1748                                                 needMapping, dataMask, -1, 1, build_shapekey_layers);
1749
1750         DM_set_object_boundbox (ob, ob->derivedFinal);
1751
1752         ob->derivedFinal->needsFree = 0;
1753         ob->derivedDeform->needsFree = 0;
1754         ob->lastDataMask = dataMask;
1755 }
1756
1757 static void editbmesh_build_data(Scene *scene, Object *obedit, BMEditMesh *em, CustomDataMask dataMask)
1758 {
1759         clear_mesh_caches(obedit);
1760
1761         if (em->derivedFinal) {
1762                 if (em->derivedFinal!=em->derivedCage) {
1763                         em->derivedFinal->needsFree = 1;
1764                         em->derivedFinal->release(em->derivedFinal);
1765                 }
1766                 em->derivedFinal = NULL;
1767         }
1768         if (em->derivedCage) {
1769                 em->derivedCage->needsFree = 1;
1770                 em->derivedCage->release(em->derivedCage);
1771                 em->derivedCage = NULL;
1772         }
1773
1774         editbmesh_calc_modifiers(scene, obedit, em, &em->derivedCage, &em->derivedFinal, dataMask);
1775         DM_set_object_boundbox (obedit, em->derivedFinal);
1776
1777         em->lastDataMask = dataMask;
1778         em->derivedFinal->needsFree = 0;
1779         em->derivedCage->needsFree = 0;
1780 }
1781
1782 void makeDerivedMesh(Scene *scene, Object *ob, BMEditMesh *em,
1783         CustomDataMask dataMask, int build_shapekey_layers)
1784 {
1785         if (em) {
1786                 editbmesh_build_data(scene, ob, em, dataMask);
1787         } else {
1788                 mesh_build_data(scene, ob, dataMask, build_shapekey_layers);
1789         }
1790 }
1791
1792 /***/
1793
1794 DerivedMesh *mesh_get_derived_final(Scene *scene, Object *ob, CustomDataMask dataMask)
1795 {
1796         /* if there's no derived mesh or the last data mask used doesn't include
1797          * the data we need, rebuild the derived mesh
1798          */
1799         if(!ob->derivedFinal || (dataMask & ob->lastDataMask) != dataMask)
1800                 mesh_build_data(scene, ob, dataMask, 0);
1801
1802         return ob->derivedFinal;
1803 }
1804
1805 DerivedMesh *mesh_get_derived_deform(Scene *scene, Object *ob, CustomDataMask dataMask)
1806 {
1807         /* if there's no derived mesh or the last data mask used doesn't include
1808          * the data we need, rebuild the derived mesh
1809          */
1810         if(!ob->derivedDeform || (dataMask & ob->lastDataMask) != dataMask)
1811                 mesh_build_data(scene, ob, dataMask, 0);
1812
1813         return ob->derivedDeform;
1814 }
1815
1816 DerivedMesh *mesh_create_derived_render(Scene *scene, Object *ob, CustomDataMask dataMask)
1817 {
1818         DerivedMesh *final;
1819         
1820         mesh_calc_modifiers(scene, ob, NULL, NULL, &final, 1, 1, 0, dataMask, -1, 0, 0);
1821
1822         return final;
1823 }
1824
1825 DerivedMesh *mesh_create_derived_index_render(Scene *scene, Object *ob, CustomDataMask dataMask, int index)
1826 {
1827         DerivedMesh *final;
1828         
1829         mesh_calc_modifiers(scene, ob, NULL, NULL, &final, 1, 1, 0, dataMask, index, 0, 0);
1830
1831         return final;
1832 }
1833
1834 DerivedMesh *mesh_create_derived_view(Scene *scene, Object *ob, CustomDataMask dataMask)
1835 {
1836         DerivedMesh *final;
1837
1838         mesh_calc_modifiers(scene, ob, NULL, NULL, &final, 0, 1, 0, dataMask, -1, 0, 0);
1839
1840         return final;
1841 }
1842
1843 DerivedMesh *mesh_create_derived_no_deform(Scene *scene, Object *ob, float (*vertCos)[3],
1844                                                                                    CustomDataMask dataMask)
1845 {
1846         DerivedMesh *final;
1847         
1848         mesh_calc_modifiers(scene, ob, vertCos, NULL, &final, 0, 0, 0, dataMask, -1, 0, 0);
1849
1850         return final;
1851 }
1852
1853 DerivedMesh *mesh_create_derived_no_virtual(Scene *scene, Object *ob, float (*vertCos)[3],
1854                                                                                         CustomDataMask dataMask)
1855 {
1856         DerivedMesh *final;
1857         
1858         mesh_calc_modifiers(scene, ob, vertCos, NULL, &final, 0, -1, 0, dataMask, -1, 0, 0);
1859
1860         return final;
1861 }
1862
1863 DerivedMesh *mesh_create_derived_physics(Scene *scene, Object *ob, float (*vertCos)[3],
1864                                                                                         CustomDataMask dataMask)
1865 {
1866         DerivedMesh *final;
1867         
1868         mesh_calc_modifiers(scene, ob, vertCos, NULL, &final, 0, -1, 1, dataMask, -1, 0, 0);
1869
1870         return final;
1871 }
1872
1873 DerivedMesh *mesh_create_derived_no_deform_render(Scene *scene, Object *ob,
1874                                                                                                   float (*vertCos)[3],
1875                                                                                                   CustomDataMask dataMask)
1876 {
1877         DerivedMesh *final;
1878
1879         mesh_calc_modifiers(scene, ob, vertCos, NULL, &final, 1, 0, 0, dataMask, -1, 0, 0);
1880
1881         return final;
1882 }
1883
1884 /***/
1885
1886 DerivedMesh *editbmesh_get_derived_cage_and_final(Scene *scene, Object *obedit, BMEditMesh *em, DerivedMesh **final_r,
1887                                                                                                  CustomDataMask dataMask)
1888 {
1889         /* if there's no derived mesh or the last data mask used doesn't include
1890          * the data we need, rebuild the derived mesh
1891          */
1892         if(!em->derivedCage ||
1893            (em->lastDataMask & dataMask) != dataMask)
1894                 editbmesh_build_data(scene, obedit, em, dataMask);
1895
1896         *final_r = em->derivedFinal;
1897         return em->derivedCage;
1898 }
1899
1900 DerivedMesh *editbmesh_get_derived_cage(Scene *scene, Object *obedit, BMEditMesh *em, CustomDataMask dataMask)
1901 {
1902         /* if there's no derived mesh or the last data mask used doesn't include
1903          * the data we need, rebuild the derived mesh
1904          */
1905         if(!em->derivedCage ||
1906            (em->lastDataMask & dataMask) != dataMask)
1907                 editbmesh_build_data(scene, obedit, em, dataMask);
1908
1909         return em->derivedCage;
1910 }
1911
1912 DerivedMesh *editbmesh_get_derived_base(Object *obedit, BMEditMesh *em)
1913 {
1914         return getEditDerivedBMesh(em, obedit, NULL);
1915 }
1916
1917
1918 /* ********* For those who don't grasp derived stuff! (ton) :) *************** */
1919
1920 static void make_vertexcosnos__mapFunc(void *userData, int index, float *co, float *no_f, short *no_s)
1921 {
1922         float *vec = userData;
1923         
1924         vec+= 6*index;
1925
1926         /* check if we've been here before (normal should not be 0) */
1927         if(vec[3] || vec[4] || vec[5]) return;
1928
1929         copy_v3_v3(vec, co);
1930         vec+= 3;
1931         if(no_f) {
1932                 copy_v3_v3(vec, no_f);
1933         }
1934         else {
1935                 normal_short_to_float_v3(vec, no_s);
1936         }
1937 }
1938
1939 /* always returns original amount me->totvert of vertices and normals, but fully deformed and subsurfered */
1940 /* this is needed for all code using vertexgroups (no subsurf support) */
1941 /* it stores the normals as floats, but they can still be scaled as shorts (32767 = unit) */
1942 /* in use now by vertex/weight paint and particle generating */
1943
1944 float *mesh_get_mapped_verts_nors(Scene *scene, Object *ob)
1945 {
1946         Mesh *me= ob->data;
1947         DerivedMesh *dm;
1948         float *vertexcosnos;
1949         
1950         /* lets prevent crashing... */
1951         if(ob->type!=OB_MESH || me->totvert==0)
1952                 return NULL;
1953         
1954         dm= mesh_get_derived_final(scene, ob, CD_MASK_BAREMESH|CD_MASK_ORIGINDEX);
1955         vertexcosnos= MEM_callocN(6*sizeof(float)*me->totvert, "vertexcosnos map");
1956         
1957         if(dm->foreachMappedVert) {
1958                 dm->foreachMappedVert(dm, make_vertexcosnos__mapFunc, vertexcosnos);
1959         }
1960         else {
1961                 float *fp= vertexcosnos;
1962                 int a;
1963                 
1964                 for(a=0; a< me->totvert; a++, fp+=6) {
1965                         dm->getVertCo(dm, a, fp);
1966                         dm->getVertNo(dm, a, fp+3);
1967                 }
1968         }
1969         
1970         dm->release(dm);
1971         return vertexcosnos;
1972 }
1973
1974 /* ******************* GLSL ******************** */
1975
1976 typedef struct
1977 {
1978         float * precomputedFaceNormals;
1979         MTFace * mtface;        // texture coordinates
1980         MFace * mface;          // indices
1981         MVert * mvert;          // vertices & normals
1982         float (*orco)[3];
1983         float (*tangent)[4];    // destination
1984         int numFaces;
1985
1986 } SGLSLMeshToTangent;
1987
1988 // interface
1989 #include "mikktspace.h"
1990
1991 static int GetNumFaces(const SMikkTSpaceContext * pContext)
1992 {
1993         SGLSLMeshToTangent * pMesh = (SGLSLMeshToTangent *) pContext->m_pUserData;
1994         return pMesh->numFaces;
1995 }
1996
1997 static int GetNumVertsOfFace(const SMikkTSpaceContext * pContext, const int face_num)
1998 {
1999         SGLSLMeshToTangent * pMesh = (SGLSLMeshToTangent *) pContext->m_pUserData;
2000         return pMesh->mface[face_num].v4!=0 ? 4 : 3;
2001 }
2002
2003 static void GetPosition(const SMikkTSpaceContext * pContext, float fPos[], const int face_num, const int vert_index)
2004 {
2005         //assert(vert_index>=0 && vert_index<4);
2006         SGLSLMeshToTangent * pMesh = (SGLSLMeshToTangent *) pContext->m_pUserData;
2007         const float *co= pMesh->mvert[(&pMesh->mface[face_num].v1)[vert_index]].co;
2008         copy_v3_v3(fPos, co);
2009 }
2010
2011 static void GetTextureCoordinate(const SMikkTSpaceContext * pContext, float fUV[], const int face_num, const int vert_index)
2012 {
2013         //assert(vert_index>=0 && vert_index<4);
2014         SGLSLMeshToTangent * pMesh = (SGLSLMeshToTangent *) pContext->m_pUserData;
2015
2016         if(pMesh->mtface!=NULL) {
2017                 float * uv = pMesh->mtface[face_num].uv[vert_index];
2018                 fUV[0]=uv[0]; fUV[1]=uv[1];
2019         }
2020         else {
2021                 const float *orco= pMesh->orco[(&pMesh->mface[face_num].v1)[vert_index]];
2022                 map_to_sphere( &fUV[0], &fUV[1], orco[0], orco[1], orco[2]);
2023         }
2024 }
2025
2026 static void GetNormal(const SMikkTSpaceContext * pContext, float fNorm[], const int face_num, const int vert_index)
2027 {
2028         //assert(vert_index>=0 && vert_index<4);
2029         SGLSLMeshToTangent * pMesh = (SGLSLMeshToTangent *) pContext->m_pUserData;
2030
2031         const int smoothnormal = (pMesh->mface[face_num].flag & ME_SMOOTH);
2032         if(!smoothnormal) {     // flat
2033                 if(pMesh->precomputedFaceNormals) {
2034                         copy_v3_v3(fNorm, &pMesh->precomputedFaceNormals[3*face_num]);
2035                 }
2036                 else {
2037                         MFace *mf= &pMesh->mface[face_num];
2038                         float *p0= pMesh->mvert[mf->v1].co;
2039                         float *p1= pMesh->mvert[mf->v2].co;
2040                         float *p2= pMesh->mvert[mf->v3].co;
2041
2042                         if(mf->v4) {
2043                                 float *p3 = pMesh->mvert[mf->v4].co;
2044                                 normal_quad_v3(fNorm, p0, p1, p2, p3);
2045                         }
2046                         else {
2047                                 normal_tri_v3(fNorm, p0, p1, p2);
2048                         }
2049                 }
2050         }
2051         else {
2052                 const short *no= pMesh->mvert[(&pMesh->mface[face_num].v1)[vert_index]].no;
2053                 normal_short_to_float_v3(fNorm, no);
2054         }
2055 }
2056 static void SetTSpace(const SMikkTSpaceContext * pContext, const float fvTangent[], const float fSign, const int face_num, const int iVert)
2057 {
2058         //assert(vert_index>=0 && vert_index<4);
2059         SGLSLMeshToTangent * pMesh = (SGLSLMeshToTangent *) pContext->m_pUserData;
2060         float * pRes = pMesh->tangent[4*face_num+iVert];
2061         copy_v3_v3(pRes, fvTangent);
2062         pRes[3]=fSign;
2063 }
2064
2065
2066 void DM_add_tangent_layer(DerivedMesh *dm)
2067 {
2068         /* mesh vars */
2069         MTFace *mtface, *tf;
2070         MFace *mface, *mf;
2071         MVert *mvert, *v1, *v2, *v3, *v4;
2072         MemArena *arena= NULL;
2073         VertexTangent **vtangents= NULL;
2074         float (*orco)[3]= NULL, (*tangent)[4];
2075         float *uv1, *uv2, *uv3, *uv4, *vtang;
2076         float fno[3], tang[3], uv[4][2];
2077         int i, j, len, mf_vi[4], totvert, totface, iCalcNewMethod;
2078         float *nors;
2079
2080         if(CustomData_get_layer_index(&dm->faceData, CD_TANGENT) != -1)
2081                 return;
2082
2083         nors = dm->getTessFaceDataArray(dm, CD_NORMAL);
2084
2085         /* check we have all the needed layers */
2086         totvert= dm->getNumVerts(dm);
2087         totface= dm->getNumTessFaces(dm);
2088
2089         mvert= dm->getVertArray(dm);
2090         mface= dm->getTessFaceArray(dm);
2091         mtface= dm->getTessFaceDataArray(dm, CD_MTFACE);
2092
2093         if(!mtface) {
2094                 orco= dm->getVertDataArray(dm, CD_ORCO);
2095                 if(!orco)
2096                         return;
2097         }
2098         
2099         /* create tangent layer */
2100         DM_add_tessface_layer(dm, CD_TANGENT, CD_CALLOC, NULL);
2101         tangent= DM_get_tessface_data_layer(dm, CD_TANGENT);
2102         
2103         /* allocate some space */
2104         arena= BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, "tangent layer arena");
2105         BLI_memarena_use_calloc(arena);
2106         vtangents= MEM_callocN(sizeof(VertexTangent*)*totvert, "VertexTangent");
2107
2108         // new computation method
2109         iCalcNewMethod = 1;
2110         if(iCalcNewMethod != 0) {
2111                 SGLSLMeshToTangent mesh2tangent= {0};
2112                 SMikkTSpaceContext sContext= {0};
2113                 SMikkTSpaceInterface sInterface= {0};
2114
2115                 mesh2tangent.precomputedFaceNormals = nors;
2116                 mesh2tangent.mtface = mtface;
2117                 mesh2tangent.mface = mface;
2118                 mesh2tangent.mvert = mvert;
2119                 mesh2tangent.orco = orco;
2120                 mesh2tangent.tangent = tangent;
2121                 mesh2tangent.numFaces = totface;
2122
2123                 sContext.m_pUserData = &mesh2tangent;
2124                 sContext.m_pInterface = &sInterface;
2125                 sInterface.m_getNumFaces = GetNumFaces;
2126                 sInterface.m_getNumVerticesOfFace = GetNumVertsOfFace;
2127                 sInterface.m_getPosition = GetPosition;
2128                 sInterface.m_getTexCoord = GetTextureCoordinate;
2129                 sInterface.m_getNormal = GetNormal;
2130                 sInterface.m_setTSpaceBasic = SetTSpace;
2131
2132                 // 0 if failed
2133                 iCalcNewMethod = genTangSpaceDefault(&sContext);
2134         }
2135
2136         if(!iCalcNewMethod) {
2137                 /* sum tangents at connected vertices */
2138                 for(i=0, tf=mtface, mf=mface; i < totface; mf++, tf++, i++) {
2139                         v1= &mvert[mf->v1];
2140                         v2= &mvert[mf->v2];
2141                         v3= &mvert[mf->v3];
2142
2143                         if (mf->v4) {
2144                                 v4= &mvert[mf->v4];
2145                                 normal_quad_v3( fno,v4->co, v3->co, v2->co, v1->co);
2146                         }
2147                         else {
2148                                 v4= NULL;
2149                                 normal_tri_v3( fno,v3->co, v2->co, v1->co);
2150                         }
2151                 
2152                         if(mtface) {
2153                                 uv1= tf->uv[0];
2154                                 uv2= tf->uv[1];
2155                                 uv3= tf->uv[2];
2156                                 uv4= tf->uv[3];
2157                         }
2158                         else {
2159                                 uv1= uv[0]; uv2= uv[1]; uv3= uv[2]; uv4= uv[3];
2160                                 map_to_sphere( &uv[0][0], &uv[0][1],orco[mf->v1][0], orco[mf->v1][1], orco[mf->v1][2]);
2161                                 map_to_sphere( &uv[1][0], &uv[1][1],orco[mf->v2][0], orco[mf->v2][1], orco[mf->v2][2]);
2162                                 map_to_sphere( &uv[2][0], &uv[2][1],orco[mf->v3][0], orco[mf->v3][1], orco[mf->v3][2]);
2163                                 if(v4)
2164                                         map_to_sphere( &uv[3][0], &uv[3][1],orco[mf->v4][0], orco[mf->v4][1], orco[mf->v4][2]);
2165                         }
2166                 
2167                         tangent_from_uv(uv1, uv2, uv3, v1->co, v2->co, v3->co, fno, tang);
2168                         sum_or_add_vertex_tangent(arena, &vtangents[mf->v1], tang, uv1);
2169                         sum_or_add_vertex_tangent(arena, &vtangents[mf->v2], tang, uv2);
2170                         sum_or_add_vertex_tangent(arena, &vtangents[mf->v3], tang, uv3);
2171                 
2172                         if(mf->v4) {
2173                                 v4= &mvert[mf->v4];
2174                         
2175                                 tangent_from_uv(uv1, uv3, uv4, v1->co, v3->co, v4->co, fno, tang);
2176                                 sum_or_add_vertex_tangent(arena, &vtangents[mf->v1], tang, uv1);
2177                                 sum_or_add_vertex_tangent(arena, &vtangents[mf->v3], tang, uv3);
2178                                 sum_or_add_vertex_tangent(arena, &vtangents[mf->v4], tang, uv4);
2179                         }
2180                 }
2181         
2182                 /* write tangent to layer */
2183                 for(i=0, tf=mtface, mf=mface; i < totface; mf++, tf++, i++, tangent+=4) {
2184                         len= (mf->v4)? 4 : 3; 
2185
2186                         if(mtface == NULL) {
2187                                 map_to_sphere( &uv[0][0], &uv[0][1],orco[mf->v1][0], orco[mf->v1][1], orco[mf->v1][2]);
2188                                 map_to_sphere( &uv[1][0], &uv[1][1],orco[mf->v2][0], orco[mf->v2][1], orco[mf->v2][2]);
2189                                 map_to_sphere( &uv[2][0], &uv[2][1],orco[mf->v3][0], orco[mf->v3][1], orco[mf->v3][2]);
2190                                 if(len==4)
2191                                         map_to_sphere( &uv[3][0], &uv[3][1],orco[mf->v4][0], orco[mf->v4][1], orco[mf->v4][2]);
2192                         }
2193                 
2194                         mf_vi[0]= mf->v1;
2195                         mf_vi[1]= mf->v2;
2196                         mf_vi[2]= mf->v3;
2197                         mf_vi[3]= mf->v4;
2198                 
2199                         for(j=0; j<len; j++) {
2200                                 vtang= find_vertex_tangent(vtangents[mf_vi[j]], mtface ? tf->uv[j] : uv[j]);
2201                                 normalize_v3_v3(tangent[j], vtang);
2202                                 ((float *) tangent[j])[3]=1.0f;
2203                         }
2204                 }
2205         }
2206         
2207         BLI_memarena_free(arena);
2208         MEM_freeN(vtangents);
2209 }
2210
2211 void DM_vertex_attributes_from_gpu(DerivedMesh *dm, GPUVertexAttribs *gattribs, DMVertexAttribs *attribs)
2212 {
2213         CustomData *vdata, *fdata, *tfdata = NULL;
2214         int a, b, layer;
2215
2216         /* From the layers requested by the GLSL shader, figure out which ones are
2217          * actually available for this derivedmesh, and retrieve the pointers */
2218
2219         memset(attribs, 0, sizeof(DMVertexAttribs));
2220
2221         vdata = &dm->vertData;
2222         fdata = tfdata = dm->getTessFaceDataLayout(dm);
2223         
2224         /* add a tangent layer if necessary */
2225         for(b = 0; b < gattribs->totlayer; b++)
2226                 if(gattribs->layer[b].type == CD_TANGENT)
2227                         if(CustomData_get_layer_index(fdata, CD_TANGENT) == -1)
2228                                 DM_add_tangent_layer(dm);
2229
2230         for(b = 0; b < gattribs->totlayer; b++) {
2231                 if(gattribs->layer[b].type == CD_MTFACE) {
2232                         /* uv coordinates */
2233                         if(gattribs->layer[b].name[0])
2234                                 layer = CustomData_get_named_layer_index(tfdata, CD_MTFACE,
2235                                         gattribs->layer[b].name);
2236                         else
2237                                 layer = CustomData_get_active_layer_index(tfdata, CD_MTFACE);
2238
2239                         if(layer != -1) {
2240                                 a = attribs->tottface++;
2241
2242                                 attribs->tface[a].array = tfdata->layers[layer].data;
2243                                 attribs->tface[a].emOffset = tfdata->layers[layer].offset;
2244                                 attribs->tface[a].glIndex = gattribs->layer[b].glindex;
2245                         } /*else {
2246                                 int player;
2247                                 CustomData *pdata = dm->getFaceDataLayout(dm);
2248                                 
2249                                 if(gattribs->layer[b].name[0])
2250                                         player = CustomData_get_named_layer_index(pdata, CD_MTEXPOLY,
2251                                                 gattribs->layer[b].name);
2252                                 else
2253                                         player = CustomData_get_active_layer_index(pdata, CD_MTEXPOLY);
2254                                 
2255                                 if (player != -1) {
2256                                         a = attribs->tottface++;
2257         
2258                                         attribs->tface[a].array = NULL;
2259                                         attribs->tface[a].emOffset = pdata->layers[layer].offset;
2260                                         attribs->tface[a].glIndex = gattribs->layer[b].glindex;
2261                                         attribs->tface[a].glTexco = gattribs->layer[b].gltexco;
2262                                         
2263                                 }
2264                         }*/
2265                 }
2266                 else if(gattribs->layer[b].type == CD_MCOL) {
2267                         /* vertex colors */
2268                         if(gattribs->layer[b].name[0])
2269                                 layer = CustomData_get_named_layer_index(tfdata, CD_MCOL,
2270                                         gattribs->layer[b].name);
2271                         else
2272                                 layer = CustomData_get_active_layer_index(tfdata, CD_MCOL);
2273
2274                         if(layer != -1) {
2275                                 a = attribs->totmcol++;
2276
2277                                 attribs->mcol[a].array = tfdata->layers[layer].data;
2278                                 attribs->mcol[a].emOffset = tfdata->layers[layer].offset;
2279                                 attribs->mcol[a].glIndex = gattribs->layer[b].glindex;
2280                         }
2281                 }
2282                 else if(gattribs->layer[b].type == CD_TANGENT) {
2283                         /* tangents */
2284                         layer = CustomData_get_layer_index(fdata, CD_TANGENT);
2285
2286                         if(layer != -1) {
2287                                 attribs->tottang = 1;
2288
2289                                 attribs->tang.array = fdata->layers[layer].data;
2290                                 attribs->tang.emOffset = fdata->layers[layer].offset;
2291                                 attribs->tang.glIndex = gattribs->layer[b].glindex;
2292                         }
2293                 }
2294                 else if(gattribs->layer[b].type == CD_ORCO) {
2295                         /* original coordinates */
2296                         layer = CustomData_get_layer_index(vdata, CD_ORCO);
2297
2298                         if(layer != -1) {
2299                                 attribs->totorco = 1;
2300
2301                                 attribs->orco.array = vdata->layers[layer].data;
2302                                 attribs->orco.emOffset = vdata->layers[layer].offset;
2303                                 attribs->orco.glIndex = gattribs->layer[b].glindex;
2304                                 attribs->orco.glTexco = gattribs->layer[b].gltexco;
2305                         }
2306                 }
2307         }
2308 }
2309
2310 /* Set object's bounding box based on DerivedMesh min/max data */
2311 void DM_set_object_boundbox(Object *ob, DerivedMesh *dm)
2312 {
2313         float min[3], max[3];
2314
2315         INIT_MINMAX(min, max);
2316
2317         dm->getMinMax(dm, min, max);
2318
2319         if(!ob->bb)
2320                 ob->bb= MEM_callocN(sizeof(BoundBox), "DM-BoundBox");
2321
2322         boundbox_set_from_min_max(ob->bb, min, max);
2323 }
2324
2325 /* --- NAVMESH (begin) --- */
2326 #ifdef WITH_GAMEENGINE
2327
2328 BM_INLINE int navmesh_bit(int a, int b)
2329 {
2330         return (a & (1 << b)) >> b;
2331 }
2332
2333 BM_INLINE void navmesh_intToCol(int i, float col[3])
2334 {
2335         int     r = navmesh_bit(i, 0) + navmesh_bit(i, 3) * 2 + 1;
2336         int     g = navmesh_bit(i, 1) + navmesh_bit(i, 4) * 2 + 1;
2337         int     b = navmesh_bit(i, 2) + navmesh_bit(i, 5) * 2 + 1;
2338         col[0] = 1 - r*63.0f/255.0f;
2339         col[1] = 1 - g*63.0f/255.0f;
2340         col[2] = 1 - b*63.0f/255.0f;
2341 }
2342
2343 static void navmesh_drawColored(DerivedMesh *dm)
2344 {
2345         int a, glmode;
2346         MVert *mvert = (MVert *)CustomData_get_layer(&dm->vertData, CD_MVERT);
2347         MFace *mface = (MFace *)CustomData_get_layer(&dm->faceData, CD_MFACE);
2348         int *polygonIdx = (int *)CustomData_get_layer(&dm->faceData, CD_RECAST);
2349         float col[3];
2350
2351         if (!polygonIdx)
2352                 return;
2353
2354         /*
2355         //UI_ThemeColor(TH_WIRE);
2356         glDisable(GL_LIGHTING);
2357         glLineWidth(2.0);
2358         dm->drawEdges(dm, 0, 1);
2359         glLineWidth(1.0);
2360         glEnable(GL_LIGHTING);*/
2361
2362         glDisable(GL_LIGHTING);
2363         /*  if(GPU_buffer_legacy(dm) ) */ { /* TODO - VBO draw code, not high priority - campbell */
2364                 DEBUG_VBO( "Using legacy code. drawNavMeshColored\n" );
2365                 //glShadeModel(GL_SMOOTH);
2366                 glBegin(glmode = GL_QUADS);
2367                 for(a = 0; a < dm->numFaceData; a++, mface++) {
2368                         int new_glmode = mface->v4?GL_QUADS:GL_TRIANGLES;
2369                         int pi = polygonIdx[a];
2370                         if (pi <= 0) {
2371                                 zero_v3(col);
2372                         }
2373                         else {
2374                                 navmesh_intToCol(pi, col);
2375                         }
2376
2377                         if(new_glmode != glmode) {
2378                                 glEnd();
2379                                 glBegin(glmode = new_glmode);
2380                         }
2381                         glColor3fv(col);
2382                         glVertex3fv(mvert[mface->v1].co);
2383                         glVertex3fv(mvert[mface->v2].co);
2384                         glVertex3fv(mvert[mface->v3].co);
2385                         if(mface->v4) {
2386                                 glVertex3fv(mvert[mface->v4].co);
2387                         }
2388                 }
2389                 glEnd();
2390         }
2391         glEnable(GL_LIGHTING);
2392 }
2393
2394 static void navmesh_DM_drawFacesTex(DerivedMesh *dm, int (*setDrawOptions)(MTFace *tface, int has_mcol, int matnr))
2395 {
2396         (void) setDrawOptions;
2397
2398         navmesh_drawColored(dm);
2399 }
2400
2401 static void navmesh_DM_drawFacesSolid(DerivedMesh *dm,
2402                                       float (*partial_redraw_planes)[4],
2403                                       int UNUSED(fast), int (*setMaterial)(int, void *attribs))
2404 {
2405         (void) partial_redraw_planes;
2406         (void) setMaterial;
2407
2408         //drawFacesSolid_original(dm, partial_redraw_planes, fast, setMaterial);
2409         navmesh_drawColored(dm);
2410 }
2411
2412 static DerivedMesh *navmesh_dm_createNavMeshForVisualization(DerivedMesh *dm)
2413 {
2414         DerivedMesh *result;
2415         int maxFaces = dm->getNumFaces(dm);
2416         int *recastData;
2417         int vertsPerPoly=0, nverts=0, ndtris=0, npolys=0;
2418         float* verts=NULL;
2419         unsigned short *dtris=NULL, *dmeshes=NULL, *polys=NULL;
2420         int *dtrisToPolysMap=NULL, *dtrisToTrisMap=NULL, *trisToFacesMap=NULL;
2421         int res;
2422
2423         result = CDDM_copy(dm, 0);
2424         if (!CustomData_has_layer(&result->faceData, CD_RECAST)) {
2425                 int *sourceRecastData = (int*)CustomData_get_layer(&dm->faceData, CD_RECAST);
2426                 if (sourceRecastData) {
2427                         CustomData_add_layer_named(&result->faceData, CD_RECAST, CD_DUPLICATE,
2428                                                    sourceRecastData, maxFaces, "recastData");
2429                 }
2430         }
2431         recastData = (int*)CustomData_get_layer(&result->faceData, CD_RECAST);
2432
2433         /* note: This is not good design! - really should not be doing this */
2434         result->drawFacesTex =  navmesh_DM_drawFacesTex;
2435         result->drawFacesSolid = navmesh_DM_drawFacesSolid;
2436
2437
2438         /* process mesh */
2439         res  = buildNavMeshDataByDerivedMesh(dm, &vertsPerPoly, &nverts, &verts, &ndtris, &dtris,
2440                                              &npolys, &dmeshes, &polys, &dtrisToPolysMap, &dtrisToTrisMap,
2441                                              &trisToFacesMap);
2442         if (res) {
2443                 size_t polyIdx;
2444
2445                 /* invalidate concave polygon */
2446                 for (polyIdx=0; polyIdx<(size_t)npolys; polyIdx++) {
2447                         unsigned short* poly = &polys[polyIdx*2*vertsPerPoly];
2448                         if (!polyIsConvex(poly, vertsPerPoly, verts)) {
2449                                 /* set negative polygon idx to all faces */
2450                                 unsigned short *dmesh = &dmeshes[4*polyIdx];
2451                                 unsigned short tbase = dmesh[2];
2452                                 unsigned short tnum = dmesh[3];
2453                                 unsigned short ti;
2454
2455                                 for (ti=0; ti<tnum; ti++) {
2456                                         unsigned short triidx = dtrisToTrisMap[tbase+ti];
2457                                         unsigned short faceidx = trisToFacesMap[triidx];
2458                                         if (recastData[faceidx] > 0) {
2459                                                 recastData[faceidx] = -recastData[faceidx];
2460                                         }
2461                                 }
2462                         }
2463                 }
2464         }
2465         else {
2466                 printf("Error during creation polygon infos\n");
2467         }
2468
2469         /* clean up */
2470         if (verts!=NULL)
2471                 MEM_freeN(verts);
2472         if (dtris!=NULL)
2473                 MEM_freeN(dtris);
2474         if (dmeshes!=NULL)
2475                 MEM_freeN(dmeshes);
2476         if (polys!=NULL)
2477                 MEM_freeN(polys);
2478         if (dtrisToPolysMap!=NULL)
2479                 MEM_freeN(dtrisToPolysMap);
2480         if (dtrisToTrisMap!=NULL)
2481                 MEM_freeN(dtrisToTrisMap);
2482         if (trisToFacesMap!=NULL)
2483                 MEM_freeN(trisToFacesMap);
2484
2485         return result;
2486 }
2487
2488 #endif /* WITH_GAMEENGINE */
2489
2490 /* --- NAVMESH (end) --- */