a70d1a02bb463b9df139589d9385e9077d5e82c3
[blender-staging.git] / source / blender / blenkernel / intern / modifier.c
1 /*
2 * $Id$
3 *
4 * ***** BEGIN GPL LICENSE BLOCK *****
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version 2
9 * of the License, or (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software  Foundation,
18 * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19 *
20 * The Original Code is Copyright (C) 2005 by the Blender Foundation.
21 * All rights reserved.
22 *
23 * Contributor(s): Daniel Dunbar
24 *                 Ton Roosendaal,
25 *                 Ben Batt,
26 *                 Brecht Van Lommel,
27 *                 Campbell Barton,
28 *                 Joseph Eagar
29 *
30 * ***** END GPL LICENSE BLOCK *****
31 *
32 * Modifier stack implementation.
33 *
34 * BKE_modifier.h contains the function prototypes for this file.
35 *
36 */
37
38 #include "stddef.h"
39 #include "string.h"
40 #include "stdarg.h"
41 #include "math.h"
42 #include "float.h"
43 #include "ctype.h"
44
45 #include "BLI_arithb.h"
46 #include "BLI_blenlib.h"
47 #include "BLI_kdopbvh.h"
48 #include "BLI_kdtree.h"
49 #include "BLI_linklist.h"
50 #include "BLI_rand.h"
51 #include "BLI_edgehash.h"
52 #include "BLI_ghash.h"
53 #include "BLI_memarena.h"
54 #include "BLI_cellalloc.h"
55 #include "BLI_mempool.h"
56 #include "BLI_array.h"
57
58 #include "MEM_guardedalloc.h"
59
60 #include "DNA_action_types.h"
61 #include "DNA_armature_types.h"
62 #include "DNA_camera_types.h"
63 #include "DNA_cloth_types.h"
64 #include "DNA_curve_types.h"
65 #include "DNA_effect_types.h"
66 #include "DNA_group_types.h"
67 #include "DNA_material_types.h"
68 #include "DNA_mesh_types.h"
69 #include "DNA_meshdata_types.h"
70 #include "DNA_modifier_types.h"
71 #include "DNA_object_types.h"
72 #include "DNA_object_fluidsim.h"
73 #include "DNA_object_force.h"
74 #include "DNA_particle_types.h"
75 #include "DNA_scene_types.h"
76 #include "DNA_smoke_types.h"
77 #include "DNA_texture_types.h"
78
79 #include "BLI_editVert.h"
80
81
82
83
84 #include "BKE_main.h"
85 #include "BKE_anim.h"
86 #include "BKE_action.h"
87 #include "BKE_bmesh.h"
88 // XXX #include "BKE_booleanops.h"
89 #include "BKE_cloth.h"
90 #include "BKE_collision.h"
91 #include "BKE_cdderivedmesh.h"
92 #include "BKE_curve.h"
93 #include "BKE_customdata.h"
94 #include "BKE_DerivedMesh.h"
95 #include "BKE_displist.h"
96 #include "BKE_fluidsim.h"
97 #include "BKE_global.h"
98 #include "BKE_multires.h"
99 #include "BKE_lattice.h"
100 #include "BKE_library.h"
101 #include "BKE_material.h"
102 #include "BKE_mesh.h"
103 #include "BKE_modifier.h"
104 #include "BKE_object.h"
105 #include "BKE_particle.h"
106 #include "BKE_pointcache.h"
107 #include "BKE_smoke.h"
108 #include "BKE_softbody.h"
109 #include "BKE_subsurf.h"
110 #include "BKE_texture.h"
111 #include "BKE_utildefines.h"
112 #include "BKE_tessmesh.h"
113
114 #include "depsgraph_private.h"
115 #include "BKE_deform.h"
116 #include "BKE_shrinkwrap.h"
117 #include "BKE_simple_deform.h"
118
119 //XXX #include "LOD_DependKludge.h"
120 #include "LOD_decimation.h"
121
122 // XXX
123 static struct DerivedMesh *NewBooleanDerivedMesh() {return NULL;}
124
125 #include "CCGSubSurf.h"
126
127 #include "RE_shader_ext.h"
128
129 //XXX #include "BIF_meshlaplacian.h"
130
131 /* Utility */
132
133 static int is_last_displist(Object *ob)
134 {
135         Curve *cu = ob->data;
136         static int curvecount=0, totcurve=0;
137
138         if(curvecount == 0){
139                 DispList *dl;
140
141                 totcurve = 0;
142                 for(dl=cu->disp.first; dl; dl=dl->next)
143                         totcurve++;
144         }
145
146         curvecount++;
147
148         if(curvecount == totcurve){
149                 curvecount = 0;
150                 return 1;
151         }
152
153         return 0;
154 }
155
156 static DerivedMesh *get_original_dm(Scene *scene, Object *ob, float (*vertexCos)[3], int orco)
157 {
158         DerivedMesh *dm= NULL;
159
160         if(ob->type==OB_MESH) {
161                 dm = CDDM_from_mesh((Mesh*)(ob->data), ob);
162
163                 if(vertexCos) {
164                         CDDM_apply_vert_coords(dm, vertexCos);
165                         //CDDM_calc_normals(dm);
166                 }
167                 
168                 if(orco)
169                         DM_add_vert_layer(dm, CD_ORCO, CD_ASSIGN, get_mesh_orco_verts(ob));
170         }
171         else if(ELEM3(ob->type,OB_FONT,OB_CURVE,OB_SURF)) {
172                 Object *tmpobj;
173                 Curve *tmpcu;
174
175                 if(is_last_displist(ob)) {
176                         /* copies object and modifiers (but not the data) */
177                         tmpobj= copy_object(ob);
178                         tmpcu = (Curve *)tmpobj->data;
179                         tmpcu->id.us--;
180
181                         /* copies the data */
182                         tmpobj->data = copy_curve((Curve *) ob->data);
183
184                         makeDispListCurveTypes(scene, tmpobj, 1);
185                         nurbs_to_mesh(tmpobj);
186
187                         dm = CDDM_from_mesh((Mesh*)(tmpobj->data), tmpobj);
188                         //CDDM_calc_normals(dm);
189
190                         free_libblock_us(&G.main->object, tmpobj);
191                 }
192         }
193
194         return dm;
195 }
196
197 /***/
198
199 static int noneModifier_isDisabled(ModifierData *md)
200 {
201         return 1;
202 }
203
204 /* Curve */
205
206 static void curveModifier_initData(ModifierData *md)
207 {
208         CurveModifierData *cmd = (CurveModifierData*) md;
209
210         cmd->defaxis = MOD_CURVE_POSX;
211 }
212
213 static void curveModifier_copyData(ModifierData *md, ModifierData *target)
214 {
215         CurveModifierData *cmd = (CurveModifierData*) md;
216         CurveModifierData *tcmd = (CurveModifierData*) target;
217
218         tcmd->defaxis = cmd->defaxis;
219         tcmd->object = cmd->object;
220         strncpy(tcmd->name, cmd->name, 32);
221 }
222
223 static CustomDataMask curveModifier_requiredDataMask(Object *ob, ModifierData *md)
224 {
225         CurveModifierData *cmd = (CurveModifierData *)md;
226         CustomDataMask dataMask = 0;
227
228         /* ask for vertexgroups if we need them */
229         if(cmd->name[0]) dataMask |= (1 << CD_MDEFORMVERT);
230
231         return dataMask;
232 }
233
234 static int curveModifier_isDisabled(ModifierData *md)
235 {
236         CurveModifierData *cmd = (CurveModifierData*) md;
237
238         return !cmd->object;
239 }
240
241 static void curveModifier_foreachObjectLink(
242                                             ModifierData *md, Object *ob,
243          void (*walk)(void *userData, Object *ob, Object **obpoin),
244                 void *userData)
245 {
246         CurveModifierData *cmd = (CurveModifierData*) md;
247
248         walk(userData, ob, &cmd->object);
249 }
250
251 static void curveModifier_updateDepgraph(
252                                          ModifierData *md, DagForest *forest, Scene *scene,
253       Object *ob, DagNode *obNode)
254 {
255         CurveModifierData *cmd = (CurveModifierData*) md;
256
257         if (cmd->object) {
258                 DagNode *curNode = dag_get_node(forest, cmd->object);
259
260                 dag_add_relation(forest, curNode, obNode,
261                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Curve Modifier");
262         }
263 }
264
265 static void curveModifier_deformVerts(
266                                       ModifierData *md, Object *ob, DerivedMesh *derivedData,
267           float (*vertexCos)[3], int numVerts, int useRenderParams, int isFinalCalc)
268 {
269         CurveModifierData *cmd = (CurveModifierData*) md;
270
271         curve_deform_verts(md->scene, cmd->object, ob, derivedData, vertexCos, numVerts,
272                            cmd->name, cmd->defaxis);
273 }
274
275 static void curveModifier_deformVertsEM(
276                                         ModifierData *md, Object *ob, BMEditMesh *editData,
277      DerivedMesh *derivedData, float (*vertexCos)[3], int numVerts)
278 {
279         DerivedMesh *dm = derivedData;
280
281         if(!derivedData) dm = CDDM_from_BMEditMesh(editData, ob->data);
282
283         curveModifier_deformVerts(md, ob, dm, vertexCos, numVerts, 0, 0);
284
285         if(!derivedData) dm->release(dm);
286 }
287
288 /* Lattice */
289
290 static void latticeModifier_copyData(ModifierData *md, ModifierData *target)
291 {
292         LatticeModifierData *lmd = (LatticeModifierData*) md;
293         LatticeModifierData *tlmd = (LatticeModifierData*) target;
294
295         tlmd->object = lmd->object;
296         strncpy(tlmd->name, lmd->name, 32);
297 }
298
299 static CustomDataMask latticeModifier_requiredDataMask(Object *ob, ModifierData *md)
300 {
301         LatticeModifierData *lmd = (LatticeModifierData *)md;
302         CustomDataMask dataMask = 0;
303
304         /* ask for vertexgroups if we need them */
305         if(lmd->name[0]) dataMask |= (1 << CD_MDEFORMVERT);
306
307         return dataMask;
308 }
309
310 static int latticeModifier_isDisabled(ModifierData *md)
311 {
312         LatticeModifierData *lmd = (LatticeModifierData*) md;
313
314         return !lmd->object;
315 }
316
317 static void latticeModifier_foreachObjectLink(
318                                               ModifierData *md, Object *ob,
319            void (*walk)(void *userData, Object *ob, Object **obpoin),
320                   void *userData)
321 {
322         LatticeModifierData *lmd = (LatticeModifierData*) md;
323
324         walk(userData, ob, &lmd->object);
325 }
326
327 static void latticeModifier_updateDepgraph(ModifierData *md, DagForest *forest,  Scene *scene,
328                                            Object *ob, DagNode *obNode)
329 {
330         LatticeModifierData *lmd = (LatticeModifierData*) md;
331
332         if(lmd->object) {
333                 DagNode *latNode = dag_get_node(forest, lmd->object);
334
335                 dag_add_relation(forest, latNode, obNode,
336                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Lattice Modifier");
337         }
338 }
339
340 static void modifier_vgroup_cache(ModifierData *md, float (*vertexCos)[3])
341 {
342         md= md->next;
343         if(md) {
344                 if(md->type==eModifierType_Armature) {
345                         ArmatureModifierData *amd = (ArmatureModifierData*) md;
346                         if(amd->multi)
347                                 amd->prevCos= MEM_dupallocN(vertexCos);
348                 }
349                 /* lattice/mesh modifier too */
350         }
351 }
352
353
354 static void latticeModifier_deformVerts(
355                                         ModifierData *md, Object *ob, DerivedMesh *derivedData,
356      float (*vertexCos)[3], int numVerts, int useRenderParams, int isFinalCalc)
357 {
358         LatticeModifierData *lmd = (LatticeModifierData*) md;
359
360
361         modifier_vgroup_cache(md, vertexCos); /* if next modifier needs original vertices */
362         
363         lattice_deform_verts(lmd->object, ob, derivedData,
364                              vertexCos, numVerts, lmd->name);
365 }
366
367 static void latticeModifier_deformVertsEM(
368                                           ModifierData *md, Object *ob, BMEditMesh *editData,
369        DerivedMesh *derivedData, float (*vertexCos)[3], int numVerts)
370 {
371         DerivedMesh *dm = derivedData;
372
373         if(!derivedData) dm = CDDM_from_BMEditMesh(editData, ob->data);
374
375         latticeModifier_deformVerts(md, ob, dm, vertexCos, numVerts, 0, 0);
376
377         if(!derivedData) dm->release(dm);
378 }
379
380 /* Subsurf */
381
382 static void subsurfModifier_initData(ModifierData *md)
383 {
384         SubsurfModifierData *smd = (SubsurfModifierData*) md;
385
386         smd->levels = 1;
387         smd->renderLevels = 2;
388         smd->flags |= eSubsurfModifierFlag_SubsurfUv;
389 }
390
391 static void subsurfModifier_copyData(ModifierData *md, ModifierData *target)
392 {
393         SubsurfModifierData *smd = (SubsurfModifierData*) md;
394         SubsurfModifierData *tsmd = (SubsurfModifierData*) target;
395
396         tsmd->flags = smd->flags;
397         tsmd->levels = smd->levels;
398         tsmd->renderLevels = smd->renderLevels;
399         tsmd->subdivType = smd->subdivType;
400 }
401
402 static void subsurfModifier_freeData(ModifierData *md)
403 {
404         SubsurfModifierData *smd = (SubsurfModifierData*) md;
405
406         if(smd->mCache) {
407                 CCS_free(smd->mCache);
408         }
409         if(smd->emCache) {
410                 CCS_free(smd->emCache);
411         }
412 }
413
414 static DerivedMesh *subsurfModifier_applyModifier(
415                 ModifierData *md, Object *ob, DerivedMesh *derivedData,
416   int useRenderParams, int isFinalCalc)
417 {
418         SubsurfModifierData *smd = (SubsurfModifierData*) md;
419         DerivedMesh *result;
420
421         result = subsurf_make_derived_from_derived(derivedData, smd,
422                         useRenderParams, NULL,
423    isFinalCalc, 0);
424
425         return result;
426 }
427
428 static DerivedMesh *subsurfModifier_applyModifierEM(
429                 ModifierData *md, Object *ob, BMEditMesh *editData,
430   DerivedMesh *derivedData)
431 {
432         SubsurfModifierData *smd = (SubsurfModifierData*) md;
433         DerivedMesh *result;
434
435         result = subsurf_make_derived_from_derived(derivedData, smd, 0,
436                         NULL, 0, 1);
437
438         return result;
439 }
440
441 /* Build */
442
443 static void buildModifier_initData(ModifierData *md)
444 {
445         BuildModifierData *bmd = (BuildModifierData*) md;
446
447         bmd->start = 1.0;
448         bmd->length = 100.0;
449 }
450
451 static void buildModifier_copyData(ModifierData *md, ModifierData *target)
452 {
453         BuildModifierData *bmd = (BuildModifierData*) md;
454         BuildModifierData *tbmd = (BuildModifierData*) target;
455
456         tbmd->start = bmd->start;
457         tbmd->length = bmd->length;
458         tbmd->randomize = bmd->randomize;
459         tbmd->seed = bmd->seed;
460 }
461
462 static int buildModifier_dependsOnTime(ModifierData *md)
463 {
464         return 1;
465 }
466
467 static DerivedMesh *buildModifier_applyModifier(ModifierData *md, Object *ob,
468                 DerivedMesh *derivedData,
469   int useRenderParams, int isFinalCalc)
470 {
471         DerivedMesh *dm = derivedData;
472         DerivedMesh *result;
473         BuildModifierData *bmd = (BuildModifierData*) md;
474         int i;
475         int numFaces, numEdges;
476         int maxVerts, maxEdges, maxFaces;
477         int *vertMap, *edgeMap, *faceMap;
478         float frac;
479         GHashIterator *hashIter;
480         /* maps vert indices in old mesh to indices in new mesh */
481         GHash *vertHash = BLI_ghash_new(BLI_ghashutil_inthash,
482                                         BLI_ghashutil_intcmp);
483         /* maps edge indices in new mesh to indices in old mesh */
484         GHash *edgeHash = BLI_ghash_new(BLI_ghashutil_inthash,
485                                         BLI_ghashutil_intcmp);
486
487         maxVerts = dm->getNumVerts(dm);
488         vertMap = MEM_callocN(sizeof(*vertMap) * maxVerts,
489                               "build modifier vertMap");
490         for(i = 0; i < maxVerts; ++i) vertMap[i] = i;
491
492         maxEdges = dm->getNumEdges(dm);
493         edgeMap = MEM_callocN(sizeof(*edgeMap) * maxEdges,
494                               "build modifier edgeMap");
495         for(i = 0; i < maxEdges; ++i) edgeMap[i] = i;
496
497         maxFaces = dm->getNumTessFaces(dm);
498         faceMap = MEM_callocN(sizeof(*faceMap) * maxFaces,
499                               "build modifier faceMap");
500         for(i = 0; i < maxFaces; ++i) faceMap[i] = i;
501
502         if (ob) {
503                 frac = bsystem_time(md->scene, ob, md->scene->r.cfra,
504                                     bmd->start - 1.0f) / bmd->length;
505         } else {
506                 frac = md->scene->r.cfra - bmd->start / bmd->length;
507         }
508         CLAMP(frac, 0.0, 1.0);
509
510         numFaces = dm->getNumTessFaces(dm) * frac;
511         numEdges = dm->getNumEdges(dm) * frac;
512
513         /* if there's at least one face, build based on faces */
514         if(numFaces) {
515                 int maxEdges;
516
517                 if(bmd->randomize)
518                         BLI_array_randomize(faceMap, sizeof(*faceMap),
519                                             maxFaces, bmd->seed);
520
521                 /* get the set of all vert indices that will be in the final mesh,
522                 * mapped to the new indices
523                 */
524                 for(i = 0; i < numFaces; ++i) {
525                         MFace mf;
526                         dm->getTessFace(dm, faceMap[i], &mf);
527
528                         if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v1)))
529                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(mf.v1),
530                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
531                         if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v2)))
532                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(mf.v2),
533                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
534                         if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v3)))
535                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(mf.v3),
536                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
537                         if(mf.v4 && !BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v4)))
538                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(mf.v4),
539                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
540                 }
541
542                 /* get the set of edges that will be in the new mesh (i.e. all edges
543                 * that have both verts in the new mesh)
544                 */
545                 maxEdges = dm->getNumEdges(dm);
546                 for(i = 0; i < maxEdges; ++i) {
547                         MEdge me;
548                         dm->getEdge(dm, i, &me);
549
550                         if(BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v1))
551                                                 && BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v2)))
552                                 BLI_ghash_insert(edgeHash,
553                                         SET_INT_IN_POINTER(BLI_ghash_size(edgeHash)), SET_INT_IN_POINTER(i));
554                 }
555         } else if(numEdges) {
556                 if(bmd->randomize)
557                         BLI_array_randomize(edgeMap, sizeof(*edgeMap),
558                                             maxEdges, bmd->seed);
559
560                 /* get the set of all vert indices that will be in the final mesh,
561                 * mapped to the new indices
562                 */
563                 for(i = 0; i < numEdges; ++i) {
564                         MEdge me;
565                         dm->getEdge(dm, edgeMap[i], &me);
566
567                         if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v1)))
568                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(me.v1),
569                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
570                         if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v2)))
571                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(me.v2),
572                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
573                 }
574
575                 /* get the set of edges that will be in the new mesh
576                 */
577                 for(i = 0; i < numEdges; ++i) {
578                         MEdge me;
579                         dm->getEdge(dm, edgeMap[i], &me);
580
581                         BLI_ghash_insert(edgeHash, SET_INT_IN_POINTER(BLI_ghash_size(edgeHash)),
582                                          SET_INT_IN_POINTER(edgeMap[i]));
583                 }
584         } else {
585                 int numVerts = dm->getNumVerts(dm) * frac;
586
587                 if(bmd->randomize)
588                         BLI_array_randomize(vertMap, sizeof(*vertMap),
589                                             maxVerts, bmd->seed);
590
591                 /* get the set of all vert indices that will be in the final mesh,
592                 * mapped to the new indices
593                 */
594                 for(i = 0; i < numVerts; ++i)
595                         BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(vertMap[i]), SET_INT_IN_POINTER(i));
596         }
597
598         /* now we know the number of verts, edges and faces, we can create
599         * the mesh
600         */
601         result = CDDM_from_template(dm, BLI_ghash_size(vertHash),
602                                     BLI_ghash_size(edgeHash), numFaces, 0, 0);
603
604         /* copy the vertices across */
605         for(hashIter = BLI_ghashIterator_new(vertHash);
606                    !BLI_ghashIterator_isDone(hashIter);
607                    BLI_ghashIterator_step(hashIter)) {
608                            MVert source;
609                            MVert *dest;
610                            int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(hashIter));
611                            int newIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(hashIter));
612
613                            dm->getVert(dm, oldIndex, &source);
614                            dest = CDDM_get_vert(result, newIndex);
615
616                            DM_copy_vert_data(dm, result, oldIndex, newIndex, 1);
617                            *dest = source;
618                    }
619                    BLI_ghashIterator_free(hashIter);
620
621                    /* copy the edges across, remapping indices */
622                    for(i = 0; i < BLI_ghash_size(edgeHash); ++i) {
623                            MEdge source;
624                            MEdge *dest;
625                            int oldIndex = GET_INT_FROM_POINTER(BLI_ghash_lookup(edgeHash, SET_INT_IN_POINTER(i)));
626
627                            dm->getEdge(dm, oldIndex, &source);
628                            dest = CDDM_get_edge(result, i);
629
630                            source.v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v1)));
631                            source.v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v2)));
632
633                            DM_copy_edge_data(dm, result, oldIndex, i, 1);
634                            *dest = source;
635                    }
636
637                    /* copy the faces across, remapping indices */
638                    for(i = 0; i < numFaces; ++i) {
639                            MFace source;
640                            MFace *dest;
641                            int orig_v4;
642
643                            dm->getTessFace(dm, faceMap[i], &source);
644                            dest = CDDM_get_tessface(result, i);
645
646                            orig_v4 = source.v4;
647
648                            source.v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v1)));
649                            source.v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v2)));
650                            source.v3 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v3)));
651                            if(source.v4)
652                                    source.v4 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v4)));
653
654                            DM_copy_tessface_data(dm, result, faceMap[i], i, 1);
655                            *dest = source;
656
657                            test_index_face(dest, &result->faceData, i, (orig_v4 ? 4 : 3));
658                    }
659
660                    CDDM_calc_normals(result);
661                    CDDM_tessfaces_to_faces(result);
662
663                    BLI_ghash_free(vertHash, NULL, NULL);
664                    BLI_ghash_free(edgeHash, NULL, NULL);
665
666                    MEM_freeN(vertMap);
667                    MEM_freeN(edgeMap);
668                    MEM_freeN(faceMap);
669                         
670                    return result;
671 }
672
673 /* Mask */
674
675 static void maskModifier_copyData(ModifierData *md, ModifierData *target)
676 {
677         MaskModifierData *mmd = (MaskModifierData*) md;
678         MaskModifierData *tmmd = (MaskModifierData*) target;
679         
680         strcpy(tmmd->vgroup, mmd->vgroup);
681 }
682
683 static CustomDataMask maskModifier_requiredDataMask(Object *ob, ModifierData *md)
684 {
685         return (1 << CD_MDEFORMVERT);
686 }
687
688 static void maskModifier_foreachObjectLink(
689                                               ModifierData *md, Object *ob,
690            void (*walk)(void *userData, Object *ob, Object **obpoin),
691                   void *userData)
692 {
693         MaskModifierData *mmd = (MaskModifierData *)md;
694         walk(userData, ob, &mmd->ob_arm);
695 }
696
697 static void maskModifier_updateDepgraph(ModifierData *md, DagForest *forest, Scene *scene,
698                                            Object *ob, DagNode *obNode)
699 {
700         MaskModifierData *mmd = (MaskModifierData *)md;
701
702         if (mmd->ob_arm) 
703         {
704                 DagNode *armNode = dag_get_node(forest, mmd->ob_arm);
705                 
706                 dag_add_relation(forest, armNode, obNode,
707                                 DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Mask Modifier");
708         }
709 }
710
711 static DerivedMesh *maskModifier_applyModifier(ModifierData *md, Object *ob,
712                 DerivedMesh *derivedData,
713   int useRenderParams, int isFinalCalc)
714 {
715         MaskModifierData *mmd= (MaskModifierData *)md;
716         DerivedMesh *dm= derivedData, *result= NULL;
717         GHash *vertHash=NULL, *edgeHash, *faceHash;
718         GHashIterator *hashIter;
719         MDeformVert *dvert= NULL;
720         int numFaces=0, numEdges=0, numVerts=0;
721         int maxVerts, maxEdges, maxFaces;
722         int i;
723         
724         /* Overview of Method:
725          *      1. Get the vertices that are in the vertexgroup of interest 
726          *      2. Filter out unwanted geometry (i.e. not in vertexgroup), by populating mappings with new vs old indices
727          *      3. Make a new mesh containing only the mapping data
728          */
729         
730         /* get original number of verts, edges, and faces */
731         maxVerts= dm->getNumVerts(dm);
732         maxEdges= dm->getNumEdges(dm);
733         maxFaces= dm->getNumTessFaces(dm);
734         
735         /* check if we can just return the original mesh 
736          *      - must have verts and therefore verts assigned to vgroups to do anything useful
737          */
738         if ( !(ELEM(mmd->mode, MOD_MASK_MODE_ARM, MOD_MASK_MODE_VGROUP)) ||
739                  (maxVerts == 0) || (ob->defbase.first == NULL) )
740         {
741                 return derivedData;
742         }
743         
744         /* if mode is to use selected armature bones, aggregate the bone groups */
745         if (mmd->mode == MOD_MASK_MODE_ARM) /* --- using selected bones --- */
746         {
747                 GHash *vgroupHash, *boneHash;
748                 Object *oba= mmd->ob_arm;
749                 bPoseChannel *pchan;
750                 bDeformGroup *def;
751                 
752                 /* check that there is armature object with bones to use, otherwise return original mesh */
753                 if (ELEM(NULL, mmd->ob_arm, mmd->ob_arm->pose))
754                         return derivedData;             
755                 
756                 /* hashes for finding mapping of:
757                  *      - vgroups to indicies -> vgroupHash  (string, int)
758                  *      - bones to vgroup indices -> boneHash (index of vgroup, dummy)
759                  */
760                 vgroupHash= BLI_ghash_new(BLI_ghashutil_strhash, BLI_ghashutil_strcmp);
761                 boneHash= BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp);
762                 
763                 /* build mapping of names of vertex groups to indices */
764                 for (i = 0, def = ob->defbase.first; def; def = def->next, i++) 
765                         BLI_ghash_insert(vgroupHash, def->name, SET_INT_IN_POINTER(i));
766                 
767                 /* get selected-posechannel <-> vertexgroup index mapping */
768                 for (pchan= oba->pose->chanbase.first; pchan; pchan= pchan->next) 
769                 {
770                         /* check if bone is selected */
771                         // TODO: include checks for visibility too?
772                         // FIXME: the depsgraph needs extensions to make this work in realtime...
773                         if ( (pchan->bone) && (pchan->bone->flag & BONE_SELECTED) ) 
774                         {
775                                 /* check if hash has group for this bone */
776                                 if (BLI_ghash_haskey(vgroupHash, pchan->name)) 
777                                 {
778                                         int defgrp_index= GET_INT_FROM_POINTER(BLI_ghash_lookup(vgroupHash, pchan->name));
779                                         
780                                         /* add index to hash (store under key only) */
781                                         BLI_ghash_insert(boneHash, SET_INT_IN_POINTER(defgrp_index), pchan);
782                                 }
783                         }
784                 }
785                 
786                 /* if no bones selected, free hashes and return original mesh */
787                 if (BLI_ghash_size(boneHash) == 0)
788                 {
789                         BLI_ghash_free(vgroupHash, NULL, NULL);
790                         BLI_ghash_free(boneHash, NULL, NULL);
791                         
792                         return derivedData;
793                 }
794                 
795                 /* repeat the previous check, but for dverts */
796                 dvert= dm->getVertDataArray(dm, CD_MDEFORMVERT);
797                 if (dvert == NULL)
798                 {
799                         BLI_ghash_free(vgroupHash, NULL, NULL);
800                         BLI_ghash_free(boneHash, NULL, NULL);
801                         
802                         return derivedData;
803                 }
804                 
805                 /* hashes for quickly providing a mapping from old to new - use key=oldindex, value=newindex */
806                 vertHash= BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp);
807                 
808                 /* add vertices which exist in vertexgroups into vertHash for filtering */
809                 for (i = 0; i < maxVerts; i++) 
810                 {
811                         MDeformWeight *def_weight = NULL;
812                         int j;
813                         
814                         for (j= 0; j < dvert[i].totweight; j++) 
815                         {
816                                 if (BLI_ghash_haskey(boneHash, SET_INT_IN_POINTER(dvert[i].dw[j].def_nr))) 
817                                 {
818                                         def_weight = &dvert[i].dw[j];
819                                         break;
820                                 }
821                         }
822                         
823                         /* check if include vert in vertHash */
824                         if (mmd->flag & MOD_MASK_INV) {
825                                 /* if this vert is in the vgroup, don't include it in vertHash */
826                                 if (def_weight) continue;
827                         }
828                         else {
829                                 /* if this vert isn't in the vgroup, don't include it in vertHash */
830                                 if (!def_weight) continue;
831                         }
832                         
833                         /* add to ghash for verts (numVerts acts as counter for mapping) */
834                         BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(i), SET_INT_IN_POINTER(numVerts));
835                         numVerts++;
836                 }
837                 
838                 /* free temp hashes */
839                 BLI_ghash_free(vgroupHash, NULL, NULL);
840                 BLI_ghash_free(boneHash, NULL, NULL);
841         }
842         else            /* --- Using Nominated VertexGroup only --- */ 
843         {
844                 int defgrp_index = -1;
845                 
846                 /* get index of vertex group */
847                 if (mmd->vgroup[0]) 
848                 {
849                         bDeformGroup *def;
850                         
851                         /* find index by comparing names - SLOW... */
852                         for (i = 0, def = ob->defbase.first; def; def = def->next, i++) 
853                         {
854                                 if (!strcmp(def->name, mmd->vgroup)) 
855                                 {
856                                         defgrp_index = i;
857                                         break;
858                                 }
859                         }
860                 }
861                 
862                 /* get dverts */
863                 if (defgrp_index >= 0)
864                         dvert = dm->getVertDataArray(dm, CD_MDEFORMVERT);
865                         
866                 /* if no vgroup (i.e. dverts) found, return the initial mesh */
867                 if ((defgrp_index < 0) || (dvert == NULL))
868                         return dm;
869                         
870                 /* hashes for quickly providing a mapping from old to new - use key=oldindex, value=newindex */
871                 vertHash= BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp);
872                 
873                 /* add vertices which exist in vertexgroup into ghash for filtering */
874                 for (i = 0; i < maxVerts; i++) 
875                 {
876                         MDeformWeight *def_weight = NULL;
877                         int j;
878                         
879                         for (j= 0; j < dvert[i].totweight; j++) 
880                         {
881                                 if (dvert[i].dw[j].def_nr == defgrp_index) 
882                                 {
883                                         def_weight = &dvert[i].dw[j];
884                                         break;
885                                 }
886                         }
887                         
888                         /* check if include vert in vertHash */
889                         if (mmd->flag & MOD_MASK_INV) {
890                                 /* if this vert is in the vgroup, don't include it in vertHash */
891                                 if (def_weight) continue;
892                         }
893                         else {
894                                 /* if this vert isn't in the vgroup, don't include it in vertHash */
895                                 if (!def_weight) continue;
896                         }
897                         
898                         /* add to ghash for verts (numVerts acts as counter for mapping) */
899                         BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(i), SET_INT_IN_POINTER(numVerts));
900                         numVerts++;
901                 }
902         }
903         
904         /* hashes for quickly providing a mapping from old to new - use key=oldindex, value=newindex */
905         edgeHash= BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp);
906         faceHash= BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp);
907         
908         /* loop over edges and faces, and do the same thing to 
909          * ensure that they only reference existing verts 
910          */
911         for (i = 0; i < maxEdges; i++) 
912         {
913                 MEdge me;
914                 dm->getEdge(dm, i, &me);
915                 
916                 /* only add if both verts will be in new mesh */
917                 if ( BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v1)) &&
918                          BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v2)) )
919                 {
920                         BLI_ghash_insert(edgeHash, SET_INT_IN_POINTER(i), SET_INT_IN_POINTER(numEdges));
921                         numEdges++;
922                 }
923         }
924         for (i = 0; i < maxFaces; i++) 
925         {
926                 MFace mf;
927                 dm->getTessFace(dm, i, &mf);
928                 
929                 /* all verts must be available */
930                 if ( BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v1)) &&
931                          BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v2)) &&
932                          BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v3)) &&
933                         (mf.v4==0 || BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v4))) )
934                 {
935                         BLI_ghash_insert(faceHash, SET_INT_IN_POINTER(i), SET_INT_IN_POINTER(numFaces));
936                         numFaces++;
937                 }
938         }
939         
940         
941         /* now we know the number of verts, edges and faces, 
942          * we can create the new (reduced) mesh
943          */
944         result = CDDM_from_template(dm, numVerts, numEdges, numFaces, 0, 0);
945         
946         
947         /* using ghash-iterators, map data into new mesh */
948                 /* vertices */
949         for ( hashIter = BLI_ghashIterator_new(vertHash);
950                   !BLI_ghashIterator_isDone(hashIter);
951                   BLI_ghashIterator_step(hashIter) ) 
952         {
953                 MVert source;
954                 MVert *dest;
955                 int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(hashIter));
956                 int newIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(hashIter));
957                 
958                 dm->getVert(dm, oldIndex, &source);
959                 dest = CDDM_get_vert(result, newIndex);
960                 
961                 DM_copy_vert_data(dm, result, oldIndex, newIndex, 1);
962                 *dest = source;
963         }
964         BLI_ghashIterator_free(hashIter);
965                 
966                 /* edges */
967         for ( hashIter = BLI_ghashIterator_new(edgeHash);
968                   !BLI_ghashIterator_isDone(hashIter);
969                   BLI_ghashIterator_step(hashIter) ) 
970         {
971                 MEdge source;
972                 MEdge *dest;
973                 int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(hashIter));
974                 int newIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(hashIter));
975                 
976                 dm->getEdge(dm, oldIndex, &source);
977                 dest = CDDM_get_edge(result, newIndex);
978                 
979                 source.v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v1)));
980                 source.v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v2)));
981                 
982                 DM_copy_edge_data(dm, result, oldIndex, newIndex, 1);
983                 *dest = source;
984         }
985         BLI_ghashIterator_free(hashIter);
986         
987                 /* faces */
988         for ( hashIter = BLI_ghashIterator_new(faceHash);
989                   !BLI_ghashIterator_isDone(hashIter);
990                   BLI_ghashIterator_step(hashIter) ) 
991         {
992                 MFace source;
993                 MFace *dest;
994                 int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(hashIter));
995                 int newIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(hashIter));
996                 int orig_v4;
997                 
998                 dm->getTessFace(dm, oldIndex, &source);
999                 dest = CDDM_get_tessface(result, newIndex);
1000                 
1001                 orig_v4 = source.v4;
1002                 
1003                 source.v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v1)));
1004                 source.v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v2)));
1005                 source.v3 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v3)));
1006                 if (source.v4)
1007                    source.v4 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v4)));
1008                 
1009                 DM_copy_tessface_data(dm, result, oldIndex, newIndex, 1);
1010                 *dest = source;
1011                 
1012                 test_index_face(dest, &result->faceData, newIndex, (orig_v4 ? 4 : 3));
1013         }
1014         BLI_ghashIterator_free(hashIter);
1015         
1016         /* recalculate normals */
1017         CDDM_calc_normals(result);
1018         
1019         /* free hashes */
1020         BLI_ghash_free(vertHash, NULL, NULL);
1021         BLI_ghash_free(edgeHash, NULL, NULL);
1022         BLI_ghash_free(faceHash, NULL, NULL);
1023         
1024         CDDM_tessfaces_to_faces(result);
1025
1026         /* return the new mesh */
1027         return result;
1028 }
1029
1030 /* Array */
1031 /* Array modifier: duplicates the object multiple times along an axis
1032 */
1033
1034 static void arrayModifier_initData(ModifierData *md)
1035 {
1036         ArrayModifierData *amd = (ArrayModifierData*) md;
1037
1038         /* default to 2 duplicates distributed along the x-axis by an
1039         offset of 1 object-width
1040         */
1041         amd->start_cap = amd->end_cap = amd->curve_ob = amd->offset_ob = NULL;
1042         amd->count = 2;
1043         amd->offset[0] = amd->offset[1] = amd->offset[2] = 0;
1044         amd->scale[0] = 1;
1045         amd->scale[1] = amd->scale[2] = 0;
1046         amd->length = 0;
1047         amd->merge_dist = 0.01;
1048         amd->fit_type = MOD_ARR_FIXEDCOUNT;
1049         amd->offset_type = MOD_ARR_OFF_RELATIVE;
1050         amd->flags = 0;
1051 }
1052
1053 static void arrayModifier_copyData(ModifierData *md, ModifierData *target)
1054 {
1055         ArrayModifierData *amd = (ArrayModifierData*) md;
1056         ArrayModifierData *tamd = (ArrayModifierData*) target;
1057
1058         tamd->start_cap = amd->start_cap;
1059         tamd->end_cap = amd->end_cap;
1060         tamd->curve_ob = amd->curve_ob;
1061         tamd->offset_ob = amd->offset_ob;
1062         tamd->count = amd->count;
1063         VECCOPY(tamd->offset, amd->offset);
1064         VECCOPY(tamd->scale, amd->scale);
1065         tamd->length = amd->length;
1066         tamd->merge_dist = amd->merge_dist;
1067         tamd->fit_type = amd->fit_type;
1068         tamd->offset_type = amd->offset_type;
1069         tamd->flags = amd->flags;
1070 }
1071
1072 static void arrayModifier_foreachObjectLink(
1073                                             ModifierData *md, Object *ob,
1074          void (*walk)(void *userData, Object *ob, Object **obpoin),
1075                 void *userData)
1076 {
1077         ArrayModifierData *amd = (ArrayModifierData*) md;
1078
1079         walk(userData, ob, &amd->start_cap);
1080         walk(userData, ob, &amd->end_cap);
1081         walk(userData, ob, &amd->curve_ob);
1082         walk(userData, ob, &amd->offset_ob);
1083 }
1084
1085 static void arrayModifier_updateDepgraph(ModifierData *md, DagForest *forest, Scene *scene,
1086                                          Object *ob, DagNode *obNode)
1087 {
1088         ArrayModifierData *amd = (ArrayModifierData*) md;
1089
1090         if (amd->start_cap) {
1091                 DagNode *curNode = dag_get_node(forest, amd->start_cap);
1092
1093                 dag_add_relation(forest, curNode, obNode,
1094                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
1095         }
1096         if (amd->end_cap) {
1097                 DagNode *curNode = dag_get_node(forest, amd->end_cap);
1098
1099                 dag_add_relation(forest, curNode, obNode,
1100                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
1101         }
1102         if (amd->curve_ob) {
1103                 DagNode *curNode = dag_get_node(forest, amd->curve_ob);
1104
1105                 dag_add_relation(forest, curNode, obNode,
1106                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
1107         }
1108         if (amd->offset_ob) {
1109                 DagNode *curNode = dag_get_node(forest, amd->offset_ob);
1110
1111                 dag_add_relation(forest, curNode, obNode,
1112                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
1113         }
1114 }
1115
1116 static float vertarray_size(MVert *mvert, int numVerts, int axis)
1117 {
1118         int i;
1119         float min_co, max_co;
1120
1121         /* if there are no vertices, width is 0 */
1122         if(numVerts == 0) return 0;
1123
1124         /* find the minimum and maximum coordinates on the desired axis */
1125         min_co = max_co = mvert->co[axis];
1126         ++mvert;
1127         for(i = 1; i < numVerts; ++i, ++mvert) {
1128                 if(mvert->co[axis] < min_co) min_co = mvert->co[axis];
1129                 if(mvert->co[axis] > max_co) max_co = mvert->co[axis];
1130         }
1131
1132         return max_co - min_co;
1133 }
1134
1135 typedef struct IndexMapEntry {
1136         /* the new vert index that this old vert index maps to */
1137         int new;
1138         /* -1 if this vert isn't merged, otherwise the old vert index it
1139         * should be replaced with
1140         */
1141         int merge;
1142         /* 1 if this vert's first copy is merged with the last copy of its
1143         * merge target, otherwise 0
1144         */
1145         short merge_final;
1146 } IndexMapEntry;
1147
1148 /* indexMap - an array of IndexMap entries
1149  * oldIndex - the old index to map
1150  * copyNum - the copy number to map to (original = 0, first copy = 1, etc.)
1151  */
1152 static int calc_mapping(IndexMapEntry *indexMap, int oldIndex, int copyNum)
1153 {
1154         if(indexMap[oldIndex].merge < 0) {
1155                 /* vert wasn't merged, so use copy of this vert */
1156                 return indexMap[oldIndex].new + copyNum;
1157         } else if(indexMap[oldIndex].merge == oldIndex) {
1158                 /* vert was merged with itself */
1159                 return indexMap[oldIndex].new;
1160         } else {
1161                 /* vert was merged with another vert */
1162                 /* follow the chain of merges to the end, or until we've passed
1163                 * a number of vertices equal to the copy number
1164                 */
1165                 if(copyNum <= 0)
1166                         return indexMap[oldIndex].new;
1167                 else
1168                         return calc_mapping(indexMap, indexMap[oldIndex].merge,
1169                                             copyNum - 1);
1170         }
1171 }
1172
1173 #if 0
1174 static DerivedMesh *arrayModifier_doArray(ArrayModifierData *amd,
1175                                           Scene *scene, Object *ob, DerivedMesh *dm,
1176        int initFlags)
1177 {
1178         int i, j;
1179         /* offset matrix */
1180         float offset[4][4];
1181         float final_offset[4][4];
1182         float tmp_mat[4][4];
1183         float length = amd->length;
1184         int count = amd->count;
1185         int numVerts, numEdges, numFaces;
1186         int maxVerts, maxEdges, maxFaces;
1187         int finalVerts, finalEdges, finalFaces;
1188         DerivedMesh *result, *start_cap = NULL, *end_cap = NULL;
1189         MVert *mvert, *src_mvert;
1190         MEdge *medge;
1191         MFace *mface;
1192
1193         IndexMapEntry *indexMap;
1194
1195         EdgeHash *edges;
1196
1197         /* need to avoid infinite recursion here */
1198         if(amd->start_cap && amd->start_cap != ob)
1199                 start_cap = mesh_get_derived_final(scene, amd->start_cap, CD_MASK_MESH);
1200         if(amd->end_cap && amd->end_cap != ob)
1201                 end_cap = mesh_get_derived_final(scene, amd->end_cap, CD_MASK_MESH);
1202
1203         Mat4One(offset);
1204
1205         indexMap = MEM_callocN(sizeof(*indexMap) * dm->getNumVerts(dm),
1206                                "indexmap");
1207
1208         src_mvert = dm->getVertArray(dm);
1209
1210         maxVerts = dm->getNumVerts(dm);
1211
1212         if(amd->offset_type & MOD_ARR_OFF_CONST)
1213                 VecAddf(offset[3], offset[3], amd->offset);
1214         if(amd->offset_type & MOD_ARR_OFF_RELATIVE) {
1215                 for(j = 0; j < 3; j++)
1216                         offset[3][j] += amd->scale[j] * vertarray_size(src_mvert,
1217                                         maxVerts, j);
1218         }
1219
1220         if((amd->offset_type & MOD_ARR_OFF_OBJ) && (amd->offset_ob)) {
1221                 float obinv[4][4];
1222                 float result_mat[4][4];
1223
1224                 if(ob)
1225                         Mat4Invert(obinv, ob->obmat);
1226                 else
1227                         Mat4One(obinv);
1228
1229                 Mat4MulSerie(result_mat, offset,
1230                                  obinv, amd->offset_ob->obmat,
1231      NULL, NULL, NULL, NULL, NULL);
1232                 Mat4CpyMat4(offset, result_mat);
1233         }
1234
1235         if(amd->fit_type == MOD_ARR_FITCURVE && amd->curve_ob) {
1236                 Curve *cu = amd->curve_ob->data;
1237                 if(cu) {
1238                         float tmp_mat[3][3];
1239                         float scale;
1240                         
1241                         object_to_mat3(amd->curve_ob, tmp_mat);
1242                         scale = Mat3ToScalef(tmp_mat);
1243                                 
1244                         if(!cu->path) {
1245                                 cu->flag |= CU_PATH; // needed for path & bevlist
1246                                 makeDispListCurveTypes(scene, amd->curve_ob, 0);
1247                         }
1248                         if(cu->path)
1249                                 length = scale*cu->path->totdist;
1250                 }
1251         }
1252
1253         /* calculate the maximum number of copies which will fit within the
1254         prescribed length */
1255         if(amd->fit_type == MOD_ARR_FITLENGTH
1256                   || amd->fit_type == MOD_ARR_FITCURVE) {
1257                 float dist = sqrt(Inpf(offset[3], offset[3]));
1258
1259                 if(dist > 1e-6f)
1260                         /* this gives length = first copy start to last copy end
1261                         add a tiny offset for floating point rounding errors */
1262                         count = (length + 1e-6f) / dist;
1263                 else
1264                         /* if the offset has no translation, just make one copy */
1265                         count = 1;
1266                   }
1267
1268                   if(count < 1)
1269                           count = 1;
1270
1271         /* allocate memory for count duplicates (including original) plus
1272                   * start and end caps
1273         */
1274                   finalVerts = dm->getNumVerts(dm) * count;
1275                   finalEdges = dm->getNumEdges(dm) * count;
1276                   finalFaces = dm->getNumTessFaces(dm) * count;
1277                   if(start_cap) {
1278                           finalVerts += start_cap->getNumVerts(start_cap);
1279                           finalEdges += start_cap->getNumEdges(start_cap);
1280                           finalFaces += start_cap->getNumTessFaces(start_cap);
1281                   }
1282                   if(end_cap) {
1283                           finalVerts += end_cap->getNumVerts(end_cap);
1284                           finalEdges += end_cap->getNumEdges(end_cap);
1285                           finalFaces += end_cap->getNumTessFaces(end_cap);
1286                   }
1287                   result = CDDM_from_template(dm, finalVerts, finalEdges, finalFaces, 0, 0);
1288
1289                   /* calculate the offset matrix of the final copy (for merging) */ 
1290                   Mat4One(final_offset);
1291
1292                   for(j=0; j < count - 1; j++) {
1293                           Mat4MulMat4(tmp_mat, final_offset, offset);
1294                           Mat4CpyMat4(final_offset, tmp_mat);
1295                   }
1296
1297                   numVerts = numEdges = numFaces = 0;
1298                   mvert = CDDM_get_verts(result);
1299
1300                   for (i = 0; i < maxVerts; i++) {
1301                           indexMap[i].merge = -1; /* default to no merge */
1302                           indexMap[i].merge_final = 0; /* default to no merge */
1303                   }
1304
1305                   for (i = 0; i < maxVerts; i++) {
1306                           MVert *inMV;
1307                           MVert *mv = &mvert[numVerts];
1308                           MVert *mv2;
1309                           float co[3];
1310
1311                           inMV = &src_mvert[i];
1312
1313                           DM_copy_vert_data(dm, result, i, numVerts, 1);
1314                           *mv = *inMV;
1315                           numVerts++;
1316
1317                           indexMap[i].new = numVerts - 1;
1318
1319                           VECCOPY(co, mv->co);
1320                 
1321                 /* Attempts to merge verts from one duplicate with verts from the
1322                           * next duplicate which are closer than amd->merge_dist.
1323                           * Only the first such vert pair is merged.
1324                           * If verts are merged in the first duplicate pair, they are merged
1325                           * in all pairs.
1326                 */
1327                           if((count > 1) && (amd->flags & MOD_ARR_MERGE)) {
1328                                   float tmp_co[3];
1329                                   VECCOPY(tmp_co, mv->co);
1330                                   Mat4MulVecfl(offset, tmp_co);
1331
1332                                   for(j = 0; j < maxVerts; j++) {
1333                                           /* if vertex already merged, don't use it */
1334                                           if( indexMap[j].merge != -1 ) continue;
1335
1336                                           inMV = &src_mvert[j];
1337                                           /* if this vert is within merge limit, merge */
1338                                           if(VecLenCompare(tmp_co, inMV->co, amd->merge_dist)) {
1339                                                   indexMap[i].merge = j;
1340
1341                                                   /* test for merging with final copy of merge target */
1342                                                   if(amd->flags & MOD_ARR_MERGEFINAL) {
1343                                                           VECCOPY(tmp_co, inMV->co);
1344                                                           inMV = &src_mvert[i];
1345                                                           Mat4MulVecfl(final_offset, tmp_co);
1346                                                           if(VecLenCompare(tmp_co, inMV->co, amd->merge_dist))
1347                                                                   indexMap[i].merge_final = 1;
1348                                                   }
1349                                                   break;
1350                                           }
1351                                   }
1352                           }
1353
1354                           /* if no merging, generate copies of this vert */
1355                           if(indexMap[i].merge < 0) {
1356                                   for(j=0; j < count - 1; j++) {
1357                                           mv2 = &mvert[numVerts];
1358
1359                                           DM_copy_vert_data(result, result, numVerts - 1, numVerts, 1);
1360                                           *mv2 = *mv;
1361                                           numVerts++;
1362
1363                                           Mat4MulVecfl(offset, co);
1364                                           VECCOPY(mv2->co, co);
1365                                   }
1366                           } else if(indexMap[i].merge != i && indexMap[i].merge_final) {
1367                         /* if this vert is not merging with itself, and it is merging
1368                                   * with the final copy of its merge target, remove the first copy
1369                         */
1370                                   numVerts--;
1371                                   DM_free_vert_data(result, numVerts, 1);
1372                           }
1373                   }
1374
1375                   /* make a hashtable so we can avoid duplicate edges from merging */
1376                   edges = BLI_edgehash_new();
1377
1378                   maxEdges = dm->getNumEdges(dm);
1379                   medge = CDDM_get_edges(result);
1380                   for(i = 0; i < maxEdges; i++) {
1381                           MEdge inMED;
1382                           MEdge med;
1383                           MEdge *med2;
1384                           int vert1, vert2;
1385
1386                           dm->getEdge(dm, i, &inMED);
1387
1388                           med = inMED;
1389                           med.v1 = indexMap[inMED.v1].new;
1390                           med.v2 = indexMap[inMED.v2].new;
1391
1392                 /* if vertices are to be merged with the final copies of their
1393                           * merge targets, calculate that final copy
1394                 */
1395                           if(indexMap[inMED.v1].merge_final) {
1396                                   med.v1 = calc_mapping(indexMap, indexMap[inMED.v1].merge,
1397                                                   count - 1);
1398                           }
1399                           if(indexMap[inMED.v2].merge_final) {
1400                                   med.v2 = calc_mapping(indexMap, indexMap[inMED.v2].merge,
1401                                                   count - 1);
1402                           }
1403
1404                           if(med.v1 == med.v2) continue;
1405
1406                           if (initFlags) {
1407                                   med.flag |= ME_EDGEDRAW | ME_EDGERENDER;
1408                           }
1409
1410                           if(!BLI_edgehash_haskey(edges, med.v1, med.v2)) {
1411                                   DM_copy_edge_data(dm, result, i, numEdges, 1);
1412                                   medge[numEdges] = med;
1413                                   numEdges++;
1414
1415                                   BLI_edgehash_insert(edges, med.v1, med.v2, NULL);
1416                           }
1417
1418                           for(j = 1; j < count; j++)
1419                           {
1420                                   vert1 = calc_mapping(indexMap, inMED.v1, j);
1421                                   vert2 = calc_mapping(indexMap, inMED.v2, j);
1422                                   /* avoid duplicate edges */
1423                                   if(!BLI_edgehash_haskey(edges, vert1, vert2)) {
1424                                           med2 = &medge[numEdges];
1425
1426                                           DM_copy_edge_data(dm, result, i, numEdges, 1);
1427                                           *med2 = med;
1428                                           numEdges++;
1429
1430                                           med2->v1 = vert1;
1431                                           med2->v2 = vert2;
1432
1433                                           BLI_edgehash_insert(edges, med2->v1, med2->v2, NULL);
1434                                   }
1435                           }
1436                   }
1437
1438                   maxFaces = dm->getNumTessFaces(dm);
1439                   mface = CDDM_get_tessfaces(result);
1440                   for (i=0; i < maxFaces; i++) {
1441                           MFace inMF;
1442                           MFace *mf = &mface[numFaces];
1443
1444                           dm->getTessFace(dm, i, &inMF);
1445
1446                           DM_copy_tessface_data(dm, result, i, numFaces, 1);
1447                           *mf = inMF;
1448
1449                           mf->v1 = indexMap[inMF.v1].new;
1450                           mf->v2 = indexMap[inMF.v2].new;
1451                           mf->v3 = indexMap[inMF.v3].new;
1452                           if(inMF.v4)
1453                                   mf->v4 = indexMap[inMF.v4].new;
1454
1455                 /* if vertices are to be merged with the final copies of their
1456                           * merge targets, calculate that final copy
1457                 */
1458                           if(indexMap[inMF.v1].merge_final)
1459                                   mf->v1 = calc_mapping(indexMap, indexMap[inMF.v1].merge, count-1);
1460                           if(indexMap[inMF.v2].merge_final)
1461                                   mf->v2 = calc_mapping(indexMap, indexMap[inMF.v2].merge, count-1);
1462                           if(indexMap[inMF.v3].merge_final)
1463                                   mf->v3 = calc_mapping(indexMap, indexMap[inMF.v3].merge, count-1);
1464                           if(inMF.v4 && indexMap[inMF.v4].merge_final)
1465                                   mf->v4 = calc_mapping(indexMap, indexMap[inMF.v4].merge, count-1);
1466
1467                           if(test_index_face(mf, &result->faceData, numFaces, inMF.v4?4:3) < 3)
1468                                   continue;
1469
1470                           numFaces++;
1471
1472                           /* if the face has fewer than 3 vertices, don't create it */
1473                           if(mf->v3 == 0 || (mf->v1 && (mf->v1 == mf->v3 || mf->v1 == mf->v4))) {
1474                                   numFaces--;
1475                                   DM_free_face_data(result, numFaces, 1);
1476                           }
1477
1478                           for(j = 1; j < count; j++)
1479                           {
1480                                   MFace *mf2 = &mface[numFaces];
1481
1482                                   DM_copy_tessface_data(dm, result, i, numFaces, 1);
1483                                   *mf2 = *mf;
1484
1485                                   mf2->v1 = calc_mapping(indexMap, inMF.v1, j);
1486                                   mf2->v2 = calc_mapping(indexMap, inMF.v2, j);
1487                                   mf2->v3 = calc_mapping(indexMap, inMF.v3, j);
1488                                   if (inMF.v4)
1489                                           mf2->v4 = calc_mapping(indexMap, inMF.v4, j);
1490
1491                                   test_index_face(mf2, &result->faceData, numFaces, inMF.v4?4:3);
1492                                   numFaces++;
1493
1494                                   /* if the face has fewer than 3 vertices, don't create it */
1495                                   if(mf2->v3 == 0 || (mf2->v1 && (mf2->v1 == mf2->v3 || mf2->v1 ==
1496                                                                  mf2->v4))) {
1497                                           numFaces--;
1498                                           DM_free_face_data(result, numFaces, 1);
1499                                                                  }
1500                           }
1501                   }
1502
1503                   /* add start and end caps */
1504                   if(start_cap) {
1505                           float startoffset[4][4];
1506                           MVert *cap_mvert;
1507                           MEdge *cap_medge;
1508                           MFace *cap_mface;
1509                           int *origindex;
1510                           int *vert_map;
1511                           int capVerts, capEdges, capFaces;
1512
1513                           capVerts = start_cap->getNumVerts(start_cap);
1514                           capEdges = start_cap->getNumEdges(start_cap);
1515                           capFaces = start_cap->getNumTessFaces(start_cap);
1516                           cap_mvert = start_cap->getVertArray(start_cap);
1517                           cap_medge = start_cap->getEdgeArray(start_cap);
1518                           cap_mface = start_cap->getTessFaceArray(start_cap);
1519
1520                           Mat4Invert(startoffset, offset);
1521
1522                           vert_map = MEM_callocN(sizeof(*vert_map) * capVerts,
1523                                           "arrayModifier_doArray vert_map");
1524
1525                           origindex = result->getVertDataArray(result, CD_ORIGINDEX);
1526                           for(i = 0; i < capVerts; i++) {
1527                                   MVert *mv = &cap_mvert[i];
1528                                   short merged = 0;
1529
1530                                   if(amd->flags & MOD_ARR_MERGE) {
1531                                           float tmp_co[3];
1532                                           MVert *in_mv;
1533                                           int j;
1534
1535                                           VECCOPY(tmp_co, mv->co);
1536                                           Mat4MulVecfl(startoffset, tmp_co);
1537
1538                                           for(j = 0; j < maxVerts; j++) {
1539                                                   in_mv = &src_mvert[j];
1540                                                   /* if this vert is within merge limit, merge */
1541                                                   if(VecLenCompare(tmp_co, in_mv->co, amd->merge_dist)) {
1542                                                           vert_map[i] = calc_mapping(indexMap, j, 0);
1543                                                           merged = 1;
1544                                                           break;
1545                                                   }
1546                                           }
1547                                   }
1548
1549                                   if(!merged) {
1550                                           DM_copy_vert_data(start_cap, result, i, numVerts, 1);
1551                                           mvert[numVerts] = *mv;
1552                                           Mat4MulVecfl(startoffset, mvert[numVerts].co);
1553                                           origindex[numVerts] = ORIGINDEX_NONE;
1554
1555                                           vert_map[i] = numVerts;
1556
1557                                           numVerts++;
1558                                   }
1559                           }
1560                           origindex = result->getEdgeDataArray(result, CD_ORIGINDEX);
1561                           for(i = 0; i < capEdges; i++) {
1562                                   int v1, v2;
1563
1564                                   v1 = vert_map[cap_medge[i].v1];
1565                                   v2 = vert_map[cap_medge[i].v2];
1566
1567                                   if(!BLI_edgehash_haskey(edges, v1, v2)) {
1568                                           DM_copy_edge_data(start_cap, result, i, numEdges, 1);
1569                                           medge[numEdges] = cap_medge[i];
1570                                           medge[numEdges].v1 = v1;
1571                                           medge[numEdges].v2 = v2;
1572                                           origindex[numEdges] = ORIGINDEX_NONE;
1573
1574                                           numEdges++;
1575                                   }
1576                           }
1577                           origindex = result->getTessFaceDataArray(result, CD_ORIGINDEX);
1578                           for(i = 0; i < capFaces; i++) {
1579                                   DM_copy_tessface_data(start_cap, result, i, numFaces, 1);
1580                                   mface[numFaces] = cap_mface[i];
1581                                   mface[numFaces].v1 = vert_map[mface[numFaces].v1];
1582                                   mface[numFaces].v2 = vert_map[mface[numFaces].v2];
1583                                   mface[numFaces].v3 = vert_map[mface[numFaces].v3];
1584                                   if(mface[numFaces].v4) {
1585                                           mface[numFaces].v4 = vert_map[mface[numFaces].v4];
1586
1587                                           test_index_face(&mface[numFaces], &result->faceData,
1588                                                           numFaces, 4);
1589                                   }
1590                                   else
1591                                   {
1592                                           test_index_face(&mface[numFaces], &result->faceData,
1593                                                           numFaces, 3);
1594                                   }
1595
1596                                   origindex[numFaces] = ORIGINDEX_NONE;
1597
1598                                   numFaces++;
1599                           }
1600
1601                           MEM_freeN(vert_map);
1602                           start_cap->release(start_cap);
1603                   }
1604
1605                   if(end_cap) {
1606                           float endoffset[4][4];
1607                           MVert *cap_mvert;
1608                           MEdge *cap_medge;
1609                           MFace *cap_mface;
1610                           int *origindex;
1611                           int *vert_map;
1612                           int capVerts, capEdges, capFaces;
1613
1614                           capVerts = end_cap->getNumVerts(end_cap);
1615                           capEdges = end_cap->getNumEdges(end_cap);
1616                           capFaces = end_cap->getNumTessFaces(end_cap);
1617                           cap_mvert = end_cap->getVertArray(end_cap);
1618                           cap_medge = end_cap->getEdgeArray(end_cap);
1619                           cap_mface = end_cap->getTessFaceArray(end_cap);
1620
1621                           Mat4MulMat4(endoffset, final_offset, offset);
1622
1623                           vert_map = MEM_callocN(sizeof(*vert_map) * capVerts,
1624                                           "arrayModifier_doArray vert_map");
1625
1626                           origindex = result->getVertDataArray(result, CD_ORIGINDEX);
1627                           for(i = 0; i < capVerts; i++) {
1628                                   MVert *mv = &cap_mvert[i];
1629                                   short merged = 0;
1630
1631                                   if(amd->flags & MOD_ARR_MERGE) {
1632                                           float tmp_co[3];
1633                                           MVert *in_mv;
1634                                           int j;
1635
1636                                           VECCOPY(tmp_co, mv->co);
1637                                           Mat4MulVecfl(offset, tmp_co);
1638
1639                                           for(j = 0; j < maxVerts; j++) {
1640                                                   in_mv = &src_mvert[j];
1641                                                   /* if this vert is within merge limit, merge */
1642                                                   if(VecLenCompare(tmp_co, in_mv->co, amd->merge_dist)) {
1643                                                           vert_map[i] = calc_mapping(indexMap, j, count - 1);
1644                                                           merged = 1;
1645                                                           break;
1646                                                   }
1647                                           }
1648                                   }
1649
1650                                   if(!merged) {
1651                                           DM_copy_vert_data(end_cap, result, i, numVerts, 1);
1652                                           mvert[numVerts] = *mv;
1653                                           Mat4MulVecfl(endoffset, mvert[numVerts].co);
1654                                           origindex[numVerts] = ORIGINDEX_NONE;
1655
1656                                           vert_map[i] = numVerts;
1657
1658                                           numVerts++;
1659                                   }
1660                           }
1661                           origindex = result->getEdgeDataArray(result, CD_ORIGINDEX);
1662                           for(i = 0; i < capEdges; i++) {
1663                                   int v1, v2;
1664
1665                                   v1 = vert_map[cap_medge[i].v1];
1666                                   v2 = vert_map[cap_medge[i].v2];
1667
1668                                   if(!BLI_edgehash_haskey(edges, v1, v2)) {
1669                                           DM_copy_edge_data(end_cap, result, i, numEdges, 1);
1670                                           medge[numEdges] = cap_medge[i];
1671                                           medge[numEdges].v1 = v1;
1672                                           medge[numEdges].v2 = v2;
1673                                           origindex[numEdges] = ORIGINDEX_NONE;
1674
1675                                           numEdges++;
1676                                   }
1677                           }
1678                           origindex = result->getTessFaceDataArray(result, CD_ORIGINDEX);
1679                           for(i = 0; i < capFaces; i++) {
1680                                   DM_copy_tessface_data(end_cap, result, i, numFaces, 1);
1681                                   mface[numFaces] = cap_mface[i];
1682                                   mface[numFaces].v1 = vert_map[mface[numFaces].v1];
1683                                   mface[numFaces].v2 = vert_map[mface[numFaces].v2];
1684                                   mface[numFaces].v3 = vert_map[mface[numFaces].v3];
1685                                   if(mface[numFaces].v4) {
1686                                           mface[numFaces].v4 = vert_map[mface[numFaces].v4];
1687
1688                                           test_index_face(&mface[numFaces], &result->faceData,
1689                                                           numFaces, 4);
1690                                   }
1691                                   else
1692                                   {
1693                                           test_index_face(&mface[numFaces], &result->faceData,
1694                                                           numFaces, 3);
1695                                   }
1696                                   origindex[numFaces] = ORIGINDEX_NONE;
1697
1698                                   numFaces++;
1699                           }
1700
1701                           MEM_freeN(vert_map);
1702                           end_cap->release(end_cap);
1703                   }
1704
1705                   BLI_edgehash_free(edges, NULL);
1706                   MEM_freeN(indexMap);
1707
1708                   CDDM_lower_num_verts(result, numVerts);
1709                   CDDM_lower_num_edges(result, numEdges);
1710                   CDDM_lower_num_faces(result, numFaces);
1711                 
1712                   CDDM_tessfaces_to_faces(result);
1713
1714                   return result;
1715 }
1716
1717 static DerivedMesh *arrayModifier_applyModifier(
1718                 ModifierData *md, Object *ob, DerivedMesh *derivedData,
1719   int useRenderParams, int isFinalCalc)
1720 {
1721         DerivedMesh *result;
1722         ArrayModifierData *amd = (ArrayModifierData*) md;
1723
1724         result = arrayModifier_doArray(amd, md->scene, ob, derivedData, 0);
1725
1726         if(result != derivedData)
1727                 CDDM_calc_normals(result);
1728
1729         return result;
1730 }
1731
1732 static DerivedMesh *arrayModifier_applyModifierEM(
1733                 ModifierData *md, Object *ob, BMEditMesh *editData,
1734   DerivedMesh *derivedData)
1735 {
1736         return arrayModifier_applyModifier(md, ob, derivedData, 0, 1);
1737 }
1738 #endif
1739
1740 DerivedMesh *arrayModifier_applyModifier(ModifierData *md, Object *ob, 
1741                                          DerivedMesh *derivedData,
1742                                          int useRenderParams, int isFinalCalc);
1743 DerivedMesh *arrayModifier_applyModifierEM(ModifierData *md, Object *ob,
1744                                            BMEditMesh *editData, 
1745                                            DerivedMesh *derivedData);
1746
1747 /* Mirror */
1748
1749 static void mirrorModifier_initData(ModifierData *md)
1750 {
1751         MirrorModifierData *mmd = (MirrorModifierData*) md;
1752
1753         mmd->flag |= (MOD_MIR_AXIS_X | MOD_MIR_VGROUP);
1754         mmd->tolerance = 0.001;
1755         mmd->mirror_ob = NULL;
1756 }
1757
1758 static void mirrorModifier_copyData(ModifierData *md, ModifierData *target)
1759 {
1760         MirrorModifierData *mmd = (MirrorModifierData*) md;
1761         MirrorModifierData *tmmd = (MirrorModifierData*) target;
1762
1763         tmmd->axis = mmd->axis;
1764         tmmd->flag = mmd->flag;
1765         tmmd->tolerance = mmd->tolerance;
1766         tmmd->mirror_ob = mmd->mirror_ob;;
1767 }
1768
1769 static void mirrorModifier_foreachObjectLink(
1770                                              ModifierData *md, Object *ob,
1771           void (*walk)(void *userData, Object *ob, Object **obpoin),
1772                  void *userData)
1773 {
1774         MirrorModifierData *mmd = (MirrorModifierData*) md;
1775
1776         walk(userData, ob, &mmd->mirror_ob);
1777 }
1778
1779 static void mirrorModifier_updateDepgraph(ModifierData *md, DagForest *forest, Scene *scene,
1780                                           Object *ob, DagNode *obNode)
1781 {
1782         MirrorModifierData *mmd = (MirrorModifierData*) md;
1783
1784         if(mmd->mirror_ob) {
1785                 DagNode *latNode = dag_get_node(forest, mmd->mirror_ob);
1786
1787                 dag_add_relation(forest, latNode, obNode,
1788                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Mirror Modifier");
1789         }
1790 }
1791
1792 /* finds the best possible flipped name. For renaming; check for unique names afterwards */
1793 /* if strip_number: removes number extensions */
1794 static void vertgroup_flip_name (char *name, int strip_number)
1795 {
1796         int     len;
1797         char    prefix[128]={""};   /* The part before the facing */
1798         char    suffix[128]={""};   /* The part after the facing */
1799         char    replace[128]={""};  /* The replacement string */
1800         char    number[128]={""};   /* The number extension string */
1801         char    *index=NULL;
1802
1803         len= strlen(name);
1804         if(len<3) return; // we don't do names like .R or .L
1805
1806         /* We first check the case with a .### extension, let's find the last period */
1807         if(isdigit(name[len-1])) {
1808                 index= strrchr(name, '.'); // last occurrance
1809                 if (index && isdigit(index[1]) ) { // doesnt handle case bone.1abc2 correct..., whatever!
1810                         if(strip_number==0) 
1811                                 strcpy(number, index);
1812                         *index= 0;
1813                         len= strlen(name);
1814                 }
1815         }
1816
1817         strcpy (prefix, name);
1818
1819 #define IS_SEPARATOR(a) ((a)=='.' || (a)==' ' || (a)=='-' || (a)=='_')
1820
1821         /* first case; separator . - _ with extensions r R l L  */
1822         if( IS_SEPARATOR(name[len-2]) ) {
1823                 switch(name[len-1]) {
1824                         case 'l':
1825                                 prefix[len-1]= 0;
1826                                 strcpy(replace, "r");
1827                                 break;
1828                         case 'r':
1829                                 prefix[len-1]= 0;
1830                                 strcpy(replace, "l");
1831                                 break;
1832                         case 'L':
1833                                 prefix[len-1]= 0;
1834                                 strcpy(replace, "R");
1835                                 break;
1836                         case 'R':
1837                                 prefix[len-1]= 0;
1838                                 strcpy(replace, "L");
1839                                 break;
1840                 }
1841         }
1842         /* case; beginning with r R l L , with separator after it */
1843         else if( IS_SEPARATOR(name[1]) ) {
1844                 switch(name[0]) {
1845                         case 'l':
1846                                 strcpy(replace, "r");
1847                                 strcpy(suffix, name+1);
1848                                 prefix[0]= 0;
1849                                 break;
1850                         case 'r':
1851                                 strcpy(replace, "l");
1852                                 strcpy(suffix, name+1);
1853                                 prefix[0]= 0;
1854                                 break;
1855                         case 'L':
1856                                 strcpy(replace, "R");
1857                                 strcpy(suffix, name+1);
1858                                 prefix[0]= 0;
1859                                 break;
1860                         case 'R':
1861                                 strcpy(replace, "L");
1862                                 strcpy(suffix, name+1);
1863                                 prefix[0]= 0;
1864                                 break;
1865                 }
1866         }
1867         else if(len > 5) {
1868                 /* hrms, why test for a separator? lets do the rule 'ultimate left or right' */
1869                 index = BLI_strcasestr(prefix, "right");
1870                 if (index==prefix || index==prefix+len-5) {
1871                         if(index[0]=='r') 
1872                                 strcpy (replace, "left");
1873                         else {
1874                                 if(index[1]=='I') 
1875                                         strcpy (replace, "LEFT");
1876                                 else
1877                                         strcpy (replace, "Left");
1878                         }
1879                         *index= 0;
1880                         strcpy (suffix, index+5);
1881                 }
1882                 else {
1883                         index = BLI_strcasestr(prefix, "left");
1884                         if (index==prefix || index==prefix+len-4) {
1885                                 if(index[0]=='l') 
1886                                         strcpy (replace, "right");
1887                                 else {
1888                                         if(index[1]=='E') 
1889                                                 strcpy (replace, "RIGHT");
1890                                         else
1891                                                 strcpy (replace, "Right");
1892                                 }
1893                                 *index= 0;
1894                                 strcpy (suffix, index+4);
1895                         }
1896                 }
1897         }
1898
1899 #undef IS_SEPARATOR
1900
1901         sprintf (name, "%s%s%s%s", prefix, replace, suffix, number);
1902 }
1903
1904 #if 0
1905 static DerivedMesh *doMirrorOnAxis(MirrorModifierData *mmd,
1906                 Object *ob,
1907                 DerivedMesh *dm,
1908                 int initFlags,
1909                 int axis)
1910 {
1911         int i;
1912         float tolerance = mmd->tolerance;
1913         DerivedMesh *result;
1914         int numVerts, numEdges, numFaces;
1915         int maxVerts = dm->getNumVerts(dm);
1916         int maxEdges = dm->getNumEdges(dm);
1917         int maxFaces = dm->getNumTessFaces(dm);
1918         int vector_size=0, j, a, b;
1919         bDeformGroup *def, *defb;
1920         bDeformGroup **vector_def = NULL;
1921         int (*indexMap)[2];
1922         float mtx[4][4], imtx[4][4];
1923
1924         numVerts = numEdges = numFaces = 0;
1925
1926         indexMap = MEM_mallocN(sizeof(*indexMap) * maxVerts, "indexmap");
1927
1928         result = CDDM_from_template(dm, maxVerts * 2, maxEdges * 2, maxFaces * 2, 0, 0);
1929
1930
1931         if (mmd->flag & MOD_MIR_VGROUP) {
1932                 /* calculate the number of deformedGroups */
1933                 for(vector_size = 0, def = ob->defbase.first; def;
1934                     def = def->next, vector_size++);
1935
1936                 /* load the deformedGroups for fast access */
1937                 vector_def =
1938                     (bDeformGroup **)MEM_mallocN(sizeof(bDeformGroup*) * vector_size,
1939                                                  "group_index");
1940                 for(a = 0, def = ob->defbase.first; def; def = def->next, a++) {
1941                         vector_def[a] = def;
1942                 }
1943         }
1944
1945         if (mmd->mirror_ob) {
1946                 float obinv[4][4];
1947                 
1948                 Mat4Invert(obinv, mmd->mirror_ob->obmat);
1949                 Mat4MulMat4(mtx, ob->obmat, obinv);
1950                 Mat4Invert(imtx, mtx);
1951         }
1952
1953         for(i = 0; i < maxVerts; i++) {
1954                 MVert inMV;
1955                 MVert *mv = CDDM_get_vert(result, numVerts);
1956                 int isShared;
1957                 float co[3];
1958                 
1959                 dm->getVert(dm, i, &inMV);
1960                 
1961                 VecCopyf(co, inMV.co);
1962                 
1963                 if (mmd->mirror_ob) {
1964                         VecMat4MulVecfl(co, mtx, co);
1965                 }
1966                 isShared = ABS(co[axis])<=tolerance;
1967                 
1968                 /* Because the topology result (# of vertices) must be the same if
1969                 * the mesh data is overridden by vertex cos, have to calc sharedness
1970                 * based on original coordinates. This is why we test before copy.
1971                 */
1972                 DM_copy_vert_data(dm, result, i, numVerts, 1);
1973                 *mv = inMV;
1974                 numVerts++;
1975                 
1976                 indexMap[i][0] = numVerts - 1;
1977                 indexMap[i][1] = !isShared;
1978                 
1979                 if(isShared) {
1980                         co[axis] = 0;
1981                         if (mmd->mirror_ob) {
1982                                 VecMat4MulVecfl(co, imtx, co);
1983                         }
1984                         VecCopyf(mv->co, co);
1985                         
1986                         mv->flag |= ME_VERT_MERGED;
1987                 } else {
1988                         MVert *mv2 = CDDM_get_vert(result, numVerts);
1989                         MDeformVert *dvert = NULL;
1990                         
1991                         DM_copy_vert_data(dm, result, i, numVerts, 1);
1992                         *mv2 = *mv;
1993                         
1994                         co[axis] = -co[axis];
1995                         if (mmd->mirror_ob) {
1996                                 VecMat4MulVecfl(co, imtx, co);
1997                         }
1998                         VecCopyf(mv2->co, co);
1999                         
2000                         if (mmd->flag & MOD_MIR_VGROUP){
2001                                 dvert = DM_get_vert_data(result, numVerts, CD_MDEFORMVERT);
2002                                 
2003                                 if (dvert)
2004                                 {
2005                                         for(j = 0; j < dvert[0].totweight; ++j)
2006                                         {
2007                                                 char tmpname[32];
2008                                                 
2009                                                 if(dvert->dw[j].def_nr < 0 ||
2010                                                    dvert->dw[j].def_nr >= vector_size)
2011                                                         continue;
2012                                                 
2013                                                 def = vector_def[dvert->dw[j].def_nr];
2014                                                 strcpy(tmpname, def->name);
2015                                                 vertgroup_flip_name(tmpname,0);
2016                                                 
2017                                                 for(b = 0, defb = ob->defbase.first; defb;
2018                                                     defb = defb->next, b++)
2019                                                 {
2020                                                         if(!strcmp(defb->name, tmpname))
2021                                                         {
2022                                                                 dvert->dw[j].def_nr = b;
2023                                                                 break;
2024                                                         }
2025                                                 }
2026                                         }
2027                                 }
2028                         }
2029                         
2030                         numVerts++;
2031                 }
2032         }
2033
2034         for(i = 0; i < maxEdges; i++) {
2035                 MEdge inMED;
2036                 MEdge *med = CDDM_get_edge(result, numEdges);
2037                 
2038                 dm->getEdge(dm, i, &inMED);
2039                 
2040                 DM_copy_edge_data(dm, result, i, numEdges, 1);
2041                 *med = inMED;
2042                 numEdges++;
2043                 
2044                 med->v1 = indexMap[inMED.v1][0];
2045                 med->v2 = indexMap[inMED.v2][0];
2046                 if(initFlags)
2047                         med->flag |= ME_EDGEDRAW | ME_EDGERENDER;
2048                 
2049                 if(indexMap[inMED.v1][1] || indexMap[inMED.v2][1]) {
2050                         MEdge *med2 = CDDM_get_edge(result, numEdges);
2051                         
2052                         DM_copy_edge_data(dm, result, i, numEdges, 1);
2053                         *med2 = *med;
2054                         numEdges++;
2055                         
2056                         med2->v1 += indexMap[inMED.v1][1];
2057                         med2->v2 += indexMap[inMED.v2][1];
2058                 }
2059         }
2060
2061         for(i = 0; i < maxFaces; i++) {
2062                 MFace inMF;
2063                 MFace *mf = CDDM_get_tessface(result, numFaces);
2064                 
2065                 dm->getTessFace(dm, i, &inMF);
2066                 
2067                 DM_copy_tessface_data(dm, result, i, numFaces, 1);
2068                 *mf = inMF;
2069                 numFaces++;
2070                 
2071                 mf->v1 = indexMap[inMF.v1][0];
2072                 mf->v2 = indexMap[inMF.v2][0];
2073                 mf->v3 = indexMap[inMF.v3][0];
2074                 mf->v4 = indexMap[inMF.v4][0];
2075                 
2076                 if(indexMap[inMF.v1][1]
2077                                  || indexMap[inMF.v2][1]
2078                                  || indexMap[inMF.v3][1]
2079                                  || (mf->v4 && indexMap[inMF.v4][1])) {
2080                         MFace *mf2 = CDDM_get_tessface(result, numFaces);
2081                         static int corner_indices[4] = {2, 1, 0, 3};
2082                         
2083                         DM_copy_tessface_data(dm, result, i, numFaces, 1);
2084                         *mf2 = *mf;
2085                         
2086                         mf2->v1 += indexMap[inMF.v1][1];
2087                         mf2->v2 += indexMap[inMF.v2][1];
2088                         mf2->v3 += indexMap[inMF.v3][1];
2089                         if(inMF.v4) mf2->v4 += indexMap[inMF.v4][1];
2090                         
2091                         /* mirror UVs if enabled */
2092                         if(mmd->flag & (MOD_MIR_MIRROR_U | MOD_MIR_MIRROR_V)) {
2093                                 MTFace *tf = result->getTessFaceData(result, numFaces, CD_MTFACE);
2094                                 if(tf) {
2095                                         int j;
2096                                         for(j = 0; j < 4; ++j) {
2097                                                 if(mmd->flag & MOD_MIR_MIRROR_U)
2098                                                         tf->uv[j][0] = 1.0f - tf->uv[j][0];
2099                                                 if(mmd->flag & MOD_MIR_MIRROR_V)
2100                                                         tf->uv[j][1] = 1.0f - tf->uv[j][1];
2101                                         }
2102                                 }
2103                         }
2104                         
2105                         /* Flip face normal */
2106                         SWAP(int, mf2->v1, mf2->v3);
2107                         DM_swap_tessface_data(result, numFaces, corner_indices);
2108                         
2109                         test_index_face(mf2, &result->faceData, numFaces, inMF.v4?4:3);
2110                         numFaces++;
2111                 }
2112         }
2113
2114         if (vector_def) MEM_freeN(vector_def);
2115
2116         MEM_freeN(indexMap);
2117
2118         CDDM_lower_num_verts(result, numVerts);
2119         CDDM_lower_num_edges(result, numEdges);
2120         CDDM_lower_num_faces(result, numFaces);
2121
2122         CDDM_tessfaces_to_faces(result);
2123
2124         return result;
2125 }
2126 #endif
2127
2128 DerivedMesh *doMirrorOnAxis(MirrorModifierData *mmd,
2129                 Object *ob,
2130                 DerivedMesh *dm,
2131                 int initFlags,
2132                 int axis);
2133 static DerivedMesh *mirrorModifier__doMirror(MirrorModifierData *mmd,
2134                                             Object *ob, DerivedMesh *dm,
2135                                                 int initFlags)
2136 {
2137         DerivedMesh *result = dm;
2138
2139         /* check which axes have been toggled and mirror accordingly */
2140         if(mmd->flag & MOD_MIR_AXIS_X) {
2141                 result = doMirrorOnAxis(mmd, ob, result, initFlags, 0);
2142         }
2143         if(mmd->flag & MOD_MIR_AXIS_Y) {
2144                 DerivedMesh *tmp = result;
2145                 result = doMirrorOnAxis(mmd, ob, result, initFlags, 1);
2146                 if(tmp != dm) tmp->release(tmp); /* free intermediate results */
2147         }
2148         if(mmd->flag & MOD_MIR_AXIS_Z) {
2149                 DerivedMesh *tmp = result;
2150                 result = doMirrorOnAxis(mmd, ob, result, initFlags, 2);
2151                 if(tmp != dm) tmp->release(tmp); /* free intermediate results */
2152         }
2153
2154         return result;
2155 }
2156
2157 static DerivedMesh *mirrorModifier_applyModifier(
2158                 ModifierData *md, Object *ob, DerivedMesh *derivedData,
2159   int useRenderParams, int isFinalCalc)
2160 {
2161         DerivedMesh *result;
2162         MirrorModifierData *mmd = (MirrorModifierData*) md;
2163
2164         result = mirrorModifier__doMirror(mmd, ob, derivedData, 0);
2165
2166         if(result != derivedData)
2167                 CDDM_calc_normals(result);
2168         
2169         return result;
2170 }
2171
2172 static DerivedMesh *mirrorModifier_applyModifierEM(
2173                 ModifierData *md, Object *ob, BMEditMesh *editData,
2174   DerivedMesh *derivedData)
2175 {
2176         return mirrorModifier_applyModifier(md, ob, derivedData, 0, 1);
2177 }
2178
2179 /* EdgeSplit */
2180 /* EdgeSplit modifier: Splits edges in the mesh according to sharpness flag
2181  * or edge angle (can be used to achieve autosmoothing)
2182 */
2183
2184 /*new cddm-based edge split code*/
2185 typedef struct VertUser {
2186         int ov, v, done;
2187         ListBase users;
2188 } VertUser;
2189
2190 typedef struct EdgeNode {
2191         struct EdgeNode *next, *prev;
2192         struct EdgeData *edge;
2193 } EdgeNode;
2194
2195 typedef struct EdgeData {
2196         EdgeNode v1node, v2node;
2197         VertUser *v1user, *v2user;
2198         float fno[3]; /*used to calculate face angles*/
2199         int has_fno;
2200         int tag;
2201         int v1, v2;
2202         int used;
2203 } EdgeData;
2204
2205 typedef struct MemBase {
2206         BLI_mempool *vertuserpool;
2207 } MemBase;
2208
2209 BM_INLINE EdgeData *edge_get_next(EdgeData *e, int ov) {
2210         if (ov == e->v1)
2211                 return e->v1node.next ? e->v1node.next->edge : NULL;
2212         else return e->v2node.next ? e->v2node.next->edge : NULL;
2213 }
2214
2215 BM_INLINE EdgeNode *edge_get_node(EdgeData *e, int ov)
2216 {
2217         if (ov == e->v1)
2218                 return &e->v1node;
2219         else return &e->v2node;
2220 }
2221
2222 BM_INLINE VertUser *edge_get_vuser(MemBase *b, EdgeData *edge, int ov)
2223 {
2224         if (ov == edge->v1)
2225                 return edge->v1user;
2226         else if (ov == edge->v2)
2227                 return edge->v2user;
2228         else {
2229                 printf("yeek!!\n");
2230                 return NULL;
2231         }
2232 }
2233
2234 BM_INLINE void edge_set_vuser(MemBase *b, EdgeData *e, int ov, VertUser *vu)
2235
2236 {
2237         VertUser *olduser = edge_get_vuser(b, e, ov);
2238
2239         if (vu == olduser)
2240                 return;
2241         
2242         if (olduser)
2243                 BLI_remlink(&olduser->users, ov==e->v1 ? &e->v1node : &e->v2node);
2244         BLI_addtail(&vu->users, ov==e->v1 ? &e->v1node : &e->v2node);
2245
2246         if (ov == e->v1)
2247                 e->v1user = vu;
2248         else e->v2user = vu;
2249 }
2250
2251 BM_INLINE VertUser *new_vuser(MemBase *base)
2252 {
2253         VertUser *vusr = BLI_mempool_calloc(base->vertuserpool);
2254
2255         return vusr;
2256 }
2257
2258 BM_INLINE MemBase *new_membase(void)
2259 {
2260         MemBase *b = MEM_callocN(sizeof(MemBase), "MemBase for edgesplit in modifier.c");
2261         b->vertuserpool = BLI_mempool_create(sizeof(VertUser), 1, 2048);
2262
2263         return b;
2264 }
2265
2266 BM_INLINE void free_membase(MemBase *b)
2267 {
2268         BLI_mempool_destroy(b->vertuserpool);
2269         MEM_freeN(b);
2270 }
2271
2272 BM_INLINE EdgeData *edge_get_first(VertUser *vu)
2273 {
2274         return vu->users.first ? ((EdgeNode*)vu->users.first)->edge : NULL;
2275 }
2276
2277 DerivedMesh *doEdgeSplit(DerivedMesh *dm, EdgeSplitModifierData *emd)
2278 {
2279         DerivedMesh *cddm = CDDM_copy(dm, 0);
2280         MEdge *medge;
2281         BLI_array_declare(medge);
2282         MLoop *mloop, *ml, *prevl;
2283         MPoly *mpoly, *mp;
2284         MVert *mvert;
2285         BLI_array_declare(mvert);
2286         EdgeData *etags, *e, *enext;
2287         BLI_array_declare(etags);
2288         VertUser *vu, *vu2;
2289         MemBase *membase;
2290         CustomData edata, vdata;
2291         int i, j, curv, cure;
2292         float threshold = cos((emd->split_angle + 0.00001) * M_PI / 180.0);
2293         float no[3], edge_angle_cos;
2294
2295         if (!cddm->numVertData || !cddm->numEdgeData)
2296                 return cddm;
2297
2298         membase = new_membase();
2299
2300         etags = MEM_callocN(sizeof(EdgeData)*cddm->numEdgeData, "edgedata tag thingies");
2301         BLI_array_set_length(etags, cddm->numEdgeData);
2302
2303         mvert = cddm->getVertArray(cddm);
2304         BLI_array_set_length(mvert, cddm->numVertData);
2305         medge = cddm->getEdgeArray(cddm);
2306         BLI_array_set_length(medge, cddm->numEdgeData);
2307         mloop = CustomData_get_layer(&cddm->loopData, CD_MLOOP);
2308         mpoly = CustomData_get_layer(&cddm->polyData, CD_MPOLY);
2309
2310         for (i=0; i<cddm->numEdgeData; i++) {
2311                 etags[i].v1 = medge[i].v1;
2312                 etags[i].v2 = medge[i].v2;
2313                 
2314                 etags[i].tag = (medge[i].flag & ME_SHARP) != 0;
2315                 
2316                 etags[i].v1node.edge = etags+i;
2317                 etags[i].v2node.edge = etags+i;
2318         }
2319
2320         if (emd->flags & MOD_EDGESPLIT_FROMANGLE) {
2321                 mp = mpoly;
2322                 for (i=0; i<cddm->numPolyData; i++, mp++) {
2323                         mesh_calc_poly_normal(mp, mloop+mp->loopstart, mvert, no);
2324
2325                         ml = mloop + mp->loopstart;
2326                         for (j=0; j<mp->totloop; j++, ml++) {
2327                                 if (!etags[ml->e].has_fno) {
2328                                         VECCOPY(etags[ml->e].fno, no);
2329                                         etags[ml->e].has_fno = 1;
2330                                 } else if (!etags[ml->e].tag) {
2331                                         edge_angle_cos = INPR(etags[ml->e].fno, no);
2332                                         if (edge_angle_cos < threshold) {
2333                                                 etags[ml->e].tag = 1;
2334                                         }
2335                                 }
2336                         }
2337                 }
2338         }
2339
2340         mp = mpoly;
2341         for (i=0; i<cddm->numPolyData; i++, mp++) {
2342                 ml = mloop + mp->loopstart;
2343                 for (j=0; j<mp->totloop; j++, ml++) {
2344                         if (etags[ml->e].tag)
2345                                 continue;
2346
2347                         prevl = mloop + mp->loopstart + ((j-1)+mp->totloop) % mp->totloop;
2348
2349                         if (!edge_get_vuser(membase, etags+prevl->e, ml->v)) {
2350                                 vu = new_vuser(membase);
2351                                 vu->ov = vu->v = ml->v;
2352                                 edge_set_vuser(membase, etags+prevl->e, ml->v, vu);
2353                         }
2354
2355                         if (!edge_get_vuser(membase, etags+ml->e, ml->v)) {
2356                                 vu = new_vuser(membase);
2357                                 vu->ov = vu->v = ml->v;
2358                                 edge_set_vuser(membase, etags+ml->e, ml->v, vu);
2359                         }
2360
2361                         /*continue if previous edge is tagged*/
2362                         if (etags[prevl->e].tag)
2363                                 continue;
2364
2365                         /*merge together adjacent split vert users*/
2366                         if (edge_get_vuser(membase, etags+prevl->e, ml->v) 
2367                             != edge_get_vuser(membase, etags+ml->e, ml->v))
2368                         {
2369                                 vu = edge_get_vuser(membase, etags+prevl->e, ml->v);
2370                                 vu2 = edge_get_vuser(membase, etags+ml->e, ml->v);
2371
2372                                 /*remove from vu2's users list and add to vu's*/
2373                                 for (e=edge_get_first(vu2); e; e=enext) {
2374                                         enext = edge_get_next(e, ml->v);
2375                                         edge_set_vuser(membase, e, ml->v, vu);
2376                                 }
2377                         }
2378                 }
2379         }
2380
2381         mp = mpoly;
2382         for (i=0; i<cddm->numPolyData; i++, mp++) {
2383                 ml = mloop + mp->loopstart;
2384                 for (j=0; j<mp->totloop; j++, ml++) {
2385                         if (!etags[ml->e].tag)
2386                                 continue;
2387
2388                         prevl = mloop + mp->loopstart + ((j-1)+mp->totloop) % mp->totloop;
2389
2390                         if (!etags[prevl->e].tag) {
2391                                 vu = edge_get_vuser(membase, etags+prevl->e, ml->v);
2392                                 if (!vu) {
2393                                         vu = new_vuser(membase);
2394                                         vu->ov = vu->v = ml->v;
2395                                         edge_set_vuser(membase, etags+prevl->e, ml->v, vu);
2396                                 }
2397
2398                                 edge_set_vuser(membase, etags+ml->e, ml->v, vu);
2399                         } else {
2400                                 vu = new_vuser(membase);
2401                                 vu->ov = vu->v = ml->v;
2402                                 edge_set_vuser(membase, etags+ml->e, ml->v, vu);
2403                         }
2404                 }
2405         }
2406
2407         curv = cddm->numVertData;
2408         cure = cddm->numEdgeData;
2409         mp = mpoly;
2410         for (i=0; i<cddm->numPolyData; i++, mp++) {
2411                 ml = mloop + mp->loopstart;
2412                 for (j=0; j<mp->totloop; j++, ml++) {
2413                         e = etags + ml->e;
2414                         if (e->v1user && !e->v1user->done) {
2415                                 e->v1user->done = 1;
2416                                 BLI_array_growone(mvert);
2417
2418                                 mvert[curv] = mvert[e->v1user->ov];
2419                                 e->v1user->v = curv;
2420
2421                                 curv++;
2422                         }
2423
2424                         if (e->v2user && !e->v2user->done) {
2425                                 e->v2user->done = 1;
2426                                 BLI_array_growone(mvert);
2427
2428                                 mvert[curv] = mvert[e->v2user->ov];
2429                                 e->v2user->v = curv;
2430
2431                                 curv++;
2432                         }
2433
2434                         vu = edge_get_vuser(membase, e, ml->v);
2435                         if (!vu)
2436                                 continue;
2437                         ml->v = vu->v;
2438
2439 #if 0 //BMESH_TODO should really handle edges here, but for now use cddm_calc_edges
2440                         /*ok, now we have to deal with edges. . .*/
2441                         if (etags[ml->e].tag) {
2442                                 if (etags[ml->e].used) {
2443                                         BLI_array_growone(medge);
2444                                         BLI_array_growone(etags);
2445                                         medge[cure] = medge[ml->e];
2446                                         
2447                                         ml->e = cure;
2448                                         etags[cure].used = 1;
2449                                         cure++;
2450                                 }
2451
2452                                 vu = etags[ml->e].v1user;
2453                                 vu2 = etags[ml->e].v2user;
2454                                 
2455                                 if (vu)
2456                                         medge[ml->e].v1 = vu->v;
2457                                 if (vu2)
2458                                         medge[ml->e].v2 = vu2->v;                               
2459                         } else {
2460                                 etags[ml->e].used = 1;
2461
2462                                 if (vu->ov == etags[ml->e].v1)
2463                                         medge[ml->e].v1 = vu->v;
2464                                 else if (vu->ov == etags[ml->e].v2)
2465                                         medge[ml->e].v2 = vu->v;
2466                         }
2467 #endif
2468                 }
2469         }
2470
2471
2472         /*resize customdata arrays and add new medge/mvert arrays*/
2473         vdata = cddm->vertData;
2474         edata = cddm->edgeData;
2475         
2476         /*make sure we don't copy over mvert/medge layers*/
2477         CustomData_set_layer(&vdata, CD_MVERT, NULL);
2478         CustomData_set_layer(&edata, CD_MEDGE, NULL);
2479         CustomData_free_layer_active(&vdata, CD_MVERT, cddm->numVertData);
2480         CustomData_free_layer_active(&edata, CD_MEDGE, cddm->numEdgeData);
2481
2482         memset(&cddm->vertData, 0, sizeof(CustomData));
2483         memset(&cddm->edgeData, 0, sizeof(CustomData));
2484
2485         CustomData_copy(&vdata, &cddm->vertData, CD_MASK_DERIVEDMESH, CD_CALLOC, curv);
2486         CustomData_copy_data(&vdata, &cddm->vertData, 0, 0, cddm->numVertData);
2487         CustomData_free(&vdata, cddm->numVertData);
2488         cddm->numVertData = curv;
2489
2490         CustomData_copy(&edata, &cddm->edgeData, CD_MASK_DERIVEDMESH, CD_CALLOC, cure);
2491         CustomData_copy_data(&edata, &cddm->edgeData, 0, 0, cddm->numEdgeData);
2492         CustomData_free(&edata, cddm->numEdgeData);
2493         cddm->numEdgeData = cure;
2494         
2495         CDDM_set_mvert(cddm, mvert);
2496         CDDM_set_medge(cddm, medge);
2497
2498         free_membase(membase);
2499         MEM_freeN(etags);
2500         
2501         /*edge calculation isn't working correctly, so just brute force it*/
2502         cddm->numEdgeData = 0;
2503         CDDM_calc_edges_poly(cddm);
2504         
2505         cddm->numFaceData = mesh_recalcTesselation(&cddm->faceData, 
2506                 &cddm->loopData, &cddm->polyData, 
2507                 mvert, cddm->numFaceData, 
2508                 cddm->numLoopData, cddm->numPolyData);
2509
2510         CDDM_set_mface(cddm, DM_get_tessface_data_layer(cddm, CD_MFACE));
2511         CDDM_calc_normals(cddm);
2512
2513         return cddm;
2514 }
2515
2516
2517 static void edgesplitModifier_initData(ModifierData *md)
2518 {
2519         EdgeSplitModifierData *emd = (EdgeSplitModifierData*) md;
2520
2521         /* default to 30-degree split angle, sharpness from both angle & flag
2522         */
2523         emd->split_angle = 30;
2524         emd->flags = MOD_EDGESPLIT_FROMANGLE | MOD_EDGESPLIT_FROMFLAG;
2525 }
2526
2527 static void edgesplitModifier_copyData(ModifierData *md, ModifierData *target)
2528 {
2529         EdgeSplitModifierData *emd = (EdgeSplitModifierData*) md;
2530         EdgeSplitModifierData *temd = (EdgeSplitModifierData*) target;
2531
2532         temd->split_angle = emd->split_angle;
2533         temd->flags = emd->flags;
2534 }
2535
2536 static DerivedMesh *edgesplitModifier_do(EdgeSplitModifierData *emd,
2537                                          Object *ob, DerivedMesh *dm)
2538 {
2539         if(!(emd->flags & (MOD_EDGESPLIT_FROMANGLE | MOD_EDGESPLIT_FROMFLAG)))
2540                 return dm;
2541         
2542         return doEdgeSplit(dm, emd);
2543 }
2544
2545 static DerivedMesh *edgesplitModifier_applyModifier(
2546                 ModifierData *md, Object *ob, DerivedMesh *derivedData,
2547   int useRenderParams, int isFinalCalc)
2548 {
2549         DerivedMesh *result;
2550         EdgeSplitModifierData *emd = (EdgeSplitModifierData*) md;
2551
2552         result = edgesplitModifier_do(emd, ob, derivedData);
2553
2554         if(result != derivedData)
2555                 CDDM_calc_normals(result);
2556
2557         return result;
2558 }
2559
2560 static DerivedMesh *edgesplitModifier_applyModifierEM(
2561                 ModifierData *md, Object *ob, BMEditMesh *editData,
2562   DerivedMesh *derivedData)
2563 {
2564         return edgesplitModifier_applyModifier(md, ob, derivedData, 0, 1);
2565 }
2566
2567 /* Bevel */
2568
2569 static void bevelModifier_initData(ModifierData *md)
2570 {
2571         BevelModifierData *bmd = (BevelModifierData*) md;
2572
2573         bmd->value = 0.1f;
2574         bmd->res = 1;
2575         bmd->flags = 0;
2576         bmd->val_flags = 0;
2577         bmd->lim_flags = 0;
2578         bmd->e_flags = 0;
2579         bmd->bevel_angle = 30;
2580         bmd->defgrp_name[0] = '\0';
2581 }
2582
2583 static void bevelModifier_copyData(ModifierData *md, ModifierData *target)
2584 {
2585         BevelModifierData *bmd = (BevelModifierData*) md;
2586         BevelModifierData *tbmd = (BevelModifierData*) target;
2587
2588         tbmd->value = bmd->value;
2589         tbmd->res = bmd->res;
2590         tbmd->flags = bmd->flags;
2591         tbmd->val_flags = bmd->val_flags;
2592         tbmd->lim_flags = bmd->lim_flags;
2593         tbmd->e_flags = bmd->e_flags;
2594         tbmd->bevel_angle = bmd->bevel_angle;
2595         strncpy(tbmd->defgrp_name, bmd->defgrp_name, 32);
2596 }
2597
2598 static CustomDataMask bevelModifier_requiredDataMask(Object *ob, ModifierData *md)
2599 {
2600         BevelModifierData *bmd = (BevelModifierData *)md;
2601         CustomDataMask dataMask = 0;
2602
2603         /* ask for vertexgroups if we need them */
2604         if(bmd->defgrp_name[0]) dataMask |= (1 << CD_MDEFORMVERT);
2605
2606         return dataMask;
2607 }
2608
2609 static DerivedMesh *bevelModifier_applyModifier(
2610                 ModifierData *md, Object *ob, DerivedMesh *derivedData,
2611   int useRenderParams, int isFinalCalc)
2612 {
2613         DerivedMesh *result;
2614         BME_Mesh *bm;
2615
2616         /*bDeformGroup *def;*/
2617         int /*i,*/ options, defgrp_index = -1;
2618         BevelModifierData *bmd = (BevelModifierData*) md;
2619
2620         options = bmd->flags|bmd->val_flags|bmd->lim_flags|bmd->e_flags;
2621
2622         //~ if ((options & BME_BEVEL_VWEIGHT) && bmd->defgrp_name[0]) {
2623                 //~ for (i = 0, def = ob->defbase.first; def; def = def->next, i++) {
2624                         //~ if (!strcmp(def->name, bmd->defgrp_name)) {
2625                                 //~ defgrp_index = i;
2626                                 //~ break;
2627                         //~ }
2628                 //~ }
2629                 //~ if (defgrp_index < 0) {
2630                         //~ options &= ~BME_BEVEL_VWEIGHT;
2631                 //~ }
2632         //~ }
2633
2634         bm = BME_derivedmesh_to_bmesh(derivedData);
2635         BME_bevel(bm,bmd->value,bmd->res,options,defgrp_index,bmd->bevel_angle,NULL);
2636         result = BME_bmesh_to_derivedmesh(bm,derivedData);
2637         BME_free_mesh(bm);
2638
2639         CDDM_calc_normals(result);
2640
2641         return result;
2642 }
2643
2644 static DerivedMesh *bevelModifier_applyModifierEM(
2645                 ModifierData *md, Object *ob, BMEditMesh *editData,
2646   DerivedMesh *derivedData)
2647 {
2648         return bevelModifier_applyModifier(md, ob, derivedData, 0, 1);
2649 }
2650
2651 /* Displace */
2652
2653 static void displaceModifier_initData(ModifierData *md)
2654 {
2655         DisplaceModifierData *dmd = (DisplaceModifierData*) md;
2656
2657         dmd->texture = NULL;
2658         dmd->strength = 1;
2659         dmd->direction = MOD_DISP_DIR_NOR;
2660         dmd->midlevel = 0.5;
2661 }
2662
2663 static void displaceModifier_copyData(ModifierData *md, ModifierData *target)
2664 {
2665         DisplaceModifierData *dmd = (DisplaceModifierData*) md;
2666         DisplaceModifierData *tdmd = (DisplaceModifierData*) target;
2667
2668         tdmd->texture = dmd->texture;
2669         tdmd->strength = dmd->strength;
2670         tdmd->direction = dmd->direction;
2671         strncpy(tdmd->defgrp_name, dmd->defgrp_name, 32);
2672         tdmd->midlevel = dmd->midlevel;
2673         tdmd->texmapping = dmd->texmapping;
2674         tdmd->map_object = dmd->map_object;
2675         strncpy(tdmd->uvlayer_name, dmd->uvlayer_name, 32);
2676 }
2677
2678 static CustomDataMask displaceModifier_requiredDataMask(Object *ob, ModifierData *md)
2679 {
2680         DisplaceModifierData *dmd = (DisplaceModifierData *)md;
2681         CustomDataMask dataMask = 0;
2682
2683         /* ask for vertexgroups if we need them */
2684         if(dmd->defgrp_name[0]) dataMask |= (1 << CD_MDEFORMVERT);
2685
2686         /* ask for UV coordinates if we need them */
2687         if(dmd->texmapping == MOD_DISP_MAP_UV) dataMask |= (1 << CD_MTFACE);
2688
2689         return dataMask;
2690 }
2691
2692 static int displaceModifier_dependsOnTime(ModifierData *md)
2693 {
2694         DisplaceModifierData *dmd = (DisplaceModifierData *)md;
2695
2696         if(dmd->texture)
2697         {
2698                 return BKE_texture_dependsOnTime(dmd->texture);
2699         }
2700         else
2701         {
2702                 return 0;
2703         }
2704 }
2705
2706 static void displaceModifier_foreachObjectLink(ModifierData *md, Object *ob,
2707                                                ObjectWalkFunc walk, void *userData)
2708 {
2709         DisplaceModifierData *dmd = (DisplaceModifierData*) md;
2710
2711         walk(userData, ob, &dmd->map_object);
2712 }
2713
2714 static void displaceModifier_foreachIDLink(ModifierData *md, Object *ob,
2715                                            IDWalkFunc walk, void *userData)
2716 {
2717         DisplaceModifierData *dmd = (DisplaceModifierData*) md;
2718
2719         walk(userData, ob, (ID **)&dmd->texture);
2720
2721         displaceModifier_foreachObjectLink(md, ob, (ObjectWalkFunc)walk, userData);
2722 }
2723
2724 static int displaceModifier_isDisabled(ModifierData *md)
2725 {
2726         DisplaceModifierData *dmd = (DisplaceModifierData*) md;
2727
2728         return !dmd->texture;
2729 }
2730
2731 static void displaceModifier_updateDepgraph(
2732                                             ModifierData *md, DagForest *forest, Scene *scene,
2733          Object *ob, DagNode *obNode)
2734 {
2735         DisplaceModifierData *dmd = (DisplaceModifierData*) md;
2736
2737         if(dmd->map_object) {
2738                 DagNode *curNode = dag_get_node(forest, dmd->map_object);
2739
2740                 dag_add_relation(forest, curNode, obNode,
2741                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Displace Modifier");
2742         }
2743 }
2744
2745 static void validate_layer_name(const CustomData *data, int type, char *name, char *outname)
2746 {
2747         int index = -1;
2748
2749         /* if a layer name was given, try to find that layer */
2750         if(name[0])
2751                 index = CustomData_get_named_layer_index(data, CD_MTFACE, name);
2752
2753         if(index < 0) {
2754                 /* either no layer was specified, or the layer we want has been
2755                 * deleted, so assign the active layer to name
2756                 */
2757                 index = CustomData_get_active_layer_index(data, CD_MTFACE);
2758                 strcpy(outname, data->layers[index].name);
2759         }
2760         else
2761                 strcpy(outname, name);
2762 }
2763
2764 static void get_texture_coords(DisplaceModifierData *dmd, Object *ob,
2765                                DerivedMesh *dm,
2766           float (*co)[3], float (*texco)[3],
2767                   int numVerts)
2768 {
2769         int i;
2770         int texmapping = dmd->texmapping;
2771
2772         if(texmapping == MOD_DISP_MAP_OBJECT) {
2773                 if(dmd->map_object)
2774                         Mat4Invert(dmd->map_object->imat, dmd->map_object->obmat);
2775                 else /* if there is no map object, default to local */
2776                         texmapping = MOD_DISP_MAP_LOCAL;
2777         }
2778
2779         /* UVs need special handling, since they come from faces */
2780         if(texmapping == MOD_DISP_MAP_UV) {
2781                 if(dm->getTessFaceDataArray(dm, CD_MTFACE)) {
2782                         MFace *mface = dm->getTessFaceArray(dm);
2783                         MFace *mf;
2784                         char *done = MEM_callocN(sizeof(*done) * numVerts,
2785                                         "get_texture_coords done");
2786                         int numFaces = dm->getNumTessFaces(dm);
2787                         char uvname[32];
2788                         MTFace *tf;
2789
2790                         validate_layer_name(&dm->faceData, CD_MTFACE, dmd->uvlayer_name, uvname);
2791                         tf = CustomData_get_layer_named(&dm->faceData, CD_MTFACE, uvname);
2792
2793                         /* verts are given the UV from the first face that uses them */
2794                         for(i = 0, mf = mface; i < numFaces; ++i, ++mf, ++tf) {
2795                                 if(!done[mf->v1]) {
2796                                         texco[mf->v1][0] = tf->uv[0][0];
2797                                         texco[mf->v1][1] = tf->uv[0][1];
2798                                         texco[mf->v1][2] = 0;
2799                                         done[mf->v1] = 1;
2800                                 }
2801                                 if(!done[mf->v2]) {
2802                                         texco[mf->v2][0] = tf->uv[1][0];
2803                                         texco[mf->v2][1] = tf->uv[1][1];
2804                                         texco[mf->v2][2] = 0;
2805                                         done[mf->v2] = 1;
2806                                 }
2807                                 if(!done[mf->v3]) {
2808                                         texco[mf->v3][0] = tf->uv[2][0];
2809                                         texco[mf->v3][1] = tf->uv[2][1];
2810                                         texco[mf->v3][2] = 0;
2811                                         done[mf->v3] = 1;
2812                                 }
2813                                 if(!done[mf->v4]) {
2814                                         texco[mf->v4][0] = tf->uv[3][0];
2815                                         texco[mf->v4][1] = tf->uv[3][1];
2816                                         texco[mf->v4][2] = 0;
2817                                         done[mf->v4] = 1;
2818                                 }
2819                         }
2820
2821                         /* remap UVs from [0, 1] to [-1, 1] */
2822                         for(i = 0; i < numVerts; ++i) {
2823                                 texco[i][0] = texco[i][0] * 2 - 1;
2824                                 texco[i][1] = texco[i][1] * 2 - 1;
2825                         }
2826
2827                         MEM_freeN(done);
2828                         return;
2829                 } else /* if there are no UVs, default to local */
2830                         texmapping = MOD_DISP_MAP_LOCAL;
2831         }
2832
2833         for(i = 0; i < numVerts; ++i, ++co, ++texco) {
2834                 switch(texmapping) {
2835                         case MOD_DISP_MAP_LOCAL:
2836                                 VECCOPY(*texco, *co);
2837                                 break;
2838                         case MOD_DISP_MAP_GLOBAL:
2839                                 VECCOPY(*texco, *co);
2840                                 Mat4MulVecfl(ob->obmat, *texco);
2841                                 break;
2842                         case MOD_DISP_MAP_OBJECT:
2843                                 VECCOPY(*texco, *co);
2844                                 Mat4MulVecfl(ob->obmat, *texco);
2845                                 Mat4MulVecfl(dmd->map_object->imat, *texco);
2846                                 break;
2847                 }
2848         }
2849 }
2850
2851 static void get_texture_value(Tex *texture, float *tex_co, TexResult *texres)
2852 {
2853         int result_type;
2854
2855         result_type = multitex_ext(texture, tex_co, NULL,
2856                                    NULL, 1, texres);
2857
2858         /* if the texture gave an RGB value, we assume it didn't give a valid
2859         * intensity, so calculate one (formula from do_material_tex).
2860         * if the texture didn't give an RGB value, copy the intensity across
2861         */
2862         if(result_type & TEX_RGB)
2863                 texres->tin = (0.35 * texres->tr + 0.45 * texres->tg
2864                                 + 0.2 * texres->tb);
2865         else
2866                 texres->tr = texres->tg = texres->tb = texres->tin;
2867 }
2868
2869 /* dm must be a CDDerivedMesh */
2870 static void displaceModifier_do(
2871                                 DisplaceModifierData *dmd, Object *ob,
2872     DerivedMesh *dm, float (*vertexCos)[3], int numVerts)
2873 {
2874         int i;
2875         MVert *mvert;
2876         MDeformVert *dvert = NULL;
2877         int defgrp_index;
2878         float (*tex_co)[3];
2879
2880         if(!dmd->texture) return;
2881
2882         defgrp_index = -1;
2883
2884         if(dmd->defgrp_name[0]) {
2885                 bDeformGroup *def;
2886                 for(i = 0, def = ob->defbase.first; def; def = def->next, i++) {
2887                         if(!strcmp(def->name, dmd->defgrp_name)) {
2888                                 defgrp_index = i;
2889                                 break;
2890                         }
2891                 }
2892         }
2893
2894         mvert = CDDM_get_verts(dm);
2895         if(defgrp_index >= 0)
2896                 dvert = dm->getVertDataArray(dm, CD_MDEFORMVERT);
2897
2898         tex_co = MEM_callocN(sizeof(*tex_co) * numVerts,
2899                              "displaceModifier_do tex_co");
2900         get_texture_coords(dmd, ob, dm, vertexCos, tex_co, numVerts);
2901
2902         for(i = 0; i < numVerts; ++i) {
2903                 TexResult texres;
2904                 float delta = 0, strength = dmd->strength;
2905                 MDeformWeight *def_weight = NULL;
2906
2907                 if(dvert) {
2908                         int j;
2909                         for(j = 0; j < dvert[i].totweight; ++j) {
2910                                 if(dvert[i].dw[j].def_nr == defgrp_index) {
2911                                         def_weight = &dvert[i].dw[j];
2912                                         break;
2913                                 }
2914                         }
2915                         if(!def_weight) continue;
2916                 }
2917
2918                 texres.nor = NULL;
2919                 get_texture_value(dmd->texture, tex_co[i], &texres);
2920
2921                 delta = texres.tin - dmd->midlevel;
2922
2923                 if(def_weight) strength *= def_weight->weight;
2924
2925                 delta *= strength;
2926
2927                 switch(dmd->direction) {
2928                         case MOD_DISP_DIR_X:
2929                                 vertexCos[i][0] += delta;
2930                                 break;
2931                         case MOD_DISP_DIR_Y:
2932                                 vertexCos[i][1] += delta;
2933                                 break;
2934                         case MOD_DISP_DIR_Z:
2935                                 vertexCos[i][2] += delta;
2936                                 break;
2937                         case MOD_DISP_DIR_RGB_XYZ:
2938                                 vertexCos[i][0] += (texres.tr - dmd->midlevel) * strength;
2939                                 vertexCos[i][1] += (texres.tg - dmd->midlevel) * strength;
2940                                 vertexCos[i][2] += (texres.tb - dmd->midlevel) * strength;
2941                                 break;
2942                         case MOD_DISP_DIR_NOR:
2943                                 vertexCos[i][0] += delta * mvert[i].no[0] / 32767.0f;
2944                                 vertexCos[i][1] += delta * mvert[i].no[1] / 32767.0f;
2945                                 vertexCos[i][2] += delta * mvert[i].no[2] / 32767.0f;
2946                                 break;
2947                 }
2948         }
2949
2950         MEM_freeN(tex_co);
2951 }
2952
2953 static void displaceModifier_deformVerts(
2954                                          ModifierData *md, Object *ob, DerivedMesh *derivedData,
2955       float (*vertexCos)[3], int numVerts, int useRenderParams, int isFinalCalc)
2956 {
2957         DerivedMesh *dm;
2958
2959         if(derivedData) dm = CDDM_copy(derivedData, 0);
2960         else if(ob->type==OB_MESH) dm = CDDM_from_mesh(ob->data, ob);
2961         else return;
2962
2963         CDDM_apply_vert_coords(dm, vertexCos);
2964         CDDM_calc_normals(dm);
2965
2966         displaceModifier_do((DisplaceModifierData *)md, ob, dm,
2967                  &nb