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