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