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