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