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