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