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