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