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